Alopex Chirps とは何か ― 分散システムのクラスタを組むためのライブラリと、採用したコンセンサス

分散データベースを作ると、本題に入る前に同じものを毎回作ることになる。ノードを見つける仕組み、相手が生きているかを判断する仕組み、ノード間でメッセージを運ぶ仕組み、そして誰が何を決めたのかを確定させる仕組みである。分散ランタイムでもサービスメッシュでもエッジクラスタでも、この四つは形を変えて現れる。

Alopex Chirps は、この四つだけを引き受けるライブラリである。Apache-2.0 OR MIT のもと crates.io で公開している。

このブログでは「コンセンサスアルゴリズム・アンダーグラウンド」という全4回の連載で、コンセンサスアルゴリズムを故障モデルと実装構造の観点から整理した。今回はその視点で、Chirps が何を引き受け、どの合意を採用しているのかを説明する。連載の各回へのリンクは記事末尾にまとめてある。

何を担い、何を担わないか

Chirps が提供するのはコントロールプレーンである。データそのものは扱わない。

担うのは次の範囲である。

• ノード識別（永続的な node_id）とシードリスト経由のクラスタ参加
• SWIM 方式のゴシップによるメンバーシップ伝播
• QUIC/TLS 上のメッセージング（send_to / broadcast / subscribe）
• Raft による順序決定と確定
• 参加・離脱・状態変化のイベント通知

担わないのは、ストレージエンジン、クエリ処理、スケジューリング、そして状態機械の中身である。何をどう適用するかは利用側が決める。

分散データベースの下に敷くこともできるし、分散ランタイムやサービスメッシュ、エッジ／IoTクラスタの制御面として使うこともできる。

三つの層が、それぞれ別の問いに答える

Chirps の内部は三層に分かれている。この分離が設計の中心である。

コンセンサスアルゴリズム・アンダーグラウンド第1回で、リーダー選出・順序決定・確定は別の問題だと整理した。Chirps ではそれがクレートの境界そのものになっている。chirps-transport-quic、chirps-gossip-swim、chirps-raft-storage と raft モジュールが、上の三行に対応する。

重要なのは三行目の性質の違いである。SWIM が返すのは推定であり、Raft が返すのは決定である。この二つを取り違えると、ゴシップの誤判定がそのまま履歴の分岐になる。

なぜ QUIC なのか

QUIC は UDP の上に作られたトランスポートである。TCP が担っていた再送・順序保証と、TLS による暗号化と、複数ストリームの多重化を一つにまとめている。Chirps は Rust 実装の quinn を使い、ノードごとに一つの UDP エンドポイントを開いて全ピアと通信する。

採用の理由は二つある。

一つは、ストリームが互いに独立していることである。QUIC は1本の接続の中に複数のストリームを持ち、ストリーム間ではヘッドオブラインブロッキングが起きない。TCP では1本の接続上でパケットが1つ失われると、その後ろに並んでいるデータはすべて待たされる。Chirps は同じ接続の上に合意メッセージ、ゴシップ、スナップショット転送、アプリケーションメッセージを同居させるため、この性質が前提になる。大きなスナップショット転送の途中で失われた1パケットが、Raft のハートビートを止めてはならない。実装ではメッセージごとに単方向ストリームを開き、種別ごとに優先度を割り当てている。

もう一つは、暗号化が前提になっていることである。QUIC は TLS を組み込んでおり、平文の接続という選択肢がない。Chirps は rustls を用い、ALPN に alopex を指定して接続を識別する。ノード間通信に後から TLS を敷く設計を持たずに済む。

合意には openraft を使う

採用したのは openraft の v0.9.17 である。Cargo.toml では openraft = { version = "=0.9.17", features = ["serde"] } と等号でピン留めしている。

コンセンサスアルゴリズム・アンダーグラウンド第2回で整理したとおり、本番の Raft 実装の大半は論文の外側にある。永続化順序、バッチング、backpressure、スナップショット、メンバーシップ変更、線形化読み取り。Chirps で自作しているのはストレージとトランスポートであり、合意そのものではない。

つまり Chirps の役割は、クラスタを組んで、そこに順序と確定を持たせることにある。ノードを繋いで、生死を追い、決めたことを失わせない。この四つが必要になった時点で依存に加える部品であり、アルゴリズムを選ぶために読むものではない。

ゴシップの推定を、合意へ持ち込まない

