GitHub user Tangruilin edited a comment on 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. 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. GitHub link: https://github.com/apache/kvrocks/discussions/3404#discussioncomment-17402479 ---- This is an automatically sent email for [email protected]. To unsubscribe, please send an email to: [email protected]
