Overview

前一篇文章深(shen)入了解(jie)Prometheus監控平臺對(dui)prometheus的存儲(chu)結構(gou)做了一下介(jie)紹，在后續的了解(jie)中，發(fa)現(xian)(xian)Prometheus的實現(xian)(xian)上(shang)實際上(shang)參考(kao)了Gorilla。

Gorilla 是Facebook內(nei)(nei)部孵化的(de)一款(kuan)內(nei)(nei)存時(shi)序數(shu)據庫，用(yong)于(yu)存儲(chu)(chu)Facebook內(nei)(nei)部監(jian)控系統的(de)時(shi)序數(shu)據，采用(yong)了比較(jiao)激進(jin)的(de)壓縮方(fang)式(shi)，節省(sheng)大量的(de)存儲(chu)(chu)空間(jian)，同時(shi)基于(yu)內(nei)(nei)存的(de)時(shi)序數(shu)據庫，使得查詢效(xiao)率得到較(jiao)大提高。

Gorilla的具體信(xin)息可以參考Facebook出的官方(fang)論文Gorilla: A Fast, Scalable, In-Memory Time Series Database

這篇(pian)文章主要想(xiang)總結一(yi)下(xia)Gorilla的壓縮算法(fa)。

時序數據的組成

對于Gorilla而言，每一個(ge)時(shi)序數據由(you)一個(ge)三元組組成(這點(dian)和(he)prometheus一致)

• key: string類型，參考prometheus的series名
• timestamp:時間戳，64bit
• value:float64類型，時序數據的值

Gorilla集qun由多(duo)個(ge)shard(實例)構成，時序存在哪一個(ge)shard上(shang)是對key進行(xing)計算(suan)得(de)到(dao)，擴容時只需要修(xiu)改分片函數，使(shi)得(de)時序能(neng)夠分配到(dao)新shard上(shang)即可。

Gorilla的(de)壓(ya)縮(suo)算法使(shi)得壓(ya)縮(suo)效(xiao)率從沒有壓(ya)縮(suo)的(de)16bytes/sample壓(ya)到了1.37bytes/samples。大概的(de)壓(ya)縮(suo)流程(cheng)如下圖所示。 

該壓(ya)縮(suo)算法(fa)對時(shi)間戳和(he)時(shi)序值采用了(le)不(bu)同壓(ya)縮(suo)方式，將(jiang)在下文具體介紹。

delta of delta -- 時間戳壓縮方式

Gorilla對時間戳采(cai)用的(de)是(shi)delta of delta的(de)壓縮方式(shi)，感覺和信號(hao)/圖形(xing)處理領域的(de)差分編碼思想上類似。

對于(yu)一個監(jian)控系統而言，我(wo)們(men)的(de)(de)采樣(yang)間(jian)隔總是固定的(de)(de)，因此采樣(yang)的(de)(de)時間(jian)戳是很有(you)規(gui)律的(de)(de)，比如第0s，第15s,第30s,第45s,只(zhi)有(you)少量的(de)(de)特(te)殊情(qing)況會有(you)較小的(de)(de)誤(wu)差。

因此，如果(guo)我們存(cun)儲(chu)(chu)的數(shu)據是(shi)和(he)前一個時(shi)間的差值，那么我們就只(zhi)需(xu)(xu)要存(cun)第(di)一個完整的時(shi)間戳，后續(xu)的時(shi)間只(zhi)需(xu)(xu)存(cun)和(he)前一個的差值，即15，15，15，15，如果(guo)有部分誤差的時(shi)間戳，則(ze)可能存(cun)的是(shi)16/14。這樣(yang)就可以減少用于(yu)存(cun)儲(chu)(chu)的bit。

