Source-linked AI summary
Don't Thrash: How to Cache Your Hash on Flash
Michael A. Bender, Martin Farach-Colton, Rob Johnson, Russell Kraner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, Erez Zadok
TL;DR
Bloom filters’ random reads and writes make them poorly suited to sets larger than RAM. The paper develops quotient-filter-based RAM and SSD structures with better locality, and reports substantially faster insertions than Bloom-filter variants with comparable or better lookup performance. The cascade filter scales better than the buffered quotient filter, while the buffered quotient filter is more query-optimized.
Problem
Bloom filters are widely used for membership queries, but random reads and writes make them perform poorly on external storage and limit set sizes beyond RAM.
Method
The paper develops a quotient filter and builds buffered quotient and cascade filters on it as RAM- and SSD-oriented alternatives to Bloom filters.
Results
The quotient-filter-based structures dramatically outperform Bloom-filter variants for insertions while offering comparable or superior lookup performance.
Takeaways & Limitations
The cascade filter is more scalable for large filter-to-RAM ratios, whereas the buffered quotient filter is more optimized for queries.
Takeaways & Limitations
The evaluation used only one Flash disk, and the authors note performance variations across disks and storage configurations.
Abstract
from arXiv · showhide
This paper presents new alternatives to the well-known Bloom filter data structure. The Bloom filter, a compact data structure supporting set insertion and membership queries, has found wide application in databases, storage systems, and networks. Because the Bloom filter performs frequent random reads and writes, it is used almost exclusively in RAM, limiting the size of the sets it can represent. This paper first describes the quotient filter, which supports the basic operations of the Bloom filter, achieving roughly comparable performance in terms of space and time, but with better data locality. Operations on the quotient filter require only a small number of contiguous accesses. The quotient filter has other advantages over the Bloom filter: it supports deletions, it can be dynamically resized, and two quotient filters can be efficiently merged. The paper then gives two data structures, the buffered quotient filter and the cascade filter, which exploit the quotient filter advantages and thus serve as SSD-optimized alternatives to the Bloom filter. The cascade filter has better asymptotic I/O performance than the buffered quotient filter, but the buffered quotient filter outperforms the cascade filter on small to medium data sets. Both data structures significantly outperform recently-proposed SSD-optimized Bloom filter variants, such as the elevator Bloom filter, buffered Bloom filter, and forest-structured Bloom filter. In experiments, the cascade filter and buffered quotient filter performed insertions 8.6-11 times faster than the fastest Bloom filter variant and performed lookups 0.94-2.56 times faster.
1. INTRODUCTION
Bloom filters support approximate membership queries but become impractical when their random-access workload exceeds RAM and reaches external storage.
- Databases, storage systems, and network protocols use Bloom filters to quickly identify elements absent from databases, external storage, or remote hosts.
- Bloom filters support insertion and membership queries while allowing tunable false-positive rates in a compact representation.For absent keys, lookup returns “absent” with probability at least 1 −ε.
- Bloom filters work well in main memory but their random reads and writes scale poorly to flash once the structure exceeds RAM.Standard Bloom filters use about one byte per stored item; counting Bloom filters require roughly four times more space.
Results
The evaluation compares quotient-filter-based structures with Bloom filters and SSD-oriented Bloom variants, finding strong insertion advantages and workload-dependent trade-offs between BQF and CF.
- The QF, BQF, and CF provide Bloom-filter functionality with better data locality, while supporting deletions.The QF targets RAM; the BQF and CF target SSDs.
- The CF is asymptotically more efficient for insertions, whereas the BQF is slightly more optimized for queries.
- QF insertions outperform Bloom-filter insertions by 1.3× to 2.5×, while Bloom filters are 1.4×-1.6× faster for uniform random lookups at 75% occupancy.Successful lookups show no clear winner in the in-RAM experiments.
- BQF and CF insert at least 4 times faster than the compared structures, while BQF is at least twice as fast for lookups.On successful lookups, BQF runs roughly 11 times better than EBF and BBF.
- The CF performs 26% faster than the BQF on the largest workload, while BQF outperforms CF for queries by at least 60%.The choice depends on the workload’s ratio of insertions to queries.
- QFs use about 20% more space than BFs at a typical 1% false-positive rate, but support deletion without the Bloom filter’s 4× space blow-up.
Applications
The paper positions CF and BQF as SSD-optimized approximate membership filters for databases with high insertion rates and independent searches.
- Write-optimized AMQs such as CF and BQF suit workloads where insertions and queries are decoupled.Webtable exemplifies this pattern because duplicate entries permit searches for duplicates to be skipped before insertion.
- Webtable uses an in-memory Bloom filter for each subtable to avoid I/O to subtables that do not contain a queried element.
- CF and BQF could let databases such as Webtable scale to larger sizes without a corresponding increase in RAM.They can keep up with the high insertion throughput of write-optimized databases.
- Related workloads requiring fast insertions and independent searches occur in deduplication, distributed information retrieval, network computing, stream computing, bioinformatics, and database querying.
2. BLOOM FILTER AND SSD VARIANTS
Bloom filters provide compact approximate membership queries but have poor locality, limiting deletions, resizing, and practical external-storage use. SSD variants improve scalability through hardware, buffering, hash localization, multilayering, or buffer policies.
- A Bloom filter supports insertion and membership queries with a tunable false-positive rate ε, trading space consumption against accuracy.
- At 1 byte per element, an optimally filled Bloom filter uses six hash functions and achieves a 1.56% false-positive rate.
- A Bloom filter does not expand or support deletions, and its poor locality makes external-storage use impractical.With k = 10 hash functions on a rotating disk, insertion can fall below 20 elements per second.
- SSD Bloom-filter variants improve scalability through faster devices, buffering, hash localization, multilayering, or specialized buffer-flushing policies.
3. QUOTIENT FILTER
The quotient filter stores hashed fingerprints compactly while preserving Bloom-filter functionality and improving locality. Its clustered layout supports efficient operations, deletions, resizing, and merging.
- The quotient filter represents each set element by a p-bit fingerprint and supports insertion, membership testing, and deletion of one fingerprint copy.
- Quotienting splits each fingerprint into a quotient and remainder, storing remainders in contiguous runs within a compact array with three metadata bits.
- QF operations scan one cluster, whose average size is O(1); at load factor 3/4, the average cluster length is 27 slots.
- The QF has comparable space and false-positive performance to the BF while offering better cache locality and additional operations.QF operations typically access one or two cache lines and can use one SSD page.
- QFs support dynamic resizing without rehashing by shifting one remainder bit into the quotient.
- Two or more QFs can be merged through sequential scans and writes, while QFs support correct deletes unlike standard Bloom filters.
Quotient Filter Variants
The quotient filter supports space-saving variants that reduce metadata overhead, with trade-offs in decoding complexity, lookup initialization, and hash-space usage.
- Synchronizers let the decoder initialize from periodic offsets, reducing per-slot overhead to arbitrarily close to two bits.
- Reserved remainders use a special remainder value to mark empty slots, reducing metadata to two bits while slightly shrinking the hash space.
- Sorting tricks achieve exactly two bits of overhead but make decoding complex and slower.
4. QUOTIENT FILTERS ON FLASH
The buffered quotient filter and cascade filter use quotient filters as SSD-oriented approximate membership structures while preserving the false-positive rate of a single QF.
- The buffered quotient filter and cascade filter are SSD-designed approximate membership structures built from quotient filters.
- Both structures have exactly the same false-positive rate as a single quotient filter storing all elements.
Buffered Quotient Filter
The buffered quotient filter uses an in-memory quotient filter as a buffer and flushes its contents sequentially to an on-disk quotient filter.
- The BQF combines an in-RAM quotient-filter buffer with a quotient filter stored on SSD.When the RAM filter fills, its fingerprints are iterated sequentially and flushed to disk.
- Sequentially ordered fingerprints make each BQF flush write sequentially to SSD.
- The amortized insertion cost for a BQF with n items, cache size M, and block size B bytes is O(n/(MB)).
Cascade Filter
The cascade filter stores quotient filters across an in-memory level and exponentially growing flash levels, merging them as they fill. Its fanout controls a lookup–insertion tradeoff, with logarithmic search cost and low amortized write cost.
- Cascade Filter: The CF maintains an in-memory Q0 and ℓ = log(n/M) + O(1) flash-resident quotient filters of exponentially increasing size.
- Cascade Filter: When levels fill, the CF merges Q0 through the smallest suitable level into a new quotient filter and empties the lower levels.
- Cascade Filter: A CF lookup checks every nonempty level, fetching one page from each.
- Cascade Filter: Increasing fanout improves lookup performance by reducing levels but decreases insertion performance because levels may be rewritten repeatedly.
- Cascade Filter: CF searches require O(log(n/M)) block reads, while inserts require O((log(n/M))/B) amortized block writes or erases.Here, B is the flash’s natural block size.
5. EVALUATION
The evaluation compares quotient-filter and Bloom-filter structures in RAM and SSD settings, examining throughput, scaling, lookup behavior, and cascade-filter fanout tradeoffs. Quotient-filter structures generally outperform Bloom-filter variants, especially for SSD insertions and larger databases.
- Evaluation design: The evaluation compares QF and BF in RAM across three false-positive rates and compares CF, BQF, EBF, BBF, and FBF on SSD.SSD experiments use RAM-to-database ratios of 1:4 and 1:24, while CF fanouts of 2, 4, and 16 are also evaluated.
- In-RAM performance: The QF substantially outperforms the BF on insertions until reaching 80% occupancy.BF insertion throughput declines with lower false-positive rates, while QF insertion slows as occupancy increases because clusters grow.
- On-disk benchmarks: In the large SSD experiment, CF performs 11 times more insertions than BF variants, while BQF performs 9 times more insertions.In the small experiment, BQF outperforms the best BF variant by 5.2× and slightly outperforms CF.
- On-disk benchmarks: The BQF achieves roughly 1.9× the uniform random lookup performance of either the best BF variant or CF.BQF uses one random read per lookup, whereas CF uses between 1 and log(n/M) random reads.
- Fanout tradeoffs: Higher CF fanout improves lookup performance but reduces insertion performance; even fanout 16 exceeds every evaluated BF-based structure for insertions.
- Scaling: CF is the most scalable structure: as the filter-to-RAM ratio grows, it increasingly outperforms BQF.The paper expects this divergence to continue beyond a ratio of 24 because BQF flushes lose space locality.
6. CONCLUSIONS
The paper introduces quotient-filter-based alternatives to Bloom filters that improve data locality and deliver strong RAM and SSD performance. It also identifies parallelism, background merging, faster negative lookups, and broader storage testing as future directions.
- The QF, BQF, and CF provide Bloom-filter functionality with better data locality, while the QF additionally supports faster operations and deletions.
- BQF and CF achieve insertion performance an order of magnitude greater than recent Bloom-filter-based structures with comparable or better lookup performance.
- CF asymptotically scales better than the other structures, matching the experimental results, and was CPU-bound during insertion benchmarks.
- Future work targets parallelism, background merging, short-circuiting lookups for nonexistent elements, and evaluation across more disks and storage configurations.