algorithmfilterhashredisbloom-filter

Between redis bloom and cuckoo filters, which is better in terms of performance?


Previous stackoverflow question regarding bloom and cuckoo filter comparison is 13 years old (Here) and predates redis-modules by a decade. And I guess cuckoo filters must have matured quite a bit over the years in terms of adoption.

So keeping that in mind, which is a better choice among the two in terms of performance as far as redis implementations are concerned? Is cuckoo filter an obvious choice over bloom given the extra features (like deletion and insertion count)? Are there any trade-offs?

I want to implement these filters for "existing username" invalidation. Are there any better techniques?


Solution

  • I guess cuckoo filters must have matured quite a bit over the years in terms of adoption.

    Cuckoo filters are relatively simple, so no 'maturity process' was required.

    That being said, since cuckoo filters introduction in 2014 many improvements have been suggested (and continuously being suggested) including:

    and even

    Whether each of these methods guarantees better results (insert performance, query performance, memory consumption, etc.) for each use case requires a comparative analysis (I'm not aware of such unbiased research).

    As for adoption:

    So keeping that in mind, which is a better choice among the two in terms of performance as far as Redis implementations are concerned? Is cuckoo filter an obvious choice over bloom given the extra features (like deletion and insertion count)? Are there any trade-offs?

    The question you referred to already has excellent answers concerning the performance and the tradeoffs between these two algorithms. It also discusses why performance is not just a single metric (insert performance vs. query performance; average time vs. worst time, etc.). Since Redis implements the data structure described in the original cuckoo filter paper (albeit in a highly optimized way), all issues discussed apply to the Redis implementation as well.


    Note that in addition to Bloom and cuckoo filters several additional approximate membership query data structures were suggested, including XOR filters, Ribbon filters, and Binary fuse filters.

    Which one is most suitable for each use case requires a non-trivial analysis.