분산 시스템의 결함 허용 속도와 합의 알고리즘 (Paxos vs Raft)

장애 대응을 하다가 밤을 꼬박 새운 어제, 원인은 의외로 사소한 아키텍처 설계 미스였습니다. 저와 같은 실수를 반복하지 않으시길 바라며 이 글을 씁니다. 여러 대의 물리적 서버를 묶어 논리적인 단일 엔티티로 동작시키는 분산 시스템 모델에서 가용성과 일관성을 동시에 담보하기 위한 최종 관문은 분산 합의(Distributed Consensus)입니다. 네트워크 단절, 메시지 유실, 혹은 서버 크래시가 일상적으로 발생하는 클러스터링 환경에서 모든 정상 노드들이 반드시 동일한 연산 순서에 동의하도록 보장하는 알고리즘은 20세기 후반 팩소스(Paxos) 알고리즘의 발명에서 체계화되었습니다. 레슬리 램포트의 제안은 수학적으로 무결한 일관성을 입증했으나 알고리즘의 상태 공간이 지나치게 복잡하여 엔지니어들이 이를 완벽히 구현하는 것이 거의 불가능에 가깝다는 수십 년의 비판을 감내해야 했습니다. Multi-Paxos는 로그 복제에 필요한 라운드트립을 최소화하려 노력했지만 코드를 검증하고 디버깅하는 일련의 과정이 여전히 거대한 장벽이었습니다. 이에 대한 근원적인 반발과 단순성에 대한 강력한 엔지니어링적 요구로 탄생한 것이 Raft 알고리즘입니다. Raft 알고리즘은 합의 공간을 강력한 리더(Strong Leader) 선출과 로그 복제(Log Replication)라는 두 가지 독립적인 서브 문제로 분할하여 추론과 구현의 난이도를 획기적으로 낮췄습니다. 클러스터의 노드들은 Leader, Follower, Candidate 중 한 상태를 유지합니다. 일반적인 상황에서 리더는 클라이언트로부터 들어온 모든 요청을 처리하며 순서가 부여된 로그 엔트리를 팔로워 노드들에게 전파합니다. 대다수(Quorum)의 노드가 로그 저장에 성공했음을 알리면 리더는 그제서야 해당 트랜잭션을 분산 시스템에 영구 커밋(Commit)시킵니다. 만약 강력한 리더가 통신 불능에 빠지면 시스템엔 Heartbeat 단절이 발생합니다. 정해진 시간 동안 심장 박동 메시지를 받지 못한 팔로워들은 즉시 임기(Term)를 올려 스스로 후보자(Candidate)가 되며 선거를 개시합니다. 랜덤화된 선거 타임아웃 주기를 두어 여러 후보가 동시에 동률로 표를 나누어 가지는 스플릿 보트(Split Vote) 현상을 방지한 것이 Raft의 백미입니다. Zookeeper의 ZAB 프로토콜 또한 유사한 리더 선출 메커니즘을 토대로 하지만, Raft는 그 구조 자체가 압도적으로 직관적이기 때문에 Etcd, Consul, 커스텀 데이터베이스 복제 프로토콜 등 현대적인 분산 인프라 코어 시스템에서 사실상의 합의 도구로 절대적인 권위를 획득하고 있습니다. 로그의 일관성이 보장된다는 것은 곧 스플릿 브레인 시나리오 아래에서도 정확한 트랜잭션의 원자성이 수호된다는 것을 의미합니다.