사전 Raft
프로토콜

Raft

gabury1고친 사람 github-actions[bot]

Raft 는 여러 대의 서버가 같은 명령을 같은 순서로 받아 적게 맞추는 규칙입니다. 서버 가운데 한 대를 리더로 뽑습니다. 리더는 받은 명령을 나머지에게 나눠 줍니다. 과반이 받아 적은 명령만 확정합니다. 그래서 서버 몇 대가 죽어도 서비스가 멈추지 않습니다. 값도 어긋나지 않습니다.

쉽고 빠른 이해

Raft 는 서버 여러 대가 한 대처럼 굴게 만드는 규칙입니다. 예를 들어 서버 세 대에 설정값을 저장하면, 어느 서버에 물어봐도 같은 값이 나오게 해 줍니다.

서버를 한 대만 두면 그 한 대가 죽는 순간 서비스가 멈춥니다. 여러 대를 그냥 두면 서로 다른 값을 주장하게 됩니다. Raft 는 「과반이 동의한 것만 확정한다」로 두 문제를 같이 풉니다.

  1. 서버들이 투표로 리더 한 대를 뽑습니다
  2. 쓰기 요청은 전부 리더가 받아 나머지에게 복사합니다
  3. 과반이 받아 적었다는 답이 오면 그 쓰기를 확정합니다
  4. 리더에게서 소식이 끊기면 남은 서버들이 다시 투표합니다

대가도 있습니다. 모든 쓰기가 리더 한 대를 거쳐서 그 한 대가 처리량의 상한이 됩니다. 쓰기마다 과반의 답을 기다리느라 느려집니다. 과반이 살아 있지 않으면 쓰기가 아예 멈춥니다. 그래서 크기는 작고 틀리면 안 되는 데이터에 씁니다. 클러스터 설정이나 잠금 같은 것입니다.

상세

이 절은 Raft 가 무슨 문제를 풀고, 그 문제를 어떤 순서로 푸는지를 봅니다. 예시는 서버 세 대짜리 클러스터를 기본으로 씁니다. 클러스터는 한 가지 일을 함께 맡은 서버들의 무리입니다. 겹침이나 분단처럼 세 대로는 잘 안 보이는 대목에서만 네 대나 다섯 대로 바꿉니다.

회의록을 여러 사람이 각자 공책에 적는다고 해 봅시다. 사람마다 다르게 적으면 나중에 누구 공책이 맞는지 알 수 없습니다. 그래서 의장 한 사람을 뽑아 의장이 불러 주는 대로만 적게 합니다. 다만 Raft 의 의장은 참석자 과반이 받아 적었다고 답해야 그 줄을 확정합니다.

Raft 가 푸는 문제

Raft 는 합의를 푸는 규칙입니다. 합의는 여러 서버가 결정 하나에 함께 동의하게 하는 문제입니다. 서버 일부가 멈추거나 메시지가 늦게 가도 동의한 결정은 뒤집히면 안 됩니다.

이 규칙이 합의하는 대상은 로그입니다. 로그는 명령을 들어온 순서대로 한 줄씩 덧붙이는 목록입니다. 「x 를 1 로」, 「y 를 지워라」 같은 명령이 한 줄씩 쌓입니다.

로그를 맞추면 데이터가 같아지는 이유는 복제 상태 기계에 있습니다. 같은 초기 상태에서 같은 명령을 같은 순서로 실행하면 서버마다 같은 상태가 나옵니다. 그러니 로그만 똑같이 맞추면 서버 세 대의 데이터가 저절로 같아집니다.

아래 그림이 그 짜임입니다. 서버마다 로그와 상태 기계가 하나씩 들어 있습니다.

flowchart TD
    CL["클라이언트"] --> A1
    subgraph SA["서버 A · 리더"]
        A1["로그: x 를 1 로 · y 삭제"] --> A2["상태 기계"] --> A3["x = 1"]
    end
    subgraph SB["서버 B"]
        B1["로그: x 를 1 로 · y 삭제"] --> B2["상태 기계"] --> B3["x = 1"]
    end
    subgraph SC["서버 C"]
        C1["로그: x 를 1 로 · y 삭제"] --> C2["상태 기계"] --> C3["x = 1"]
    end
    A1 -. "같은 로그로 맞춤 · Raft" .-> B1
    A1 -. "같은 로그로 맞춤 · Raft" .-> C1

