분산 합의 (Consensus) 알고리즘

Paxos와 Raft 알고리즘의 동작 원리 및 한계점 #

이 두 알고리즘은 노드 장애 crash fault를 견디고 동일한 상태를 복제하기 위해 설계된 대표적인 합의 알고리즘이다.

Paxos #

Paxos는 제안자 Proposer, 수락자 Acceptor, 학습자 Learner로 역할을 분담한다. 합의 과정은 크게 2단계로 나뉜다.

Prepare/Promise: 제안자가 제안 번호를 생성해 수락자들에게 보내고, 수라작들은 더 높은 번호의 제안을 받지 않겠다고 약속 promise 한다.
Accept/Aceepted: 과반수의 약속을 받으면 제안자가 실제 데이터를 담아 수락을 요청하고, 수락자들이 이를 승인하면 합의가 완료된다.

한계점은 알고리즘 자체가 매우 추상적이고 이해하기가 어려우며 논문에서 다루는 기본 paxos 즉 singole-decree paxos 만으로는 지속적인 로그 복제가 어려워 멀티 팍소스로 확장을 해야한다는데 표준화된 아키텍처가 없어 시스템마다 구현체가 파편화되는 문제가 있다.

정족수 교차 원리를 알아보자.

N \ge 2F + 1

분산 시스템에서 데이터 일관성을 유지하기 위한 수학적 기반은 '비둘기집 원리'를 응용한 정족수 교차 Quorum Intersection이다.

상황 증명: 읽기 정족수를 R, 쓰기를 W라고 할때 최신 데이터를 항상 읽어오기 위해서는 이전 쓰기에 참여한 노드와 이번 읽기에 참여하는 노드 사이에 최소 1개의 노드가 겹쳐야한다. 즉,

R + W > N

을 만족해야한다. 가용성을 극대화하기 위해 보통 $R = W = \lfloor \frac{N}{2} \rfloor + 1$ 과반수로 설정한다.

수식을 전개하면 전체 노드중 F가 다운되었을때 남은 N - F 노드로 과반수 정족수를 채워 시스템이 멈추지 않게 돌아가야한다.

N - F \ge \lfloor \frac{N}{2} \rfloor + 1

이를 정리하면 합의를 위한 최소 노드 조건은

N \ge 2F + 1

실제 한계는 과반수 미만의 장애까지는 견딜 수 있으나 하지만 시스템 전체 노드 절반 이상이 동시에 다운되거나 네트워크 분절로 과반수를 구성할 수 없게되면 paxos 기반 시스템은 잘못된 데이터를 쓰느니 시스템 전체의 쓰기 작업을 거부 즉 가용성을 포기하는 한계가 있다.

FLP 불가능성 정리와 livelock #

Paxos를 이해할 때 가장 중요한 이론적 한계는 1985년 증명된 FLP impossibiliity 이다.

비동기 네트워크 환경에서는 단 1개의 노드만 다운되어도 안정성과 생존성을 동시에 100% 만족하는 결정론적 합의 알고리즘은 존재하지 않는다.
안정성: 모든 노드가 동일한 값에 합의함 (결코 두개의 다른 합의 없음)
생존성: 시스템이 멈추지 않고 언젠가는 반드시 합의를 종료함
실제상황에서 paxos는 무결성을 위해 안정성을 선택하고 생존성을 포기했다 결과적으로 라이브락이라는 수학적 딜레마에 빠지게 되는데
- 제안자 A가 제안번호 1로 1단계를 과반수로 받아낸다
- A가 2단계 accept를 요청하기 전에 제안자 B가 번호2로 1단계 요청을 과반수의 약속으로 갱신해버린다.
- A의 2단계 요청은 기각된다. 화가난 A는 제안번호 3으로 다시 1단계 요청을해 B를 무효화시킨다
- B의 2단계가 기각된다.

위 상황처럼 타이밍이 절묘하게 엇갈리면 아무도 장애가 나지 않았음에도 합의가 영원히 완료되지않고 리소스를 소모하는 무한루프 상태에 빠지는 것이 순수 paxos 알고리즘이 가진 수학적 논리적 한계점이다.

