[incubator-kvrocks-website] branch main updated: Add description of Stream design (#17)

[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 84802a4  Add description of Stream design (#17)
84802a4 is described below

commit 84802a4fd18634ec7ae6bc1769fd96f6a382646f
Author: Yaroslav <to...@gmail.com>
AuthorDate: Thu Sep 22 15:38:13 2022 +0300

    Add description of Stream design (#17)
---
 docs/04-Design/00-design-structure-on-rocksdb.md | 38 ++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)

diff --git a/docs/04-Design/00-design-structure-on-rocksdb.md b/docs/04-Design/00-design-structure-on-rocksdb.md
index 8222d41..d751600 100644
--- a/docs/04-Design/00-design-structure-on-rocksdb.md
+++ b/docs/04-Design/00-design-structure-on-rocksdb.md
@@ -1,6 +1,6 @@
 # Design Complex Structure On Rocksdb
 
-kvrocks uses the rocksdb as storage, it's developed by Facebook which is built on LevelDB with many extra features, like column family, transaction and backup, see the rocksdb wiki: [Features Not In LevelDB](https://github.com/facebook/rocksdb/wiki/Features-Not-in-LevelDB). The basic operations in rocksdb are `Put(key, value)`, `Get(key)`, `Delete(key)`, other complex structures aren't supported. The main goal of this doc is to explain how we built the Redis hash/list/set/zset/bitmap on  [...]
+kvrocks uses the rocksdb as storage, it's developed by Facebook which is built on LevelDB with many extra features, like column family, transaction and backup, see the rocksdb wiki: [Features Not In LevelDB](https://github.com/facebook/rocksdb/wiki/Features-Not-in-LevelDB). The basic operations in rocksdb are `Put(key, value)`, `Get(key)`, `Delete(key)`, other complex structures aren't supported. The main goal of this doc is to explain how we built the Redis hash/list/set/zset/bitmap/str [...]
 
 ## String
 
@@ -15,7 +15,7 @@ key =>  |  flags   |  expire    |       payload      |
 
 we prepend 1-byte `flags` and 4-bytes expire before the user's value:
 
-- `flags` is used to tell the kvrocks which type of this key-value, maybe `string`/`hash`/`list`/`zset`/`bitmap`
+- `flags` is used to tell the kvrocks which type of this key-value, maybe `string`/`hash`/`list`/`zset`/`bitmap`/`stream`
 - `expire` stores the absolute time of key should be expired, zero means the key-value would never expire
 - `payload` is the user's raw value
 
@@ -185,3 +185,37 @@ key|version|id => |      NULL     |
                   +---------------+
 ```
 
+## Stream
+
+Each entry in a stream has its unique ID in the form of `MS-SEQ` where `MS` is the number of milliseconds and `SEQ` is the counter for entries added within the same millisecond. These two values are concatenated with the `-` (minus sign). The entry ID may be generated by the server or explicitly set by the client. A stream metadata tracks the ID of the last added entry. 
+
+#### stream metadata
+
+Redis stream is organized by the metadata and sub keys-values. The metadata has fields mentioned before (`flags`, `expiration`, `version`, `size`) and additional fields, that are specific only for this data type. The structure of the metadata value is the following:
+
+- `flags` (1 byte)
+- `expiration` (4 bytes)
+- `version` (8 bytes)
+- `size` (4 bytes)
+- `LGE ID MS` (8 bytes) stores the `MS` value of the last generated entry ID
+- `LGE ID SEQ` (8 bytes) stores the `SEQ` value of the last generated entry ID
+- `RFE ID MS` (8 bytes) stores the `MS` value of the very first entry ID that was added to the stream
+- `RFE ID SEQ` (8 bytes) stores the `SEQ` value of the very first entry ID that was added to the stream
+- `MDE ID MS` (8 bytes) stores the `MS` value of the max deleted entry ID
+- `MDE ID SEQ` (8 bytes) stores the `SEQ` value of the max deleted entry ID
+- `FE ID MS` (8 bytes) stores the `MS` value of the current first entry ID
+- `FE ID SEQ` (8 bytes) stores the `SEQ` value of the current first entry ID
+- `LE ID MS` (8 bytes) stores the `MS` value of the current last entry ID
+- `LE ID SEQ` (8 bytes) stores the `SEQ` value of the current last entry ID
+- `TNE` (8 bytes) stores the total number of entries that were added to the stream during its lifetime
+
+#### stream sub keys-values
+
+the sub-key in a stream is composed by the stream key, version and the entry ID. The entry ID is encoded as two consecutive 8-bytes integer values (`EID MS` and `EID SEQ`). The stream entry value may represent any even number of strings. This value is encoded as a sequence of strings and each string value is prepended by its length as a 4-bytes variable integer. 
+
+```shell
+                              +-----------------------+
+key|version|EID MS|EID SEQ => |     encoded value     |
+                              +-----------------------+
+```
+