분산 데이터베이스 탐구: 합의 알고리즘 (Paxos, Raft, PBFT, PoW)

분산 데이터베이스 탐구:  합의 알고리즘

이전 글에서 분산 시스템에서 데이터 일관성 문제와 관련된 문제를 어떻게 해결하는 로컬 트랜잭션과 분산 트랜잭션, 충돌 회피 또는 충돌 감지 및 해결 다양한 전략을 공부해보았다. 이번 글은 그 연장선으로 합의 알고리즘에 대해서 다루려고 한다. 

 

단일 노드와 분산 노드의 트랜잭션

단일 데이터베이스의 트랜잭션

단일 데이터베이스에서는 트랜잭션은 흔히 데이터베이스 엔진에서 구현되며, 이를 ACID 트랜잭션이라고 부른다. ACID 속성은 데이터베이스 시스템의 신뢰성과 무결성을 위한 기본 요소이다. 이는 원자성(A)뿐만아니라 WAL 로그를 통해 쓰기 지속성(D) 그리고 사용자 관점에서의 데이터 일관성(C)과 동시성 제어 메커니즘으로 고립성(I)을 구현한다. 이 속성은 트랜잭션이 안정적으로 처리되도록 보장하며, 동시에 액세스하는 복잡한 다중 사용자 환경에서도 데이터베이스를 일관되고 안정적이며 예측 가능한 상태로 유지한다. 대표적으로 MySQL, PostgreSQL와 같은 상용적인 관계형 DB에 정의되어 있다.

 

분산 데이터베이스의 트랜잭션

이전 글(분산 데이터베이스 탐구: 데이터 복제와 일관성)에서 다뤘던 분산된 노드가 하나의 트랜잭션에 관여하는 경우에는 분산 트랜잭션을 사용한다. 대표적으로는 원자적 커밋을 달성하는 2PC(2-phase commit)가 있다. 이러한 과정은 코디네이터(트랜잭션 매니저)를 통해 분산된 노드가 마치 하나처럼 커밋 혹은 롤백을 하여 원자성을 지닌 최종적 일관성(C)을 보장한다. 

• 분산 트랜잭션 특히 2PC는 다른 방법으로 달성하기 어려운 중요한 안전성을 보장해준다. 하지만 성능 비용이 상당하다.^[각주:1]
• 다양한 시스템 간의 일관성 보장이 필요한 이종 분산 트랜잭션은 더 까다롭다. 

 

2-Phase Commit

 

일관성과 합의: 분산 트랜잭션과 합의 알고리즘의 차이점

'일관성과 합의'는 데이터 중심 애플리케이션 설계의 한 챕터의 제목이다. 여러 노드간에 상태를 일관되게 유지하려면, 그러한 시스템의 모든 부분이 합의에 도달해야 한다. 여기서 개인적으로 궁금했던 부분은 '왜 2PC와 같은 분산 트랜잭션은 합의라고 불리지 않을까?'였다. 생각해보니 이유는 간단했다. 이는 분산 트랜잭션의 코디네이터와 합의 알고리즘의 역할을 생각해보면 된다.

• 공통점: 모든 노드가 통신을 이뤄 최종적으로 하나의 값으로 수렴하는 과정은 분산 트랜잭션과 통상적인 합의 알고리즘(합의를 이루고 나중에 적용되는 것도 있음) 일치한다. 
• 2PC: 하지만 중개자없이 다수결 투표로 이뤄지는 합의 알고리즘과는 다르게 분산 트랜잭션은 중개자가 존재하는 코디네이터에서 단일 장애 지점(SpoF)이 발생하면 시스템 자체가 블로킹될 수 있다는 치명적인 단점을 지녔다. 
• 합의 알고리즘: 합의 알고리즘은 일부 노드 장애가 발생하여도 모든 노드가 동일한 상태나 값을 도달하도록 합의를 통해 보장한다. 이를Liveness라고 한다. 생동감있는 마이크로 서비스를 운영할 때는 노드 장애 현상은 당연하게 여겨지기 때문에 이러한 속성은 매우 중요하게 다뤄진다.^[각주:2]

 

정리해보면, 둘 다 최종 일관성을 목표로 하는 건 일치한다. 그러나 2PC는 하나의 값으로 수렴하는 Safety를 중점으로 하고 중앙 코디네이터를 통한 트랜잭션 관리를 맡긴 반면, 합의 알고리즘은 하나의 값으로 수렴하는 Safety와 분산된 환경에서 결함이 발생하여도 정상적 동작을 보장하는 Liveness의 균형을 맞추기 위해 노력한다. 따라서 합의 알고리즘은 2PC의 Safety + 분산 환경에 중요한 Liveness 속성을 자체적으로 일부 지닌 더 복잡한 프로세스라고 보면 된다.

 

분산 트랜잭션을 사용하면 명확한 일관성을 보장하고 구현이 간단하다는 장점이 있지만 중앙 코디네이터의 SPoF의 문제와 중앙 의존적이라는 점에서 확장성에 제약도 존재한다. 합의 알고리즘은 구현과 이해가 다소 어렵지만 분산 환경에서 중요한 고가용성과 내결함성을 지니게 되며, 운영 관리나 시스템 확장성에서도 이점을 가져간다. 이러한 장단점 트레이드-오프를 고려하여 분산 트랜잭션에서 합의 알고리즘 시스템으로 변경한 실제 사례로는 Kafka가 있다. 오픈 소스 메세지 브로커 프로젝트 Kafka는 중앙 코디네이터가 관리하는 Zookeeper를 사용하여 리더 선출, 브로커 및 토픽 관리를 해왔다가 Raft 합의 프로토콜을 사용하는 KRaft모드로 전환하였다. 이러한 변화는 위에서 말한 합의 알고리즘의 장점을 취한다고 한다.^[각주:3] 

 

