A Bloom filter for a set of keys from a universe is an array of bits, initially 0, together with hash functions . Inserting sets the bits to 1. A query for answers “possibly in ” if all of the bits are 1 and “not in ” otherwise (Bloom 1970). A key in is always reported as possibly present. A key outside is reported as possibly present with some probability , the false-positive rate, taken over the choice of hash functions.

The filter stores no keys, only which bit positions the inserted keys hashed to, so its size depends on and and not on the size of the keys. It cannot list its members, and a plain bit array cannot delete one, since a bit may be shared by several keys. With bits per key and the best , falls by a factor of about 0.6185 per added bit per key, so 10 bits per key give 0.82% and 20 give 0.0067%. LSM storage engines such as LevelDB and RocksDB keep Bloom filters in each table file to skip the disk read for a key that the file does not hold, and perform that read needlessly for a fraction of absent keys.

The variants below change where the bits of a key are placed, how many hash evaluations produce them, or what each cell holds. On the series benchmark, with the 5,843,219 keys of the first hour inserted and the other 55,131,589 keys of the day queried as absent keys, the partitioned and double-hashed layouts have the standard filter’s false-positive rate within sampling error from 6 to 24 bits per key. Placing all bits in one 512-bit cache line multiplies the rate by 1.18 at 10 bits per key and by 7.3 at 24, and halves the cost of an insertion into a 320 MiB filter. LevelDB’s probe sequence, applied to one filter of the whole hour, has a rate that stops falling at about .

The false-positive rate

Assume the bit positions written during insertion are independent and uniform on . A given bit is still 0 after all insertions with probability

and an absent key is a false positive if its independent positions all hit 1 bits. Treating the fraction of 1 bits as its expectation gives the formula found in most sources (Broder and Mitzenmacher 2004, §2.1):

Bloom’s own filter sets distinct bits per key, and the paper gives the fraction of 0 bits as for an -bit array, so its rate is (Eqs. 16 and 17). The formula above describes the variant with independent positions that may coincide, which is what implementations build because it needs no check for repeated positions.

Choosing . As a function of the approximation is minimized at . There the expected fraction of 1 bits is exactly , and . Solving for gives bits per key. Fewer hash functions leave more bits at 0 but test fewer of them; more test more bits but set more of them. Since must be an integer, implementations round or truncate , and the rate near the optimum is flat: at 10 bits per key, , 7 and 8 give 0.843%, 0.819% and 0.846%.

The exact rate. Given the filter, an absent key passes with probability , where is the realized fraction of 1 bits, so , and by Jensen’s inequality . Bose et al. (2008) showed that the approximation is a strict underestimate for (under a mild condition on and ) and gave an exact expression with Stirling numbers of the second kind. Their smallest example is , , : the inserted key sets one bit or both with probability each, so , while the approximation gives . Christensen, Roginsky and Jimeno (2010) gave the equivalent form , where is the number of occupied bins after balls are thrown into bins, proved that the approximation is never larger than the true rate, and showed that the relative error is large only for small filters (their figure reaches several hundred percent at bits). For the filters of millions of bits measured below, concentrates so tightly around its mean that the approximation and the exact rate agree to the precision of the measurement. The difference returns in blocked filters, which are many small filters.

The lower bound. Any structure that answers membership queries with no false negatives and false-positive rate , for sets of keys from a universe much larger than , must use at least bits in the worst case (Carter et al. 1978; Dietzfelbinger and Pagh 2008, Theorem 13, for , with an loss). A Bloom filter at its best uses bits per key, a factor above the bound, and Dietzfelbinger and Pagh note that this factor is tight for Bloom filters. The cuckoo, quotient, xor and ribbon filters of the next note in the series close most of the gap.

Lower boundStandardBlocked, 512-bit linesBlocked, 64-bit words
1%6.649.59 ()9.92 ()12.1 ()
0.1%9.9714.4 ()15.6 ()24.0 ()
0.01%13.319.2 ()22.0 ()45.5 ()

The table gives the bits per key each layout needs at its best integer , from the closed forms that the measurements below confirm for each layout.

Measured on the benchmark

