Paxos 기능 개발기 - 개념정리(1)

본 내용은 연구자료로 실제 정보와 다를 수 있습니다. 

본문 오류 및 잘못된 개념은 댓글로 피드백 부탁드립니다.  

 

 

😃 Paxos

Paxos는 분산 시스템에서 일관성과 내고장성을 보장하기 위한 알고리즘입니다. Paxos 알고리즘은 여러 개의 노드가 협력하여 합의를 도출하는 과정을 거칩니다.

• 일관성 : 분산 시스템 내의 모든 노드가 동일한 데이터를 가지고 있음
• 내고장성 : 분산 시스템에서 일부 노드의 장애나 오류로 인해 시스템 전체가 정상적으로 동작하지 않더라도 데이터의 일관성과 신뢰성을 유지할 수 있는 능력

 

 

 

🤜 Paxos의 구성요소

Paxos 알고리즘은 Proposer(제안자), Acceptor(수락자), Learner(학습자)라는 세 가지 주요 구성요소로 이루어져 있습니다. 

• Proposer(제안자): Proposer는 값의 제안을 시작하는 역할을 합니다. Prepare 단계에서 다른 노드들에게 제안을 보내고, Accept 단계에서 다수의 응답을 받은 후 수락 메시지를 전송합니다.
• Acceptor(수락자): Acceptor는 제안자로부터의 제안을 받고, 해당 제안을 수락하거나 거절하는 역할을 합니다. Accept 단계에서 제안자로부터의 제안을 받으면 수락 응답을 전송합니다.
• Learner(학습자): Learner는 최종적으로 합의된 값을 학습하는 역할을 합니다. Learn 단계에서 합의된 값에 대해 학습합니다.

 

이처럼 일련의 합의 과정을 통해서 합의된 값을 로그에 기록하여 관리합니다. 하지만  분산 시스템에서 일관성과 내고장성을 보장하기 위한 알고리즘이 Paxos 하나뿐일까요? 다음을 보면서 확인해봅시다. 

 

 

 

 

👐 Raft와 Paxos의 비교

Raft와 Paxos는 모두 분산 시스템에서 일관성과 내고장성을 보장하기 위한 알고리즘입니다. 하지만 두 알고리즘은 몇 가지 차이점이 있습니다.

1. 안정성: Paxos는 매우 복잡한 알고리즘이기 때문에 구현하기가 어렵습니다. 반면에 Raft는 비교적 간단하고 이해하기 쉬운 알고리즘입니다.
2. 리더 선택: Paxos는 여러 개의 리더를 동시에 선택할 수 있습니다. 반면에 Raft는 오직 하나의 리더만 선택할 수 있습니다.
3. 로그 복제: Paxos는 로그 복제를 위해 다단계 합의 프로토콜을 사용합니다. 이는 알고리즘의 복잡성을 증가시키지만, 성능 면에서 유리합니다. 반면에 Raft는 로그 복제를 단계적으로 처리하므로 구현하기가 더욱 단순해집니다.
4. 리더 선출: Paxos는 리더 선출을 위해 보다 복잡한 메커니즘을 사용합니다. 반면에 Raft는 선거 과정을 단순화하여 리더 선출을 보다 효율적으로 수행할 수 있습니다.

 

다른점에 대한 카테고리를 나눠봤는데, 하나하나 살펴볼까요?

 

 

 

 

🙋‍♂️ Paxos에서의 리더 선택

Paxos 알고리즘은 분산 시스템에서 합의를 도출하기 위해 리더를 선출하는 과정을 포함하고 있습니다. 리더 선출 과정은 다음과 같습니다:

