"우리...의견 좀 맞출까...?" - 분산 환경에서의 합의 알고리즘 (Paxos, Raft)

저는 중국집을 자주 갑니다.
요즘 시대에 가성비이기도 하고, 친구들과 함께 밥을 먹을 때 가장 무난한 선택이기도 하기 때문이죠.

그날도 사람들과 함께 중국집을 갔습니다.
전 정말 좋아하는 짬뽕을 시키고, 친구들도 각자가 좋아하는 매뉴를 시켰죠.
각자가 주문한 메뉴가 나오고, 저희는 입가에 미소를 가득 띄우며 먹을 준비를 했습니다.

그리고, 탕수육이 나왔죠.

싸해지는 분위기,
서늘한 공기,
그리고 서로의 눈치를 보는 7명의 사내들.

제가 가장 용기를 내어 소리쳐봅니다.

그래서, 다들 찍먹이지?

3명이 동시에 일어나서 말도 안된다고 이야기를 하며 탕수육은 원래부터 부먹이었다고 소리를 칩니다.
저를 포함한 나머지 3명 역시 반박하며 찍먹의 바삭함을 강조하며 논리를 펼쳤죠.
그리고 나머지 한 명은 뭐가 문제냐며 제발 좀 그냥 먹어라라고 소리를 치죠.

오늘도, 평화롭게 밥을 먹기는 글렀습니다.

0. 그래서 합의가 왜 필요한데?

위 이야기와 같은 상황은 많이 벌어집니다.
부먹이냐 찍먹이냐, 치킨 한 마리냐 두 마리냐, 민초를 시키냐 말냐 등등
여러 명의 의견을 조율하느라 한참 고민한 경험은 모두에게 한 번쯤은 있는 일일 것입니다.

누구 하나 확실히 “이걸로 가자!”라고 외쳐 주면 다들 편한데, 그렇지 못하면 메뉴 토론은 꼬리에 꼬리를 물며 길어지기 마련이죠.

분산 환경에서 서버도 똑같은 문제에 직면합니다.
여러 대의 서버가 동시에 움직이지만, 사용자 입장에서는 마치 한 대의 서버처럼 일관된 응답을 받길 원하죠.
그런데 네트워크 지연, 서버 장애, 메시지 중복·손실 같은 변수가 나타나면 서버마다 “내가 먼저 처리했어!” 혹은 “난 아직 몰라!” 하며 제각각 다른 상태로 달려가게 됩니다.

이럴 때 필요한 것이 바로 합의(consensus)입니다.

리더가 총대를 매고 '찍먹!'이라고 이야기를 하면 그날의 탕수육은 찍먹이 되듯이,
누군가가 과반수가 찬성한 의견을 공식 선언해 주면, 서버들끼리 “찬성!”이라며 한 목소리를 낼 수 있기 때문이죠.

분산 환경에서는 이러한 합의를 이끌어내는 여러 알고리즘이 있습니다. 그 중에서 오늘 여러분들에게 소개드릴 알고리즘음 바로 Paxos와 Raft 알고리즘입니다.

제가 개인적으로 공부하며 재밌는 내용이기도 했고,
이제부터 공부한 내용을 노트가 아니라 Velog에 정리를 하며 공유를 하고자 하여 글을 작성해보았습니다. 😁😁

---

1. 철부지 인싸의 약속 잡기 - Paxos

Paxos는 1989년 컴퓨터 과학자 레슬리 램포트(Leslie Lamport)가 제안한 분산 합의 알고리즘입니다. 원래 논문 제목은 “The Part-Time Parliament”(파트타임 의회)였는데, 고대 그리스의 작은 섬 “Paxos”에서 의회가 열린다는 우화에서 유래한 이름을 차용했죠.

Paxos의 개념은 단순합니다.

'과반수의 찬성'만 있으면, 모두가 같은 의견에 도달할 수 있다!

Paxos는 아무리 네트워크가 불안정하고 분산 환경에서의 노드가 언제든 실패할 수 있는 환경에서도, '과반수의 찬성'만 얻을 수 있다면 모든 노드가 하나의 결정에 일관되게 도달할 수 있다는 점에서 구상이 된 알고리즘입니다.

마치 하나의 투표 시스템을 보는 것과 같은 Paxos가 실제로는
어떻게 진행되는지 한 번 천천히 알아볼까요! 😎😎

자, 등장인물을 소개합니다!

다음 등장인물들은 Paxos를 구성하는 중요 등장인물들입니다!

