GitHub user Tangruilin edited a discussion: support CMS and Top-k for kvrocks
# 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:
- #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 d: [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)
```
For detailed algorithm explanation, see:
[https://redis.io/docs/latest/develop/data-types/probabilistic/count-min-sketch/](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 | E 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.
**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 | 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 |
**Write Amplification Calculation:**
```
Write amplification = Actual written data / Theoretical required 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
```
**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 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, i think the per-bucket approach is superior.
---
## 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) | 0 | Write Metadata + initialize
all buckets, lazy write |
| `CMS.INITBYDIM` | 1 | 0 | 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 write amplification; Single Key
has fewer I/O operations but higher write amplification.
---
## References
- [Redis Count-Min
Sketch](https://redis.io/docs/latest/develop/data-types/probabilistic/count-min-sketch/)
- [HeavyKeeper
Paper](https://www.usenix.org/conference/atc18/presentation/gong) - Gong et
al., USENIX ATC 2018
- [Discussion #2449](https://github.com/apache/kvrocks/discussions/2449)
GitHub link: https://github.com/apache/kvrocks/discussions/3404
----
This is an automatically sent email for [email protected].
To unsubscribe, please send an email to: [email protected]