1. 제안자(Proposer)는 리더 선출을 시작하기 위해 Prepare 메시지를 모든 노드에게 보냅니다.
2. Acceptor는 Prepare 메시지를 받으면, 현재까지 가장 높은 수락된 제안 번호를 응답으로 보냅니다.
3. 제안자는 다수의 응답을 수신한 후, 가장 높은 수락된 제안 번호와 함께 Accept 메시지를 전송합니다.
4. Acceptor는 Accept 메시지를 받으면, 제안 번호가 현재까지 수락된 제안 번호보다 크거나 같은 경우에만 해당 제안을 수락합니다.
5. 하나의 제안이 다수의 Acceptor로부터 수락될 경우, 해당 제안의 값을 리더로 선출합니다.

합의과정 비슷하지만, 리더 선택은 합의 결과로 로그를 남기지 않습니다. 리더를 가장 높은 번호를 가진 리더로 선택하기 때문이죠. 여기서! Paxos 는 다중리더 아니였나? 라고 생각하실 수 있습니다. 하지만 다중 리더를 가질 수 있는 Paxos 알고리즘에서도 다음과 같은 이유로 리더 선출 과정은 필요합니다:

1. 일관성 보장: Paxos 알고리즘은 분산 시스템에서 일관성을 유지하기 위해 합의를 도출하는 과정을 거칩니다. 여러 개의 리더가 동시에 작업을 수행할 수 있지만, 이들은 각자의 작업을 수행하고 일관성을 유지하기 위해 합의 과정을 거쳐야 합니다. 리더 선출 과정을 통해 각 리더는 자신의 작업을 다른 리더와 합의하여 일관성을 유지할 수 있습니다.
2. 병렬 처리: 다중 리더를 가질 수 있는 Paxos 알고리즘은 병렬 처리를 통해 성능을 향상시킬 수 있습니다. 여러 개의 리더가 동시에 작업을 수행하므로, 작업들은 병렬로 처리될 수 있습니다. 리더 선출 과정을 통해 각 리더는 자신의 작업을 독립적으로 수행하고, 필요한 경우에는 합의를 통해 일관성을 유지합니다.
3. 장애 대응: 리더가 장애로 인해 동작하지 않는 경우, 다른 리더들은 이를 감지하고 새로운 리더를 선출해야 합니다. 리더 선출 과정을 통해 분산 시스템은 리더의 장애에 대응할 수 있으며, 일관성과 내결함성을 유지할 수 있습니다.

 

아 그러면 리더를 확인해서 그 리더를 계속해서 쓰면 되는구나~! 💡

 

문득 이런 생각이 들 수도 있습니다. 하지만 반은 맞고 반은 틀렸습니다. Paxos 를 쓰는 클라이언트는 리더들이 어떤게 있는지 알 수 있고, 현재 리더라고 생각하는 노드에 제안합니다.  하지만 다음과 같은 상황에서는 다른 리더를 고려해서 병렬처리를 할 수 있도록 해야겠죠. 

 

 

 

 

 

👨‍👨‍👧‍👧 Paxos 에서의 리더 교체 상황

Paxos 알고리즘에서는 리더 교체 상황에 대해 다음과 같은 가정을 할 수 있습니다:

1. 리더의 장애: 리더가 장애로 인해 동작하지 않는 경우, 다른 노드들은 이를 감지하고 새로운 리더를 선출해야 합니다. 이를 위해 일반적으로 타임아웃(TImeout) 메커니즘을 사용합니다. 타임아웃이 발생하면, 다른 노드들은 리더 선출 과정을 시작하여 새로운 리더를 선출합니다.
2. 악의적인 동작: 악의적인 노드가 리더로서 부적절한 동작을 하거나 다른 노드를 방해하는 경우, 보안 메커니즘을 사용하여 이를 탐지하고 대응할 수 있습니다. 예를 들어, 악의적인 동작을 감지한 노드들은 다른 노드들과 협력하여 악의적인 리더를 제거하고 새로운 리더를 선출할 수 있습니다.

악의적인 동작은 판별하기 어렵다고 해도, 리더의 장애는 분명합니다. 요청에 대해서 실패하거나, Timeout 으로 인해 동작하지 않는다고 판단하는 경우, 다른 리더를 선출하여 진행해야겠죠. 그렇다면 하나의 리더가 동시에 여러 제안을 처리할 수 있을까요?

 

 

 

 

 

 

