Cuckoo filter + LRU - seems like a natural match for Vector?

[johnhtodd]

We need memory-efficient, CPU-efficient ways of caching large numbers of event keys so that we do not re-transmit the same things more than once (ideally.) However, as mentioned, we have limited memory so we'd like to evict things that aren't recently hot. A Cuckoo filter would be the ideal candidate (it supports deletions, unlike Bloom) but what we really need is Cuckoo + LRU eviction. Any suggestions for a Cuckoo Rust library for starters? I see only one paper on Cuckoo + LRU, and no Rust code for it, and really I see only one Rust Cuckoo implementation.

I don't know how many bits would have to be added to each object for an LRU timer, but it would seem to me that this could be done very efficiently with just a few bits if you divide the memory space into "buckets" and just evict all the members of a bucket when capacity is reached instead of keeping timers/counts. You'd only need the number of bits in each object to match the bucket size. 5 bits, 32 buckets, etc. I'm sure someone more clever has reduced this even more significantly.

We would be open to developing this feature (and probably will) but guidance on easier/better paths is welcome.

Counter-point: we could just use a hash + LRU model, but that doesn't seem to be quite as memory-efficient as Cuckoo.

References:
https://link.springer.com/article/10.1007/s10489-021-02567-0
https://github.com/axiomhq/rust-cuckoofilter
https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

[pront]

Thanks for bringing this up! The combination of Cuckoo filters with LRU eviction is an interesting approach for memory-efficient deduplication. Given the complexity and impact of this proposal, I think this would benefit from a RFC. This would help the community and maintainers evaluate the design more thoroughly and ensure it fits well with Vector's architecture.

Some things to cover:

1. The numbers

• How many unique keys do we want to support?
• What are the memory constraints?
• What false positive rate would be acceptable for your use case?

2. Design specifics

• Describe the algorithm
• Discuss configuration parameters
• What metrics to emit

3. Implementation Considerations

• Is a Cuckoo filter strictly necessary? How does this compare to e.g. hash + LRU or counting Bloom filters?
• How would this integrate with Vector's existing transform pipeline?

[esensar]

Thanks for bringing this up! The combination of Cuckoo filters with LRU eviction is an interesting approach for memory-efficient deduplication. Given the complexity and impact of this proposal, I think this would benefit from a RFC. This would help the community and maintainers evaluate the design more thoroughly and ensure it fits well with Vector's architecture.

Before I go into an RFC, our idea is to work on Cuckoo filter in a separate library and only integrate it into Vector as a part of some component (probably enrichment table - maybe even as an extension to the memory enrichment table). It could also be integrated in some other transforms of course, but the enrichment table is our main goal for now.

