Paxos 알고리즘은 1989년에 처음 공개되었으며 그리스의 팩소스 섬에서 가상의 입법 합의 시스템에 사용된 후 이름지어졌습니다.
분산 시스템에서 여러 프로세스 간에 하나의 값에 동의하기 위한 프로토콜로서, 동시에 여러 개의 값이 제안되지만, 결국에는 이 중 하나의 값이 선택되도록 하는 것이 골자입니다. 하지만 여러 제안자에 의해 동시에 여러 값의 후보가 제안될 수 있다는 점 때문에 프로토콜의 동작이 복잡해 구현이 어렵다는 단점이 있습니다.
사실 글을 쓰는 저도 100% 이해했다고 말하긴 어렵지만, 아래 영상을 보고 제가 이해한 내용을 최대한 쉽게 풀어써보고자 합니다.
PREPARE : Proposer가 어떤 값을 제안하기 위해 제안번호(ID)를 먼저 Accepter들한테 보냄
PROMISE : Accepter는 제안한 번호(ID)이하의 값을 받지 않겠다고 약속 (ex. 5가오면 5이하의 숫자는 무시됨)
ACCEPT : 다수의 Accepter가 동일한 ID의 PROMISE메세지를 Proposer에게 보냈다면 Proposer는 해당 ID와 VALUE를 Accepter에게 보냄
ACCEPTED : Accepter는 메세지(ID,VALUE)를 받고 ID가 마지막으로 약속한 값인 경우에만 VALUE를 받아들이고 VALUE를 Proposer와 Learner에게 전파한다
만약 마지막으로 약속한 값이 아닐경우 Accepter는 메세지를 무시할 수 있고, 거절응답을 P에게 보낼 수 있음
리더가 정해지고 나서는 시스템의 모든 변경사항이 리더를 통하게 됩니다. 각 변경사항은 로그엔트리(log Entries)에 저장되고 다른 follower들에게 복제됩니다.
로그 엔트리
Term : 임기
Index : log 저장할때의 번호 (1부터시작함)
Data
1.클라이언트가 리더에게 변경사항을 보냄 2.변경사항은 리더의 로그엔트리에 저장됨
3.AppendEntries RPC를 호출해서 log를 전달 4.Follower는 새로받은 로그를 저장하고 성공 응답을 보냄
AppendEntries RPC Arguments:
term: 현재 leader의 임기
leaderId : leader id
prevLogIndex : 바로 이전의 log index
prevLogTerm : 바로 이전의 log index에 기록된 임기(term)
entries[] : 저장할 로그 엔트리 (비어있으면 heartbeat용)
leaderCommit : 현재 leader의 commitIndex
아래 사진의 경우에서는 과반수의 노드(여기선 3개의 노드)에 복제되었으므로 커밋된 것으로 간주하고, 이를 Committed Entries(여기서는 7)라고 칭합니다.
한 번 커밋된 엔트리는 다음 임기의 리더들에게 반드시 포함될 것을 보장하는데, 이를 Leader Completeness라고 합니다.
이게 어떻게 보장될 수 있을까요?
다시한번 AppendEntries의 동작을 되짚어보겠습니다.
리더는 새로운 엔트리를 다른 서버로 전파할 때 AppendEntries RPC를 호출합니다. 문제 없이 성공한다면 로그엔트리를 복사하고, 실패한다면 인덱스 값을 1씩 감소시켜서 성공할 때까지 반복하고 성공한다면 로그를 복사합니다.
그것을 과반수의 follower들에게 전파를 성공한다면 위에 언급한 것처럼 commit을 하게 됩니다.
여기서 살펴봐야 할 것은 두가지 입니다.
Election Restriction (선거 제약)
Candidate는 Leader가 되려면 과반수 노드의 투표가 있어야 함
RequestVote RPC에는 Candidate의 마지막 로그의 index와 term이 파라미터로 포함되어있는데, 요청을 받은 투표자(Follower)의 index나 term이 더 높으면 요청을 거절함
Commit Rules (커밋 규칙)
Raft에서는 반드시 현재 임기의 로그가 복제되어야만 커밋으로 간주한다.
Raft에서는 위 두가지 규칙을 통해서 Leader Completeness를 보장하고 있습니다.
박스안의 숫자는 임기를 의미합니다.
한 번 순서를 따라가보도록 하겠습니다.
(a) : 2대리더는 1번노드입니다. 2번 index까지 과반수의 노드에 전파가 되어서 커밋이 되었습니다. (commitIndex=2) (b) : 3번 index가 다수의 노드에 전파되어 커밋되기전에 -> 5번노드가 각 노드에게 투표를 요청합니다. -> 1번과 2번노드에게는 선거제약 규칙때문에 투표를 거절당하고, 3번,4번노드에게 표를 받아서 5번노드가 3대리더가 되었습니다. (commitIndex=2) (c) : 다시 1번노드가 24번 노드에게 표를 받아 4대리더가 됩니다. -> 그리고 3번 index를 노드3번에 복사하여 과반수 노드에 전파를 성공했습니다. -> 하지만 이는 커밋규칙에 따라 현재임기의 로그가 아니므로 커밋되었다고 할 수 없습니다. (d) : 만약 5번노드가 24번 노드에게 표를 받아 다시 리더가 된다면 이전 것을 덮어씌우기 때문입니다. (commitIndex=3) (e) : 하지만 (c)상황에서 1번노드가 4번 index까지 무사히 과반수 노드에 전파를 성공해 커밋한다면 5번노드는 당선될 수 없습니다.(commitIndex=4)
일련의 과정을 통해 리더가 바뀌더라도 이전에 커밋했던 index들은 계속 유지된다는 것을 확인할 수 있습니다.
글을 쓰다보니, paxos알고리즘이 이해하기 어렵다고 하는데 저는 개인적으로 raft가 더 어려웠던 것 같습니다. paxos는 그냥 핥아보기만하고 raft는 깊게 파고들어서 그런걸까요?ㅋㅋㅋ 아니면 이정도는 누워서 떡먹기라고 생각하는 스탠포드 학생들이 대단한 것일까요…. 역시 컴퓨터 굇수들은 무서워요
