[incubator-kvrocks-website] branch main updated: cleanups in bitmap blog article (#70)

[hu...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

hulk pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/incubator-kvrocks-website.git


The following commit(s) were added to refs/heads/main by this push:
     new 1db142b  cleanups in bitmap blog article (#70)
1db142b is described below

commit 1db142ba209067c2b4a9f19bd8afa2de9407c936
Author: Binbin <bi...@qq.com>
AuthorDate: Wed Mar 22 10:40:24 2023 +0800

    cleanups in bitmap blog article (#70)
    
    Summary of Changes:
    1. remove `ZWSP` from `WiscKey: Separating Keys from Values in SSD-conscious Storage`
    2. add a space between to128, change `to128` to `to 128`
    3. remove an extra space
    4. add a period, consistent with the above
    5. fix dead `redis_bitmap.cc` GitHub link
---
 blog/2021-11-07-how-to-implement-bitmap-on-rocksdb/index.md | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/blog/2021-11-07-how-to-implement-bitmap-on-rocksdb/index.md b/blog/2021-11-07-how-to-implement-bitmap-on-rocksdb/index.md
index 74a0aed..52757a8 100644
--- a/blog/2021-11-07-how-to-implement-bitmap-on-rocksdb/index.md
+++ b/blog/2021-11-07-how-to-implement-bitmap-on-rocksdb/index.md
@@ -33,15 +33,15 @@ amplification ratio = (1 + 10 + 100 +1000 + 10000 + 100000 + 1000000) * M / (100
 
 However, the magnification space rate is much larger than this theoretical value since the last layer generally cannot reach the maximum value. It is also mentioned in the RocksDB documentation. For details see also RockDB's blog ["Dynamic Level Size for Level-Based Compaction"](https://rocksdb.org/blog/2015/07/23/dynamic-level.html).
 
-In addition, since RocksDB reads and writes are all based on key-value, the larger the value, the greater the read-write amplification may be. For example, suppose there is a JSON with a Value of 10 MiB. If you want to modify a field in this key, you need to read the entire JSON, modify and write it back again, which will cause huge read-write amplification. The paper ["WiscKey: Separating Keys from Values ​​in SSD-conscious Storage"](https://www.usenix.org/system/files/conference/fast16 [...]
+In addition, since RocksDB reads and writes are all based on key-value, the larger the value, the greater the read-write amplification may be. For example, suppose there is a JSON with a Value of 10 MiB. If you want to modify a field in this key, you need to read the entire JSON, modify and write it back again, which will cause huge read-write amplification. The paper ["WiscKey: Separating Keys from Values in SSD-conscious Storage"](https://www.usenix.org/system/files/conference/fast16/f [...]
 
 ## Implement bitmap on RocksDB
 
 Kvrocks is disk storage compatible with the Redis protocol implemented on RocksDB. It needs to support the bitmap data structure, so needs to implement the bitmap on RocksDB. In most scenes, the bitmap is used as sparse arrays, which means the offset written should be random, for the first time maybe 1, and the next offset maybe 1000000000 or more. Therefore, the implementation will face the above-mentioned amplification issue.
 
-A simple way is to regard the entire bitmap as a value, and read the value into the memory and then write it back when writing. Although this implementation is very simple, it would cause seriously amplification when the value was huge. In addition to the problem of effective space utilization, it may directly cause the entire service to be unavailable since we need to read and write back the entire value. Bitmap in Pika is such an implementation, but the maximum value is limit to128 KiB [...]
+A simple way is to regard the entire bitmap as a value, and read the value into the memory and then write it back when writing. Although this implementation is very simple, it would cause seriously amplification when the value was huge. In addition to the problem of effective space utilization, it may directly cause the entire service to be unavailable since we need to read and write back the entire value. Bitmap in Pika is such an implementation, but the maximum value is limit to 128 Ki [...]
 
-Since we know that the core problem is caused by a single key-value that is too large, the most direct way is to split the bitmap into multiple key-values, and control the single key-value size within a reasonable range, so the amplification is relatively under control. In the current implementation of Kvrocks, each key-value is divided into 1 KiB(8192 bits) . The algorithm diagram is as follows:
+Since we know that the core problem is caused by a single key-value that is too large, the most direct way is to split the bitmap into multiple key-values, and control the single key-value size within a reasonable range, so the amplification is relatively under control. In the current implementation of Kvrocks, each key-value is divided into 1 KiB(8192 bits). The algorithm diagram is as follows:
 
 ![bitmap-of-kvrocks](bitmap-of-kvrocks.jpeg)
 
@@ -49,7 +49,7 @@ Take `setbit foo 8192002 1` as an example, the implementation steps are:
 
 * Calculate the key corresponding to the offset of `8192002`, because Kvrocks uses a value of 1 KiB, so the number of the key is `8192002/(1024*8)=1000`, so you can know the bit should be stored in the sub key `foo1000`.
 * Then get the value corresponding to this key from RocksDB and calculate the offset in the segment, `8192002%8192` is equal to `2`, and then set the bit with the offset of 2 to 1.
-* Finally, write the entire value back to RocksDB
+* Finally, write the entire value back to RocksDB.
 
 A key point of this implementation is only read-write the limit part of the bitmap we need. Assuming that we have only executed `setbit` twice, `setbit foo 1 1` and `setbit foo 8192002 1`, then there will only read and write two keys `foo:0` and `foo:1000` in RocksDB, and the actual read-value size is only 2 KiB in total. It can be perfectly adapted to the sparse array scene like the bitmap, and will also not cause the problem of space enlargement due to sparse writing.
 
@@ -60,7 +60,7 @@ GetBit is similar. It first calculates the key where the offset is located, and
 * If not exist, means that segment has not been written, returns 0 directly.
 * If exists, read the Value and return the value of the corresponding bit.
 
-In addition, the actual key-value size is also determined by the largest offset currently written. It would NOT always create a 1024 KiB key-value when there is a write. This can also help to optimize the read-write amplification problem within a single key-value in some degree. You can read [the source code of bitmap](https://github.com/KvrocksLabs/kvrocks/blob/unstable/src/redis_bitmap.cc) for more details.
+In addition, the actual key-value size is also determined by the largest offset currently written. It would NOT always create a 1024 KiB key-value when there is a write. This can also help to optimize the read-write amplification problem within a single key-value in some degree. You can read [the source code of bitmap](https://github.com/apache/incubator-kvrocks/blob/unstable/src/types/redis_bitmap.cc) for more details.
 
 ## Summary