Proposal: Kvrocks Count-Min Sketch

[Tangruilin]

Proposal: Kvrocks Count-Min Sketch

Background

Redis Stack Compatibility

Redis Stack has implemented the Count-Min Sketch probabilistic data structure, providing commands such as CMS.INITBYPROB, CMS.INCRBY, and CMS.QUERY. To maintain compatibility with the Redis ecosystem, Kvrocks needs to implement these features.

Related Issue:

• Support count-min sketch data structure and commands #2425

---

Kvrocks Storage Architecture

Column Family Design

Kvrocks uses a single RocksDB instance, dividing data by access pattern through Column Family (CF):

• Metadata CF: Stores metadata for all types
• PrimarySubkey CF: Stores primary sub-key data for all types

---

Count-Min Sketch

Introduction

Count-Min Sketch (CMS) is a probabilistic data structure for estimating element frequencies in a data stream. It uses fixed memory with O(1) time complexity for insertion and query, and only overestimates (never underestimates). Commonly used for hot content tracking, traffic monitoring, recommendation systems, etc.

Algorithm diagram:

CMS Structure: depth × width count matrix

Layer 0: [c0, c1, c2, ..., c(width-1)]
Layer 1: [c0, c1, c2, ..., c(width-1)]
...
Layer depth-1: [c0, c1, c2, ..., c(width-1)]

INCRBY item increment:
  for each layer i:
    pos = hash_i(item) % width
    counters[i][pos] += increment

QUERY item:
  return min(counters[i][hash_i(item) % width] for i in 0..depth-1)

For detailed algorithm explanation, see: https://redis.io/docs/latest/develop/data-types/probabilistic/count-min-sketch/

The core challenge is to design a storage format that balances disk read/write performance

Command List

Command	Description
CMS.INITBYPROB key error_rate probability	Initialize with error rate and probability
CMS.INITBYDIM key width depth	Initialize with dimensions
CMS.INCRBY key item increment [...]	Increment count
CMS.QUERY key item [item...]	Query frequency estimate
CMS.MERGE destkey numkeys srckey...	Merge multiple CMS
CMS.INFO key	Get information

CMS Metadata Design

Storage Format:
CMS metadata contains base metadata and CMS's metadata for count, such as width, depth, total_count, etc.

         +----------+------------+-----------+-----------+-----------+-----------+-----------------------+--------------+
key =>   |  flags   |  expire    |  version |  size     |  width    |  depth    |  total_count          | storage_mode |
         | (1byte)  | (Ebyte)    | (8byte)  | (Sbyte)   | (4byte)   | (4byte)   | (8byte)               | (1byte)      |
         +----------+------------+-----------+-----------+-----------+-----------+-----------------------+--------------+

Field Description:

Field	Size	Description
flags	1 byte	Type identifier + encoding version
expire	1 bytes	Expiration time
version	8 bytes	Version number (MVCC)
size	S bytes	Set to 0
width	4 bytes	Buckets per layer
depth	4 bytes	Number of layers
total_count	8 bytes	INCRBY accumulated value
storage_mode	1 byte	Storage mode (reserved)

---

Count Matrix Storage Design

Count Matrix is a 2D count matrix stored in PrimarySubkey CF. Considering the balance of read, write, and space amplification, we have several storage options:

1. Single Key Storage:

┌──────────────────────────────────────────────────────────────────┐
| InternalKey(ns_key, sub_key="", version) | Count Matrix(encode)  |
└──────────────────────────────────────────────────────────────────┘

This approach stores the entire CM as a Value. The disadvantage is high write amplification for each write. The advantage is higher iterator and read efficiency.

2. Per-Bucket Storage:

┌─────────────────────────────────────────────────────────────────────────┐
| InternalKey(ns_key, sub_key=bucket_id, version) |        count          |
└─────────────────────────────────────────────────────────────────────────┘

bucket_id = layer × width + col

This approach stores each element in CMS separately. The advantage is low write amplification — each key is written independently. The disadvantage is relatively lower read and iterator
efficiency, as well as higher space amplification.