Safety와 Liveness

위에서  Safety와 Liveness를 말해서 언뜻 이해했겠지만 다시 설명하자면, Safety와 Liveness의 특성은 분산 컴퓨팅에서 쓰이는 합의 알고리즘이 네트워크에서 통용되기 위해서 가져야하는 필수적인 요소들이다.^[각주:4]

• Safety: Safety란 나쁜 일이 발생해서는 안되는 속성을 뜻한다. 합의된 결과는 모두에게 일관되게 보여져야 하고 변하지 않는다. 블록체인의 finality와 동일한 개념으로 봐도 된다.
• Liveness: Liveness란 좋은 일이 발생해야만 하는 속성을 뜻한다. 블록체인 비동기 네트워크 내에서 반드시 합의가 이루어져야 한다.

 

FLP Impossibility

그렇다면 Safety와 Liveness를 모두 충족하는 합의 알고리즘은 존재할 수 있을까? 1985년 'Impossibility of Distributed Consensus with One Faulty Process’ 논문^[각주:5]에서 FLP Impossibility 결과를 도출해낸다. FLP는 논문 저자들의 앞글자를 따온 약자이다. 논문 내용을 일부 정리하면 다음과 같다.

• 증명은 귀류법을 통해 이뤄진다. 한 가지 결함이 있는 노드가 있는 경우에 Safety와 Liveness를 모두 만족하는 완전한 합의를 이룰 수 있다고 가정한 다음에 이에 대한 모순을 도출해낸다.
• 수신한 메시지에 따라 영구적으로 state를 전환하는 state machine이 있을 때, 메시지 수신 지연이 네트워크 지연에 의한 것인지 장애에 의한 것인지 알 수 없다. 그래서 계속 state를 변경하여 합의에 도달하지 못하는 상황이 발생하여 무한 실행이 이뤄진다. (그래서 MSA에서는 서킷 브레이커 패턴이 존재한다) 
• 그러므로, '한 가지 결함이 있는 노드가 있는 경우에 Safety와 Liveness를 모두 만족하는 완전한 합의를 이룰 수 있다'는 가정은 모순이 된다.
• 따라서, 비동기 네트워크에서는 Safety와 Liveness를 모두 만족하는 합의 알고리즘을 설계하는 것이 불가능함을 알 수 있다.

 

이러한 증명은 비동기 네트워크로 구성된 블록체인과 같은 분산 시스템 구조에서 합의 알고리즘을 설계하려면 Safety와 Liveness를 양측에 두고 줄다리기를 해야 함을 뜻한다. 

 

장애 멈춤(Fail-Stop)과 비잔틴(Byzantine) 합의 알고리즘

합의는 이러한 분산 시스템이 마치 하나처럼(원자성) 동작하면서 대규모 트래픽을 결함없이 다루고자 하는 것을 목표로 한다. 즉 내결함성에 더 초점을 맞춘 일관성 모델이 바로 '합의'이다. 모든 것이 불확실한 시스템에서 구체적인 안전성(Safety)을 가져오고 내결함성까지 유지해주기 때문이다. 물론 공짜는 아니다. 2PC와 비슷하게 내결함성과 일관성을 보장하는 대신 일부 성능과 트레이드 오프한다. (2PC는 원자성과 일관성을 보장하는 대신 성능 반납) 그래서 마찬가지로 모든 곳에서 사용되지는 않는다. 합의 과정에서 제안이 결정되기 전 노드가 제안에 투표하는 과정은 일종의 동기식 복제다. 이전 글(분산 데이터베이스 탐구: 데이터 복제와 일관성)에서 다뤘듯이 동기식 복제는 성능 비용을 수반한다.

고가용성과 내결함성 (공부하면서 헷갈렸던 내용을 정리하면 다음과 같다.)
- 고가용성(High Availability, HA): 시스템 가동 시간을 최대화하고 다운타임을 최소하하는 것. 
- 내결함성(Fault Tolerance, FT): 시스템 내부 결함이 발생하더라도 정상적인 동작을 보장하는 것. 

고가용성은 시스템 연속적인 가동을 유지하는 데 중점을 두고 내결함성은 장애가 발생하더라도 올바르게 작동하는 데 중점을 둔다.

 

합의 알고리즘으로 얼마나 내결함성을 보장할 수 있을지에 대해서도 구분지어볼 수 있다. 

• 장애 멈춤(Fail-stop) 합의 알고리즘: 운영중인 시스템 노드가 오류가 발생하면 그냥 중단된다. 해당 알고리즘은 잘못된 응답을 하는 노드보다 응답하지 않는 노드에 대응하는 것을 목표로 한다. 대표적으로 Paxos, Raft가 있다.
• 비잔틴(Byzantine) 합의 알고리즘: 노드들이 고장나서 멈추는 것을 넘어서서 악의적인 행동을 할 수 있다고 가정한다. 해당 알고리즘으로 이러한 악의적인 노드들이 존재함에도 불구하고 시스템 정상 작동을 보장한다. 대표적으로 PBFT, PoW, PoS가 있다.

 

