This is an automated email from the ASF dual-hosted git repository.
qiaojialin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-iotdb.git
The following commit(s) were added to refs/heads/master by this push:
new 52868fe [IOTDB-683] Add system design doc for building MetadataIndex
(#1219)
52868fe is described below
commit 52868fe40568b78c0e8dbd968b038b41d5ca993f
Author: Zesong Sun <[email protected]>
AuthorDate: Tue May 19 20:18:04 2020 +0800
[IOTDB-683] Add system design doc for building MetadataIndex (#1219)
* [IOTDB-683] Add system design doc for building MetadataIndex
---
docs/SystemDesign/1-TsFile/3-Write.md | 64 +++++++++++++++++++++++++++++++-
docs/zh/SystemDesign/1-TsFile/3-Write.md | 63 ++++++++++++++++++++++++++++++-
2 files changed, 125 insertions(+), 2 deletions(-)
diff --git a/docs/SystemDesign/1-TsFile/3-Write.md
b/docs/SystemDesign/1-TsFile/3-Write.md
index 5a28f2d..4d807c3 100644
--- a/docs/SystemDesign/1-TsFile/3-Write.md
+++ b/docs/SystemDesign/1-TsFile/3-Write.md
@@ -61,4 +61,66 @@ After the persistence is complete, the corresponding
metadata information is cac
- TsFileWriter.close()
-Based on the metadata cached in memory, TsFileMetadata is generated and
appended to the end of the file, and the file is finally closed.
\ No newline at end of file
+Based on the metadata cached in memory, TsFileMetadata is generated and
appended to the end of the file (`TsFileWriter.flushMetadataIndex()`), and the
file is finally closed.
+
+One of the most important steps in constructing TsFileMetadata is to construct
MetadataIndex tree. As we have mentioned before, the MetadataIndex is designed
as tree structure so that not all the `TimeseriesMetadata` need to be read when
the number of devices or measurements is too large. Only reading specific
MetadataIndex nodes according to requirement and reducing I/O could speed up
the query. The whole process of constructing MetadataIndex tree is as below:
+
+* org.apache.iotdb.tsfile.file.metadata.MetadataIndexConstructor
+
+### MetadataIndexConstructor.constructMetadataIndex()
+
+The input params of this method:
+* Map\<String, List\<TimeseriesMetadata\>\> deviceTimeseriesMetadataMap, which
indicates the map from device to its `TimeseriesMetadata`
+* TsFileOutput out
+
+The whole method contains three parts:
+
+1. In measurement index level, each device and its TimeseriesMetadata in
`deviceTimeseriesMetadataMap` is converted into `deviceMetadataIndexMap`.
Specificly, for each device:
+ * Initialize a `queue` for MetadataIndex nodes in this device
+ * Initialize a leaf node of measurement index level, which is
`LEAF_MEASUREMENT` type
+ * For each TimeseriesMetadata：
+ * Serialize
+ * Add an entry into `currentIndexNode` every `MAX_DEGREE_OF_INDEX_NODE`
entries
+ * After storing `MAX_DEGREE_OF_INDEX_NODE` entries, add `currentIndexNode`
into `queue`, and point `currentIndexNode` to a new MetadataIndexNode
+ * Generate upper-level nodes of measurement index level according to the
leaf nodes in `queue`, until the final root node (this method will be described
later), and put the "device-root node" map into `deviceMetadataIndexMap`
+
+2. Then judge whether the number of devices exceed `MAX_DEGREE_OF_INDEX_NODE`.
If not, the root node of MetadataIndex tree could be generated and return
+ * Initialize the root node of MetadataIndex tree, which is
`INTERNAL_MEASUREMENT` type
+ * For each entry in `deviceMetadataIndexMap`:
+ * Serialize
+ * Convert it into an entry and add the entry into `metadataIndexNode`
+ * Set the `endOffset` of root node and return it
+
+3. If the number of devices exceed `MAX_DEGREE_OF_INDEX_NODE`, the device
index level of MetadataIndex tree is generated
+ * Initialize a `queue` for MetadataIndex nodes in device index level
+ * Initialize a leaf node of device index level, which is `LEAF_DEVICE` type
+ * For each entry in `deviceMetadataIndexMap`:
+ * Serialize
+ * Convert it into an entry and add the entry into `metadataIndexNode`
+ * After storing `MAX_DEGREE_OF_INDEX_NODE` entries, add `currentIndexNode`
into `queue`, and point `currentIndexNode` to a new MetadataIndexNode
+ * Generate upper-level nodes of device index level according to the leaf
nodes in `queue`, until the final root node (this method will be described
later)
+ * Set the `endOffset` of root node and return it
+
+### MetadataIndexConstructor.generateRootNode
+
+The input params of this method:
+* Queue\<MetadataIndexNode\> metadataIndexNodeQueue
+* TsFileOutput out
+* MetadataIndexNodeType type, which indicates the internal nodes type of
generated tree. There are two types: when the method is called by measurement
index level, it is INTERNAL_MEASUREMENT; when the method is called by device
index level, it is INTERNAL_DEVICE
+
+The method needs to generate a tree structure of nodes in
metadataIndexNodeQueue, and return the root node:
+1. New `currentIndexNode` in specific `type`
+2. When there are more than one nodes in the queue, loop handling the queue.
For each node in the queue:
+ * Serialize
+ * Convert it into an entry and add the entry into `currentIndexNode`
+ * After storing `MAX_DEGREE_OF_INDEX_NODE` entries, add `currentIndexNode`
into `queue`, and point `currentIndexNode` to a new MetadataIndexNode
+3. Return the root node in the queue when the queue has only one node
+
+### MetadataIndexConstructor.addCurrentIndexNodeToQueue
+
+The input params of this method:
+* MetadataIndexNode currentIndexNode
+* Queue\<MetadataIndexNode\> metadataIndexNodeQueue
+* TsFileOutput out
+
+This method set the endOffset of current MetadataIndexNode, and put it into
queue.
\ No newline at end of file
diff --git a/docs/zh/SystemDesign/1-TsFile/3-Write.md
b/docs/zh/SystemDesign/1-TsFile/3-Write.md
index 0cbb1e4..b9e4936 100644
--- a/docs/zh/SystemDesign/1-TsFile/3-Write.md
+++ b/docs/zh/SystemDesign/1-TsFile/3-Write.md
@@ -62,4 +62,65 @@ TsFile 文件层的写入接口有两种
* TsFileWriter.close()
-根据内存中缓存的元数据，生成 TsFileMetadata 追加到文件尾部，最后关闭文件。
\ No newline at end of file
+根据内存中缓存的元数据，生成 TsFileMetadata
追加到文件尾部(`TsFileWriter.flushMetadataIndex()`)，最后关闭文件。
+
+生成 TsFileMetadata 的过程中比较重要的一步是建立元数据索引 (MetadataIndex)
树。正如我们提到过的，元数据索引采用树形结构进行设计的目的是在设备数或者传感器数量过大时，可以不用一次读取所有的
`TimeseriesMetadata`，只需要根据所读取的传感器定位对应的节点，从而减少 I/O，加快查询速度。以下是建立元数据索引树的详细算法和过程：
+
+* org.apache.iotdb.tsfile.file.metadata.MetadataIndexConstructor
+
+### MetadataIndexConstructor.constructMetadataIndex()
+
+方法的输入包括：
+* Map\<String, List\<TimeseriesMetadata\>\> deviceTimeseriesMetadataMap，表示设备到其
TimeseriesMetadata 列表的映射
+* TsFileOutput out，是包装好的 TsFile output
+
+整个方法分成三大部分：
+1. 在传感器索引层级，把 `deviceTimeseriesMetadataMap` 中的每一个设备及其 `TimeseriesMetadata`
列表，转化为 MetadataIndexNode 并放进 `deviceMetadataIndexMap` 中。具体来说，对于每一个设备：
+ * 初始化此设备的索引节点的队列 `queue`
+ * 初始化传感器索引层级的叶子节点 `currentIndexNode` ，类型为 `LEAF_MEASUREMENT`
+ * 对于每个 TimeseriesMetadata：
+ * 序列化
+ * 每隔 `MAX_DEGREE_OF_INDEX_NODE` 个，加一条 entry 到 `currentIndexNode` 中
+ * 每当 currentIndexNode 中攒够 `MAX_DEGREE_OF_INDEX_NODE` 个 entry 后，将
`currentIndexNode` 加入 `queue` 中，并将 `currentIndexNode` 指向一个新的 MetadataIndexNode
+ * 根据 `queue` 中已经存储的叶子节点，逐层生成上层节点，直至最终的根节点（此方法解析见下），并将"设备-根节点"对应的映射加入
`deviceMetadataIndexMap` 中
+
+2. 接下来，判断设备数是否超过 `MAX_DEGREE_OF_INDEX_NODE`，如果未超过则可以直接形成元数据索引树的根节点并返回
+ * 初始化元数据索引树的根节点 `metadataIndexNode`，类型为 `INTERNAL_MEASUREMENT`
+ * 对于 `deviceMetadataIndexMap` 中的每一个 entry：
+ * 序列化
+ * 将其转化成一个索引项，加入到 `metadataIndexNode` 中
+ * 设置根节点的 `endOffset` 并返回
+
+3. 如果设备数超过 `MAX_DEGREE_OF_INDEX_NODE`，则需要形成元数据索引树的设备索引层级
+ * 初始化存放设备索引层级节点的队列 `queue`
+ * 初始化设备索引层级的叶子节点 `currentIndexNode` ，类型为 `LEAF_DEVICE`
+ * 对于 `deviceMetadataIndexMap` 中的每一个 entry：
+ * 序列化
+ * 将其转化成一个索引项，加入到 `metadataIndexNode` 中
+ * 每当 currentIndexNode 中攒够 `MAX_DEGREE_OF_INDEX_NODE` 个 entry 后，将
`currentIndexNode` 加入 `queue` 中，并将 `currentIndexNode` 指向一个新的 MetadataIndexNode
+ * 根据 `queue` 中已经存储的叶子节点，逐层生成上层节点，直至最终的根节点（此方法解析见下）
+ * 设置根节点的 `endOffset` 并返回
+
+### MetadataIndexConstructor.generateRootNode
+
+方法的输入包括：
+* Queue\<MetadataIndexNode\> metadataIndexNodeQueue，是放有 MetadataIndexNode 的队列
+* TsFileOutput out，是包装好的 TsFile output
+* MetadataIndexNodeType type，是所形成的树的内部节点的类型，有两种：在传感器索引层级调用时，传入
INTERNAL_MEASUREMENT；在设备索引层级调用时，传入 INTERNAL_DEVICE
+
+该方法需要将队列中的 MetadataIndexNode 形成树级结构，并返回根节点：
+1. 根据需要的类型 `type` 初始化 `currentIndexNode`
+2. 当队列中有多余一个节点时，循环处理队列，对于队列中存在的每个节点：
+ * 序列化
+ * 将其转化成一个索引项，加入到 `currentIndexNode` 中
+ * 每当 currentIndexNode 中攒够 `MAX_DEGREE_OF_INDEX_NODE` 个 entry 后，将
`currentIndexNode` 加入 `queue` 中，并将 `currentIndexNode` 指向一个新的 MetadataIndexNode
+3. 队列中只剩下一个节点时，返回队列中最终剩余的根节点
+
+### MetadataIndexConstructor.addCurrentIndexNodeToQueue
+
+方法的输入包括：
+* MetadataIndexNode currentIndexNode，是当前需要加入队列的 MetadataIndexNode
+* Queue\<MetadataIndexNode\> metadataIndexNodeQueue，是放有 MetadataIndexNode 的队列
+* TsFileOutput out，是包装好的 TsFile output
+
+该方法直接设定当前节点的 endOffset，并将该节点加入队列中。
\ No newline at end of file
