本稿の出発点は、バックエンドエンジニアの面接で問われるシステム設計と障害境界です。元記事は面接全体を扱っていますが、ここでは Bloom Filter の実装だけを独立した技術テーマとして掘り下げます。
先に結論
Bloom Filter は、「そのキーは存在しない」と高速に判断するための確率的データ構造です。
- 追加済みのキーを「存在しない」と判定する偽陰性はありません。
- 未追加のキーを「存在するかもしれない」と判定する偽陽性はあります。
- 1,000件・目標偽陽性率1%なら、必要量は9,586 bit（1,199 byte）、ハッシュ回数は7回です。
- TypeScriptでは
Uint8Arrayのbitsetと、2個の32-bit hashから位置を作るDouble Hashingで実装できます。
重要なのは、Bloom Filterを正解データとして扱わないことです。false なら問い合わせを止め、true ならDBやキャッシュで最終確認します。
どんな問題を解くのか
存在しないキーへの問い合わせが多いAPIを考えます。毎回DBやオブジェクトストレージまで見に行くと、見つからない問い合わせにもI/Oコストがかかります。
Bloom Filterを手前に置くと、bitが一つでも0だった時点で「確実に存在しない」と判断できます。すべて1なら存在する可能性があるため、後段へ問い合わせます。
よくある用途は次の通りです。
- キャッシュに存在しないキーを、永続ストレージへ問い合わせる前に除外する
- LSM-treeで、対象SSTableにキーがないことを読み取り前に判定する
- クローラーで、すでに処理した可能性があるURLを小さいメモリでふるいにかける
一方、「存在するか」を確定する用途や、1件の誤判定も許されない認可判定には使えません。
bit数とハッシュ回数を決める
想定要素数を n、許容する偽陽性率を p とすると、必要bit数 m とハッシュ回数 k の目安は次です。
m = ceil(-n * ln(p) / (ln(2) ^ 2))
k = round((m / n) * ln(2))
n = 1000、p = 0.01 を代入すると、m = 9586、k = 7 になります。bitsetなので実メモリは ceil(9586 / 8) = 1199 byte です。
要素を n 件追加した後の理論上の偽陽性率は、次で近似できます。
(1 - exp(-k * n / m)) ^ k
予定より多く追加すると1のbitが増え、偽陽性率も上がります。容量は実装時の飾りではなく、運用上の契約です。
TypeScriptで実装する
k 個の独立したハッシュ関数を用意する代わりに、2個のハッシュ値から h1 + i * h2 を作ります。これはDouble Hashingと呼ばれる方法です。
class BloomFilter {
readonly bitSize: number;
readonly hashCount: number;
readonly bits: Uint8Array;
constructor(bitSize: number, hashCount: number) {
if (!Number.isInteger(bitSize) || bitSize <= 0) {
throw new RangeError("bitSize must be a positive integer");
}
if (!Number.isInteger(hashCount) || hashCount <= 0) {
throw new RangeError("hashCount must be a positive integer");
}
this.bitSize = bitSize;
this.hashCount = hashCount;
this.bits = new Uint8Array(Math.ceil(bitSize / 8));
}
static fromExpectedItems(expectedItems: number, falsePositiveRate: number) {
if (!Number.isInteger(expectedItems) || expectedItems <= 0) {
throw new RangeError("expectedItems must be a positive integer");
}
if (!(falsePositiveRate > 0 && falsePositiveRate < 1)) {
throw new RangeError("falsePositiveRate must be between 0 and 1");
}
const ln2 = Math.log(2);
const bitSize = Math.ceil(
(-expectedItems * Math.log(falsePositiveRate)) / (ln2 * ln2),
);
const hashCount = Math.max(
1,
Math.round((bitSize / expectedItems) * ln2),
);
return new BloomFilter(bitSize, hashCount);
}
add(value: string): void {
for (const index of this.#indices(value)) {
this.bits[index >>> 3] |= 1 << (index & 7);
}
}
mightContain(value: string): boolean {
for (const index of this.#indices(value)) {
if ((this.bits[index >>> 3] & (1 << (index & 7))) === 0) {
return false;
}
}
return true;
}
estimateFalsePositiveRate(insertedItems: number): number {
return (1 - Math.exp((-this.hashCount * insertedItems) / this.bitSize)) **
this.hashCount;
}
*#indices(value: string): Generator<number> {
const bytes = new TextEncoder().encode(value);
const h1 = fnv1a32(bytes, 0x811c9dc5);
const h2 = fnv1a32(bytes, 0x9e3779b9) | 1;
for (let i = 0; i < this.hashCount; i++) {
yield ((h1 + Math.imul(i, h2)) >>> 0) % this.bitSize;
}
}
}
function fnv1a32(bytes: Uint8Array, seed: number): number {
let hash = seed >>> 0;
for (const byte of bytes) {
hash ^= byte;
hash = Math.imul(hash, 0x01000193) >>> 0;
}
return hash;
}
bit操作の読み方
index >>> 3 は floor(index / 8) と同じで、対象byteを求めます。index & 7 は index % 8 と同じで、そのbyte内のbit位置を求めます。
this.bits[index >>> 3] |= 1 << (index & 7);
この1行で、対象bitだけを1にできます。h2 に | 1 を付けて奇数にしているのは、2個目のハッシュ値が0になり、全ハッシュが同じ位置を指す退化を避けるためです。
Math.imul と >>> 0 は、JavaScriptのnumberを32-bit整数の乗算・加算として扱うために使っています。本番でフィルターを永続化する場合は、ハッシュ関数・seed・文字エンコードをバージョン付きで固定してください。どれかを変えると、同じキーでも別のbitを参照します。
偽陰性がないことと、偽陽性率をテストする
次のテストはBunでそのまま実行できます。
import { strict as assert } from "node:assert";
const filter = BloomFilter.fromExpectedItems(1_000, 0.01);
assert.equal(filter.bitSize, 9_586);
assert.equal(filter.hashCount, 7);
assert.equal(filter.bits.byteLength, 1_199);
const inserted = Array.from({ length: 1_000 }, (_, i) => `user:${i}`);
for (const value of inserted) filter.add(value);
for (const value of inserted) {
assert.equal(filter.mightContain(value), true, `false negative: ${value}`);
}
let falsePositives = 0;
const trials = 20_000;
for (let i = 0; i < trials; i++) {
if (filter.mightContain(`absent:${i}`)) falsePositives++;
}
const observedRate = falsePositives / trials;
const estimatedRate = filter.estimateFalsePositiveRate(inserted.length);
assert.ok(observedRate < 0.025, `unexpected FPR: ${observedRate}`);
assert.throws(() => BloomFilter.fromExpectedItems(0, 0.01), RangeError);
assert.throws(() => BloomFilter.fromExpectedItems(100, 1), RangeError);
console.log({
bitSize: filter.bitSize,
hashCount: filter.hashCount,
memoryBytes: filter.bits.byteLength,
falsePositives,
trials,
observedRate,
estimatedRate,
});
実行結果は次でした。
{
bitSize: 9586,
hashCount: 7,
memoryBytes: 1199,
falsePositives: 96,
trials: 20000,
observedRate: 0.0048,
estimatedRate: 0.010034531962677975
}
観測値は入力集合やハッシュ関数で揺れるため、理論値と完全一致することは要求しません。ここでは次の三つを固定しています。
- 追加済み1,000件に偽陰性がないこと
- 観測偽陽性率が異常に高くないこと
- 不正な容量・確率を早い段階で拒否すること
削除を実装してはいけない理由
通常のBloom Filterでbitを0へ戻す削除はできません。同じbitを複数のキーが共有しているため、あるキーの削除でbitを戻すと、別の追加済みキーに偽陰性が発生します。
削除が必要なら、bitの代わりに小さなcounterを持つCounting Bloom Filterを検討します。ただし、メモリ使用量、counterのoverflow、同じキーを何回追加・削除したかという新しい境界が増えます。定期的に元データから再構築できるなら、通常版を作り直す方が単純です。
実運用で先に決めること
容量超過をどう観測するか
追加件数を数え、設計時の expectedItems に近づいたら再構築します。bitの充填率も監視できますが、追加件数と目標偽陽性率をダッシュボードに出す方が説明しやすいです。
更新順序をどうするか
永続ストレージへの書き込みが成功する前にfilterへ追加すると、失敗したキーが偽陽性として残ります。これは偽陰性ではないため正しさは壊しませんが、除外効率が落ちます。通常は永続化成功後に追加します。
複数プロセスでどう共有するか
各workerが別々のfilterを持つと、更新を受け取っていないworkerで偽陰性が起こり得ます。共有filter、更新イベント、定期snapshotなど、同期方法を明示する必要があります。「Bloom Filterには偽陰性がない」という性質は、同じ更新済みfilterを読むことが前提です。
面接で説明する順番
技術面接では、コードから話し始めるより次の順番が伝わりやすいです。
- 目的は「存在しない問い合わせを安く除外すること」と定義する
- 偽陰性なし・偽陽性ありという非対称な契約を説明する
-
nとpからmとkを決める - bitsetとDouble Hashingで計算量を示す
- 削除、容量超過、複数worker同期という障害境界を説明する
計算量は追加・問い合わせともに O(k)、メモリは O(m) です。設計した容量では k を定数とみなせるため、実質的には一定時間で判定できます。
まとめ
Bloom Filterの価値は「少ないメモリで存在を当てる」ことではなく、「存在しないものを確実に落とし、重い問い合わせを減らす」ことにあります。
TypeScript実装では、Uint8Array のbitset、Double Hashing、32-bit演算を組み合わせれば依存なしで構成できます。ただし、本番で説明すべき中心はコードよりも、偽陽性をどこで最終確認するか、容量超過をどう検知するか、複数worker間の更新をどう揃えるかという運用境界です。