Fail-stop 합의 알고리즘 1: Paxos

Paxos는 1989년에 Leslie Lamport가 쓴 'The Part-Time Parliament'^[각주:6] 논문에서 공개된 알고리즘이다. Paxos는 분산 시스템 내에서 여러 노드 간에 하나의 값을 합의하기 위해 고안된 알고리즘으로 여러 장애 상황(네트워크 지연, 노드 실패)에서도 일관된게 합의를 이뤄나가도록 설계되었다.

• Safety: Paxos는 장애가 발생하는 경우에도 일관된 단일 값이 선택되도록 보장한다. 이는 다수의 노드가 값에 동의해야 하는 일련의 제안을 통해 달성된다. 값이 선택되면(정족수에 의해 합의) Paxos는 다른 값을 선택할 수 없도록 보장하여 Safety을 보장한다.
• Liveness: Paxos는 특정 조건, 주로 대다수의 노드가 작동하고 서로 통신할 수 있는 상태에서 Liveness를 보장한다. 그러나 노드가 지속적으로 실패하거나 메시지가 손실되면 Paxos는 결정을 내리지 못한 채 정지될 수 있다. 따라서 Liveness는 네트워크의 안정성에 따라 달라진다.

 

Paxos 동작방식

해당 알고리즘에는 3가지 역할 모델이 존재한다. 

• Proposer: 합의 값을 제안한다
• Acceptor: 제안된 값을 승인하거나 거절한다. 과반수 투표를 진행하기 때문에 합의 시작 전에 전체 Acceptor 중 과반 수 이상이 Active 상태여야 한다
• Learner: 합의된 값을 학습하고 시스템 다른 부분에 적용한다

 

Paxos는 다음 과정을 통해 합의를 이뤄낸다.

 

1) Prepare 단계

Proposer는 유니크한 번호와 함께 prepare 메시지를 Acceptor들에게 보낸다 

1. 장애 시나리오: Proposer가 장애가 발생하여 prepare 메시지를 보내지 못한 경우
2. 대응: 다른 Proposer가 새로운 prepare 메시지와 더 높은 번호를 사용하여 Acceptor들에게 메시지를 보낼 수 있다. 그런데 네트워크 지연 등 어떠한 이유로 Proposer가 여럿이 되는 경우에는 먼저 합의에 도달한 Proposer 제안이 승낙된다. (이미 제안된 번호보다 높으면 거절, 이미 합의된 값을 높은 번호로 learner에게 알리면 거절)

2) Promise 단계

Acceptor는 이전에 승인된 제안보다 높은 번호의 prepare 메시지를 받으면 promise 메시지로 응답한다

1. 장애 시나리오: Acceptor 중 일부가 응답하지 않는 경우
2. 대응: Proposer는 Acceptor의 과반수로부터 promise 메시지를 받으면 다음 단계로 진행한다. 모든 Acceptor의 응답은 필요하지 않다.

3) Accept 단계

Proposer는 다수의 Acceptor로부터 promise 메시지를 받으면, 그 값과 함께 accept 메시지를 Acceptor들에게 보낸다

1. 장애 시나리오: 일부 Acceptor가 accept 메시지를 받지 못하는 경우
2. 대응: Proposer는 Acceptor의 과반수만 accept 메시지를 승인하면 합의가 성공적으로 이루어졌다고 판단한다

4) Accepted 단계

Acceptor는 accept 메시지를 받으면 해당 값을 합의 값으로 승인하고 Learner에게 이를 알린다.

1. 장애 시나리오: Learner 중 일부가 합의 값을 받지 못하는 경우
2. 대응: 다른 Acceptor 또는 Learner로부터 합의 값을 다시 학습할 수 있다

 

이러한 합의 과정을 통해 Paxos는 최종적으로 정확히 한 가지 값만 합의되도록 보장한다. 그리고 각 단계에서 시스템 노드 일부가 장애가 나더라도 합의 과정은 계속해서 진행된다. 다만 당시에는 Paxos는 이해와 구현이 어렵고 잦은 메시지 교환으로 오버헤드가 많다고 받아들여졌다.

 

Fail-stop 합의 알고리즘 2: Raft

2014년 USENIX에서 “In Search of an Understandable Consensus Algorithm”라는 논문^[각주:7]이 발표되고 Raft라는 알고리즘이 등장한다. Raft는 논문 제목 그대로 “이해 가능한” 합의 알고리즘을 만드는 데 초점을 두고, 이름에서 알 수 있듯이 "안정적인 보트"라는 개념에서 시작하여 분산 시스템의 복잡한 바다에서 안정성을 목표로 하고 복제 상태 머신(SMR, State Machine Replication) 구현을 목적으로 한다. 

복제 상태 머신(SMR, State Machine Replication)이란?

상태 머신(State Machine)은 말 그대로 상태를 가지는 기계로, 흔히 우리가 사용하는 앱(프로그램)이나 Java 바이트코드를 실행하는 JVM을 생각하면 된다. 복제 상태 머신을 구현하게 되면 이러한 상태 머신을 여러 개 복제해놓고 하나의 노드가 장애가 발생하여도 전체 시스템은 문제 없이 동작가능하게 한다. 대표적으로 Kafka에서 사용하는 KRaft(또는 Zookeeper), K8s의 etcd가 있다. 또한 블록체인에서 흔히 접하는 개념이다. 

