Skip to content
Published on

etcdアーキテクチャ内部分析: Raft合意アルゴリズム

🇰🇷KO🇺🇸EN🇯🇵JA
Split View
Authors

etcdアーキテクチャ内部分析: Raft合意アルゴリズム

etcdは分散システムで重要な役割を果たす強い一貫性（strongly consistent）を保証する分散キーバリューストアです。Kubernetesのすべてのクラスター状態がetcdに保存され、その信頼性はRaft合意アルゴリズムに基づいています。

1. Raft合意アルゴリズム概要

Raftは理解しやすく設計された合意アルゴリズムで、Paxosと同等の安全性を提供しながら実装が遥かにシンプルです。

1.1 コア概念

Raftの核心は3つのサブ問題に分解されます:

  • リーダー選出（Leader Election）: クラスターで1つのリーダーを選出
  • ログ複製（Log Replication）: リーダーがログエントリをフォロワーに複製
  • 安全性（Safety）: コミットされたエントリが失われないことを保証

1.2 ノード状態

Raftクラスターの各ノードは3つの状態のいずれかです:

  • Leader: クライアントリクエストを処理しログを複製
  • Follower: リーダーのリクエストに応答する受動的役割
  • Candidate: リーダー選出に参加する中間状態

1.3 Term（任期）

Raftは時間をTermという論理的単位に分割します。各Termは選出で始まり、選出に成功すればそのTerm中に1つのリーダーが存在します。Termは単調増加し、古いTermのメッセージは無視されます。

2. リーダー選出（Leader Election）詳細

2.1 選出過程

  1. Followerが一定時間（election timeout）リーダーからheartbeatを受信しなければCandidateに転換
  2. Candidateは現在のTermを増加させ自分に投票した後、他のノードにRequestVote RPCを送信
  3. 過半数（majority）の投票を得ればリーダーに選出
  4. リーダーになったら直ちに空のheartbeatを送信して権限を確立

2.2 選出タイムアウト

選出タイムアウトはランダム化されており、同時に複数のノードがCandidateになることを防止します。etcdではデフォルトで1000〜1500msの範囲です。

2.3 Pre-Voteメカニズム

etcdはネットワークパーティション復旧後の不要なリーダー交代を防止するためPre-Voteを実装しています。Candidateになる前にまずPre-Voteを要求し、過半数が同意した場合のみ実際の選出を開始します。

// etcdのraft状態遷移（簡略化）
// Follower -> PreCandidate -> Candidate -> Leader

func (r *raft) tickElection() {
    r.electionElapsed++
    if r.electionElapsed >= r.randomizedElectionTimeout {
        r.electionElapsed = 0
        r.Step(pb.Message{Type: pb.MsgHup})
    }
}

2.4 Learnerノード

etcd 3.4からLearnerノードが導入されました。Learnerは投票権のない非投票メンバーで、ログ複製のみ受信します。新メンバーが既存ログに追いつくまでLearnerとして維持するとクラスター可用性に影響を与えません。

3. ログ複製（Log Replication）

3.1 ログエントリ構造

各ログエントリは以下を含みます:

  • Index: ログ内の位置（単調増加）
  • Term: そのエントリが生成されたTerm
  • Data: ステートマシンに適用するコマンド（例: Put key=value）

3.2 複製過程

  1. クライアントがリーダーにリクエスト送信
  2. リーダーがログエントリを自身のログに追加
  3. リーダーがAppendEntries RPCでフォロワーに複製
  4. 過半数のフォロワーが確認（acknowledge）するとコミット
  5. コミットされたエントリをステートマシンに適用（apply）
  6. クライアントにレスポンス返却

3.3 ログ一貫性保証

Raftは2つの属性でログ一貫性を保証します:

  • Log Matching: 同じindexとtermを持つ2つのエントリは同じコマンドを格納
  • Leader Completeness: コミットされたエントリはその後のすべてのリーダーのログに存在
Leader Log:  [1:1][2:1][3:2][4:2][5:3]
                                  ^-- committed up to here

Follower A:  [1:1][2:1][3:2][4:2][5:3]  (up to date)
Follower B:  [1:1][2:1][3:2]            (lagging, will catch up)

4. etcdサーバーアーキテクチャ

4.1 EtcdServer構造

EtcdServerはetcdのコア構造体で、以下のコンポーネントを調整します:

  • RaftNode: Raft合意ロジック処理
  • Backend: BoltDBベースストレージ
  • KV Store: MVCCキーバリューストア
  • Lessor: Lease管理
  • Watchable Store: Watchメカニズム