세 서버의 상태가 같은 것은 로그가 같아서입니다. Raft 가 맡는 일은 점선 부분, 곧 로그를 맞추는 일뿐입니다.

이렇게 로그를 여러 서버에 똑같이 두는 것을 복제 로그라고 부릅니다. Raft 는 이 복제 로그를 안전하게 맞추는 절차입니다.

과반

이 절차의 결정은 전부 과반으로 내립니다. 과반은 전체 서버 수의 절반보다 많은 수입니다. 세 대면 두 대, 다섯 대면 세 대입니다.

이 수를 쓰는 이유는 겹침입니다. 과반을 이루는 서버 무리를 두 번 고르면, 두 무리는 반드시 한 대 이상 겹칩니다. 다섯 대 가운데 세 대를 두 번 고르면, 어떻게 골라도 적어도 한 대는 양쪽에 다 들어갑니다.

flowchart TD
    subgraph P1["첫 결정에 동의한 과반 무리"]
        A["서버 A"]
        B["서버 B"]
    end
    subgraph BOTH["양쪽에 다 든 서버"]
        C["서버 C · 앞선 결정을 기억"]
    end
    subgraph P2["둘째 결정에 동의한 과반 무리"]
        D["서버 D"]
        E["서버 E"]
    end
    A --- C
    B --- C
    C --- D
    C --- E

그림에서 첫 무리는 A·B·C, 둘째 무리는 C·D·E 입니다. 겹친 C 가 앞선 결정을 기억하고 있습니다. 그래서 뒤의 결정이 앞의 것을 모르고 뒤집는 일을 막습니다.

이렇게 결정에 필요한 최소 인원을 정족수라고도 부릅니다. Raft 의 정족수는 과반입니다.

서버의 세 역할

서버는 언제나 세 역할 가운데 하나를 맡습니다.

역할 하는 일
리더 쓰기 요청을 받아 로그에 적고 나머지에게 복사합니다. 한 번에 한 대뿐입니다
팔로워 리더가 보낸 것을 받아 적고 답합니다. 스스로 요청을 처리하지 않습니다
후보 리더가 사라졌다고 보고 표를 모으는 중인 서버입니다

평소에는 리더 한 대에 나머지가 전부 팔로워입니다. 팔로워에게 쓰기 요청이 오면 리더에게 넘기거나 리더 주소를 알려 줍니다.

역할은 아래처럼 옮겨갑니다. 모든 서버는 팔로워로 시작합니다.

stateDiagram-v2
    [*] --> 팔로워
    팔로워 --> 후보: 리더 소식이 끊김
    후보 --> 리더: 과반의 표를 얻음
    후보 --> 후보: 표가 갈려 다시 선거
    후보 --> 팔로워: 다른 리더를 발견
    리더 --> 팔로워: 더 큰 임기를 발견

팔로워는 리더 소식이 끊기면 후보가 됩니다. 후보는 과반의 표를 얻으면 리더가 됩니다. 다른 리더를 만나면 팔로워로 돌아갑니다. 리더도 자기보다 큰 임기 번호를 보면 곧바로 팔로워로 내려갑니다. 임기는 바로 다음 소절에서 풉니다.

임기

시간은 임기로 나뉩니다. 임기는 1, 2, 3 처럼 하나씩 커지는 번호입니다. 선거가 한 번 열릴 때마다 임기가 하나 올라갑니다.

임기 하나에는 리더가 많아야 한 대입니다. 표가 갈려 아무도 못 뽑히면 그 임기는 리더 없이 끝납니다. 다음 임기에서 다시 뽑습니다.

flowchart TD
    T1["임기 1 · 선거"] --> T1R["리더 A 가 운영"]
    T1R --> T2["임기 2 · 선거"]
    T2 --> T2R["표가 갈림 · 리더 없이 끝남"]
    T2R --> T3["임기 3 · 선거"]
    T3 --> T3R["리더 B 가 운영"]

임기마다 선거로 시작합니다. 선거가 성공하면 그 임기 동안 리더가 운영하고, 실패하면 곧바로 다음 임기로 넘어갑니다.

