時序資料庫連載系列：Berkeley 的黑科技 BTrDB

本文是對面向 IoT 領域的開源時序資料庫 BTrDB 内部實作細節的研究和介紹。

https://www.atatech.org/articles/131386#0 1. 場景介紹

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

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

該項目有這樣幾個特點：

1. 時間線在很長時間内有一定的不變性，其生命周期跟(IoT)裝置周期一緻

2. 資料頻率很高（120 Hz）且固定

3. 資料的時間分辨率很高（100ns級别），一般如Druid，TimescaleDB 時間精度最多做到 ms 級别

4. 資料傳輸經常性出現亂序

5. 時間線數量有限

BTrDB 為了适應上述場景，設計并提出了 "time-partitioning version-annotated copy-on-write tree" 的資料結構，為每一條時間線建構了一棵樹（可以參考B+Tree），資料在該樹中按照時間戳排序，葉子節點有序得存放某個時間段内的時序資料。

可以想見，這棵樹的生命周期跟裝置的生命周期直接挂鈎，是以随着時間的發展，這棵樹即使隻包含一條時間線，也會占用很可觀的存儲空間（約 10M points/day）；另外由于是基于樹結構，并且引入了版本（version-annotated) 的概念，BTrDB 可以很好的支援亂序資料和任意精度的時序資料。

由于資料結構不同于以往時序資料庫基于LSM-Tree的變種，是以 BTrDB 還提供了一套新的時序資料查詢接口，友善在 BTrDB 上層建構各種算法和應用。

https://www.atatech.org/articles/131386#1 2. 資料結構

https://www.atatech.org/articles/131386#2 2.1 version-annotated & CoW 特性

在資料寫入時，BTrDB 會先修改在記憶體中的資料塊（建立或者使用 CoW 機制修改已有塊），當資料達到一定門檻值時再寫回底層塊存儲；由于 CoW 機制，并且底層塊存儲（預設使用Ceph）無法覆寫更新，是以隻能建立一個新版本的資料塊。

https://www.atatech.org/articles/131386#3 2.2. 葉子節點

對于 IoT 裝置發來的資料，由于頻率固定，這些葉子節點占用空間大小基本一緻。

葉子節點還未持久化到底層存儲時，在記憶體中通過數組的方式分别存放時間戳和（雙精度浮點）值；在序列化到底層存儲時，會通過delta-delta的方式壓縮時間戳和值；在序列化雙精度浮點數值之前，會将浮點資料數拆分為尾數和指數兩部分，并分别進行delta-delta壓縮。

https://www.atatech.org/articles/131386#4 2.3. 中間節點:

中間節點被劃分為多個 bucket，每個 bucket 中存放着指向子節點的連結（帶版本号）以及子節點的統計資料：

• 子節點的時間範圍
• 聚合資料，如 sum, max, min，count 等
• 子節點連接配接位址和版本号

在處理查詢時，如果中間節點的時間精度滿足查詢需求，查詢操作就不再讀取下層子節點了，這樣就很自然的實作了将精度功能；這種實作方式，能夠很好的處理亂序、重複資料以及删除操作，并且與其他現有的實作相比，能夠很好的保證資料的一緻性。

https://www.atatech.org/articles/131386#5 2.4. 插入時樹的分裂

一棵新的樹（對應一條新的時間線）隻有一個根節點，在 BTrDB 的實作中，根節點時間跨度約為146.23年，這樣每個 bucket 的時間跨度為 

146.23/64 ~= 2.28

 （年），根據預設配置，1970年在根節點的第16個 bucket。

可見，根節點在建立時就已經限制了資料的時間範圍，後續資料的插入是自頂向下逐層分裂的，當資料因為丢失等原因造成時間線不完整時，部分節點的深度可能會不一樣，是以并不是一顆嚴格的平衡樹。資料插入過程如下：

• 資料插入操作從根節點開始；
• 如果目前節點是中間節點，則周遊每個資料，為每個資料找到對應的 bucket；
• 如果對應的 bucket 不存在，則建立新的 bucket 和與該 bucket 關聯的子節點：
  • 如果目前 bucket 待插入的點個數超過葉子節點最大點數（預設1024），則直接建立中間子節點；
  • 否則，建立葉子節點；
• 将資料插入到與所屬 bucket 關聯的子節點中；
• 如果目前節點是葉子節點，節點中資料個數和待插入資料個數總合超過 1024 個點，則分裂目前節點建立出新的中間節點，将資料插入新的中間節點；否則将待插入資料和目前節點已有資料合并，并按照時間戳排序；
• 目前節點插入成功後，自底向上更新父節點的統計資訊；

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

