What is a Bloom filter and where is it used in system design?

A Bloom filter is a bit array with k hash functions that tests set membership using very little memory. It answers either possibly in the set or definitely not. Systems put it in front of expensive operations, such as the SSTable read path in Bigtable and Cassandra, crawler URL dedup, cache-penetration guards and username-taken checks.

Can a Bloom filter give false negatives?

No. Adding an item sets its k bits and nothing clears them, so an added item always reads back as possibly present. Only false positives happen, when other items have set every bit a new item maps to. If your filter returns a false negative, the bug is in your hashing or indexing.

How do I calculate the size and hash count of a Bloom filter?

Use m = -n ln p / (ln 2)^2 for the bits and k = (m / n) ln 2 for the hash functions, where n is the expected item count and p the target false-positive rate. For 1,000,000 items at 1 percent that gives 9,585,059 bits, about 9.585 bits per item, and k of 6.64, rounded to 7. Redis documents the same formulas.

Can you delete an item from a Bloom filter?

Not from the basic version, because clearing one of an item's bits could clear a bit another item needs and create false negatives. A counting Bloom filter replaces bits with counters so deletes work, and a cuckoo filter supports deletion with a different layout. For slowly changing data you can also rebuild the filter on a schedule.

Does Redis support Bloom filters?

Yes. The Redis documentation describes Bloom filter commands including BF.RESERVE, BF.ADD, BF.EXISTS, BF.MADD and BF.MEXISTS, and lists checking whether a username has been taken as a use case. Availability depends on your Redis edition and version, so confirm the commands exist on your server before designing around them.

Bloom Filter Explained: Where It Fits in System Design

A Bloom filter is a bit array plus k hash functions that answers maybe or definitely not. See the m and k formulas, a measured error rate and real uses.

Key Takeaway

A Bloom filter is a bit array plus k hash functions that answers whether an item is possibly in a set or definitely not. It never returns false negatives, and its false-positive rate is tunable, costing about 9.6 bits per item at 1 percent. Systems use it to skip disk reads, duplicate work and cache-miss floods.

Picture a lookup that is nearly always a miss. A product id that was never created, a username nobody has registered, a URL a crawler has not seen. Each miss still walks past the cache and lands on the database, which is the most expensive place to learn that the answer is no.

This post explains the Bloom filter as a way to answer that no cheaply. It covers how the bit array and the k hash functions work, derives m and k from n and p with the arithmetic shown, and runs a TypeScript implementation against 1,000,000 keys to measure the real false-positive rate. The claims about Redis, Cassandra and Bigtable come from their own documentation, linked at the end. The web crawler and key-value store design posts on this site both lean on Bloom filters; this one is the deep dive they point at.

What is a Bloom filter, and what does it promise?

A Bloom filter is a space-efficient probabilistic data structure that tests whether an element is a member of a set. Burton Bloom described it in 1970. Its answer has exactly two forms: possibly in the set, or definitely not in the set. False positives are possible and false negatives are not.

That asymmetry is the whole design. A definite no is safe to act on, so you skip the expensive lookup. A maybe is only a hint, so you still do the real lookup and accept that sometimes it finds nothing. The filter stores no items at all, only bits, which is why it can be small. The price is that it cannot list what it holds and, in its basic form, cannot forget anything.

How does a Bloom filter store and check an item?

The structure is an array of m bits, all zero at the start, plus k hash functions that each map an item to one position in that array. There are only two operations.

To add an item, hash it with all k functions and set the k bits at those positions to 1. A bit that is already 1 stays 1.
To check an item, hash it the same way and read the k bits. If any of them is 0, the item was never added, so the answer is definitely not.
If all k bits are 1, the answer is possibly present. Those bits may have been set by the item itself, or by a mix of other items that happened to cover the same positions.

A false negative is impossible because adding an item sets its bits and nothing ever clears them. A false positive happens when other items have, by chance, set every one of the k bits a new item maps to. The fuller the array gets, the more likely that is, which is why the false-positive rate climbs as you add more items than the filter was sized for.

How do you choose the bit count m and hash count k?

You pick two inputs, the number of items n you expect and the false-positive rate p you can tolerate, and two formulas give the rest. The optimal bit count is m = -n ln p divided by (ln 2) squared, and the optimal hash count is k = (m / n) ln 2. Redis publishes the same formulas in its Bloom filter documentation. Here are the numbers for 1,000,000 items at 1 percent, computed with the formulas rather than looked up.

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 1

The result matches the published figures: Redis quotes 9.585 bits per item and 7 hash functions at a 1 percent error rate, and Wikipedia gives about 9.6 bits per element. Notice how cheap the next step down is: a tenfold lower error rate costs only about 4.8 more bits per item, so most of the memory goes into the first few percent of accuracy. The last block of the arithmetic is the one to remember. A filter sized for 1,000,000 items and fed 2,000,000 does not fail, it quietly drifts from 1 percent to about 15.7 percent.

Size n for the number of items you will have in a year, not today. Redis reserves a filter with BF.RESERVE key error_rate capacity, and its documentation says that outgrowing the capacity either stacks a new sub-filter, which makes checks slower, or lets the error rate grow if you chose NONSCALING.

Does a real Bloom filter hit its false-positive target?

I wrote the smallest version I could in TypeScript and measured it. It inserts the keys user:0 to user:999999 for n = 1,000,000, then probes with the keys ghost:0 to ghost:999999, none of which was ever inserted. Every positive on a ghost key is a false positive. It derives k hash functions from one SHA-256 digest by double hashing, a standard technique that avoids computing k separate hashes. It runs on Node 26, which executes .ts files directly. The keys are fixed strings, so there is no random seed and the run is repeatable.

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 of that exact run, on Node v26.10.0. These are measurements of this demo, not a benchmark of any production library.

