Available in: Redis Stack
Time complexity: O(1)
Create a Cuckoo Filter as
key with a single sub-filter for the initial amount
capacity for items. Because of how Cuckoo Filters work, the filter is
likely to declare itself full before
capacity is reached and therefore fill
rate will likely never reach 100%. The fill rate can be improved by using a
bucketsize at the cost of a higher error rate.
When the filter self-declare itself
full, it will auto-expand by generating
additional sub-filters at the cost of reduced performance and increased error
rate. The new sub-filter is created with size of the previous sub-filter
Like bucket size, additional sub-filters grow the error rate linearly.
The size of the new sub-filter is the size of the last sub-filter multiplied by
expansion. The default value is 1.
The minimal false positive error rate is 2/255 ≈ 0.78% when bucket size of 1 is used. Larger buckets increase the error rate linearly (for example, a bucket size of 3 yields a 2.35% error rate) but improve the fill rate of the filter.
maxiterations dictates the number of attempts to find a slot for the incoming
fingerprint. Once the filter gets full, high
maxIterations value will slow
down insertions. The default value is 20.
Unused capacity in prior sub-filters is automatically used when possible. The filter can grow up to 32 times.
2^nnumber. The filter will likely not fill up to 100% of it's capacity. Make sure to reserve extra capacity if you want to avoid expansions.
expansion. Expansion is rounded to the next
redis> CF.RESERVE cf 1000 OK
redis> CF.RESERVE cf 1000 (error) ERR item exists
redis> CF.RESERVE cf_params 1000 BUCKETSIZE 8 MAXITERATIONS 20 EXPANSION 2 OK