プロンプトとコンテキスト
バッチ構築とメンバーシップクエリを備えた静的Xor Filterを実装してください。3セグメント構成、ピーリングキュー、フィンガープリントの割り当て、ビルドリトライ、偽陽性率、およびインプレース削除がサポートされない理由を説明してください。
Xor Filterは静的な近似的メンバーシップ構造です。各キーに対して短いフィンガープリントを格納し、クエリ時に3箇所のフィンガープリントをXORします。研究によれば、空間効率と検索速度においてBloom FilterやCuckoo Filterに対抗できますが、その構築はピーリング可能なランダムハイパーグラフに依存します。シードが失敗した場合は再ビルドが必要となるため、この構造はバッチ生成とその後の読み取り専用公開に適しています。
面接官が見ているポイント
面接官は、3つの配列の構築、重複や空集合の処理、次数キューによるハイパーグラフのピーリング、逆順でのフィンガープリント割り当て、構築とクエリでの同一ハッシュの使用、偽陽性の計算、削除および更新の制限の説明、リトライ・ピークメモリ・並行読み取りに関する論理的思考ができるかをチェックします。
明確化のための質問
データセットと更新モデル
キー数、重複ポリシー、再ビルド頻度、更新レイテンシ、削除が必須かどうかを確認します。Xor Filterは静的セットを対象としています。動的なワークロードではCuckoo Filterや階層的な再ビルドと比較検討する必要があります。
エラーと空間の目標
許容される偽陽性率、フィンガープリントの幅、偽陰性が許容されるか、および検索スループットとビルド時のピークメモリの優先順位を確認します。
キーとハッシュの境界
キーが整数、バイト文字列、または構造化オブジェクトのいずれであるか、ハッシュシードがどのように永続化されるか、言語をまたぐ実装で同一のバイト順序（エンディアン）と正規化が必要かどうかを確認します。
30秒での回答
「テーブルを3つのセグメントに分割します。各キーは各セグメント内の1つの位置にマッピングされ、固定幅のフィンガープリントを格納します。構築中、スロットの次数と接続エッジを追跡し、次数1のスロットをピーリングし、エッジが残った場合は新しいシードで再ビルドします。ピーリングの逆順で、あるスロットに対してキーのフィンガープリントと他の2つのスロット値のXORを割り当てます。クエリでは3つの位置を再計算してそれらをXORし、一致すれば『存在する可能性がある』ことを意味します。テーブルは静的かつ近似的であるため、安全なインプレース削除はサポートされません。」
ステップバイステップの解決策
ステップ1: レイアウトとフィンガープリントの定義
独立した64ビットハッシュ結果から3つの位置と下位ビットのフィンガープリントを導出します。テーブルをほぼ均等なセグメントに分割し、各位置をそのセグメント内に収まるよう縮小（剰余等）します。空のスロットが実際の値と混同されないよう、ゼロフィンガープリントの扱いを一貫して定義します。
ステップ2: ハイパーグラフの次数を構築する
各キーを3つのスロットを接続するハイパーエッジとして扱います。構築中、各スロットの次数と接続エッジのリストを保存し、次数1のスロットをキューに入れます。最初にキーを重複排除するか、セットのセマンティクスを明示的に定義します。そうしないと、1つのハイパーエッジが重複してカウントされる可能性があります。
ステップ3: グラフをピーリングする
次数1のスロットを取り出し、その一意のエッジを見つけ、そのエッジ、一意のスロット、および他の2つのスロットを記録します。エッジを削除し、3つのスロットすべての次数をデクリメントします。新しく次数1になったスロットをキューに入れます。キューが空になった後も未削除のエッジが残っている場合、このシードではピーリング不可能なグラフが生成されたことになります。
ステップ4: 逆順でフィンガープリントを割り当てる
記録されたエッジをピーリングの逆順で処理します。一意のスロットに、キーのフィンガープリントと他の2つのスロットの現在の値のXORを設定します。これにより、3つのスロットすべてをXORするとそのキーのフィンガープリントが得られます。書き込まれていないスロットはゼロとして寄与します。
ステップ5: 検索（Lookup）の実装
検索では、構築時と同じシード、位置関数、フィンガープリント関数を使用し、3つのセグメントを読み取ってそれらをXORします。一致は「存在する可能性がある」ことのみを意味し、メンバーシップの証明にはなりません。呼び出し側はデータベースまたは正確なセットと照合してヒットを解決する必要があります。
build(keys):
repeat with a new seed:
edges = positions_and_fingerprints(keys, seed)
queue = all degree-1 slots
order = peel(edges, queue)
if order contains every edge:
table = zeroed slots
for edge in reverse(order):
table[edge.unique] = edge.fp XOR table[edge.other1] XOR table[edge.other2]
return seed, table
fail after bounded retries
contains(key):
a, b, c = positions(key, seed)
return table[a] XOR table[b] XOR table[c] == fingerprint(key)ステップ6: 失敗とリソースの処理
ビルドの失敗は検索の偽陰性ではありません。このシードのグラフに完全なピーリング順序が存在しないことを意味します。リトライ回数を制限し、シードまたはテーブルサイズを変更し、不完全なテーブルを公開するのではなく明示的なエラーを返します。次数配列、エッジリスト、ピーリングスタックにより、ビルド時のピークメモリは最終的な読み取り専用テーブルよりも大きくなります。
ステップ7: 更新と検証の説明
テーブルは完全なキーセットに対する方程式を解くため、挿入や削除を行うと他のキーのXOR関係が崩れる可能性があります。再ビルド、2つのバージョンのアトミックなスワップ、または小さなフィルターの階層化によって更新します。空集合、単一キー、重複、ハッシュ衝突、ビルド失敗、シリアライズ復元、偽陽性、並行読み取り専用検索をテストします。
模範解答
キーセットを3セグメントの3均一ハイパーグラフにマッピングし、次数キューでピーリングを行い、ピーリングの逆順で短いフィンガープリントを割り当てます。検索は3回のスロット読み取りとXORを実行するため定数時間ですが、結果は近似的メンバーシップです。ビルド失敗は現在のシードがピーリング可能でないことを意味します。上限を設定して新しいシードでリトライし、上限を超えた場合は公開を拒否します。テーブルはすべてのキーに依存しているため、インプレースの挿入や削除は安全ではありません。本番環境の更新では、新しいテーブルを再ビルドしてアトミックにスワップします。シード、テーブルサイズ、フィンガープリント幅、バイト順序をバージョンとともに永続化し、正確なセットに対して偽陽性を測定します。
よくある間違い
- 間違い: 構築失敗後に不完全なテーブルを返す。 → 失敗の理由: 未処理のエッジによって偽陰性が発生する可能性があります。 → 修正方法: シードまたはテーブルサイズを変更し、すべてのエッジが割り当てられた後にのみ公開します。
- 間違い: 検索時に異なるシードやセグメントマッピングを使用する。 → 失敗の理由: 構築と検索で異なるスロットを参照してしまいます。 → 修正方法: シード、セグメント境界、ハッシュ実装を永続化し、バージョン管理します。
- 間違い: 検索の陽性判定を厳密なメンバーシップとして扱う。 → 失敗の理由: 短いフィンガープリントは偽陽性を引き起こします。 → 修正方法: フィルターを事前チェックとして使用し、その後に正確なストレージを参照します。
- 間違い: インプレース削除をサポートする。 → 失敗の理由: 共有スロットは他のXOR方程式にも関与しています。 → 修正方法: 再ビルドするか、2つのバージョンを使用するか、動的フィルターを選択します。
フォローアップ質問と回答
なぜ1つの配列ではなく3つのセグメントを使用するのですか？
3つのセグメントを使用することで、すべてのエッジが各領域に1つずつのスロットを持つことになり、ピーリング可能なハイパーグラフの構築と定数時間の検索が実用的になります。正確な比率と負荷率はベンチマークで測定する必要があります。
フィンガープリントの幅はどのように選択しますか？
フィンガープリントを短くするとスペースは削減されますが、偽陽性が増加します。無関係なキーでミス率を測定し、その結果生じる正確なストレージへの検索コストとメモリ削減量のバランスを取ります。
シードのリトライによって結果は不安定になりますか？
テーブルの内容は変わりますが、最終的なシード、バージョン、テーブルを一緒に永続化すれば検索は再現可能です。同じリリースマニフェストに構築メタデータを含めます。
どのような場合にBloom FilterやCuckoo Filterを選択しますか？
頻繁な挿入、削除、カウンティング、またはオンラインでのリサイズが必要な場合は、動的フィルターが適しています。Xor Filterは、コンパクトな読み取り専用検索が重要となる、静的でバッチ構築されるセットに対して最も威力を発揮します。