This is an automated email from the ASF dual-hosted git repository. sunzesong pushed a commit to branch jira_683 in repository https://gitbox.apache.org/repos/asf/incubator-iotdb.git
commit f9f58335d1e2220bef265ba0dffe48e8a23a5c0d Author: samperson1997 <[email protected]> AuthorDate: Mon May 18 14:35:48 2020 +0800 [IOTDB-683] Add system design doc for building MetadataIndex --- docs/SystemDesign/1-TsFile/3-Write.md | 147 ++++++++++++++++++++++++++++++- docs/zh/SystemDesign/1-TsFile/3-Write.md | 147 ++++++++++++++++++++++++++++++- 2 files changed, 292 insertions(+), 2 deletions(-) diff --git a/docs/SystemDesign/1-TsFile/3-Write.md b/docs/SystemDesign/1-TsFile/3-Write.md index 5a28f2d..5be8398 100644 --- a/docs/SystemDesign/1-TsFile/3-Write.md +++ b/docs/SystemDesign/1-TsFile/3-Write.md @@ -61,4 +61,149 @@ 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, 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` + +``` + for (Entry<String, List<TimeseriesMetadata>> entry : deviceTimeseriesMetadataMap.entrySet()) { + // if TimeseriesMetadata list of the device is empty, continue directly + if (entry.getValue().isEmpty()) { + continue; + } + Queue<MetadataIndexNode> measurementMetadataIndexQueue = new ArrayDeque<>(); + TimeseriesMetadata timeseriesMetadata; + // when initializing MetadataIndexNode of one device, new a node of LEAF_MEASUREMENT type + MetadataIndexNode currentIndexNode = new MetadataIndexNode( + MetadataIndexNodeType.LEAF_MEASUREMENT); + for (int i = 0; i < entry.getValue().size(); i++) { + timeseriesMetadata = entry.getValue().get(i); + // when constructing from leaf node, every "degree number of nodes" are related to an entry + if (i % MAX_DEGREE_OF_INDEX_NODE == 0) { + // once current MetadataIndexNode is full, add it into queue, which is used to generate later tree structure + if (currentIndexNode.isFull()) { + addCurrentIndexNodeToQueue(currentIndexNode, measurementMetadataIndexQueue, out); + currentIndexNode = new MetadataIndexNode(MetadataIndexNodeType.LEAF_MEASUREMENT); + } + // new an entry of TimeseriesMetadata, and add it in the current MetadataIndexNode + currentIndexNode.addEntry(new MetadataIndexEntry(timeseriesMetadata.getMeasurementId(), + out.getPosition())); + } + // serialize TimeseriesMetadata + timeseriesMetadata.serializeTo(out.wrapAsStream()); + } + // add current MetadataIndexNode, which contains some remaining entries in this device, into queue + addCurrentIndexNodeToQueue(currentIndexNode, measurementMetadataIndexQueue, out); + // generate root node of measurement index level according to queue (this method will be described later), and put the "device-root node" map into deviceMetadataIndexMap + deviceMetadataIndexMap.put(entry.getKey(), generateRootNode(measurementMetadataIndexQueue, + out, MetadataIndexNodeType.INTERNAL_MEASUREMENT)); + } +``` + +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 +``` + if (deviceMetadataIndexMap.size() <= MAX_DEGREE_OF_INDEX_NODE) { + // new a MetadataIndexNode. Since it cannnot be the leaf node of measurement index level, it is INTERNAL_MEASUREMENT type + MetadataIndexNode metadataIndexNode = new MetadataIndexNode( + MetadataIndexNodeType.INTERNAL_MEASUREMENT); + for (Map.Entry<String, MetadataIndexNode> entry : deviceMetadataIndexMap.entrySet()) { + // new an entry of device metadata, and add it in the current MetadataIndexNode + metadataIndexNode.addEntry(new MetadataIndexEntry(entry.getKey(), out.getPosition())); + // serialize device metadata + entry.getValue().serializeTo(out.wrapAsStream()); + } + // set the endOffset of current MetadataIndexNode and return it + metadataIndexNode.setEndOffset(out.getPosition()); + return metadataIndexNode; + } +``` + +3. If the number of devices exceed `MAX_DEGREE_OF_INDEX_NODE`, the device index level of MetadataIndex tree is generated + +``` + for (Map.Entry<String, MetadataIndexNode> entry : deviceMetadataIndexMap.entrySet()) { + // when constructing from internal node, each node is related to an entry. Once current MetadataIndexNode is full, add it into queue, which is used to generate later tree structure + if (currentIndexNode.isFull()) { + addCurrentIndexNodeToQueue(currentIndexNode, deviceMetadaIndexQueue, out); + // new MetadataIndexNode in LEAF_DEVICE type + currentIndexNode = new MetadataIndexNode(MetadataIndexNodeType.LEAF_DEVICE); + } + // new an entry of device metadata, and add it in the current MetadataIndexNode + currentIndexNode.addEntry(new MetadataIndexEntry(entry.getKey(), out.getPosition())); + // serialize device metadata + entry.getValue().serializeTo(out.wrapAsStream()); + } + // add current MetadataIndexNode, which contains some remaining entries, into queue + addCurrentIndexNodeToQueue(currentIndexNode, deviceMetadaIndexQueue, out); + // generate root node of device index level according to queue (this method will be described later) + deviceMetadataIndexNode = generateRootNode(deviceMetadaIndexQueue, + out, MetadataIndexNodeType.INTERNAL_DEVICE); + // set the endOffset of current MetadataIndexNode and return it + deviceMetadataIndexNode.setEndOffset(out.getPosition()); + return deviceMetadataIndexNode; +``` + +* 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: + +``` + int queueSize = metadataIndexNodeQueue.size(); + MetadataIndexNode metadataIndexNode; + // new a currentIndexNode in specific type + MetadataIndexNode currentIndexNode = new MetadataIndexNode(type); + // loop handle the queue until which has only one root node + while (queueSize != 1) { + for (int i = 0; i < queueSize; i++) { + metadataIndexNode = metadataIndexNodeQueue.poll(); + // when constructing from internal node, each node is related to an entry. Once current MetadataIndexNode is full, add it into queue + if (currentIndexNode.isFull()) { + addCurrentIndexNodeToQueue(currentIndexNode, metadataIndexNodeQueue, out); + currentIndexNode = new MetadataIndexNode(type); + } + // new an entry of the MetadataIndexNode, and add it in the current MetadataIndexNode + currentIndexNode.addEntry(new MetadataIndexEntry(metadataIndexNode.peek().getName(), + out.getPosition())); + // serialize MetadataIndexNode + metadataIndexNode.serializeTo(out.wrapAsStream()); + } + // dd current MetadataIndexNode, which contains some remaining entries, into queue + addCurrentIndexNodeToQueue(currentIndexNode, metadataIndexNodeQueue, out); + currentIndexNode = new MetadataIndexNode(type); + // count current queue size + queueSize = metadataIndexNodeQueue.size(); + } + // return the root node, which is remaining in the queue + return metadataIndexNodeQueue.poll(); +``` + +* 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: + +``` + currentIndexNode.setEndOffset(out.getPosition()); + metadataIndexNodeQueue.add(currentIndexNode); +``` diff --git a/docs/zh/SystemDesign/1-TsFile/3-Write.md b/docs/zh/SystemDesign/1-TsFile/3-Write.md index 0cbb1e4..6727143 100644 --- a/docs/zh/SystemDesign/1-TsFile/3-Write.md +++ b/docs/zh/SystemDesign/1-TsFile/3-Write.md @@ -62,4 +62,149 @@ 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` 中 + +``` + for (Entry<String, List<TimeseriesMetadata>> entry : deviceTimeseriesMetadataMap.entrySet()) { + // 如果设备对应的 TimeseriesMetadata 列表为空，则直接跳过 + if (entry.getValue().isEmpty()) { + continue; + } + Queue<MetadataIndexNode> measurementMetadataIndexQueue = new ArrayDeque<>(); + TimeseriesMetadata timeseriesMetadata; + // 对于每一个设备的 MetadataIndexNode 初始化时，新建一个节点，类型为 LEAF_MEASUREMENT + MetadataIndexNode currentIndexNode = new MetadataIndexNode( + MetadataIndexNodeType.LEAF_MEASUREMENT); + for (int i = 0; i < entry.getValue().size(); i++) { + timeseriesMetadata = entry.getValue().get(i); + // 当使用 TimeseriesMetadata 建立叶子节点的时候，每 MAX_DEGREE_OF_INDEX_NODE 个节点对应一个索引项 entry + if (i % MAX_DEGREE_OF_INDEX_NODE == 0) { + // 一旦当前节点满了，就将其加入节点队列，此队列用于后面不断形成树的层级结构 + if (currentIndexNode.isFull()) { + addCurrentIndexNodeToQueue(currentIndexNode, measurementMetadataIndexQueue, out); + currentIndexNode = new MetadataIndexNode(MetadataIndexNodeType.LEAF_MEASUREMENT); + } + // 将 TimeseriesMetadata 对应成一个索引项放入当前索引节点中 + currentIndexNode.addEntry(new MetadataIndexEntry(timeseriesMetadata.getMeasurementId(), + out.getPosition())); + } + // 将 TimeseriesMetadata 序列化，一个 TimeseriesMetadata 的处理结束 + timeseriesMetadata.serializeTo(out.wrapAsStream()); + } + // 将当前节点加入节点队列，里面包含这个设备中最终剩余的一些索引项 + addCurrentIndexNodeToQueue(currentIndexNode, measurementMetadataIndexQueue, out); + // 根据队列生成当前设备在传感器索引层级最终的根节点（此方法解析见下），并将设备-根节点对应的映射加入 deviceMetadataIndexMap 中 + deviceMetadataIndexMap.put(entry.getKey(), generateRootNode(measurementMetadataIndexQueue, + out, MetadataIndexNodeType.INTERNAL_MEASUREMENT)); + } +``` + +2. 接下来，判断设备数是否超过 `MAX_DEGREE_OF_INDEX_NODE`，如果未超过则可以直接形成元数据索引树的根节点并返回 + +``` + if (deviceMetadataIndexMap.size() <= MAX_DEGREE_OF_INDEX_NODE) { + // 新建一个 MetadataIndexNode，由于它一定不是传感器索引层级的叶子节点，因此其类型为 INTERNAL_MEASUREMENT + MetadataIndexNode metadataIndexNode = new MetadataIndexNode( + MetadataIndexNodeType.INTERNAL_MEASUREMENT); + for (Map.Entry<String, MetadataIndexNode> entry : deviceMetadataIndexMap.entrySet()) { + // 将设备的元数据对应成一个索引项放入当前索引节点中 + metadataIndexNode.addEntry(new MetadataIndexEntry(entry.getKey(), out.getPosition())); + // 将设备元数据序列化 + entry.getValue().serializeTo(out.wrapAsStream()); + } + // 设置当前 MetadataIndexNode 的 endOffset 并返回 + metadataIndexNode.setEndOffset(out.getPosition()); + return metadataIndexNode; + } +``` + +3. 如果设备数超过 `MAX_DEGREE_OF_INDEX_NODE`，则需要形成元数据索引树的设备索引层级 + +``` + for (Map.Entry<String, MetadataIndexNode> entry : deviceMetadataIndexMap.entrySet()) { + // 当建立中间节点的时候，每个节点对应一个索引项 entry，一旦当前节点满了，就将其加入节点队列，此队列用于后面不断形成树的层级结构 + if (currentIndexNode.isFull()) { + addCurrentIndexNodeToQueue(currentIndexNode, deviceMetadaIndexQueue, out); + // 此时初始化的新 MetadataIndexNode 节点类型为 LEAF_DEVICE + currentIndexNode = new MetadataIndexNode(MetadataIndexNodeType.LEAF_DEVICE); + } + // 将设备的元数据对应成一个索引项放入当前索引节点中 + currentIndexNode.addEntry(new MetadataIndexEntry(entry.getKey(), out.getPosition())); + // 将设备元数据序列化 + entry.getValue().serializeTo(out.wrapAsStream()); + } + // 将当前节点加入节点队列，里面包含最终剩余的一些索引项 + addCurrentIndexNodeToQueue(currentIndexNode, deviceMetadaIndexQueue, out); + // 根据队列生成设备索引层级最终的根节点（此方法解析见下） + deviceMetadataIndexNode = generateRootNode(deviceMetadaIndexQueue, + out, MetadataIndexNodeType.INTERNAL_DEVICE); + // 设置当前 MetadataIndexNode 的 endOffset 并返回 + deviceMetadataIndexNode.setEndOffset(out.getPosition()); + return deviceMetadataIndexNode; +``` + +* MetadataIndexConstructor.generateRootNode + +方法的输入包括： +* Queue\<MetadataIndexNode\> metadataIndexNodeQueue，是放有 MetadataIndexNode 的队列 +* TsFileOutput out，是包装好的 TsFile output +* MetadataIndexNodeType type，是所形成的树的内部节点的类型，有两种：在传感器索引层级调用时，传入 INTERNAL_MEASUREMENT；在设备索引层级调用时，传入 INTERNAL_DEVICE + +该方法需要将队列中的 MetadataIndexNode 形成树级结构，并返回根节点： + +``` + int queueSize = metadataIndexNodeQueue.size(); + MetadataIndexNode metadataIndexNode; + // 根据需要的类型初始化一个 currentIndexNode + MetadataIndexNode currentIndexNode = new MetadataIndexNode(type); + // 循环处理队列，直到队列中只有根节点时结束 + while (queueSize != 1) { + for (int i = 0; i < queueSize; i++) { + metadataIndexNode = metadataIndexNodeQueue.poll(); + // 当建立中间节点的时候，每个节点对应一个索引项 entry，一旦当前节点满了，就将其加入节点队列 + if (currentIndexNode.isFull()) { + addCurrentIndexNodeToQueue(currentIndexNode, metadataIndexNodeQueue, out); + currentIndexNode = new MetadataIndexNode(type); + } + // 将节点的元数据对应成一个索引项放入当前索引节点中 + currentIndexNode.addEntry(new MetadataIndexEntry(metadataIndexNode.peek().getName(), + out.getPosition())); + // 将节点序列化 + metadataIndexNode.serializeTo(out.wrapAsStream()); + } + // 将当前节点加入节点队列，里面包含最终剩余的一些索引项 + addCurrentIndexNodeToQueue(currentIndexNode, metadataIndexNodeQueue, out); + currentIndexNode = new MetadataIndexNode(type); + // 计算当前队列的大小，判断其是否为1 + queueSize = metadataIndexNodeQueue.size(); + } + // 返回队列中最终剩余的根节点 + return metadataIndexNodeQueue.poll(); +``` + +* MetadataIndexConstructor.addCurrentIndexNodeToQueue + +方法的输入包括： +* MetadataIndexNode currentIndexNode，是当前需要加入队列的 MetadataIndexNode +* Queue\<MetadataIndexNode\> metadataIndexNodeQueue，是放有 MetadataIndexNode 的队列 +* TsFileOutput out，是包装好的 TsFile output + +该方法直接设定当前节点的 endOffset，并将该节点加入队列中： + +``` + currentIndexNode.setEndOffset(out.getPosition()); + metadataIndexNodeQueue.add(currentIndexNode); +```