• Safety: Raft는 리더 개념을 통해 Safety를 보장한다. 한 노드가 임기 동안 리더로 선출되며, 해당 임기 동안에는 모든 변경사항은 리더를 통해서 결정이 이루어진다.  
• Liveness: 리더 노드가 어떠한 이유에서든 지속적으로 실패하면(hartbeats로 체크) 다시 투표를 통해 리더를 선출한다. 이러한 시스템을 통해 Liveness를 보장한다. 이 또한 Paxos와 유사하게 네트워크 안전성과 리더 재선출 빈도에 따라 Liveness가 결정된다.

 

Raft 동작방식

Raft 알고리즘에는 리더라는 역할을 도입하였다.

• Leader: 리더는 값을 결정하여 로그에 저장하고 이를 Follower들에게 알린다
• Follower: 리더의 요청을 수신하여 처리한다
• Candidate: 새로운 리더가 되기위해 Follower에서 변경된 노드이다

 

In Search of an Understandable Consensus Algorithm 논문 Figure 4

 

Raft는 오직 2단계 과정을 통해 합의를 이뤄낸다.

 

1) Leader Election 단계

모든 합의 결정이 해당 리더에 의해 이루어진다. 리더가 실패하거나 네트워크 파티션이 발생하면 새로운 리더가 선출된다.

1. 장애 시나리오: 현재 리더가 다운되거나 네트워크 문제로 인해 접근할 수 없게 될 경우
2. 대응: 모든 서버는 정해진 "election timeout"을 가지고 있다. 이 타임아웃 시간 동안 리더로부터 어떠한 메시지도 받지 못하면, 서버는 리더가 다운되었거나 네트워크 문제가 발생했을 것이라 판단한다. 그리고 새로운 리더를 선출한다.
3. 새로운 리더 선출 과정: 초기 상태와 같다. 모두가 팔로워이고 "election timeout"동안 리더로부터 메시지를 받지 못하면 참가자로 변하면서 자신에게 투표해달라고 요청한다. 클러스터의 과반수로부터 투표를 받으면 리더 상태로 전환된다. 
4. heartbeats: 리더가 선출되면 리더는 주기적으로 heartbeat 메시지를 팔로워들에게 전송하여 자신이 건재함을 알린다. 

2) Log Replication 단계

리더가 결정한 연산은 로그 항목으로 만들어지며, 이 항목은 다른 모든 서버에 복제된다. 일단 과반수의 서버에서 로그 항목이 복제된다. 일단 과반수의 서버에서 로그 항목이 복제되면, 그 연산은 커밋되고 State Machine에 적용된다

1. 장애 시나리오: 리더가 로그 항목을 복제하려 할 때, 일부 서버들이 다운되거나 응답하지 않는 경우
2. 대응: 리더는 로그 항목을 모든 팔로워 서버에게 전송한다. 팔로워 서버는 로그 항목을 수신하면 이를 저장하고 리더에게 응답한다. 리더는 과반수의 팔로워 서버로부터 응답을 받으면 해당 로그 항목이 성공적으로 복제되었다고 판단한다. 만약, 리더가 일부 팔로워 서버로부터 응답을 받지 못한다면, 해당 서버에 대해 로그 항목을 다시 전송하거나 재시도한다.

 

Raft는 Safety을 위해 다음과 같은 규칙을 도입했다.

1. Election Restriction: 리더는 모든 커밋된 로그를 저장해야 한다. 새롭게 선출된 리더가 모든 커밋된 로그를 가지고 있지 않으면 팔로워들이 전송해줘야 하는 번거로움이 생기기 때문이다. 참가자(Candidate)들이 리더가 되기 위해서는 다수의 노드들에게 투표해달라고 통신을 보낸다. 즉 다수의 노드들이 동일한 커밋된 로그를 지니고 있어야 한다.
2. Commit Rules: 이전 임기 메시지가 과반수 이상 복제되었다고 커밋으로 간주하지 않는다. 반드시 현재 임기의 메시지가 복제되어야지만 커밋으로 간주한다.
   1. 아래 그림을 보면 (a), (b)에서 같은 임기(2)를 가진 리더가 서로 값을 결정하고 다른 노드들에게 복제한다.
   2. (c)에서 S1은 S3에게 값을 복제한다.
   3. (d)가 이틈을 타서 (S2~S4) 노드들에게 투표를 받아 다시 리더가 되고 빠르게 자신의 값을 복제시킨다
   4. 그러나 (c)에서 S1이 4의 값까지 무사히 전파를 성공한다면 S5가 제안한 값은 받아들여질 수 없다.

 

Commit Rules(S5가 뒤늦게 2번 임기 리더를 하여 값을 복제하지만 이미 S1이 3번 임기를 진행하고 있어 반영되지 않는 상황)

 

 

Fail-Stop 합의 알고리즘으로 분류되는 Paxos, Raft의 Safety와 Liveness에 대해 정리해보면 다음과 같다. 

 

	Paxos	Raft
개념	분산 시스템의 여러 노드 간의 값에 동의한다	보다 이해하기 쉽고 안정적인 방식으로 SMR을 복제한다
Safety	장애가 발생한 경우에도 일관된 값을 보여지도록 Safety를 보장한다.	리더 개념을 통해 Safety를 보장한다. 모든 값의 변화는 리더를 통해 이뤄진다.
Liveness	대다수의 노드가 작동하고 통신할 수 있는 조건에서 Liveness가 보장된다.	Paxos와 마찬가지로 통신할 수 있는 조건에 더하여 리더 실패 시 리더 재선출을 통해 Liveness가 보장된다. (Heartbeats로 체크)

 

 