再(zai)更進一步壓(ya)縮，我們可(ke)以存儲時(shi)(shi)間(jian)(jian)(jian)(jian)差(cha)(cha)的差(cha)(cha)值(zhi)，第(di)一個(ge)時(shi)(shi)間(jian)(jian)(jian)(jian)戳(chuo)是(shi)(shi)(shi)0，第(di)二(er)個(ge)時(shi)(shi)間(jian)(jian)(jian)(jian)戳(chuo)和第(di)一個(ge)時(shi)(shi)間(jian)(jian)(jian)(jian)戳(chuo)的差(cha)(cha)值(zhi)是(shi)(shi)(shi)15，第(di)三個(ge)時(shi)(shi)間(jian)(jian)(jian)(jian)戳(chuo)和第(di)二(er)個(ge)時(shi)(shi)間(jian)(jian)(jian)(jian)的差(cha)(cha)值(zhi) 減去(qu)第(di)二(er)個(ge)時(shi)(shi)間(jian)(jian)(jian)(jian)戳(chuo)和第(di)一個(ge)時(shi)(shi)間(jian)(jian)(jian)(jian)戳(chuo)的差(cha)(cha)值(zhi) 是(shi)(shi)(shi)0，因(yin)此我們存儲的數(shu)據就是(shi)(shi)(shi)0，15，0，0。如果有(you)部(bu)分誤差(cha)(cha)的時(shi)(shi)間(jian)(jian)(jian)(jian)戳(chuo)，那么(me)0可(ke)能就是(shi)(shi)(shi)1/2/-1/-2。可(ke)以看(kan)出(chu)，所需要(yao)的bit數(shu)大幅地下降。

Gorilla采用的就是后面說(shuo)的這種壓縮(suo)方(fang)式(delta of delta)

每一個時間窗口(2小時)的數據會存放在一個block當中，block header會存放這個時間窗口的開始時間(t−1t_{-1}t−1?),需要64bit

第一個時序數據會存儲數據采樣時間和起始時間的差值(t0t_0t0?),需(xu)要14bit，這個14bit足夠存2個小時(shi)的差(cha)值了。

然后，對于后續的每一個(ge)時間戳(chuo)，采用下圖(a)的公式計算delta of delta的值

• 如果是0，則只需要存0這一個bit
• 如果大小在-63到64區間，則加上前綴10進行存儲，一共存儲2+7個bit
• 如果在-255到256區間，則加上前綴110進行存儲，一共存儲3+9個bit
• 如果在-2047到2048區間，則加上前綴1110進行存儲，一共存儲4+12bit
• 更大的話，則加上前綴1111，再加上實際的差值，一共32bit

對(dui)于(yu)這個區間(jian)的(de)(de)選擇，應該是facebook通過具(ju)體數據的(de)(de)分析(xi)得(de)到的(de)(de)。

從論文(wen)的(de)圖中可以(yi)看到，絕大部分的(de)時(shi)間戳，其實用1個bit(0)存儲就夠了，需要用32位來(lai)存儲的(de)是極少(shao)數。

現在再回頭(tou)看(kan)這個(ge)圖，就可以(yi)知道他的時間是怎么算出來的了(le)

t2t_2t2?和t1t_1t1?的差值是60，而前(qian)一個(ge)時間點的delta是62,計算出來的D=-2，在-63到(dao)64區間，所以需要加上10前(qian)綴，在用(yong)7bit存儲-2

t3t_3t3?的delta和t2t_2t2?一樣，所(suo)以直(zhi)接存0，只用1bit

XOR -- 值壓縮方式

Gorilla的值(zhi)類型(xing)是float64雙精度(du)類型(xing)，對其(qi)進行(xing)壓(ya)縮的方式則是將值(zhi)和前一個值(zhi)進行(xing)XOR異或

雙(shuang)精(jing)度浮點數(shu)的結構如上圖，1位的符(fu)號位，11位的指數(shu)位，，和52位的小數(shu)位

對于(yu)監控(kong)系統而言(yan)，每隔固定的(de)時間進(jin)行采樣，其實(shi)數據(ju)量(liang)并不會有太大(da)變化，對于(yu)平穩運行的(de)的(de)系統，不可(ke)能會cpu突然暴漲，內存突然暴漲。所(suo)以存儲的(de)值其實(shi)有很多位是(shi)一樣的(de)。

Gorilla利用這個特性(xing)，利用異或(huo)對數據進(jin)行(xing)壓縮。

