The sampling is not random during evictions in fill_sample

alfa07 commented 1 year ago

The rust iterators over HashMap do not work the same as in golang. In rust iteration order is stable between calls if hashmap does not change. If it changes the iteration order is still mostly the same. That not the case for golang where iteration order is different between calls to k := range map.

https://github.com/al8n/stretto/blob/262f340411cf860d898ddd6f3147ea603db82a15/src/policy.rs#L321 https://github.com/dgraph-io/ristretto/blob/3177d9c9520c37d36b18113be01fea6393f63860/policy.go#L317

I suspect that cache performance (hit rates) suffer significantly because of this.

al8n commented 1 year ago

Good catch! Thanks. Do you have any suggestions about this? I have no idea how to make Rust's map behave like the Go's.

alfa07 commented 1 year ago

Thinking about it I see two options:

Implement custom (specialized?) hash map
Fork hashbrown and add iter_from iterator which starts from arbitrary place in the HashMap's backing array

phantomhker commented 1 year ago

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

al8n commented 1 year ago

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

phantomhker commented 1 year ago

It seems that the ring buffer is related to frequency in admit policy, why do you think it's useless?

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

al8n commented 1 year ago

It seems that the ring buffer is related to frequency in admit policy, why do you think it's useless?

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

On https://github.com/dgraph-io/ristretto/blob/main/cache.go#L229, what they do is that they only push the keyhash to the getBuf, and there is the only place the getBuf is used, so I think the ringbuffer is doing nothing in the current implementation. In admit policy, it seems that they are not using ringbuffer anymore.

phantomhker commented 1 year ago

The defaultPolicy in ristretto actually implements the ringConsumer interface, the Push() method will be called in getBuf, maybe you can see here https://github.com/dgraph-io/ristretto/blob/main/policy.go#L113. And that's why the push() method in LFUPolicy in stretto is not called, it should be called in getBuf. It seems that you're confused by the duck type in golang

It seems that the ring buffer is related to frequency in admit policy, why do you think it's useless?

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

On https://github.com/dgraph-io/ristretto/blob/main/cache.go#L229, what they do is that they only push the keyhash to the getBuf, and there is the only place the getBuf is used, so I think the ringbuffer is doing nothing in the current implementation. In admit policy, it seems that they are not using ringbuffer anymore.

al8n commented 1 year ago

The defaultPolicy in ristretto actually implements the ringConsumer interface, the Push() method will be called in getBuf, maybe you can see here https://github.com/dgraph-io/ristretto/blob/main/policy.go#L113. And that's why the push() method in LFUPolicy in stretto is not called, it should be called in getBuf.

It seems that the ring buffer is related to frequency in admit policy, why do you think it's useless?

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

On https://github.com/dgraph-io/ristretto/blob/main/cache.go#L229, what they do is that they only push the keyhash to the getBuf, and there is the only place the getBuf is used, so I think the ringbuffer is doing nothing in the current implementation. In admit policy, it seems that they are not using ringbuffer anymore.

Ah, good catch! You are right! Thanks! I will try to fix this as soon as possible. But I have to say that at least after May 1.

al8n commented 1 year ago

In conclusion, there are two bugs that need to be fixed.

[ ] The order of the iter of the map should be nonstable. Thanks for @alfa07 has been submitted a PR for hashbrown, let us see when it will we merged by the hashbrown.
[x] The ringbuffer stuff should be implemented. #39

Thanks for @alfa07 and @phantomhker report the problems!

al8n / stretto

The sampling is not random during evictions in fill_sample #37