⛑️ 작업중인 리더의 제약사항

Paxos 알고리즘에서는 현재 작업 중인 리더에게는 새로운 제안을 할 수 없는 구조입니다. Paxos 알고리즘은 한 번에 하나의 리더만을 허용하며, 해당 리더는 합의 과정을 주도합니다. 이는 Paxos 알고리즘의 안정성과 일관성을 보장하는 중요한 특징입니다.

 

새로운 제안이 발생할 경우, 해당 제안은 현재 리더에 의해 수락되어야 합니다. 다른 노드들은 리더로부터의 제안을 수락하기 위해 응답을 보내야 합니다. 현재 작업 중인 리더가 다른 제안에 바쁜 경우, 새로운 제안은 대기해야 합니다. 이는 Paxos 알고리즘에서 리더의 안정성과 합의 과정의 일관성을 유지하기 위한 방법입니다.

 

따라서, 작업 중인 리더에게는 동시에 여러 개의 제안을 할 수 없습니다. 다른 제안이 발생하면 해당 제안은 대기하고, 리더가 비어있을 때에만 새로운 제안을 수행할 수 있습니다. 이를 통해 Paxos 알고리즘은 안정성과 일관성을 유지하면서 분산 시스템에서 합의를 도출할 수 있습니다.

 

하나의 예로 다음과 같이 수락(Accepted) 이 실패한 경우 각기 다른 Proposer 에서 다시 요청하는 것을 볼 수 있습니다. 

  Proposer           Acceptor        Learner
 |  |  |  |       |  |  |  |  |       |  |
 X--------------->|->|->|->|->|       |  |  Prepare(1)
 |<---------------X--X--X--X--X       |  |  Promise(1,{null,null,null,null,null})
 x--------------->|  |  |  |  |       |  |  Accept!(1,V1)
 |  |  |  |       X------------------>|->|  Accepted(1,V1)
 !  |  |  |       |  |  |  |  |       |  |  !! FAIL !!
    |  |  |       |  |  |  |  |       |  |
    X--------------->|->|->|->|       |  |  Prepare(2)
    |<---------------X--X--X--X       |  |  Promise(2,{null,null,null,null})
    X--------------->|  |  |  |       |  |  Accept!(2,V2)
    |  |  |       |  X--------------->|->|  Accepted(2,V2)
    !  |  |       |  |  |  |  |       |  |  !! FAIL !!
       |  |       |  |  |  |  |       |  | 
       X--------->|---->|->|->|       |  |  Prepare(3)
       |<---------X-----X--X--X       |  |  Promise(3,{V1,null,null,null})
       X--------------->|->|  |       |  |  Accept!(3,V1)
       |  |       |  |  X--X--------->|->|  Accepted(3,V1)
       !  |       |  |  |  |  |       |  |  !! FAIL !!
          |       |  |  |  |  |       |  |
          X------>|->|------->|       |  |  Prepare(4)
          |<------X--X--|--|--X       |  |  Promise(4,{V1(1),V2(2),null})
          X------>|->|->|->|->|       |  |  Accept!(4,V2)
          |       X--X--X--X--X------>|->|  Accepted(4,V2)

 

<참고: https://en.wikipedia.org/wiki/Paxos_(computer_science)>

 

 

 

 

 

 

 

 

 

지금까지 Paxos 의 개념과 Paxos 에서의 리더 선출 및 제안 방법에 대해서 기술하였는데요. 👏👏

잘못된 자료가 있다면 언제든지 소통 부탁드립니다. 🙇

 

다음글에서는 제안 충돌 상황과 로그 관리에 대해서 알아봅시다~!  🙌

 

 

 

 

 

---

 

참고 : https://en.wikipedia.org/wiki/Paxos_(computer_science)