정족수

무언가를 성립시키는 데 필요한 최소한의 동의 수입니다. 복제본을 여럿 둔 시스템에서는 몇 개가 답해야 그 읽기나 쓰기를 끝난 것으로 칠지를 이 값이 정합니다. 전부를 기다리지도 않고 하나만 믿지도 않는 자리입니다.

상세

회의에서 쓰는 정족수와 같은 말입니다. 정해진 인원이 모여야 안건을 처리할 수 있습니다.

정족수는 어떤 연산을 성립시키려면 동의를 받아야 하는 최소한의 노드 집합입니다. 복제본이 셋이면 둘이 답해야 하고 다섯이면 셋이 답해야 하는 식입니다. 숫자 하나로 적히지만 실제로 일을 하는 것은 그 숫자로 만들어지는 집합들입니다. 본체는 수가 아니라 두 번의 결정이 서로 겹치느냐입니다.

과반수는 전체의 절반을 넘는 수를 말합니다. 정족수를 그 크기로 잡은 것이 과반수 정족수이고, 줄여서 과반이라 부릅니다.

핵심 성질은 겹침입니다. Paxos 를 설명한 논문은 값을 하나만 고르게 하려면 충분히 큰 집합을 그저 아무 과반수로 잡으면 된다고 적습니다. 근거로 드는 것은 어떤 두 과반수도 최소 한 명의 수락자를 공통으로 갖는다는 점입니다. 수락자가 값을 최대 하나만 수락할 수 있다면 이것으로 충분합니다.

Raft 논문의 안전성 증명도 같은 겹침에 기댑니다. 앞선 임기의 리더가 로그 항목을 클러스터의 과반에 복제했고 뒤 임기의 리더가 클러스터 과반의 표를 받았다면, 그 항목을 받아들이면서 동시에 새 리더에게 표를 던진 서버가 최소 하나 있습니다. 논문은 그 서버를 투표자라 부르고 그것이 모순을 끌어내는 열쇠라고 적습니다.

flowchart TB
    A["앞 임기 리더가 로그 항목을 복제한 과반 · 세 대"]
    B["뒤 임기 리더에게 표를 던진 과반 · 세 대"]
    subgraph C["서버 다섯 대"]
        direction TD
        S1["서버 1"]
        S2["서버 2"]
        S3["서버 3 · 투표자"]
        S4["서버 4"]
        S5["서버 5"]
    end
    A --> S1
    A --> S2
    A --> S3
    B --> S3
    B --> S4
    B --> S5

서버가 다섯 대면 과반은 세 대입니다. 세 대를 두 번 고르면 자리가 여섯인데 서버는 다섯뿐이라 어느 한 대는 두 번 뽑힐 수밖에 없습니다. 그림의 서버 3 이 그 자리이고 논문이 투표자라 부르는 서버입니다. 그래서 뒤에 오는 결정은 앞의 결정을 아는 서버를 반드시 하나는 만나고, 서로를 모르는 두 결정이 동시에 성립하는 일이 막힙니다.

과반수가 가장 흔한 선택인 까닭이 여기 있습니다. 어떤 두 집합도 반드시 겹치게 만드는 가장 작은 크기가 과반이기 때문입니다. 겹치기만 하면 되므로 전부의 동의를 기다릴 필요가 없고, 나머지가 답하지 않아도 연산은 진행됩니다. 반대로 정족수를 못 채우면 그 연산은 성립하지 않습니다.

배경

같은 데이터를 여러 대에 복제해 두는 까닭은 한 대가 죽어도 서비스를 이어 가기 위해서입니다. 그런데 복제본이 여럿이 되는 순간 정해야 할 것이 하나 생깁니다. 어디까지 반영되어야 그 쓰기를 끝난 것으로 칠 것인가입니다.

양 끝은 둘 다 곤란합니다. 전부의 동의를 받기로 하면 한 대만 죽거나 응답이 늦어도 모든 쓰기가 멈춥니다. 복제본을 늘릴수록 멈출 자리가 늘어납니다. 반대로 아무 한 대의 동의만 받기로 하면 서로 다른 두 요청이 서로 다른 복제본에서 각각 성립합니다. 나중에 둘을 맞춰 보면 어느 쪽이 진짜인지 가릴 근거가 없습니다.

필요했던 것은 그 사이의 조건이었습니다. 전부는 아니되, 두 번의 결정이 서로를 모른 채 지나치는 일은 없어야 합니다. 이 조건을 만족시키는 가장 간단한 방법이 서로 겹치는 집합만 인정하는 것이고, 그 집합을 의사결정 기구에서 쓰던 말을 그대로 빌려 정족수라 부릅니다.

