Facebook的時序數據庫技術(上)

聲明：此文核心內容源自Facebook在2015年發表的論文《Gorilla: A Fast, Scalable, In-Memory Time Series DataBase》, 但本文大部分內容為筆者在精讀論文以后做的總結，內容組織形式也有較大的出入。本文所有的圖片均源自該論文。

基本概念

以監控數據為例，介紹時序數據庫的兩個重要概念“Time Series”與“Data Point”：

Time Series

一個數據源的一個指標，按固定時間間隔產生的源源不斷的監控數據，稱之為Time Series，中文通常將其翻譯成”時間線”。”按固定時間間隔”是一種理想假設，會存在少量的異常情形。

例如： 我們希望收集每一臺物理機上的CPU使用率信息，物理機Host A上的CPU 1，就是一個確定的數據源，而CPU使用率就是指標信息，假設我們收集指標的時間間隔為5秒鐘，那么，Host A上CPU 1上按5秒鐘間隔產生的所有指標數據，就稱之為一個Time Series，而物理機Host A上的CPU 2的CPU使用率信息則屬于另外一個獨立的Time Series。從這個定義上來看，一個Time Series本身是無時間邊界的，只能說，在某一個時刻，最老的與最新的指標數據是什么。

Data Point

Time Series中按固定時間間隔產生的每一條監控數據，稱之為一個Data Point。即，Data Point是構成Time Series的基本數據單元。繼續上面的例子，Host A的CPU 1的每一條CPU使用率信息，就是一個Data Point。

一個Data Point中至少包含兩個關鍵組成部分：Timestamp信息，Point Value信息（具體的指標值）。

正文內容

對于一個數據庫系統而言，保障用戶數據不丟失通常是設計的第一要則，而數據可靠性的提升往往是以犧牲系統吞吐量為代價的。

今天，我們要談論的，就是一款在故障場景下允許丟失少量數據的時序數據庫技術，即Facebook的Gorilla。

Facebook在2015年發表的一篇論文詳細介紹了Gorilla的技術細節，這篇論文名為《Gorilla: A Fast, Scalable, In-Memory Time Series DataBase》，此文正是對這篇論文的詳細解讀。Gorilla的部分設計思路非常值得借鑒，而且已被應用于其它的時序數據庫技術中。

Gorilla源自Facebook對于內部基礎設施的近乎”變態”的監控需求，我們先來看看這些數據：

20億個不同的Time Series

每分鐘產生7億個Data Points，即每秒鐘產生1200萬個Data Points

數據需要存儲26個小時

高峰期的查詢高達40000次每秒

查詢時延需要小于1ms

每個 Time Series每分鐘可產生4個Data Points

每年的數據增長率為200%

對于監控數據，本身還具有如下幾個典型特點：

重寫輕讀

以聚合分析為主，幾乎不存在針對單Data Point的點查場景。因此，即使丟失個別的Data Points，一般不會影響到整體的分析結果。

越老的數據價值越低，而應用通常只讀取最近發生的數據。Facebook的統計表明，85%的查詢與最近26個小時的數據寫入有關。

Facebook的監控系統主要依賴于ODS(Operational Data Store)，它提供了基礎的TSDB能力，查詢服務，問題發現與告警系統。在Gorilla之前，ODS完全基于HBase構建，Time Series數據由ODS Write Service收集后寫到HBase中。但直接基于HBase的讀取，P90時延過高，應用不得不在查詢場景上做一些舍棄。如果在ODS中添加一層Read-Through Cache，當Cache未命中時直接讀取HBase代價依然是過高的。在Gorilla之前，Facebook也考慮過基于Memcached作為Write-Through Cache的方案，但新增Data Point需要先讀取已有的Time Series，更新后再寫回到Memcached，這會導致Memcached的負載過重。

Write-Through Cache與Read-Through Cache

Write-Through Cache: 新數據寫入到Cache的同時也寫入到后端持久化存儲系統中。

Read-Through Cache: 讀取時先讀取Cache，如果Cache中不存在，則觸發一次后端持久化存儲系統的讀取操作，從而將數據加載到Cache中，而后返回給客戶端。

現有的其它時序數據庫技術，典型如OpenTSDB，InfluxDB，都是基于Disk的設計，顯然無法滿足Facebook的監控需求。

Gorilla可以說在深刻理解了的監控數據/時序數據的特點基礎上，很好的滿足了Facebook自身的需求。縱觀整篇論文，其關鍵技術點可以總結為如下幾個方面：

- 基于內存的設計。針對時序數據，設計了高效的內存數據結構，可支持高效的時序數據掃描，針對單個Time Series查詢時可提供穩定的低時延保障。

