Introduction

A lock-free cuckoo filter implementation.

Requirements

• C++ 17
• CMake >= 3.4.1
• GCC 4.1 or newer (for __sync_bool_compare_and_swap) and x86_64 platform
• libssl-dev (for generating MD5 fingerprint)
• (optional) Doxygen, graphviz

Usage

• install build-essential, cmake and libssl-dev.
• create dir ./build under project root directory and cd into it.
• run cmake ...
• run make to build both the filter shared library and test cases. New test cases can be added by creating .cpp file(s) under ./test, the CMake script will automatically detect and build new test cases.
• executable test can be found in ./build/bin/.
• (optional) install doxygen, graphviz and run doxygen in project root directory to generate documents.

Reports

• Project Proposal
• Milestone Report
• Final Report

Future Optimizations

• Store all fingerprints in a single, contiguous memory block to improve cache locality and reduce allocation overhead.
• Implement a breadth-first search (BFS)-based replacement algorithm for more efficient eviction decisions.

References

[1] Cuckoo Filter: Practically Better Than Bloom

[2] Lock-free Cuckoo Hashing

[3] MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing

[4] Hazard pointers: safe memory reclamation for lock-free objects