Paper: Paxos Made Live – An Engineering Perspective
이 논문은 Paxos를 실제로 구현하고자 할 때 고려해야할 현실적인 문제들과 해결방식을 설명하고 있다. Google은 Chubby에서 필요로하는 분산 로그 스토리지를 위해 기존의 상용 솔루션을 대체하는 Paxos를 구현하게 되었다고 한다.
Paxos를 이용한 분산 로그 스토리지의 기본적인 아이디어는 데이터베이스 오퍼레이션에 대해서 Paxos 알고리즘을 반복적으로 적용하면, 복제본들 사이에 데이터베이스 오퍼레이션들의 로그를 동일하게 쌓아올릴 수 있고, 결과적으로 분산 로그 스토리지를 구현할 수 있게 된다. Chubby가 기반하고 있는 분산 DB는 Paxos로 구현된 분산 로그 스토리지에 저장된 데이터오퍼레이션들의 리플레이 로그와, 스냅샷을 관리한다. 흥미로운 점은 분산 로그 스토리지는 다른 분산 시스템을 만들 때에도 강력한 기초가 될 수 있기 때문에, 분산 로그와 분산 DB 레이어 사이를 깔끔한 인터페이스로 정의해서 분산 로그를 재사용할 수 있도록 모듈화를 꾀한 점이다.
이 논문에서는 Paxos 알고리즘에 대한 괜찮은 설명이 나오는데, Multi-Paxos에 대한 언급도 나온다. 그동안 Paxos 알고리즘의 최적화에 해당하는 Multi-Paxos라는 단어를 도입한 것이 이 논문이라고 생각하고 있었는데, 이번에 블로그 글을 정리하다가 다시 찾아보니, 애초에 Paxos의 오리지널 논문인 Lamport의 “Part-time Parliament”에서 Multi-decree parliament라는 알고리즘으로 소개되고, 이를 Prisco, Lampson, Lynch의 “Revisiting the Paxos algorithm”에서 처음으로 “Multi-Paxos”라는 이름을 사용한 것으로 보인다.
Handling disk corruption
디스크 손상에 의한 두가지 상황, 즉 파일의 내용이 바뀌었거나 파일 자체가 없어지는 경우에 대한 탐지 방법을 제시하고 있다. 전자는 각 파일에 대한 checksum을 유지하는 방법으로 해결하고, 후자는 리플리카였음을 나타내는 marker를 GFS에 보관하는 방법으로 디스크 손상을 탐지한다. (이러한 방법과 관련해 역시 유명한 Viewstamped Replication 논문을 인용하고 있으므로 나중에 꼭 읽어보도록 하자.)
디스크 손상이 탐지되었을 경우에는 리빌드를 진행하게 되는데, non-voting member 즉, promise나 acknowledgement 메시지에는 응답하지 않는 노드로서 Paxos에 참가하고 catch-up mechanism을 사용한다. catch-up mechanism 자체에 대해서는 이 논문에는 그리 자세한 설명은 없다.
이렇게 디스크 손상에 대비하는 메커니즘이 있다면 모든 쓰기를 디스크에 바로 flush하지 않아도 되는 최적화가 가능해진다.
Master leases
stale data를 읽지 않도록 보장하기 위해서는, 읽기 오퍼레이션 조차도 Paxos로 실행해서 다른 업데이트들과 직렬화되도록 하는 것이 필요하다. 일반적으로 읽기 오퍼레이션이 대부분의 오퍼레이션을 차지하므로 이는 매우 비효율적이다.
이에 대한 해결책으로 제시하는 것이 마스터 리스이고, 이는 마스터가 리스를 가지고 있는 동안에는 다른 복제본이 Paxos로 업데이트를 진행할 수 없는 것을 보장하기 때문에, 읽기 오퍼레이션을 로컬에서 제공할 수 있게 된다. 그리고, 리스가 만료되기 전에 보통 갱신되기 때문에 마스터가 대체로 항상 리스를 가지고 있게 된다.
Epoch numbers
어떤 복제본으로 업데이트 요청이 왔을 때 마스터의 지위를 잃어버리거나 다시 얻었다면, 그 요청은 중단되어야 하는데, 이를 구분하기 위해 어떤 마스터가 연속적으로 재임하는 동안에는 같은 값으로 유지되는 Epoch number라는 개념을 도입하고 있다. 아마도 Raft 알고리즘의 term과 동일한 개념이 아닐까 싶다.
Group membership
그룹 멤버쉽 문제란 복제본이 추가되거나 제거되는 등 복제본의 집합에 일어난 변화를 어떻게 다루는지에 대한 문제다. 그룹 멤버쉽 문제에도 Paxos를 활용해 해결할 수가 있다는 아이디어를 인용하고 있는데, 아이디어 자체는 단순하나 – 복제본 집합의 변화의 로그를 Paxos로 유지하면 될 것이다 – 디스크 손상 등의 문제들을 고려해서 구현하는 것은 쉽지 않다고 얘기하고 있다.
Snapshots
로그를 무한정 쌓을 수 없으므로 스냅샷을 생성해서 기존의 로그가 필요하지 않게 만드는 메커니즘을 필요로 한다. Paxos 자체는 복제된 로그의 일관성에만 관심이 있지, 복제되고 있는 데이터 구조 자체에 대해서는 인지하지 못하므로, 스냅샷을 생성하는 것은 애플리케이션의 책임이 된다. 따라서, 애플리케이션은 자유롭게 스냅샷을 생성하고, 스냅샷이 생성된 것에 대해서 Paxos 프레임워크 쪽에 알려주어, Paxos 프레임워크가 스냅샷 이전의 로그를 삭제할 수 있도록 한다. 스냅샷은 복제본 사이에 동기화되지 않으며, 각각의 복제본은 독립적으로 스냅샷을 생성할 시점을 결정한다.
이러한 메커니즘은 간단해보이지만, 로그와 스냅샷이 서로 일관성있게 유지되도록 하기 위한 복잡성들이 존재한다.
- 각각의 스냅샷에 관련된 모든 Paxos 관련 정보 – 스냅샷을 생성하는 시점의 Paxos instance number와 그 시점의 그룹 멤버쉽 – 를 담고 있는 스냅샷 핸들이라는 개념이 존재한다. 스냅샷을 복구할 때는, 애플리케이션은 스냅샷 핸들을 Paxos 프레임워크 쪽에 전달하고, Paxos 프레임워크 이를 이용해 복구를 진행한다.
- 클라이언트가 스냅샷을 생성하려고 할 때는 먼저 스냅샷 핸들을 요청한다. 클라이언트는 스냅샷을 생성하는데, 이 스냅샷은 스냅샷 핸들의 정보와 일관되어야 하므로 Paxos가 진행됨에 따라서 업데이트라 발생하는 것에 대해서 주의를 기울여야 한다. 마지막으로 스냅샷이 생성되었다면 클라이언트는 Paxos 프레임워크에 스냅샷 핸들을 전달하면서 스냅샷이 생성되었음을 알린다. 스냅샷의 생성에 실패했다면 단순히 Paxos 프레임워크에 이를 알리지 않는 것으로 충분하다.
- catch-up을 위해서는 다른 복제본으로부터 최근의 스냅샷을 얻어오고, 나머지 로그 레코드들도 다른 복제본으로부터 얻어온다.
Database transactions
CAS (compare and swap) 오퍼레이션을 atomic하게 유지하기 위해서 CAS에 관련된 데이터를 Paxos 상에서의 하나의 값으로 취급한다. 실제로 데이터베이스 트랜잭션을 구현하지 않더라도, 이러한 방식을 확장함으로써 트랜잭션 스타일의 지원이 가능하다.
MultiOp은 이러한 트랜잭션 지원을 위해 atomic하게 적용되고 guard, top, fop의 세가지 부분으로 이루어져 있다. guard라고 불리는 테스트의 리스트가 한가지 부분이고, 이 모든 테스트가 참이라면 데이터베이스 오퍼레이션의 리스트인 top을 실행하고, 그렇지 않다면 역시 데이터베이스 오퍼레이션의 리스트인 fop을 실행한다.
Software Engineering
알고리즘의 표현, 실행시간 일관성 검증, 테스팅, 동시성 등에 관련한 이슈들을 설명하고 있는데, 특별히 흥미로운 테스팅 항목에 대해 살펴보자.
시스템에 랜덤한 실패들을 집어넣더라도 Safety와 Liveness를 만족하는지를 테스트하는데, 테스트가 실패했을 때 이를 재현할 수 있어야 하므로, 테스트가 시작할 때 설정된 시드를 확보해서 동일한 테스트를 재현할 수 있도록 하고 있다.
이외에도 Chubby 시스템이 하위 시스템의 실패에도 잘 동작하는지를 테스트하기 위해서, 분산 로그 시스템에 여러 hook을 구현하고 역시 랜덤하게 실패하도록 했을 때 Chubby 시스템이 그러한 실패들을 잘 극복하는지를 테스트 하기도 한다.
이러한 테스트 방식은 체계적인 방식은 아니나, 최근 분산시스템을 테스트하는 것에 대해서는 일반적인 방법으로 자리잡아 나가고 있는 것 같다.
Summary
이 논문의 마지막 부분은 컴파일러 개발 분야가 매우 복잡하지만, 이론이 널리 알려져있고 yacc, ANTLR 등의 도구와 같이 현실에도 잘 적용되어있는 점을 지적하면서, 분산시스템 분야는 그렇지 않음을 지적하고 있다.
- There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions. The cumulative effort will be substantial and the final system will be based on an unproven protocol.
- The fault-tolerance computing community has not developed the tools to make it easy to implement their algorithms.
- The fault-tolerance computing community has not paid enough attention to testing, a key ingredient for building fault-tolerant systems.
References
Paxos는 Paxos made simple을 통해서 공부했었는데, 시간이 날 때 오리지널 페이퍼인 Lamport, Leslie. "The part-time parliament." ACM Transactions on Computer Systems (TOCS) 16.2 (1998): 133-169.를 읽어보는 것이 좋을 듯 하다.
리스에 관해서는 Gray, Cary, and David Cheriton. Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. Vol. 23. No. 5. ACM, 1989.을 참고하자.
그룹 멤버쉽 문제에 관해서 Cristian, Flaviu. "Reaching agreement on processor-group membership in synchronous distributed systems." Distributed Computing 4.4 (1991): 175-187.