나는 Raft 합의 알고리즘(분산 알고리즘의 대표 주자)을 Python으로 구현했다. 꽤 형편없는 구현이다! 그래도 (어느 정도는) 올바르게 동작한다.
비슷한 도전에 관심이 있는 사람에게 전하고 싶은 메모를 몇 가지 적어 본다.
돌이켜 보면, Raft를 배우고 올바르게 구현하는 데 가장 유용했던 자료는 다음과 같다.
- Raft 논문(5절까지 읽고 그림 2를 수시로 참고할 것)
- 학생을 위한 Raft 가이드
- 가장 널리 쓰이는 Raft 구현체 중 하나
- 저장소를 복제하고
raft.go내용을 훑어본 다음, LLM과 대화를 주고받으며 코드베이스와 설계 결정을 이해해 보자
- 저장소를 복제하고
- Eli Bendersky의 블로그 연재
먼저 한 시간 정도 논문을 읽은 뒤, 수신한 바이트를 읽어 배열에 추가하는 UDP 또는 TCP 서버의 코드 뼈대를 작성해 보기를 권한다. 그다음 나는 Eli의 구현을 따라가며 같은 순서로 내 Raft 구현에 기능을 추가했다.
리더 선출 비슷한 것이 돌아가게 된 뒤에는 버그와 알고리즘에 대한 내 이해가 잘못된 부분을 찾기 시작했다. 학생용 가이드, Raft 논문의 그림 2, 내 구현을 번갈아 보며 내 구현이 어디서 일치하는지(또는 다른지) 꼼꼼히 생각했다. 또한 위 자료의 내용을 컨텍스트에 넣고 LLM으로 이 코드를 검토하는 데도 적극적으로 활용했다.
로그 복제, 영속성 등에도 위 과정을 반복하면 된다.
구현에 관하여
나는 구현을 단순화하기 위해 몇 가지 설계 선택을 했다. 순서에 특별한 의미는 없다.
- 각 노드는 단일 스레드에서 실행되며 메시지도 그 스레드에서 처리한다
- 시스템의 로컬 "시간"을 추적하는 데 "논리 시계"를 사용한다(예를 들어, 시스템 시간을 사용하는 대신
tick()호출로 각 노드의 로컬 카운터를 증가시킨다) - 네트워크 파싱, 저장/영속성 처리, 핵심 Raft 알고리즘, 노드 자체를 제어하는 유틸리티/명령 등 모든 것을 파일 하나에 넣어 구현을 "뒤섞어 놓는다"
2번은 타당하고 올바른 설계 선택으로 보인다(etcd 구현에서도 논리 시계를 사용한다). 3번은 학습/교육 측면에서 더 낫다고 볼 수도 있다. 모든 것이 한 파일에 있으면 한눈에 볼 수 있어 좋고, 구현을 마음껏 뜯어고치면서 어떤 추상화가 알고리즘에 가장 잘 맞는지 살펴보기에도 좋다.
1번은 내가 보기에도 꽤 부적절한 선택이다. 구현이 훨씬 단순해지는 것은 사실이지만(교착 상태에 빠지는 문제나 노드 내부 상태의 원자적 갱신을 덜 걱정해도 된다), 결과물은 온전한 Raft라고 하기 어려워진다. 첫 구현이라면 이 정도는 괜찮아 보인다. 알고리즘 자체만으로도 충분히 복잡하니, 뮤텍스와 씨름하기보다는 핵심 Raft 알고리즘의 논리 오류를 디버깅하는 데 시간을 쓰는 편이 낫다고 생각한다.
이런 방식으로 Raft를 구현하는 일은 약 30시간짜리 프로젝트라고 생각한다. 처음 Raft 논문을 읽고 관련 자료를 검토하는 데 몇 시간 정도 걸릴 것이다. 나는 휴일 동안 하루에 6~8시간씩 코딩하며 약 3일 만에 코드 대부분을 작성했다. 기존 구현에는 아직 다듬고 개선할 부분이 남아 있으며(예를 들어 미묘한 버그 수정), 여기에 반나절 정도 더 걸릴 것 같다.
종합해 보면, 핵심 알고리즘 중 하나를 이해하는 데 이 정도면 꽤 괜찮은 셈이다. 그 알고리즘이 뒷받침하는 대상이 이토록 많은 인프라라는 점을 생각하면 말이다.