합의: 여러 노드가 하나의 결정을 유지하기 위한 문제
분산 합의는 여러 노드가 제안한 값들 중 하나를 결정하고, 참여자들이 서로 모순된 결정을 내리지 않도록 하는 문제다. 단순한 투표 집계보다 어렵다. 노드가 중단되거나 메시지가 늦게 도착해도 이미 결정된 사실을 바꾸지 않아야 한다.
합의는 결정의 일치라는 안전성과 결국 결정한다는 진행 조건을 함께 다룬다.
안전성과 진행은 다른 성질이다
Agreement는 정상 참여자들이 다른 값을 결정하지 않는다는 조건이다. Validity는 결정값이 허용된 제안에서 나와야 한다는 조건이며 정확한 형태는 합의 문제의 모델에 따라 달라진다. Termination은 정상 참여자들이 결국 결정을 내린다는 진행 조건이다.
아무 결정도 하지 않으면 모순된 결정을 피할 수 있지만 종료 조건을 만족하지 못한다. 반대로 아무 값이나 즉시 반환하면 빠르게 끝나도 제안 유효성이나 일치를 어길 수 있다. 합의 알고리즘은 두 종류의 목표를 함께 다룬다.
복제 상태 기계는 같은 초기 상태에서 같은 명령 순서를 적용하면 같은 결과를 얻는다. 그래서 분산 저장소는 “이번 로그 위치에 어떤 명령을 넣을까”를 반복해서 합의한다. 값 하나의 합의와 지속적인 명령 로그를 유지하는 구현 사이에는 추가 복구·진행 규칙이 있다.
Node A proposes command X.
Node B proposes command Y.
Node C has not yet heard either proposal.
Allowed outcome: all deciding nodes choose X.
Allowed outcome: all deciding nodes choose Y.
Forbidden outcome: A decides X while B decides Y for the same slot.
어떤 값이 선택될지는 통신 순서와 프로토콜에 따라 달라질 수 있다. 한 노드가 최초로 받았다는 이유만으로 전체가 같은 최초를 관찰할 수 있다고 가정하면 안 된다.
완전한 비동기 모델의 한계
메시지 지연에 상한이 없고 한 노드가 중단될 수 있는 완전 비동기 모델에서는 결정적 알고리즘이 모든 실행에서 안전성과 종료를 동시에 보장할 수 없다는 FLP 결과가 있다. 이는 합의 구현이 언제나 실패한다는 뜻이 아니라, 항상 종료한다는 보장이 불가능한 실행이 존재한다는 뜻이다.
실제 프로토콜은 안전성을 지키면서 네트워크가 충분히 안정되고 필요한 노드들이 통신하는 기간에 진행하도록 설계한다. 타임아웃은 지연을 의심하는 도구이며, 시간이 지났다는 사실만으로 원격 노드가 실제로 죽었다고 증명하지는 못한다.
Paxos와 Raft의 일반적인 설명은 악의적으로 서로 다른 메시지를 보내는 노드보다 중단 장애를 가정한다. 비잔틴 합의는 다른 모델과 조건이 필요하다. 노드 수나 허용 장애 수의 공식도 그 가정 없이 섞어 쓰면 부정확하다.
합의는 로그 순서, 리더 권한, 설정 변경 같은 결정의 기반이 된다. 하지만 합의 하나가 외부 결제 효과, 여러 데이터베이스의 원자 커밋, 사용자 읽기 보장을 모두 자동으로 해결하지는 않는다. 합의할 대상과 실패 모델을 먼저 정의해야 보장 범위가 명확해진다.