임기 번호는 낡은 리더를 가려내는 데 씁니다. 서버끼리 주고받는 메시지에는 보낸 쪽의 임기가 늘 실립니다. 자기보다 큰 임기를 본 서버는 자기가 뒤처졌다는 것을 알고 팔로워로 돌아갑니다. 자기보다 작은 임기가 실린 메시지는 거절합니다.

예를 들어 임기 3 의 리더가 네트워크에서 잠시 끊겼다고 해 봅시다. 그 사이 나머지가 임기 4 의 새 리더를 뽑았습니다. 옛 리더가 돌아와 임기 3 으로 명령을 보내면 다른 서버들이 거절합니다. 옛 리더는 답에 실린 임기 4 를 보고 스스로 물러납니다.

sequenceDiagram
    participant A as 옛 리더 A
    participant B as 서버 B
    participant C as 새 리더 C
    Note over A: 네트워크에서 끊김
    Note over B,C: 그 사이 C 가 임기 4 리더
    A->>B: 명령 · 임기 3
    B-->>A: 거절 · 내 임기는 4
    Note over A: 팔로워로 물러남

A 는 자기가 아직 리더라고 믿고 있었습니다. 답에 실린 더 큰 번호 하나로 스스로 뒤처진 것을 알아챕니다.

리더 선출

리더는 살아 있다는 신호를 주기적으로 보냅니다. 이 신호를 하트비트라고 부릅니다. 보낼 명령이 없어도 빈 메시지를 계속 보냅니다.

팔로워는 저마다 선거 시한을 갖습니다. 선거 시한은 리더 소식을 얼마나 기다릴지 정한 시간입니다. 이 시간 안에 하트비트가 안 오면 리더가 죽었다고 보고 선거를 엽니다.

선거를 여는 서버는 네 일을 합니다.

  1. 임기를 하나 올리고 후보가 됩니다
  2. 자기 자신에게 한 표를 던집니다
  3. 나머지 서버에게 RequestVote 로 표를 청합니다
  4. 과반의 표가 모이면 리더가 되어 곧바로 하트비트를 보냅니다

RequestVote 는 표를 청하는 메시지입니다.

아래는 서버 A 가 리더 소식을 못 받아 선거를 여는 모습입니다.

sequenceDiagram
    participant A as 서버 A
    participant B as 서버 B
    participant C as 서버 C
    Note over A: 선거 시한이 지남 · 임기 5 후보
    A->>B: RequestVote 임기 5
    A->>C: RequestVote 임기 5
    B-->>A: 찬성
    Note over A: 자기 표 + B 의 표 · 과반
    Note over A: 임기 5 리더
    A->>B: 하트비트
    A->>C: 하트비트

A 는 자기 표와 B 의 표로 세 대 가운데 두 대를 모았습니다. 과반이라 C 의 답을 기다리지 않고 리더가 됩니다. 곧바로 하트비트를 보내 다른 서버가 선거를 열지 않게 막습니다.

서버 한 대는 임기 하나에 한 표만 던집니다. 기본은 먼저 청한 후보에게 주는 것입니다. 이 규칙에는 뒤의 「커밋된 줄을 지키는 투표 규칙」에서 조건이 하나 더 붙습니다.

한 표 규칙 덕분에 한 임기에 과반을 얻는 후보는 많아야 하나입니다. 과반을 이루는 두 무리는 반드시 한 대 이상 겹칩니다. 겹친 서버는 한 임기에 두 번 투표할 수 없습니다.

분할 투표

팔로워 여럿이 한꺼번에 후보가 되면 표가 나뉩니다. 누구도 과반을 못 얻고 임기가 끝납니다. 이것을 분할 투표라고 부릅니다.

아래는 네 대 클러스터에서 두 후보가 표를 반씩 나눠 가진 모습입니다. 네 대의 과반은 세 대입니다.