Each filter was built from the 5,843,219 distinct keys that appear in the first hour of the benchmark and queried with all 55,131,589 keys that first appear later in the day, none of which was inserted, with 5 independent sets of hash functions per configuration. The keys are the 64-bit MurmurHash64A values of the key strings, and hash of key is MurmurHash3’s 64-bit finalizer applied to XOR a random 64-bit seed, reduced to by a multiply-high. The table gives false positives per million absent keys at bits per key and for the layouts that spread a key’s bits over the whole array, with the formula in the second column; the blocked layouts follow in their own section.

, FormulaStandardPartitionedDouble
6, 456,06056,06056,05056,070
8, 621,58021,56021,57021,570
10, 78,1948,1928,1938,189
12, 83,1423,1453,1373,142
16, 11458.7458.4457.3458.8
20, 1467.167.566.868.4
24, 179.849.669.859.48

The three layouts in the table, and enhanced double hashing (described below), match the formula within 2% up to 20 bits per key and within 4% at 24, where each trial counts about 540 false positives. Over a grid of 8 sizes from 2 to 20 bits per key and from 1 to 14 (10 million absent keys per point), the standard filter’s measured rate differs from the formula by at most 0.33% up to 12 bits per key, 0.85% at 16 and 2.0% at 20, and the measured minimum falls at the integer nearest except at 20 bits per key, where and differ by less than the sampling error.

Partitioned filters

A partitioned filter divides the array into slices of bits and lets address only slice , so a key’s bits are always distinct. Its rate is , which is at least the standard filter’s, with equality only at , and has the same limit (Broder and Mitzenmacher 2004, §2.1). At these sizes the difference is far below the sampling error: the measured rates in the table agree with the standard filter’s to within 2%, in both directions.

Double hashing

Computing independent hash values costs hash evaluations per key. Kirsch and Mitzenmacher (2008) proved that two suffice: with for , the false-positive rate converges to as with fixed, and the convergence is . Dillinger and Manolios (2004) argued that plain double hashing behaves like a fingerprint of a little less than two indices and proposed enhanced double hashing, , computed by adding to the step after each probe. On the benchmark both match the standard filter from 6 to 24 bits per key, with between 35 and 140 million bits. The largest deviation of plain double hashing from the formula, at 24 bits per key, is about 2 standard errors, and enhanced double hashing is within 0.5% of the formula at every size in the table.

Blocked filters

A lookup in a standard filter of bits reads up to bits at independent positions, and once the array is larger than the cache each of them is a separate cache miss. A blocked filter (Putze, Sanders and Singler 2009) uses the first hash value to choose a block of bits, one 64-byte cache line for , and places all bits of the key inside that block, so a lookup reads one line. The filter is a sequence of small standard filters, and the number of keys a block receives is approximately Poisson with mean . Blocks that receive more keys than average have a higher fill, and since the false-positive rate is convex in the fill, the overloaded blocks raise the rate more than the underloaded ones lower it. Putze et al. give

with , the standard approximation for a -bit filter holding keys. They report that at 20 bits per key the rate almost triples, from to .

, 512-bit, measured512-bit, exact64-bit, measured64-bit, exact
6, 457,72057,74069,13069,120
8, 623,60023,61037,69037,670
10, 79,6829,68620,96020,940
12, 84,1364,13512,78012,780
16, 11885.2885.57,0007,005
20, 14230.6230.34,8974,900
24, 1772.372.23,9933,996

The table gives false positives per million absent keys on the benchmark for 512-bit and 64-bit blocks, at the same as the table of the other layouts, with the exact blocked rate described next. The measured rates exceed this formula by 0.3% at 6 bits per key, 1.2% at 10, 3.0% at 16 and 6.9% at 24. The gap is the Bose et al. effect inside each block: a 512-bit filter holding an average of 21 to 85 keys is small enough that its fill varies around its mean. Replacing by the exact rate of Christensen et al. for a -bit filter, with the number of distinct bits after uniform throws into bits, computed by dynamic programming over , reproduces every measured blocked rate within 0.2%. For 64-bit blocks the measured rates exceed Putze’s formula by 2.6% at 6 bits per key and by 30% at 24, and the exact form again agrees within 0.2%.

