Paxos
두 가지 합의 구축 단계를 사용해 노드 연결이 끊어져도 안전한 합의에 도달할 수 있다.
Problem
여러 노드가 상태를 공유할 때는 특정 값에 대해 서로 합의해야 하는 경우가 많다. 리더와 팔로워가 있는 경우 리더가 값을 결정하여 팔로워에게 전달한다. 하지만 리더가 없는 경우 노드들이 직접 값을 결정해야 한다. 혹은 리더 - 팔로워 구조에서도 리더를 선출하기 위해 이 작업을 수행해야할 수 있다.
리더는 2단계 커밋을 사용하여 복제본이 안전하게 업데이트를 받도록할 수 있지만, 리더가 없으면 경쟁 노드가 쿼럼을 모으려고 시도할 수 있다. 이 과정은 노드가 실패하거나 연결이 끊어질 수 있기 때문에 더욱 복잡해진다. 노드가 특정 값에 대한 쿼럼을 달성할 수 있지만 이 값을 전체 클러스터에 전달하기 전에 연결이 끊어질 수 있다.
Solution
Paxos 알고리즘은 3단계로 작동하여 네트워크 파티션 혹은 노드 장애에도 불구하고 여러 노드가 동일한 값에 동의하도록 한다. 처음 두 단계에서는 값에 대한 합의를 도출하고, 마지막 단계에서는 그 합의를 나머지 복제본에 전달한다.
- 준비 단계 : Generation Clock을 설정하고 이미 허가된 값들을 수집한다.
- 수락 단계 : 복제본에게 이 generation에 대한 값을 수락하도록 제안한다.
- 커밋 단계 : 모든 레플리카에 값이 선택되었음을 알린다.
첫 번째 단계에서 값을 제안하는 노드(제안자)는 클러스터의 모든 노드(수락자)에 연락하여 해당 값을 고려하겠다고 약속할지 묻는다. 정족수 이상의 수락자가 그러한 약속을 반환하면 제안자는 두 번째 단계로 이동한다. 두 번째 단계에서 제안자는 제안된 값을 전송하고, 노드의 정족수가 이 값을 수락하면 해당 값이 선택된다. 마지막 단계에서 제안자는 선택한 값을 클러스터의 모든 노드에 커밋할 수 있다.
Flow of the Protocol
먼저 Pxos 프로토콜의 일반적인 흐름에 대한 예시를 보여준 다음, 프로토콜의 작동 방식에 대해 자세히 살펴본다.
| Proposer | Acceptor |
|---|---|
| Generation Clock에서 다음 generation number를 가져온다. 이 번호를 기반으로 모든 수락자에게 준비 요청을 전송한다. | |
| 준비 요청의 생성 번호가 노드가 알고있는 promised generation 변수보다 늦으면 이 값으로 promised generation을 업데이트하고 promise 응답을 반환한다. 이미 제안을 수락한 경우 수락한 제안을 반환한다. | |
| 수락자 정족수로부터 응답을 받으면 응답에 이미 제안이 수락된 값이 포함되어 있는지 확인한다. 포함되어 있다면 자신의 제안 값을 가장 높은 generation number를 가진 응답으로 변경한다. 그리고 모든 수락자에게 해당 생성 번호와 제안된 값으로 수락 요청을 보낸다. | |
| 수락 요청의 generation number가 알고있는 promised generation 변수보다 늦으면 해당 제안을 수락된 제안으로 저장하고 요청을 수락했다고 응답한다. | |
| 수락자 정족수로부터 성공적인 응답을 받으면 선택한 값을 기록하고 모든 노드에 커밋 메세지를 보낸다. |
Paxos의 기본 규칙들을 살펴보았다. 이제 어떻게 작동하는지 예시를 살펴보자.
다섯개의 노드로 구성된 클러스터를 생각해보자. 클라이언트가 아테네 노드에 접속해 이름을 “alice”로 설정해달라고 요청한다. 이제 아테네 노드는 모든 노드가 이 변경에 동의하는지 확인하기 위해 Paxos 상호작용을 시작해야 한다. 아테네는 다른 모든 노드에게 이름을 “alice”로 변경할 것을 제안하므로 아테네를 제안자라고 한다. 아테네를 포함한 클러스터의 모든 노드는 제안을 수락할 수 있는 수락자다.
아테네가 “alice”를 제안하는 동시에 노드 에페소스는 이름을 “elanor”로 설정하라는 요청을 받는다. 따라서 에페소스도 제안자가 된다.
준비 단계에서 제안자는 몇 가지 준비 요청을 보내며 시작하는데, 요청에는 generation number가 포함된다. Paxos는 단일 장애 지점을 피하기 위한 것이므로 단일 generation clock에서 이 값을 가져가지 않는다. 대신 각 노드는 generation number와 노드 ID를 결합한 자체 generation clock을 유지한다. 노드 ID는 동률을 끊는데 사용되는데, [2,a] > [1,e] > [1,a] 순이다. 각 수락자는 지금까지 본 가장 최근의 promise를 기록한다.
| Node | Athens | Byzantium | Cyrene | Delphi | Ephesus |
|---|---|---|---|---|---|
| promised generation | 1,a | 1,a | 0 | 1,e | 1,e |
| accepted value | none | none | none | none | none |
그 이전에는 어떤 요청도 본 적 없으므로 모두 호출 제안자에게 promise를 반환한다. 반환된 값을 promise라고 부르는데, 이는 수락자가 약속된 generation clock보다 빠른 메세지를 고려하지 않겠다고 약속한다는 의미다.
아테네는 준비 메세지를 키레네에게 보낸다. 아테네가 응답으로 promise를 받으면 이는 이제 쿼럼을 나타내는 5개의 노드 중 3개의 노드로부터 promise를 받았다는 것을 의미한다. 이제 아테네는 준비 메세지 전송에서 수락 메세지 전송으로 전환한다.
아테네가 클러스터 노드 과반수로 부터 promise를 받지 못할 수도 있다. 이 경우 아테네는 generation clock을 증가시켜 준비 요청을 다시 시도한다.
| Node | Athens | Byzantium | Cyrene | Delphi | Ephesus |
|---|---|---|---|---|---|
| promised generation | 1,a | 1,a | 1,a | 1,e | 1,e |
| accepted value | none | none | none | none | none |
이제 아테네는 generation과 제안된 값이 포함된 수락 메세지를 전송하기 시작한다. 아테네와 비잔티움이 제안을 수락한다.
| Node | Athens | Byzantium | Cyrene | Delphi | Ephesus |
|---|---|---|---|---|---|
| promised generation | 1,a | 1,a | 1,a | 1,e | 1,e |
| accepted value | alice | alice | none | none | none |
에페소스는 이제 키레네에게 준비 메세지를 보낸다. 키레네는 아테네에게 promise를 보냈지만 에페소스의 요청이 더 높은 generation이므로 에페소스의 요청이 우선된다. 키레네가 에페소스에게 promise를 다시 보낸다.
이제 키레네는 아테네로부터 수락 요청을 받지만 generation number가 에페소스와의 promise보다 뒤처져 있기 때문에 이를 거부한다.
| Node | Athens | Byzantium | Cyrene | Delphi | Ephesus |
|---|---|---|---|---|---|
| promised generation | 1,a | 1,a | 1,e | 1,e | 1,e |
| accepted value | alice | alice | none | none | none |
이제 에페소스는 준비 메세지에서 정족수를 확보했으므로 수락 단계로 넘어갈 수 있다. 자신과 델파이에게 수락 요청을 보냈지만 더 이상의 수락 요청을 보내기 전에 다운되어 버린다.
| Node | Athens | Byzantium | Cyrene | Delphi | Ephesus |
|---|---|---|---|---|---|
| promised generation | 1,a | 1,a | 1,e | 1,e | 1,e |
| accepted value | alice | alice | none | elanor | elanor |
한편 아테네는 키레네의 수락 요청이 거부된 것을 처리해야 한다. 이는 더 이상 정족수를 채울 수 없음을 의미하며, 따라서 제안은 실패하게 된다. 이렇듯 제안자가 초기 쿼럼을 상실하는 경우는 항상 발생할 수 있다. 다른 제안자가 쿼럼을 달성하기 위해 초기 제안자중 하나 이상의 멤버가 이탈하는 경우이다.
간단한 2단계 커밋이 있는 상황에서는 에페소스가 계속 진행되어 해당 값이 선택되기를 기대할 수 있지만, 에페소스가 다운되었기 때문에 이러한 계획은 이제 문제가 될 수 있다. 수락자 정족수에 제한이 있다면 에페소스의 충돌로 인해 전체 제안 프로세스가 교착 상태에 빠질 수 있다. 그러나 paxos는 이런 일이 일어날 것으로 예상했기 때문에 아테네는 이번에 더 높은 generation을 대상으로 재시도를 하게 된다.
준비 메세지를 다시 보내지만 이번에는 generation number가 더 높다. 첫 번째 라운드와 마찬가지로 3가지 promise를 반환하지만 중요한 차이점이 있다. 아테네는 이미 “alice”를 수락했고, 델파이는 “elanor”를 수락했다. 이 두 수용자는 모두 promise를 반환하지만 이미 수락한 제안의 generation number와 함께 이미 수락한 값도 반환한다. 해당 값을 반환하면 아테네에 한 약속을 반영해 promised generation을 [2,a]로 업데이트 한다.
| Node | Athens | Byzantium | Cyrene | Delphi | Ephesus |
|---|---|---|---|---|---|
| promised generation | 2,a | 1,a | 2,a | 2,a | 1,e |
| accepted value | alice | alice | none | elanor | elanor |
이제 정족수를 채운 아테네는 수락단계로 넘어가야 하는데, promised 응답에서 받은 이미 수락된 값 중 가장 높은 “elanor”를 제안해야 한다. 아테네가 [1,a]로 수락한 “alice”보다 더 큰 generation number를 가졌기 때문이다.
아테네가 수락 요청을 보내기 시작하는데 이번에는 “elanor”와 함께 현재 generation number가 보내진다. 아테네가 자신에게 수락 요청을 보내고 이를 수락한다. 이는 중요한 수락인데, 이제 “elanor”를 수락하는 노드가 세 개가 되어 “elanor”에 대한 정족수가 충족되므로 “elanor”를 선택된 값으로 간주할 수 있기 때문이다.
| Node | Athens | Byzantium | Cyrene | Delphi | Ephesus |
|---|---|---|---|---|---|
| promised generation | 2,a | 1,a | 2,a | 2,a | 1,e |
| accepted value | elanor | alice | none | elanor | elanor |
“elanor”가 선택된 값임에도 불구하고 아직 아무도 이를 인지하지 못하고 있다. 수락 단계에서 아테네는 정족수에 미달하고 에페소스는 오프라인 상태이므로 “elanor”가 값으로 선택되었다는 것만 인지하고 있다. 아테네는 수락 요청이 몇 개만 더 수락되면 커밋할 수 있다. 하지만 이제 아테네는 다운된다.
이 시점에서 아테네와 에페소스는 크래시되었다. 그러나 클러스터에는 여전히 노드 정족수가 작동 중이므로 계속 작동할 수 있으며, 실제로 프로토콜을 따르면 “elanor”가 선택된 값이라는 것을 발견할 수 있다.
키레네는 이름을 “carol”로 설정하라는 요청을 받으므로 제안자가 된다. [2,a] generation을 보았으므로 [3,c] generation으로 준비 단계를 시작한다. “carol”로 이름을 제안하고 싶지만 지금은 준비 요청만 발행하고 있다.
키레네는 클러스터의 나머지 노드에 준비 메세지를 보낸다. 아테네의 이전 준비 단계와 마찬가지로 키레네는 수락된 값을 받환받으므로 “carol”은 값으로 제안되지 않는다. 이전과 마찬가지로 델파이의 “elanor”는 비잔티움의 “alice”보다 늦기 때문에 키레네는 “elanor”와 [3,c]로 수락 단계를 시작한다.
| Node | Athens | Byzantium | Cyrene | Delphi | Ephesus |
|---|---|---|---|---|---|
| promised generation | 2,a | 3,c | 3,c | 3,c | 1,e |
| accepted value | elanor | alice | none | elanor | elanor |
계속해서 노드를 크래시하고 깨울 수는 있지만, 이제 “elanor”가 승리할 것이 분명해졌다. 노드의 정족수가 충족되는 한, 적어도 하나 이상의 노드는 “elanor”를 값으로 사용할 것이며 준비를 시도하는 노드는 준비 단계에 대한 정족수를 확보하기 위해 “elanor”를 수락한 노드 한 곳에 연락해야 할 것이다. 키레네가 커밋을 보내면서 합의는 마무리된다.
언젠가 아테네와 에페소스가 다시 온라인 상태가 되면 쿼럼이 무엇을 선택 했는지 알게 될 것이다.
Requests don’t need to be rejected
위의 예시에서는 오래된 generation의 요청을 거부하는 수락자를 봤다. 하지만 프로토콜은 이와 같은 명시적 거부를 요구하지 않는다. 공식화된 대로 수락자는 오래된 요청을 무시할 수도 있다. 이 경우에도 프로토콜은 여전히 단일 합의 값으로 수렴한다. 이는 프로토콜의 중요한 특징인데, 분산 시스템이기 때문에 언제든지 연결이 끊어질 수 있으므로 프로토콜의 안전성을 보장하기 위해 거부에 의존하지 않는 것이 유리하기 때문이다. 여기서 안전성이란 프로토콜이 하나의 값만 선택하고, 한 번 선택된 값은 덮어쓰지 않는다는 것을 의미한다.
그러나 거부를 보내는 것은 성능을 개선하기 때문에 여전히 유용하다. 제안자가 자신이 오래된 제안자라는 사실을 빨리 알면 알수록 더 높은 세대의 제안자들과 더 빨리 다른 라운드를 시작할 수 있다.
Competing proposers may fail to choose
이 프로토콜이 잘못될 수 있는 한 가지 방법은 두 명 이상의 제안자가 한 사이클에 들어오는 경우이다.
- alice는 아테네와 비잔티움에 의해 수락된다.
- elanor는 모든 노드에 의해 준비되어 alice가 정족수를 확보하지 못한다.
- elanor는 델파이와 에페소스에 의해 수락된다.
- alice는 모든 노드에 의해 준비되어 elanor가 정족수를 확보하지 못한다.
- alice는 아테네와 비잔티움에 의해 승인된다.
- … 등등의 상황을 livelock이라 한다.
FLP 불가능 결과는 결함이 있는 노드 하나만 있어도 클러스터가 값을 선택하지 못할 수 있음을 보여준다.
제안자가 새로운 generation을 선택해야 할 때마다 무작위로 일정 시간을 기다리도록 함으로써 이러한 livelock이 발생할 가능성을 줄일 수 있다. 이러한 무작위성을 통해 다른 제안자가 전체 정족수에 준비 요청을 보내기 전에 정족수를 수락할 수 있을 가능성이 높아진다.
하지만 livelock이 발생하지 않도록 보장할 수는 없다. 이는 근본적인 트레이드 오프이며, 안전과 livelock중 하나를 보장할 수는 있지만 둘 다 보장할 수는 없다. Paxos는 안전을 최우선으로 보장한다.