The Bloom Filter

Here is a problem that turns up in almost every large system. Items arrive one at a time, and for each one you have to answer a single question. Have I seen this one before? A crawler asks it of every link it discovers, and a cache asks it of every key. So here is the question this lecture answers. Have I seen this item before, when the set of items I have seen is far too large to keep? The second half of that sentence is where all of the difficulty lives. The obvious answer is to keep the set. Every item you have seen goes into a hash set, and every new one gets looked up. Across the bottom here is n, the number of items, counted in millions. Up the side is memory, in gigabytes. URLs are not small. Sixty four bytes each is a kind estimate, and this red line is what that costs you. A billion of them is sixty four gigabytes, and it is a straight line, because an exact set charges you for every item, forever. The dashed line is the memory the machine actually has. Eight gigabytes. The red line crosses it here, at about a hundred and twenty five million URLs, and past that point the structure does not fit and the process dies. The blue line is where we are going. The same billion URLs, about ten bits each, and the whole structure is a gigabyte and a quarter. Fifty times smaller, and it never stores a single URL. You do not get that for free. What you give up is certainty, in one direction only. A Bloom filter answers two ways: definitely not in the set, or probably in the set. The second of those is sometimes wrong. Two things to hold on to before we build it. It never stores the items, so you can never ask it what is in there. And the mistakes only ever go one way. It will never tell you an item is absent when you did in fact insert it.

So we are not going to store the items. We are going to store a fixed row of bits, and nothing else. Here is one: sixteen bits, numbered zero to fifteen, and every single one of them is zero. Call the length m. In a real filter m is not sixteen, it is a few billion. Sixteen is a size you can see. And notice what is missing here. There is no list of items anywhere in this picture, no copy of anything that was ever inserted. There are only bits. So take an item. Call it x. We hash it, not once, but k times, with k independent hash functions. Here k is three, and the first of them hands back position two. The second gives seven, and the third gives eleven. Three positions, three bits, and we set all three of them to one. That is the whole of the insert operation. Notice what did not happen there. We did not store x. We did not store a hash of x, or a pointer to x, or how long it was. Three bits went from zero to one, and the item itself is gone. Insert a second item. Its three hashes come out four, seven, and thirteen, so we set those. And look at position seven. It was already a one, set by the first item, and it stays a one. The row has no idea that two different items are now leaning on that single bit. Hold on to that. A third item, and its positions are one, nine, and fourteen. Three items are in the filter now, and eight of the sixteen bits are ones. That is the entire state. So now the other half of the job. How do you ask a question? To test an item you hash it exactly the same way, and you look at the k bits it names. Here is the second item again. Four, seven, thirteen. All three of them are ones. So the filter says: probably present. And it is right, we did insert that one. But look at what it actually checked. It never compared the item to anything at all. It read three bits. Now an item that was never inserted. Its positions come out zero, nine, and fourteen. The bit at nine is a one, the bit at fourteen is a one, and the bit at zero is not. And that settles it. If this item had ever been inserted, every one of its bits would have been set at that moment, and bits in this row are never cleared. A single zero anywhere is proof of absence. Definitely not in the set. That answer is exact, and it is the one guarantee the structure gives you. It is worth more than it sounds. Most of the time the thing you are asking about really is new, and you get told so for three bit lookups and no disk at all.

Here is that same row, with those same three items in it, and now I am going to ask about an item that nobody ever inserted. Call it v. Its three positions come out two, four, and nine. Two is a one. The first item set it. Four is a one. The second item set that. Nine is a one, and the third item set that. So all k bits are ones, and the filter says: probably present. And it is wrong. No item set that pattern. Three different items each happened to set one of its bits, and between them they covered it. That is a false positive. It is not a bug, and there is no clever fix for it. It is what you bought when you decided to store bits instead of items. The bits do not remember who set them. What you can do is work out how often it happens, before you ship anything, and then choose how often you are willing to let it happen. So let us count it. Fix one bit in the row and follow it. Call P nought the chance that this bit is still a zero, and P one the chance that something has set it. A single hash function picks a position uniformly out of m, so it misses our bit with probability one minus one over m. Inserting one item runs k hashes. Inserting n items runs k times n of them, and if the hash functions are independent our bit survives every one of them, with probability one minus one over m, all raised to the power k n. That form is awkward to think with, so use the standard approximation. When m is large it is very close to e to the minus k n over m. Same number, and far easier to see what it does. Turn it around. The chance that a given bit has been set is one minus that. And this curve is exactly that number, for our sixteen bit row with three hash functions, as n climbs. With three items in, the formula says about forty three percent of the bits are ones. We counted eight out of sixteen, which is fifty. With only sixteen bits that is the sort of luck you get. Now push n up to twelve. Nearly ninety percent of the row is ones, and at that point almost any pattern you ask about is already covered by something. The false positive rate climbs with n, and this is the reason why. So now the query itself. An item that was never inserted names k bits. Each one is a one with probability P one, and if we treat those as independent, all k of them are ones with probability P one to the k. There it is. The false positive rate, epsilon, is one minus e to the minus k n over m, all raised to the k. Read the exponent as the total number of bits you have set, k of them for each of n items, divided by the room you gave them to spread out in. Read the rest of it the way an engineer reads it. n is handed to you by the problem. m is what you are willing to pay for. And k is the one you actually get to choose, and it is not at all obvious which way to push it.

