데이터 중심의 애플리케이션 설계 - 합의 알고리즘

합의는 여러 노드가 어떤 것에 동의 하는 것이다. 합의의 문제는 동시 쓰기 문제에서 비롯된다. 예를 들어, 여러 비행기 승객이 마지막 좌석을 예약하기 위해 동시에 예약을 요청했다면 어떤 고객에게 좌석을 부여할지 결정해야 한다.

합의 알고리즘은 다음의 네 가지 사항을 충족해야 한다.

• 만장 일치: 어떤 두 노드도 다른 결정을 할 수 없다.
• 무결성: 어떤 노드도 두 번 결정 할 수 없다.
• 유효성: 노드가 어떤 값 v를 결정한다면, v는 어떤 노드가 제안한 것이라야 한다.
• 종료: 충돌되지 않은 모든 노드는 반드시 결정해야 한다.

합의를 기반으로 하는 시스템 모뎅은 노드가 충돌할 수 있음을 가정한다. 단순히 소프트웨어 충돌이 아닌, 지진으로 인해 데이터센터가 무너질 수도 있음을 가정하는 것이다. 두 단계 커밋과 같이 노드가 복구되길 기다려야 한다면 합의는 종료되지 않을 것이다.

종료 속성은 노드의 절반 미만이 충돌하거나 연결할 수 없다는 가정을 전제로 한다. 그러나 대부분의 합의 구현은 대다수의 노드가 실패하거나 심각한 네트워크 문제가 발생하더라도 안전 속성(합의, 무결성, 유효성)이 항상 충족되도록 보장한다. 따라서 대규모 정전이 발생해도 시스템이 요청을 처리하지 못할 수는 있지만, 잘못된 결정을 내려 합의 시스템을 손상시킬 수는 없다.

대부분의 합의 알고리즘은 비잔틴 결함이 없다고 가정한다. 즉, 노드가 프로토콜을 올바르게 따르지 않을 경우(예를 들어, 서로 모순되는 메시지를 다른 노드에 보내는 경우) 프로토콜의 안전 속성이 깨질 수 있다. 비잔틴 결함이 있는 노드가 1/3 미만인 경우 합의를 비잔틴 결함을 무력화할 수 있다.