Replacing SQL with Redis Bloom Filters for Question Recommendations

What Bloom filters are, why they crush membership checks at scale, and how I used Redis Bitfields to answer “has this user already seen this question?” on a 1v1 quiz hot path.

May 26, 2026 · 9 min read

A surprising amount of backend work comes down to one question:

Has this user already seen this item?

Feeds, recommendations, quizzes, ads — different products, same membership check. At scale, that check is where systems get slow — either because you store too much, or because you query a growing history table on every request.

Arpit Bhayani’s essay on Bloom filters is one of the clearest end-to-end writeups of the data structure. This post borrows that framing, then zooms into a production problem I had to solve: when two learners match in a 1v1 quiz, pick questions that neither has already seen, without paying SQL membership cost on the hot path.

Why this problem eats memory and latency

Exact membership is simple: keep every seen ID in a set (or a row in a table). It is also expensive.

Arpit’s recommendation example makes the memory case vivid: millions of users × thousands of seen items × ID storage + hash-set overhead lands you in hundreds of gigabytes of RAM if you materialize exact sets for everyone. A Bloom filter stores existence, not IDs — typically on the order of ~10 bits per element for ~1% false positives — and can cut that footprint by an order of magnitude.

My constraint was slightly different. We already had exact history in SQL. The pain was latency and blast radius:

the membership table was huge and still growing
every match joined candidates against that history (often through a stored procedure with fallbacks)
spikes contended with other features on the same database

So the win I needed was not only “use less RAM.” It was “answer membership without touching the giant table on every match.”

What a Bloom filter answers

A Bloom filter is a probabilistic set. Given an element, it says:

Definitely not in the set, or
Probably in the set (with a tunable false-positive rate)

It never produces false negatives. If something was inserted, a lookup will never claim it is absent. It can produce false positives: claiming something might be present when it is not.

That tradeoff is perfect for recommendations and quizzes. If the filter says a question might have been seen, skip it or fall back. The cost of a false positive is a slightly smaller candidate pool. The cost of a false negative would be showing a question the user already attempted — which a Bloom filter will not do.

Structure

Two ingredients:

A bit array of length m (all zeros at start)
k hash functions, each mapping an input to a position in [0, m)

add(x):
  for i in 1..k:
    bit_array[hash_i(x) % m] = 1

contains(x):
  for i in 1..k:
    if bit_array[hash_i(x) % m] == 0:
      return false   # definitely not seen
  return true        # probably seen

Concrete intuition (same idea as Arpit’s apple/banana/cherry example): after a few inserts, unrelated items can collide on already-set bits and look “present.” That is the false positive — not a bug, the price of compression.

A useful product analogy

Imagine a user who has watched 1,000 reels on Instagram, on a platform with a billion users. Recommending the next reel is hard. Knowing whether this user has already seen this reel is harder still — and you cannot afford a full history scan on every request.

Same shape of problem. Different product.

The math that actually matters

After inserting n elements with k hashes into m bits, the false-positive rate is roughly:

p ≈ (1 - e^(-kn/m))^k

Two useful design rules (standard Bloom filter results):

k_optimal ≈ (m/n) * ln(2)
m/n      ≈ -ln(p) / (ln(2))^2     // ~9.6 bits/element for p=1%, ~14.4 for p=0.1%

function bloomParams(n: number, p: number) {
  const m = Math.ceil(-(n * Math.log(p)) / Math.log(2) ** 2);
  const k = Math.max(1, Math.round((m / n) * Math.log(2)));
  return { m, k };
}

Formulas give a starting point. Production still needs your real n distribution. In my case, usage was heavily skewed: typical learners attempted on the order of tens of questions in a month; power users were in the thousands. Sizing only for the median wastes accuracy; sizing only for p99 wastes memory.

Hashing: you usually do not need `k` independent hashes

A common production trick (Kirsch–Mitzenmacher / double hashing) is to compute two hashes and derive the rest:

g_i(x) = h1(x) + i * h2(x)   (mod m)

That keeps CPU cheap while preserving the asymptotic false-positive behavior. Implementation detail that bites: keep the step (h2) from degenerating (e.g. force it odd when m is a power of two) so positions do not collapse. RocksDB and others have hit this in the wild; Arpit covers the nuance well in his hashing section.

The problem on the quiz hot path

After two learners matched, the backend had to pick a small set of questions quickly.

The expensive part was not ranking. It was:

For each candidate question, has learner A already seen it? Has learner B already seen it?

Before (hot path)

  Match formed
       │
       ▼
  SQL membership joins + fallbacks
       │
       ▼
  Questions  (slow, contended DB)

After

  Match formed
       │
       ▼
  Cached candidates
       │
       ▼
  Redis Bloom(A) + Redis Bloom(B)
       │
       ▼
  Keep questions definitely unseen by both

