亚洲欧美日韩综合系列在线_91精品人妻一区二区_欧美大肥婆一级特大AA片_九色91视频免费观看_亚洲综合国产精品_av中文字幕在线不卡_久久精品色综合网_看黄色视频的软件_无卡无码高清中文字幕码2024_亚洲欧美日韩天堂网

本文是對面向 IoT 領域的開源時序數(shù)據庫 BTrDB 內部實現(xiàn)細節(jié)的研究和介紹。

1. 場景介紹

BTrDB 論文中介紹了一個實際的項目，能很好解釋清楚 BTrDB 的設計初衷和適用場景：

在一個電網中大量部署了某類傳感器，每個傳感器會產生 12 條時間線，每條時間線頻率為 120Hz（即每秒 120 個點），時間精度為 100ns；由于各種原因，傳感器數(shù)據傳輸經常性出現(xiàn)延遲、（時間）亂序等。BTrDB 在該場景下單機能支撐 1000 個類似的傳感器，寫入速率約 1.44M points/s。

該項目有這樣幾個特點：
1. 時間線在很長時間內有一定的不變性，其生命周期跟(IoT)設備周期一致
2. 數(shù)據頻率很高（120 Hz）且固定
3. 數(shù)據的時間分辨率很高（100ns級別），一般如Druid，TimescaleDB 時間精度最多做到 ms 級別
4. 數(shù)據傳輸經常性出現(xiàn)亂序
5. 時間線數(shù)量有限

BTrDB 為了適應上述場景，設計并提出了 "time-partitioning version-annotated copy-on-write tree" 的數(shù)據結構，為每一條時間線構建了一棵樹（可以參考B+Tree），數(shù)據在該樹中按照時間戳排序，葉子節(jié)點有序得存放某個時間段內的時序數(shù)據。
可以想見，這棵樹的生命周期跟設備的生命周期直接掛鉤，因此隨著時間的發(fā)展，這棵樹即使只包含一條時間線，也會占用很可觀的存儲空間（約 10M points/day）；另外由于是基于樹結構，并且引入了版本（version-annotated) 的概念，BTrDB 可以很好的支持亂序數(shù)據和任意精度的時序數(shù)據。

由于數(shù)據結構不同于以往時序數(shù)據庫基于LSM-Tree的變種，因此 BTrDB 還提供了一套新的時序數(shù)據查詢接口，方便在 BTrDB 上層構建各種算法和應用。

2. 數(shù)據結構

2.1 version-annotated & CoW 特性

在數(shù)據寫入時，BTrDB 會先修改在內存中的數(shù)據塊（新建或者使用 CoW 機制修改已有塊），當數(shù)據達到一定閾值時再寫回底層塊存儲；由于 CoW 機制，并且底層塊存儲（默認使用Ceph）無法覆蓋更新，因此只能創(chuàng)建一個新版本的數(shù)據塊。

2.2. 葉子節(jié)點

對于 IoT 設備發(fā)來的數(shù)據，由于頻率固定，這些葉子節(jié)點占用空間大小基本一致。

葉子節(jié)點還未持久化到底層存儲時，在內存中通過數(shù)組的方式分別存放時間戳和（雙精度浮點）值；在序列化到底層存儲時，會通過delta-delta的方式壓縮時間戳和值；在序列化雙精度浮點數(shù)值之前，會將浮點數(shù)據數(shù)拆分為尾數(shù)和指數(shù)兩部分，并分別進行delta-delta壓縮。

2.3. 中間節(jié)點:

中間節(jié)點被劃分為多個 bucket，每個 bucket 中存放著指向子節(jié)點的鏈接（帶版本號）以及子節(jié)點的統(tǒng)計數(shù)據：

• 子節(jié)點的時間范圍

• 聚合數(shù)據，如 sum, max, min，count 等

• 子節(jié)點連接地址和版本號

