In the previous article, we saw how to size and create a Cuckoo Filter. Here we'll see how to do searches, add new values, and remove old ones.
Adding a value to a Cuckoo Filter
For a CF, searches and removals are simple and depend entirely on the addition logic, so it makes sense to start there. Let's assume we already have a CF with some previously stored fingerprints. We are using 4-bit fingerprints, so a single hex digit (1–9, A-F) is enough. The CF has 8 buckets, each with 2 slots.
First, consider the easy case in Figure 11½–18. We want to add GROUCHO; we calculate its fingerprint (A) and indices (2 and 7), and both buckets have free space, so we can add the fingerprint in either bucket.
Figure 11½–18: When both buckets are available for an addition, we can pick either.
For a second case (see Figure 11½–19) suppose HARPO should go in buckets 2 or 1. In this case, bucket 2 is full, but bucket 1 has space, so we have no choice but to add the new fingerprint there.
Figure 11½–19: As long as at least one of the picked buckets has some free slot, additions are immediate
Finally (Figure 11½–20) let's go for the difficult case. CHICO should go in either bucket 3 or 5, but both are full. In this case, we randomly pick a value in one bucket (here, the 9 in bucket 5), place CHICO's fingerprint there, and relocate the kicked-out value. How do we do this? Given the fingerprint (9) and the bucket (5) we can calculate that the companion bucket would be 7. The bucket has free space, so the 9 goes there and we are done.
Figure 11½–20: If both buckets are full, we kick a value out to make space; this may end in a whole run of "kicks"
But what happens if bucket 7 is also full? That starts a sequence of "kicking out" steps, in which you again pick a value from the bucket, use its (now free) space, and relocate the kicked-out value to its alternative bucket. However, there's a possible issue: this sequence might get into a loop, so after a maximum number of attempts we have to accept that we cannot add the value and roll back all our changes. (But why? See question 11½–10.)
Let's now get to coding. We'll need some auxiliary functions to calculate fingerprints, indices, hashes, etc.
➊ const fingerprintOf = (filter, item) =>
hashWithSeed(item, 0) & ((1 << filter.p) - 1) || 1;
➋ const hashBucket = (filter, item, seed) =>
hashWithSeed(item, seed) % filter.b;
➌ const index1 = (filter, item) => hashBucket(filter, item, 1);
➍ const index2 = (filter, index1, fingerprint) =>
index1 ^ hashBucket(filter, fingerprint, 2);
➎ const twoBuckets = (filter, item) => {
const fingerprint = fingerprintOf(filter, item);
const i1 = index1(filter, item);
return {
fingerprint,
indices: [i1, index2(filter, i1, fingerprint)]
};
};
To compute a fingerprint ➊ we use the same hashWithSeed function we've been using, masking to get just p bits; should the fingerprint be zero, we return 1 instead. (See question 11½–9 for an alternative.) The hashBucket function ➋ is auxiliary; given a number and a seed, it uses hashing and the modulus operation to produce a bucket number. The index functions ➌ ➍ apply the formulae we described to produce both indices. For maximum independence, we use different seeds for the hashes in each calculation. Finally ➎ twoBuckets just uses the first four functions to return an object with the fingerprint and the two indices.
Now we can add a value to the CF.
➊const MAX_KICKS = 500;
const add = (filter, item) => {
➋if (filter.c + 1 > filter.n) {
throw new Error("Cuckoo filter load limit reached");
}
➌const { fingerprint, indices } = twoBuckets(filter, item);
for (const index of indices) {
if (filter.buckets[index].length < filter.s) {
filter.buckets[index].push(fingerprint);
filter.c++;
return true;
}
}
➍const originalBuckets = new Map();
➎let index = singlePickAll(indices);
➏let carriedFingerprint = fingerprint;
for (let kick = 0; kick < MAX_KICKS; kick++) {
// Save the original bucket if it hasn't been saved yet.
➐ const bucket = filter.buckets[index];
if (!originalBuckets.has(index)) {
originalBuckets.set(index, bucket.slice());
}
➑ const slot = randomInt(0, bucket.length);
[carriedFingerprint, bucket[slot]] = [
bucket[slot],
carriedFingerprint
];
index = index2(filter, index, carriedFingerprint);
➒ if (filter.buckets[index].length < filter.s) {
filter.buckets[index].push(carriedFingerprint);
filter.c++;
return true;
}
}
➓for (const [bucketIndex, originalBucket] of originalBuckets) {
filter.buckets[bucketIndex].splice(
0,
filter.buckets[bucketIndex].length,
...originalBucket
);
}
return false;
};
To detect "kick out loops", we'll have ➊ a fixed upper limit on how many times we'll attempt the removal process. For starters ➋ we check if the CF is loaded enough; if so, we reject the addition. Then ➌ we calculate the fingerprint and indices for the value, and if there's free space in any corresponding bucket, we put the fingerprint there, and we're done. We may have to restore buckets later ➍ so we'll use the originalBuckets map to store the original versions of any buckets we may modify.
At this point ➎ we know we'll have to kick out some value, so we use the singlePickAll function we developed in the Sampling section of Chapter 8 in the book; it takes a whole array as input and randomly picks a value, so index points to one of the two buckets for the value. The carriedFingerprint variable ➏ will represent the kicked-out value in the loop we'll do. If we hadn't yet modified the bucket ➐ we'll save it into the originalBuckets map so we can later restore it, if need be.
We want to remove a random fingerprint from the bucket; we use the randomInt function from the Choosing Numbers Randomly section of Chapter 8 to select some slot ➑ and we use it for the value we were moving. If there is space in the slot ➒ we are done; otherwise, the loop will continue trying to relocate the value in carriedFingerprint. Should the loop finish because of the iterations limit ➓ we'll restore all buckets from the map, so they remain as they were.
We now know how to add values to a CF; we can move on to searching, which will need much less code, as we'll see.
Searching a Cuckoo Filter
Let's start by reviewing some examples. In Figure 11½–21 we see the search for CHICO: we calculate the two indices and check whether the fingerprint is at either. We find it, so the search was positive.
Figure 11½–21: A search for an inserted value is successful, for its fingerprint will be at one of two buckets
Now, we could look for ZEPPO; see Figure 11½–22. Why. We calculate the fingerprint and indices, but in this case the fingerprint isn't found in any bucket; we know ZEPPO was never stored, and the search is negative.
Figure 11½–22: A search fails if the fingerprint is not at any of the value's two buckets
Finally, we can also have false positives; see Figure 11½–23. Imagine that when looking for GUMMO, its fingerprint is A (the same as GROUCHO's) and its first index is 7. Calculating the second index would produce 2; both indices match GROUCHO's, and we'd wrongly believe GUMMO had been inserted.
Figure 11½–23: There's always the possibility that two different values will produce the same fingerprint and indices, and that would produce a false positive
Now we can get to actual code, which is quite short.
const find = (filter, item) => {
➊ const {
fingerprint,
indices: [i1, i2]
} = twoBuckets(filter, item);
➋ return (
filter.buckets[i1].includes(fingerprint) ||
filter.buckets[i2].includes(fingerprint)
);
};
This logic (just two lines!) is straightforward. We first ➊ calculate the fingerprint and indices, then ➋ check whether the former is included in either bucket; very direct! (See question 11½–11 for an alternative way to write this code.)
Now we just need to remove a value from a CF; this will take only a few more lines than a search.
Removing a value from a Cuckoo Filter
Since we already know how to find a value in a CF, removal is really simple.
const remove = (filter, item) => {
➊ const { fingerprint, indices } = twoBuckets(filter, item);
➋ for (const index of indices) {
const slot = filter.buckets[index].indexOf(fingerprint);
➌ if (slot !== -1) {
filter.buckets[index].splice(slot, 1);
filter.c--;
return true;
}
}
return false;
};
As in find we start ➊ by calculating the fingerprint and the bucket indices. Then ➋ we check both buckets; if the fingerprint is found at any of them ➌ we just remove it, and we're done.
Bye for now! In the next article in the series, we will introduce XOR Filters, which trade dynamic updates flexibility for maximum speed and lower memory requirements.
Questions
11½–9. If at first you fail… If, when calculating the fingerprint, the hash function returns a zero, would this alternative work? Why or why not?
const fingerprintOf = (filter, item) =>
hashWithSeed(item, 0) & ((1 << filter.p) - 1) ||
hashWithSeed(item, 4) & ((1 << filter.p) - 1);
11½–10. Let it Be. Why do we need to restore the buckets to their original values? Would the CF be broken if we didn't do that?
11½–11. Some like it short. Just for variety, can you rewrite find to use the .some method?
Top comments (0)