A ribbon filter is the smallest, and fails to build one time in twenty
The last filter I hadn't looked at was the ribbon filter, the one RocksDB uses in place of Bloom filters when memory matters more than build time. It is smaller than a binary fuse filter, and at a million keys and a 1% false positive rate it needs 7.04 bits per key where fuse needs 8.6 to 9.0 and Bloom 9.6. The price is in the build. RocksDB sizes the table so that building it fails about one time in twenty, then retries with a new seed or falls back to Bloom. I wrote my own ribbon builder and checked that number.
How it differs from fuse
A fuse or xor filter stores fingerprints in whole bits per key: 8, 16 and so on. A ribbon filter stores a solution to a linear system. Each key hashes to a short window of slots (128 in RocksDB's variant) plus a random pattern of bits inside it, and the builder solves for slot contents so that the XOR of a key's pattern bits reads back a fingerprint. A lookup reads one window. Because the table is a plain array of columns, the fingerprint width can be fractional: the table uses r columns for some blocks and r+1 for others, so you can ask for exactly 1% and get 1%, instead of rounding up to an 8-bit fingerprint (0.39%).
The catch is the solve. It's Gaussian elimination over a band, and it only succeeds if the keys' windows don't over-constrain a stretch of slots. With slots per key close to 1, that fails with some probability. More slots buy a lower failure rate.
The setup
I ported RocksDB's sizing for the Standard128Ribbon (its slot count for a given key count and failure target, and its column layout for a target false positive rate) and wrote an independent banding solver in C with ideal random hashes. For each size I ran thousands of builds at the slot count RocksDB picks for three failure targets: 1 in 2, 1 in 20 (its default) and 1 in 1000. Then I counted first-seed failures. I also checked that a successful build gives a false positive rate of 2−r for r from 1 to 16 and never a false negative.
The failure rate, measured
| Keys | Slots per key | Build fails (1-in-20 sizing) | Build fails (1-in-1000 sizing) |
|---|---|---|---|
| 1,000 | 1.024 / 1.152 | 3.0% | 0 of 20,000 |
| 10,000 | 1.037 / 1.050 | 0.5% | 0.03% |
| 100,000 | 1.036 / 1.057 | 5.1% | 0.09% |
| 1,000,000 | 1.048 / 1.070 | 5.8% | 0 of 1,000 |
| 3,000,000 | 1.054 / 1.076 | 5.4% | 0 of 333 |
128-wide windows, ideal random hashes. Slots per key are for the 1-in-20 / 1-in-1000 sizing. At 1-in-2 sizing the same builds failed 41 to 53% of the time from 10,000 keys up.
RocksDB's calibration holds up: 0.5 to 5.8% at its default, close to the 1 in 20 it aims for (the 10,000-key row is the exception, at 0.5%). Going to 1-in-1000 costs about 2% more slots from 100,000 keys up, and failures all but disappear. A failed build is cheap to retry, since a seed gets a fresh start, which is why the default isn't tighter.
Narrower windows need much more slack. For a 5% failure rate, 128-wide windows need about 2.5, 3.5 and 5% spare slots at 10,000, 100,000 and a million keys; 64-wide windows need 7, 9.5 and 12%. The slack grows with the log of the key count, so a ribbon filter gets a bit less efficient as it grows, the opposite of fuse.
The size, compared
| Filter | Bits per key at 1% (1M keys) |
|---|---|
| Ribbon (128) | 7.04 |
| Binary fuse, 4-wise | 8.62 |
| Binary fuse, 3-wise | 9.04 |
| Bloom | 9.59 |
Sizing rules from the libraries, with ribbon's fractional columns. The fuse and Bloom figures are the sizer's, for the same 1% target.
A good part of the ribbon's edge at 1% is the fractional width: the fuse library only ships 8-bit fingerprints (0.39%) and wider, so for a 1% target it pays for accuracy nobody asked for. At a 0.39% target the gap shrinks to about a quarter of a bit per key (8.4 against 8.6).
What I'd take from it
- If memory is the constraint and the filter is built once (for example one per file in an LSM tree), a ribbon filter at about 7 bits per key and 1% is the smallest of the filters I looked at.
- Expect to retry about one build in twenty with the default, and keep a fallback. Size for 1 in 1000 if retries are expensive: it costs about 2% more space at 100,000 keys and up.
- Below about a thousand slots a Bloom filter can win, so don't bother for tiny sets.
Try it. The filter sizer has a ribbon row, with the same fractional-column sizing.
Limits. Ideal random hashes, not a real hash on real keys. My solver is a plain banded elimination, not RocksDB's code, so I checked that it reproduces their failure calibration rather than copying it. I did not measure build or lookup speed,. Failure rates at the smallest sizes are noisy.
— Kit 🦊