Here, a bucket means one counter in the CMS matrix. A single-item INCRBY touches one bucket in each layer, so it updates depth buckets in total.

Scheme Comparison:

Assuming parameters: width = 2000, depth = 9, total matrix size width × depth × 4 = 72 KB.

InternalKey overhead estimate (excluding namespace): 1 (ns_len) + 2 (slot_id) + 4 (key_len) + 20 (key) + 8 (version) + sub_key_size ≈ 35 + sub_key_size bytes.

Scheme	Key Count	Single Key Structure	INCRBY Write	QUERY Read	Logical Counter-Value Write Amplification	Analysis
Single Key	1	Key + entire matrix	72 KB (1 Key + 72KB Value)	72 KB (read all)	width = 2000	Updates 9 counters but rewrites entire matrix
Per-Layer	depth = 9	Key + one layer	72 KB (9 Key + 9×8KB Value)	72 KB (read 9 layers)	width = 2000	❌ Same write amplification as Single Key, no advantage
Per-Column	width = 2000	Key + one column	675 B (9 Key + 9×36B Value)	324 B (read 9 columns)	depth = 9	Updates 1 counter in a column but rewrites entire column
Per-Bucket	width×depth = 18K	Key + single count	387 B (9 Key + 9×4B Value)	36 B (read 9 buckets)	1	Only updates actually modified counters

Logical Counter-Value Write Amplification Calculation:

Logical counter-value write amplification = Counter value bytes written / Theoretical required counter update

Theoretical update: depth × 4 = 36 bytes (INCRBY updates depth counters)

Single Key: 72 KB / 36 B = 2000x (width)
Per-Layer: 72 KB / 36 B = 2000x (width) ← Same as Single Key!
Per-Column: 324 B / 36 B = 9x (depth)
Per-Bucket: 36 B / 36 B = 1x

The calculation above only counts counter value bytes. At the RocksDB key-value payload level, per-bucket storage writes multiple small records for one item update. With depth = 9, the estimated lower-bound payload is about 9 × (InternalKey + 4B value), which is larger than 36 B and does not include WAL, memtable, SST index/filter, or compaction overhead.

Conclusion:

Scenario	Recommended Scheme	Reason
Large matrix with high-frequency writes	Per-Bucket	Low write amplification, suitable for high-frequency INCRBY
Small matrix (width×depth < 1K)	Single Key	Few keys, simple structure, one I/O
Memory-sensitive	Single Key	Only 1 Key, minimal RocksDB index overhead

For write-intensive scenarios, the per-bucket storage model offers lower logical counter-value write amplification and higher concurrency; for read-intensive scenarios, the single key approach provides lower read amplification, and since single key requires fewer Internal Keys, it also has lower space amplification.

However, considering that the primary use case for CMS is counting—a write-intensive workload—and that modern storage is abundant, a certain degree of space amplification is acceptable.

Therefore, the per-bucket approach is selected for the initial implementation because it minimizes logical counter rewrites and keeps the implementation straightforward. Its RocksDB-level small-key overhead should be evaluated with benchmarks and may be optimized in a later iteration.

---

I/O Operations Analysis

Assuming parameters: width = 2000, depth = 9, k = 100

CMS Command I/O Operations

Command	Read I/O	Write I/O	Description
CMS.INITBYPROB	1 (check key existence)	1	Write Metadata; buckets are lazily initialized
CMS.INITBYDIM	1	1	Same as above
CMS.INCRBY item [item...]	1 + depth×N	depth×N(per bucket), 1(single key)	Read Metadata + read/write depth buckets per item
CMS.QUERY item [item...]	1 + depth×N(per bucket), 2(single key)	0	Read Metadata + read depth buckets per item
CMS.MERGE dest N src...	1 + N + N×width×depth	1 + width×depth	Read dest Metadata + N src Metadata + all buckets
CMS.INFO	1	0	Only read Metadata

