InfluxDB引擎原理

引言

InfluxDB是一款Go語(yǔ)言寫(xiě)的時(shí)序數(shù)據(jù)庫(kù)。時(shí)序數(shù)據(jù)庫(kù)主要用于存儲(chǔ)基于時(shí)間序列的指標(biāo)數(shù)據(jù)，例如一個(gè)Web頁(yè)面的PV、UV等指標(biāo)，將其定期采集，并打上時(shí)間戳，就是一份基于時(shí)間序列的指標(biāo)。時(shí)序數(shù)據(jù)庫(kù)通常用來(lái)配合前端頁(yè)面來(lái)展示一段時(shí)間的指標(biāo)曲線(xiàn)。

為什么需要時(shí)序數(shù)據(jù)庫(kù)

時(shí)序數(shù)據(jù)庫(kù)較傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)以及NoSQL究竟有什么優(yōu)勢(shì)，下面會(huì)結(jié)合相關(guān)模型的特性進(jìn)行分析

LSM Tree

LSM tree是基于Google的BigTable架構(gòu)，數(shù)據(jù)以K-V方式存儲(chǔ)。

寫(xiě)數(shù)據(jù)首先會(huì)插入到內(nèi)存中的樹(shù)。當(dāng)內(nèi)存中的樹(shù)中的數(shù)據(jù)超過(guò)一定閾值時(shí)，會(huì)進(jìn)行合并操作。合并操作會(huì)從左至右遍歷內(nèi)存中的樹(shù)的葉子節(jié)點(diǎn)與磁盤(pán)中的樹(shù)的葉子節(jié)點(diǎn)進(jìn)行合并，當(dāng)被合并的數(shù)據(jù)量達(dá)到磁盤(pán)的存儲(chǔ)頁(yè)的大小時(shí)，會(huì)將合并后的數(shù)據(jù)持久化到磁盤(pán)，同時(shí)更新父親節(jié)點(diǎn)對(duì)葉子節(jié)點(diǎn)的指針。

這種機(jī)制保證了寫(xiě)入的效率，因?yàn)閿?shù)據(jù)會(huì)在合并后順序?qū)懭氪疟P(pán)頁(yè)。但會(huì)推遲磁盤(pán)回寫(xiě)，因此為保障讀數(shù)據(jù)的一致性，會(huì)先在內(nèi)存中查詢(xún)，如果內(nèi)存中沒(méi)有，則到磁盤(pán)上查詢(xún)。

刪除數(shù)據(jù)時(shí)，在內(nèi)存（C0）中查找，如果沒(méi)有，則在內(nèi)存中新建一個(gè)索引，將鍵值設(shè)置刪除標(biāo)記（創(chuàng)建墓碑），這樣后續(xù)的滾動(dòng)合并操作時(shí)，再有查詢(xún)操作，就會(huì)被直接返回該鍵值不存在。 數(shù)據(jù)會(huì)在之后的Compaction當(dāng)中從數(shù)據(jù)文件中刪除。

Compaction

當(dāng)日志文件超過(guò)一定大小的閾值是 (默認(rèn)為 1MB):

建立一個(gè)新的memtable和日志文件，以后的操作都是用新的memtable和日志文件

后臺(tái)進(jìn)行如下操作:

1. 將舊的 memtable寫(xiě)到SSTable中（過(guò)程為先轉(zhuǎn)為immtable_table，然后遍歷寫(xiě)入)

2. 廢棄舊的 memtable

3. 刪除舊的 memtable和日志文件

4. 將新的SSTable加到level 0中.

對(duì)于時(shí)序數(shù)據(jù)而言，LSM tree的讀寫(xiě)效率很高。但是熱備份以及數(shù)據(jù)批量清理的效率不高。

B+ Tree

B+ Tree，很多關(guān)系型數(shù)據(jù)庫(kù)像 Berkerly DB , sqlite , mysql 數(shù)據(jù)庫(kù)都使用了B+樹(shù)算法處理索引。B+ Tree的特點(diǎn)是數(shù)據(jù)按照索引有序排放，犧牲一定寫(xiě)入性能，保證了讀取效率。但數(shù)據(jù)量很大時(shí)（GB），查詢(xún)效率就會(huì)很低。因?yàn)閿?shù)據(jù)量越大，樹(shù)分叉就越多，遍歷時(shí)的開(kāi)銷(xiāo)就越大。

