hesela.devScalable Bloom filter
A scalable Bloom filter grows a chain of membership filters with progressively tighter false-positive budgets as the represented set expands.
Growth: New sub-filters are added as existing ones reach their occupancy limit. A lookup is positive if any sub-filter answers positive. Older filters remain represented; this is growth, not an aging policy that forgets old keys. [1]
Error budget: For a target P and tightening ratio 0 < r < 1, assign sub-filter i the bound P(1-r)r^i, starting at i=0. If those bounds hold for the absent-key query population, the union bound limits the whole chain to P without requiring independent sub-filter errors. Multiplying negative probabilities needs an independence assumption. [1]
Example: For P=1% and r=0.5, the first three budgets are 0.5%, 0.25% and 0.125%. Their sum is 0.875%, leaving 0.125% for all later filters. These are allocated bounds, not measured error rates.
Resource trade-off: More sub-filters consume memory and query work. Larger capacity expansion reduces their number but reserves more space before it is needed. Capacity expansion and error tightening are separate parameters. [1] Documented non-scaling mode rejects additions when capacity is exhausted instead of extending the chain. [2]
Relations
Limitations
- The error budget does not provide a fixed memory ceiling, deletion support or a bound against adaptively chosen queries. [1, 3]
Citations
- Almeida, Baquero, Preguica and Hutchison. Scalable Bloom Filters. IPL 101(6), 2007, pp. 255-261, section 4. DOI: 10.1016/j.ipl.2006.10.007.
- Redis documentation. BF.RESERVE: capacity, expansion, NONSCALING and sub-filter overhead.
- Bender et al. Bloom Filters, Adaptivity, and the Dictionary Problem. arXiv:1711.01616v3 (2018), sections 1-4.
Sources & caveats
- Shipping status reflects documented auto-scaling Bloom-filter support in Redis. The illustrative P and r budget does not specify that implementation's parameter mapping. [2]
- The original paper analyzes partitioned sub-filters and space/growth trade-offs; its plots are not a contemporary storage-engine latency benchmark. [1]
- The 1% example is geometric-series arithmetic. The chain bound assumes valid per-filter error bounds for the same query population, not adversarial robustness. [3]