Bloom filter (Wikipedia)

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Search, Analytics and Geo · 10 minSeen filtering: Bloom filter versus exact setsHow to avoid showing a user the same item twice in a feed or recommendation list, what a Bloom filter trades away, and how to size the memory.Read hereClose

  The problem

  A feed, a recommendation list or a "discover" page should not show the same item twice. For each user we must answer, quickly, "has this user already seen item X?" for every candidate item, and record what they see. With millions of users and thousands of items each, memory becomes the main constraint.

  100%

  Figure SDA-SAG-10-1 · Where seen filtering sits · © forcsguy.com

  Option 1: exact sets

  Keep, per user, the exact set of seen item ids: a Redis set, a sorted set with a time score so you can trim, or a bitmap if ids are small dense integers. Answers are always right. The cost is memory: 2,000 ids of 8 bytes is 16 KB per user, or about 1.6 TB for 100 million users.

  Option 2: a Bloom filter per user

  A Bloom filter is a bit array and several hash functions. To add an item, set the bits its hashes point to. To test, check those bits: if any is 0, the item was definitely not added; if all are 1, it was probably added.

  • No false negatives: an item that was shown will never be shown again.
  • A small chance of false positives: some fresh items are wrongly treated as seen, so they are skipped.
  • For a 1 percent false-positive rate you need about 9.6 bits per item, so 2,000 items need about 2.4 KB per user, around 240 GB for 100 million users. That is 6 to 7 times smaller.

  100%

  Figure SDA-SAG-10-2 · How a Bloom filter answers · © forcsguy.com

  Sizing: with n items and false-positive rate p, use about m = -n x ln(p) / (ln 2)^2 bits and k = (m / n) x ln 2 hash functions.

  Before: exact set of ids

  100%

  After: Bloom filter

  100%

  What changed

  • Memory per user drops by roughly ten times or more
  • A small share of new items are wrongly treated as seen
  • A filter cannot list or remove what it holds

  Handling time

  Standard Bloom filters cannot delete. Two common fixes:

  • Rotating windows: keep one filter per day or week. Test against all of them; add to the newest; drop the oldest. This also expresses "seen in the last 30 days".
  • Counting Bloom filters use small counters instead of bits so items can be removed, at several times the memory.

  A filter can also be sized for the expected number of items; adding far more than planned makes false positives climb, so create a new filter instead of growing one forever.

  Choosing

  Need	Choice
  Exactness, small sets, explicit "hide this" actions	Exact sets
  Huge user base, soft rule, memory matters	Bloom filter
  Many items per user over a long window	Rotating Bloom filters
  Check across billions of items globally (for example crawled URLs)	Partitioned Bloom filters

  Many systems use both: an exact set for the last few items and the explicit hides, and a Bloom filter for the long tail.

  Real-world reading

  Related reading

  • Bloom filter (Wikipedia)Wikipedia contributors · WikipediaDocumentation
  • Scaling Memcache at Facebook (paper)Nishtala et al. · Meta (Facebook)Papers

  Open this lesson with its quiz and exercise