Enhance the implementation of Random Sample Keys in kvrocks about kvrocks HOT 9 OPEN

I'm trying to implement this. During my impl, I found a problem that:

1. Get random set size
2. Get all indices, counting the random fetching indices
3. Traverse the set

The command 1-3 should be done in one snapshot, otherwise, the case might be:

• Get all indices, size == 10
• Random need to access 10th member
• User delete an element
• 10th cannot be fetched

So, GetMetadata and traversing the set should be done in one rocksdb snapshot. Would you think this is safe and ok? @git-hulk @PragmaTwice

from kvrocks.

I'm wondering if it'd be better to sacrifice the scope of the candidate set to simplify the implementation like below:

1. if size <= N(e.g. 128/256), then iterate all members and randomly pick one of them.
2. if size > N, random among the first N elements if the cached random point is empty. Otherwise, seek from the cached random point and then random among the next N elements, then cache the random point again or remove the cache random point if it reaches the end.

from kvrocks.

if size > N, random among the first N elements if the cached random point is empty. Otherwise, seek from the cached random point and then random among the next N elements, then cache the random point again or remove the cache random point if it reaches the end.

I thought of using this previously, and this is named "statistics" in this issue. but where should we storing this and how do updating this?

from kvrocks.

but where should we storing this and how do updating this?

We're now using a LRU to cache the iterator key while scanning the DB/hash/set, maybe we can do this in the same way.

from kvrocks.

That's a bit complex 🤔, in my current impl I may just need to iter the set with one snapshot...

from kvrocks.

That's a bit complex 🤔, in my current impl I may just need to iter the set with one snapshot...

Yes, it should be more complex than the current implementation. Then I think the implementation with the same snapshot is good.

from kvrocks.

Yeah, another point is that support get meta by snapshot can enhance our isolation. It might slightly affect LSM-Tree Garbage collection, but I think it's ok

from kvrocks.