sequenceDiagram
    participant A as 서버 A
    participant B as 서버 B
    participant C as 서버 C
    participant D as 서버 D
    Note over A,C: A 와 C 가 함께 임기 5 후보
    A->>B: RequestVote 임기 5
    C->>D: RequestVote 임기 5
    B-->>A: 찬성
    D-->>C: 찬성
    Note over A,D: 둘 다 2표 · 과반 3 을 못 채움 · 임기 5 끝
    Note over A: 선거 시한이 먼저 끝난 A 가 임기 6 후보
    A->>B: RequestVote 임기 6
    A->>C: RequestVote 임기 6
    B-->>A: 찬성
    C-->>A: 찬성
    Note over A: 3표 · 과반 · 임기 6 리더

같은 일이 되풀이되지 않게 선거 시한을 서버마다 무작위로 고릅니다. 정해진 범위 안에서 저마다 다른 길이를 뽑습니다. 그러면 대개 선거 시한이 먼저 끝난 한 대가 선거를 엽니다. 다른 서버들의 시한이 끝나기 전에 그 한 대가 표를 다 모읍니다.

로그 복제

리더가 뽑히면 쓰기 요청을 받기 시작합니다. 로그의 줄마다 두 값이 함께 적힙니다. 몇 번째 줄인지를 뜻하는 줄 번호와, 그 줄을 받은 리더의 임기입니다.

요청 하나가 확정되기까지는 아래 순서를 밟습니다.

  1. 클라이언트가 리더에게 명령을 보냅니다
  2. 리더가 자기 로그 끝에 그 명령을 한 줄 덧붙입니다. 줄 번호와 지금 임기를 같이 적습니다
  3. 리더가 팔로워들에게 AppendEntries 로 새 줄을 보냅니다
  4. 과반이 받아 적었다고 답하면 리더가 그 줄을 확정합니다
  5. 리더가 명령을 실행하고 클라이언트에게 결과를 돌려줍니다

AppendEntries 는 로그 줄을 덧붙이라는 메시지입니다. 줄을 안 싣고 보내는 AppendEntries 가 하트비트입니다.

4 번에서 확정하는 것을 커밋이라고 부릅니다. 커밋된 줄은 다시는 지워지지 않습니다. 리더는 다음 AppendEntries 에 「여기까지 커밋됐다」를 실어 보냅니다. 팔로워는 그것을 보고 그 줄까지 실행합니다.

sequenceDiagram
    participant 클라이언트
    participant A as 리더 A
    participant B as 팔로워 B
    participant C as 팔로워 C
    클라이언트->>A: x 를 1 로
    Note over A: 로그 7 번 줄에 적음
    A->>B: AppendEntries 7 번 줄
    A->>C: AppendEntries 7 번 줄
    B-->>A: 적었음
    Note over A: A + B · 과반 · 7 번 줄 커밋
    A-->>클라이언트: 완료
    C-->>A: 적었음
    A->>B: AppendEntries · 7 번 줄까지 커밋됨
    A->>C: AppendEntries · 7 번 줄까지 커밋됨
    Note over B,C: 7 번 줄 실행

C 의 답은 클라이언트에게 완료를 알린 뒤에 도착했습니다. 과반이 이미 모였으니 뒤처진 한 대를 기다리지 않습니다. 이 덕분에 한 대가 늦거나 죽어도 쓰기가 계속 돕니다. 팔로워들은 다음 메시지에서 커밋 소식을 듣고 나서야 그 줄을 실행합니다.

로그 일치 검사

리더가 바뀌다 보면 팔로워 로그가 리더와 어긋날 수 있습니다. 줄이 모자라기도 하고, 커밋 안 된 줄이 남아 있기도 합니다. Raft 는 리더 로그를 정답으로 보고 팔로워를 거기에 맞춥니다.

맞추는 데 쓰는 것이 일치 검사입니다. 리더는 새 줄을 보낼 때 그 바로 앞 줄의 번호와 임기를 같이 보냅니다. 팔로워는 자기 로그의 같은 번호 줄이 같은 임기인지 봅니다.

같으면 새 줄을 덧붙이고 성공을 답합니다. 다르거나 그 줄이 없으면 거절합니다. 거절을 받은 리더는 한 줄 앞으로 물러나 다시 보냅니다.

아래는 어긋난 두 로그의 모양입니다. 칸마다 「줄 번호 · 임기」를 적었습니다.