지금까지 Fail-Stop 합의 알고리즘에 대해 알아보았다. 둘 다 어떠한 상황에서도 Safety를 보장하는 방식으로 설계되었다. 하지만 노드 장애 상황만 가정하지 만약 악의적인 노드가 침투하였을 때에 대한 가정은 이뤄지지 않는다. BFT 합의 알고리즘은 이러한 신뢰할 수 없는 커뮤니케이션 문제를 직접적으로 해결하기 위해 고안되었다. 두 장군 문제 이야기부터 시작해보자.

 

두 장군 문제

'두 장군 문제'는 컴퓨터 과학과 분산 시스템의 고전적인 문제로 여겨진다. 신뢰할 수 없는 커뮤니케이션 채널을 통해 합의를 도출하는 데 따르는 어려움을 다루는 사고 실험이다. 같은 팀 A1, A2이 B를 포위해서 공격하려고 한다. 그러기 위해서는 공격할 시간과 구체적인 전략을 합의해야 하는데 스파이(악의적 행동)이나 적에게 포로(장애)가 될 가능성이 있어 이를 해결해야 한다. 과학자들은 이 문제는 절대 풀 수 없음을 증명했다. 통신이 손실될 수 있고 수신 확인이 보장되지 않는 환경에서는 두 당사자가 합의에 도달했다고 절대적으로 확신하는 것이 불가능하다는 것이다. 이러한 모습만 봐도 분산 시스템에서 합의를 도출하는 것은 얼마나 어려운지를 알아 볼 수 있다.

1. 기본 가정: A2에게 첫 번째 메시지가 도달하지 않을 수 있다고 가정한다. 이 경우 A2 장군은 A1 장군이 공격을 준비하고 있다는 사실을 알 수 없다.
2. 응답: A2가 첫 번째 메시지를 받은 후, A2가 다시 A1에게 응답을 보낼 수 있다. 그러나 이는 다시 A1에게 도달했는지 보장하기 어렵다. 
3. 응답의 응답: 만약 A1이 가까스로 A2의 답장을 받았다면, 그 사실을 확인하는 메시지를 A2에게 다시 보낼 수 있다. 그러나 또 다시 이 부분도 확신할 수 없다.

실제로 현재 web2 인터넷 상에서는 이러한 신뢰성있는 프로토콜을 위해 TCP 3handshake를 사용하고 있다. 이는 속도 등 여러 문제가 있어 http3 부터는 UDP 비신뢰성기반 프로토콜에서 커스텀하여 사용하는 추세로 변하고 있다.^[각주:8]

 

두 장군 문제

 

비잔틴 장군 문제

두 장군 문제를 일반화한 것이 비잔틴 장군 문제이다. 시스템 내의 일부 노드가 고의로 악의적인 행동을 하거나 결함을 가지는 환경에서 어떻게 모든 올바른 노드들이 합의에 도달할 수 있는지에 대한 문제이다. 비잔틴 제국의 군대에 비유해서 비잔틴 장군 문제라고 불리어지는 데 큰 뜻은 없는 것 같다. 문제는 다음과 같다. 

• 합의 도달: 모든 정직한 장군들은 동일한 계획에 동의해야 한다
• 배신자의 존재: 시스템에는 잘못된 또는 오해를 불러일으키는 정보를 전달할 수 있는 배신자가 있을 수 있다
• 배신자 식별: 정직한 장군들은 배신자를 명확하게 식별할 수 없다

 

이러한 비잔틴 장군 문제를 해결하는 것은 분산 시스템에서 중요하다. 대표적으로 비잔틴 장애 허용(Byzantine fault tolerance)이라는 합의 알고리즘을 실용적으로 개선한 PBFT(Pratical Byzantine Fault Tolerance) 알고리즘이 존재한다. 이러한 BFT 알고리즘들은 Fail-Stop에 해당하는 Paxos, Raft와는 다르게 신뢰할 수 없는 노드나 악의적인 행동이 발생하여도 안정적인 합의를 달성할 수 있도록 설계되었다. 

 

Byzantine 합의 알고리즘: PBFT

1999년도에 제안된 PBFT 알고리즘^{[각주:9][각주:10]}은 비잔틴 장군 문제를 해결하여 BFT 알고리즘으로 실용적으로 고안해내었다. 비동기 네트워크간의 불확실한 커뮤니케이션 문제를 어느정도 해소하였고, 결정론적인 Saftey를 확보했다는 점에서 현재 많은 분산 시스템의 합의 방식으로 사용되고 있다. 본 논문에서는 뷰 변경 프로토콜, 3단계 프로토콜, 다수결 합의 시스템 등을 통해 어떻게 문제를 풀어나갔는지 설명한다. (비트코인이 사용하는 PoW 합의 알고리즘이 갖고있는 확률적인 Safety의 문제도 갖고 있지 않아서 이를 많이 사용하는 추세이다.)

