Bloom filters

Eight words go into a row of 64 bits, three bits each. Then words that were never added ask whether they are in. Watch how the filter answers.

⋯23static unsigned bit_index(uint32_t h, int i)24{25    uint32_t a = h & 63u;26    uint32_t b = ((h >> 6) & 63u) | 1u;27    return (a + (uint32_t)i * b) & 63u;28}29 30void add(const char *s)31{32    uint32_t h = fnv1a(s);33    for (int i = 0; i < K; i++)34        bits |= (uint64_t)1 << bit_index(h, i);35}36 37bool might_contain(const char *s)38{39    uint32_t h = fnv1a(s);40    for (int i = 0; i < K; i++)41        if ((bits & ((uint64_t)1 << bit_index(h, i))) == 0)42            return false;43    return true;44}⋯46int main(void)47{48    const char *present[20] = {49        "filter", "sample", "window", "phase", "gain", "delay", "noise", "pulse",50        "chirp", "tone", "echo", "carrier", "band", "notch", "ripple", "decay",51        "spike", "drift", "bias", "clock"52    };53    const char *absent[20] = {54        "apple", "river", "stone", "cloud", "tiger", "piano", "lemon", "bread",55        "chair", "glass", "plant", "rope", "sand", "wheel", "coin", "hill",56        "mask", "nest", "ink", "fog"57    };58    for (int i = 0; i < WORDS; i++)59        add(present[i]);60    int set = 0;61    for (int b = 0; b < 64; b++)62        set += (int)((bits >> b) & 1u);63    int missed = 0, maybe = 0;64    for (int i = 0; i < WORDS; i++)65        if (!might_contain(present[i]))66            missed++;67    for (int i = 0; i < 20; i++)68        if (might_contain(absent[i]))69            maybe++;70    printf("%d words, %d of 64 bits set, %d missed, %d of 20 absent words say maybe\n",71           WORDS, set, missed, maybe);72    return 0;73}

Bits instead of items

A Bloom filter answers one question about a set: is this item in it? It does not store the items. It keeps an array of m bits, all 0 at first, and k hash functions, each sending an item to one of the bits.

To add an item, set its k bits. To test an item, look at its k bits. If any of them is 0, the item was never added: adding it would have set that bit. If all k are 1, the item was probably added, but the bits might have been set by other items. The filter answers “certainly not” or “probably”, never a certain “yes”.

That is the trade. The filter here holds up to 20 words in 8 bytes, whatever their length, and in return it is sometimes wrong in one direction.

The code and its cost

#define K 3

static uint64_t bits = 0;

static unsigned bit_index(uint32_t h, int i)
{
    uint32_t a = h & 63u;
    uint32_t b = ((h >> 6) & 63u) | 1u;
    return (a + (uint32_t)i * b) & 63u;
}

void add(const char *s)
{
    uint32_t h = fnv1a(s);
    for (int i = 0; i < K; i++)
        bits |= (uint64_t)1 << bit_index(h, i);
}

bool might_contain(const char *s)
{
    uint32_t h = fnv1a(s);
    for (int i = 0; i < K; i++)
        if ((bits & ((uint64_t)1 << bit_index(h, i))) == 0)
            return false;
    return true;
}

The 64 bits are one uint64_t, used as a set of bits as in Counting and bitmasks: |= sets a bit, & tests one. The three positions come from one FNV-1a hash: a is its low 6 bits, b the next 6 with the lowest bit forced to 1, and the positions are a, a + b and a + 2b, each mod 64. Because b is odd, the three are always different. For “filter”, FNV-1a gives 3353438327, so a = 55, b = 33, and the positions are 55, 24 and 57.

The cast in (uint64_t)1 << ... matters. A plain 1 is an int, 32 bits here and signed, and shifting it by 31 or more is undefined behaviour in C: at 31 the result, 2³¹, no longer fits in an int, and from 32 the shift is as wide as the type. 1u, an unsigned int, can be shifted by up to 31, and the 64-bit (uint64_t)1 used here by up to 63.