Why not Redis Sets / cache / RedisBloom module?

Redis Sets — exact, but memory grows with every ID for every user (back to the “store the set” problem).
Cached SQL — misses reintroduce the original latency; you are still coupled to the table shape.
RedisBloom module — clean API, but it was not available on the Redis tier we were running.

So I implemented the filter with Redis Bitfields: get/set individual bits at an offset, pipelined for the k positions per lookup.

const K = 4;
 
function hashPositions(questionId: string, m: number): number[] {
  // Prefer double-hashing in production; outline only.
  return Array.from({ length: K }, (_, i) => hash(questionId, i) % m);
}
 
async function bloomMightContain(
  redis: Redis,
  userKey: string,
  questionId: string,
  m: number,
): Promise<boolean> {
  const positions = hashPositions(questionId, m);
  const pipeline = redis.pipeline();
  for (const offset of positions) {
    pipeline.call("BITFIELD", userKey, "GET", "u1", `#${offset}`);
  }
  const bits = await pipeline.exec();
  return bits.every((bit) => Number(bit) === 1);
}

Choosing `k` and `m` for skewed users

I estimated false-positive rates across (k, m) for expected insert counts, then validated against usage percentiles.

What I landed on:

k = 4 — good tradeoff for our insert counts and acceptable FP rate (not always the textbook optimum; fixed k kept the implementation simple)
Default m = 2048 bits (2¹¹) — for roughly ~100 inserts, estimated FP rate was around 0.001%, fine for skipping candidates
Store the size exponent in the first few bits of each user’s key so the runtime can recover m = 2^exponent without a second key

const DEFAULT_EXPONENT = 11; // 2^11 = 2048
 
async function readSizeExponent(redis: Redis, userKey: string): Promise<number> {
  const exp = await redis.call("BITFIELD", userKey, "GET", "u5", "#0");
  return Number(exp?.[0] ?? DEFAULT_EXPONENT);
}

Grow the filter instead of over-provisioning

Standard Bloom filters do not support deletes cleanly (bits are shared). Variants like counting Bloom filters exist — Arpit walks through them — but I did not need deletes. I needed capacity growth.

Compromise:

Start small (2048 bits)
Track fill
When roughly half full, double m and re-insert that user’s known question IDs

Re-insertion is required because hash positions depend on m.

async function maybeResize(
  redis: Redis,
  userKey: string,
  knownQuestionIds: string[],
  setBits: number,
  exponent: number,
) {
  const m = 2 ** exponent;
  if (setBits / m < 0.5) return { exponent, m };
 
  const nextExponent = exponent + 1;
  const nextM = 2 ** nextExponent;
  await redis.del(userKey);
  await redis.call("BITFIELD", userKey, "SET", "u5", "#0", nextExponent);
  for (const id of knownQuestionIds) {
    await bloomAdd(redis, userKey, id, nextM);
  }
  return { exponent: nextExponent, m: nextM };
}

Formulas chose a sensible default. The resize policy made the system survive real skew.

Request path (outline)

                 ┌─────────────────────┐
  attempt event  │  async Bloom insert │
 ───────────────►│  for that learner   │
                 └─────────────────────┘
                            ▲
                 ┌──────────┴──────────┐
  match formed   │  candidate cache    │
 ───────────────►│  + Bloom A & B      │──► unseen-by-both
                 └─────────────────────┘

Cache a candidate pool so you are not scanning the full catalog every match
Load both learners’ filters
Keep questions that are definitely unseen by both
If a user’s m is not the default, recompute hash positions for that length
Fall back gradually if the ideal set is too thin

On writes, attempt events asynchronously insert into the learner’s filter. Freshness is part of correctness.

I also precomputed hash positions for the default m on cached candidates — most users stayed on the default size, so most matches avoided rehashing.

function selectUnseenByBoth(
  candidates: string[],
  mightHaveSeenA: (id: string) => boolean,
  mightHaveSeenB: (id: string) => boolean,
) {
  return candidates.filter((id) => !mightHaveSeenA(id) && !mightHaveSeenB(id));
}

Results

Question-fetch latency dropped to roughly one-third of the previous baseline (~60% reduction).

Operationally:

membership left the giant SQL path
matchmaking stopped waiting on heavy joins
memory scaled with how much each user actually attempted

Tradeoffs

False positives are a product decision. Skipping a valid unseen item is fine only with enough candidates and a fallback.

Resizing is correct but not free. Doubling + re-insert is the price of not over-provisioning.

Bloom filters do not replace ranking. They answer membership. Ranking is a separate concern.

No deletes in the classic structure. If you need removals, look at counting / deletable variants — again, Arpit’s post is a good map of that space. I needed growth, not deletion.

Freshness matters. Stale inserts make a perfect filter wrong.