그럼에도 주키퍼가 이걸 기용한 이유를 알고싶다면 다음 포스팅에서 이어적어보겠다.

Raft #

Raft는 paxos의 이해와 구현의 어려움을 해결하기위해 탄생했고 노드의 상태를 Leader, Follower, Candidate 이 3가지로 명확하게 나눈다.

모든 클라이언트들의 요청은 오직 리더가 받으며, 리더는 이 요청을 로그로 만들어 팔로워들에게 복제(log replication) 한 뒤에 과반수가 응답하면 데이터를 확정 commit 한다.

강력한 리더 기반 구조이기 때문에 write 요청이 폭증하는 대규모 트래픽 환경에서는 노드의 네트워크 대역폭이나 처리능력이 전체 클러스터의 병목이 될 수도 있다.

etcd, Zookeeper 내부 구현체의 리더 선출 및 split-brain 방어 기법 #

이 두 시스템은 분산 환경의 설정 관리 및 서비스 디스커버리를 위해 널리 사용되며, 각각 Raft, ZAB(Zookeepr Atomic Broadcast) 프로토콜을 사용한다.

리더 선출 기법 #

etcd (Raft 프로토콜 기반): 리더가 주기적으로 보내는 하트비트가 끊기면 팔로워들은 후보자 상태로 전환하여 투표를 시작한다. 이때 동시에 여러 후보자가 나와 표가 분산되는 것을 막기 위해 랜덤 타임아웃 randomized election timeout을 사용한다. 각 노드가 150~300ms 사이의 무작위 시간을 대기하므로 가장 먼저 깨어난 노드가 리더로 선출될 확률이 높다.
Zookeeper(ZAB 프로토콜 기반): Fast Leader Election 알고리즘을 사용한다. 노드들은 자신이 가진 데이터의 최신 상태를 나타내는 zxid(트랜잭션 id)를 서로 교환한다. 기본적으로 데이터가 가장 최신인 zxid가 가장 높은 노드가 리더로 선출되며 만약 최신 상태와 같다면 설정된 노드 ID myid가 더 큰쪽이 리더가 된다.

Split-Brain 방어 #

네트워크가 단절되어 클러스터가 두 개 이상으로 쪼개질 때, 양쪽 모두 리더를 선출하여 데이터가 엇갈리는 현상을 split brain이라고 한다.

두 시스템 모두 과반수 quorum 룰을 통해 원칙적으로 방어한다.

클러스터가 5대일때 네트워크가 3대와 2대로 쪼개진다고 가정해보겠다.
3대가 있는 그룹은 전체의 과반수 (n / 2 + 1)을 넘기 때문에 정상적으로 리더를 선출하고 데이터를 기록할 수 있다.
2대가 있는 그룹은 과반수를 채우지 못하므로 새로운 리더를 선출할 수 없고, 기존 리더가 이 그룹에 포함되어 있더라도 쓰기 요청시 과반수 응답을 받지 못해 데이터를 commit 하지 못한다.
추가로 임기 Raft의 Term, Zookeeper의 Epoch 번호를 사용하여 네트워크 복구 시 예전 임기의 리더가 가진 권한을 즉시 무효화한다.

대규모 클러스터에서 BFT(Byzantine Fault Toleration) #

단순히 노드가 꺼지는 장애 crash를 넘어, 노드가 해킹되거나 악의적으로 거짓 정보를 퍼트리는 상황 byzantine fault 비잔티움 폴트까지 방어하는 알고리즘이 BFT다.

BFT의 한계와 대규모 적용의 어려움이 있는데 합의에 참여하는 노드가 서로 교차 검증해야하므로 노드 수가 증가할 수록 통신량이 기하급수적으로 증가(통상적으로 노드 수의 제곱에 비례)한다. 따라서 수백 수천대의 노드가 참여하는 대규모 클러스터에서는 전통적인 PBFT(Practical BFT)를 직접 적용하기 어렵다.

비잔틴 장애 허용 BFT 동작 방식과 수학적 한계 #

BFT 알고리즘 예를들어 PBFT는 노드가 단순히 다운되는것을넘어 해킹되어 거짓 정보를 보내는 악의적인행위 여기선 Byzantine라고 부름. 를 방어하는 합의구조이다.

