search

axiomhq / rust-cuckoofilter

Cuckoo Filter: Practically Better Than Bloom (In Rust)
MIT License
271 stars 38 forks source link

If NotEnoughSpace, the add method adds the given element but removes another random element #26

Closed florianjacob closed 6 years ago

florianjacob commented 6 years ago

Document this unexpected behaviour, and describe how this could be fixed with an eviction cache.

@seiflotfy did I miss something?

seiflotfy commented 6 years ago

I might be misunderstanding, but isn't this what cuckoo filter already does?

florianjacob commented 6 years ago

isn't this what cuckoo filter already does?

I could not find something like this, To me, it looks like the last content of fp is implicitly dropped after https://github.com/seiflotfy/rust-cuckoofilter/blob/b27c79f4bcf4a5bbaa6f4283747a10e1ec310314/src/lib.rs#L178 Of course it's totaly possible that I missed it or did not understand it. 😅 Can you point me to the code where that is implemented, or explain how it's done?

I stumbled over this problem somewhere else, and found out the reference implementation handles this with something they call the “victim cache”.

florianjacob commented 6 years ago

For reference what I mean, the struct for the victim cache in the author's implementation. The add method checks the victim cache and fills it, and it is additionally checked in contains.

We can see this behaviour is missing in the current rust-cuckoofilter when increasing total_items e.g. to 1048576 (=2^20) in the false_positive_rate test, which will lead to a fail in this assertion, because a random element is dropped from the filter when not all elements can be inserted.