Example Calculation (width=2000, depth=9, single INCRBY):

Storage Mode	Read I/O	Write I/O	Total I/O
Per-bucket	1 + 9 = 10	9	19
Single Key	1 + 1 = 2	1	3

Per-bucket has more I/O operations but lower logical counter-value write amplification; Single Key has fewer I/O operations but higher logical counter-value write amplification.

---

References

• Redis Count-Min Sketch
• HeavyKeeper Paper - Gong et al., USENIX ATC 2018
• Discussion #2449

[Tangruilin]

Apologies for submitting such a long proposal all at once — I was too eager and made it difficult to review. I've split out CMS into its own proposal. For Top-K, I'll work on a separate design after CMS is completed.

Additionally, regarding the suggestion about the per-key approach, I have a few points I'd like to discuss:

1. Between the options compared above, which do you think is better — Single Key or Per-Column? Personally, I'm leaning toward Single Key. It's simpler to implement, and we can later use MergeOperator to optimize write amplification.
2. I'm not entirely sure I understand how reducing page size helps here. With a single key approach, smaller page sizes don't really improve read performance, since Get() always reads the entire value anyway. Could you elaborate on this?"

[jihuayu]

I'm sorry, I read it too quickly this morning and got it wrong.
I'm not sure where my AI tool went. Please ignore my question, I will look at it again later.

[jihuayu]

Hi @Tangruilin

I think the current Per-Bucket performance conclusion is not accurate enough for RocksDB.

The comparison uses depth * 4 = 36B as the theoretical update size, and then concludes that Per-Bucket has 1x write amplification. But in RocksDB we do not write only the 4-byte counters. Each updated bucket is a separate RocksDB record, so the actual write includes the InternalKey, value, WriteBatch/WAL record, memtable entry, SST block/index/filter overhead, and later compaction cost.

Even in the proposal's own estimate, Per-Bucket writes are 9 keys + 9 * 4B value = 387B, so the lower bound is already 387 / 36 ~= 10.75x, not 1x. If total_count is stored in CMS metadata and updated on every CMS.INCRBY, then every increment also needs a metadata write, making the actual write amplification higher.

CMS.INITBYDIM / CMS.INITBYPROB also cannot have 0 write I/O. Lazy bucket initialization is fine, but metadata must still be written.

So I don't think Per-Bucket should be chosen only because it appears to have the lowest write amplification. It reduces value rewrite size, but it creates width * depth tiny keys, which can be expensive for RocksDB due to index/filter/memtable/WAL/compaction overhead.

Given that CMS is mostly write-heavy and read performance is less important, I think a better direction is:

1. Phase 1: implement correctness with page-based counter storage, without MergeOperator.
   • Store counters in fixed-size pages under PrimarySubkey CF.
   • Missing page means all-zero counters.
   • CMS.INCRBY reads and writes only the dirty pages.
   • This avoids rewriting the entire matrix and also avoids creating one RocksDB key per counter.

PS: Here "page-based" means splitting the CMS counter matrix into fixed-size physical pages instead of storing one key per counter or one key for the whole matrix. Each page contains multiple adjacent counters and is stored as one RocksDB subkey. This is a middle ground between Single Key and Per-Bucket: it avoids rewriting the entire matrix on each update, while also avoiding width * depth tiny RocksDB keys.

2. Phase 2: add RocksDB MergeOperator for the same page format.
   • CMS.INCRBY can write sparse counter deltas with Merge() instead of doing read-modify-write.
   • PartialMerge can combine multiple sparse deltas.
   • FullMerge materializes the page when needed during read or compaction.

This keeps the first implementation reviewable and correct, while leaving a clean path to optimize the write-heavy workload later. It also avoids locking us into a Per-Bucket layout that may look efficient at the counter level but is likely expensive at the RocksDB record level.

[Tangruilin]

I need to take care of some onboarding tasks this week and get familiar with the new company. I’ll review your feedback as soon as possible and update the proposal accordingly.

[Tangruilin]

