プロンプトとコンテキスト
Cuckoo Filter は近似メンバーシップ構造です。false はアイテムが確実に存在しないことを意味し、true は存在する可能性があることを意味します。標準的な Bloom Filter と比較して、バケットに短いフィンガープリントを格納するため、削除や柔軟な検索をサポートできます。トレードオフとして、挿入時にエントリが再配置される可能性があり、許容量の上限付近で挿入が失敗することがあります。この問題では、ハッシュ処理、配列レイアウト、ランダム化、エッジケースの処理、およびベンチマークがテストされます。
面接官が評価しているポイント
- フィンガープリントと 2 つの候補バケットの関係を説明できるか。
- 削除処理が偽陰性を回避し、再配置がループを防ぐために有界になっているか。
- 重複操作、満杯のバケット、ハッシュ衝突、並行性の境界を適切に処理しているか。
- 容量、フィンガープリントのビット数、目標とする偽陽性率を使用してパラメータを選択および検証できるか。
最初に確認すべき明確化のための質問
想定されるアイテム数、バケットあたりのスロット数、許容される偽陽性率、メモリ予算について質問します。削除、永続化、並行書き込み、または決定論的な動作は必要ですか？ 値は安定したバイト列にエンコード可能ですか、またハッシュシードはバージョン間で固定されている必要がありますか？ 挿入に失敗した場合、システムは再構築するか、層（tier）を追加するか、それとも呼び出し元に信頼できる情報源（source of truth）を参照させるべきですか？ 偽陽性によってどのようなバックエンドコストが発生しますか？
30秒の回答フレームワーク
各値に対して、ゼロ以外のフィンガープリント f とプライマリバケット i1 を計算し、フィンガープリントからセカンダリバケット i2 を導出することで、f が正確に 2 つの候補内に収まるようにします。検索では両方のバケットをチェックします。削除では、Bloom Filter で共有ビットをクリアするのとは異なり、一致するフィンガープリントのみをクリアします。挿入ではまずいずれかのバケットを試行し、両方が満杯の場合は有界なランダム再配置を実行します。キックの上限に達した場合は失敗を返し、再構築または別の層の追加をトリガーします。フィンガープリントの長さ、バケット容量、最大負荷は、偽陽性、挿入成功率、レイテンシのテストによって調整する必要があります。
ステップごとの詳細解説
1. インターフェースと不変条件の定義
add(x) が成功した後、そのフィンガープリントは 2 つの候補バケットのいずれかに存在しなければなりません。mightContain(x) は、いずれのバケットにも f が含まれていない場合にのみ false を返します。remove(x) は一致するフィンガープリントのみをクリアします。2 つの値がフィンガープリントを共有している場合、一方を削除するともう一方が true を返し続ける可能性がありますが、これは許容される偽陽性です。ただし、挿入された値が false を返してはなりません。
2. フィンガープリントと候補バケットの生成
安定したエンコーディングからプライマリインデックス i1 を計算し、固定長のゼロ以外のフィンガープリント f を取得します。i2 = i1 XOR hash(f) を導出し、バケット数で剰余を取ります。インデックスとフィンガープリントの計算では、ハッシュアルゴリズム、シード、バイト順序、バージョンを固定する必要があります。そうしないと、永続化されたエントリやリサイズされたテーブルが読み取り不能になります。フィンガープリントが短いと偽陽性率が上昇し、長いと消費メモリが増加します。
3. バケットレイアウトと検索の設計
各バケットには、完全な値ではなく固定数のフィンガープリントスロットが格納されます。検索では i1 と i2 のみを読み取り、どちらかに f が含まれている場合に「存在する可能性がある」と返します。バケットの幅は、負荷と局所的な衝突に影響します。連続した配列を使用することでポインタのオーバーヘッドを削減できます。バケット数、スロット数、フィンガープリントビット数、ハッシュバージョンをテーブルとともに永続化します。
4. 挿入と有界な再配置の処理
候補となるいずれかのバケット内の空きスロットを試します。両方が満杯の場合は、バケットとスロットを 1 つ選択してそのフィンガープリントを追い出し（evict）、追い出されたフィンガープリントをその代替バケットに移動します。再配置には最大回数または訪問済みバケットのガードが必要であり、無限ループしてはなりません。高い負荷と不適切なハッシュ分布を区別できるように、ランダム性、キック数、失敗原因を観測可能にします。
5. 削除と重複操作の実装
両方の候補バケットで一致するフィンガープリントを検索し、1 つのスロットをクリアします。呼び出し元が厳密な要素レベルの削除を要求する場合、短いフィンガープリントは衝突する可能性があるため、信頼できるストアに対して検証するか、より長いフィンガープリントを使用します。remove は、存在しない値に対して冪等であるべきです。重複する add が別のスロットを消費するかどうかを定義します。重複を許可するか、既存のフィンガープリントを検出して書き込みをスキップすることができます。
6. 安全なテスト、失敗処理、およびリサイズ
挿入された値が偽陰性を生成しないこと、ランダムに生成された非存在値が期待通りの偽陽性率を示すこと、削除が仕様通りに動作すること、重複操作が安定していること、満杯のバケットが再配置を行うこと、決定論的な入力が一貫して動作することをテストします。負荷係数、再配置の失敗、検索レイテンシ、メモリを記録します。閾値に達したら、より大きなテーブルで再構築するか層を追加します。リーダーに一時的な不整合が見えないよう、リサイズ中も古いスナップショットを保持します。
模範解答
安定したゼロ以外のフィンガープリント f とプライマリバケット i1 を計算し、そこから i2 = i1 XOR hash(f) を導出します。各バケットには固定数のフィンガープリントが格納されます。検索では両方をチェックし、f が両方に存在しない場合にのみ false を返します。削除では一致するスロットがクリアされるため、Bloom Filter のように共有ビットがクリアされることはありません。短いフィンガープリントの衝突が問題になる場合は、信頼できる情報源を参照します。挿入では両方のバケットを試行し、有界なランダムキックを実行し、制限に達した場合は失敗を返します。エンコーディング、ハッシュシード、バケット数、スロット、バージョンを固定し、重複の動作を定義して、削除を冪等にします。テストでは、挿入された値に対する偽陰性の排除、非存在サンプルの偽陽性、削除、満杯のバケット、再配置の失敗、並行性の境界を網羅します。高負荷や高い失敗率は、再構築または別のフィルター層の追加をトリガーします。
よくある間違い
- Cuckoo Filter を完全な集合として扱い、偽陽性を無視する。
- 1 つのバケットインデックスしか格納せず、追い出されたフィンガープリントが代替バケットを見つけられなくなる。
- キック制限を省略し、サイクルによってリクエストがブロックされるのを放置する。
- 空スロットと区別がつかないゼロフィンガープリントを許可する。
- 削除中にバケット全体または誤ったスロットをクリアしてしまい、偽陰性を引き起こす。
- 重複操作、永続化バージョン、リサイズ中の二重読み取り、および挿入失敗を無視する。
フォローアップの質問と回答
なぜ Bloom Filter は通常削除できないのに、Cuckoo Filter は削除できるのですか？
Cuckoo Filter は特定のスロットからフィンガープリントを削除します。Bloom Filter のビットは複数の値で共有される可能性があるため、それをクリアすると別の値が破損する可能性があります。どちらも偽陽性を返す可能性があり、厳密な削除には依然としてフィンガープリントの衝突を考慮する必要があります。
フィンガープリントの長さとバケット幅はどのように選択しますか？
アイテム数、目標偽陽性率、メモリ、負荷の目標から始めます。理論を用いてフィンガープリントのビット数とスロット数を見積もり、実際の分布を用いてベンチマークを実行します。フィンガープリントを長くすると偽陽性は減少しますが、使用領域が増加します。バケット幅を広げると、スキャンのコストと引き換えに負荷を改善できます。
再配置が制限に達したとき、単に新しいアイテムを破棄することはできますか？
明示的な失敗を返してください。決して挿入が成功したと偽ってはいけません。呼び出し元は、より大きなフィルターを再構築するか、別の層に書き込むか、信頼できる情報源にアイテムを保持することができます。メンバーシップが暗黙のうちに失われないよう、負荷と失敗率を監視します。
スレッド間で検索と削除の一貫性を保つにはどうすればよいですか？
スナップショットセマンティクスまたはロックセマンティクスを選択します。アトミックなスロット更新、シャーディングされたロック、または不変スナップショットの公開を使用します。コントラクトが線形化可能性を要求しない限り、並行する検索と削除によって一時的な偽陽性が許容される場合があります。通常の同期されていないメモリアクセスは、一貫性設計とは呼べません。