KeeProMise opened a new issue, #1423: URL: https://github.com/apache/incubator-kvrocks/issues/1423
### Search before asking - [X] I had searched in the [issues](https://github.com/apache/incubator-kvrocks/issues) and found no similar issues. ### Motivation “We break the bitmap values into fragments(1KiB, 8192 bits/fragment), and subkey is the index of the fragment. For example, when the request to set the bit of 1024 would locate in the first fragment with index 0, to set a bit of 80970 would locate in 10th fragment with index 9.” ### Solution If we modify a bit in a certain fragment, we still need 1kb of space, can we directly save the value of the position that needs to be modified when the amount of data is small? Assuming that we block by 1kb, the range of the position to be modified is 1~2^10-1. For a certain position x, we only need to save 10 bits, and we can go to the whole, that is, use a position data 2b (16 bits). So 1kb, we can store up to 512 location data. So when the modified bit position in a fragment is less than 512, we can directly save its position value. Assuming that only a small number of positions in the fragment are modified at this time (for example, two positions are changed from 0 to 1), then only 4b space is needed , without taking up the full 1kb. When a storage engine with an LSM mechanism such as rocksdb is used at the bottom layer, reducing space usage can also reduce read and write amplification. ### Are you willing to submit a PR? - [X] I'm willing to submit a PR! -- 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]