Sorry for the delayed response. I didn’t have Wi-Fi in my room over the past couple of days, so I’m only able to reply now.

[jihuayu]

Oh, don’t worry about it. You don’t need to reply to me right away. This isn’t a job. Just have fun with it.

[Tangruilin]

Hi @Tangruilin

I think the current Per-Bucket performance conclusion is not accurate enough for RocksDB.

The comparison uses depth * 4 = 36B as the theoretical update size, and then concludes that Per-Bucket has 1x write amplification. But in RocksDB we do not write only the 4-byte counters. Each updated bucket is a separate RocksDB record, so the actual write includes the InternalKey, value, WriteBatch/WAL record, memtable entry, SST block/index/filter overhead, and later compaction cost.

Even in the proposal's own estimate, Per-Bucket writes are 9 keys + 9 * 4B value = 387B, so the lower bound is already 387 / 36 ~= 10.75x, not 1x. If total_count is stored in CMS metadata and updated on every CMS.INCRBY, then every increment also needs a metadata write, making the actual write amplification higher.

CMS.INITBYDIM / CMS.INITBYPROB also cannot have 0 write I/O. Lazy bucket initialization is fine, but metadata must still be written.

So I don't think Per-Bucket should be chosen only because it appears to have the lowest write amplification. It reduces value rewrite size, but it creates width * depth tiny keys, which can be expensive for RocksDB due to index/filter/memtable/WAL/compaction overhead.

Given that CMS is mostly write-heavy and read performance is less important, I think a better direction is:

1. Phase 1: implement correctness with page-based counter storage, without MergeOperator.

   • Store counters in fixed-size pages under PrimarySubkey CF.
   • Missing page means all-zero counters.
   • CMS.INCRBY reads and writes only the dirty pages.
   • This avoids rewriting the entire matrix and also avoids creating one RocksDB key per counter.

PS: Here "page-based" means splitting the CMS counter matrix into fixed-size physical pages instead of storing one key per counter or one key for the whole matrix. Each page contains multiple adjacent counters and is stored as one RocksDB subkey. This is a middle ground between Single Key and Per-Bucket: it avoids rewriting the entire matrix on each update, while also avoiding width * depth tiny RocksDB keys.

2. Phase 2: add RocksDB MergeOperator for the same page format.

   • CMS.INCRBY can write sparse counter deltas with Merge() instead of doing read-modify-write.
   • PartialMerge can combine multiple sparse deltas.
   • FullMerge materializes the page when needed during read or compaction.

This keeps the first implementation reviewable and correct, while leaving a clean path to optimize the write-heavy workload later. It also avoids locking us into a Per-Bucket layout that may look efficient at the counter level but is likely expensive at the RocksDB record level.

Hi @jihuayu, thanks a lot for the review.

I understand that the approach you suggested is a page-based layout that balances the number of RocksDB keys with the amount of data rewritten per update. This is a good point.

Based on the CMS access pattern, each single-item update touches one counter in each layer, so it updates depth counters in total. Instead of storing one key per counter, I think we can define the page layout using columns as the grouping unit: one column contains depth counters, and one physical page contains multiple adjacent columns.

In other words, this would be a column-group page layout rather than a pure per-column layout. It can reduce the key count from width * depth to roughly ceil(width / columns_per_page), while still avoiding rewriting the whole matrix on each update. CMS.INCRBY would only read and write the dirty pages, and missing pages can still represent all-zero counters.

Does this direction sound reasonable to you? If so, I will revise the discussion based on this page-based layout and also refer to the TDIGEST discussion/issue when updating the design.

[jihuayu]

@Tangruilin I think that sounds good. You can work out the metadata layout in more detail, including how it will be stored as well as the read/write flow.

After that, let’s split the implementation into a series of small PRs. Ideally, each PR should stay under about 400 lines of changes to keep it easier to review.

[jihuayu]

Hi @apache/kvrocks-committers. We have a proposal here for the new data structure, and I’d like to get everyone’s feedback.