時(shí)序數(shù)據(jù)庫連載系列：Berkeley 的黑科技 BTrDB
來源：焦先 發(fā)布時(shí)間：2019-02-23 16:56:33 閱讀量：1269
本文是對(duì)面向 IoT 領(lǐng)域的開源時(shí)序數(shù)據(jù)庫 BTrDB 內(nèi)部實(shí)現(xiàn)細(xì)節(jié)的研究和介紹。
1. 場景介紹
BTrDB 論文中介紹了一個(gè)實(shí)際的項(xiàng)目，能很好解釋清楚 BTrDB 的設(shè)計(jì)初衷和適用場景：
在一個(gè)電網(wǎng)中大量部署了某類傳感器，每個(gè)傳感器會(huì)產(chǎn)生 12 條時(shí)間線，每條時(shí)間線頻率為 120Hz（即每秒 120 個(gè)點(diǎn)），時(shí)間精度為 100ns；由于各種原因，傳感器數(shù)據(jù)傳輸經(jīng)常性出現(xiàn)延遲、（時(shí)間）亂序等。BTrDB 在該場景下單機(jī)能支撐 1000 個(gè)類似的傳感器，寫入速率約 1.44M points/s。
該項(xiàng)目有這樣幾個(gè)特點(diǎn)：
1. 時(shí)間線在很長時(shí)間內(nèi)有一定的不變性，其生命周期跟(IoT)設(shè)備周期一致
2. 數(shù)據(jù)頻率很高（120 Hz）且固定
3. 數(shù)據(jù)的時(shí)間分辨率很高（100ns級(jí)別），一般如Druid，TimescaleDB 時(shí)間精度最多做到 ms 級(jí)別
4. 數(shù)據(jù)傳輸經(jīng)常性出現(xiàn)亂序
5. 時(shí)間線數(shù)量有限
BTrDB 為了適應(yīng)上述場景，設(shè)計(jì)并提出了 "time-partitioning version-annotated copy-on-write tree" 的數(shù)據(jù)結(jié)構(gòu)，為每一條時(shí)間線構(gòu)建了一棵樹（可以參考B+Tree），數(shù)據(jù)在該樹中按照時(shí)間戳排序，葉子節(jié)點(diǎn)有序得存放某個(gè)時(shí)間段內(nèi)的時(shí)序數(shù)據(jù)。
可以想見，這棵樹的生命周期跟設(shè)備的生命周期直接掛鉤，因此隨著時(shí)間的發(fā)展，這棵樹即使只包含一條時(shí)間線，也會(huì)占用很可觀的存儲(chǔ)空間（約 10M points/day）；另外由于是基于樹結(jié)構(gòu)，并且引入了版本（version-annotated) 的概念，BTrDB 可以很好的支持亂序數(shù)據(jù)和任意精度的時(shí)序數(shù)據(jù)。
由于數(shù)據(jù)結(jié)構(gòu)不同于以往時(shí)序數(shù)據(jù)庫基于LSM-Tree的變種，因此 BTrDB 還提供了一套新的時(shí)序數(shù)據(jù)查詢接口，方便在 BTrDB 上層構(gòu)建各種算法和應(yīng)用。
2. 數(shù)據(jù)結(jié)構(gòu)
2.1 version-annotated & CoW 特性
在數(shù)據(jù)寫入時(shí)，BTrDB 會(huì)先修改在內(nèi)存中的數(shù)據(jù)塊（新建或者使用 CoW 機(jī)制修改已有塊），當(dāng)數(shù)據(jù)達(dá)到一定閾值時(shí)再寫回底層塊存儲(chǔ)；由于 CoW 機(jī)制，并且底層塊存儲(chǔ)（默認(rèn)使用Ceph）無法覆蓋更新，因此只能創(chuàng)建一個(gè)新版本的數(shù)據(jù)塊。
2.2. 葉子節(jié)點(diǎn)
對(duì)于 IoT 設(shè)備發(fā)來的數(shù)據(jù)，由于頻率固定，這些葉子節(jié)點(diǎn)占用空間大小基本一致。
葉子節(jié)點(diǎn)還未持久化到底層存儲(chǔ)時(shí)，在內(nèi)存中通過數(shù)組的方式分別存放時(shí)間戳和（雙精度浮點(diǎn)）值；在序列化到底層存儲(chǔ)時(shí)，會(huì)通過delta-delta的方式壓縮時(shí)間戳和值；在序列化雙精度浮點(diǎn)數(shù)值之前，會(huì)將浮點(diǎn)數(shù)據(jù)數(shù)拆分為尾數(shù)和指數(shù)兩部分，并分別進(jìn)行delta-delta壓縮。
2.3. 中間節(jié)點(diǎn):
中間節(jié)點(diǎn)被劃分為多個(gè) bucket，每個(gè) bucket 中存放著指向子節(jié)點(diǎn)的鏈接（帶版本號(hào)）以及子節(jié)點(diǎn)的統(tǒng)計(jì)數(shù)據(jù)：
子節(jié)點(diǎn)的時(shí)間范圍
聚合數(shù)據(jù)，如 sum, max, min，count 等
子節(jié)點(diǎn)連接地址和版本號(hào)
在處理查詢時(shí)，如果中間節(jié)點(diǎn)的時(shí)間精度滿足查詢需求，查詢操作就不再讀取下層子節(jié)點(diǎn)了，這樣就很自然的實(shí)現(xiàn)了將精度功能；這種實(shí)現(xiàn)方式，能夠很好的處理亂序、重復(fù)數(shù)據(jù)以及刪除操作，并且與其他現(xiàn)有的實(shí)現(xiàn)相比，能夠很好的保證數(shù)據(jù)的一致性。
2.4. 插入時(shí)樹的分裂
一棵新的樹（對(duì)應(yīng)一條新的時(shí)間線）只有一個(gè)根節(jié)點(diǎn)，在 BTrDB 的實(shí)現(xiàn)中，根節(jié)點(diǎn)時(shí)間跨度約為146.23年，這樣每個(gè) bucket 的時(shí)間跨度為 146.23/64 ~= 2.28 （年），根據(jù)默認(rèn)配置，1970年在根節(jié)點(diǎn)的第16個(gè) bucket。
可見，根節(jié)點(diǎn)在創(chuàng)建時(shí)就已經(jīng)限制了數(shù)據(jù)的時(shí)間范圍，后續(xù)數(shù)據(jù)的插入是自頂向下逐層分裂的，當(dāng)數(shù)據(jù)因?yàn)閬G失等原因造成時(shí)間線不完整時(shí)，部分節(jié)點(diǎn)的深度可能會(huì)不一樣，因此并不是一顆嚴(yán)格的平衡樹。數(shù)據(jù)插入過程如下：
數(shù)據(jù)插入操作從根節(jié)點(diǎn)開始；
如果當(dāng)前節(jié)點(diǎn)是中間節(jié)點(diǎn)，則遍歷每個(gè)數(shù)據(jù)，為每個(gè)數(shù)據(jù)找到對(duì)應(yīng)的 bucket；
如果對(duì)應(yīng)的 bucket 不存在，則創(chuàng)建新的 bucket 和與該 bucket 關(guān)聯(lián)的子節(jié)點(diǎn)：
如果當(dāng)前 bucket 待插入的點(diǎn)個(gè)數(shù)超過葉子節(jié)點(diǎn)最大點(diǎn)數(shù)（默認(rèn)1024），則直接創(chuàng)建中間子節(jié)點(diǎn)；
否則，創(chuàng)建葉子節(jié)點(diǎn)；
將數(shù)據(jù)插入到與所屬 bucket 關(guān)聯(lián)的子節(jié)點(diǎn)中；
如果當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)，節(jié)點(diǎn)中數(shù)據(jù)個(gè)數(shù)和待插入數(shù)據(jù)個(gè)數(shù)總合超過 1024 個(gè)點(diǎn)，則分裂當(dāng)前節(jié)點(diǎn)創(chuàng)建出新的中間節(jié)點(diǎn)，將數(shù)據(jù)插入新的中間節(jié)點(diǎn)；否則將待插入數(shù)據(jù)和當(dāng)前節(jié)點(diǎn)已有數(shù)據(jù)合并，并按照時(shí)間戳排序；
當(dāng)前節(jié)點(diǎn)插入成功后，自底向上更新父節(jié)點(diǎn)的統(tǒng)計(jì)信息；
從上面過程可以看到，節(jié)點(diǎn)在插入時(shí)在兩個(gè)地方可能出現(xiàn)分裂。一個(gè)是從根節(jié)點(diǎn)開始，自頂向下分裂；另一個(gè)是從葉子節(jié)點(diǎn)開始，向上分裂。
雖然這棵樹并不是一顆平衡樹，但是對(duì)于 IoT 類項(xiàng)目，設(shè)備的時(shí)間線生命周期、數(shù)據(jù)采集頻率很穩(wěn)定，在絕大多數(shù)場景下，節(jié)點(diǎn)中數(shù)據(jù)都是均衡分布的。
2.5 節(jié)點(diǎn)占用的內(nèi)存空間
在默認(rèn)實(shí)現(xiàn)中，葉子節(jié)點(diǎn)中最多存儲(chǔ)1024個(gè)數(shù)據(jù)點(diǎn)；中間節(jié)點(diǎn)中最多存儲(chǔ)64個(gè)子節(jié)點(diǎn)指針，因此：
對(duì)于還未持久化的葉子節(jié)點(diǎn)，占用的內(nèi)存空間為：
1024*2*8 = 16K（見 2.2.1）對(duì)于還未持久化的中間節(jié)點(diǎn)，占用的內(nèi)存為：
64*6*8 + 64*2*8 = 4K（見 2.2.2）
3. 數(shù)據(jù)存儲(chǔ)相關(guān)
3.1 寫 WAL
在數(shù)據(jù)插入時(shí)，會(huì)先將數(shù)據(jù)寫入到 WAL(Write Ahead Log) 中；
每次寫 WAL 都會(huì)返回一個(gè)check point，代表數(shù)據(jù)在WAL中的寫入位置；
WAL 寫入成功后，原始數(shù)據(jù)和 check point 會(huì)被寫入時(shí)間線的緩沖區(qū)；
時(shí)間線的緩沖與時(shí)間線一一對(duì)應(yīng)，最大容納32768個(gè)數(shù)據(jù)點(diǎn)；
當(dāng)緩沖區(qū)滿時(shí)，數(shù)據(jù)會(huì)被插入到樹結(jié)構(gòu)中，并將該緩沖區(qū)對(duì)應(yīng)的 check points 在 WAL 中標(biāo)記為刪除狀態(tài)；
在 WAL 的 replay 過程中會(huì)根據(jù)已被刪除的 check points 過濾原始數(shù)據(jù)。
下面的示意圖展示了WAL中 check points 與時(shí)間序列緩沖區(qū)的關(guān)聯(lián)關(guān)系，在緩沖區(qū)清空后，BTrDB 會(huì)將已經(jīng)刪除的 check points 寫入到當(dāng)前 WAL 對(duì)應(yīng)的塊文件的元信息（block attributes）中：
當(dāng)一個(gè) WAL 塊文件中所有的 check points 都標(biāo)記為已刪除時(shí)，該文件就可以從 Ceph 中刪除了。當(dāng)前 WAL 文件大小超過16M時(shí)就會(huì)創(chuàng)建新的塊文件，在理想情況下，塊文件都能被及時(shí)刪除；但是如果某些時(shí)間線出現(xiàn)異常，向前文提到的，其緩沖區(qū)在 8 小時(shí)后才能被回收，那么負(fù)責(zé)記錄這些時(shí)間線的 WAL 文件也就只能在8小時(shí)后被回收。
這些滯留的 WAL 文件大小只有16M，數(shù)量與出現(xiàn)異常的 IoT 設(shè)備數(shù)量成線性關(guān)系，因此需要更多 IoT 設(shè)備運(yùn)行統(tǒng)計(jì)數(shù)據(jù)才能統(tǒng)計(jì)其影響。
3.2 寫 Block
BTrDB 的樹結(jié)構(gòu)在持久化后會(huì)產(chǎn)生兩類數(shù)據(jù)，一個(gè)稱為 superblock，記錄了當(dāng)前樹的最新版本、更新時(shí)間、根節(jié)點(diǎn)位置等基本信息；另外一個(gè)稱為 segment，統(tǒng)一包含了樹的葉子節(jié)點(diǎn)和中間節(jié)點(diǎn)的數(shù)據(jù)。
superblock 是帶版本的，每個(gè)版本的 superblock 只占用16Byte，格式為：
{root: 根節(jié)點(diǎn)位置，8Byte, timestamp: 修改時(shí)間，8Byte}superblock 在 Ceph 中的尋址方式為：
塊存儲(chǔ) id = uuid.toString() + (version >> 20)
塊存儲(chǔ)中的 offset = (version & 0xFFFFF)*16
在 BTrDB 中持久化樹結(jié)構(gòu)時(shí)葉子節(jié)點(diǎn)和中間節(jié)點(diǎn)會(huì)一并序列化到 segment 中，每個(gè)節(jié)點(diǎn)的尋址編碼方式為：
塊存儲(chǔ)的 id = uuid.toString() + (address >> 24)
節(jié)點(diǎn)在塊存儲(chǔ)中的偏移量 = (address & 0xFFFFFF)可以看到， WAL 文件， superblock 塊文件以及 segment 塊文件大小都是 16M。另外，BTrDB 中沒有 compaction，也沒有對(duì)過期版本數(shù)據(jù)的清理，只有上文中介紹的對(duì) WAL 的處理，寫入放大會(huì)很明顯。
新的查詢語義
這里只是羅列、簡單介紹下 BTrDB 提供的新的查詢語義，這些查詢語義的提出與 BTrDB 的數(shù)據(jù)結(jié)構(gòu)有很大關(guān)系，或者是為了利用樹結(jié)構(gòu)某些特性，或者是為了規(guī)避樹結(jié)構(gòu)一些不足：
GetRange(UUID, StartTime, EndTime, Version) → (Version, [(Time, Value)]) 查詢時(shí)間線在某個(gè)時(shí)間范圍內(nèi)的詳細(xì)（原始）數(shù)據(jù)；
GetLatestVersion(UUID) → Version 查詢時(shí)間線最新版本；
GetStatisticalRange(UUID, StartTime, EndTime, Version, Resolution) → (Version, [(Time, Min, Mean, Max, Count)]) 獲取給定時(shí)間范圍內(nèi)，滿足一定時(shí)間精度的，大于等于給定版本的時(shí)間線的聚合數(shù)據(jù)；
GetNearestValue(UUID, Time, Version, Direction) → (Version, (Time, Value)) 向前、向后獲取下一個(gè)點(diǎn)；
ComputeDiff(UUID, FromVersion, ToVersion, Resolution) → [(StartTime, EndTime)] 在滿足給定時(shí)間精度條件下，獲取兩個(gè)版本號(hào)范圍內(nèi)，所有更新節(jié)點(diǎn)的起止時(shí)間；適合做增量計(jì)算。
上面接口中的時(shí)間分辨率參數(shù)（Resolution），對(duì)于接口的性能有很大影響。前文提到根節(jié)點(diǎn)的時(shí)間分辨率是2.2年，從樹的根節(jié)點(diǎn)到底層節(jié)點(diǎn)，節(jié)點(diǎn)中數(shù)據(jù)的時(shí)間分辨率越來越高；在查詢時(shí)，低分辨率數(shù)據(jù)聚合程度高，掃面的數(shù)據(jù)塊少；高分辨率的數(shù)據(jù)聚合程度低，但是需要掃面的數(shù)據(jù)塊很多。
總結(jié)
BTrDB 中數(shù)據(jù)結(jié)構(gòu)是針對(duì)單條時(shí)間線構(gòu)建的，并且針對(duì) IoT 設(shè)備數(shù)據(jù)穩(wěn)定的特點(diǎn)，構(gòu)建了一棵樹來存儲(chǔ)時(shí)序數(shù)據(jù)；樹結(jié)構(gòu)解決了傳統(tǒng) TSDB 在亂序插入、刪除、預(yù)降精度等方面面臨的問題。
13450931319
微信登錄
QQ登錄
微博登錄
售前咨詢