The library implementation is a work in progress and because of that, the specification might change too, as we find some better approaches or run into issues with our current approach. We have considered alternatives (https://github.com/axiomhq/rust-cuckoofilter), but it lacks runtime configuration and the additions to the Cuckoo filter (like TTL, LRU) that we need, so we have decided to build our own.

Some things to cover:

1. The numbers

• How many unique keys do we want to support?

This is up to the user when they define the table. The number of bits used for fingerprint (and optionally counter and TTL) multiplied by the maximum number of objects defines the memory usage (note: it is not possible to exactly define maximum number of objects - it will always be slightly bigger, because the number of buckets must be a power of two, so it is increased to the next power of two - https://people.bu.edu/staro/cuckoo_filter_workshop_paper.pdf). All of these parameters are tune-able at the time of creation of the filter table (described below). Resizing is generally not supported, because the fingerprints would have to be rehashed and repositioned in the filter. No resizing also results in a predictable memory usage (it should not change through the filters lifetime, everything is pre-allocated on startup).

• What are the memory constraints?

User-defined (see above answer)

• What false positive rate would be acceptable for your use case?

This is also user-defined, based on the way Cuckoo filters work. The more fingerprint bits, the lower the false positive rate, and this is clearly defined in the original paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) with examples listed in section 7 table 3 with conservative values. Adding bits to the hash size dramatically decreases false positive rates.

2. Design specifics

• Describe the algorithm

The core Cuckoo filter implementation is based on https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf. The LRU implementation was initially inspired by this paper: https://link.springer.com/article/10.1007/s10489-021-02567-0, but the actual implementation is quite different.

NOTE: This is not a final design - this is a preliminary version that we are testing.

Insertions, deletions and presence checks are done as in regular Cuckoo filter, but in this implementation, each slot in a bucket can hold other pieces of data, besides the fingerprint - TTL, LRU counter and any other data that we might want to associate with an item.

If LRU is enabled:

• Each insert and presence check increases the LRU counter for that fingerprint. If an item reaches maximum allowed LRU count (depending on number of bits configured), all items get their LRU counter halved inside that bucket, so that we can keep tracking the difference between the items in a bucket - this means that items from different buckets don't work on the same LRU "scale", so it is hard to compare LRU counters of different buckets, which might need some work.
• When inserting into a full bucket, instead of kicking randomly, kick the item with the lowest LRU. When inserting that item into the alternative bucket, compare that LRU with others and either stop the kicking process if it turns out that LRU is lower than any other in that bucket, or repeat the process.

If TTL is enabled:

• TTL is configured with a default TTL value, number of bits designated for TTL and TTL resolution. TTL resolution is required to fit in larger TTLs in smaller number of bits at the cost of accuracy. Each bucket gets a TTL baseline (which is a timestamp) and then each item gets a TTL as an offset from that baseline. Each insertion checks if new TTL can fit in the designated bits, otherwise it needs to move up the baseline to current time and recalculate.
• Each insertion checks target bucket for potentially expired items, treating them as empty slots and storing new fingerprints in.
• Each presence check also checks TTL and removes the item if expired.
• This ensures we don't need to do full table scans, but we still get correct TTL. Full table scans wouldn't be helpful, because even if we removed items right when they expired, we wouldn't reclaim any memory, because it is all pre-allocated anyways.

Drawbacks to consider:

• It is possible to have duplicate fingers in the filter - either in different buckets or even in the same bucket, because of the fact that there are 2 valid buckets for each item and that they can be moved around as other items are inserted in their place. This can produce confusing results when looking at associated data, because a fingerprint could be stored multiple times in the filter and have different sets of associated data - for that reason, the associated data should really only be used to control the lifetime - like LRU and TTL, because we can tolerate false positives.
• All associated data could really just be related to a different item, sharing the same fingerprint. This is the drawback of only storing hashes (fingerprints), but is to be expected when using probabilistic filters.
• LRU makes sense only on the bucket level. Depending on the configured number of bits, it could make sense on the level of the whole filter, but there is still a chance that less used item will replace a more used item if counter was recently halved.
• LRU is currently LFU actually, but it could be easily changed to LRU (per bucket at least) - there is also the implementation from https://link.springer.com/article/10.1007/s10489-021-02567-0 which behaves more like LRU

• Discuss configuration parameters

Current version that we are working on supports the following configuration parameters:
General Cuckoo filter params:

• fingerprint_bits mainly affects false positive rate -> more bits = less false positives, but more memory consumed
• bucket_size -> larger buckets improve table occupancy, but require higher fingerprint_bits count to achieve the same false positive rate - also extreme bucket sizes affect performance negatively, because they often need to be scanned fully - generally recommended to be 4-8
• max_entries -> maximum number of entries that could be stored in the filter. The actual number will always be higher, because the number of buckets needs to be a power of 2 -> actual capacity = next_power_of_two(max_entries / bucket_size)
• max_kicks -> larger kick count could result in higher load factors, but can negatively impact insert performance at high loads -> usually set to 500, but in cases where high load is expected and some higher false positive rate could be tolerated, I would suggest setting this at a much lower value

LRU params:

• lru_enabled -> true of false
• lru_counter_bits -> I haven't added this one, but I think it would make sense (currently hardcoded at 8 bits) - it could produce more efficient memory layout if number of all bits is at a byte level (we already round it up like that anyways)

TTL params:

• ttl_enabled -> true or false
• ttl -> default TTL (this one can be inherited from memory enrichment table if we decide to implement this as an extension for memory enrichment tables)
• ttl_bits -> number of bits for ttl - allows higher accuracy and larger TTL at the cost of memory
• ttl_resolution (in seconds) -> can trade accuracy for lower memory footprint - higher values mean lower resolution

• What metrics to emit

Still not finalized, but some metrics that would be useful in measuring the
performance of the filter would be:

• cache hits
• cache misses
• entries count
• kicked items
• expired items (if TTL is used)
• memory used (this one is static though)

3. Implementation Considerations

• Is a Cuckoo filter strictly necessary? How does this compare to e.g. hash + LRU or counting Bloom filters?

While counting Bloom filter supports deletion, it would require tracking TTL separately for each item and then entries could be deleted using that data, but that defeats the purpose of the filter. Also, besides this, Cuckoo is more space efficient with larger sets and lower target false positive rate (the paper has a more detailed comparison in sections 6 and 7: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf).

Hash + LRU would achieve a much higher false positive rate - in general it should be similar to Cuckoo filter, but without the Cuckoo hashing, meaning each fingerprint can only have 1 valid bucket to be stored in, causing more collisions and failed insertions.

• How would this integrate with Vector's existing transform pipeline?

This would either be another enrichment table accessible in VRL, or an extension to the current memory enrichment table (like a different mode of operation). The actual library could be used as an alternative wherever bloom filter is used (like in tag_cardinality_limit transform), but we are interested in the implementation accessible in VRL.