Chirps には二つのメンバーシップがある。これを混同しないことが、層を分けた実際の理由である。

一つは SWIM ゴシップのメンバーシップである。alive / suspect / dead の状態と incarnation 番号を持ち、ping、間接 ping、タイムアウトで遷移する。

PING B
  ↓ 応答なし
PING-REQ B（C, D 経由）
  ↓ 応答なし
B を suspect
  ↓ suspect_to_dead_timeout
B を dead

もう一つは Raft のメンバーシップ、すなわち投票者集合である。こちらは change_membership で変更し、openraft の joint consensus を経由する。

leader.add_learner(4, BasicNode::default()).await?;
leader.change_membership(BTreeSet::from([1, 2, 4])).await?;

コンセンサスアルゴリズム・アンダーグラウンド第1回で確認したとおり、停止と遅延は区別できない。したがってゴシップが dead と判断したことは、そのノードを投票者集合から外してよいという意味にはならない。SWIM の状態変化はイベントとして利用側へ通知され、投票者集合の変更は別の経路で明示的に行われる。

障害検知とメンバーシップ拡散はコンセンサスではない。コンセンサスアルゴリズム・アンダーグラウンド第4回で並べたこの区別が、Chirps では層の境界として実装されている。

合意の器は提供し、意味は利用側が決める

Chirps は状態機械を持たない。利用側が StateMachine を実装して渡す。

#[async_trait]
impl StateMachine for KvStateMachine {
    type Command = Vec<u8>;
    type Response = Vec<u8>;

    async fn apply(&mut self, log_id: LogId<u64>, command: Self::Command)
        -> StateMachineResult<Self::Response> { /* 状態を更新する */ }

    async fn snapshot(&self) -> StateMachineResult<Box<dyn AsyncSnapshotData>> { /* ... */ }
    async fn restore(&mut self, snapshot: Box<dyn AsyncSnapshotData>) -> StateMachineResult<()> { /* ... */ }
}

コマンドもレスポンスも Vec<u8> である。Chirps はバイト列の順序と確定だけを保証し、その中身を解釈しない。KVストアを載せるか、ジョブキューを載せるか、設定配布を載せるかは利用側の問題になる。

ログの置き場所は Chirps が持つ。WalRaftStorage が openraft のストレージ抽象を実装し、実体は alopex-core 0.3 の WAL プリミティブの上に載っている。書かれるレコードは5種類である。

pub enum RaftWalRecord {
    AppendLog(Entry<ChirpsTypeConfig>),
    Vote(Vote<ChirpsNodeId>),
    SnapshotApplied(SnapshotMeta<ChirpsNodeId, BasicNode>),
    Truncate(LogId<ChirpsNodeId>),
    Purge(LogId<ChirpsNodeId>),
}

コンセンサスアルゴリズム・アンダーグラウンド第1回で整理した「ログへの追加・コミット・適用は別の事象である」という区別が、レコード種別として現れている。ファイル先頭には "RWAL" のマジック、フォーマットバージョン、group_id、node_id を持つヘッダを置く。スナップショットは "SNAP" のマジックを持ち、チャンクごとに CRC32 を付ける。検査の単位はファイルではなくチャンクである。

投票の永続化には設定を用意していない。save_vote は例外なく同期書き込みを行う。

self.write_frame(&WalFrame::Record(RaftWalRecord::Vote(*vote)), true)

一方、ログ追記は WalStorageConfig::fsync_interval で調整できる。既定値の 0 はエントリごとの fsync を意味し、0 より大きい値を設定すると、その件数ごとにまとめて fsync する。投票は設定不能で常に同期、ログ追記は設定可能、既定は安全側という構成である。

一本の接続に、四種類のトラフィックが同居する

コントロールプレーンを一つのライブラリにまとめた結果、同じ QUIC 接続の上を性質の違うトラフィックが流れる。合意メッセージ、ゴシップ、スナップショット転送、そして利用側のアプリケーションメッセージである。

そこでストリーム種別ごとに優先度を割り当てている。

同じ Raft 由来でも、Raft は High、RaftSnapshot は Normal と別扱いになっている。コンセンサスアルゴリズム・アンダーグラウンド第2回で挙げた「スナップショット転送によるI/O飽和」は、新規ノードの追い付き処理がハートビートを押しのけ、無関係なリーダー選挙を誘発する形で現れる。

プロファイルについても実行時の強制がある。

