이번 포스팅에서는 Paxos 알고리즘에 대해 살펴보겠습니다. 분산 시스템에서 여러 대의 서버가 서로 다른 데이터를 가지고 있을 수 있기 때문에 동시성과 일관성을 보장하는 것은 쉬운 문제가 아닙니다. 이런 문제를 해결하기 위해 분산 환경에서 노드 간 합의를 도출하는 알고리즘인 Paxos가 등장하게 되었습니다.
Paxos 알고리즘은 Leslie Lamport가 제안한 알고리즘으로, 분산 시스템에서 노드 간 합의를 도출하는 알고리즘 중 가장 널리 사용되는 알고리즘 중 하나입니다. 이번 포스팅에서는 Leslie Lamport의 "Paxos Made Simple" 논문을 읽고 Paxos가 어떻게 분산 환경에서 노드 간 합의를 도출하는지 살펴보겠습니다.
하지만 논문만으로는 이해가 쉽지 않기 때문에, 논문의 내용을 이해하기 쉽게 보완하여 Paxos에 대해 설명드리겠습니다. 이번 포스팅을 통해 Paxos 알고리즘의 핵심 아이디어와 동작 방식을 이해하고, 분산 시스템에서 합의를 도출하는 방법을 이해해 보도록 하겠습니다.
Introduction
Leslie Lamport는 "The Part-Time Parliament"라는 논문을 통해 처음으로 Paxos 알고리즘을 제안했습니다. 그러나 이 논문의 내용은 매우 난해하고 이해하기 어려워, Paxos 알고리즘이 널리 사용되기까지는 시간이 걸렸습니다.
그 이후 Leslie Lamport는 "Paxos Made Simple" 논문을 쓰면서, Paxos 알고리즘의 핵심 아이디어와 동작 방식을 보다 쉽게 설명했습니다. 이를 통해 Paxos 알고리즘이 널리 사용되고, 분산 시스템에서 합의를 도출하는 데 필수적인 알고리즘 중 하나가 되었습니다.
The Consensus Algorithm
The Problem
Paxos는 분산환경에서 클러스터의 노드 간 합의(consensus)를 도출하는 알고리즘 중 하나입니다. Paxos의 특징을 살펴보기 앞서 해당 논문에서 활용하는 용어부터 소개하겠습니다.
- Majority: Majority는 클러스터 전체 노드의 절반을 초과하는 수를 의미합니다. Majority가 중요한 이유는, Majority 이상의 노드가 동의하는 경우에만 합의가 성립되기 때문입니다.
- Message: 노드 간의 통신을 통해 데이터를 주고받는데, 이를 Message라고 표현합니다. Message는 노드 간에 전달되는 데이터를 말합니다.
다음은 Paxos에서 정의하는 분산환경에서의 클러스터 특징입니다.
1. 클러스터 내의 노드는 언제든 실패할 수 있습니다.
2. 클러스터 내 노드의 역할은 3가지입니다. Proposer, acceptor, learner. 하나의 노드는 하나 이상의 역할을 맡을 수 있습니다(이번 포스팅에서는 learner에 대해 살펴보지 않겠습니다).
We let the three roles in the consensus algorithm be performed by three classes of agents: proposers, acceptors, and learners. In an implementation, a single process may act as more than one agent, but the mapping from agents to processes does not concern us here.
3. 각 노드의 메시지 처리 속도는 제각각이고, 언제든 실패할 수 있습니다. 또한 노드는 재시작될 수도 있습니다.
Agents operate at arbitrary speed, may fail by stopping, and may restart.
4. 각 노드는 디스크 등의 stable storage를 가집니다.
Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be remembered by an agent that has failed and restarted.
5. 메시지가 전달되는데 오래 걸리 수 있으며, 중복되거나 유실될 수 있습니다. 하지만 메시지 자체가 의도치 않은 방향으로 변경되는 것은 가정하지 않습니다.
Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted.
Paxos 알고리즘을 이해하기 위해서는 Majority라는 개념을 이해하는 것이 매우 중요합니다. Majority는 클러스터 내 전체 노드 수의 절반을 초과하는 노드 수를 의미합니다. Paxos에서는 Majority 이상의 노드가 합의를 도출하면, 해당 값이 클러스터 내 모든 노드가 합의한 값으로 간주됩니다.
예를 들어, 클러스터 내 전체 노드 수가 7개라고 가정하면, Majority는 4개 이상의 노드를 의미합니다. 따라서, 4개 이상의 노드가 동의한 경우에만 합의가 도출됩니다. 만약 Majority 이상의 노드가 특정 값 A에 대해 합의를 도출한다면, 해당 값은 클러스터 내 모든 노드가 합의를 도출한 것으로 간주됩니다.
또한, Majority가 A를 선택하는 과정에 있는 경우와 동시에 또 다른 Majority가 C를 선택하는 과정에 있는 경우도 있을 수 있습니다. 이 경우에는 A를 선택한 Majority와 C를 선택한 Majority에 모두 포함된 노드를 통해 최종 합의 값을 결정할 수 있습니다. 아래 그림에서는 중간에 위치한 노드가 A를 선택한 Majority와 C를 선택한 Majority 모두에 포함되는 것을 확인할 수 있습니다.
Choosing a Value
Paxos 알고리즘은 크게 phase1과 phase2로 나뉘어져 있습니다. Phase1은 prepare과 promise를, 그리고 phase2에서는 accept 메시지를 주고받습니다.
1. Prepare: proposer은 n 대의 acceptor 노드에게 prepare 요청을 통해 특정 값을 제안합니다.
요청은 다음과 같은 데이터를 포함합니다.
- Round Id: 이전 합의 과정에서 사용되지 않은 유일한 값입니다. 단조 증가하는 값을 사용할 수 있습니다. Round Id는 Acceptor이 여러 prepare 또는 accept 메시지를 수신하였을 때 어떤 값을 선택할지 결정하는데 활용합니다.
- Server Id: 다수의 노드가 동시에 Propose를 수행하면 Round Id가 동일할 수 있습니다. 이를 구분하기 위해 각 서버는 고유한 Server Id 값을 가지고 있습니다. 이는 각 노드를 고유하게 식별하고, 합의 과정에서 메시지를 구분하기 위한 용도로 사용됩니다.
- Value: Proposer가 제안하고자 하는 값을 의미합니다.
2. Acceptor는 다수의 prepare 요청을 동시에 받은 상태일 수 있습니다. Acceptor은 prepare 요청 중 round id가 가장 높은 메시지를 선택하고 해당 값을 사용하겠음을 약속하는 promise 응답을 proposer에 반환합니다.
3. Proposer이 majority 이상의 acceptors로부터 promise 메시지를 수신하였다면 제한했던 값을 사용하자는 accept 메시지를 acceptors에 송신합니다.
4. Acceptor는 수신된 accept 메시지의 round id보다 높은 round id를 지닌 prepare 요청을 받지 않는 이상 accept 메시지의 값을 사용하기로 합의합니다. Accepted 메시지 응답을 통해 합의 과정을 마무리합니다.
Acceptor Failure
Accepted 실패
다음은 acceptor 노드가 요청을 처리하지 못하는 상황에 대해 살펴보겠습니다.
우선 1대의 Acceptor만이 실패한 경우를 생각해보겠습니다. 이 경우, Proposer는 1대의 Acceptor로부터 accepted 메시지를 수신하고, 자기 자신으로부터도 accepted 메시지를 수신한 것으로 간주됩니다(실제로는 자기 자신과 accepted 메시지를 주고받지 않습니다. 하지만 자신이 제안한 값이기 때문에 해당 메시지를 accepted 한 상태로 간주할 수 있습니다). 이러한 상황에서, 총 3대의 노드를 소유한 클러스터에서 majority(3 / 2 + 1), 즉 2대 이상이 accepted 완료했기 때문에 정상적으로 합의를 도출할 수 있습니다.
하지만, 만약 2대의 Acceptors가 실패한 경우에는 어떨까요? 이 경우, 최종적으로 Proposer 1대의 노드만이 accepted 상태가 되기 때문에 Majority가 아닌 상황이 됩니다. 따라서 합의에 실패하게 됩니다.
Majority 이상의 노드가 동작한다면 합의 과정은 정상적으로 수행될 수 있습니다.
Promise 실패
Promise 실패 케이스도 위에서 살펴본 accepted 실패 케이스와 유사합니다. 만약 majority 이상의 노드가 promise 응답을 반환한다면 합의과정은 정상적으로 수행됩니다.
Proposer Failure
Promise 실패
Promise 단계에서 proposer이 실패하는 경우 동작하는 노드 중 하나가 proposer으로 선출돼서 합의 과정을 이어나갈 수 있습니다.
Accept 실패
만약 어떤 acceptor도 accept 메시지를 수신하지 못한다면, 합의 과정은 중단됩니다. 그러나, 만약 accept 메시지가 하나 이상의 acceptor에게 전달된 경우 새로운 proposer에 의해 이전의 합의과정이 이어질 수 있습니다.
위 그림을 보면, accept 메시지 "(1,1) 버거"가 하나의 acceptor에만 수신된 것을 확인할 수 있습니다. 이 acceptor는 다음 prepare 메시지 "(2,2) 피자"를 수신할 때 이전에 받은 accept 메시지 "(1, 1) 버거"를 함께 전달하여, 이전 합의 과정에서 이미 선택된 값이 있음을 알립니다. 따라서 5번 과정에서 promise 응답 메시지를 보낼 때, 이전 합의 과정에서 수신한 accept 메시지의 값을 함께 전달합니다. 이전 합의 과정에 이미 accept 메시지의 값이 있으면, 새로운 proposer는 해당 값을 사용하여 합의 과정을 이어갑니다(round id와 server id는 새로운 proposer이 지정한 값을 사용합니다).
마무리
이번 포스팅을 통해 분산환경에서 합의를 도출하는 대표적인 알고리즘인 Paxos에 대해 살펴봤습니다. 다음 포스팅으로는 분산 시스템을 구축하는데 가장 많이 사용되는 알고리즘인 Raft 알고리즘에 대해 대해 살펴보겠습니다.
Reference
https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
https://www.youtube.com/watch?v=SRsK-ZXTeZ0
'논문' 카테고리의 다른 글
| Cassandra는 어떻게 대규모 쓰기를 처리할까 (2) | 2023.04.22 |
|---|---|
| LSM-Tree는 왜 사용할까 (0) | 2023.04.11 |