Seen filtering: Bloom filter versus exact sets

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.

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