GitHub user Tangruilin edited a discussion: Proposal: Kvrocks Count-Min Sketch
# 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 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/](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](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]
