Nezha: A Key-Value Separated Distributed Store with Optimized Raft Integration

本論文は、合意プロトコルとストレージエンジン間の重複する永続化操作による I/O オーバーヘッドを解消するため、キー・バリュー分離と Raft を最適化して統合し、Put/Get/Scan 操作で大幅なスループット向上を実現した分散キーバリューストア「Nezha」を提案するものである。

要約

🏠 背景：なぜ新しいシステムが必要なの？

現代のインターネットサービス（EC サイトや SNS など）は、膨大なデータを扱っています。このデータを安全に保存するために、多くのシステムは**「Raft（ラフト）」という「合意形成のルール」と、「LSM ツリー」**という「データの整理術」を組み合わせて使っています。

しかし、ここには**「無駄な作業」**が潜んでいました。

📦 従来の仕組みの「無駄な動き」

Imagine 想像してみてください。あなたがスーパーマーケットで「牛乳（データ）」を棚に並べる作業をしているとします。

1. ルールブックへの記録（Raft ログ）: 「誰がいつ牛乳を置いたか」を、全店員が共有するルールブックに書き込みます。
2. 作業メモ（WAL）: 作業中のメモ帳に「牛乳を置いた」と書き込みます。
3. 棚への配置（SSTable）: 実際の牛乳を棚に並べます。

問題点: 牛乳（データ）そのものが3 回も書き込まれるのです！

• ルールブックに「牛乳」と書く。
• メモ帳に「牛乳」と書く。
• 棚に「牛乳」を置く。

さらに、棚が混んできたら、整理のために**「棚の入れ替え（コンパクション）」**という重労働が発生し、牛乳を何度も持ち運ばなければなりません。
これが、データの書き込みが重く、遅くなる原因でした。

---

🚀 Nezha（哪吒）の解決策：「中身」と「住所」を分ける！

Nezha は、この無駄を劇的に減らすために、「中身（値）」と「住所（キー）」を分けるという大胆なアイデアを採用しました。

🏷️ 1. 「中身」と「住所」の分離（Key-Value Separation）

Nezha は、ルールブック（Raft）に**「牛乳そのもの」を全部書き込むのではなく、「牛乳の保管場所（住所）」だけ**を書き込むようにしました。

• 従来のやり方: ルールブックに「牛乳 1 リットル」を 3 回コピーして書く。
• Nezha のやり方:
  1. 牛乳（データ）を1 回だけ、専用の倉庫（ValueLog）に置きます。
  2. ルールブックには「倉庫の A 列 3 段」という**「住所」**だけを書きます。

メリット:

• 書き込みが爆速: 重い牛乳を 3 回コピーする代わりに、軽い「住所」だけをコピーすれば OK です。
• 整理が楽: 棚の入れ替え（コンパクション）をするときも、重い牛乳を運ぶ必要がなく、軽い「住所」だけを書き換えれば済みます。

結果: 書き込み速度が約 4.6 倍に向上しました！

---

🧹 2. 掃除屋（GC）の新しい働き方

「住所」だけを書き込むと、古い住所がルールブックに散らばってしまいます。これを整理する「掃除（Garbage Collection: GC）」が必要ですが、ここで新しい問題が生まれます。

• 問題: 掃除中に新しい注文が入ると、データがバラバラになってしまい、読み取りが遅くなったり、システムが止まったりする恐れがあります。

Nezha は、この掃除を**「3 つのフェーズ（段階）」**に分けて行うことで、掃除中でもお店を止めずに営業できるようにしました。

1. 掃除前（Pre-GC）: 普通の営業。
2. 掃除中（During-GC）:
   • 新しい注文は**「仮のカウンター（New Storage）」**で受け付けます。
   • 古いデータは**「古い倉庫（Active Storage）」**に残したまま、裏側で整理作業をします。
   • 顧客は、どちらのカウンターからでも最新の牛乳がもらえるように、システムが自動で探します。
3. 掃除後（Post-GC）: 整理された新しい倉庫（Sorted ValueLog）にデータが整然と並び、検索が爆速になります。

メリット:

