You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@kvrocks.apache.org by "enjoy-binbin (via GitHub)" <gi...@apache.org> on 2023/03/22 02:33:22 UTC
[GitHub] [incubator-kvrocks-website] enjoy-binbin opened a new pull request, #70: cleanups in bitmap blog article
enjoy-binbin opened a new pull request, #70:
URL: https://github.com/apache/incubator-kvrocks-website/pull/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 a extra space
4. add a period, consistent with the above
5. fix dead `redis_bitmap.cc` github link
--
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-website] git-hulk commented on a diff in pull request #70: cleanups in bitmap blog article
Posted by "git-hulk (via GitHub)" <gi...@apache.org>.
git-hulk commented on code in PR #70:
URL: https://github.com/apache/incubator-kvrocks-website/pull/70#discussion_r1144171159
##########
blog/2021-11-07-how-to-implement-bitmap-on-rocksdb/index.md:
##########
@@ -33,23 +33,23 @@ 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/fast16-papers-lu.pdf) that optimizes the large Key-Value of LSM-Tree by separating key-value to reduce the write amplification problem caused by Compaction. The [titan](https://github.com/tikv/titan) project of TiKV is based on WiscKey paper to optimize RocksDB's write amplification in large key-value scenarios. RocksDB also implements this function in the community version, but it is still in an experimental stage.
+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/fast16-papers-lu.pdf) that optimizes the large Key-Value of LSM-Tree by separating key-value to reduce the write amplification problem caused by Compaction. The [titan](https://github.com/tikv/titan) project of TiKV is based on WiscKey paper to optimize RocksDB's write amplification in large key-value scenarios. RocksDB also implements this function in the community version, but it is still in an experimental stage.
Review Comment:
Good catch.
--
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-website] enjoy-binbin commented on a diff in pull request #70: cleanups in bitmap blog article
Posted by "enjoy-binbin (via GitHub)" <gi...@apache.org>.
enjoy-binbin commented on code in PR #70:
URL: https://github.com/apache/incubator-kvrocks-website/pull/70#discussion_r1144169824
##########
blog/2021-11-07-how-to-implement-bitmap-on-rocksdb/index.md:
##########
@@ -33,23 +33,23 @@ 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/fast16-papers-lu.pdf) that optimizes the large Key-Value of LSM-Tree by separating key-value to reduce the write amplification problem caused by Compaction. The [titan](https://github.com/tikv/titan) project of TiKV is based on WiscKey paper to optimize RocksDB's write amplification in large key-value scenarios. RocksDB also implements this function in the community version, but it is still in an experimental stage.
+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/fast16-papers-lu.pdf) that optimizes the large Key-Value of LSM-Tree by separating key-value to reduce the write amplification problem caused by Compaction. The [titan](https://github.com/tikv/titan) project of TiKV is based on WiscKey paper to optimize RocksDB's write amplification in large key-value scenarios. RocksDB also implements this function in the community version, but it is still in an experimental stage.
Review Comment:
GH did not show it, here is a pic from CLion
--
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-website] git-hulk merged pull request #70: cleanups in bitmap blog article
Posted by "git-hulk (via GitHub)" <gi...@apache.org>.
git-hulk merged PR #70:
URL: https://github.com/apache/incubator-kvrocks-website/pull/70
--
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-website] enjoy-binbin commented on a diff in pull request #70: cleanups in bitmap blog article
Posted by "enjoy-binbin (via GitHub)" <gi...@apache.org>.
enjoy-binbin commented on code in PR #70:
URL: https://github.com/apache/incubator-kvrocks-website/pull/70#discussion_r1144170262
##########
blog/2021-11-07-how-to-implement-bitmap-on-rocksdb/index.md:
##########
@@ -33,23 +33,23 @@ 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/fast16-papers-lu.pdf) that optimizes the large Key-Value of LSM-Tree by separating key-value to reduce the write amplification problem caused by Compaction. The [titan](https://github.com/tikv/titan) project of TiKV is based on WiscKey paper to optimize RocksDB's write amplification in large key-value scenarios. RocksDB also implements this function in the community version, but it is still in an experimental stage.
+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/fast16-papers-lu.pdf) that optimizes the large Key-Value of LSM-Tree by separating key-value to reduce the write amplification problem caused by Compaction. The [titan](https://github.com/tikv/titan) project of TiKV is based on WiscKey paper to optimize RocksDB's write amplification in large key-value scenarios. RocksDB also implements this function in the community version, but it is still in an experimental stage.
## 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. Limit the value size can avoid the above-mentioned extreme cases, but it will greatly affect the user scenes of bitmap.
+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 KiB. Limit the value size can avoid the above-mentioned extreme cases, but it will greatly affect the user scenes of bitmap.
-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:
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.
Review Comment:
Consistent with the above, there is a period in the previous sentence.. OCD
--
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-website] git-hulk commented on pull request #70: cleanups in bitmap blog article
Posted by "git-hulk (via GitHub)" <gi...@apache.org>.
git-hulk commented on PR #70:
URL: https://github.com/apache/incubator-kvrocks-website/pull/70#issuecomment-1478842878
@enjoy-binbin Thanks for your fix again.
--
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-website] enjoy-binbin commented on pull request #70: cleanups in bitmap blog article
Posted by "enjoy-binbin (via GitHub)" <gi...@apache.org>.
enjoy-binbin commented on PR #70:
URL: https://github.com/apache/incubator-kvrocks-website/pull/70#issuecomment-1478849280
no problems, thanks for the quick review
--
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-website] tisonkun commented on pull request #70: cleanups in bitmap blog article
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on PR #70:
URL: https://github.com/apache/incubator-kvrocks-website/pull/70#issuecomment-1478848257
Thanks for taking care of it :)
--
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