GitHub user Tangruilin edited a discussion: support CMS and Top-k for kvrocks
# Kvrocks Count-Min Sketch & Top-K Design Proposal ## 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 - Support count-min sketch data structure and commands](https://github.com/apache/kvrocks/issues/2425) Related Issue: [#3176 - Add TopK Probabilistic Data Structure](https://github.com/apache/kvrocks/issues/3176) ### 3. Incremental Implementation Strategy --- ## 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 --- ## Phase 1: 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. --- ## Phase 3: HeavyKeeper Evolution ### HeavyKeeper Core Changes HeavyKeeper's storage format is basically the same as CMS/Top-K, **the only change is adding fingerprint field to Value**. **Changes:** | Storage Location | CMS/Top-K | HeavyKeeper | Change | |-----------------|-----------|-------------|--------| | Count Matrix Value | `[count:4B]` | `[fingerprint:2B][count:4B]` | +2 bytes fingerprint | | HeapBucket node | `[itemIdx:4B][count:4B]` | `[fingerprint:2B][itemIdx:4B][count:4B]` | +2 bytes fingerprint | | ValueSlots / SlotBitmap | No change | No change | No change | | Metadata | No change | No change | No change | **Essence: Only need to add `fingerprint:2B` before Value, everything else reuses existing design.** --- ### Count Matrix Storage Format ``` ┌──────────────────────────────────────────────────────────────────────────────────────────────┐ │ InternalKey(ns_key, sub_key=bucket_id, version) | [fingerprint:2B | count:4B] │ └──────────────────────────────────────────────────────────────────────────────────────────────┘ ``` **Field Description:** | Field | Size | Description | |-------|------|-------------| | fingerprint | 2 bytes | Element's hash fingerprint for collision detection | | count | 4 bytes | Count value (may be decayed) | ### I/O Operations Comparison Summary | Data Structure | Init I/O | Single Operation I/O | Query I/O | Description | |----------------|----------|---------------------|-----------|-------------| | CMS (per-bucket) | ~18K | ~19 | ~10 | More I/O but lower write amplification | | CMS (single key) | ~2 | ~3 | ~2 | Less I/O but higher write amplification | | Top-K | ~18K | ~21 ~ 30 | ~10 | More than CMS due to heap/ValueSlots I/O | **Optimization Suggestions:** - High-frequency write scenarios → Per-bucket storage (more I/O but lower write amplification) - Low-frequency/query scenarios → Single Key storage (less I/O) - Top-K can consider caching HeapBucket in memory to reduce repeated reads ## References - [Redis Count-Min Sketch](https://redis.io/docs/latest/develop/data-types/probabilistic/count-min-sketch/) - [Redis Top-K](https://redis.io/docs/latest/develop/data-types/probabilistic/top-k/) - [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]