TSM

influxdb在v0.9.5版本引入TSM引擎，該引擎修改自L(fǎng)SM

預(yù)寫(xiě)日志

當(dāng)前日志文件達(dá)到2MB大小后封閉，并開(kāi)始寫(xiě)新的日志文件

寫(xiě)數(shù)據(jù)時(shí)，日志文件落盤(pán)(fsync)且數(shù)據(jù)索引加入內(nèi)存表后返回成功。這樣的設(shè)計(jì)保證了數(shù)據(jù)的一致性。同時(shí)對(duì)寫(xiě)盤(pán)的吞吐性能提出要求，建議批量提交數(shù)據(jù)（influxdb提供了批量提交的API）。日志遵循TLV格式，并采用較精簡(jiǎn)的數(shù)據(jù)結(jié)構(gòu)，來(lái)減少寫(xiě)操作的開(kāi)銷(xiāo)。

數(shù)據(jù)文件

文件結(jié)構(gòu)
一個(gè)文件的中數(shù)據(jù)塊按照時(shí)序進(jìn)行排列

對(duì)照LevelDB的結(jié)構(gòu)，增加了min和max time, 基于一段時(shí)間范圍的數(shù)據(jù)提取會(huì)非常簡(jiǎn)單

Data Block結(jié)構(gòu)
ID由存放的key (measurement name + tagset) 以及 field name進(jìn)行hash(fnv64-a hash)生成
Compressd block當(dāng)中會(huì)存儲(chǔ)metric值，數(shù)據(jù)壓縮算法后面會(huì)進(jìn)行詳述

Index Block結(jié)構(gòu)

讀取數(shù)據(jù)

首先會(huì)根據(jù)查詢(xún)請(qǐng)求的時(shí)間范圍，在數(shù)據(jù)文件中進(jìn)行二進(jìn)制搜索，找到符合范圍的文件。之后在內(nèi)存中的映射表根據(jù)查詢(xún)指標(biāo)項(xiàng)HASH獲取ID，并通過(guò)索引找到數(shù)據(jù)塊的起始地址。之后根據(jù)數(shù)據(jù)塊及其下一數(shù)據(jù)塊的timestamp我們可以推算出需要取出多少個(gè)數(shù)據(jù)塊，最后將數(shù)據(jù)塊中的數(shù)據(jù)解壓，得到結(jié)果

更新數(shù)據(jù)

如果多個(gè)更新在同一個(gè)時(shí)間范圍內(nèi)，預(yù)寫(xiě)日志會(huì)緩存起來(lái)一起更新。

刪除數(shù)據(jù)

兩階段式處理，第一階段，預(yù)寫(xiě)日志會(huì)將其持久化在日志中，并通知索引維護(hù)內(nèi)存中的墓碑. 此時(shí)查詢(xún)數(shù)據(jù)，就會(huì)返回不存在。第二階段，預(yù)寫(xiě)日志寫(xiě)索引文件，會(huì)優(yōu)先處理刪除，之后再處理刪除操作之后的其他插入(包括刪除的序列以及其他序列)，并清除內(nèi)存中的墓碑。

數(shù)據(jù)壓縮

數(shù)據(jù)壓縮的目的是為了減少存儲(chǔ)空間以及降低寫(xiě)磁盤(pán)的開(kāi)銷(xiāo)
每個(gè)壓縮數(shù)據(jù)塊當(dāng)中會(huì)包含一個(gè)系列的點(diǎn)（壓縮時(shí)間戳、壓縮值), 因?yàn)闀r(shí)間戳是一個(gè)單調(diào)遞增的序列，因此壓縮時(shí)填入的時(shí)間的偏移量

總結(jié)

influxdb的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)了數(shù)據(jù)基于系列以及時(shí)間戳2個(gè)維度的有序存取。并通過(guò)壓縮數(shù)據(jù)來(lái)降低I/O開(kāi)銷(xiāo)。在取一個(gè)系列在一定時(shí)間范圍內(nèi)的數(shù)據(jù)這個(gè)場(chǎng)景下，能夠提高處理速度。 由于數(shù)據(jù)按時(shí)間進(jìn)行歸并，對(duì)Retention操作而言，可以以數(shù)據(jù)文件為單位進(jìn)行操作，效率會(huì)比較高。