Capacity Planning from 500 Million to 10 Billion Items

In one line

Size filters from n (with growth), the target FPR (from the cost of a false positive) and the placement (local copies multiply memory). 500M at 0.1% ≈ 0.9 GB; 1B ≈ 1.8 GB; 10B ≈ 18 GB, which moves the design from a local filter to partitioned, sharded or static-compressed filters.

0/4 · 0%

Think of it like this

Planning warehouse space for a growing business. Doubling stock doubles shelf space, and at some point one warehouse isn't enough and you open regional ones.

Key ideas

01
Choose p from economics: cost per false positive (a database query, a disk read, a user-visible delay) × false positives per second, vs memory cost. Often 0.1% is barely more expensive than 1% and cuts downstream load 10×.
02
Growth headroom: size for n at the next planned rebuild (for example 12 months of growth, or 2× current), or plan periodic rebuilds.
03
Placement multiplies memory: a 1.8 GB filter held locally in 200 instances is 360 GB of RAM; in Redis it's 1.8 GB × replicas.
04
At 10B items: 18 GB at 0.1% per copy. Options: hash-partitioned sub-filters spread across Redis shards, per-shard filters co-located with data, higher FPR (1% → 12 GB), static filters (binary fuse ~14 GB at 0.1%), or tiered designs (hot recent items in a local filter, full set in a shared one).
05
Include operational overhead: 2× memory during zero-downtime rebuilds, snapshot storage and transfer time, and load time on instance start.

Code & diagrams

capacity.txttext

n                target 0.1%          k    local copies x 100      notes
500 million      7.19 Gbit = 0.90 GB  10   90 GB fleet-wide        local filters feasible
1 billion        14.4 Gbit = 1.80 GB  10   180 GB                  consider shared or partitioned
10 billion       144 Gbit  = 18.0 GB  10   1.8 TB (no)             partition across shards / static filter
at 1% instead:   500M 0.60 GB | 1B 1.20 GB | 10B 12.0 GB
rebuild window:  + 1 extra copy while v(n+1) is built and validated

Interview problem

The problem

500 million, then 1 billion, then 10 billion elements

Plan capacity for a membership filter at 500 million elements with a 0.1% target, then 1 billion, then 10 billion. Calculate m, k and memory at each step and explain what architecture changes.

Explain it without notes

How do you choose a target FPR from business requirements?

Practice

Your database handles 5K lookups/sec spare; attack traffic can reach 3M non-member queries/sec. What FPR do you need, and what does it cost for 300M items?

Trade-offs

↔
Bigger filters mean less downstream load; placement and rebuild overhead can dominate memory cost at scale.

Done when you can

I can plan filter capacity end to end, including placement, rebuilds and architecture changes at 10B scale.

Command Palette