팍소스 알고리즘 (Paxos algorithm)
쉽게 풀면
팍소스는 여러 노드가 참여해 제안을 내고 투표하는 과정을 통해 합의에 이르는 알고리즘이다. 제안자가 값을 제안하면 다수의 노드(과반수)가 이를 승인해야 하며, 과반수의 동의를 얻은 값만이 최종적으로 확정된다. 과반수 개념을 사용하기 때문에 일부 노드가 고장 나거나 응답하지 않아도, 살아있는 과반수만 합의에 참여하면 시스템 전체는 계속 동작할 수 있다. 이론적으로 정확하지만 이해하기 어렵기로 유명하여, 이후 더 이해하기 쉬운 것을 목표로 만들어진 라프트 알고리즘이 실무에서 대안으로 자주 쓰인다.
왜 중요한가
팍소스는 분산 시스템에서 여러 노드가 장애나 네트워크 지연 속에서도 하나의 값에 합의할 수 있음을 최초로 엄밀하게 증명한 알고리즘이어서, 이후 등장한 대부분의 합의 알고리즘과 분산 데이터베이스 설계의 이론적 토대가 되었습니다. 대규모 분산 시스템에서 리더 선출, 복제 로그 관리, 분산 락 서비스 등을 구현할 때 결국 팍소스나 그 변형이 근간에 자리 잡고 있어, 분산시스템 논문에서 배경 이론으로 빈번하게 인용됩니다.
논문에서는 이렇게 쓰입니다
분산 시스템에서 장애를 견디며 값에 대한 합의를 이루는 구체적인 알고리즘을 명시할 때 사용된다.
단일 값이 아니라 연속적인 로그 항목들의 순서에 합의해야 하는 상태 머신 복제 시스템에서 쓰이는 표현이다.
서로 다른 합의 알고리즘의 성능을 비교하는 분산시스템 벤치마크 연구에서 쓰이는 예이다.
조금 더 깊게 보면
팍소스는 크게 제안자가 먼저 과반수 노드로부터 준비 승낙을 받는 단계와, 실제 값을 제안해 과반수의 수락을 받는 단계로 구성되며, 이 두 단계 구조 덕분에 노드 장애나 메시지 유실이 있어도 안전성(서로 다른 값이 동시에 확정되지 않음)을 보장할 수 있습니다. 다만 원본 알고리즘은 단일 값에 대한 합의만 다루기 때문에, 실제 시스템에서는 연속된 로그 항목마다 팍소스를 반복 적용하는 다중 팍소스(multi-paxos) 형태로 확장해서 사용하는 경우가 대부분입니다. 논문에서 라프트와 비교할 때는 안전성 증명의 엄밀함은 팍소스가 앞서지만, 구현과 이해의 용이성 면에서는 라프트가 실무적으로 선호된다는 점이 자주 언급됩니다.
주의할 점
팍소스는 이론적으로 견고하지만 원본 논문의 설명이 난해하기로 악명 높아, 실제 구현에서는 이해와 구현이 더 쉬운 라프트 알고리즘이 대안으로 널리 채택된다.