Hi all,
I’ve been working on a concurrent cuckoo filter implementation in Rust: atomic-cuckoo-filter.
A cuckoo filter is a probabilistic data structure for fast set membership testing. Unlike traditional implementations, this version uses lock-free atomic operations and is designed for high-concurrency environments.
Feedback and suggestions are welcome!
I wonder why did you choose Cuckoo algorithm for this scenario? It uses two-jump lookup process in worst cases, which introduces some performance penalty compared to alternatives that use sequential memory scans.
Is it somehow connected to the concurrent access?
Cuckoo filters support deletions. Is there any alternatives with better cache-line locality for lookups?
I think that this is might be relevant:
In general there are filter algorithms that focus on cache-friendliness and memory-parallelism that beat Cuckoo and standard Bloom. As far as I understand the main advantage of Cuckoo (in terms of lookup speed) is that it provides predictable worst-case performance, while trading off average-case performance.
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.