プロンプトとコンテキスト
レプリケーションされたKey-Valueストア向けのバックグラウンドアンチエントロピーサービスを設計してください。書き込みが継続している間にノードが一時的にオフラインになる可能性があります。システムはフルスキャンを回避し、最終的に収束しなければなりません。Merkle木がどのように差分を特定するか、修復がどのようにレート制限されるか、そして古いレプリカが新しいデータを上書きするのをどのように防ぐかを説明してください。
Dynamoの論文では、キー範囲ごとのMerkle木について説明されています。最初にルートと内部ノードを比較し、次にハッシュが異なるリーフ範囲のみを同期します。この面接では、検出、バージョン調停、並行修復、リソースバジェット、およびオブザーバビリティを1つのプロトコルに統合することが問われます。
面接官がテストしていること
面接官は、整合性の目標、バージョニング、パーティションおよびツリー更新の境界、増分比較、冪等な修復、スロットリング、リトライ、トポロジ変更、そして信頼できる収束の論証をテストしています。リード修復（read repair）や人間による復旧がいつ必要になるかを説明してください。
確認のための質問
キースペースのパーティション、レプリケーション係数、読み取りおよび書き込みの整合性、バージョン表現、削除セマンティクス、許容される古さ（staleness）、データサイズ、および修復の帯域幅を確認します。障害モデル、ネットワーク分断、暗号化、テナント分離、および修復がビジネストラフィックとリソースを共有するかどうかについて尋ねます。
30秒の回答
「仮想ノードまたはキー範囲ごとにバージョン管理されたMerkle木を維持します。ピア同士で範囲、ルートハッシュ、およびスナップショットのウォーターマークを交換します。ルートが一致していれば処理をスキップし、不一致の場合は異なるリーフまで再帰的に探索してキーをバッチ処理します。修復の書き込みにはバージョンまたはツームストーンを付与し、古い値を拒否する決定論的なコンフリクト解決ルールを使用します。冪等なバッチ、リース、帯域幅バジェット、リトライ、および飽和度メトリクスによって修復の安全性を保ちます。修復の経過時間、差分カウント、およびサンプリングされたレプリカの読み取りによって収束を実証します。」
詳細な回答
ステップ 1: パーティションとバージョンの定義
キースペースを所有者レプリカセットを持つ安定した範囲に分割します。各レコードには単調増加バージョン、ベクタークロック、または因果バージョンを付与します。削除には伝播するツームストーンが必要です。レコードが存在しないことが『最初から存在しなかった』を意味してはなりません。
ステップ 2: 比較可能なMerkle木の構築
リーフはキーとバージョンのダイジェストを決定論的な順序で集約し、親は子のハッシュを格納します。再構築または増分更新のいずれも可能ですが、ルートが一意の意味を持つように、書き込みスナップショットの境界を明示する必要があります。
ステップ 3: ルートからリーフへの比較
最初に範囲の識別情報とルートを比較します。ルートが等しい場合は転送の必要はありません。ルートが異なる場合は、最小の相違範囲が見つかるまで子ノードを再帰的に探索し、キーとバージョンの要約をバッチ化します。1つの修復が他のパーティションをブロックしないように、ホットな範囲を分割するか、バッチサイズに上限を設けます。
ステップ 4: バージョンと削除の調停
異なるキーが届いたときにバージョンの関係を比較します。並行するバージョンは到着時刻だけで解決することはできません。マージするか、コンフリクトを保持するか、またはビジネスルールを適用します。ツームストーンには、クリーンアップの前に保持期間と安全なウォーターマークが必要です。
ステップ 5: 修復バッチの冪等性の確保
バッチにはその範囲、スナップショットバージョン、シーケンス、およびダイジェストを含めます。バッチを再実行しても余計な副作用は発生しません。ターゲット側は適用前にバージョンを確認し、古いバッチは安全に拒否またはスキップされます。結果は再生可能で監査可能です。
ステップ 6: リソースと並行性のバジェット管理
テナント、範囲、ノード、および優先度ごとに、並行性、帯域幅、CPU、ディスク読み取り、およびキューのバジェットを設定します。ビジネストラフィックを優先します。ノードが過負荷になった場合や、レプリケーション遅延がしきい値を超えた場合は修復を一時停止します。ノードが一斉にリトライしないように、指数バックオフにジッターを追加します。
ステップ 7: トポロジ変更と障害の処理
ノードの参加や離脱、または範囲の移動が発生したときに、レプリカセットとツリーのメタデータを再計算します。再起動後に再開できるように、進捗、スナップショット、およびリースを永続化します。ネットワーク分断中は書き込みの受け入れを継続しますが、収束していると主張するのではなく、古い状態やコンフリクト状態を明示します。
ステップ 8: 収束の証明と運用
最終修復時刻、相違キー数、ツームストーンの経過時間、失敗したバッチ、バージョンのコンフリクト、および範囲ごとの帯域幅を監視します。定期的にレプリカ間のサンプリング読み取りを比較し、最大許容古さのSLOを設定します。修復が恒常的に失敗する場合は、無限にリトライするのではなく、アラートを発報し、範囲を隔離するか手動で復旧します。
模範解答
キースペースを仮想ノードの範囲にパーティショニングし、範囲ごとにバージョンダイジェストを持つMerkle木を維持します。ピア同士で範囲の識別情報、ルートハッシュ、およびスナップショットのウォーターマークを交換します。ルートが等しければスキップし、ツリーが異なる場合は差分のあるリーフまで再帰的に探索してそれらのキーのみを転送します。レコードにはベクタークロックまたは単調増加バージョンを使用し、削除にはツームストーンを使用し、コンフリクトは決定論的なマージまたは調停ルールに従います。到着が遅かったという理由だけで古いバージョンが勝つことはありません。修復バッチはスナップショット、シーケンス、ダイジェストを持ち、冪等です。テナント、範囲、ノード、帯域幅のバジェットによりビジネストラフィックを保護し、障害時にはジッター付きバックオフを適用します。トポロジの変更時にはレプリカセットとリースを再計算します。運用面では差分、修復の経過時間、コンフリクト、ツームストーン、失敗を追跡し、レプリカの読み取りをサンプリングし、古さのSLOを設定します。恒常的な不一致が発生した場合は、人間による復旧のために範囲を隔離します。
よくある間違い
ルートが異なるときにシャード全体を送信する
Merkle木の目的は、最小の相違範囲を再帰的に特定することです。完全な転送はネットワークとディスクのコストを何倍にも増やし、ホットなパーティションをブロックする可能性があります。
すべてのコンフリクトをLast-Write-Winsで解決する
クロックスキューと並行書き込みにより、到着時刻は安全な因果シグナルにはなりません。バージョンの関係、マージルール、またはビジネス調停を使用してください。
削除とツームストーンを無視する
削除が即座に消去されると、遅延しているレプリカが古い値を復活させてしまう可能性があります。ツームストーンの保持と安全なクリーンアップは収束の一部です。
フォローアップの質問と回答
Merkle木は継続的な書き込みをどのように処理しますか？
新しい書き込みが新しいバージョンに入る間、一貫したスナップショットまたはバージョンウォーターマークを比較します。バッチが完了した後に修復ウォーターマークを進めます。変化し続けるルートは単一のスナップショットではありません。
特定の範囲が極端にホットな場合はどうしますか？
さらに分割し、バッチと並行性に上限を設け、古さのウィンドウが最も大きい子範囲を優先します。必要に応じて一時的に読み取り増幅を減らすか、レプリカを移動します。
修復の途中でノードが再起動した場合はどうなりますか？
リース、バッチシーケンス、および永続化された進捗から再開します。ターゲット側のバージョンチェックにより重複バッチが安全になり、ソース側はスナップショットを再検証します。
古いツームストーンが早すぎる段階で削除されるのをどのように防ぎますか？
関連するすべてのレプリカが安全なウォーターマークまたは確認応答ポイントを通過した後にのみクリーンアップし、最も古いツームストーンの経過時間を監視します。確認が取れていない場合は保持します。
リード修復とアンチエントロピーの違いは何ですか？
リード修復はビジネスの読み取りパス上で発見された差分を修正し、ホットなキーをカバーします。アンチエントロピーはプロアクティブなバックグラウンドスキャンであり、コールドデータをカバーします。両者はバージョンと修復のセマンティクスを共有します。
自動修復はいつ停止すべきですか？
コンフリクトがマージできない場合、データが破損している場合、認可が異常な場合、またはリソースが過負荷のままである場合は、一時停止して範囲を隔離します。人間による復旧のために証拠とスナップショットを保持します。