So, choosing k. Fix the budget at ten bits an item, which is the number you will see quoted everywhere, and the rate depends on k and nothing else. Here it is, plotted against the number of hash functions. With one hash function, each item sets a single bit, and the rate is about nine and a half percent. Nearly one query in ten comes back wrong. Two hash functions: three point three percent. Three: one point seven. Every extra hash function is another bit that has to be a one by accident, and that gets rapidly less likely. Five hash functions gets you under one percent. Seven gets you eight in a thousand, and that is the best this budget can do. Now watch what happens if you keep going. Ten hash functions is worse than seven. Fourteen is worse than three. The curve turns around and climbs back up. And the reason is sitting in the formula. Every extra hash function is one more bit a query has to match, which helps you. But it is also one more bit set on every insert, so the exponent grows and the row fills up faster, which hurts you. Past a point the second effect wins. The minimum is where those two balance, and it lands somewhere clean. The best k is m over n times the natural log of two, which for ten bits an item is six point nine. So you use seven. And there is a check you can run in production. At the optimal k the row ends up with almost exactly half its bits set. Half ones, half zeros. If your filter is much fuller than half, you are running too many hash functions. Which leaves the budget itself. Substitute that optimal k back into the rate, and the whole expression collapses into one number raised to the bits per item. About zero point six two, to the power m over n. So here is the curve an engineer actually wants. Bits per item across the bottom, false positive rate up the side. At eight bits an item, two percent. At ten bits, eight in a thousand. At fourteen, about one in a thousand. At twenty bits an item you are down to seven in a hundred thousand, and you are still using less than three bytes a URL. Every extra bit per item multiplies the error by roughly zero point six two. That is what makes ten the number people quote. It is the first place the curve is properly flat, and it is under one percent. And look at the shape of it. Going from three bits an item to eight is cheap, and it buys you an enormous amount. After that it gets expensive, because you are paying linearly for an error that is shrinking exponentially.

One more property, and it is the one that catches people out. You cannot remove anything from a Bloom filter. Here is why, on the row we already have, with the same three items in it. Suppose we want to take the first item back out. Its bits were two, seven, and eleven, so the obvious move is to clear those three. Now ask about the second item, which is still very much in the set. Its bits are four, seven, and thirteen. Four is a one. Thirteen is a one. And seven is now a zero, because we just cleared it. So the filter says definitely absent, about an item that is definitely present. That is a false negative, and it is the single answer this structure promised you it would never get wrong. The bit at seven was never the first item's bit to give back. It was shared, and nothing in the row records how many items are leaning on it. So we put it back, and we do not do that again. Which gives us the rule, and it is worth stating plainly. A Bloom filter supports insert, and it supports query, and it does not support delete. If the things you are tracking ever go away again, this is the wrong structure for them. There is a variant that fixes it. Replace each bit with a small counter, increment on insert, decrement on delete, and now the shared position knows that two items are leaning on it. You pay for that. Four bit counters make the whole thing four times bigger, which was most of the reason you reached for a Bloom filter in the first place. So where does this earn its keep? A crawler is the clean case. You pull a URL off the frontier, and before you spend a network round trip on it, you ask whether you have fetched it already. The filter answers in the two ways we know. Definitely new, and you fetch it. Probably seen, and you drop it on the floor. A billion URLs at ten bits each is a gigabyte and a quarter, which fits in memory on any machine you would run a crawler on. The exact set was sixty four gigabytes, and a disk seek for every link on every page. At seven hash functions the rate is eight in a thousand, so about eight million URLs out of a billion get reported as seen when they never were, and never get fetched. On a web that size, that is a rounding error in your coverage. And notice which way the errors fall. What cannot happen is a page you have already fetched coming back as new. That is the one that puts a crawler in a loop, and it is precisely the answer the filter is exact about. So that is the whole structure. Bits instead of items. k hash functions instead of a comparison. A false positive rate you can compute before you ship. And no deletions, ever.