- 高效的壓縮算法。對DataPoint中的Timestamp與Point Value的數據特點提出了針對性的壓縮編碼機制，壓縮效果顯著，存儲空間節省90%以上，單個Data Point平均只占用1.37 Bytes。該壓縮機制有力支撐了基于內存的整體設計方案。

- 先緩存后批量寫日志。流式寫入到Gorilla中的數據，先緩存到一個64KB大小后，寫入到一個Append-Only的日志文件中。如果在數據未寫滿64KB之前，進程故障會導致數據丟失，而Gorilla容忍這種數據丟失場景。以少量的數據丟失換取寫入的高吞吐量。

- 無狀態易擴展。基于Shared-Nothing的設計，可以輕易實現數據節點的橫向擴展。

- 跨Region雙活集群。利用部署在兩個Region區的兩個集群來提升服務的高可用性

數據模型、分片、路由

Gorilla/ODS的一個Data Point由如下的三元組構成：

{string key,?timestamp,?point value}

與OpenTSDB、InfluxDB的模型相對比，Gorilla因舍棄了Tag的設計而顯得更加簡潔。Gorilla依賴于額外的元數據信息去索引string key，與Time Series數據相比，這部分數據顯得非常輕量級，但在整篇論文中，這里并沒有過多提及。

Gorilla的數據分片稱之為Shard，數據節點稱之為Gorilla Host。Shard被分配在一個Host中提供讀寫服務，Shard與Host的關系，類似于HBase中的Region與RegionServer的關系。Shard分配工作由基于Paxos實現的ShardManager負責。

一個Data Point，按照string key進行Hash運算后，匹配到對應的Shard，再由Shard的路由信息找到對應的Host。隨著時間的不斷推移，新的Time Series不斷被加入，而Gorilla的Hosts可以輕易擴展，擴展后，只需要簡單的調整分片規則讓新的Time Series映射到新的Hosts中即可。

內存組織結構

基于磁盤的讀取方式，是無法滿足高并發、低時延的查詢需求的。Facebook統計了ODS中的查詢后發現，85%的查詢與最近26個小時的數據寫入有關，如果將最近26個小時的數據全部緩存在內存中，將是一個理想的方案。

內存中的數據組織結構，稱之為Time Series Map，簡稱為TSmap。TSmap的組成結構如下圖所示：

由上圖可以看出來，TSmap的核心構成包含一個Vector以及一個Map：

- Vector存放了所有Time Series的指針，有利于高效掃描。基于C++標準庫的Shard Pointer實現。

- Map以Time Series Name為Key，以Time Series指針為Value。可按Time Series Name快速查詢，提供穩定的低時延保障。

上圖中的右側部分的TS，是一個Time Series的核心數據部分。一個TS包含0個或多個2小時以前的Blocks，以及一個當前正在接收新數據的Block。正在被寫入的Block，其實就是一個append-only的string, 經壓縮編碼后的Data Point數據，都被append到這個Block中，當超過2小時以后，這個Block被關閉，此后，這個Block在被移除之前不會再發生任何變更。Close時，這個Block被復制到一個較大的Slaps中以期有效降低內存碎片。

高效的壓縮算法

既然整個設計圍繞內存展開，對于整體數據的內存占用大小是至關重要的，這既涉及到方案的可行性，又涉及整個方案的性價比。

一個Data Point按照16 Bytes計算，而1秒鐘產生的Data Points數量為1200W，那么，在不考慮任何壓縮算法的前提下，一天的數據總量約為16TB。因此，一個高效的壓縮算法顯得至關重要。

我們知道一個Data Point中最關鍵的組成部分是Timestamp與Point Value，這兩部分數據具有如下典型特點：

- Data Point通常按固定的時間間隔產生。

- 在很多Time Series中，Point Value的變化通常是平緩的，甚至在很多情形中保持不變。

Gorilla針對Timestamp與Point Value的不同特點，采用了不同的壓縮編碼算法。我們可以先從下圖中獲取一些直觀的認識：

Timestamp壓縮(Delta-Of-Delta)

Facebook通過分析存放于ODS中的Time Series數據后，發現絕大部分Data Points都按固定的時間周期采集。例如，某一個Time Series可能固定按照60秒產生一個Data Point。當然也會出現一定的時間偏差，但這個偏差值在受限的范圍內。也就是說，在大多數情形下，可以將一個Time Series中的連續的Data Points的Timestamp列表視作一個等差數列，這是Delta-Of-Delta編碼算法的最適用場景。編碼原理如下：

1. 在Block Header中，存放起始Timestamp T(-1)，一個Block對應2個小時的時間窗口。假設第一個Data Point的Timestamp為T(0)，那么，實際存放時，我們只需要存T(0)與T(-1)的差值。