4.2 リクエスト処理フロー

クライアントのPutリクエストが処理される過程:

  1. gRPCサーバーがリクエスト受信
  2. 認証と権限確認
  3. リクエストをRaftに提案（propose）
  4. Raft合意後コミット
  5. Applyループでコミットされたエントリをステートマシンに適用
  6. バックエンド（BoltDB）に永続化
  7. クライアントにレスポンス返却

4.3 Applyループ

ApplyループはetcdのコアループでRaftでコミットされたエントリを順番にステートマシンに適用します:

// Applyループの簡略化された構造
func (s *EtcdServer) applyAll(ep *etcdProgress, apply *apply) {
    s.applySnapshot(ep, apply)
    s.applyEntries(ep, apply)
    // 適用完了後インデックス更新
    s.setAppliedIndex(apply.snapshot.Metadata.Index)
}

4.4 Linearizable Read

etcdはデフォルトでLinearizable Readをサポートします。読み取りリクエスト時にリーダーがまだ現在のリーダーであるか確認するため過半数にheartbeatを送信します。これによりstale readを防止します。

Serializable Readオプションを使用するとリーダー確認なしでローカルから読み取り、パフォーマンスは良いですが最新データでない可能性があります。

5. キーバリューストア: BoltDBとMVCC

5.1 BoltDB（bbolt）バックエンド

etcdはBoltDB（bboltフォーク）をバックエンドストレージとして使用します。BoltDBはB+ツリーベースの組み込みキーバリューデータベースで:

  • 読み取り最適化されたB+ツリー構造
  • ページ単位ストレージ（4KBデフォルト）
  • ACIDトランザクションサポート
  • 単一writer、複数readerモデル

5.2 MVCC（Multi-Version Concurrency Control）

etcdはMVCCを使用してキーのすべてのバージョンを維持します:

  • Revision: グローバル単調増加カウンター。すべてのトランザクションごとに増加
  • Key Index: キー名からrevisionリストへのマッピング
  • Generation: キーの作成から削除までのライフサイクル
Key: "/app/config"
  Generation 1: [create:rev5] [modify:rev8] [modify:rev12] [tombstone:rev15]
  Generation 2: [create:rev20] [modify:rev25]
                                              ^-- current

5.3 BoltDB内部バケット構造

etcdはBoltDBに2つの主要バケットを維持します:

  • keyバケット: revisionをキーとし実際のキーバリューデータを値として格納
  • metaバケット: メタデータ（consistent index、scheduled compact revisionなど）

6. Watchメカニズム

6.1 Watchable Store

etcdのWatchはキーまたはキー範囲の変更をリアルタイムでストリーミングします:

  • synced watchers: 現在のrevisionまで追いついたwatcher。新イベントを即座に受信
  • unsynced watchers: まだ追いついていないwatcher。ヒストリーからイベントを再生

6.2 イベント生成

MVCCストアに書き込み操作が発生すると:

  1. トランザクションがコミットされる時にイベント生成
  2. watchable storeがイベントを該当watcherに配信
  3. gRPCストリームを通じてクライアントに送信

6.3 Watchリカバリ

クライアントが接続切断後に再接続する際、最後に受信したrevisionからWatchを再開できます。そのrevisionが既にコンパクションされていればエラーが返され、クライアントは全データを再ロードする必要があります。

7. ネットワークとgRPC通信

7.1 ピア間通信

etcdクラスターメンバー間の通信は2つのチャネルを使用します:

  • Stream: 長期接続でRaftメッセージ（heartbeat、append entriesなど）を送信
  • Pipeline: 大容量データ（スナップショットなど）転送

7.2 クライアント通信

クライアントはgRPCを通じてetcdと通信します。主要サービス:

  • KV: Put, Range, DeleteRange, Txn
  • Watch: Watch
  • Lease: LeaseGrant, LeaseRevoke, LeaseKeepAlive
  • Cluster: MemberAdd, MemberRemove, MemberList
  • Maintenance: Alarm, Status, Defragment, Snapshot

8. まとめ

etcdのアーキテクチャはRaft合意アルゴリズムを基盤に強い一貫性を保証しながら、BoltDBの効率的なストレージとMVCCの多バージョン管理により高いパフォーマンスを達成しています。次の記事ではBoltDBとMVCCストレージエンジンの内部構造をより深く見ていきます。

Discuss on Twitter • View on GitHub