• 読み取り速度も落ちません。むしろ、整理された棚のおかげで、「特定の牛乳を探す（Get）」や「牛乳からビールまで探す（Scan）」のが約 1.2 倍〜1.7 倍速くなりました。

---

🌟 まとめ：Nezha がすごい理由

Nezha は、**「Raft（合意形成）」と「データ保存」という 2 つの異なる世界を、まるで「注文」と「配送」**を一体化させるように深く結びつけました。

• 従来のシステム: 「重い荷物を何度も運んで、何度も記録する」→ 遅い。
• Nezha のシステム: 「重い荷物は 1 回だけ運び、記録するのは『住所』だけ。掃除中でも営業を止めない」→ 超高速で、安全。

実験結果:

• データの書き込み（Put）: 460% 向上（約 4.6 倍）
• データの読み込み（Get）: 12.5% 向上
• 範囲検索（Scan）: 72.6% 向上

まるで、**「重い荷物を運ぶトラックを減らし、代わりにナビゲーター（住所）だけを素早く配る」**ようなシステムです。これにより、クラウドやビッグデータ処理の未来が、より速く、安く、効率的になることが期待されています。

技術概要

論文「Nezha: A Key-Value Separated Distributed Store with Optimized Raft Integration」の技術的サマリー

本論文は、分散キーバリューストアにおける一貫性保証（Raft プロトコル）とストレージエンジン（LSM-Tree）の間の重複した永続化操作が引き起こす重大なパフォーマンスボトルネックを解決するための、新しい分散ストレージシステム**「Nezha」**を提案するものです。

以下に、問題定義、手法、主要な貢献、実験結果、および意義について詳細をまとめます。

---

1. 問題定義 (Problem)

現代の分散キーバリューストア（etcd, TiDB, CockroachDB など）は、データの一貫性を保証するためにRaftなどの合意形成プロトコルと、書き込み最適化されたストレージエンジン（LSM-Tree）を組み合わせています。しかし、この組み合わせには以下のような**冗長なディスク書き込み（Redundant Disk Writes）**という深刻な問題が存在します。

1. 三重の書き込みオーバーヘッド:
   • 従来のシステムでは、1 つのデータ書き込みリクエストに対して、少なくとも以下の 3 回のディスク書き込みが発生します。
     1. Raft ログの永続化（ValueLog への書き込み）。
     2. 合意形成後、ストレージエンジンの WAL（Write-Ahead Log）への書き込み。
     3. MemTable が満杯になった際の SSTable へのフラッシュ（Compaction による追加書き込み）。
2. パフォーマンスのボトルネック:
   • 大規模な値（Value）を扱う場合、この重複書き込みが I/O オーバーヘッドを大幅に増大させ、スループットを低下させます。
   • 従来の LSM-Tree 最適化（WAL 削除など）は、Raft レベルとストレージレベルの両方の重複を完全には解消できていません。

2. 提案手法 (Methodology)

Nezha は、**キー・バリュー分離（Key-Value Separation）**の概念を Raft プロトコルと有機的に統合し、アーキテクチャレベルでこの問題を解決します。主な設計要素は以下の通りです。

A. KVS-Raft（最適化された合意プロトコル）

• バリューの分離: 従来のように値（Value）を LSM-Tree 内部と Raft ログの両方に書き込むのではなく、値は Raft の ValueLog にのみ 1 回書き込み、状態マシン（State Machine）には軽量な「オフセット（値の位置情報）」のみを保持します。
• 効果: これにより、値の永続化回数を「最低 3 回」から「1 回」に削減し、書き込み増幅（Write Amplification）を劇的に低減します。

B. Raft 対応の適応型ガベージコレクション（GC）フレームワーク

キー・バリュー分離を導入すると、値が ValueLog に散らばるため、読み込み（Get/Scan）時の I/O がランダムになり、パフォーマンスが低下するリスクがあります。これを解決するため、Nezha は以下の GC メカニズムを設計しました。