Adding and testing each take k steps, plus one hash, however many items the filter holds. main adds the first 8 of its 20 words, tests those 8, then tests 20 words it never added, and prints 8 words, 22 of 64 bits set, 0 missed, 0 of 20 absent words say maybe.

No false negatives

A word that was added always answers “probably”. Its k bits were set when it was added, and nothing ever clears a bit, so they are all still 1. The filter is never wrong about an item it holds: “missed” is 0 in every run from 1 to 20 words.

The other answer can be wrong. A word that was never added answers “probably” when all of its bits happen to be set by other words: a false positive. With 16 words in the filter, “tiger” finds its bits 56, 59 and 62 all lit and says “probably”.

How often it is wrong

With m bits, k hash functions and n items added, take one bit. Each of the kn bit settings misses it with probability 1 − 1/m, so if the settings fall independently and uniformly over the bits, the bit is still 0 afterwards with probability

A word never added says “probably” when all k of its bits are 1. If its k positions are independent of each other and of the bits already set, that happens with probability about

This is an approximation, and it rests on independence: every position equally likely and unrelated to every other. Real hashes only come close. Here the three positions are not even independent of each other, since they are a, a + b and a + 2b from one hash; a filter built for real use would derive them from better-separated hashes.

The traced runs give a check. For m = 64 and k = 3, the formula expects about 64(1 − e^(−0.375)) ≈ 20 bits set after 8 words; the run sets 22. It predicts 3.1 % false positives, 0.6 of 20 test words; the run measures 0 of 20. At 20 words it predicts 22.5 %, 4.5 of 20; the run measures 3 of 20, 15 %. With only 20 test words the measured share moves in steps of 5 %. If each test word were fooled independently with probability 0.225, the count out of 20 would have a standard deviation of about 1.9, so 3 against 4.5 is well within the scatter. On the plot every dot sits below the line, partly because this hash sets fewer bits than the formula expects: 34 at 20 words, against about 39.

Choosing k

More hash functions make each test harder to fool, but they also set more bits, so the array fills faster. For given m and n, the rate is least at about

and there each bit is 1 with probability about one half. With m = 64: for 8 words the best k is 8 ln 2 ≈ 5.5; for 20 words it is 3.2 ln 2 ≈ 2.2. The program’s k = 3 would be the best choice for about 15 words: (64/15) ln 2 ≈ 3.0.

No removal

An item cannot be taken out. Clearing its k bits could clear a bit another item needs, and that item would then answer “certainly not”: a false negative. A counting filter keeps a small counter per position instead of a bit, adding 1 on add and subtracting 1 on removal.

Worked example

The formula for m = 64, k = 3.

Doubling the bits. With n = 16 and k = 3, 128 bits instead of 64 give kn/m = 0.375 again, so the rate falls from 0.147 to 0.031, the same as 8 words in 64 bits. For a fixed k, in the approximation, only the ratio n/m matters.

A million items at 1 %. Putting the best k back into the formula gives a rate of about (1/2)^k, and solving for the bits per item gives

For p = 0.01 that is 4.605 / 0.4805 ≈ 9.6 bits per item, about 9.6 million bits, or 1.2 MB, for a million items, with k = 9.6 ln 2 ≈ 6.6, so 7 hash functions. Storing a million 20-byte keys instead would take 20 MB.

Two checks. Can “certainly not” ever be wrong? (No: every bit an added word set stays set.) What happens to the rate when m doubles and n stays the same? (It falls: at n = 16 and k = 3, from 0.147 to 0.031.)

Where it’s used

Databases and key–value stores, which keep a filter per file on disk and skip reading the file when the filter says a key is certainly not there.

Web browsers, some of which have checked addresses against a filter of unsafe sites before asking a server.

Spell checkers and network routers, where a small filter in fast memory answers most questions and only the “probably” answers need a slower check.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, uint64_t 8, little-endian. The bit positions come from FNV-1a as this page computes it; addresses in the pictures are short stand-ins, by one rule for the whole course.