A blocked filter’s best is smaller than , because each additional bit raises the fill of an already crowded block. With 3 trials over , the measured minimum for 512-bit blocks is at for 10 bits per key (0.965%, against 0.969% at ) and at for 16 bits per key (0.084%, against 0.087% at ), the same values the exact formula selects. RocksDB’s cache-local filter uses 512-bit lines and chooses 6 probes at 10 bits per key and 9 at 16.

Register-blocked filters (Lang et al. 2019) reduce the block to one 64-bit word, so a lookup builds a -bit mask and compares one word against it with no data-dependent branch. Their rate is higher again: at their best the measured rate is 1.79% at 10 bits per key () and 0.40% at 16 (), against 0.82% and 0.046% for the standard layout, and the bits per key needed for 0.01% rise to 45. Lang et al. also describe sectorized layouts that spread a key’s bits over several words of one cache line, which sit between the two blocked layouts measured here.

LevelDB’s probe sequence

LevelDB’s filter computes one 32-bit hash of the key and probes , each reduced modulo the filter’s size in bits, with rotated right by 17 bits. Its comment cites Kirsch and Mitzenmacher, and it sets , rounding down to save probes. Kirsch and Mitzenmacher’s analysis assumes that and are independent and uniform on , while here is a fixed function of , and two structural properties follow.

  • The third probe takes few values. Writing with 16-bit halves, , so the high and low halves of differ by 0, 1 or 2 modulo , and takes at most values. Enumerating all values of confirms that takes 196,606 distinct values, against about for a random function and between and for the second, fourth, fifth and sixth probes. In a filter of 58 million bits, every key’s third probe lands in a set of at most 196,606 bits, which are almost all 1 after the insertions, so the probe filters almost nothing and contributes almost no new 1 bits. The measured fill at 10 bits per key () is 0.394, equal to rather than .
  • All probes are determined by 32 bits. An absent key whose 32-bit hash equals that of an inserted key passes, which happens with probability about for million.
Bits per key, per millionLevelDB sequence, per million
1068,43611,620
1611458.71,874
201367.91,450
24169.871,373

At 20 and 24 bits per key the rate has reached the 32-bit floor of 1,360 per million. These runs place all 5.8 million keys of the hour in one filter. LevelDB stores filters per table file, and both effects shrink with the number of keys per filter: the floor is proportional to , and in a sample of 4 million hash values the third probe’s values were as evenly spread modulo as itself for every filter size tried up to 65,536 bits. How many keys LevelDB’s own filters hold was not measured.

Counting filters

Fan et al. (2000) replaced each bit by a small counter so that a key can be deleted, in a protocol in which Web proxies summarize their cache contents for one another. Insertion increments the key’s counters, deletion decrements them, and a query tests whether all are nonzero. The structure was later named the counting Bloom filter. Each counter after insertions is approximately Poisson with mean , and Fan et al. bound the probability that any counter reaches 16 by when , so 4-bit counters suffice; a counter that would exceed 15 stays at 15. The cost is 4 bits per cell where the plain filter uses 1. Deleting a key that was never inserted, such as an absent key that the filter reported as possibly present, can decrement to 0 a counter that an inserted key depends on and so produce false negatives.

On the benchmark, at 10 cells per key and ( million counters, mean ), the largest counter over 10 independent builds was 8 once, 9 eight times and 10 once, and the average numbers of counters holding each value from 0 to 6, which account for all but about one in counters, agree with the Poisson probabilities within 0.2%. The bound for this is .

Cost of a lookup

A standard filter with computes 7 hash values per key and reads 7 bits for an insertion or a present key. An absent key stops at the first 0 bit; with half the bits set it reads 2 bits on average. Double hashing computes 2 hash values and reads the same bits. The blocked layouts compute 2 hash values and read one cache line or one word. The timings below are single-threaded, at 10 bits per key and for every layout, on 4 sizes of filter, with queries per measurement; the median of 3 repetitions is shown, and repetitions differed by up to 30% on this virtual machine.

Filter sizeStandardDouble hashingBlocked, 512Blocked, 64
160 KiB13 / 21 / 1411 / 22 / 1312 / 20 / 127 / 8 / 8
1.25 MiB14 / 24 / 1613 / 23 / 1411 / 21 / 147 / 8 / 10
20 MiB55 / 44 / 5143 / 43 / 4034 / 33 / 3023 / 23 / 24
320 MiB147 / 81 / 131120 / 85 / 11378 / 58 / 7059 / 60 / 61