• 非同期なデータ整理: 古い ValueLog のデータをキー順にソートし、ハッシュインデックス付きの「ソート済み ValueLog」として再構築します。これにより、範囲クエリ（Scan）時のシーケンシャルアクセスを可能にします。
• 3 フェーズのリクエスト処理: GC 実行中もシステムが停止しないよう、リクエスト処理を以下の 3 フェーズに分割して管理します。
  1. Pre-GC: 通常の Active Storage のみで処理。
  2. During-GC: 新しいリクエストは「New Storage」へ、既存データは「Active Storage」と「New Storage」の両方を並列検索。
  3. Post-GC: 整理された「Final Compacted Storage（ソート済み）」と「New Storage」を参照。
• 安全性の保証: Raft のログ順序性を損なうことなく、GC によるデータ削除や整理を安全に行うためのメカニズムを実装しています。

C. 3 フェーズリクエスト処理メカニズム

Put（書き込み）、Get（ポイント検索）、Scan（範囲検索）の各操作に対し、GC の進行状況に応じて最適なアクセスパスを動的に選択するアルゴリズムを実装し、一貫性と可用性を両立させています。

3. 主要な貢献 (Key Contributions)

1. 問題の特定: 分散キーバリューストアにおける、合意プロトコルとストレージエンジン間の「不要なデータ永続化操作」が現代ハードウェア環境での主要なボトルネックであることを実証的に分析しました。
2. Nezha システムの設計:
   • KVS-Raft: 強一貫性を保ちつつ、キー・バリュー分離を Raft レベルに統合した新しい合意プロトコル。
   • Raft 対応 GC: 読み込み性能を最適化しつつ、データ整合性を保証するガベージコレクションフレームワーク。
   • 3 フェーズ処理: GC 実行中のリクエスト処理の正しさを保証するメカニズム。
3. 実装と評価: 大規模な実験評価を通じて、従来の Raft ベースのシステムと比較して、Put、Get、Scan 操作すべてで顕著な性能向上を実現したことを示しました。

4. 実験結果 (Results)

Nezha は、3 ノードクラスタ環境で 100GB のデータを用いた実験において、以下の成果を上げました。

• スループットの向上:
  • Put（書き込み）: 平均 460.2% の向上（従来の 4.6 倍）。値のサイズが大きくなるほどその差は顕著になります。
  • Get（ポイント検索）: 平均 12.5% の向上。GC によるインデックス最適化により、キー・バリュー分離特有のオーバーヘッドを解消しました。
  • Scan（範囲検索）: 平均 72.6% の向上。ソート済みファイルによるシーケンシャルアクセスの復元が寄与しました。
• レイテンシの低減:
  • Put 操作のレイテンシは平均 59.2% 削減されました。
  • GC 実行中であっても、書き込みスループットへの影響は最小限（Nezha-NoGC とほぼ同等）に抑えられています。
• スケーラビリティ: クラスタサイズを 3 ノードから 7 ノードに増やしても、Original システムと比較して 3.5 倍〜5.3 倍のスループットを維持しました。
• YCSB ワークロード: 様々な読み書き比率（A-F）のワークロードにおいて、一貫して高い性能を発揮し、特にスキャン負荷の高いワークロード E において他システムを大きく凌駕しました。

5. 意義 (Significance)

• コンセンサスとストレージの共設計（Co-design）の推進: 従来の「レイヤーを分けて最適化する」アプローチから脱却し、合意プロトコル（Raft）とストレージ構造を深く統合することで、根本的な I/O 冗長性を排除しました。
• 大規模データ処理への適応: NVMe SSD の普及によりソフトウェアレベルの I/O 効率が重要視される現代において、書き込み増幅を劇的に削減するアーキテクチャは、クラウド環境でのコスト削減（ストレージ使用量と I/O 回数の削減）にも直結します。
• 実用性の高い強一貫性システム: 従来の LSM-Tree ベースのシステムが抱える「書き込みは速いが読み込みが重い」というトレードオフを、Raft の安全性を損なわずに解消し、実用的な分散データベースとしての基盤技術として貢献します。

結論として、Nezha は、分散システムにおける「一貫性」と「高性能」の両立を、キー・バリュー分離と Raft の革新的な統合によって実現した画期的なシステムです。