$ 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%

All three configurations had 0 false negatives across the 1,000,000 inserted keys, which is the guarantee. The measured false-positive rates of 10.099 percent, 1.007 percent and 0.095 percent sit close to the 10, 1 and 0.1 percent targets, and the sizes match the formulas, with 1,170.1 KiB for the 1 percent filter. The 1 percent filter holds a million items in about 1.1 MiB.

My first run printed hundreds of thousands of false negatives, which should be impossible. The cause was one line: a bitwise OR in JavaScript returns a signed 32-bit integer, so about half of the strides came out negative and produced negative bit positions. The fix is the unsigned shift shown in the code. If your filter ever reports a false negative, the bug is in your hashing or indexing, never in the theory.

Where do real systems use Bloom filters?

Every real use has the same shape: a cheap membership test sits in front of an expensive operation, and a wrong maybe only wastes that operation once. The table lists the four uses that come up most in system design.

Use case	What the filter answers	What a false positive costs
LSM storage read path (Bigtable, Cassandra)	Might this SSTable hold the requested row or partition?	One wasted disk read of a file that does not have the row
Web crawler URL dedup	Has this URL possibly been crawled already?	A new URL wrongly skipped, so one page is never fetched
Cache-penetration guard	Does this id exist at all?	One cache miss and one database query, the same as having no filter
Username or email taken check	Is this name possibly registered already?	A database check, or a name rejected that was actually free

The Bigtable paper describes the storage case. Clients can ask for Bloom filters on the SSTables of a locality group, and the authors write that a filter lets a tablet server ask whether an SSTable might contain data for a row and column pair, so most lookups for non-existent rows or columns do not need to touch disk. Cassandra does the same per SSTable, and the DataStax documentation exposes it as the table setting bloom_filter_fp_chance, a value from 0 to 1.0 where 1.0 disables the filter. Higher values use less memory but cause more disk I/O when SSTables are fragmented, and the filters are not used for range scans. For crawler dedup, the arithmetic is the same as section three: 1,000,000,000 URLs at 1 percent is 9.585059 bits each, or 1,198,132,375 bytes, about 1.12 GiB. Storing the URLs themselves at an assumed 80 bytes each would be 80,000,000,000 bytes.

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;
}

The cache-penetration guard is the one I would reach for first on a single VPS with Redis already running, because Redis ships Bloom filter commands. Its documentation lists BF.RESERVE, BF.ADD, BF.EXISTS and the multi-item BF.MADD and BF.MEXISTS, and names checking whether a username has been taken as a typical use. The sketch below assumes the Bloom filter commands are available on your Redis server; confirm that for your edition and version before depending on it. It also assumes you keep the filter in step with the table by calling BF.ADD on every create.

Can you delete from a Bloom filter, and what replaces it?

Not from the basic version. Clearing one of an item's k bits could also clear a bit that other items rely on, which would create false negatives, the one error the structure promises never to make. When you need removal, there are three directions.

Structure	Delete items	False positives	Memory and trade-off
Bloom filter	No	Yes, tunable	About 9.6 bits per item at 1 percent, according to Wikipedia. Faster inserts than a cuckoo filter, per Redis.
Counting Bloom filter	Yes	Yes, tunable	Each bit becomes a multibit counter, so it costs more memory than one bit per slot.
Cuckoo filter	Yes	Yes, tunable	The authors report lower space overhead than space-optimised Bloom filters for many items at moderately low rates. Redis says checks are quicker.
Exact hash set	Yes	None	Stores the items themselves. Redis estimates about 40 bytes, or 320 bits, per IP address in a set.

The counting variant replaces each bit with a counter that is incremented on add and decremented on delete. The cuckoo filter, from the paper by Fan, Andersen, Kaminsky and Mitzenmacher, is a different structure that supports adding and removing items. The pragmatic third option is to rebuild: for data that changes slowly, such as a daily job, build a fresh filter from the source of truth and swap it in.

When should you skip a Bloom filter?

A Bloom filter is easy to add and easy to get subtly wrong. Run through this checklist before you do.

Is the check usually a miss? A filter only saves work when most queries are for items that are absent. If most are present, it adds a step and saves nothing.
Can the next step tolerate a wrong maybe? The false positive must lead to a harmless extra lookup, never to a wrong answer shown to a user.
Do you know n? Without a stable estimate of the item count, the false-positive rate drifts as in the 15.7 percent example, so use a scalable or rebuilt filter.
Do you need deletes or a list of members? If yes, use a cuckoo filter, a counting filter or an exact set.
Is an exact set affordable? For small data, a hash set has no false positives. Measure the memory before reaching for a probabilistic structure.

A Bloom filter trades a small, tunable chance of a wasted lookup for a large cut in memory, and it never loses an item you added. Derive m and k from n and p, remember that going past n degrades the error rate, and place it only in front of an expensive operation that tolerates a harmless wrong maybe.

Sources and further reading

Frequently Asked Questions

Bloom Filter Explained: Where It Fits in System Design

Frequently Asked Questions

Bloom Filter Explained: Where It Fits in System Design

What is a Bloom filter, and what does it promise?

How does a Bloom filter store and check an item?

How do you choose the bit count m and hash count k?

Does a real Bloom filter hit its false-positive target?

Where do real systems use Bloom filters?

Can you delete from a Bloom filter, and what replaces it?

When should you skip a Bloom filter?

What is a Bloom filter, and what does it promise?

How does a Bloom filter store and check an item?

How do you choose the bit count m and hash count k?

Does a real Bloom filter hit its false-positive target?

Where do real systems use Bloom filters?

Can you delete from a Bloom filter, and what replaces it?

When should you skip a Bloom filter?