--- title: 反熵とデータ修復 url: https://doc.liz6.com/ja/distributed-systems/06-distributed-storage/02-anti-entropy-and-data-repair locale: ja area: distributed-systems tags: - distributed-systems - distributed-storage date: 2026-06-30 modified: 2026-07-16 description: read repair は読み込まれたデータのみを修復するため、コールドデータは長期間不整合状態になる可能性があります。反熵（Anti-Entropy）は、Merkle木を用いてバックグラウンドでレプリカを体系的に照合・修復し、gossip駆動の増分照合によって最終的にすべてのレプリカを収束させます。 --- # 反熵とデータ修復 > read repair は読み込まれたデータのみを修復するため、コールドデータは長期間不整合状態になる可能性があります。反熵（Anti-Entropy）は、Merkle木を用いてバックグラウンドでレプリカを体系的に照合・修復し、gossip駆動の増分照合によって最終的にすべてのレプリカを収束させます。 ## 概要 [前節](/distributed-systems/06-distributed-storage/01-distributed-read-write-path.md)では、read repair と hinted handoff が読み書きパス上で「ついでに」データを修復する方法について解説しました。これらはパッシブな修復であり、読み込まれたレコードのみを修復するため、大量のコールドデータは長期間不整合状態のままになる可能性があります。**反熵（Anti-Entropy）**は、アクティブで体系的な修復プロセスです。バックグラウンドでレプリカを継続的に照合し、不整合を特定して修復し、最終的にすべてのレプリカを整合状態（収束）へ導きます。この節の中核となるのは **Merkle tree** です。これは2つのデータセット間の差分を効率的に照合できる木構造です。 ## なぜ read repair では不十分か read repair には3つの盲点があります。 - **読み込まれたデータのみを修復する**: コールドデータが1ヶ月間読み込まれなければ、不整合は1ヶ月間放置されます。 - **単一のキーのみを修復する**: 「特定のレプリカ全体が大幅に遅れている」といった状況を検出できません。 - **ノードの再参加を処理しない**: ノードが1週間ダウンした後で復帰した場合、大量の書き込みを見逃しており、hinted handoff は期限切れになっています。この場合、体系的な全量補完が必要です。反熵は、これらの3つの盲点を解決します。 ## Merkle tree: 差分照合のエンジン 2つのノード上のデータ（数GBのキーバリュー集合の場合もある）において、どのキーが不整合であるかを効率的に特定するにはどうすればよいでしょうか？ 1件ずつ照合するのは遅すぎます。Merkle tree は照合を ~O(log n) に削減します。構築方法: 1. ノード上の全キーを範囲ごとに複数の bucket（Merkle tree のリーフ）に分割します。 2. 各 bucket に対して hash（その bucket 内の全キーバリューの集約 hash）を計算します。 3. 上位ノード = hash(子ノード hash の連結)。 4. root hash がデータセット全体を表します。 2つのノードのデータを照合するには、root hash を交換します。一致すれば整合しています。一致しない場合は、子ノードの hash を再帰的に照合し、不一致の bucket を特定します。その後、その bucket 内のキーのみを1件ずつ照合・修復します。**2つのノード間で hash のみを交換すればよく、実際のデータは送信しません**。不一致の bucket が特定されて初めて、その部分のデータが送信されます。 ### 実装の詳細 - **動的構築**: Merkle tree は常駐しません。照合が必要になった時点で現在のデータに基づいて構築され、完了後に破棄されます。Cassandra の `nodetool rebuild` はこの構築をトリガーします。 - **bucket の粒度**: 細かすぎると木が大きくなり構築が遅くなります。粗すぎると特定が不正確になり、修復対象が多くなります。Cassandra ではデフォルトで 15 層です。 - **構築コスト**: 全データをスキャンして hash を計算するため、大規模データセットでは負荷が高くなります。そのため、反熵は**バックグラウンドで低頻度**（例: 1日1回）で実行され、リアルタイムではありません。 ## 2つの反熵モード ### gossip 反熵: Dynamo のアプローチ [Gossip プロトコル](/distributed-systems/05-members-and-discovery/02-gossip-protocol.md)はメンバーの発見だけでなく、反熵にも使用されます。各ノードは定期的にランダムなピアを選択します。 1. 両ノードは各自の Merkle tree root hash を交換します。 2. root が不一致の場合、再帰的に照合して不一致の bucket を特定します。 3. 不一致のキーに対して、**バージョンベクトル（または最終書き込みタイムスタンプ）**を用いてどちらの更新を適用するかを決定します。単純に「相手が持っていないものは送る」のではなく、両ノードが同じキーを更新している場合（競合は[競合解決](/distributed-systems/03-replication-and-consistency/02-conflict-resolution.md)参照）があるためです。 4. 勝者のバージョンを相手にプッシュします。ランダムなピアを選択する gossip による反熵には優れた数学的性質があります。N 個のノード間で、各ステップでランダムに1つのピアを選択する場合、不整合データは O(log N) 回のラウンドで高い確率で修復されます。これは Demers 1987年の「Epidemic Algorithms」における核心的な結論です。 ### 全量修復: ノードの再参加ノードがダウン後に再参加した場合、大量の書き込みを見逃しており、hinted handoff が期限切れになっている可能性があります。この場合、一度に全量を補完する必要があります。 1. 新規ノードは、他のレプリカから自分が担当するトークン範囲のデータを**全量取得**します（または増分: 変更ログがある場合はダウン期間中の変化のみを取得）。 2. 取得時には Merkle tree を用いて検証し、取得したデータが完全かつ正確であることを確認します。 3. 取得後、ローカルのインデックスと Bloom filter を構築します。 [Cassandra](/) の `nodetool rebuild`、[Riak](/) の `riak-admin transfers`、HDFS DataNode の block report はすべてこのパターンです。 ## 整合性と修復の相互作用直感に反する点ですが、**反熵は「最終整合性」の負債を返済するものです**。システムが強整合性（例: Raft）を使用している場合、通常時は反熵は不要です。Raft のログレプリケーションは、コミット済みエントリが過半数で整合していることを保証しているためです。Raft で「修復」が必要になるのは以下のケースのみです。 - **スナップショット転送**: 新規参加したフォロワーが大幅に遅れている場合、リーダーはログをトリンケートしている可能性があります。この場合、リーダーはスナップショット（状態機械の全量スナップショット）を送信します。これは本質的に全量修復です。 - **ディスク破損**: 単一ノードのローカルデータが破損した場合、他のノードから全量を再取得します（これは反熵の「ノード再参加」と同様です）。したがって、反熵のエンジニアリング形態は整合性モデルに依存します。[レプリケーションポリシー](/distributed-systems/03-replication-and-consistency/01-replication-strategies.md)が最終整合性寄りのほど、反熵は重要になり、エンジニアリング化された Merkle tree + gossip が必要になります。強整合性寄りのほど、反熵は「コンセンサスプロトコルのログレプリケーション + スナップショット」に置き換えられますが、「全量の再取得」のニーズは残っており、トリガー条件や実装方法が異なるだけです。 ## 修復のスケジューリングとスロットリング反熵にはコストがかかります。Merkle tree の構築には全データのスキャン（CPU + IO）が必要であり、hash や実際のデータの送信はネットワーク帯域を消費します。制御が必要です。 - **スロットリング**: 修復が占めるスループットを制限します。Cassandra の `compaction_throughput_mb_per_sec` は、修復中のストリーミングにも影響します。 - **スケジューリング**: ビジネスのピークを避けます。または、オフピーク時に全量修復を実行し、ピーク時は read repair のみを行います。 - **増分優先**: システムに変更ログ（直近で変更されたキーのリスト）がある場合、まずその部分を修復し、その後で全量検証を行います。 ## トレードオフと失敗パターン - **read repair を反熵として使用**: コールドデータは永遠に修復されない → 定期的な全量反熵が必要。 - **Merkle tree 構築による IO 逼迫**: 反熵中にノードの CPU/ディスク使用率が急上昇し、通常の読み書きに影響 → スロットリング + オフピーク時のスケジューリング。 - **全量修復によるネットワーク飽和**: 数GBのデータ取得時に帯域を埋め尽くす → ストリーミングのスロットリング + 並列度の制御。 - **バージョン競合解決の誤り**: 反熵中に「Last-Writer-Wins」を用いて並行更新を上書き → タイムスタンプではなくバージョンベクトルを使用（[競合解決](/distributed-systems/03-replication-and-consistency/02-conflict-resolution.md)参照）。 ## 参考文献 - **論文**: "Dynamo" (Merkle tree による反熵、2007年)、「Epidemic Algorithms for Replicated Database Maintenance」(Demers 1987年) *Keywords: anti-entropy, Merkle tree, hash tree, incremental comparison, gossip repair, read repair, hinted handoff, replica migration, consistent hashing rebalance, full vs incremental repair, repair scheduling, repair throttling, version vector, epidemic algorithm*