hur.st

Background

A bloom filter is a bitmap which lets you test if an item is a member of a set, in constant time and constant space. It tells you with 100% certainty if the item is NOT in the set, and it tells you with variable certainty if the item MIGHT be in the set. In other words, it answers yes/no if an item is in the set, but there's a chance of false positives, but no chance of false negatives.

The probability of a false positive is based on the number of items in the set, and the number of bits in the bitmap. Here (http://hur.st/bloomfilter) is a calculator, for example, which lets you say how many items are in the set, and what probability you want for false positives, and it tells you how many bits should be in the bitmap, and how many bits you should set each time you are adding an element into the filter (they call this 'number of hashes').

So you can imagine there are a lot of really interesting applications for bloom filters when you want a really fast, compact way of knowing if something is LIKELY to be true. Like, 'is this request in my cache?'

Bloom filters can also be used to provide some interesting privacy-preserving properties. In Bitcoin, for example, you have a wallet with money stored at a bunch of addresses, and unused addresses where new money can come in. You don't want anyone to just be able to look into your wallet and know all your addresses, but you DO want to be notified when someone sends you money. So you load up a bloom filter with a bunch…

There are 555,278,657 passwords in the database. With a Bloom Filter, you could quickly rule out potential inputs. Even better, there is no need to hash the input, because... it's already a cryptographic hash.

The input SHA-1 provides 160 bits of hash. If we divide that up into 5 hash values of 32 bits, we can get a 3% false positive rate with a 483 MiB Bloom Filter (which will easily fit in memory).

https://hur.st/bloomfilter/?n=555M&p=0.03&m=&k=

This will be blindingly fast. We're talking 5 random reads from memory. Even in the worst case of 5 cache misses, we're still well under 1us. This will let us return "not found" for 97% of inputs that aren't in the database.

If we get a hit there, then we could turn to a larger bloom filter for greater accuracy, but we'd have to actually hash the key to get more hash bits.

Of course if you get hits for all your bloom filters, you still have to do a real lookup to positively confirm that the key is in the database.

> I think what I am trying to say is that cooking can never be standardized, nor should it.

Not that this is what is being attempted here, but rather than one or more recipes that each represents a particular set of curated choices, you could instead create a "recipe as multidimensional model" that captures the entirety of the configuration-space for "the food that is called X", where you can both adjust inputs and see how output parameters (e.g. saltiness, acidity, viscosity) will change, or constrain output parameters to find optimal input parameters.

In other words, something like https://hur.st/bloomfilter/, but for tuning your chocolate-chip cookies.

> Check out this excellent visualization by Thomas Hurst showing how parameters influence each other:

> https://hur.st/bloomfilter/

Blush. However will I cope with all this extra traffic?

One common way to improve bloom filter cache performance is to divide them into blocks - elsewhere is mentioned doing it to the cache line, but it would be interesting to see how much performance would be gained with a more naive approach, for instance, splitting the filter into 4KiB pages.

I've done this for disk-backed filters, but never looked to see if it improved performance generally.

Vernor Vinge's A Fire Upon the Deep (1992) depicts a galaxy of countless highly advanced civilizations in the far future - and describes its "net" as "the net of a million lies". However, it also depicts every message with an AI's best judgement of its reliability - for example:

>From: Sandor Arbitration Intelligence at the Zoo [A known military corporation of the High Beyond. If this is a masquerade, somebody is living dangerously.]

More examples here: https://hur.st/afutd.html (spoilers if you read more than the From lines)

~391 MB if we store SHA-1 hashes of the URLs (160 bits each) and HN ids and assume 16.3 million posts[1]. (Probably less, since, as you said, some posts are just comments.) If we're okay submitting one out of every hundred URLs as a SHA-1 hashed value to an external server, we can reduce that further to ~18 MB with a bloom filter[2].

[1]: https://www.google.com/search?q=(160+bits+%2B+32+bits)+*+16.3+million&oq=(160+bits+%2B+32+bits)+*+16.3+million

[2]: https://hur.st/bloomfilter?n=16300000&p=0.01