> [!abstract] 概要(TPDS abstract の日本語訳) > 合意プロトコルは分散システムにおけるフォールトトレランスに不可欠であり、上位システムの性能と可用性に大きく影響する。近年の研究は、Remote Direct Memory Access(RDMA)の優れた性能と one-sided primitive を活用して合意プロトコルを高速化してきた。性能面を超えて、RDMA のプロセッサバイパス特性は、プロセッサが故障してもサーバがネットワーク要求を処理し続けることを可能にし、細粒度の障害モデルを実現する。この細粒度障害モデルは、伝統的にプロセッサ障害をサーバ全体のクラッシュとみなしてきた既存の合意プロトコルの可用性を高めうる。本論文では、この細粒度障害モデルに完全に適応した初の RDMA ベース合意プロトコルである R2aft(RDMA+Raft)を導入する。可用性の利点を超えて、R2aft は RDMA の高性能を活かすための特定の最適化も統合する。YCSB ワークロードを用いて、R2aft が最先端の RDMA ベース合意プロトコルである Mu と同等のスループットを維持しつつ、わずか 12.2% のレイテンシオーバーヘッドしか生じないことを示す。 ## 論文情報 - タイトル: R2aft: A Speedy and Highly Available RDMA-Based Consensus Protocol - 著者: Zhiyuan Dong, Haitao Song, Zhaoguo Wang(Member, IEEE) - 所属: [[Shanghai Jiao Tong University]] Institute of Parallel and Distributed Systems(Zhiyuan Dong, Zhaoguo Wang)、Shanghai Artificial Intelligence Research Institute, Shanghai Jiao Tong University(Haitao Song)。責任著者は Zhaoguo Wang。 - 媒体: IEEE Transactions on Parallel and Distributed Systems(TPDS), Vol. 37, No. 7, July 2026 - 発表年: 受理 2026-03-26、公開 2026-04-03、掲載号 2026-05-14 - DOI: 10.1109/TPDS.2026.3679987 - 投稿履歴: 初回投稿 2022-04-10、改訂 2024-09-07、受理 2026-03-26(査読期間が約 4 年に及ぶ) - コード URL: 記載なし ## 概要 分散システムの合意プロトコルは通常、いずれかのコンポーネント(プロセッサ・メモリ・NIC)の 1 つが故障するとサーバ全体の故障として扱う「粗粒度障害モデル」を前提にする。本論文は、RDMA のプロセッサバイパス特性によりプロセッサ障害とサーバ障害を切り離せることに着目し、その「細粒度障害モデル」をリーダー選出とログ複製の両方に適用した Raft 派生の合意プロトコル R2aft を提案する。Single Writer Multiple Reader のメモリ領域設計と Write-Read-Verify の処理順序により、リモートプロセッサを完全にバイパスしながら正しさを保証し、YCSB ベンチマークで既存 RDMA ベース合意プロトコルと同等の性能を達成する。 ## 問題設定 - **入力**: 分散システムを構成する N = 2F + 1 台のサーバ群。各サーバは処理系(プロセッサ)と RDMA コンポーネント(メモリ・RNIC)を持つ。 - **出力**: サーバ間で一貫した合意ログ(commit された命令列)と、その命令をキーバリューストアなどの状態機械へ適用した結果。 - **前提条件**: - 各サーバの RDMA アクセス可能領域は不揮発性メモリまたはバッテリバックアップメモリで永続化される。 - RDMA 接続の確立とアクセス許可の管理(reconfiguration 時)には現行の RDMA 仕様上どうしてもリモートプロセッサが必要(脚注 1)。 - x86 ISA の 8 バイトアラインアクセスはアトミック(AMD post 世代・Intel P6 後継で保証)である前提を利用し、メタデータをアトミックに read/write できるようにパックする。 - **必要なデータ**: 各サーバ上の合意ログ(circular buffer)と、リーダー選出・ログ複製に使うメタデータ(`cur_term`・`last_term`・`last_index`・`commit_index` など)。 ## 提案手法 - **アーキテクチャ**: Fig. 2 に示すとおり、各サーバのプロセッサはリーダー選出・ログ複製のロジックのみを担い、実際のリモートアクセスは RNIC 経由の RDMA one-sided primitive(READ/WRITE)で行う。ローカル領域へは CPU load/store でアクセスし、RDMA のキャッシュ一貫性保証により local/remote アクセスの混在が正当性を損なわない。 ![[_attachments/R2aft_A_Speedy_and_Highly_Available_RDMA-Based_Consensus_Protocol/fig02-r2aft-overview.png]] (Figure 2. R2aft を用いた分散システムの全体像。クライアントは上位システムへ提案を送り、上位システムの R2aft ライブラリ(Leader/Candidate)がプロセッサ経由でローカルメモリを CPU load/store により更新し、RNIC 経由の RDMA one-sided primitive でリモートサーバの Log/Metadata 領域へ書き込む。リモート側の Processor は DMA で反映された内容を CPU load/store で読み出すのみで、複製処理自体には関与しない。Source: Fig. 2, R2aft 論文。) - **アルゴリズム/手法の詳細**: - **Single Writer Multiple Reader Region**: R2aft は各サーバのメモリを N 個(N = コンセンサスグループのサーバ数)の非重複領域に分割し、1 領域につき書き込み可能なサーバを 1 台に限定する(Algorithm 1・Fig. 3)。全サーバが同一領域へ書けない設計により、古いリーダーが他サーバの領域を直接上書きしてリーダー選出・ログ複製を破壊する経路を構造的に排除する。 ![[_attachments/R2aft_A_Speedy_and_Highly_Available_RDMA-Based_Consensus_Protocol/fig03-data-layout.png]] (Figure 3. R2aft の詳細データレイアウト。各サーバは自身が書き込み可能な論理領域(S0/S1/.../Sn Writable Logical Region)を N 個保持する。各領域内で `cur_term`・`last_term`・`last_index` はリーダー選出用に 8 バイトアラインでパックされアトミックアクセス可能にし、`head_index`・`apply_index`・`commit_index` はログの circular buffer 管理に使われる。Source: Fig. 3, R2aft 論文。) - **Write-Read-Verify アプローチ**: 既存の合意プロトコルが用いる「Read-Verify-Write」ではリモートプロセッサによる同期がない環境で競合状態が発生しうる(Fig. 1 の反例: stale リーダー S0 が新リーダー S2 による commit 後に古い cmd0 で S1 のログを上書きしてしまう)。R2aft はこれを「Write-Read-Verify」に並べ替える: (1) 自身の領域へ先に書き込み、(2) 他サーバの領域を読み、(3) 自分の更新が成功したかを検証する。2 台のサーバが競合する合意操作を同時に発行しても、少なくとも一方は相手の更新を観測して検証に失敗するため、同一インデックスに対して複数の操作が成功することはない。 ![[_attachments/R2aft_A_Speedy_and_Highly_Available_RDMA-Based_Consensus_Protocol/fig01-strawman-counterexample.png]] (Figure 1. strawman アプローチ(Raft の全データアクセスを単純に RDMA one-sided primitive へ置き換えるだけの素朴な設計)が引き起こす不整合の反例。term 0 のリーダー S0 が S1 の term 検証に通過した直後に停止(Stalled)し、その間に term 1 の新リーダー S2 が cmd1 を委譲・commit する。停止から復帰した S0 は cmd1 を上書きして古い cmd0 を commit してしまい、同一ログインデックスに 2 つの異なる命令が commit される。Source: Fig. 1, R2aft 論文。) - **リーダー選出(Algorithm 2・3)**: 候補者はまず全ローカル領域の `cur_term` の最大値から新しい term を計算し、自領域の `cur_term` を更新したうえで、各リモートサーバへ RDMA WRITE で自分の term を書き込み、RDMA READ で相手の `elect_info_t` 全体(term と log 情報)を 1 回の RDMA READ で取得する(`elect_info_t` を連続配置しているため)。`latterThan` により最新ログを判定し、リモート側の term が自分より低く、かつリモート側の最新ログが自分より新しくなければ 1 票を獲得する。過半数(quorum)を得た候補者はリーダーとなり、`syncLog` で最新ログを自分のログへコピーし、`next_index` を再計算する。 - **ログ複製(Algorithm 4)**: リーダーは新しいログエントリをローカルに追記した後、各フォロワーに対して 1 回の RDMA WRITE でログエントリ本体を、もう 1 回の RDMA WRITE で `log_info`(term・index)を送り、最後に RDMA READ でフォロワーの `cur_term` 全体を検証用に読み出す。この 3 つの one-sided primitive は同一 RDMA コネクションの FIFO 順序保証により 1 回のネットワークラウンドトリップにまとめられる。読み出した term が自分の term 以下であれば複製成功とみなし、過半数の成功で commit する。 - **実装上の工夫**: - RDMA コネクションの FIFO 順序保証を利用し、複数の READ/WRITE を 1 ラウンドトリップに束ねる(Dare の 2 ラウンドトリップに対する優位性の源泉)。 - リーダー選出のメタデータ(`cur_term` の配列と `log_info` の配列)を連続配置し、1 回の RDMA READ で全て取得できるようにする。 - `last_term`/`last_index` を 8 バイトにパックし、x86 の 8 バイトアラインアクセスのアトミック性を利用して RDMA READ/WRITE と CPU load/store の両方から矛盾なくアトミックに読める設計にする。 - リーダー選出の再試行が頻発しないよう、タイムアウトに指数バックオフを適用する。 - ログは固定サイズの circular buffer とし、`apply_index` の最小値をもとに `head_index` を更新する pruning entry を用いてリクレームする。 - Reconfiguration は Raft ライクな 2 フェーズ(old → transitional → new)方式を採用し、異なる configuration から 2 人のリーダーが選出されることを防ぐ。ただし RDMA のアクセス制御(コネクションのクローズ・パーミッション設定)自体はリモートプロセッサに依存せざるを得ない(脚注 1 の制約)。 ## 新規性 - 既存の RDMA ベース合意プロトコル(Dare・Sift・Protected Memory Paxos・Mu)は、いずれもログ複製ではリモートプロセッサを完全にバイパスする一方、リーダー選出(古いリーダーからの RDMA アクセス権限剥奪など)ではリモートプロセッサに依存しており、「細粒度障害モデル」をログ複製にしか適用できていなかった。R2aft はリーダー選出とログ複製の両方でリモートプロセッサを完全にバイパスした初の RDMA ベース合意プロトコルである。 - Dare・Sift は stale リーダーの RDMA コネクションを閉じることで対処し、Aguilera らはメモリ領域の read/write パーミッションを操作して対処するが、いずれもリモートプロセッサの介在を要する。R2aft は Single Writer Multiple Reader Region という構造的制約(誰も他人の領域を書けない)によって、プロセッサの介入なしに同じ問題を解決する。 - Disk Paxos(ストレージエリアネットワークで個々のディスクを独立故障単位とする)からアイデアを借用しつつも、R2aft は N 個のサーバの RDMA コンポーネントとプロセッサをそれぞれ独立の故障単位として扱い、2F + 1 サーバで F 個の RDMA コンポーネント故障と 2F 個のプロセッサ故障を許容する、より一般の分散合意問題に適用する。 ## 実験設定 - **実験環境**: 9 台構成のクラスタ、Mellanox SB7890 100 Gbps InfiniBand スイッチ。各マシンは 12 コア Intel Xeon E5-2650 v4 を 2 基、ConnectX-4 MCX455A 100 Gbps InfiniBand RNIC を 2 基搭載。 - **比較対象**: RPC ベース Raft(Etcd 相当、RDMA two-sided primitive によるカスタム RPC 実装)、Dare のエミュレーション版(2 ラウンドトリップの RDMA WRITE)、Mu のエミュレーション版(canary byte による 1 ラウンドトリップ RDMA WRITE)。いずれも R2aft と同一コードベース・同一インタフェース・同一データ構造(RDMA accessible circular buffer)で公平比較。 - **アプリケーション**: 分散パーティション化キーバリューストア。各サーバはワーカースレッドごとに独立したシャードを担当し、各ワーカースレッドが 1 つの合意プロトコルインスタンスを実行する。 - **評価指標**: YCSB ベンチマークの YCSB-A(50% 書き込み)、YCSB-B(95% 読み取り)、および 100% 書き込みの「update-only」ワークロード。ログエントリサイズは 64 バイトと 1024 バイトを比較。レイテンシは操作生成からインデクシングデータ構造への適用完了までを測定し、90 パーセンタイルを主指標、50/99 パーセンタイルをエラーバーで表示。すべての結果は 5 回実行の平均。 ## 実験結果 - **レイテンシ(Fig. 5、5 サーバ、100% 書き込み)**: R2aft は Dare に対し最大 14.9% のレイテンシ削減を達成した(Dare は 1 サーバあたり 2 つの one-sided primitive を使うが 2 ラウンドトリップを要するため)。Mu は 1 つの one-sided primitive・1 ラウンドトリップのみでレイテンシが最良となり、R2aft は Mu に対し約 12.2% 高いレイテンシとなった。RPC ベース Raft は two-sided primitive の追加データ転送オーバーヘッドにより両ログサイズで最も高いレイテンシを示した。 ![[_attachments/R2aft_A_Speedy_and_Highly_Available_RDMA-Based_Consensus_Protocol/fig05-latency-comparison.png]] (Figure 5. 5 サーバ構成・100% 書き込みワークロードでのレイテンシ比較。ログエントリサイズ 64 バイトと 1024 バイトの両方で、Mu が最良、次いで R2aft・Dare、RPC ベース Raft が最も高いレイテンシを示す。縦軸ラベルは論文原文どおり "Read Latency" と表記されているが、本文の記述(100% 書き込みワークロードでの測定)と整合しない可能性がある点に注意。Source: Fig. 5, R2aft 論文。) - **スループット(Fig. 6、1024 バイトログエントリ)**: 100% 書き込みワークロードでは、RPC ベース Raft は Unreliable Datagram の最大転送単位 4KB の制約により 3 サーバ構成で最も低いスループットを示し、サーバ数が 3 を超えるとネットワーク帯域がボトルネックとなった。Dare・Mu・R2aft は one-sided primitive によりこの制約を受けず、より高いスループットを達成。サーバ数が 3 を超えると、いずれのプロトコルもネットワーク帯域に制約される。YCSB-A(50% 書き込み)では傾向は概ね同様だが、必要な複製ログ数の減少に伴いボトルネックがリーダーのプロセッサ側へ移りつつある。YCSB-B(5% 書き込み)では読み取りがバッチ化されたリーダー検証で処理されるため、リーダーのプロセッサが常時ボトルネックとなり、4 プロトコル間のスループット差はごく小さい。 ![[_attachments/R2aft_A_Speedy_and_Highly_Available_RDMA-Based_Consensus_Protocol/fig06-throughput-1024b.png]] (Figure 6. 1024 バイトログエントリでの書き込み比率別スループット。(a) 100% 書き込み、(b) 50% 書き込み(YCSB-A)、(c) 5% 書き込み(YCSB-B)。書き込み比率が下がるほど 4 プロトコル間のスループット差が縮小する。Source: Fig. 6, R2aft 論文。) - **クライアント負荷可変時(Fig. 8、5 サーバ・100% 書き込み)**: 1024 バイトログエントリではネットワーク帯域がボトルネックとなるため、全プロトコルがおよそ 96 クライアントでピークスループットに達し差は小さい。64 バイトログエントリでは one-sided primitive を使うプロトコル(R2aft・Mu・Dare)がリーダーの処理能力をフル活用でき、クライアント数 3072 でピークスループットに達するのに対し、two-sided primitive 制約を受ける Raft はクライアント数 384 でピークとなる。 - **故障回復と再構成(Fig. 9、3 サーバ・64 バイトログエントリ)**: S1 がリーダーである状態から開始し、2 秒目に S1 のサーバ全体が故障すると約 20ms 不可用となり、S2 が新リーダーに選出される。4 秒目に S2 の「プロセッサのみ」が故障すると、粗粒度障害モデルに基づく Raft・Dare・Mu は 3 サーバ中 2 故障を許容できず完全に停止するのに対し、細粒度障害モデルを持つ R2aft はリクエスト処理を継続できる。唯一残った S3 が約 30ms の不可用期間の後に新リーダーとなる。6 秒目に S1・S2 が復帰し、10 秒目・14 秒目に新サーバ S4・S5 が追加されると、コンセンサスグループの過半数条件が増えることで一時的にスループットが低下する。その後 S2・S4 を削除するとスループットは段階的に回復する。 ![[_attachments/R2aft_A_Speedy_and_Highly_Available_RDMA-Based_Consensus_Protocol/fig09-failure-recovery-throughput.png]] (Figure 9. R2aft の故障回復・再構成中のスループット推移。2 秒目のリーダーサーバ全体故障、4 秒目のリーダープロセッサのみの故障(この間も R2aft は動作継続)、6 秒目の 2 サーバ復帰、10・14 秒目の新サーバ追加、それ以降の 2 サーバ削除に伴うスループット変化を時系列で示す。Source: Fig. 9, R2aft 論文。) ## 考察 - R2aft の中心的トレードオフは「細粒度障害モデルによる可用性向上」と「マルチリージョン設計に伴う性能オーバーヘッド」であり、著者らは Mu 比 12.2% のレイテンシ増を「許容可能なトレードオフ」と位置づけている。 - 故障シナリオ実験(Fig. 9)は、既存の RDMA ベース合意プロトコル(粗粒度障害モデル)が「プロセッサのみの故障」でも 3 サーバ中 2 故障扱いとなり完全停止する一方、R2aft は継続動作できることを実証しており、これが本論文の中心的貢献の実証的裏付けになっている。 - Reconfiguration(サーバの追加・削除)は依然としてリモートプロセッサの関与を必要とする(RDMA のアクセス許可管理の制約による)ため、R2aft の「プロセッサバイパス」は通常運用(リーダー選出・ログ複製)に限定される。 ## 強み / 弱点・課題 - **強み**: - リーダー選出・ログ複製の両方でリモートプロセッサを完全にバイパスする初の RDMA ベース合意プロトコルであり、既存の RDMA ベース合意プロトコルが対処しきれていなかった課題を解決する。 - Write-Read-Verify という単純な処理順序の入れ替えのみで、追加の同期プリミティブなしに競合状態を防ぐ点は実装上のオーバーヘッドが小さい。 - Mu に匹敵するスループットを維持しながら可用性を高めており、性能と可用性のトレードオフが小さい。 - **弱点・課題(著者らが Discussion で認める限界)**: - **メモリ消費が O(N)**: 各サーバが N 個のデータ領域を保持する必要があり、実装では 1 領域あたり 256MB、5 サーバ構成で 1 サーバあたり 1.25GB を消費する。著者らは現代サーバでは許容範囲としているが、サーバ数が増えるほど比例して増加する。 - **Reconfiguration は依然プロセッサ依存**: RDMA のアクセス許可管理の現行仕様上の制約により、サーバの追加・削除にはリモートプロセッサの関与が必要。 - 著者らは、RNIC が汎用計算をサポートできるようになれば、単一データ領域のみで stale リーダーの誤った上書きを防げる可能性があり、これを将来課題としている(プログラマブル NIC との協調設計)。