bug: hash collision causes cache usage to be lower than expected

[KaguraMilet]

I'm trying to implement the SIEVE eviction algorithm for foyer. During the debugging process, I found that due to hash collision, even if the cache capacity is greater than or equal to the number of inserted elements, the actual number of elements maintained by the cache is lower than the number of inserted elements. I'm curious if this is expected behavior.

To reproduce this scenario:
modify fn init_cache(cache: &Cache<u64, u64>, rng: &mut StdRng) in foyer-memory/src/cache.rs test part

fn init_cache(cache: &Cache<u64, u64>, rng: &mut StdRng) {
        let mut v = (0..100).collect_vec();
        v.shuffle(rng);
        for i in v {
            let previous = cache.usage();
            cache.insert(i, i);
            assert_eq!(cache.usage(), previous + 1);
        }
}

[MrCroxx]

Hi @KaguraMilet . Thank you for reporting. Let me check.

[MrCroxx]

Hi @KaguraMilet , sorry for the late reply. I was working on the tutorial these days.

I've checked the code. It is not a bug. This is because foyer uses a sharding in-memory cache design. The capacity is divided into each shard. If a shard is already full, it will evict entries on insertions.

[KaguraMilet]

Thanks for your reply, so this is expected behavior, right?

[MrCroxx]

Thanks for your reply, so this is expected behavior, right?

Yes. It is. It will simplify the sharding design and avoid concurrent overhead.

[MrCroxx]

But still, thank you for reporting. I'm working on the design doc and that will explain it better. 🥰