Bloom Filter the Misses

Bloom Filter the Misses

Ninety percent of the lookups arriving here are for keys that do not exist, and — this is the part that matters — no two of them are the same. Something is walking a ten-million-key space, one id at a time, and it will not come back.

So caching the misses does nothing. A tombstone is only useful if somebody asks the same question twice, and nobody does. (That is challenge #82; this is deliberately the other case.)

Nine times a second your service asks Redis "have you got this?" (no), asks Postgres "have you got this?" (no), and returns 404. Two network round trips to answer a question about a hundred thousand keys — a set small enough to describe in memory, if you were willing to describe it approximately.

System Architecture

Your task

Answer "no" without asking anybody.

You edit the lookup-api repo (cloned into your dev-vm): app.py. Commit and push; the platform rebuilds and redeploys.

The Postgres image writes every real key to /seed/keys.txt at build time. The app already mounts that file and ignores it — see load_keyset(). pybloom-live is already in requirements.txt.

Two rules constrain the answer. A key that exists must always be found — there is no acceptable rate of losing real data. And a key that gets created must become findable within five seconds, so whatever you build has to learn.

Pass criteria

The grader watches the last minute (five, for the correctness probes). All three must hold:

• Queries reaching the database ≤ 3/second — measured at Postgres. Currently ~10.
• Zero keys that exist but were not found.
• Zero newly created keys still reported missing — after a five-second grace.

Among passing solutions the leaderboard ranks by memory used.

Where to look

• "Queries reaching the database / s" — about the same as your request rate, which means nothing in front of the database is helping.

• From the dev-vm:

  bash

  wc -l /seed/keys.txt          # inside the postgres pod: how big is the real keyset?
  curl -s -o /dev/null -w '%{time_total}\n' http://lookup-api:80/key/ghost-8123791
  

Submit once the database query rate is near 1/second and both correctness probes are clean. Submissions are free, so your best score counts.