Playground

Everything below runs the same distillate build you would install, in this tab, over keys generated on the spot. Nothing is simulated and no numbers are hard-coded.

Keys to insert

Up to 100,000. Past that the playground refuses rather than freeze the tab.

Target false positive rate

Binary Fuse ignores this; its rate is fixed by fingerprint width.

Build

Query a key

Inserted keys are key-0 through key-9999. Trymiss-22, which none of them ever saw.

Query

Add a key after the build

The Bloom filters and Cuckoo take it. Binary Fuse is static and cannot, which is the trade it makes for its size.

Add

Grow past the build

Adds that many more generated keys. Classic and Blocked Bloom were sized for the build, so their measured rate climbs past the target. Scalable Bloom opens larger stages instead and stays under it. Cuckoo was sized for the build too; once full it refuses keys rather than drop one it holds.

Grow

Delete a key

Only Cuckoo can delete, and only a key it holds. The other filters keep it, and say why.

Delete

Structure	Keys held	Not found	Bits/key	Size	Stages	Measured rate	Last query
Classic Bloomdistillate/bloom
Blocked Bloomdistillate/blocked
Binary Fuse 8distillate/fuse
Scalable Bloomdistillate/scalable
Cuckoodistillate/cuckoo

Count how often, not whether

Every structure above answers have I seen this key. A Count-Min sketch answers how many times, and it is the only one here whose size was fixed before it saw a key: growing the set costs it nothing and buys it less accuracy. It cannot answer membership at all, which is why it is not a row in that table.

Record occurrences of

How many

The build recorded each key once. Add more and the estimate follows the truth, never below it.

Record

Grid

Size

Recorded

True count

Estimate

Overestimate

Bound

The estimate is never below the truth. Collisions with other keys only push it up, by at most the bound, which is the error factor times everything recorded. So the bound grows with the stream: an overestimate of a few hundred is noise for a key seen eighty thousand times and useless for one seen three times.

Which keys, not how many times

Count-Min answers for a key you name. Top-K lists the heaviest keys without being asked about any, because it keeps the keys it counts. It is fed by the same Record form above: record more of a key and watch it climb.

Error

Recorded

Key	Estimate	Lower bound	True count

The truth always sits inside the bracket. The estimate is never below the true count and the lower bound never above it; the gap is at most the error. A key that falls off the list was never heavier than the error.

How slow is the tail, not how many

A DDSketch answers what value sits at this quantile, within a relative error of the true one, tails included. The build fed it one latency per key, around 100 ms with a long tail, and it keeps the target above as its relative accuracy. The exact column comes from every value the page recorded itself.

Record a value

How many

A hundred slow requests move p99.9 and leave p50 where it was. Negative values and zero count too.

Observe

Recorded

Accuracy

Quantile	Exact	Estimate	Band

The estimate always sits inside the band. The band is the exact value plus and minus the relative accuracy, so p99.9 is as close in proportion as p50, where a sketch with a rank guarantee would let the tail drift furthest.

What share is under a threshold

A KLL sketch answers what share of values is at or below this one, and every quantile, within an error in rank that holds whatever the values are. It holds the same latencies as the DDSketch above, and the form there records into both. It keeps its default k and a fixed seed, so every build shows the same answers.

Recorded

k

Rank bound

Quantile	Exact	KLL	DDSketch	KLL rank error

Share	Exact	KLL

Every rank error stays under the bound. It is a share of everything recorded, so an SLO question such as the share under 200 ms is answered as well as the median. In the far tail a small share is a long way in value: at p99.9 KLL can sit within a tenth of a percent in rank and still read hundreds of milliseconds low, where DDSketch stays within its relative accuracy.

How alike two sets are, from a sketch of each

A MinHash answers how much do these two sets overlap as their Jaccard similarity: shared items over all items. The build made set A from the keys above and set B from as many keys starting halfway through them, so they share half of each. Each set is sketched into 128 slots; the exact figure comes from the sets the page keeps itself.

Record intoSet ASet B

Item

Recording set A's keys into set B pulls the two together; new items push them apart.

Include

Set A

Set B

Exact

Estimate

Band

Slots

The estimate lands inside the band about 95% of the time.The band is the exact figure plus and minus two standard errors, and a MinHash's error is a matter of chance rather than a bound, so now and then it falls outside. More slots narrow the band; a set smaller than the slot count widens it.

Which keys differ between two sets, at the cost of the difference

Rateless set reconciliation tells a client exactly which keys it and a server do not share. The server holds the keys above; the client lacks some of them and holds as many of its own, d in all. The server streams frames of 64 coded symbols, and the client stops it once it decodes. Each run builds both sides fresh, since a stream serves one peer.

Keys that differ, d:

100

Reconcile

Frames

Symbols

Sent

Sending the set

Decoded

Only the server

Only the client

What is sent follows d, not the size of the set. Each symbol is 20 bytes whatever the keys, and about 1.4 symbols per differing key decode a large difference; a small one still pays for a whole frame. Sending the set means its keys as UTF-8, the least that could cost. The client learns the server's keys as 64-bit hashes; the server maps them back by hashing its own, as shown here.

How many two segments share, from a sketch of each

A Theta sketch counts distinct keys, and two of them combine by union, intersection and difference, so overlaps are answered from sketches kept apart. Segment A is the keys above; segment B holds as many, sharing the fraction you pick and making up the rest from keys of its own. Each is sketched at k = 4096, beside a HyperLogLog at p = 16, which can only union and so estimates the rest by inclusion-exclusion.

Overlap:

10

%

Count	Exact	Theta, 2 sd	HLL
A or B
A and B
A, not B

A false positive is the filter working, not a bug. These structures trade exactness for space: a key that was never inserted can still answer yes, at roughly the target rate. What they never do is the reverse.

Not found is zero, and stays zero. That column counts inserted keys the filter cannot find. It is guaranteed to be zero by how these structures are built, not a lucky property of this sample: a key that was added always answers yes. The measured rate is the false positive rate, checked over 20,000 keys that were never inserted; it is an estimate, so expect it within roughly a factor of two of the target at these sample sizes. Binary Fuse ignores the target entirely, so its rate is not compared against one.

For how to pick between these five, seeChoosing a structure. For what a target rate costs in memory at your capacity, see thesizing calculator.