Lock Free Cuckoo Filter
Contributors Yifei Wang (xsxszab) Yuchen Wang (yw7) Summary We implemented an efficient lock-free cuckoo filter in C++. Experiments demonstrate that our filter significantly outperforms its coarse-grained lock counterpart while reaching throughput comparable to the fine-grained lock version on both GHC and PSC platforms. 1. Background 1.1 Cuckoo Hash Table and Cuckoo Filter Cuckoo Hashing Cuckoo hashing is a type of open-addressing hash algorithm with $\mathcal{O}(1)$ worst-case lookup time. It uses two hash functions, $hash_1$ and $hash_2$, to identify two potential locations for a key. If any of these two locations is empty, the key will be inserted there. Otherwise, Cuckoo hashing kicks out one item, places the new key, and moves the displaced key to its alternative location. This replacement process continues until an empty entry is found. ...