Crate feldera_buffer_cache 

Sharded, weighted in-memory cache with a SIEVE-inspired eviction scan.

This crate adapts the NSDI’24 SIEVE design to Feldera’s storage cache needs: weighted capacity accounting, per-shard locking, and Arc-shared values. The core idea from the paper is preserved: read path only needs to set one visited bit, and a moving hand evicts the first entry that remains unvisited after a scan. This makes things scale nicely because the bit is per-entry and reads have little contention on cache-lines as we don’t manage the queues on the read path.

Overview

• Keys are assigned to shards by hash(key) & (num_shards - 1).
• Each shard stores:
  • HashMap<K, usize> mapping keys to dense indices in nodes.
  • Vec<Node<K, V>> holding keys, Arc<V> values, charges, and visited bits.
  • A hand index for eviction scans over the dense vector.
  • Weighted occupancy (used_charge) and a per-shard capacity budget.
• get() still takes a shard read lock, then sets the visited bit. This is cheaper than LRU-style list mutation, but it is not the paper’s no-lock hit path.
• Removals use swap_remove, so the internal scan order is compact and index-based instead of the paper’s stable linked FIFO queue.

Attribution

Some inspiration and tests were adapted from https://docs.rs/crate/sieve-cache/latest, which is MIT licensed.

Structs

SieveCache

A sharded, weighted, thread-safe SIEVE cache.