• Safety: 결함이 있거나 악의적인 노드가 있는 경우에도 해당 노드를 제외하고는 모든 노드가 동일한 상태에 도달한다는 Safety를 보장한다. 
• Liveness: 결함이 있는 노드가 있음에도 불구하고 결함이 없는 노드가 수신한 모든 요청(트랜잭션)이 실행되고 응답되는 Liveness를 보장한다. Liveness를 일부 희생한다는 말은 비동기 네트워크의 상황을 이야기한다. 지연이 어느정도 발생하면 Liveness를 완전하게 보장할 수는 없다.

 

PBFT 동작 방식

PBFT는 시퀀스 번호(N)와 뷰 번호(V)를 사용하여 요청을 처리하고, 합의를 위해 3단계 과정을 거치는 작업을 수행한다. 시스템은 각 라운드(또는 뷰)에서 리더를 선출하고, 리더는 요청을 처리하고 다른 노드와 정보를 교환한다.

• View에서 하나의 복제본은 Primary이고 나머지는 Backup이라고 부른다.
• View는 연속해서 번호가 매겨진다 (Rounding)
• 각 View마다 Primary 선정은 p = v mod R로 한다. (v는 View 번호)
• 만약 선정된 노드가 장애가 난다면, View 변경 프로토콜로 인해서 View가 변경된다.

 

View 변경 프로토콜은 비동기 네트웨크 상황에서 Primary 장애가 발생할 경우를 대비하여 동작한다. 해당 기능은 View가 변경됨에도 작업 순서나 커밋 충돌이 없도록 방지해주며, Primary 장애에도 계속 시스템이 동작할 수 있도록 해주기 때문에 Safety와 Liveness를 보장하기 위한 중요한 프로토콜이다.

 

View에서 Primary가 선정되었으면 이제는 3단계 프로토콜을 진행해야 한다. 이는 비잔틴 노드의 개수가 최대 f개일 때, 전체 네트워크 노드 수가 3f+1개라는 전제로 진행된다. 왜 3f+1개 일까? 합의는 과반수 투표에 의해서 이뤄져야하기 때문이다.

• 여기서 f개의 결함이 있다고 가정해보자. (항상 최악의 수를 가정해야 한다)
• 합의에 도달하기 위해서는 과반수 동의가 필요하다. 과반수 동의를 위해서 x개가 필요하다고 하자.
• 그런데, x개에서 과반수 동의를 이뤄야 하는 상황에서도 f개의 결함이 존재할 수 있다. 과반수를 동의를 이루기 위해서는 f개보다 많은 표를 얻어야 하므로, 최소 f+1개가 존재해야 한다. 
• 따라서, 과반수 동의를 위해서 필요한 노드의 수 x는 2f+1개이다. 그래서 safety와 liveness를 위해서 총 3f+1개의 노드가 필요하다.

 

가정만으로는 와닿지 않을 수 있다. 3f+1개로 어떻게 악의적인 공격에도 올바른 합의에 도달할 수 있는지는 각 단계 프로토콜을 거치면서 더 자세히 이해해보자.

 

PBFT 3단계 프로토콜

 

Client Request

Client가 Primary 노드에게 요청을 보내면서 PBFT는 시작한다.

 

1) Pre-prepare 단계

Primary 선정은 View 번호에서 mod 함수를 적용하여 뽑힌 노드 번호에 해당하는 노드로 선정한다. 그렇게 선정되어 Client Request을 받은 Primary 노드는 자신을 제외한 나머지 Backup 노드들(3f)에게 Pre-Prepare 메시지를 멀티캐스팅한다. 

 

2) Prepare 단계

Pre-Prepare 메시지를 전달받은 Backup 노드들이 일을 처리할 시간이다. 각 노드들은 자신이 받은 Pre-Prepare메시지를 검증한다. 만약 해당 메시지를 수락한다면 다른 노드들에게 Prepare 메시지를 전송한다. 수락하지 않는다면 아무 동작도 하지 않는다. 

 

그렇게 각 노드들은 자신이 가지고 있는 Pre-Prepare 메시지 정보를 토대로 다른 노드에게서 온 Prepare 메시지를 검증한다. 그렇게 검증된 메시지가 2f개가 충족되면 'prepared certificate'로 Commit 진입 준비 완료 단계가 된다.

• Primary 노드를 제외한 3f개 노드들만 Prepare 메시지를 전송하므로 과반수 동의를 얻기 위해서는 최소 2f개 메시지가 필요하다.

 

3) Commit 단계

'prepare certificated'가 된 노드들은 Commit 메시지를 다른 노드들에게 멀티캐스팅한다. 이렇게 Commit 단계가 시작된다. 각 노드들이 다른 노드들로부터 2f+1개의 메시지를 받으면 'committed certficate' 상태가 된다. 

• 최악의 경우, Prepare에서 받은 2f개 중 f개는 결함이라고 가정해보자. 그럼 이제 Primary를 포함한 노드 집합에서 과반수 동의를 구하려면 최소 f+1개의 동의가 필요하다. 따라서, 2f+1개의 메세지를 받아야 한다.
• Primary도 악의적인 노드라면? 이는 f개에 포함되므로 여전히 남은 f+1개 정상 노드로 인해서 올바른 합의에 도달할 수 있다.

 

'committed certificate' 상태가 된 노드는 상태 변화 함수를 시행한다. 요청을 수용하여 합의를 본 것이다. 최종적으로 합의를 이루지 못한 노드들(최악의 경우 2f개)은 Livness를 일부 희생한 결과라고 보면 된다.

 