이를 위해 모든 노드는 리더가 보낸 메시지 뿐만 아니라 다른 일반 노드들이 어떤 메시지를 받았는지 서로 교차 검증한다.

한계 지표 내결함성 조건은

N \ge 3F + 1

를 따라야하는데, BFT 시스템이 정상적으로 합의를 이루기위한 총 노드수 N와 허용 가능한 악의적 노드수 F의 수학적 한계이다.

즉 전체노드의 1/3 이상이 악의적이면 합의가 불가능하다라고 하고 그 증명은 다음과 같다.

네트워크 지연으로 인해 전체 N개의 노드중에 F개의 노드가 응답하지 않는 최악의 상황을 가정한다. 시스템은 무한정 기다릴 수 없으므로 최소 N - F 개의 응답만으로 다수결 결정을 내려야한다. 그런데 하필 응답을 보낸 N - F개의 노드중에 악의적인 노드 F가 모두 포함되어 거짓말을 하고있다면? 다수결로 올바른 합의 (정상 노드의 의견 채택)을 하려면 순수하게 정상적인 노드의 수가 악의적인 노드의 수보다 무조건 많아야한다. 그렇다 맞는말을 하는사람보다 아닌말을 하는사람이 더 많아 아닌말이 맞는말이 되어버린다는것을 막는것이다.

정상 노드 수: $(N - F) - F = N - 2F$ 악의적 노드 수: $F$

N - 2F > F

N > 3F

실제 한계 F = 1을 방어하기 위해 최소 4대의 노드가 필요하며 악의적인 노드 전체가 $frac{1}{3}$ 을 넘어서면 시스템 안정성이 깨져 두 개의 다른 데이터가 동시에 합의될 위험이 생긴다.

메시지 통신 복잡도의 한계 #

O(N^2)

BFT의 가장 큰 성능적 한계는 네트워크 대역폭의 고갈이기도 하다.

수학적 한계: 교차 검증을 위해 각 노드는 다른 모든 노드에게 자신이 받은 메시지를 방송 broadcast 해야한다. PBFT의 경우에는 prepare 단계와 commit 단계에서 각각 O(n^2) 메시지가 발생하고 노드수가 증가할수록 네트워크에 전송되는 총 메시지 수는 제곱으로 폭증하게 된다.
실제 한계: 노드가 10대일때 수 백개의 메시지로 긑나지만, 노드가 1,000대가 되면 단 한번의 데이터 저장을 위해 수백만개의 메시지가 쏟아지고 이 때문에 퍼블릭 블록체인에서 10,000대이상의 전체 노드에 전통적인 BFT를 직접 적용하는 것은 물리적인 네트워크 대역폭의 한계로 불가능하다.

대규모 클러스터 적용 및 해결 사례 #

퍼블릭 블록체인의 위임형 검증자 Tenderminit/Cosmos: 전체 네트워크에 수만대의 노드가 있더라도 지분(Stake)등에 의해 선출된 소수의 검증자 validator ex. 100~150 그룹을 구성한다. 합의를 위한 BFT 과정은 이 검증자 그룹 내부에서만 수행하여 성능 저하를 막고 나머지 일반 노드를은 결정된 합의를 전달받는 구조로 대규모 확장을 이루어냈다.
허가형 Permissioned 엔터프라이즈 환경 Hyperledger Fabric: 신원이 확인된 기업이나 기관들끼리 네트워크를 구성할 때 사용한다. 완전히 신뢰할 수 없는 멀티 테넌트 환경이므로 BFT가 필요하지만, 노드 수가 통제가 가능하기 때문에 합의 노드 orderer 들 사이에서 최적화된 BFT계열 알고리즘을 사용하여 초당 수천건 이상의 트랜잭션을 처리한다.
우주항공 및 군사 분산 제어 시스템: 가장 고전적인 형태의 사례인데 비행기나 우주선의 다중센서와 제어 컴퓨터들이 방사선이나 물리적 손상으로 인해 임의의 오작동(비잔티움)을 일으킬때 전체 비행 시스템이 올바른 방향을 유지하도록 대규모 센서 네트워크간의 상태를 합의하는데 사용된다.