apache / apache/kvrocks

Enhance the implementation of Random Sample Keys in kvrocks

Open
#2,144 10 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
C++
Stars
4.4k
Forks
658
Avg merge
1d 20h
Merged PRs (30d)
10

Description

### Search before asking

- [X] I had searched in the [issues](https://github.com/apache/kvrocks/issues) and found no similar issues.

### Motivation

Random sample keys is supported in kvrocks. When running commands like `spop`, scanning all data would be a bottleneck. Currently, the implementation is:
1. Get all sampled values
2. Random filtering K values
3. return

Unlike redis, it's complexity is always O(N), N is the element cardinal, which is extremly high. It's a bit hard to get "random" in kvrocks because we're based on rocksdb.

### Solution

There're some rules we can apply:
1. Maintaining a eq-depth histogram if random is frequently. This is the best one if random sample is frequently. However, we'll suffer from maintaining cost during write. TiKV using size based sampling to maintain the split range

So, instead, maybe we can enhance the implementation of current impl. For example:
1. Counting all "indices" of random values, and sorting them
2. Using iterator to get only these indices

The complexity is still O(N), but the performance might be enhanced.

### Are you willing to submit a PR?

- [x] I'm willing to submit a PR!

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by locating kvrocks' current random-sample implementation used by commands such as spop and measure its all-data scan behavior. Compare the proposed index-counting and iterator approach with the existing behavior and Redis expectations; done requires an agreed implementation that improves sampling performance without changing command results.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, redis
Domain
database
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.