Paper: A simple totally ordered broadcast protocol
이 페이퍼는 Zab라는 ZooKeeper의 내부에 구현되어있는 ordered broadcast 프로토콜을 소개하고 있다. 이 페이퍼는 informal한 형태로 Zab에 대한 요구사항과 동기, 그리고 프로토콜 자체에 대해서 설명하고 있으므로 이를 파악하기에 좋은 것 같다. Zookeeper에 대한 페이퍼와 Zab에 대한 좀 더 formal한 페이퍼도 따로 있으므로 앞으로 읽어볼 것.
Zab는 Zookeeper Atomic Broadcast라는 이름대로 Zookeeper의 노드들 사이에 동일한 오퍼레이션들의 순서를 유지하고 결과적으로 노드들의 상태를 동일하게 유지되기 위해 사용된다. (Atomic Broadcast 참고.)
Zookeeper는 클라이언트로부터의 request들을 그대로 Zab로 보내는 것이 아니라 conditional operation이나 version increment를 포함하고 있어서 본질적으로 idempotent하지 않은 request를 idempotent한 transaction으로 변환하는 과정을 가지고 있다. 이 변환은 leader 노드에서만 발생할 수 있으며, 그 이유는 leader 노드만이 오퍼레이션으로 인해 변할 미래의 상태에 대한 완벽한 정보를 가지고, 새로운 값을 정할 수 있기 때문이다.
Requirements
Zookeeper는 다음과 같은 요구사항을 가지고 있다.
- Reliable delivery
- If a message, m, is delivered by one server, then it will be eventually delivered by all correct servers.
- Total order
- If message a is delivered before message b by one server, then every server that delivers a and b delivers a before b.
- Causal order
- If message a causally precedes message b and both messages delivered, then a must be ordered before b.
- Prefix property
- If m is the last message delivered for a leader L, any message proposed before m by L must also be delivered.
우리가 알고 있는 Zookeeper의 특성 상 다른 것들은 쉽게 추론할 수 있으나, 클라이언트 입장에서의 correctness를 표현한 Causal order requirement는 이러한 말로 표현하는 것을 아직 자주 본 것은 아니라서 눈여겨보게 되었다.
Zookeeper의 어떤 노드가 실패했을 때 snapshot을 읽어들인 다음 snapshot 이후에 배달된 transaction들을 리플레이하게 되는데, 위에서 설명했던 idempotent한 transaction 덕에 이러한 복구 과정에서 atomic broadcast는 at most once delivery를 보장하지 않아도 된다. 이는 또한 복구 과정에서는 total order requirement가 완화되는 것을 의미하기도 한다.
Motivation
이 부분에서는 왜 이미 존재하는 프로토콜을 사용하지 않고 Zab를 고안해서 사용하게 되었는가를 각 프로토콜을 들어 설명하고 있다. 굉장히 많은 페이퍼들을 인용하며 설명을 하고 있는데, 가장 중요한 것은 역시 Paxos와의 비교라고 할 수 있다. 이 페이퍼는 현실의 조건에 따른 가정을 토대로 Paxos를 단순화시킬 수 있다고 이야기 하고 있다.
Paxos는 메시지의 손실과 순서가 바뀌는 것 조차도 허용하고 있지만, TCP를 사용한다면 메시지가 FIFO 순서로 전달되는 것을 가정할 수 있고, Zab는 이에 따라 per-proposer causality를 보장할 수 있다. Paxos는 FIFO channel을 가정하지 않기 때문에 이러한 보장을 할 수 없다.
두번째로 Paxos에서는 복수의 leader로부터 하나의 인스턴스에 대한 proposal이 가능하므로, proposal이 서로 충돌하거나 어떤 값이 commit 되었는지 알아내기 힘든 문제가 있다. Paxos에서는 어떤 노드라도 높은 투표만 얻으면 리더가 될 수 있는 반면, Zab에서는 다수의 노드가 기존의 리더를 버리지 않는 이상 새로운 리더가 될 수 없다. 이로 인해 Zab에서는 주어진 인스턴스에 대해서 단 하나의 proposal을 보장할 수 있고, 이는 프로토콜을 여러 면에서 단순화 시킨다.
Protocol
Zab protocol은 recovery와 broadcast 두 개의 모드로 이루어져있다. Zookeeper를 처음으로 실행했을 때나 leader 실패가 발생했을 때는 recovery 모드가 되고, leader가 성립되고 quorum이 leader와 동기화를 완료하게 되면 broadcast 모드가 된다.
Zookeeper는 broadcast의 leader를 (request를 transaction으로 변환하기 위한) write request의 leader로도 사용하기 때문에, 만약 분리되었을 경우 발생할 둘 사이의 latency를 제거한다.
Broadcast
단순화된 two-phase commit과 유사하다고 얘기하고 있다. two-phase commit과는 달리 Zab에는 abort가 없기 때문에 follower는 leader의 proposal을 수용하거나 leader를 포기하는 두가지의 선택지 밖에는 없으며, 또한 leader는 quorum을 이룬 follower들로부터 ack을 받는다면 commit을 진행할 수 있다.
broadcast 프로토콜은 모든 커뮤니케이션에 대해 FIFO 채널을 이용하므로 순서를 보증하는 것이 매우 쉽다.
leader가 proposal을 보낼 때는 zxid라고 불리는 단조증가하는 ID를 부여한다. Zab는 causal ordering을 보존하기 때문에 전달된 메시지는 zxid들에 의해서도 정렬된다. 이 후에 proposal은 follower별로 존재하는 queue에 넣어지고, 이는 FIFO 채널을 통해 follower로 전달된다. follower는 받은 proposal을 디스크에 쓰고 leader에게 ack을 보낸다. leader가 다수의 follower로부터 ack을 받으면 commit을 broadcast하고 leader 자신에게 메시지를 배달(deliver)한다. follower들은 commit을 받았을 때 메시지를 배달한다.
Recovery
Recovery에서 중요한 것은 commit된 모든 메시지를 제대로 보존하는 것과 commit되지 않은 – skip된 메시지를 보존하지 않는 것이다.
commit된 모든 메시지를 보존하는 문제는 leader election 과정에서 quorum 서버 중에서 가장 높은 proposal number를 가지고 있는 노드를 leader로 선택하는 것이다. 새로 선출된 leader는 새로운 proposal을 처리하기 전에 트랜잭션 로그에 있는 모든 메시지들이 propose되고 quorum에 의해 commit되도록 한다.
새로운 follower 노드가 추가되었을 때는 leader는 우선 follower가 보지 못한 proposal을 모두 queueing하고 그 다음 마지막으로 commit된 proposal까지 commit들을 queueing한 후에 새로운 follower노드를 broadcast 리스트에 등록한다.
skip된 메시지를 보존하지 않는 것은 epoch을 이용한다. Zookeeper의 zxid는 64bit 숫자인데, lower 32bit은새로운 proposal을 생성할 때마다 증가하는 counter이고, high order 32bit은 epoch에 해당한다. 새로운 leader가 선출될 때마다 로그 상에 가지고 있는 가장 높은 zxid의 epoch에 1을 더하고, counter를 0으로 리셋한 zxid를 이후의 proposal을 위해 사용한다.
epoch을 통해서 여러 리더들이 동일한 zxid를 사용하는 것을 방지할 수 있을 뿐만 아니라, 더욱 중요하게는, 한번 실패했던 리더가 되살아나더라도 zxid가 낮기 때문에 리더가 될 수 없고, 이 노드가 follower가 되었을 때 leader는 기존 epoch의 proposal을 truncate하도록 해주기 때문에, recovery 과정이 단순해지고 빨라지는 장점을 가지고 있다.
Closing
Raft 등에서도 채용된 여러가지 개념들을 볼 수 있었다는 점이 재미있었다. two-phase commit-like 프로토콜이나 quorum이 유지되는 한 leadership의 유지, epoch (term)의 개념 등. 또한 다른 consensus 프로토콜들을 통해 어렴풋이 추측하고 있던 Zookeeper의 프로토콜에 대해 조금 더 정확하게 이해할 수 있게된 것 같다. 사실 Zab 이외에도 여러가지 알고리즘이나 최적화 등이 Zookeeper에 활용되었으리라 추측하는데, 위에서 언급한 Zookeeper에 관련한 다른 페이퍼들이나 Zookeeper의 코드를 읽어보아도 재미있을 것 같다.