if is_raft_frame(frame) && matches!(requested, MessageProfile::Ephemeral) {
    warn!("Ephemeral requested for Raft traffic; overriding to Control");
    return Ok(MessageProfile::Control);
}

Raft フレームを再送なしのベストエフォート経路へ流す指定は、警告を出したうえで信頼経路へ戻される。利用側のアプリケーションメッセージと同じAPIを共有しているからこそ、この強制が必要になる。

利用側から見た使い方

トランスポートは既存のものをそのまま使う。ChirpsRaftTransport が openraft の RaftNetwork / RaftNetworkFactory を実装し、Chirps の MessageBackend へ委譲するため、合意層が独自のソケットを持つことはない。

leader.initialize(BTreeSet::from([1, 2, 3])).await?;
let response = leader.propose(b"hello".to_vec()).await?;
leader.trigger_snapshot().await?;

propose はリーダーでない場合に自動転送せず、NotLeader とリーダーIDを返す。呼び出し側でリダイレクトする方式である。

タイミングの既定値は LAN を前提にしている。選挙タイムアウト 150ms、ハートビート 50ms、AppendEntries の最大バッチ 1,000件、スナップショットしきい値 10,000エントリ。コンセンサスアルゴリズム・アンダーグラウンド第1回で触れたとおり、これらの数値は部分同期の仮定そのものであり、RTT の大きい環境では引き上げる必要がある。

運用面では、Prometheus メトリクス（raft_state、raft_term、raft_commit_index、raft_applied_index、raft_leader_id ほか）と、target="raft" の構造化ログイベントを出している。コンセンサスアルゴリズム・アンダーグラウンド第1回で分けた「コミット」と「適用」はメトリクスでも別系列であり、両者の差が開き続けている状態は状態機械側の詰まりを意味する。

いま提供している範囲と、これから積むもの

読み取り経路は propose に一本化されている。is_leader() はメトリクスの current_leader を参照するだけなので、分断後の古いリーダーを判別する用途には使えない。コンセンサスアルゴリズム・アンダーグラウンド第2回で挙げた ReadIndex やリーダーリースに相当する線形化読み取りは、今後の実装となる。

RaftNode が扱うのは単一グループである。GroupId は WAL のパスと受信フレームの検査に使われ、グループIDが一致しないメッセージは拒否される。識別と経路の分離はすでに入っているので、コンセンサスアルゴリズム・アンダーグラウンド第2回で扱った Multi-Raft、すなわち範囲ごとに Raft グループを走らせる形は、この上に積む次の実装となる。分散データベースの下敷きとして使うなら、ここが本命になる。

MessageProfile は Control と Ephemeral が動作する。Durable はスタブで、要求されると警告を出してエラーを返す。永続キューを伴う配送として今後実装する。

まとめ

• Chirps は分散システムのコントロールプレーンだけを引き受ける部品である。ノード発見、メンバーシップ、メッセージング、合意を担い、ストレージや状態機械の中身は担わない。
• 内部は QUIC（誰と繋ぐか）、SWIM（誰が生きていそうか）、Raft（何を正史とするか）の三層に分かれる。答の性質が推定と決定で異なるため、層を分けている。
• 合意には openraft v0.9.17 を採用し、自作しているのはストレージとトランスポートである。
• ゴシップの dead は投票者集合の変更を意味しない。投票者集合は change_membership で明示的に変更する。
• 状態機械は利用側が実装する。Chirps はバイト列の順序と確定を保証し、中身を解釈しない。
• 一本の接続に合意・ゴシップ・スナップショット・アプリケーションが同居するため、ストリーム優先度とプロファイル強制で経路を分けている。
• 線形化読み取り、Multi-Raft、Durable プロファイルは今後の実装となる。

連載「コンセンサスアルゴリズム・アンダーグラウンド」

本記事で参照した全4回の連載は次のとおり。

• コンセンサスアルゴリズム・アンダーグラウンド【第1回】 ― 停止と遅延は区別できない
• コンセンサスアルゴリズム・アンダーグラウンド【第2回】 ― クラッシュ故障の系譜、PaxosとRaft
• コンセンサスアルゴリズム・アンダーグラウンド【第3回】 ― 嘘をつくノード、PBFTからDAG-BFTへ
• コンセンサスアルゴリズム・アンダーグラウンド【第4回】 ― 身元を数えられない世界、PoWとPoS