• 제안자 (Proposer)
  • "이걸로 하자!"라고 하며 의견을 제안하는 사람 (의견 통합의 대상)
    • 각 제안은 $N_1, N_2, \cdots$와 같이 제안 번호가 붙습니다.
      • 제안자는 항상 더 높은 제안 번호로 새로운 제안을 보냅니다.
    • 그리고 각 제안에 해당하는 값은 $V_1, V_2, \cdots$로 표현을 합니다.
  • 제안자는 한 명이거나, 여러 명일 수 있습니다.
• 수락자 (Acceptor)
  • 의견을 찬성(accept) 혹은 약속(Promise)하는 심사위원
  • 수락자는 '과반수'라는 개념이 성립할 만큼 필요합니다.
• 학습자 (Learner)
  • 최종 결과를 듣고 "아하! 그렇게 되었군!"을 외치는 관객
  • 수락자와 제안자의 합의 결과를 듣고, 최종 결과를 받아 적는 역할입니다.

예를 들어, 총 노드가 20개이고, 안건을 내는 제안자가 1명이라고 가정을 했을 때,

• 수락자는 과반수 찬성을 모아야 하니 최소 11명이 필요하고,
• 나머지 8명이 학습자가 될 수 있겠죠! (물론, 수락자가 '나도 결과 좀 알려줘!'라면서 학습자 역할도 함께 겸하는 경우가 많습니다 ㅎㅎ)

이후 설명을 제안자가 하나이라고 가정하고 설명을 진행하겠습니다. 제안자가 여러 노드일 수도 있어요. 그런데 이 경우는 조~금 복잡하니, 일단은 제안자가 한 명이라고 가정한 후에 설명을 계속할게요!

나랑 놀아줘!! Paxos Algorithm 설명

Paxos 알고리즘은 총 4개의 단계로 이루어집니다.

1. PREPARE 단계
2. PROMISE 단계
3. ACCEPT 단계
4. CHOSEN 단계

각 단계들을 하나의 이야기에 빗대어 설명을 해보도록 하겠습니다. 😁😁

1. PREPARE 단계

제안자가 완전 철부지 인싸라고 가정을 해볼게요! 완전 철부지지만, 모든 친구들과 항상 함께 놀고 싶은 귀염둥이 친구이죠ㅎㅎ

어느날, 제안자가 친구인 '수락자'들과 놀기로 결심했어요! 그런데 친구들이 너무 많은 나머지, 약속 장소와 약속 시간을 서로 맞춰야 할 지경에 이르렀죠. 이때, 약속 장소와 약속 시간을 제안값 $V$라고 합시다.

그런데, 제안자는 한 가지 단점이 있는데, 바로 약속을 밥 먹듯이 바꾼다라는거죠! 제안자도 본인의 단점을 너무나도 잘 알고 있기 때문에, 다음과 같이 친구들에게 약속을 '제안'합니다.

내 제안 번호 $N$으로 $V$를 합의하는거 어때?

즉, 약속 시간과 약속 장소인 $V$를 친구들에게 제안하는데, 이 제안의 번호를 붙이는 거죠. 그리고 만약 마음에 변덕이 생겨 새로운 제안을 하고 싶다면, 무조건 더 높은 제안 번호로 제안을 하겠다!라고 약속을 합니다.

2. PROMISE 단계

수락자들은 제안이 들어온 것에 기쁘면서도, 한편으로는 고민에 휩싸입니다. 분명 제안자가 다른 제안을 보내는 경우도 존재할 거란 말이죠?

그래서 각각의 수락자들은 결심을 합니다!

좋아! 너의 제안인 $N$을 일단은 수락하기로 약속(Promise)할게 ! 그리고, 너보다 낮은 번호로 들어오는 제안은 앞으로 모두 거절할게!

수락자들은 바로 수락하지 않고, 대신 해당 제안을 '약속'합니다. 제안 번호 $N$보다 낮은 번호로 오는 제안은 거절하기로 하죠. 이 약속이 깨지고 수락자가 새로운 제안을 받아드리는 경우는 오직 더 높은 제안 번호를 가진 제안이 들어올겁니다.

수락자는 제안자에게 답장을 합니다.

$N$보다 적은 번호 제안은 거절할게! 그리고, 내가 이전에 받아들인 제안이 있다면, 그것에 대한 $N, V$를 알려줄게!

3. ACCEPT 단계