壓縮的思路大致如下：

• block的第(di)一個(ge)數不壓縮存儲

• 后續的(de)每個值和前一(yi)個值做XOR異(yi)或

• 如果結果為0，則(ze)只存儲一(yi)位0

• 如(ru)果結(jie)果不為0，那么會有兩種情況

  • 如果異或的結果和前一個數異或的結果，他們的前導0和后導0數量一樣，那么存儲前綴10加有效位的數據
  • 如果前導0和后導0數量不一致，那么就存前綴11+ 5位的前導0數量 +6位的有效位數量(實際上就是存了后導0數量) +有效位數據

論文(wen)中(zhong)也給出了一些(xie)實例

 對于(yu)絕大部分(fen)的(de)(de)數(shu)據，是可(ke)以共(gong)享前導0和后(hou)導0的(de)(de)，因此需要用于(yu)存儲的(de)(de)bit是較(jiao)少的(de)(de)。

分(fen)布情況 

同樣的，再看這張圖，可以知道第二個數據24的XOR結果(0)和前一個時序數據的XOR結果沒有共享前后導0，因此需要存前綴11，然后數據0x001有11個前導0，有效為長度位(wei)1，有效位(wei)數據(ju)是(shi)1，最后(hou)存儲(chu)的(de)結果就如圖所示。

通過上面的(de)(de)(de)壓縮(suo)(suo)分析，其實(shi)如果一個block的(de)(de)(de)時(shi)(shi)間窗(chuang)口(kou)越(yue)長(chang)，壓縮(suo)(suo)效率會(hui)越(yue)高。但同時(shi)(shi)，解壓縮(suo)(suo)的(de)(de)(de)成本的(de)(de)(de)會(hui)相應提高，Facebook的(de)(de)(de)論文給出的(de)(de)(de)一個最合適的(de)(de)(de)時(shi)(shi)間窗(chuang)口(kou)為2小(xiao)時(shi)(shi)，prometheus采用的(de)(de)(de)也是這個值。

Gorilla內存中的數據結構

Gorilla的(de)實現用的(de)是C++，他存(cun)儲的(de)數據結構大致如下(xia)圖所示

• shardMap是分片的map，ShardMap用一個數組vector來存儲TSmap的指針（unique_ptr)，查詢時，通過key計算出時序在哪個分片shard上，然后快速查找到對應的TsMap上。
• TSmap即Timeseries Map，由一個vector和map組成，均作為時序數據的索引使用。vector的元素指向對應時間序列的智能指針(shared_ptr)；map以時間序列的名稱作為key（大小寫不敏感但是保留大小寫），指向時間序列的智能指針作為value。vector可以提供較好的范圍查詢能力，map提供較好的點查詢能力。
• TS為真正存儲數據的塊，包含一個打開的block，用于寫入新數據。和多個關閉的塊，存儲舊數據。每個塊存儲2個小時的數據

ps.TsMap對每個(ge)分(fen)片(pian)維(wei)護(hu)一個(ge)分(fen)片(pian)的讀寫鎖(suo)，減小(xiao)鎖(suo)的粒度，不(bu)用(yong)鎖(suo)全部數據。

與Gorilla不(bu)同，Gorilla 的解碼(ma)放在客戶端，而promethus的解碼(ma)在服務(wu)端完成(cheng)。

高可用

facebook在(zai)論文中提(ti)到(dao)，Gorilla通過將(jiang)數據寫到(dao)兩個(ge)(ge)不(bu)同(tong)地區的(de)集qun中，一(yi)(yi)個(ge)(ge)壞了(le)會切(qie)換到(dao)另一(yi)(yi)個(ge)(ge)；

Gorrila在不(bu)同(tong)的數據中心(xin)維護兩個完全一(yi)樣但(dan)不(bu)考慮一(yi)致(zhi)性的實例級(ji)別的數據副(fu)本(ben)，以實現數據中心(xin)故障(zhang)或分區的情況下的高可用。

對(dui)于這點，prometheus感覺也是采樣的相似的思路。