flowchart TD
    subgraph L["리더 로그"]
        L1["1 · 임기 1"] --> L2["2 · 임기 1"] --> L3["3 · 임기 2"] --> L4["4 · 임기 3"]
    end
    subgraph F["팔로워 로그"]
        F1["1 · 임기 1"] --> F2["2 · 임기 1"] --> F3["3 · 임기 2 · 같음 · 일치 지점"] --> F4["4 · 임기 2 · 임기 다름 · 커밋 안 된 줄 · 지우고 리더 줄로 덮음"]
    end
    L --> F

3 번 줄까지는 번호와 임기가 둘 다 같습니다. 4 번 줄은 번호는 같지만 임기가 다릅니다. 팔로워의 4 번 줄은 옛 리더에게서 받았다가 커밋되지 못한 줄입니다.

리더가 새 5 번 줄을 보내면 두 로그는 아래처럼 주고받으며 맞춰집니다.

sequenceDiagram
    participant L as 리더
    participant F as 팔로워
    L->>F: AppendEntries 5 번 줄 · 앞 줄 4 · 임기 3
    Note over F: 내 4 번 줄은 임기 2 · 다름
    F-->>L: 거절
    Note over L: 한 줄 앞으로 물러남
    L->>F: AppendEntries 4~5 번 줄 · 앞 줄 3 · 임기 2
    Note over F: 내 3 번 줄도 임기 2 · 같음
    F-->>L: 성공 · 4 번 줄 덮어씀

첫 요청은 앞 줄 검사에서 걸렸습니다. 한 줄 물러난 둘째 요청이 일치 지점을 찾았고, 팔로워는 그 뒤를 리더의 줄로 바꿨습니다.

이렇게 물러나다 보면 두 로그가 같아지는 지점을 찾습니다. 그 뒤로 팔로워에게 남은 줄은 지우고 리더의 줄로 덮어씁니다. 지워지는 줄은 커밋되지 않은 줄뿐입니다. 이유는 바로 아래 소절에서 봅니다.

일치 검사가 지키는 성질은 이것입니다. 두 로그에서 번호와 임기가 같은 줄이 있으면, 그 줄과 그 앞의 모든 줄이 같습니다. 줄마다 바로 앞 줄을 검사하고 나서 붙였기 때문입니다. 그 앞 줄도 자기 앞 줄을 검사하고 붙었으니, 거슬러 올라가면 처음까지 전부 같습니다. 덕분에 한 줄만 비교해도 앞부분 전체가 같다는 것을 압니다.

커밋된 줄을 지키는 투표 규칙

리더가 커밋된 줄을 모르면 위의 덮어쓰기가 커밋된 줄까지 지웁니다. Raft 는 이것을 선거에서 막습니다. 커밋된 줄을 전부 가진 서버만 리더가 될 수 있게 합니다.

앞의 「먼저 청한 후보에게 한 표」에 조건이 하나 붙습니다. 투표하는 서버는 후보의 로그가 자기 로그만큼 최신일 때만 표를 줍니다. 최신을 가르는 법은 둘입니다.

비교 더 최신인 쪽
마지막 줄의 임기가 다르면 임기가 큰 쪽
마지막 줄의 임기가 같으면 로그가 긴 쪽

이 조건이 통하는 것은 과반의 겹침 덕분입니다. 커밋된 줄은 과반의 로그에 들어 있습니다. 후보가 리더가 되려면 과반의 표가 필요합니다. 과반을 이루는 두 무리는 한 대 이상 겹치므로, 그 줄을 가진 서버가 투표자 가운데 적어도 한 대 있습니다.

그 서버는 그 줄이 없는 후보에게 표를 주지 않습니다. 그러니 커밋된 줄이 없는 후보는 과반을 못 모읍니다. 새 리더는 언제나 커밋된 줄을 전부 갖고 시작합니다.

아래는 다섯 대에서 이 조건이 걸리는 모습입니다. 7 번 줄은 A·B·C 에 들어가 커밋됐습니다. 7 번 줄이 없는 E 가 C·D 에게 표를 청합니다.