수락자에게 하나 둘 약속 답장이 오기 시작하고, 제안자는 과반수 이상의 수락자에게 답장이 오는 순간 됐다!라고 외치며 최종 제안을 공지합니다.

내가 과반수 이상의 답장을 받았어! 모두들 이 $N$이라는 제안에 동의하는거지?

당연하게도, 제안자는 본인이 보냈던 $N$, 그리고 해당 제안의 값인 $V_{final}$을 공지합니다.

각각의 수락자는 공지된 $N$을 보고 다음과 같은 선택을 합니다.

1. 공지된 $N$이 본인이 마지막으로 약속한 $N$과 같을 경우, 제안자는 해당 수락자가 약속한 $V$를 최종 제안으로 선택한 것입니다. 수락자는 해당 제안에 찬성 (Accept)을 하고, 찬성 응답을 제안자에게 보냅니다.

2. 공지된 $N$이 본인이 마지막으로 약속한 $N$보다 높을 경우, 수락자는 한숨을 내쉽니다. 네, 그렇습니다. 제안자가 약속을 또 바꾼거죠. 그렇지만 어떤 이유에서인지 본인은 새로운 제안을 듣지 못했습니다. 네트워크 환경이 안 좋았나보네요.
   마음이 넓은 수락자는 제안자에게 맞추기로 합니다. 수락자는 해당 제안에 찬성 (Accept)을 하고, 찬성 응답을 제안자에게 보냅니다.

3. 드물게 발생하는 경우지만, 공지된 $N$이 본인이 약속한 $N$보다 낮을 경우 수락자들은 본인이 약속한 $N$보다 적은 번호 제안은 거절할게!라는 본인들의 약속에 맞추어 해당 공지를 무시 (Skip)합니다. 아무리 제안자가 약속을 자주 바꿔도, 본인들이 한 약속은 지켜야하니까요!

여기서 눈치가 빠르신 분들은 아시겠지만, 수락자들은 $N$값만을 보고 찬성 혹은 무시를 합니다!

4. CHOSEN 단계

만약, 과반수 이상의 찬성이 응답이 되면, 제안자는 아싸!하면서 공지를 합니다.

자, 과반수가 동의한 $N$로 결정!! 땅땅!!!

그리고, 결정된 (Chosen) $N$과 $V_{final}$을 모든 수락자, 그리고 더 나아가 모든 학습자에게 공지합니다. (네, 제안자는 수락자들로 만족하지 않아요 😉😉) 이때, 모든 수락자들과 학습자들은 해당 $N, V_{final}$로 본인들의 $N, V$를 업데이트합니다.

짠, 이제 모든 합의 과정이 이루어졌어요! 제안자, 수락자, 그리고 학습자까지 모두 같은 제안값인 $V$를 가지게 되었습니다.

위 내용을 이해하셨다면, Paxos를 이해하신 것과 다름 없어요!😎😎

만약... 과반수의 수락자들이 Skip한다면?

만약 과반수의 수락자가 찬성을 하지 않으면요?

제안자가 시무룩해지는 순간이죠...ㅎㅎ 하지만 철부지 인싸 제안자는 여기서 끝나지 않습니다!

내 제안을 안 받아들여줘...? 그러면...번호를 조금 높여보자!

제안자는 $N$의 값을 살짝 높인 후, 다시 prepare 단계부터 수행을 합니다. "이번에는 받아주겠지?"하면서요ㅎㅎ

언제나 그랬듯이, 수락자들은 더 높은 $N$이 오면 수락을 해줍니다. 그렇게 재시도를 통해 제안자는 본인이 원하는 $V$로 합의를 이루어내고야 말죠.

제안자가 여러명인 경우?

만약 이런 철부지 제안자가 여러 명이라면요?

ㅎㅎ...생각만해도 머리가 아프네요 😅😅 여러 제안자가 “나도 나도!” 하고 동시에 제안을 보내면, 수락자들은 “어? 이 번호가 먼저야, 저 번호가 먼저야?” 하며 순간 멘붕에 빠집니다.

그래서 실제로는 제안자 중 하나의 리더를 선출하거나, 충돌 시 타임아웃과 백오프(back-off) 전략을 써서 조율을 합니다. 이 과정을 통해 한 명의 Proposer만 Prepare–Promise–Accept 절차를 밟도록 질서를 세우면, 네트워크 지연과 충돌 걱정 없이 깔끔하게 합의를 이룰 수 있습니다.

---

