FA-73284 / Probabilistic sketches / Member archive

Cuckoo filter with partial-key relocation: failed insert keeps partial relocations · case 04

A failed insert silently evicts some other item's fingerprint, creating a false negative.

Member previewVariant 4 · 3 implementations · 10 checks per implementation

Case contract

Input {m (power of two), max_kicks, ops} with pre-hashed 32-bit items. Fingerprint f is bits 24-31, with 0 remapped to 1 (0 marks an empty slot in packed tables). i1 = h mod m and the alternate bucket is alt(i, f) = (i XOR (f*0x5bd1e995 mod 2^32)) mod m, so it is computable from the fingerprint alone. Buckets hold 2 fingerprints. Insert tries i1, then i2, then performs up to max_kicks evictions starting at i1, swapping slot (kick mod 2); on failure the table is restored and "full" is returned. Delete removes one copy, from i1 first. Return [results, buckets].

Why this case matters

Cuckoo filters give deletable approximate membership for caches and dedup stores; relocation only works if the alternate bucket is derivable from the stored fingerprint.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
fill 0 m=4 kicks=3	`[["ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "full", true, true, false, true, true, true, true, false, false], [[86, 31], [19, 144], [235], [105, 149]]]`	`[["ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "full", true, true, true, true, true, true, true, false, false], [[142, 31], [144], [235, 86], [105, 149]]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.