jihuayu commented on PR #3481: URL: https://github.com/apache/kvrocks/pull/3481#issuecomment-4395729667
Hi @nagisa-kunhah. Regarding the current proposal, I have the following suggestions: ### Paging the Buckets I believe that assigning one key per bucket will lead to a massive number of small keys, which is fatal to the system's performance. The overhead of RocksDB internal keys, memtables, index/filters, and compaction will be significantly greater than one or a few bytes. I suggest we introduce a **Page** abstraction for buckets, where one page contains multiple buckets. For example, a 1KB page could contain 256 buckets. I have performed a rough estimation as follows: #### Full Page Utilization | Page Size | Buckets/Page | Actual Page Size | Full Page Utilization | Worst-case Amplification (1 Bucket) | Worst-case Amplification vs. Bucket-per-Key | Buckets Needed to Break Even | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 1KB | 256 | 1101B | 93.01% | 275x | 13.6x | 14 | | 2KB | 512 | 2125B | 96.38% | 531x | 26.2x | 27 | | 4KB | 1024 | 4173B | 98.15% | 1043x | 51.5x | 52 | | 8KB | 2048 | 8269B | 99.07% | 2067x | 102.1x | 103 | **Note on "Buckets Needed to Break Even":** This represents the minimum number of buckets that must be used within a page for the "paged" approach to become more space-efficient than the "bucket-per-key" approach. This occurs at approximately 5% occupancy. #### Scenario for Default Capacity = 1024 | Page Size | Buckets/Page | Pages before 1st Expansion | New Sub-filter Pages before 2nd Expansion | Total Pages before 2nd Expansion | | :--- | :--- | :--- | :--- | :--- | | 1KB | 256 | 2 | 4 | 6 | | 2KB | 512 | 1 | 2 | 3 | | 4KB | 1024 | 1 | 1 | 2 | | 8KB | 2048 | 1 | 1 | 2 | Based on these findings, I recommend a default page size of **2KB** or **4KB**. ### Using MultiGet / Batch Read for Candidate Buckets/Pages Operations like `CF.EXISTS`, `MEXISTS`, and `ADD` typically access two candidate buckets in each sub-filter. If we use bucket-level keys, this results in many random reads. Even with page-level keys, we should aggregate requests and use `MultiGet` to reduce the number of round-trips to RocksDB. ### Insertion Order: Prioritize Latest -> Old RedisBloom queries from the newest sub-filter to the oldest. In Kvrocks, if we proceed from old to new, every write operation will first hit the older, fuller filters. This is likely to increase read amplification and the probability of "kick-outs." I suggest maintaining consistency with RedisBloom's "latest -> old" approach. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
