Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Bloom filter adalah bit array plus k hash function yang menjawab mungkin ada atau pasti tidak ada. Lihat rumus m dan k, error rate terukur, dan pemakaiannya.
Matthews Wong
Software Engineer
Ringkasan Utama
Bloom filter adalah bit array plus k hash function yang menjawab apakah sebuah item mungkin ada di dalam set atau pasti tidak ada. Ia tidak pernah memberi false negative, dan false-positive rate bisa diatur, dengan biaya sekitar 9,6 bit per item untuk 1 persen. Sistem memakainya untuk melewati disk read, kerja duplikat, dan banjir cache miss.
Bayangkan lookup yang hampir selalu miss. Product id yang tidak pernah dibuat, username yang belum didaftarkan siapa pun, URL yang belum pernah dilihat crawler. Setiap miss tetap melewati cache lalu sampai ke database, padahal itu tempat paling mahal untuk mengetahui bahwa jawabannya tidak.
Tulisan ini menjelaskan Bloom filter sebagai cara murah untuk menjawab tidak itu. Isinya cara kerja bit array dan k hash function, penurunan m dan k dari n dan p lengkap dengan hitungannya, lalu implementasi TypeScript yang dijalankan terhadap 1.000.000 key untuk mengukur false-positive rate yang sebenarnya. Klaim tentang Redis, Cassandra, dan Bigtable berasal dari dokumentasi resminya, tertaut di bagian akhir. Tulisan web crawler dan key-value store di situs ini sama-sama bersandar pada Bloom filter; tulisan ini adalah pembahasan lengkapnya.
Bloom filter adalah struktur data probabilistik yang hemat ruang untuk menguji apakah sebuah elemen anggota suatu set. Burton Bloom menjelaskannya pada 1970. Jawabannya hanya punya dua bentuk: mungkin ada di dalam set, atau pasti tidak ada. False positive mungkin terjadi, false negative tidak.
Ketidaksimetrisan itulah inti desainnya. Jawaban pasti tidak aman untuk ditindaklanjuti, jadi lookup yang mahal bisa dilewati. Jawaban mungkin hanyalah petunjuk, jadi Anda tetap melakukan lookup sungguhan dan menerima bahwa kadang hasilnya kosong. Filter ini sama sekali tidak menyimpan item, hanya bit, sehingga ukurannya bisa kecil. Harganya, ia tidak bisa menampilkan isinya dan, dalam bentuk dasar, tidak bisa melupakan apa pun.
Strukturnya adalah array berisi m bit yang semuanya nol di awal, ditambah k hash function yang masing-masing memetakan item ke satu posisi di array itu. Hanya ada dua operasi.
False negative mustahil karena menambah item men-set bit-nya dan tidak ada yang pernah menghapusnya. False positive terjadi ketika item lain kebetulan sudah men-set semua k bit yang dituju item baru. Makin penuh array, makin besar kemungkinannya, itulah sebabnya false-positive rate naik saat Anda memasukkan lebih banyak item dari ukuran yang direncanakan.
Anda memilih dua input, jumlah item n yang diharapkan dan false-positive rate p yang masih bisa diterima, lalu dua rumus memberi sisanya. Jumlah bit optimal adalah m = -n ln p dibagi (ln 2) kuadrat, dan jumlah hash optimal adalah k = (m / n) ln 2. Redis menerbitkan rumus yang sama di dokumentasi Bloom filter-nya. Berikut angka untuk 1.000.000 item pada 1 persen, dihitung dengan rumus, bukan dicari di tabel.
Inputs: n = 1,000,000 items, target false-positive rate p = 0.01
m = -n x ln(p) / (ln 2)^2
= -1,000,000 x (-4.605170) / 0.480453
= 9,585,059 bits (rounded up)
= 9.585 bits per item
= 1,198,132 bytes = 1,170.1 KiB
k = (m / n) x ln 2
= 9.585059 x 0.693147
= 6.644 -> 7 hash functions
Check the p you actually get with k = 7:
p = (1 - e^(-k n / m))^k
= (1 - e^(-0.7303))^7
= 0.51824^7
= 0.01004 (about 1.0 percent, as designed)
Same n, other targets (same two formulas):
p = 0.1 -> 4,792,530 bits (4.79 bits per item) k = 3
p = 0.001 -> 14,377,588 bits (14.38 bits per item) k = 10
Overfill the 1 percent filter to 2,000,000 items (it was sized for 1,000,000):
p = (1 - e^(-7 x 2,000,000 / 9,585,059))^7 = 0.157 -> 15.7 percent, not 1Hasilnya cocok dengan angka yang dipublikasikan: Redis menyebut 9,585 bit per item dan 7 hash function pada error rate 1 persen, dan Wikipedia menyebut sekitar 9,6 bit per elemen. Perhatikan betapa murahnya langkah berikutnya: error rate sepuluh kali lebih rendah hanya butuh sekitar 4,8 bit tambahan per item, jadi sebagian besar memori terpakai untuk beberapa persen akurasi pertama. Blok terakhir dalam hitungan itu yang perlu diingat. Filter yang dirancang untuk 1.000.000 item lalu diisi 2.000.000 tidak gagal, ia diam-diam bergeser dari 1 persen ke sekitar 15,7 persen.
Tentukan n berdasarkan jumlah item setahun ke depan, bukan hari ini. Redis membuat filter dengan BF.RESERVE key error_rate capacity, dan dokumentasinya menyebut bahwa melewati capacity akan menumpuk sub-filter baru yang membuat pengecekan lebih lambat, atau membiarkan error rate naik jika Anda memilih NONSCALING.
Saya menulis versi sekecil mungkin dalam TypeScript lalu mengukurnya. Kode ini memasukkan key user:0 sampai user:999999 untuk n = 1.000.000, lalu memeriksa dengan key ghost:0 sampai ghost:999999 yang tidak pernah dimasukkan. Setiap hasil positif pada key ghost adalah false positive. Ia menurunkan k hash function dari satu digest SHA-256 lewat double hashing, teknik standar yang menghindari penghitungan k hash terpisah. Kode berjalan di Node 26 yang bisa mengeksekusi file .ts langsung. Key-nya string tetap, jadi tidak ada random seed dan hasilnya bisa diulang.
import { createHash } from "node:crypto";
// Sizing from the two standard formulas.
function size(n: number, p: number) {
const m = Math.ceil((-n * Math.log(p)) / Math.LN2 ** 2); // bits
const k = Math.max(1, Math.round((m / n) * Math.LN2)); // hash functions
return { m, k };
}
class BloomFilter {
readonly bits: Uint8Array;
readonly m: number;
readonly k: number;
constructor(m: number, k: number) {
this.m = m;
this.k = k;
this.bits = new Uint8Array(Math.ceil(m / 8));
}
// Double hashing: two 32-bit hashes from one SHA-256, then h1 + i*h2 mod m
// stands in for k independent hash functions (Kirsch-Mitzenmacher).
private positions(key: string): number[] {
const d = createHash("sha256").update(key).digest();
const h1 = d.readUInt32LE(0);
// Odd, so the stride never collapses. The >>> 0 matters: "| 1" yields a SIGNED
// 32-bit int, so half of all keys got a negative stride and negative indices.
const h2 = (d.readUInt32LE(4) | 1) >>> 0;
return Array.from({ length: this.k }, (_, i) => (h1 + i * h2) % this.m);
}
add(key: string) {
for (const p of this.positions(key)) this.bits[p >> 3] |= 1 << (p & 7);
}
mightContain(key: string) {
return this.positions(key).every(
(p) => (this.bits[p >> 3] & (1 << (p & 7))) !== 0,
);
}
}
const N = 1_000_000; // inserted keys: "user:0" .. "user:999999"
const PROBES = 1_000_000; // never inserted: "ghost:0" .. "ghost:999999"
console.log("node", process.version, "n =", N, "probes =", PROBES);
for (const p of [0.1, 0.01, 0.001]) {
const { m, k } = size(N, p);
const bf = new BloomFilter(m, k);
for (let i = 0; i < N; i++) bf.add(`user:${i}`);
let falseNegatives = 0;
for (let i = 0; i < N; i++)
if (!bf.mightContain(`user:${i}`)) falseNegatives++;
let falsePositives = 0;
for (let i = 0; i < PROBES; i++)
if (bf.mightContain(`ghost:${i}`)) falsePositives++;
console.log(
`target p=${p} m=${m} bits (${(m / 8 / 1024).toFixed(1)} KiB) bits/item=${(m / N).toFixed(3)} k=${k}` +
` false negatives=${falseNegatives} false positives=${falsePositives}/${PROBES} = ${((falsePositives / PROBES) * 100).toFixed(3)}%`,
);
}Output dari run persis itu, di Node v26.10.0. Ini adalah pengukuran demo ini, bukan benchmark library produksi mana pun.
$ node bloom-demo.ts
node v26.10.0 n = 1000000 probes = 1000000
target p=0.1 m=4792530 bits (585.0 KiB) bits/item=4.793 k=3 false negatives=0 false positives=100994/1000000 = 10.099%
target p=0.01 m=9585059 bits (1170.1 KiB) bits/item=9.585 k=7 false negatives=0 false positives=10070/1000000 = 1.007%
target p=0.001 m=14377588 bits (1755.1 KiB) bits/item=14.378 k=10 false negatives=0 false positives=952/1000000 = 0.095%Ketiga konfigurasi menghasilkan 0 false negative dari 1.000.000 key yang dimasukkan, dan itulah jaminannya. False-positive rate terukur 10,099 persen, 1,007 persen, dan 0,095 persen, dekat dengan target 10, 1, dan 0,1 persen, dan ukurannya cocok dengan rumus, yaitu 1.170,1 KiB untuk filter 1 persen. Filter 1 persen menampung sejuta item dalam sekitar 1,1 MiB.
Run pertama saya mencetak ratusan ribu false negative, padahal itu mustahil. Penyebabnya satu baris: operator OR bitwise di JavaScript mengembalikan integer 32-bit bertanda, sehingga sekitar separuh stride bernilai negatif dan menghasilkan posisi bit negatif. Perbaikannya adalah unsigned shift yang terlihat di kode. Jika filter Anda pernah melaporkan false negative, bug-nya ada di hashing atau indexing, bukan di teorinya.
Setiap pemakaian nyata punya bentuk yang sama: tes keanggotaan yang murah berdiri di depan operasi mahal, dan jawaban mungkin yang keliru hanya menyia-nyiakan operasi itu sekali. Tabel berikut memuat empat pemakaian yang paling sering muncul di system design.
| Kasus pemakaian | Pertanyaan yang dijawab filter | Biaya sebuah false positive |
|---|---|---|
| Read path penyimpanan LSM (Bigtable, Cassandra) | Mungkinkah SSTable ini memuat row atau partition yang diminta? | Satu disk read sia-sia pada file yang tidak punya row itu |
| Dedup URL pada web crawler | Mungkinkah URL ini sudah pernah di-crawl? | URL baru terlewat secara keliru, jadi satu halaman tidak pernah diambil |
| Pelindung cache penetration | Apakah id ini benar-benar ada? | Satu cache miss dan satu query database, sama seperti tanpa filter |
| Pengecekan username atau email sudah dipakai | Mungkinkah nama ini sudah terdaftar? | Satu pengecekan database, atau nama yang ditolak padahal sebenarnya masih bebas |
Paper Bigtable menjelaskan kasus penyimpanan. Client bisa meminta Bloom filter untuk SSTable dalam sebuah locality group, dan penulisnya menyebut filter memungkinkan tablet server bertanya apakah sebuah SSTable mungkin memuat data untuk pasangan row dan kolom tertentu, sehingga sebagian besar lookup untuk row atau kolom yang tidak ada tidak perlu menyentuh disk. Cassandra melakukan hal yang sama per SSTable, dan dokumentasi DataStax mengeksposnya sebagai setelan tabel bloom_filter_fp_chance, nilai 0 sampai 1,0 dengan 1,0 berarti filter dimatikan. Nilai lebih tinggi memakai lebih sedikit memori tetapi menambah disk I/O ketika SSTable terfragmentasi, dan filter tidak dipakai untuk range scan. Untuk dedup crawler, hitungannya sama seperti bagian ketiga: 1.000.000.000 URL pada 1 persen adalah 9,585059 bit per URL, atau 1.198.132.375 byte, sekitar 1,12 GiB. Menyimpan URL-nya sendiri dengan asumsi 80 byte per URL berarti 80.000.000.000 byte.
import Redis from "ioredis";
const redis = new Redis();
const FILTER = "products:known-ids";
// Once, at deploy time: 0.001 error rate, room for 1,000,000 ids (BF.RESERVE key error_rate capacity).
// await redis.call("BF.RESERVE", FILTER, "0.001", "1000000");
export async function getProduct(id: string) {
// BF.EXISTS answers 0 = definitely never added, 1 = probably added.
const maybe = Number(await redis.call("BF.EXISTS", FILTER, id));
if (maybe === 0) return null; // no cache lookup, no database query, no false negative possible
const cached = await redis.get(`product:${id}`);
if (cached) return JSON.parse(cached);
const row = await db.product.findUnique({ where: { id } }); // a false positive costs only this miss
if (row) await redis.set(`product:${id}`, JSON.stringify(row), "EX", 300);
return row;
}
// On every create: BF.ADD keeps the filter in step with the table.
export async function createProduct(data: ProductInput) {
const row = await db.product.create({ data });
await redis.call("BF.ADD", FILTER, row.id);
return row;
}Pelindung cache penetration adalah yang pertama akan saya pakai di satu VPS yang sudah menjalankan Redis, karena Redis menyediakan perintah Bloom filter. Dokumentasinya mencantumkan BF.RESERVE, BF.ADD, BF.EXISTS serta BF.MADD dan BF.MEXISTS untuk banyak item, dan menyebut pengecekan apakah username sudah dipakai sebagai contoh pemakaian khas. Sketsa di bawah mengasumsikan perintah Bloom filter tersedia di server Redis Anda; pastikan itu untuk edisi dan versi Anda sebelum bergantung padanya. Sketsa itu juga mengasumsikan Anda menjaga filter tetap sinkron dengan tabel dengan memanggil BF.ADD pada setiap create.
Tidak bisa pada versi dasar. Mengosongkan salah satu dari k bit sebuah item bisa ikut mengosongkan bit yang dipakai item lain, dan itu menciptakan false negative, satu-satunya error yang dijanjikan tidak akan pernah terjadi. Jika Anda butuh penghapusan, ada tiga arah.
| Struktur | Hapus item | False positive | Memori dan trade-off |
|---|---|---|---|
| Bloom filter | Tidak | Ada, bisa diatur | Sekitar 9,6 bit per item pada 1 persen menurut Wikipedia. Insert lebih cepat daripada cuckoo filter, menurut Redis. |
| Counting Bloom filter | Ya | Ada, bisa diatur | Setiap bit menjadi counter multibit, jadi memorinya lebih besar daripada satu bit per slot. |
| Cuckoo filter | Ya | Ada, bisa diatur | Penulisnya melaporkan overhead ruang lebih rendah daripada Bloom filter yang dioptimalkan untuk banyak item pada rate yang cukup rendah. Redis menyebut pengecekannya lebih cepat. |
| Hash set eksak | Ya | Tidak ada | Menyimpan itemnya sendiri. Redis memperkirakan sekitar 40 byte, atau 320 bit, per alamat IP dalam sebuah set. |
Varian counting mengganti setiap bit dengan counter yang bertambah saat add dan berkurang saat delete. Cuckoo filter, dari paper Fan, Andersen, Kaminsky, dan Mitzenmacher, adalah struktur berbeda yang mendukung penambahan dan penghapusan item. Opsi ketiga yang pragmatis adalah membangun ulang: untuk data yang jarang berubah, seperti job harian, bangun filter baru dari source of truth lalu tukar.
Bloom filter mudah ditambahkan dan mudah salah secara halus. Jalani checklist ini sebelum memakainya.
Bloom filter menukar peluang kecil yang bisa diatur untuk lookup sia-sia dengan penghematan memori yang besar, dan ia tidak pernah kehilangan item yang sudah Anda tambahkan. Turunkan m dan k dari n dan p, ingat bahwa melewati n merusak error rate, dan tempatkan hanya di depan operasi mahal yang menoleransi jawaban mungkin yang keliru tapi tidak berbahaya.