Raft 알고리즘 배경 지식

등장 배경

싱글 컴퓨터로는 성능 향상에 한계가 있습니다. 만약 그 컴퓨터에 장애가 발생하면, 작동하던 서비스도 중단될 수밖에 없습니다.

이러한 문제를 해결하기 위해 복잡한 연산을 여러 컴퓨터가 나눠서 수행하고, 하나의 컴퓨터가 고장 나더라도 나머지 컴퓨터가 그 작업을 맡아서 처리할 수 있는 분산 환경(Distributed System)이 등장했습니다.

하지만 여러 컴퓨터가 하나의 시스템처럼 동작하기 위해서는, 모든 컴퓨터가 서로 어긋남 없이 하나의 상태를 공유해야 합니다. 이를 해결하기 위해 분산 환경에서 상태를 공유하는 알고리즘이 개발되었고, 이를 합의 알고리즘(Consensus Algorithm)이라고 부릅니다. 여기서 합의란 클라이언트와 서버가 동일한 데이터를 공유하는 상태(동기화)가 되는 것을 의미합니다.

합의 알고리즘은 분산 시스템에서 각 노드가 동일한 데이터 상태를 유지하도록 보장합니다. 이 과정은 다양한 네트워크 장애, 노드 오류, 메시지 지연 등과 같은 문제를 처리하면서 시스템의 일관성과 가용성을 확보하는 데 중요한 역할을 합니다. 대표적인 합의 알고리즘으로는 Paxos, Raft, Zookeeper 등이 있으며, 이들은 모두 시스템의 안정성과 신뢰성을 향상시키는 데 기여하고 있습니다.

Raft는 분산 시스템에서 합의를 형성하는 데 널리 사용되는 알고리즘으로, 특히 이해하기 쉽고 구현하기 용이하도록 설계되었습니다. Raft는 주로 분산 시스템의 일관성과 가용성을 보장하면서, 네트워크 분할 상황에서도 시스템의 복구 가능성을 높이는 것을 목표로 합니다.

Raft 합의 알고리즘

Raft는 주로 세 가지 주요 구성 요소로 작동합니다:

1. 리더 선출 (Leader Election):

   • 시스템 내의 노드 중 하나가 리더가 됩니다. 리더는 로그 복제를 담당하며, 모든 쓰기 요청은 리더를 통해 처리됩니다.
   • 리더는 주기적으로 팔로워들에게 하트비트를 보내어 자신의 리더 자격을 유지합니다.
   • 리더가 실패하면 팔로워 중 하나가 새로운 리더로 선출됩니다.

2. 로그 복제 (Log Replication):

   • 리더는 클라이언트로부터 로그 엔트리를 받아 이를 다른 팔로워 노드에 복제합니다.
   • 대다수의 노드(정족수)가 로그 엔트리를 저장한 후에 커밋된 것으로 간주합니다.
   • 이 과정은 시스템의 일관성을 유지하면서, 노드들이 동일한 상태를 갖도록 보장합니다.

3. 안전성 보장 (Safety):

   • 로그의 일관성을 보장하기 위해, 커밋된 로그는 절대 뒤집히거나 변경되지 않습니다.
   • 새로운 리더는 반드시 최신의 커밋된 로그 상태를 기반으로 리더 자격을 유지해야 합니다.

Raft의 분할내성, 가용성, 일관성

• 일관성 (Consistency): Raft는 시스템의 일관성을 보장합니다. 이는 리더가 결정한 로그가 시스템 내 모든 노드에 동일하게 반영된다는 것을 의미합니다. 시스템의 모든 노드는 항상 같은 상태를 유지하려고 하며, 리더의 로그가 커밋되면 이 상태가 전체 시스템에 퍼지게 됩니다.

• 가용성 (Availability): Raft는 특정 노드(리더)가 정상적으로 작동하면 클라이언트의 요청을 계속해서 처리할 수 있습니다. 하지만 네트워크 분할이나 리더의 장애 상황에서는 일시적으로 가용성이 낮아질 수 있습니다. 리더가 없는 동안에는 쓰기 요청을 처리할 수 없습니다.

• 분할내성 (Partition Tolerance): Raft는 네트워크 분할 상황에서도 시스템을 복구할 수 있습니다. 시스템이 분할되면 두 개의 하위 네트워크로 나뉘게 되고, 각 네트워크는 자체적인 리더를 선출하려고 시도합니다. 이 과정에서 더 많은 노드의 지지를 받은 네트워크만이 유효한 리더를 갖게 되고, 나머지 네트워크는 리더가 없는 상태로 대기합니다. 네트워크가 복구되면 시스템은 다시 정상적인 상태로 돌아갑니다.

Raft의 신뢰성 확보 방안

Raft의 신뢰성을 높이기 위해서는 다음과 같은 방안이 고려될 수 있습니다:

