WEBVTT 00:00:00.070 --> 00:00:03.588 Here is a problem that turns up in almost every large system. 00:00:03.692 --> 00:00:08.255 Items arrive one at a time, and for each one you have to answer a single question. 00:00:08.452 --> 00:00:10.343 Have I seen this one before? 00:00:10.426 --> 00:00:13.071 A crawler asks it of every link it discovers, 00:00:13.154 --> 00:00:15.941 and a cache asks it of every key. 00:00:17.338 --> 00:00:20.253 So here is the question this lecture answers. 00:00:20.450 --> 00:00:22.398 Have I seen this item before, 00:00:22.481 --> 00:00:25.640 when the set of items I have seen is far too large to keep? 00:00:25.837 --> 00:00:29.517 The second half of that sentence is where all of the difficulty lives. 00:00:29.942 --> 00:00:32.323 The obvious answer is to keep the set. 00:00:32.427 --> 00:00:37.257 Every item you have seen goes into a hash set, and every new one gets looked up. 00:00:37.361 --> 00:00:42.029 Across the bottom here is n, the number of items, counted in millions. 00:00:42.226 --> 00:00:44.885 Up the side is memory, in gigabytes. 00:00:45.589 --> 00:00:47.445 URLs are not small. 00:00:47.528 --> 00:00:52.869 Sixty four bytes each is a kind estimate, and this red line is what that costs you. 00:00:53.066 --> 00:00:57.104 A billion of them is sixty four gigabytes, and it is a straight line, 00:00:57.187 --> 00:01:00.973 because an exact set charges you for every item, forever. 00:01:01.769 --> 00:01:05.358 The dashed line is the memory the machine actually has. 00:01:05.554 --> 00:01:07.146 Eight gigabytes. 00:01:07.249 --> 00:01:11.996 The red line crosses it here, at about a hundred and twenty five million URLs, 00:01:12.079 --> 00:01:16.387 and past that point the structure does not fit and the process dies. 00:01:17.184 --> 00:01:19.493 The blue line is where we are going. 00:01:19.576 --> 00:01:21.327 The same billion URLs, 00:01:21.410 --> 00:01:25.288 about ten bits each, and the whole structure is a gigabyte and a quarter. 00:01:25.601 --> 00:01:29.631 Fifty times smaller, and it never stores a single URL. 00:01:30.427 --> 00:01:32.518 You do not get that for free. 00:01:32.714 --> 00:01:36.280 What you give up is certainty, in one direction only. 00:01:36.476 --> 00:01:38.950 A Bloom filter answers two ways: 00:01:39.263 --> 00:01:42.662 definitely not in the set, or probably in the set. 00:01:42.745 --> 00:01:45.463 The second of those is sometimes wrong. 00:01:46.515 --> 00:01:49.174 Two things to hold on to before we build it. 00:01:49.487 --> 00:01:53.342 It never stores the items, so you can never ask it what is in there. 00:01:53.539 --> 00:01:56.337 And the mistakes only ever go one way. 00:01:56.441 --> 00:02:00.122 It will never tell you an item is absent when you did in fact insert it. 00:02:01.219 --> 00:02:03.330 So we are not going to store the items. 00:02:03.413 --> 00:02:07.420 We are going to store a fixed row of bits, and nothing else. 00:02:07.616 --> 00:02:11.481 Here is one: sixteen bits, numbered zero to fifteen, 00:02:11.564 --> 00:02:14.223 and every single one of them is zero. 00:02:14.420 --> 00:02:16.092 Call the length m. 00:02:17.005 --> 00:02:21.113 In a real filter m is not sixteen, it is a few billion. 00:02:21.196 --> 00:02:23.402 Sixteen is a size you can see. 00:02:23.506 --> 00:02:25.385 And notice what is missing here. 00:02:25.468 --> 00:02:27.939 There is no list of items anywhere in this picture, 00:02:28.022 --> 00:02:30.598 no copy of anything that was ever inserted. 00:02:30.681 --> 00:02:32.354 There are only bits. 00:02:32.732 --> 00:02:35.180 So take an item. Call it x. 00:02:35.263 --> 00:02:41.290 We hash it, not once, but k times, with k independent hash functions. 00:02:41.394 --> 00:02:45.713 Here k is three, and the first of them hands back position two. 00:02:46.510 --> 00:02:49.727 The second gives seven, and the third gives eleven. 00:02:49.830 --> 00:02:54.266 Three positions, three bits, and we set all three of them to one. 00:02:54.463 --> 00:02:57.308 That is the whole of the insert operation. 00:02:58.523 --> 00:03:00.567 Notice what did not happen there. 00:03:00.880 --> 00:03:02.445 We did not store x. 00:03:02.528 --> 00:03:08.067 We did not store a hash of x, or a pointer to x, or how long it was. 00:03:08.171 --> 00:03:12.490 Three bits went from zero to one, and the item itself is gone. 00:03:13.705 --> 00:03:15.552 Insert a second item. 00:03:15.748 --> 00:03:20.451 Its three hashes come out four, seven, and thirteen, so we set those. 00:03:21.248 --> 00:03:22.755 And look at position seven. 00:03:22.838 --> 00:03:27.436 It was already a one, set by the first item, and it stays a one. 00:03:27.633 --> 00:03:32.034 The row has no idea that two different items are now leaning on that single bit. 00:03:32.346 --> 00:03:33.694 Hold on to that. 00:03:34.607 --> 00:03:39.309 A third item, and its positions are one, nine, and fourteen. 00:03:40.106 --> 00:03:44.774 Three items are in the filter now, and eight of the sixteen bits are ones. 00:03:44.970 --> 00:03:47.142 That is the entire state. 00:03:47.594 --> 00:03:49.801 So now the other half of the job. 00:03:49.905 --> 00:03:51.682 How do you ask a question? 00:03:52.896 --> 00:03:55.913 To test an item you hash it exactly the same way, 00:03:55.996 --> 00:03:58.307 and you look at the k bits it names. 00:03:58.504 --> 00:04:00.501 Here is the second item again. 00:04:00.698 --> 00:04:02.716 Four, seven, thirteen. 00:04:02.799 --> 00:04:04.878 All three of them are ones. 00:04:05.675 --> 00:04:08.647 So the filter says: probably present. 00:04:08.844 --> 00:04:11.387 And it is right, we did insert that one. 00:04:11.839 --> 00:04:14.093 But look at what it actually checked. 00:04:14.289 --> 00:04:17.100 It never compared the item to anything at all. 00:04:17.296 --> 00:04:19.004 It read three bits. 00:04:19.916 --> 00:04:22.274 Now an item that was never inserted. 00:04:22.587 --> 00:04:26.721 Its positions come out zero, nine, and fourteen. 00:04:26.917 --> 00:04:30.468 The bit at nine is a one, the bit at fourteen is a one, 00:04:30.551 --> 00:04:32.944 and the bit at zero is not. 00:04:33.740 --> 00:04:35.285 And that settles it. 00:04:35.482 --> 00:04:39.499 If this item had ever been inserted, every one of its bits would have been set 00:04:39.499 --> 00:04:42.946 at that moment, and bits in this row are never cleared. 00:04:43.029 --> 00:04:46.022 A single zero anywhere is proof of absence. 00:04:46.105 --> 00:04:48.103 Definitely not in the set. 00:04:48.807 --> 00:04:52.950 That answer is exact, and it is the one guarantee the structure gives you. 00:04:53.033 --> 00:04:55.193 It is worth more than it sounds. 00:04:55.390 --> 00:04:58.650 Most of the time the thing you are asking about really is new, 00:04:58.733 --> 00:05:02.147 and you get told so for three bit lookups and no disk at all. 00:05:03.241 --> 00:05:06.664 Here is that same row, with those same three items in it, 00:05:06.747 --> 00:05:10.217 and now I am going to ask about an item that nobody ever inserted. 00:05:10.300 --> 00:05:14.794 Call it v. Its three positions come out two, four, and nine. 00:05:15.497 --> 00:05:18.679 Two is a one. The first item set it. 00:05:18.876 --> 00:05:22.407 Four is a one. The second item set that. 00:05:22.510 --> 00:05:25.518 Nine is a one, and the third item set that. 00:05:26.059 --> 00:05:31.677 So all k bits are ones, and the filter says: probably present. And it is wrong. 00:05:31.760 --> 00:05:33.781 No item set that pattern. 00:05:34.395 --> 00:05:37.389 Three different items each happened to set one of its bits, 00:05:37.472 --> 00:05:39.562 and between them they covered it. 00:05:40.359 --> 00:05:45.329 That is a false positive. It is not a bug, and there is no clever fix for it. 00:05:45.781 --> 00:05:49.625 It is what you bought when you decided to store bits instead of items. 00:05:49.821 --> 00:05:52.214 The bits do not remember who set them. 00:05:53.126 --> 00:05:57.258 What you can do is work out how often it happens, before you ship anything, 00:05:57.341 --> 00:06:00.406 and then choose how often you are willing to let it happen. 00:06:00.603 --> 00:06:02.113 So let us count it. 00:06:03.626 --> 00:06:06.146 Fix one bit in the row and follow it. 00:06:06.459 --> 00:06:09.684 Call P nought the chance that this bit is still a zero, 00:06:09.767 --> 00:06:12.717 and P one the chance that something has set it. 00:06:12.914 --> 00:06:17.604 A single hash function picks a position uniformly out of m, so it misses our bit 00:06:17.604 --> 00:06:20.461 with probability one minus one over m. 00:06:21.257 --> 00:06:24.057 Inserting one item runs k hashes. 00:06:24.253 --> 00:06:27.398 Inserting n items runs k times n of them, 00:06:27.481 --> 00:06:31.368 and if the hash functions are independent our bit survives every one of them, 00:06:31.451 --> 00:06:36.491 with probability one minus one over m, all raised to the power k n. 00:06:37.404 --> 00:06:41.619 That form is awkward to think with, so use the standard approximation. 00:06:41.723 --> 00:06:46.158 When m is large it is very close to e to the minus k n over m. 00:06:46.471 --> 00:06:49.490 Same number, and far easier to see what it does. 00:06:50.287 --> 00:06:54.978 Turn it around. The chance that a given bit has been set is one minus that. 00:06:55.175 --> 00:06:57.240 And this curve is exactly that number, 00:06:57.323 --> 00:07:01.700 for our sixteen bit row with three hash functions, as n climbs. 00:07:02.497 --> 00:07:03.621 With three items in, 00:07:03.704 --> 00:07:07.223 the formula says about forty three percent of the bits are ones. 00:07:07.327 --> 00:07:09.995 We counted eight out of sixteen, which is fifty. 00:07:10.078 --> 00:07:13.202 With only sixteen bits that is the sort of luck you get. 00:07:13.398 --> 00:07:15.199 Now push n up to twelve. 00:07:15.740 --> 00:07:18.002 Nearly ninety percent of the row is ones, 00:07:18.085 --> 00:07:22.312 and at that point almost any pattern you ask about is already covered by something. 00:07:22.508 --> 00:07:26.782 The false positive rate climbs with n, and this is the reason why. 00:07:27.578 --> 00:07:32.781 So now the query itself. An item that was never inserted names k bits. 00:07:32.977 --> 00:07:38.142 Each one is a one with probability P one, and if we treat those as independent, 00:07:38.225 --> 00:07:42.057 all k of them are ones with probability P one to the k. 00:07:42.482 --> 00:07:43.560 There it is. 00:07:43.643 --> 00:07:46.114 The false positive rate, epsilon, 00:07:46.197 --> 00:07:51.445 is one minus e to the minus k n over m, all raised to the k. 00:07:51.642 --> 00:07:55.042 Read the exponent as the total number of bits you have set, 00:07:55.125 --> 00:08:00.245 k of them for each of n items, divided by the room you gave them to spread out in. 00:08:01.042 --> 00:08:03.748 Read the rest of it the way an engineer reads it. 00:08:03.945 --> 00:08:06.325 n is handed to you by the problem. 00:08:06.522 --> 00:08:08.914 m is what you are willing to pay for. 00:08:09.111 --> 00:08:12.058 And k is the one you actually get to choose, 00:08:12.141 --> 00:08:14.975 and it is not at all obvious which way to push it. 00:08:16.066 --> 00:08:18.110 So, choosing k. 00:08:18.724 --> 00:08:21.790 Fix the budget at ten bits an item, which is the number you 00:08:21.790 --> 00:08:26.272 will see quoted everywhere, and the rate depends on k and nothing else. 00:08:26.468 --> 00:08:30.022 Here it is, plotted against the number of hash functions. 00:08:30.818 --> 00:08:32.314 With one hash function, 00:08:32.398 --> 00:08:36.822 each item sets a single bit, and the rate is about nine and a half percent. 00:08:36.925 --> 00:08:39.968 Nearly one query in ten comes back wrong. 00:08:40.510 --> 00:08:43.584 Two hash functions: three point three percent. 00:08:43.668 --> 00:08:46.188 Three: one point seven. 00:08:46.500 --> 00:08:50.690 Every extra hash function is another bit that has to be a one by accident, 00:08:50.774 --> 00:08:53.166 and that gets rapidly less likely. 00:08:54.218 --> 00:08:57.330 Five hash functions gets you under one percent. 00:08:57.526 --> 00:09:01.986 Seven gets you eight in a thousand, and that is the best this budget can do. 00:09:02.782 --> 00:09:05.194 Now watch what happens if you keep going. 00:09:05.278 --> 00:09:08.030 Ten hash functions is worse than seven. 00:09:08.134 --> 00:09:10.190 Fourteen is worse than three. 00:09:10.294 --> 00:09:13.000 The curve turns around and climbs back up. 00:09:13.482 --> 00:09:15.883 And the reason is sitting in the formula. 00:09:15.966 --> 00:09:20.914 Every extra hash function is one more bit a query has to match, which helps you. 00:09:21.018 --> 00:09:23.953 But it is also one more bit set on every insert, 00:09:24.036 --> 00:09:28.564 so the exponent grows and the row fills up faster, which hurts you. 00:09:28.878 --> 00:09:31.374 Past a point the second effect wins. 00:09:32.288 --> 00:09:36.304 The minimum is where those two balance, and it lands somewhere clean. 00:09:36.502 --> 00:09:40.226 The best k is m over n times the natural log of two, 00:09:40.310 --> 00:09:43.062 which for ten bits an item is six point nine. 00:09:43.514 --> 00:09:45.106 So you use seven. 00:09:46.158 --> 00:09:48.886 And there is a check you can run in production. 00:09:49.198 --> 00:09:53.796 At the optimal k the row ends up with almost exactly half its bits set. 00:09:53.900 --> 00:09:56.084 Half ones, half zeros. 00:09:56.397 --> 00:10:01.146 If your filter is much fuller than half, you are running too many hash functions. 00:10:02.658 --> 00:10:04.680 Which leaves the budget itself. 00:10:04.876 --> 00:10:07.649 Substitute that optimal k back into the rate, 00:10:07.732 --> 00:10:11.958 and the whole expression collapses into one number raised to the bits per item. 00:10:12.410 --> 00:10:16.684 About zero point six two, to the power m over n. 00:10:17.226 --> 00:10:20.512 So here is the curve an engineer actually wants. 00:10:20.708 --> 00:10:25.120 Bits per item across the bottom, false positive rate up the side. 00:10:25.316 --> 00:10:27.814 At eight bits an item, two percent. 00:10:28.726 --> 00:10:31.432 At ten bits, eight in a thousand. 00:10:31.884 --> 00:10:34.671 At fourteen, about one in a thousand. 00:10:35.123 --> 00:10:39.138 At twenty bits an item you are down to seven in a hundred thousand, 00:10:39.222 --> 00:10:42.764 and you are still using less than three bytes a URL. 00:10:43.560 --> 00:10:48.380 Every extra bit per item multiplies the error by roughly zero point six two. 00:10:48.692 --> 00:10:51.526 That is what makes ten the number people quote. 00:10:51.839 --> 00:10:54.646 It is the first place the curve is properly flat, 00:10:54.730 --> 00:10:56.796 and it is under one percent. 00:10:57.594 --> 00:10:59.336 And look at the shape of it. 00:10:59.788 --> 00:11:05.024 Going from three bits an item to eight is cheap, and it buys you an enormous amount. 00:11:05.128 --> 00:11:06.891 After that it gets expensive, 00:11:06.974 --> 00:11:11.492 because you are paying linearly for an error that is shrinking exponentially. 00:11:12.565 --> 00:11:16.037 One more property, and it is the one that catches people out. 00:11:16.652 --> 00:11:19.262 You cannot remove anything from a Bloom filter. 00:11:19.345 --> 00:11:24.094 Here is why, on the row we already have, with the same three items in it. 00:11:25.146 --> 00:11:28.096 Suppose we want to take the first item back out. 00:11:28.200 --> 00:11:33.286 Its bits were two, seven, and eleven, so the obvious move is to clear those three. 00:11:33.990 --> 00:11:37.961 Now ask about the second item, which is still very much in the set. 00:11:38.065 --> 00:11:41.003 Its bits are four, seven, and thirteen. 00:11:41.315 --> 00:11:42.814 Four is a one. 00:11:43.127 --> 00:11:44.718 Thirteen is a one. 00:11:44.915 --> 00:11:48.585 And seven is now a zero, because we just cleared it. 00:11:49.637 --> 00:11:54.467 So the filter says definitely absent, about an item that is definitely present. 00:11:54.919 --> 00:11:56.682 That is a false negative, 00:11:56.765 --> 00:12:01.050 and it is the single answer this structure promised you it would never get wrong. 00:12:01.846 --> 00:12:05.551 The bit at seven was never the first item's bit to give back. 00:12:05.654 --> 00:12:09.962 It was shared, and nothing in the row records how many items are leaning on it. 00:12:10.275 --> 00:12:13.898 So we put it back, and we do not do that again. 00:12:14.695 --> 00:12:18.422 Which gives us the rule, and it is worth stating plainly. 00:12:19.819 --> 00:12:23.288 A Bloom filter supports insert, and it supports query, 00:12:23.371 --> 00:12:25.473 and it does not support delete. 00:12:25.670 --> 00:12:28.408 If the things you are tracking ever go away again, 00:12:28.491 --> 00:12:30.698 this is the wrong structure for them. 00:12:31.494 --> 00:12:33.713 There is a variant that fixes it. 00:12:33.909 --> 00:12:39.538 Replace each bit with a small counter, increment on insert, decrement on delete, 00:12:39.621 --> 00:12:43.291 and now the shared position knows that two items are leaning on it. 00:12:43.488 --> 00:12:44.905 You pay for that. 00:12:45.217 --> 00:12:48.747 Four bit counters make the whole thing four times bigger, which was most 00:12:48.747 --> 00:12:51.999 of the reason you reached for a Bloom filter in the first place. 00:12:53.651 --> 00:12:55.730 So where does this earn its keep? 00:12:56.043 --> 00:12:58.087 A crawler is the clean case. 00:12:58.399 --> 00:13:02.405 You pull a URL off the frontier, and before you spend a network round trip 00:13:02.405 --> 00:13:05.610 on it, you ask whether you have fetched it already. 00:13:06.406 --> 00:13:09.019 The filter answers in the two ways we know. 00:13:09.216 --> 00:13:11.606 Definitely new, and you fetch it. 00:13:11.689 --> 00:13:14.592 Probably seen, and you drop it on the floor. 00:13:15.644 --> 00:13:19.764 A billion URLs at ten bits each is a gigabyte and a quarter, 00:13:19.847 --> 00:13:23.352 which fits in memory on any machine you would run a crawler on. 00:13:23.435 --> 00:13:25.918 The exact set was sixty four gigabytes, 00:13:26.001 --> 00:13:29.275 and a disk seek for every link on every page. 00:13:30.072 --> 00:13:35.006 At seven hash functions the rate is eight in a thousand, so about eight million URLs 00:13:35.006 --> 00:13:40.080 out of a billion get reported as seen when they never were, and never get fetched. 00:13:40.532 --> 00:13:44.503 On a web that size, that is a rounding error in your coverage. 00:13:45.300 --> 00:13:47.925 And notice which way the errors fall. 00:13:48.121 --> 00:13:52.859 What cannot happen is a page you have already fetched coming back as new. 00:13:53.172 --> 00:13:54.728 That is the one that puts a crawler 00:13:54.728 --> 00:13:59.349 in a loop, and it is precisely the answer the filter is exact about. 00:14:00.262 --> 00:14:02.306 So that is the whole structure. 00:14:02.502 --> 00:14:04.558 Bits instead of items. 00:14:04.662 --> 00:14:07.751 k hash functions instead of a comparison. 00:14:07.947 --> 00:14:13.486 A false positive rate you can compute before you ship. And no deletions, ever.