2. 배에서 일어나는 유쾌한 선상반란 - Raft

Raft는 배의 키 조정 장치인 Rudder에서 살짝 변형된 말입니다.

만약에 여러분들이 Paxos를 이해하는데 어려웠다면...그것은 정답입니다...ㅎㅎ 실제로 Paxos는 합의 과정이 복잡하고, 구현도 어려워 이를 실제로 구현한 분산 시스템은 적었죠.

미국 스탠포드 대학교의 한 학생과 한 교수도 Paxos가 너무 어렵다고 생각했죠.

Diego: 지도교수님, Paxos 이거 너무 어려운데요?
John: 그렇군... 더 쉬운걸 만들어야겠어...
Diego: 네...빨리 더 쉬운 알고리즘이 나와야겠어요...
John: 만들자고.
Diego: 네?

그렇게 2014년, 당시 박사 과정을 밟고 있던 학생 Diego Ongaro와 지도 교수 John Ousterhout가 새로운 분산 합의 알고리즘 Raft을 만들어 USENIX에 발표합니다. Paxos보다 더 쉬우면서도 구현도 간단한 알고리즘이었던 Raft는 인기를 끌고 곧 많은 오픈 소스(e.g. etcd, Consul)에 적용되기 시작했죠.

하나의 이야기로 Paxos를 설명했던 것과 달리, Raft는 하나의 예시로 설명을 해볼까해요. Raft가 '배'라는 개념에서 출발이 된 알고리즘이라는 것을 기억해주세요! 😁😁

자, 등장인물을 소개합니다!

다음 등장인물들은 Raft를 구성하는 중요 등장인물들입니다!

• 선장 (Leader)

  • 배의 키를 잡고 항로를 항해하는 선장님입니다. 😎😎
  • 부하들에게 명령을 하며, 모든 부하들이 동일한 명령을 따르도록 지휘합니다.
    • 이 명령은 ‘로그(log)’ 형태로, 알고리즘 내에서 AppendEntries 단위로 Followers에게 전송됩니다.
    • 이 log는 이후에 있을 '투표(Election)'시에도 사용이 됩니다.
  • 명령이 없을 때에는, 부하들에게 Heartbeat을 보내며 본인의 생존신고를 합니다. 선장은 항상 살아있어야하기 때문이죠

• 부하 (Follower)

  • 선장에 지시에 따라 움직이는 충성스러워보이는 부하들입니다.
  • 명령에 따라 움직이며, 평상시에 선장의 Heartbeat을 들으며 선장이 살아있는 것을 알죠
  • 만약, 일정 시간동안 선장이 Heartbeat를 보내지 않는다면, 부하들은 '선장이 사라졌다!'라고 판단하고 본심을 드러냅니다.

• 후보자 (Candidate)

  나도 선장 해볼래!

  • 비어버린 선장 자리를 눈치채고, 이를 차지하기 위해 스스로 Candidate 상태가 된 부하입니다.
  • 새로운 선장이 되기 위해 부하들에게 자신에게 투표해 달라는 RequestVote 요청을 Followers에게 보냅니다.

반란이다!! - Raft 알고리즘 설명

Raft 알고리즘은 총 4개의 단계로 이루어집니다.

1. 선상반란 단계
2. 투표 (Election) 단계
3. 명령 전파 & 로그 복제 (Log Replication) 단계
4. 커밋 (Commit) 단계

1. 선상반란 단계

부하들은 선장의 생존 신고 (Heartbeat)을 계속 받습니다. 그런데, 일정 시간 선장의 생존 신고를 받지 못한 부하 한 명이 선장이 사라졌음을 눈치챕니다. (부하들은 각자 150ms ~ 300ms 사이의 랜덤한 Election Timeout을 가지고 있고 가장 먼저 Timeout이 발생한 부하가 선장의 실종을 감지합니다.)

반란이다!!

눈치 빠른 부하는 곧바로 후보자로 변신합니다. 후보자가 된 부하는 다음과 같은 일을 합니다.

1. 자신의 '시기(term)'을 하나만큼 높입니다. (term += 1)
2. 모든 부하들에게 본인이 선장이 되는 것에 대한 동의표를 요청합니다. (RequestVote)

이때, RequestVote에는 다음과 같은 정보가 들어가있습니다.

• 시기(term)
• candidateId
• lastLogIdx, lastLogTerm: 로그의 최신 위치와 시기를 알리는 정보