2. 對于接下來的Data Point的Timestamp T(N)， 首先計算Delta Of Delta值：

D = (T(N) - T(N-1)) - (T(N-1) - T(N-2))

而后，按照D的值所處的區間范圍，分別有5種不同情形的處理：

Case 1: 如果D為0，那么，存儲一個bit '0'

Case 2: 如果D位于區間[-63, 64]，存儲2個bits '10'，后面跟著用7個bits表示的D值

Case 3: 如果D位于區間[-255, 256]，存儲3個bits '110'，后面跟著9個bits表示的D值

Case 4: 如果D位于區間[-2047, 2048]，存儲4個bits '1110'，后面跟著12個bits表示的D值

Case 5: 如果D位于其它區間255, 256]，存儲4個bits '1111'，后面跟著32個bits表示的D值

關于這些Range的選取，是出于個別Data Points可能會缺失的考慮。例如：

假設正常的Interval為每60秒產生一個Data Point，如果缺失一個Data Point，那么，相鄰的兩個Data Points之間的Delta值為：60, 60, 121 and 59，此時，Delta Of Delta值將變為： 0, 61, -62。

這恰好落在區間[-63, 64]之間。

如果缺失4個Data Point，那么，Delta Of Delta值將落在區間[-255, 256]之間。

下圖針對Gorilla中的440,000條真實的Data Points采樣數據，對Timestamp數據應用了Delta-Of-Delta編碼之后的效果：

96.39%的Timestamps只需要占用一個Bit的空間，這樣看來，壓縮的效果非常明顯。

Point Value壓縮（XOR）

Gorilla中限制Point Value的類型為雙精度浮點數，在未啟用任何壓縮編碼的前提下，每個Point Value理應占用64個Bits。

同樣，Facebook在認真調研了ODS中的數據特點以后也有了這樣一個關鍵發現：在大多數Time Series中，相鄰的Data Points的Value變化比較輕微。這一點比較好理解，假設某一個Time Series關聯某個儀器溫度指標的監控，那么，溫度的變化應該是漸進式的而非跳躍式的。XOR編碼就是用來描述相鄰兩條Point Value的變化部分，下圖直觀描述了Point Value 24.0與12.0的變化部分：

XOR編碼詳細原理如下：

1.第一個Value存儲時不做任何壓縮。

2.后面產生的每一個Value與前一個Value計算XOR值：

如果XOR值為0，即兩個Value相同，那么存為'0'，只占用一個bit。

如果XOR為非0，首先計算XOR中位于前端的和后端的0的個數，即Leading Zeros與Trailing Zeros。

1) 第一個bit值存為'1'。

2) 比較Leading Zeros與Trailing Zeros部分是否與前一個XOR值相同：

2.1) 相同，則第2個bit值存為'0'，而后，緊跟著去掉Leading Zeros與Trailing Zeros以后的有效XOR值部分。

2.2) 不同，則第2個bit值存為'1'，而后，緊跟著5個bits用來描述Leading Zeros的值，再用6個bits來描述有效XOR值的長度，最后再存儲有效XOR值部分（這種情形下，至少產生了13個bits的冗余信息）

如下是針對Gorilla中1,600,000個Point Value采樣數據采用了XOR壓縮編碼后的效果：

從結果來看：

-?只占用1個bit的Value比例高達59.06%，這說明約一半以上的Point Value較之上一個Value并未發生變化。

-?30%比例的Value平均占用26.6 bits，即上面的情形2.1。

- 余下的12.64%的Value平均占用39.6 bits，即上面的情形2.2。

另外，XOR壓縮編碼機制，對于Integer類型的Point Value效果尤為顯著。

Block大小

壓縮算法通常都是基于Block進行的，Block越大，效果越明顯。對于時序數據的壓縮，則需要選擇一個合理的時間窗大小的數據進行壓縮。Facebook測試了不同的時間窗大小的壓縮效果：

可以看出來，隨著時間窗的逐步變大，壓縮效果的確越顯著。但超過2個小時(120 minutes)的時間窗大小以后，隨著時間窗口的逐步變大，壓縮效果的改善并不明顯。時間窗口為2小時的每個Data Point平均只占用1.37 bytes。

本文總結

本文先從Facebook的內需監控需求出發，討論了Gorilla的設計初衷。簡單介紹了Gorilla的數據模型、分片與路由機制以后，詳細介紹了Gorilla的基于內存的數據結構設計，以及針對Timestamp與Point Value的壓縮編碼機制。下篇文章將介紹Gorilla的數據持久化機制，故障處理機制以及跨Region的雙活方案。

本文轉載自微信公眾號【Nosql漫談】。

NoSQL數據庫

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。