雖然這棵樹并不是一顆平衡樹，但是對于 IoT 類項目，裝置的時間線生命周期、資料采集頻率很穩定，在絕大多數場景下，節點中資料都是均衡分布的。

https://www.atatech.org/articles/131386#6 2.5 節點占用的記憶體空間

在預設實作中，葉子節點中最多存儲1024個資料點；中間節點中最多存儲64個子節點指針，是以：

• 對于還未持久化的葉子節點，占用的記憶體空間為：

  1024*2*8 = 16K

  （見 2.2.1）
• 對于還未持久化的中間節點，占用的記憶體為：

  64*6*8 + 64*2*8 = 4K

  （見 2.2.2）

https://www.atatech.org/articles/131386#7 3. 資料存儲相關

https://www.atatech.org/articles/131386#8 3.1 寫 WAL

• 在資料插入時，會先将資料寫入到 WAL(Write Ahead Log) 中；
• 每次寫 WAL 都會傳回一個check point，代表資料在WAL中的寫入位置；
• WAL 寫入成功後，原始資料和 check point 會被寫入時間線的緩沖區；
• 時間線的緩沖與時間線一一對應，最大容納32768個資料點；
• 當緩沖區滿時，資料會被插入到樹結構中，并将該緩沖區對應的 check points 在 WAL 中标記為删除狀态；
• 在 WAL 的 replay 過程中會根據已被删除的 check points 過濾原始資料。

下面的示意圖展示了WAL中 check points 與時間序列緩沖區的關聯關系，在緩沖區清空後，BTrDB 會将已經删除的 check points 寫入到目前 WAL 對應的塊檔案的元資訊（block attributes）中：

當一個 WAL 塊檔案中所有的 check points 都标記為已删除時，該檔案就可以從 Ceph 中删除了。目前 WAL 檔案大小超過16M時就會建立新的塊檔案，在理想情況下，塊檔案都能被及時删除；但是如果某些時間線出現異常，向前文提到的，其緩沖區在 8 小時後才能被回收，那麼負責記錄這些時間線的 WAL 檔案也就隻能在8小時後被回收。

這些滞留的 WAL 檔案大小隻有16M，數量與出現異常的 IoT 裝置數量成線性關系，是以需要更多 IoT 裝置運作統計資料才能統計其影響。

https://www.atatech.org/articles/131386#9 3.2 寫 Block

BTrDB 的樹結構在持久化後會産生兩類資料，一個稱為 superblock，記錄了目前樹的最新版本、更新時間、根節點位置等基本資訊；另外一個稱為 segment，統一包含了樹的葉子節點和中間節點的資料。

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

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

superblock 在 Ceph 中的尋址方式為：

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

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

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

可以看到， WAL 檔案， superblock 塊檔案以及 segment 塊檔案大小都是 16M。另外，BTrDB 中沒有 compaction，也沒有對過期版本資料的清理，隻有上文中介紹的對 WAL 的處理，寫入放大會很明顯。

https://www.atatech.org/articles/131386#10 新的查詢語義

這裡隻是羅列、簡單介紹下 BTrDB 提供的新的查詢語義，這些查詢語義的提出與 BTrDB 的資料結構有很大關系，或者是為了利用樹結構某些特性，或者是為了規避樹結構一些不足：

• GetRange(UUID, StartTime, EndTime, Version) → (Version, [(Time, Value)]) 查詢時間線在某個時間範圍内的詳細（原始）資料；
• GetLatestVersion(UUID) → Version 查詢時間線最新版本；
• GetStatisticalRange(UUID, StartTime, EndTime, Version, Resolution) → (Version, [(Time, Min, Mean, Max, Count)]) 擷取給定時間範圍内，滿足一定時間精度的，大于等于給定版本的時間線的聚合資料；
• GetNearestValue(UUID, Time, Version, Direction) → (Version, (Time, Value)) 向前、向後擷取下一個點；
• ComputeDiff(UUID, FromVersion, ToVersion, Resolution) → [(StartTime, EndTime)] 在滿足給定時間精度條件下，擷取兩個版本号範圍内，所有更新節點的起止時間；适合做增量計算。

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

https://www.atatech.org/articles/131386#11 總結

BTrDB 中資料結構是針對單條時間線建構的，并且針對 IoT 裝置資料穩定的特點，建構了一棵樹來存儲時序資料；樹結構解決了傳統 TSDB 在亂序插入、删除、預降精度等方面面臨的問題。

阿裡雲時序時空資料庫TSDB 1元購！立即體驗：

https://promotion.aliyun.com/ntms/act/tsdbtry.html?spm=5176.149792.775960.1.dd9e34e2zgsuEM&wh_ttid=pc