갈래

갈리는 축은 둘입니다. 정족수를 하나로 두느냐 연산마다 따로 두느냐, 그리고 겹침을 어디까지 요구하느냐입니다.

과반수 정족수

모든 정족수를 같은 크기로 두고 그 크기를 과반으로 잡습니다. 멤버가 n 개인 클러스터의 정족수는 (n/2)+1 입니다. 어떤 두 과반수도 서로 겹치므로 따로 붙일 조건이 없습니다. 가장 단순한 형태라 합의 알고리즘의 기본형이 대개 이 모양입니다.

홀수 노드 권고가 여기서 나옵니다. 홀수 크기 클러스터에 노드를 하나 더하면 정족수에 필요한 노드 수는 언제나 늘어납니다. 기계가 많아지니 나아 보이지만, 정족수를 잃지 않고 죽을 수 있는 노드 수는 똑같은데 죽을 수 있는 노드만 늘어납니다. 클러스터 크기를 짝수로 올리는 것은 추가 장애 내성을 사 주지 않습니다.

읽기 정족수와 쓰기 정족수

읽기와 쓰기에 각각 다른 정족수를 두고, 둘이 겹치도록만 맞춥니다. Dynamo 논문은 설정값 두 개를 둡니다. R 은 읽기 하나가 성공하려면 참여해야 하는 최소 노드 수, W 는 쓰기 하나가 성공하려면 참여해야 하는 최소 노드 수입니다. 복제 계수를 N 이라 할 때 R + W > N 이 되도록 잡으면 정족수 비슷한 시스템이 됩니다.

(N, R, W) = (3, 2, 2)

여러 Dynamo 인스턴스가 쓰는 흔한 설정입니다. 왜 합이 N 을 넘어야 하는지는 복제본 셋을 늘어놓고 보면 드러납니다.

flowchart TB
    subgraph G1["쓰기 둘 · 읽기 둘 · 합이 넷 — 복제본 셋을 넘어 겹친다"]
        direction TD
        W1["쓰기 정족수"] --> A1["복제본 1"]
        W1 --> A2["복제본 2 · 새 값을 갖고 읽기에도 답한다"]
        R1["읽기 정족수"] --> A2
        R1 --> A3["복제본 3"]
    end
    subgraph G2["쓰기 하나 · 읽기 하나 · 합이 둘 — 복제본 셋을 못 넘어 안 겹친다"]
        direction TD
        W2["쓰기 정족수"] --> B1["복제본 1"]
        R2["읽기 정족수"] --> B3["복제본 3"]
        B2["복제본 2"]
    end

합이 넷인 칸에서는 복제본이 셋뿐이라 두 쪽이 같은 복제본을 최소 하나 붙잡습니다. 그 복제본이 방금 쓴 값을 갖고 있으니 읽기가 새 값을 놓치지 않습니다. 합이 둘인 칸에서는 셋을 못 넘습니다. 쓰기가 붙잡은 복제본과 읽기가 붙잡은 복제본이 어긋날 수 있고, 그러면 읽기는 옛 값만 보고 끝납니다.

이 모델에서 읽기나 쓰기 하나의 지연은 R 개(또는 W 개) 복제본 가운데 응답이 가장 늦은 것이 정합니다. 그래서 R 과 W 는 지연을 위해 보통 N 보다 작게 잡습니다. Cassandra 의 일관성 수준은 이 방식의 한 판입니다. 읽기 쪽 일관성 수준이 쓰기 쪽과 정족수 교집합을 보장할 만큼의 노드를 담으면, 쓰기는 대체로 뒤이은 읽기에 보입니다.

유연 정족수

겹침을 모든 자리에 요구하지 않는 갈래입니다. Flexible Paxos 논문은 두 단계가 각각 과반수 합의를 요구하는 Paxos 가 보수적이라고 지적합니다. 관찰한 것은 Paxos 의 각 단계가 서로 겹치지 않는 정족수를 써도 된다는 점입니다. 교집합은 단계 사이에서만 필요하므로 과반수 정족수는 필수가 아닙니다. 이 완화를 써서 정족수를 유연하게 고를 수 있게 일반화한 것이 Flexible Paxos 입니다.

예시

etcd 의 클러스터 크기 표

클러스터 상태 갱신에 합의하려면 노드의 과반, 곧 정족수가 필요합니다. 멤버가 n 개인 클러스터의 정족수는 (n/2)+1 입니다. 공식 FAQ 는 크기별로 정족수와 견딜 수 있는 장애 수를 이렇게 적습니다.