在處理查詢時，如果中間節(jié)點的時間精度滿足查詢需求，查詢操作就不再讀取下層子節(jié)點了，這樣就很自然的實現(xiàn)了將精度功能；這種實現(xiàn)方式，能夠很好的處理亂序、重復數(shù)據以及刪除操作，并且與其他現(xiàn)有的實現(xiàn)相比，能夠很好的保證數(shù)據的一致性。

2.4. 插入時樹的分裂

一棵新的樹（對應一條新的時間線）只有一個根節(jié)點，在 BTrDB 的實現(xiàn)中，根節(jié)點時間跨度約為146.23年，這樣每個 bucket 的時間跨度為 146.23/64 ~= 2.28 （年），根據默認配置，1970年在根節(jié)點的第16個 bucket。

可見，根節(jié)點在創(chuàng)建時就已經限制了數(shù)據的時間范圍，后續(xù)數(shù)據的插入是自頂向下逐層分裂的，當數(shù)據因為丟失等原因造成時間線不完整時，部分節(jié)點的深度可能會不一樣，因此并不是一顆嚴格的平衡樹。數(shù)據插入過程如下：

• 數(shù)據插入操作從根節(jié)點開始；

• 如果當前節(jié)點是中間節(jié)點，則遍歷每個數(shù)據，為每個數(shù)據找到對應的 bucket；

• 如果對應的 bucket 不存在，則創(chuàng)建新的 bucket 和與該 bucket 關聯(lián)的子節(jié)點：

  • 如果當前 bucket 待插入的點個數(shù)超過葉子節(jié)點最大點數(shù)（默認1024），則直接創(chuàng)建中間子節(jié)點；

  • 否則，創(chuàng)建葉子節(jié)點；

• 將數(shù)據插入到與所屬 bucket 關聯(lián)的子節(jié)點中；

• 如果當前節(jié)點是葉子節(jié)點，節(jié)點中數(shù)據個數(shù)和待插入數(shù)據個數(shù)總合超過 1024 個點，則分裂當前節(jié)點創(chuàng)建出新的中間節(jié)點，將數(shù)據插入新的中間節(jié)點；否則將待插入數(shù)據和當前節(jié)點已有數(shù)據合并，并按照時間戳排序；

• 當前節(jié)點插入成功后，自底向上更新父節(jié)點的統(tǒng)計信息；

從上面過程可以看到，節(jié)點在插入時在兩個地方可能出現(xiàn)分裂。一個是從根節(jié)點開始，自頂向下分裂；另一個是從葉子節(jié)點開始，向上分裂。

雖然這棵樹并不是一顆平衡樹，但是對于 IoT 類項目，設備的時間線生命周期、數(shù)據采集頻率很穩(wěn)定，在絕大多數(shù)場景下，節(jié)點中數(shù)據都是均衡分布的。

2.5 節(jié)點占用的內存空間

在默認實現(xiàn)中，葉子節(jié)點中最多存儲1024個數(shù)據點；中間節(jié)點中最多存儲64個子節(jié)點指針，因此：

• 對于還未持久化的葉子節(jié)點，占用的內存空間為：1024*2*8 = 16K（見 2.2.1）

• 對于還未持久化的中間節(jié)點，占用的內存為：64*6*8 + 64*2*8 = 4K（見 2.2.2）

3. 數(shù)據存儲相關

3.1 寫 WAL

• 在數(shù)據插入時，會先將數(shù)據寫入到 WAL(Write Ahead Log) 中；

• 每次寫 WAL 都會返回一個check point，代表數(shù)據在WAL中的寫入位置；

• WAL 寫入成功后，原始數(shù)據和 check point 會被寫入時間線的緩沖區(qū)；

• 時間線的緩沖與時間線一一對應，最大容納32768個數(shù)據點；

• 當緩沖區(qū)滿時，數(shù)據會被插入到樹結構中，并將該緩沖區(qū)對應的 check points 在 WAL 中標記為刪除狀態(tài)；

• 在 WAL 的 replay 過程中會根據已被刪除的 check points 過濾原始數(shù)據。

下面的示意圖展示了WAL中 check points 與時間序列緩沖區(qū)的關聯(lián)關系，在緩沖區(qū)清空后，BTrDB 會將已經刪除的 check points 寫入到當前 WAL 對應的塊文件的元信息（block attributes）中：

