hesela.devCuckoo filter
A cuckoo filter is an approximate-membership structure that stores short fingerprints in candidate buckets and supports insertion, lookup and deletion subject to its update contract.
A positive lookup is not proof that a key has an outstanding insertion: deleting an absent or already-deleted key can remove another key's fingerprint and cause false negatives. [3] Preserving one fingerprint per successful insertion allows a legitimate deletion to retain a colliding live key. [1] Positive-only insertion suppression is also unsafe when later deletions must preserve distinct keys. [4] Our pinned-library experiment forces collisions; it does not measure their frequency or reproduce the paper's benchmarks. [5]
Relations
- related
- bloom-filter, ribbon-filter, lsm-tree
Citations
- Bin Fan, David G. Andersen, Michael Kaminsky and Michael D. Mitzenmacher. Cuckoo Filter: Practically Better Than Bloom. CoNEXT 2014, section 3. DOI: 10.1145/2674005.2674994.
- Redis command reference. CF.DEL: deletion precondition and false-negative warning. Documentation review, not a Redis execution test.
- Redis command reference. CF.ADDNX: fingerprint matches can suppress insertion. Documentation review, not a Redis execution test.
- Hesela. Cuckoo deletion contracts, controlled-collision experiment and reproduction instructions.