GitHub user jihuayu added a comment to the discussion: Proposal: Kvrocks Count-Min Sketch
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. GitHub link: https://github.com/apache/kvrocks/discussions/3404#discussioncomment-17348942 ---- This is an automatically sent email for [email protected]. To unsubscribe, please send an email to: [email protected]