3 과 4 를 견줘 보면 정족수만 2 에서 3 으로 올라가고 장애 내성은 1 그대로입니다. 홀수 크기 클러스터는 짝수 크기와 같은 수의 장애를 견디면서 노드는 더 적게 씁니다.

MongoDB 의 w: "majority"

쓰기 관심사 값입니다. 이 값이 요구하는 과반이 그 쓰기의 정족수입니다. 계산된 과반의 데이터 보유 투표 멤버가 자기 로컬 oplog(operations log, 연산 로그)에 그 변경을 내구성 있게 썼다는 확인을 요청합니다. 여기서 말하는 과반은 두 값 중 작은 쪽으로 계산됩니다. 아비터를 포함한 모든 투표 멤버의 과반, 그리고 데이터 보유 투표 멤버의 수입니다.

투표 멤버 3 (프라이머리-세컨더리-세컨더리)
  모든 투표 멤버의 과반 = 2
  데이터 보유 투표 멤버 수 = 3
  계산된 과반 = min(2, 3) = 2

투표 멤버 3 (프라이머리-세컨더리-아비터)
  모든 투표 멤버의 과반 = 2
  데이터 보유 투표 멤버 수 = 2
  계산된 과반 = min(2, 2) = 2

앞의 구성에서는 프라이머리와 세컨더리 하나에 전파되면 클라이언트에게 확인이 돌아갑니다. 뒤의 구성에서는 쓰기가 데이터 보유 멤버에만 적용될 수 있으므로 프라이머리와 세컨더리에 전파되어야 합니다. 같은 값 "majority" 를 걸어도 멤버 구성에 따라 실제로 기다리는 대상이 달라집니다.

Apache Cassandra 의 QUORUM 일관성 수준

Cassandra 는 연산마다 일관성과 가용성을 맞바꾸게 하고, 그 손잡이를 일관성 수준이라 부릅니다. 운영자는 복제 계수를 몰라도 메뉴에서 고르기만 하면 됩니다.

ONE           복제본 하나만 응답하면 된다
TWO           복제본 둘이 응답해야 한다
THREE         복제본 셋이 응답해야 한다
QUORUM        복제본의 과반(N/2 + 1)이 응답해야 한다
ALL           복제본 전부가 응답해야 한다
LOCAL_QUORUM  코디네이터가 속한 데이터센터의 복제본 과반이 응답해야 한다
EACH_QUORUM   각 데이터센터의 복제본 과반이 응답해야 한다

QUORUM 이 과반수 정족수 그 자체이고, LOCAL_QUORUM 과 EACH_QUORUM 은 셀 범위를 데이터센터로 좁히거나 데이터센터마다 따로 요구하는 변형입니다.

Apache ZooKeeper 의 앙상블

ZooKeeper 는 클러스터를 앙상블이라 부릅니다. 앙상블의 과반이 살아 있는 한 서비스는 가용합니다. 여기서 요구하는 과반이 곧 이 서비스의 정족수입니다. 과반을 요구하기 때문에 홀수 대를 쓰는 편이 유리합니다. 네 대면 한 대의 장애만 감당할 수 있습니다. 두 대가 죽으면 남은 두 대가 과반을 이루지 못하기 때문입니다. 다섯 대면 두 대의 장애를 감당합니다.

서비스가 활성 상태이려면 서로 통신할 수 있는, 죽지 않은 기계의 과반이 있어야 합니다. 서버가 n 개인 앙상블에서 n 이 홀수이면 znode 데이터를 하나도 잃지 않고 최대 n/2 대의 서버 장애까지 견딥니다.

관련 항목

정족수를 요구하는 합의 프로토콜

합의 · Raft · Paxos · Flexible Paxos · 리더 선출

정족수를 이루는 구성 요소

클러스터 · 노드 · 복제 · 복제 계수 · 아비터 · 옵저버

정족수를 정하는 방식

과반수 · 홀수 노드 · 가중 투표 · 일관성 수준

정족수가 지키는 성질

정족수 교집합 · 선형화 가능성 · 결과적 일관성

정족수 크기와 맞바꾸는 값

장애 허용 · 가용성 · 고가용성 · 지연 대 처리량 · CAP(Consistency, Availability, Partition tolerance)

정족수가 깨졌을 때 나타나는 문제

정족수 상실 · 스플릿 브레인 · 네트워크 분단 · 좀비 노드

정족수를 실제로 채택한 시스템

Cassandra · etcd · MongoDB · ZooKeeper · Dynamo