當一個 WAL 塊文件中所有的 check points 都標記為已刪除時，該文件就可以從 Ceph 中刪除了。當前 WAL 文件大小超過16M時就會創(chuàng)建新的塊文件，在理想情況下，塊文件都能被及時刪除；但是如果某些時間線出現(xiàn)異常，向前文提到的，其緩沖區(qū)在 8 小時后才能被回收，那么負責記錄這些時間線的 WAL 文件也就只能在8小時后被回收。
這些滯留的 WAL 文件大小只有16M，數(shù)量與出現(xiàn)異常的 IoT 設備數(shù)量成線性關系，因此需要更多 IoT 設備運行統(tǒng)計數(shù)據才能統(tǒng)計其影響。

3.2 寫 Block

BTrDB 的樹結構在持久化后會產生兩類數(shù)據，一個稱為 superblock，記錄了當前樹的最新版本、更新時間、根節(jié)點位置等基本信息；另外一個稱為 segment，統(tǒng)一包含了樹的葉子節(jié)點和中間節(jié)點的數(shù)據。

superblock 是帶版本的，每個版本的 superblock 只占用16Byte，格式為：

{root: 根節(jié)點位置，8Byte, timestamp: 修改時間，8Byte}

superblock 在 Ceph 中的尋址方式為：

塊存儲 id = uuid.toString() + (version >> 20)
塊存儲中的 offset = (version & 0xFFFFF)*16

在 BTrDB 中持久化樹結構時葉子節(jié)點和中間節(jié)點會一并序列化到 segment 中，每個節(jié)點的尋址編碼方式為：

塊存儲的 id = uuid.toString() + (address >> 24)
節(jié)點在塊存儲中的偏移量 = (address & 0xFFFFFF)

可以看到， WAL 文件， superblock 塊文件以及 segment 塊文件大小都是 16M。另外，BTrDB 中沒有 compaction，也沒有對過期版本數(shù)據的清理，只有上文中介紹的對 WAL 的處理，寫入放大會很明顯。

新的查詢語義

這里只是羅列、簡單介紹下 BTrDB 提供的新的查詢語義，這些查詢語義的提出與 BTrDB 的數(shù)據結構有很大關系，或者是為了利用樹結構某些特性，或者是為了規(guī)避樹結構一些不足：

• GetRange(UUID, StartTime, EndTime, Version) → (Version, [(Time, Value)]) 查詢時間線在某個時間范圍內的詳細（原始）數(shù)據；

• GetLatestVersion(UUID) → Version 查詢時間線最新版本；

• GetStatisticalRange(UUID, StartTime, EndTime, Version, Resolution) → (Version, [(Time, Min, Mean, Max, Count)]) 獲取給定時間范圍內，滿足一定時間精度的，大于等于給定版本的時間線的聚合數(shù)據；

• GetNearestValue(UUID, Time, Version, Direction) → (Version, (Time, Value)) 向前、向后獲取下一個點；

• ComputeDiff(UUID, FromVersion, ToVersion, Resolution) → [(StartTime, EndTime)] 在滿足給定時間精度條件下，獲取兩個版本號范圍內，所有更新節(jié)點的起止時間；適合做增量計算。

上面接口中的時間分辨率參數(shù)（Resolution），對于接口的性能有很大影響。前文提到根節(jié)點的時間分辨率是2.2年，從樹的根節(jié)點到底層節(jié)點，節(jié)點中數(shù)據的時間分辨率越來越高；在查詢時，低分辨率數(shù)據聚合程度高，掃面的數(shù)據塊少；高分辨率的數(shù)據聚合程度低，但是需要掃面的數(shù)據塊很多。

總結

BTrDB 中數(shù)據結構是針對單條時間線構建的，并且針對 IoT 設備數(shù)據穩(wěn)定的特點，構建了一棵樹來存儲時序數(shù)據；樹結構解決了傳統(tǒng) TSDB 在亂序插入、刪除、預降精度等方面面臨的問題。