Feedback: Cuckoo filter

[umangkumarr]

Inconsistency Between Redis Documentation and Referenced Paper Regarding Cuckoo Filter Load / Fill Rates

Page: https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/

I noticed an inconsistency in the documentation for cuckoo filters when comparing the Redis documentation with the research paper linked on the same page.

The linked paper:
Cuckoo Filter: Practically Better Than Bloom
(https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) states the following:

"With k = 2 hash functions, the load factor α is 50% when the bucket size b = 1 (i.e., the hash table is directly mapped), but increases to 84%, 95% or 98% respectively using bucket size b = 2, 4 or 8."

However, the Redis documentation under “Choosing the Bucket Size”
(https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/#choosing-the-bucket-size-bucketsize) states:

"When bucket size of 1 is used the fill rate is 55% and false positive error rate is 2/256 ≈ 0.78% which is the minimal false positive rate you can achieve. Larger buckets increase the error rate linearly but improve the fill rate of the filter. For example, a bucket size of 3 yields a 2.34% error rate and an 80% fill rate. Bucket size of 4 yields a 3.12% error rate and a 95% fill rate."

Question

Could you clarify which values are correct, or whether the Redis implementation deviates intentionally from the results in the paper (e.g., due to differences in assumptions, parameterization, fingerprint size, or implementation-specific adjustments)?

[dwdougherty]

@LiorKogan: Can you or somebody from engineering address @umangkumarr's inquiry?

[LiorKogan]

@umangkumarr Just to clarify - are you referring to 50% vs 55%?

[umangkumarr]

@LiorKogan
Referring to:

• 50% vs 55% for the bucket size of 1.
• As per research paper, for bucket size of 2 fill rate is 84%. Then how come fill rate is 80% for bucket size of 3 (as per redis doc)

[LiorKogan]

These numbers indeed look strange. They could be based on a simulation instead of a theoretical analysis, but this is still unexpected. I don't have a good answer to that. We would need to find some time to analyze it.

[umangkumarr]

Hi @LiorKogan
Can you please share an ETA? Our solution for a feature depends on it.

[LiorKogan]

Sorry, I cannot provide any ETA.

Maybe @ashtul can recall something about these numbers?

[ashtul]

@umangkumarr @LiorKogan
The fill rate may and will change depends on your data and whether or not you allow duplicate entries, (which you shouldn't allow unless you absolutely need deletion).
IMO, using a single slot per bucket is bad practice.

[umangkumarr]

@ashtul We are planning to go with the bucket size of 2. Need assurance that the fill rate in that case will be 84%.
Also why would there be duplicate entires for a single key even if we allow deletion.

[ashtul]

@umangkumarr no one can give you any guarantee. With duplicates and the 'right' data, you can block the filter at less than 1%.
You will have duplicates of entries since the fingerprint size is 8 bits so ultimately, different entries will get the same fingerprint. Therefore, duplicates does not mean the same entry twice but rather two entries that end up with the same values.