• 정족수 기반의 합의: Raft는 정족수(대다수의 노드)가 로그 복제를 승인해야 합의가 이루어지도록 설계되어 있어, 시스템의 안전성을 보장합니다.

• 로그 일관성 보장: 리더는 로그의 일관성을 유지하기 위해 끊임없이 팔로워에게 하트비트를 전송하여, 팔로워들이 리더의 상태를 유지하도록 합니다.

• 장애 감지 및 복구: 노드의 상태를 주기적으로 모니터링하여 장애를 신속하게 감지하고, 새로운 리더를 빠르게 선출하여 시스템이 정상적으로 동작하도록 합니다.

Raft는 이러한 특징들을 통해 분산 시스템에서의 합의 형성에 신뢰성과 안정성을 제공합니다. 이는 특히 네트워크가 불안정하거나 장애가 발생할 가능성이 있는 환경에서 매우 유용합니다.

Raft 알고리즘에서는 분산 시스템의 모든 노드가 세 가지 상태 중 하나를 가집니다.

Raft의 노드 상태

1. 리더 (Leader):
   • 리더는 클라이언트의 모든 요청을 수신합니다.
   • 로컬에 로그를 기록하고 모든 팔로워에게 로그를 전달합니다.
   • 클라이언트와의 상호작용을 주도하며, 클라이언트의 요청을 처리하고 결과를 반환합니다.
2. 팔로워 (Follower):
   • 클라이언트로부터 받은 요청을 리더에게 리다이렉트합니다.
   • 리더로부터 수신한 요청을 처리하고, 로그를 리더와 동기화합니다.
   • 리더의 명령을 따르며, 주기적으로 리더로부터 하트비트를 받아 리더의 생존을 확인합니다.
3. 후보 (Candidate):
   • 새로운 리더를 선출하기 위해 후보 상태가 됩니다.
   • 팔로워는 리더가 하트비트를 보내지 않으면 일정 시간이 지나 후보가 되어 리더 선출을 시도합니다.
   • 과반수의 노드로부터 투표를 얻으면 리더가 됩니다.

Term의 역할과 기능

Term은 Raft 알고리즘에서 리더 선출 시 할당되는 일종의 일련번호로, 리더의 ID 역할을 합니다. Term은 시스템 내에서 리더의 상태와 그 유효성을 판단하는 중요한 지표로 사용됩니다.

Term의 주요 기능

1. 리더의 ID 역할:

   • Term은 각 리더에게 고유한 ID를 부여하며, 리더가 변경될 때마다 Term이 증가합니다. 이는 리더의 변경 여부를 쉽게 파악할 수 있도록 합니다.

2. 중복 투표 방지:

   • Term은 리더 선출 시 투표의 중복을 방지하는 데 사용됩니다. 노드들은 자신이 알고 있는 최신 Term을 기반으로 투표하며, 이전 Term의 요청은 무시됩니다.

3. 서버 간 통신에서의 역할:

   • Term은 서버 간의 통신 중에 전달되며, 각 노드는 수신한 Term을 기준으로 자신의 Term을 업데이트합니다.

Term의 작업 수행

1. Term 업데이트:

   • 한 서버의 Term이 다른 서버의 Term보다 작을 경우, 해당 서버는 자신의 Term을 최신으로 업데이트합니다. 이는 전체 시스템의 일관성을 유지하는 데 도움을 줍니다.

2. 상태 전환:

   • Candidate 또는 Leader의 Term이 다른 노드보다 작다면, 해당 노드는 자동으로 Follower로 상태를 전환합니다. 이는 최신 정보를 반영하여 잘못된 리더 선출을 방지합니다.

3. 오래된 Term에 대한 요청 거부:

   • 오래된 Term으로 요청이 들어오면, 그 요청은 거부됩니다. 이는 시스템의 일관성과 무결성을 유지하는 데 중요한 역할을 합니다.

이러한 기능을 통해 Raft의 Term은 분산 시스템에서 리더의 안정적인 선출과 상태 일관성을 유지하는 데 핵심적인 역할을 합니다. Term을 이용하여 시스템은 지속적으로 최신 상태를 반영하고, 분산 환경에서의 오류를 최소화합니다.

리더 선출 과정

Raft 알고리즘에서 리더 선출 과정은 다음과 같이 진행됩니다:

1. 초기 상태:

   • 모든 노드는 시스템 시작 시 Follower 상태로 시작합니다.

2. Election Timeout:

   • Follower는 리더의 하트비트를 일정 시간(election timeout) 동안 받지 못하면 Candidate 상태로 전환합니다.
   • Election timeout은 각 노드마다 150ms에서 300ms 사이의 무작위 시간으로 설정되어, 동시에 여러 노드가 Candidate가 되는 것을 방지합니다.