flowchart TD
    subgraph HAS["7 번 줄을 가진 과반 무리"]
        A["서버 A"]
        B["서버 B"]
        C["서버 C · 두 무리에 다 듦"]
    end
    subgraph ASK["E 가 표를 청한 무리"]
        D["서버 D · 7 번 줄 없음 · 찬성"]
        E["후보 E · 7 번 줄 없음 · 자기 표"]
    end
    E -- "RequestVote" --> C
    E -- "RequestVote" --> D
    C --> R["C · 후보 로그가 덜 최신 · 표 거절"]
    R --> END["E 는 2표 · 과반 3 을 못 모음"]

E 가 모을 수 있는 표는 자기 표와 D 의 표뿐입니다. 셋째 표가 될 C 는 7 번 줄을 갖고 있어서 거절합니다.

견딜 수 있는 고장 수

Raft 는 과반이 살아 있는 동안 돕니다. 서버가 2f + 1 대면 f 대까지 죽어도 됩니다.

서버 수 과반 죽어도 되는 수
3 2 1
4 3 1
5 3 2
7 4 3

네 대는 세 대와 견디는 수가 같습니다. 서버만 늘고 과반도 같이 커지기 때문입니다. 클러스터를 대개 세 대나 다섯 대처럼 홀수로 꾸리는 것도 이 때문입니다.

분단 중의 동작

분단은 네트워크가 끊겨 서버들이 서로 못 닿는 무리로 갈리는 일입니다. 다섯 대가 세 대와 두 대로 갈린 경우를 봅니다. 옛 리더는 두 대 쪽에 남았습니다.

flowchart TD
    subgraph BIG["세 대 쪽 · 과반"]
        C["서버 C"]
        D["서버 D"]
        E["서버 E · 임기 N+1 새 리더 · 쓰기 커밋됨"]
    end
    subgraph SMALL["두 대 쪽"]
        A["서버 A · 임기 N 옛 리더 · 커밋 못 함"]
        B["서버 B"]
    end
    BIG -. "네트워크 끊김" .- SMALL

세 대 쪽은 리더 소식이 끊기니 선거를 열고, 과반인 세 표로 새 리더를 뽑습니다. 이 쪽은 쓰기를 계속 받습니다.

두 대 쪽의 옛 리더도 쓰기 요청을 받을 수는 있습니다. 그러나 과반의 답을 못 모으니 어떤 줄도 커밋하지 못합니다. 클라이언트는 완료 답을 못 받습니다.

리더가 두 대 있는 것처럼 보여도 값이 두 갈래로 확정되지 않습니다. 두 리더가 저마다 쓰기를 확정해 데이터가 갈리는 사고를 스플릿 브레인이라고 부릅니다. Raft 는 과반 규칙으로 이것을 막습니다. 네트워크가 이어지면 옛 리더는 더 큰 임기를 보고 물러납니다. 커밋 못 한 줄은 새 리더의 로그로 덮입니다.

스냅샷으로 로그 줄이기

로그는 덧붙이기만 하니 계속 커집니다. 새로 들어온 서버가 처음부터 전부 다시 실행하려면 오래 걸립니다.

서버는 이 문제를 스냅샷으로 풉니다. 스냅샷은 어느 줄까지 실행한 상태를 전부 저장한 사본입니다. 스냅샷을 뜨면 그 줄까지의 로그는 지워도 됩니다.

flowchart TD
    subgraph BEFORE["스냅샷 전"]
        B1["1 번 줄"] --> BM["2~5 번 줄"] --> B6["6 번 줄"] --> B7["7 번 줄"] --> B8["8 번 줄"] --> B9["9 번 줄"]
    end
    subgraph AFTER["스냅샷 후"]
        S["스냅샷 · 6 번 줄까지 실행한 상태"] --> A7["7 번 줄"] --> A8["8 번 줄"] --> A9["9 번 줄"]
    end
    BEFORE --> AFTER

1~6 번 줄 여섯 줄이 스냅샷 한 덩어리로 바뀌었습니다. 7 번 줄부터는 로그로 남습니다.

팔로워가 너무 뒤처져 리더가 이미 지운 줄을 요구하면, 리더는 줄 대신 스냅샷을 보냅니다. 팔로워는 스냅샷을 받아 상태를 갈아 끼웁니다. 그리고 그 뒤 줄부터 받아 적습니다.

