[GitHub] [incubator-kvrocks] KeeProMise opened a new issue, #1423: For bitmap, there are some suggestions

["KeeProMise (via GitHub)" <gi...@apache.org>]

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: issues-unsubscribe@kvrocks.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [incubator-kvrocks] KeeProMise closed issue #1423: For bitmap, there are some suggestions

["KeeProMise (via GitHub)" <gi...@apache.org>]

KeeProMise closed issue #1423: For bitmap, there are some suggestions
URL: https://github.com/apache/incubator-kvrocks/issues/1423


-- 
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: issues-unsubscribe@kvrocks.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [incubator-kvrocks] git-hulk commented on issue #1423: For bitmap, there are some suggestions

["git-hulk (via GitHub)" <gi...@apache.org>]

git-hulk commented on issue #1423:
URL: https://github.com/apache/incubator-kvrocks/issues/1423#issuecomment-1536227392

   Hi, @KeeProMise Thanks for your proposal.
   
   For the current implementation, the bitmap's fragment won't always take 1KiB, it determines by the max bit position in this fragment. That's to say, if the max set position is 3, the fragment size should be 1 byte, and it will be 1KiB if the max set position is 8000.
   
   Another question is how the new data fragment is compatible with the previous one. My sentiment is negative unless we have enough users complain about this.  


-- 
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: issues-unsubscribe@kvrocks.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [incubator-kvrocks] mapleFU commented on issue #1423: For bitmap, there are some suggestions

["mapleFU (via GitHub)" <gi...@apache.org>]

mapleFU commented on issue #1423:
URL: https://github.com/apache/incubator-kvrocks/issues/1423#issuecomment-1536226013

   For bitmap compression, there are multiple possible ways. And please notice that, for a "dense" bitmap, compression might be useless.
   
   There are some mature bitmap compression methods, like Roaring Bitmap or Oracle BCC.
   
   By the way, introducing an format change should be heavy, because we need to detect which underlying data is used and considering the backward capability.


-- 
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: issues-unsubscribe@kvrocks.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org