3. Candidate가 되는 과정:

   • Follower는 Candidate가 되면 새로운 선거 기간(Term)을 시작합니다.
   • Candidate는 자신에게 투표하고, 다른 노드들에게 RequestVotes RPC를 보냅니다.

4. 투표 요청:

   • Candidate는 자신에게 한 표를 행사하고, 나머지 노드들에게 투표 요청을 보냅니다.

5. 투표 응답:

   • Follower는 현재 Term 내에 투표한 적이 없을 경우, Candidate의 요청에 응답하여 투표를 합니다.
   • Follower는 투표 후 자신의 election timeout을 초기화합니다.
   • 모든 노드는 Term당 한 번의 투표만 할 수 있습니다.

6. 리더가 되는 조건:

   • Candidate는 과반수 이상의 투표를 받으면 Leader가 됩니다.
   • 리더가 된 노드는 클라이언트의 요청을 수신하고, 다른 노드에 로그를 복제하여 시스템의 일관성을 유지합니다.

이 과정을 통해 Raft는 시스템 내의 모든 노드가 하나의 리더를 선택하고, 그 리더를 통해 일관된 상태를 유지할 수 있도록 보장합니다. 리더는 일정 주기마다 하트비트를 팔로워들에게 보내며, 리더의 상태를 지속적으로 유지합니다. 이로 인해 시스템은 높은 가용성과 신뢰성을 가지게 됩니다.

로그 복제 (Log Replication)

Raft 알고리즘에서 로그 복제는 분산 시스템의 모든 변경 사항이 리더를 통해 처리되고, 각 노드의 로그가 일관되도록 보장하는 중요한 과정입니다. 로그 복제는 리더가 클라이언트의 요청을 처리하고 이를 팔로워 노드에 복제함으로써 이루어집니다.

로그 엔트리 구성 요소

로그 엔트리는 일반적으로 다음 세 가지 정보를 포함합니다:

1. Term:

   • 리더 선출 시 할당되는 1씩 증가하는 일련번호로, 로그의 유효성을 확인하는 데 사용됩니다.

2. Index:

   • 로그가 저장될 때마다 1씩 증가하는 일련번호입니다. 로그의 순서를 결정하며, 인덱스는 1부터 시작합니다.

3. Data:

   • 클라이언트의 요청에 대한 실제 데이터로, 상태 머신에 적용될 명령입니다.

로그 복제 과정

로그 복제 과정은 다음과 같이 진행됩니다:

1. 클라이언트 요청:

   • 클라이언트가 변경 사항을 리더에게 보냅니다.

2. 로그 엔트리 저장:

   • 리더는 받은 변경 사항을 자신의 로그 엔트리에 저장합니다.

3. AppendEntries 메시지 전송:

   • 리더는 다음 하트비트 주기 동안 AppendEntries 메시지를 통해 자신의 로그 엔트리를 모든 팔로워에게 전달합니다.
   • 이 메시지는 새로운 로그 엔트리를 포함하며, 각 팔로워는 이를 수신합니다.

4. 로그 엔트리 저장:

   • AppendEntries 메시지를 받은 팔로워는 새로운 로그 엔트리를 자신의 로그에 저장합니다.
   • 팔로워는 AppendEntriesResponse 메시지를 리더에게 보내, 로그 엔트리 저장 성공을 알립니다.

5. 과반수 응답:

   • 리더는 과반수의 팔로워로부터 성공 응답을 받으면 해당 로그 엔트리를 커밋합니다.
   • 커밋이란 로그 엔트리가 시스템의 영구 상태로 인정되어 클라이언트에게 응답할 준비가 되었다는 것을 의미합니다.

6. 클라이언트 응답:

   • 리더는 자신의 로그 엔트리를 커밋한 후, 클라이언트에게 응답 메시지를 보냅니다. 이는 요청이 성공적으로 처리되었음을 나타냅니다.

7. 팔로워에게 커밋 알림:

   • 리더는 팔로워들에게도 로그 엔트리가 커밋되었음을 알립니다.
   • 커밋 알림을 받은 팔로워들은 자신의 로그 엔트리를 커밋하여 일관된 상태를 유지합니다.

로그 복제의 중요성

• 일관성 유지: 로그 복제는 시스템의 일관성을 유지하는 핵심 메커니즘입니다. 모든 노드가 동일한 로그를 갖도록 보장함으로써, 시스템 전체가 같은 상태를 유지할 수 있게 됩니다.

• 장애 복구: 리더가 실패하더라도 로그 복제를 통해 다른 팔로워들이 일관된 상태를 유지하므로, 새로운 리더가 쉽게 선출되고 시스템을 안정적으로 유지할 수 있습니다.

• 확장성: 로그 복제는 클러스터의 크기를 유연하게 확장할 수 있게 하며, 시스템의 처리 능력을 향상시킵니다.