정리하자면, 후보자가 된 부하는 RequestVote를 통해 다음과 같이 나머지 부하들에게 이야기하는 것입니다.

내 로그가 가장 최신 로그니, 사라진 선장을 이어서 이 배를 운행할 수 있어! 그러니 나한테 표 던져 줘!

2. 투표 단계 (Election)
이때 후보자들은,

• 내가 아직 투표하지 않았고,
• 요청된 시기(term)가 내 시기보다 높고,
• 후보자의 로그가 내 로그보다 뒤쳐져있지 않다면

좋아! 너가 선장해라!

라고 이야기를 하며 해당 후보자에게 찬성표를 던집니다. (voteGranted = true)

만약 후보자가 과반수의 부하들에게 찬성표를 받는다면, 새로운 선장이 됩니다.

만약 과반수의 표를 얻지 못한다면, 다시 Election Timeout이 리셋되어 부하의 상태로 돌아가게 됩니다.
정말 희박한 확률로 Candidate이 여러 명일 경우에도 안심이 되는 이유죠. 투표수가 분산되어 한 후보자가 과반수 득표할 확률이 매우 낮아지니까요!

3. 명령 전파 & 로그 복제 (Log Replication) 단계
새로 선장이 된 후보자는, 이제 선장의 일을 하기 시작합니다.
계속 생존 신고를 하며, 모든 부하들이 동일한 명령을 따르도록 지휘하는 일을 말이죠!

선장은 부하들에게 명령할 로그(log)가 있다면, (분산 환경에서 클라이언트에게 받은 요청이 되겠죠)

• 해당 로그를 새로운 로그 항목 (log entry)로 추가하고,
• 부하들에게 AppendEntries로 해당 로그를 전파합니다. 이 로그들은 부하들에게 복제가 되어 모두가 동일한 로그를 갖게 될 것입니다.

이때, AppendEntries에는 다음과 같은 정보가 들어가있습니다.

• 시기(term)
• leaderId
• prevLogIdx, prevLogTerm: log 등록 전, 리더가 가지고 있었던 최신 로그에 대한 정보입니다. 부하들에게 “내 로그 여기까지 너희랑 똑같지?”를 물어보는 기준점이 됩니다.
• entries[]: 새로이 추가된 log로서, 부하들이 복제할 로그입니다.

이때 부하들은 명령을 전달 받습니다.

• 만약 term이 본인보다 높고, prevLogIdx, prevLogTerm이 동일하면 해당 entries[]를 본인 로그에 붙인 후, 성공을 응답합니다. (success = true)
  • 이 때, 부하는 본인의 Election Timeout을 리셋합니다! (선장이 일 잘하네...두고보자...)
• 만약 term이 본인보다 낮거나, prevLogIdx, prevLogTerm이 불일치하다면 해당 AppendEntries를 거절합니다. (success = false)

4. 커밋 (Commit) 단계
선장은 과반수의 부하가 성공(success = true)을 응답한다면, 해당 로그에 대한 인덱스(Idx)를 커밋의 대상이 되는 인덱스 (commitIndex)로 올립니다.

그리고 다시 부하들에게 AppendEntries를 전파하는데, 이 때에는 다음 정보가 들어가있습니다.

• leaderCommit: 부하들에게 '해당 로그 인덱스까지 커밋해도 돼!'라고 알려줍니다. 부하들은 본인들이 가지고 있는 로그 중 해당 인덱스까지 작업에 옮길 것입니다.

부하들은 해당 leaderCommit에 따라 작업을 수행합니다. (전공자들은 '부하 자신의 FSM에 반영한다'라고 이해해도 될 것 같습니다ㅎㅎ)

이 작업을 통해 선장과 부하들은 '같은 로그', 그리고 '같은 작업 수행'을 보장합니다! 배는 순탄하게 흘러갈 것입니다...선장이 사라지기 전까진요 😉😉

---

마무리

이 외에도 Zab, PBFT와 같이 많이 사용되는 합의 알고리즘이 있습니다! 이 알고리즘에 대해서도 추후에 다뤄보도록 하겠습니다. 😎😎

많이 어려운 내용이었는데, Velog에 정리하다보니 이해가 그나마 되네요ㅎㅎ
진작에 공부한 내용을 대충 노트에 끄적이는게 아니라 이렇게 체계적으로 정리할 걸 그랬습니다.
앞으로 회고 뿐만이 아니라 공부하는 내용들에 대해서 자주 포스팅하도록 할게요! 😉😉