Each cell gives nanoseconds per insertion, per query for an absent key and per query for a present key. The two smaller filters fit in the 2 MiB per-core L2 cache, the third in the last-level cache, and the largest exceeds the 260 MiB last-level cache that the processor reports. Queries are independent of one another, so the processor overlaps their cache misses, and the figures are throughput, not the latency of an isolated lookup.

At 320 MiB the 512-bit blocked layout halves the cost of an insertion and of a present query relative to the standard layout (78 against 147 ns, 70 against 131 ns), and lowers the cost of an absent query by 28% (58 against 81 ns), since the standard layout reads only about 2 bits for an absent key. Double hashing saves 5 of the 7 hash evaluations and 14 to 22% of the cost of an insertion or present query at the two larger sizes, but reads as many cache lines as the standard layout. Inside the L2 cache the standard, double-hashed and 512-bit layouts cost the same within the measurement’s spread, and an absent query costs more than a present one (21 against 14 ns for the standard layout at 160 KiB). That difference is consistent with a mispredicted branch at the exit of the probe loop, whose position is random for absent keys; the register-blocked layout, which tests all bits with one comparison and has no such branch, costs the same for both. Lang et al. find that at high query rates blocked Bloom filters outperform cuckoo filters.

Comparing layouts

110%1%10−310−410−5136791215hash functions per key, kfalse-positive rate

At 10 bits per key and k = 7, 5,127 of 524,288 absent keys pass the filter: 0.98% (95% interval 0.95% to 1.00%). The standard formula gives 0.82% and the blocked formula 0.97%. 50.2% of the bits are set, and that fraction to the power k is 0.80%.

One lookup in a 2048-bit filter with the same settings

Its 7 probes fall in 5 of the 32 words and 1 of the 4 cache lines. The lookup stops at probe 1, the first bit that is 0.

Simulation in the browser. Each measured point builds a filter of 220 bits holding 220/b integer keys and queries 219 integers that were not inserted; the hashes are seeded 32-bit mixing functions, not the pageview data. The blocked formula is the Poisson-weighted rate of Putze, Sanders and Singler with each block's fill treated exactly. A downward caret marks a point with no false positives. The lower panel draws a 2048-bit filter one 64-bit word per row; a cache line is 8 rows.

The figure builds filters of bits in the browser and measures each layout’s false-positive rate for every from 1 to 16, with the standard formula and, for the blocked layouts, the exact blocked formula drawn through the points. At 10 bits per key the 512-bit blocked points sit on the orange curve, about 18% above the standard curve at , and their minimum is at ; the 64-bit blocked rate at is 2.6 times the standard rate. LevelDB’s sequence shows the effect of its third probe: the simulated keys never share a 32-bit hash, so the floor of the previous section is absent and the excess comes from the third probe alone. The lower panel draws a filter of 2048 bits, one 64-bit word per row, and circles the bits that one absent key probes, so that the standard layout’s probes scatter across the array while a blocked layout’s probes stay in one line or one word.

Consequences for implementations

For a filter that fits in a core’s L2 cache, the layouts measured here differ in lookup cost by less than the measurement’s spread, except the register-blocked layout, which is 2.6 times faster for absent keys and 1.8 times for present keys and needs 27% more space at a 1% rate and 67% more at 0.1%. For a filter larger than the cache, a 512-bit blocked layout halves the cost of insertions and present queries at a space overhead of 3% at 1%, 8% at 0.1% and 15% at 0.01%, provided is chosen for the blocked layout (6 at 10 bits per key) and not as . The space comparisons above use the exact blocked formula, since the measured rates exceed the Poisson approximation of Putze et al. by up to 7% for 512-bit blocks and 30% for 64-bit blocks at the sizes measured. Double hashing from two independent 64-bit hash values had no measurable cost in accuracy at any size measured. A filter whose probes derive from one 32-bit hash has a false-positive rate of at least about , which for one filter of 5.8 million keys is 0.14%, the rate of a standard filter with independent 64-bit hashes at 13.7 bits per key.