Client Reply

commit 단계까지 종료한 노드들은 클라이언트에게 응답 메시지를 보낸다. 클라이언트는 f+1개의 메시지만 받으면 결과를 수락한다. 만약 f+1개의 메세지를 받지 못하면 요청을 재전송한다. 

• Commit 단계에서 가정한 최악의 경우 f+1개가 다수의 합의를 본 노드이기 때문이다. f개만 받으면 악의적인 노드들로부터 온 메시지인지 아닌지 판별이 어렵다. f+1개를 오면 f개가 악의적인 노드 결과라고 해도 나머지 1개의 메시지로 올바른 합의인지 판별할 수 있다.

 

PBFT의 Safety와 Liveness에 대해 정리해보면 다음과 같다. 

 

	PBFT(Proof of Work)
개념	분산된 환경에서 비잔틴 장애 상황에서도 올바른 합의에 도달한다.
Safety	3단계 프로토콜(Pre-Prepare, Prepare, Commit)과 2/3 다수결 합의 시스템을 통해 최악의 비잔틴 상황에서도 올바른 합의에 도달할 수 있는 Safety를 보장한다.
Liveness	뷰 변경 프로토콜과 같은 기능으로 네트워크 지연과 노드의 장애에도 불구하고 합의를 이루고 정상적으로 동작함으로써 Liveness를 보장한다. 그러나 긴 지연이 발생하면 Liveness를 완전하게 보장한다고 할 수는 없어서 Liveness는 일부 희생한다고 보면 된다.

 

 

여기까지 Fail-Stop 알고리즘 Paxos, Raft와 BFT 알고리즘 PBFT에 대해서 알아보았다.^[각주:11] 그러나 FLP Impossibility 증명에서 제시한 비동기 네트워크에서 발생하는 Liveness 문제는 완전하게 극복할 수 없는 것일까? 하지만, 분산된 원장 첫 번째 블록체인 상용 사례인 비트코인 합의 알고리즘 PoW을 보면 재밌는 부분이 있다. 

 

비트코인 합의 알고리즘, PoW

2008년 공개된 'Bitcoin: A Peer-to-Peer Electronic Cash System'^[각주:12] 논문에는 Safety와 Liveness의 밸런스에 대해 기존 합의 알고리즘과는 다른 접근 방식을 보여주었다. 기본적으로 Saftey와 Liveness를 대하는 분산 컴퓨팅의 통념을 무시했다. 위 Paxos, Raft, PBFT와 같은 합의 알고리즘을 보면 Safety를 확보한 상태에서 비동기 네트워크에서 발생하는 Liveness의 손실을 최소화할지 고민했지만, PoW는 전통적인 결정론적 방식이 아닌 확률론적 접근 방식을 통해 문제를 돌파하였다.

• Safety: 비트코인 PoW는 일단 트랜잭션이 블록체인에 추가되면 모든 노드에서 변경 불가능하고 일관되게 유지하도록 Safety를 보장한다. 확인해야 하는 트랜잭션이 많아질수록(블록의 길이가 길어질수록) 보안은 더욱 강화된다. 물론, Safety를 확률적으로 확보하는 것이기 때문에 51% 공격과 같은 네트워크 공격이 성공할 경우 Safety를 보장할 수 없다는 단점을 안고 있다. 
• Liveness: 비트코인 네트워크는 블록체인에 새 블록을 계속해서 추가하는 방식으로 Liveness를 최대화한다. 네트워크 내에 있는 모든 거래를 전부 합의하지는 못하더라도, 일단 합의된 거래는 네트워크 내에 있는 모두가 동일한 값으로 제공되는 것이 더 중요하다고 보았기 때문이다. 비트코인 네트워크는 모든 유효한 트랜잭션을 수락하고 가장 긴 블록을 따라 포크를 해결함으로써 Liveness를 보장하고 있다. 그래서 높은 해쉬 파워(Hash Rates)가 비트코인 네트워크의 Liveness를 뜻한다. 그리고 Liveness가 높을수록 51% 공격에 대한 위험은 낮아지고 탈중앙성은 높아진다고 볼 수 있다. 

 

Pow의 Liveness에 대해 더 자세히 알아보자. 만약 두 채굴자가 동시에 블록을 생성한다면 어떻게 될까?

 

동시 블록 생성

S 블록에서 A와 B로 fork가 생긴다고 가정해보자. A 블록 내용과 B 블록 내용은 다르기 때문에 Safety는 이제 깨지게 된다. 그래서 확률론적이라고 하는 것이다. 

 

bitcoin block fork A, B

 

참고로, 이렇게 Block이 fork 되는 현상은 매우 흔하게 발생한다. 이러한 충돌을 해소하기 위해 비트코인 뿐만 아니라 여타 다른 체인들에서도 Block Reorganization이 작업이 이루어진다. 이러한 현상으로 인해 최신인줄 알았던 블록이 사라지는 현상도 발생하기 때문에 아직은 사용자 경험이 그렇게 좋은 기술은 아니다.^[각주:13]

 

줄다리기 시작

여기서 이제 줄다리기가 시작된다. 

block 줄다리기

 

더 긴 체인을 채택

최종적으로는 결국 긴 체인이 채택된다. 

 

긴 체인 선택

 

 