sequenceDiagram
    participant L as 리더
    participant F as 뒤처진 팔로워
    Note over L: 6 번 줄까지 스냅샷 · 그 줄들은 지움
    Note over F: 3 번 줄부터 필요
    L->>F: 스냅샷
    Note over F: 상태를 갈아 끼움
    L->>F: AppendEntries 7 번 줄부터

리더에게 3 번 줄은 이미 없습니다. 그래서 줄을 하나씩 보내는 대신 6 번 줄까지의 결과를 한 번에 넘깁니다.

Raft 의 대가

이 절차는 안전과 맞바꿔 몇 가지를 내줍니다. 모든 쓰기가 리더 한 대로만 지나가서 생기는 대가입니다.

대가 까닭
쓰기 처리량의 상한 모든 쓰기가 리더 한 대를 거칩니다
쓰기 지연 쓰기마다 과반의 답을 기다립니다
선거 동안 쓰기 멈춤 리더가 죽으면 새 리더가 뽑힐 때까지 확정이 없습니다
과반을 잃으면 멈춤 살아 있는 서버가 과반에 못 미치면 쓰기를 거절합니다

표의 마지막 항목은 고른 결과입니다. 과반을 못 모을 때 틀린 값을 내느니 멈추는 쪽을 골랐습니다.

이 선택을 가리키는 말이 둘 있습니다. 일관성은 어느 서버에 물어도 같은 값이 나오는 성질입니다. 가용성은 요청에 늘 답하는 성질입니다.

CAP 정리는 네트워크가 갈렸을 때 이 둘을 함께 지킬 수 없다고 말합니다. Raft 는 그때 가용성을 내주고 일관성을 지키는 쪽입니다. CAP 는 Consistency · Availability · Partition tolerance 의 머리글자입니다.

Raft 는 서버가 멈추거나 메시지가 늦는 고장만 견딥니다. 서버가 거짓 메시지를 보내는 고장은 못 견딥니다. 그런 고장을 비잔틴 장애라고 부릅니다. 그것까지 견디려면 다른 절차가 필요합니다.

이런 성질 때문에 Raft 는 크기는 작고 틀리면 안 되는 데이터에 씁니다. 클러스터 설정, 누가 리더인지 같은 메타데이터, 분산 잠금이 그런 데이터입니다. 대량의 사용자 데이터에는 데이터를 여러 조각으로 나눕니다. 그리고 조각마다 Raft 클러스터를 따로 둡니다.

Paxos 와의 차이

Paxos 는 Raft 보다 먼저 나온 합의 규칙입니다. 둘은 같은 문제를 풉니다. 견디는 고장도 같습니다.

갈리는 곳은 짜임새입니다. Raft 는 이해하기 쉬운 것을 목표로 설계됐습니다. 그래서 문제를 리더 선출, 로그 복제, 안전성 셋으로 나눠 따로 설명합니다. 리더를 강하게 두어 로그가 리더에서 팔로워 쪽으로만 흐르게 한 것도 같은 목표에서 나왔습니다.

Paxos 는 값 하나를 정하는 절차에서 출발합니다. 로그 전체를 맞추려면 그 절차를 여러 번 겹쳐 써야 합니다. 겹쳐 쓰는 방법은 구현마다 갈립니다.

관련 항목

Raft 가 푸는 문제와 그 틀

합의 · 합의 알고리즘 · 복제 상태 기계 · 복제 로그 · 복제 · 분산 시스템

Raft 를 이루는 구성 요소

리더 · 팔로워 · 임기 · 로그 · 커밋 · 하트비트 · 선거 시한 · RPC

Raft 가 거치는 처리 단계

리더 선출 · 로그 복제 · 스냅샷 · 로그 압축 · 멤버십 변경

Raft 가 기대는 성질과 규칙

과반 · 정족수 · 안전성 · 진행성 · 선형화 가능성 · CAP

Raft 가 막는 장애

분단 · 스플릿 브레인 · 단일 장애점 · 고가용성 · 비잔틴 장애

Raft 와 같은 문제를 두고 겨루는 합의 규칙

Paxos · Multi-Paxos · Zab · Viewstamped Replication · PBFT

Raft 를 채택한 제품

etcd · Consul · CockroachDB · TiKV · Kafka KRaft

다른 이름: Raft 합의 알고리즘 · 래프트