체인에 포함되지 않은 B계열에 있는 고아 블록에 있는 트랜잭션들은 다른 블록에 포함되어 추가된다. 만약 51%, 49% 시나리오가 장기적으로 지속되면 어떻게 할까? 일반적인 시나리오에서는 거의 발생하지 않는다.(가장 큰 규모로는 ethereum epoch 121471에서 7개의 블록이 re-org 발생한 적이 있다) 혹 고의적으로 기존 네트워크에 침투하는 세력이 있는 경우에는 엄청난 해시력이 필요하기 때문에 긴 fork 상황이 지속될수록 불안정한 상태로 머물게된다. 그리고 51% 공격을 계속 한다고 해도 어떠한 체계, 가치를 무너뜨리는 동기가 없는 한 결국 공격자가 경제적으로 손실을 보게 된다. 가장 높은 연산력(51%)을 보유하게 되면 가장 많은 블록을 생성하게 되고 블록의 신뢰성이 무너지게 됨에 따라 손해가 보는 쪽은 높은 연산력을 가지고 있는 쪽이기 때문이다. 

 

비트코인 PoW 합의 알고리즘의 Safety, Liveness에 대해 정리하면 다음과 같다.

 

	PoW(Proof of Work)
개념	채굴자는 블록체인에 새로운 블록을 생성하기 위해 복잡한 수학 문제를 해결한다.
Safety	Raft, Paxos는 완전한 Safety를 보장하려는 반면에, PoW는 가장 긴 체인을 통해 확률적으로 Safety를 보장한다. 그래서 51% 공격을 할 수 있다.
Liveness	지속적인 채굴 활동으로 인해 Liveness를 보장한다. 채굴 보상 시스템에 의해 Liveness에 영향을 줄 수 있다.

 

정리

비트코인은 우선 모든 거래(트랜잭션)를 수용하는 방식으로 Liveness를 완전하게 보장하고 하드포크가 발생할 경우 가장 긴 블록을 활용하는 방식으로 Safety 문제를 보완했다. 기존 다른 합의 알고리즘은 이러한 방식을 생각할 수 없었던 것일까? 아니면 사용할 수 없었던 것일까? 개인적으로는 다루고자 하는 문제가 달라서 이러한 결과물이 나왔다고 생각한다. 

 

Fail-Stop 단순 기존 분산 컴퓨팅 합의 알고리즘 목적은 하나의 컴퓨팅 능력으로는 한계가 있어 여러 노드가 협력하여 일관된 상태를 유지하고, 데이터의 정확성과 무결성을 보장하는 데 있었다. Safety와 Liveness는 이러한 시스템들이 효율적으로 동작하고, 오류나 장애에도 불구하고 데이터의 일관성을 유지하는 데 필수적인 요소였다. 그래서 적용된 Apache Zookeeper(Paxos 알고리즘), Apache Kafka의 KRaft(Raft 알고리즘)와 같은 백엔드 개발에 필요한 상용 기술에 주로 접목되어 있다.

 

PBFT는 데이터 일관성 보장을 지키면서 더 나아가 악의적인 공격에서도 합의를 이룰 수 있게하기 위해 고안되었다. 그만큼 높은 네트워크 통신을 요구한다는 단점이 있다. 금융 서비스, 항공 교통 제어 시스템 등의 고신뢰성이 요구되는 분야에 적합하며, 블록체인에서도 널리 사용되고 있다. Tendermint, HyperLedger가 이에 속한다.

 

PoW는 완전히 분산되고 익명인 환경에서 무신뢰 합의를 가능하게 하기 위해 개발되었다. 목표는 중앙 기관에 의존하지 않는 디지털 현금 시스템을 만드는 것이었다. 멈추지 않는 시스템을 만들어야 했기 때문에 강력한 Liveness을 불어넣었다. 무언가 서사 구조가 Evolution 느낌이 있지만 그런 것보다는 목적에 따라 그에 알맞는 방향으로 설계되었다고 보는 것이 좋을 듯 싶다.

 

Resources

1. Randy Wiggiton, Ryan Lowe, Macros Albe, and Fernando Ipar, "Distributed Transactions in MYSQL" [본문으로]
2. Coupang Reveal 2021, 쿠팡의 대규모 트래픽을 다루는 백엔드 전략 [본문으로]
3. KRaft: Apache Kafka Without ZooKeeper, Confluent [본문으로]
4. SAFETY, LIVENESS, AND CONSISTENCY, University of Washington [본문으로]
5. Impossibility of Distributed Consensus with One Faulty Process, Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson [본문으로]
6. Leslie Lamport, ACM Transactions on Computer System 16, 2. May 1998. The Part-Time Parliament [본문으로]
7. Diego Ongaro, John Ousterhout, "In Search of an Understandable Consensus Algorithm", Stanford Univ [본문으로]
8. HTTP/1에서 2.0 그리고 3.0 으로 [본문으로]
9. PBFT, Practical Byzantine Fault Tolerance, Hashnet [본문으로]
10. MIGUEL CASTRO, BARBARA LISKOV, Practical Byzantine Fault Tolerance and Proactive Recovery [본문으로]
11. 한국블록체인비즈니스연구회 공식 리서치팀 #48. 합의 알고리즘 이해하기 - PBFT Consensus Algorithm [본문으로]
12. Satoshi Nakamoto, Oct 2008. Bitcoin: A Peer-to-Peer Electronic Cash System [본문으로]
13. Brady Werkheiser, Alchemy, Juen 2022. What is a reorg? [본문으로]