Prometheus 參考實現的時序數據庫 Gorilla 介紹

在大型微服務架構中，服務監控和實時分析需要大量的時序數據。存儲這些時序數據最高效的方案就是使用時序數據庫 (TSDB)。設計時序數據庫的重要挑戰之一便是在效率、擴展性和可靠性中找到平衡。這篇論文介紹的是 Facebook 內部孵化的內存時序數據庫，Gorilla。Facebook 團隊發現：

  1. 監控系統的用戶主要關注的是數據的聚合分析，而不是單個數據點

  2. 對於線上問題的根源分析來說，最近的數據比過去的數據更有價值

Gorilla  以可能拋棄少量數據爲代價，在讀寫高可用方面做了優化。爲了改進查詢效率，開發團隊使用了激進的壓縮技術：

  1. delta-of-delta timestamps

  2. XOR'd floating point values

相比基於 HBase 的方案，Gorilla 將內存消耗縮小 10 倍，並使得數據得以存放在內存中，進而將查詢時延減少 73 倍，查詢吞吐量提高了 14 倍。這樣的性能改進也解鎖了更多的監控、調試工具，如相關性分析、密集可視化。Gorilla 甚至能夠優雅的解決單點到整個可用區域故障的問題。

介紹

以下是 FB 內部對時序數據庫的要求：

Write Dominate

對時序數據庫的首要限制就是必須一直能夠寫入數據，即寫數據的高可用。因爲 FB 內部的服務集羣每秒將產生 1 千萬個採樣數據點。相較之下，讀數據比寫數據要求通常要低好幾個數量級，因爲數據的消費者是一些運維、開發使用的控制面板以及自動化報警系統，它們的請求頻率低且通常只關注部分時序數據。由於用戶關注的往往是整組時序數據的聚合結果，而不是單個數據點，因此傳統數據庫中的 ACID 保證也並不是時序數據庫的核心要求，即便在極端情況下，丟棄少量數據也不會影響核心用途。

State Transition

FB 內部希望能夠及時發現一些系統的狀態轉移事件，如：

因此要求時序數據庫能支持對較短的時間窗口內的採樣數據進行細粒度的聚合。具備在十秒級內展示捕獲到的狀態轉移事件能夠幫助自動化工具快速發現問題，阻止其發生擴散。

High Availability

即便當不同 DC 之間發生網絡分區，DC 內部的服務也應當能夠將實時監控的數據寫入到 DC 內部的時序數據庫，也能夠從中讀取數據。

Fault Tolerance

如果能夠將數據複製到多個區域 (regions)，就可以在單個 DC 或整個地理區域發生問題時也能正常運作。

Gorilla 正是爲滿足以上所有要求而開發的時序數據庫，它可以被理解成是時序數據的 write-through cache，由於數據都在內存中，Gorilla 幾乎可以在 10 毫秒級別內處理大部分請求。通過對 FB 內部已經投入使用很長時間的 Operational Data Store (ODS，基於 HBase 的時序數據庫解決方案）的研究，發現超過 85% 的數據查詢只涉及到過去 26 小時內產生的數據，通過進一步的調研發現，如果使用內存數據庫來代替磁盤（disk-based）數據庫，就能夠達到用戶對響應時間的要求。

在 2015 年春，FB 內部的監控系統共產生超過 20 億組時間序列，每秒產生 1200 萬個，每天 1 萬億個數據點。假設每個採樣點需要 16 字節來存儲，就意味着一天需要 16 TB 內存。Gorilla 團隊通過基於 XOR 的浮點數壓縮算法將每個採樣點所需字節數降到 1.37，將內存總需求量縮小將近 12 倍。

針對可用性要求，Gorilla 團隊在不同區域、DC 中部署多個 Gorilla 實例，實例時間相互同步數據，但不保證一致性。數據的讀取請求將被轉發到最近的 Gorilla 實例。

背景和需求

ODS

ODS 是 FB 線上服務監控系統的重要組成部分，它由一個基於 HBash 的時序數據庫，數據查詢服務以及報警系統共同構成。它的整體架構如下圖所示：

ODS 的消費者主要由兩部分構成：

  1. 便於開發人員分析問題的可交互圖表系統

  2. 自動化報警系統

在 2013 年初，FB 的監控團隊意識到基於 HBase 的時序數據庫無法處理未來的讀負載，儘管圖標分析時數據查詢的延遲還可以容忍，但達到幾秒鐘的查詢 90th 分位點已經阻塞了自動化報警的正常運作。在眼下其它現成方案都無法滿足要求的情況下，監控團隊開始將關注點轉向緩存解決方案。儘管 ODS 就使用了簡單的 read-through cache，但這種方案只是緩存多張圖表中共同的時序數據，但每當圖表查詢最新的數據時，依然還會出現 cache miss，這時候數據讀取就擊穿到了 HBase。監控團隊也考慮過使用 Memcache 作爲 write-through cache，但每次寫入大量最新數據會對 memcache 引入很大的流量，最終這個方案也被否決了。監控團隊需要更加高效的解決方案。

Gorilla 需求

以下是對新的解決方案的要求陳述：

與其他 TSDB 系統比較

由於 Gorilla 的設計是將所有數據放在內存中，因此它的內存數據結構與其它的時序數據庫有所不同。也得益於這樣的設計，開發者也可以將 Gorilla 看作是基於磁盤的時序數據庫的 write-through cache。

OpenTSDB

OpenTSDB 是繼續 HBase 的時序數據庫解決方案，它與 ODS 的 HBase 存儲層很相似。兩個系統的表結構設計非常相似，也採用了類似的優化、橫向擴容的解決方案。但前面也提到，基於磁盤的解決方案很難支持快速查詢的需求。ODS 的 HBase 存儲層會刻意降低舊數據的採樣精度，從而節省總體空間佔用；OpenTSDB 則會保存數據的完全精度。犧牲舊數據的精度，能夠帶來更快的舊數據查詢速度以及空間的節省，FB 團隊認爲這是值得的。OpenTSDB 標識時序數據的數據模型相比 Gorilla 更加豐富，每組時序數據可以標記任意組鍵值數據，即所謂的標籤 (tags)。Gorilla 只通過一個字符串來標記時序數據，它依賴於上層工中從去抽取標識時序數據的信息。

Whisper (Graphite)

Graphite 以 Whisper format 將時序數據存儲在本地磁盤上。Whisper format 期望時序數據的採樣區間是穩定的，如果採樣區間發生抖動，Graphite 就無能爲力了。相較之下，如果時序數據的採樣區間是穩定的，Gorilla 能夠更高效地存儲數據，Gorilla 也能處理區間不穩定的情況。在 Graphite 中，每組時序數據都存在一個獨立的文件中，新的樣本點會覆蓋超過一定時間的舊數據；Gorilla 也很類似，但區別在於它將數據存儲在內存中。由於 Graphite 是基於磁盤的時序數據庫，同樣不滿足 FB 內部的需求。

InfluxDB

InfluxDB 的數據模型表達力比 OpenTSDB 更加豐富，時序中的每一個樣本都可以擁有完整元數據，但這種做法也導致它的數據存儲需要佔用更多的磁盤空間。InfluxDB 也支持集羣部署，橫向擴容，運維團隊無需管理 HBase/Hadoop 集羣。在 FB 中已經有專門的團隊負責運維 HBase 集羣，因此對於 ODS 團隊來說這並不是一個痛點。與其它系統類似，InfluxDB 也將數據存儲在磁盤中，其查詢效率要遠低於內存數據庫。

Gorilla 架構

在 Gorilla 中，每條時序樣本數據都由一個三元組構成：

Gorilla 採用一種新的時序壓縮算法，將存儲每條時序樣本數據所需的空間由之前的 16 字節降到了平均 1.37 個字節。

通過將每組時序數據通過 string key 分片到某個的 Gorilla 服務，就能比較容易地實現橫向擴容。在 Gorilla 正式上線 18 個月後，存儲 26 小時的數據約需要 1.3TB 內存，每個集羣需要 20 臺機器。在論文寫作時，每個集羣已經需要 80 臺機器。

Gorilla 通過同時將時序數據寫入兩臺位於不同 regions 的機器中，來抵禦單點故障、網絡分區、甚至整個 DC 故障。一旦發現故障，所有的讀請求將被轉發到備選 region 中的服務上，保證用戶對故障無明顯感知。

時間序列壓縮

Gorilla 對壓縮算法主要有兩個要求：

對比連續的樣本數據分析，能夠觀察到：

因此 Gorilla 對時間戳和數據值分別使用不同的壓縮算法。在分析具體算法之前，可以看一下算法的整體流程：

  1. 每塊數據的開頭記錄起始時間戳

  2. 第一條樣本數據

  1. 從第二條樣本數據開始

Time Stamps 壓縮

通過分析 ODS 中的時序數據，Gorilla 團隊觀察到大多數時序樣本都是按固定區間到達服務，如 60 秒。儘管偶爾會出現 1 秒鐘的延遲或提早，總體上時間窗口是穩定的。

假設連續時間戳的 delta 爲：60, 60, 59, 61，那麼 delta of delta 就是：0, -1, 2，於是通過起始時間、第一條數據與起始時間的 delta，以及剩下所有樣本點的 delta of delta，就能夠存儲完整的數據。

算法中爲 D 選擇的區間在真實數據能夠獲得最大的壓縮率。一個時序數據可能隨時出現數據點丟失，於是可能出現這樣的 delta 序列：60, 60, 121, 59，這時候 delta of delta 就是：0, 61, -62，這時候就需要存儲 10 bits 數據。下圖是時序壓縮的統計表現：

Values 壓縮

通過分析 ODS 的數據，Gorilla 團隊觀察到大部分相鄰的時序數據值之間不會有很大的變化。根據 IEEE 754 中定義的浮點數編碼格式：

通常相鄰的數值之間，sign、exponent 以及 mantissa 前面的一些 bits 不會改變，如下圖所示：

因此利用這個，我們可以通過記錄相鄰數值的 XOR 中不同的信息來壓縮數據。完整的算法流程如下：

  1. 第一個數值無壓縮存儲

  2. 如果與上一個數值 XOR 的結果爲 0，即數值未發生改變，則存儲 1 bit，'0'

  3. 如果與上一個數值 XOR 的結果不爲 0，則先存儲 1 bit，'1'

具體可參考流程圖中的例子，即：

下圖展示時序數據值壓縮算法的統計表現：

  1. 59% 的數值只需要 1 bit 即可以存儲

  2. 28% 的數值只需要 26.6 bits 即可存儲

  3. 13% 的數值需要 39.6 bits 可以存儲

這裏有一個 trade-off 需要考慮：每個數據塊所覆蓋的時間跨度。更大的時間跨度可以獲得更高的壓縮率，然而解壓縮所需的資源也越多，具體的統計結果展示如下：

從圖中可以看出在 2 小時之後，繼續增大跨度帶來壓縮率提升的邊際收益已經非常小，因此 Gorilla 最終選擇 2 小時的時間跨度。

內存中的數據結構

Gorilla 在內存中的數據結構如下圖所示

整個數據結構可以分三層：

ShardMap

每個 Gorilla 節點上都維護着一個 ShardMap，後者負責將時序名稱的哈希值映射到相應的 TSmap 上。如果 ShardMap 上對應的指針爲空，則目標時序數據不在當前的節點 (分片) 上。由於系統中分片的數量是常數，且預期數量級在 3 位數內，因此存儲 ShardMap 的成本很低。ShardMap 的併發訪問通過一個 read-write spin lock 來控制。

TSmap

TSmap 是時序數據的索引。它由以下兩部分構成：

  1. 所有 TS 的指針構成的向量，標記爲 vector

  2. 將時序名稱的哈希值映射到 TS 指針的字典，標記爲 map

vector 用於快速掃描所有數據；map 用於滿足穩定、快速的查詢請求。TSmap 的併發控制通過一個 read-write spin lock 實現。掃描完整數據時，只需要複製 vector，後者是由一批指針構成，速度很快，critical section 很小；刪除數據時，通過 tombstoned 標記刪除，被動回收。

TS

每組時序數據都由一系列數據塊構成，每個數據塊保存 2 小時的數據，最新的數據塊還處於打開狀態，上面維持着最近的數據。最新的數據塊中只能往後追加數據，一旦時間滿 2 小時，數據塊就會被關閉，已經關閉的數據塊在被清出內存之前不允許再被修改。

讀取數據時，查詢所涉及的所有數據塊將被複制一份，直接返回給 RPC 客戶端，數據的解壓縮過程由客戶端完成。

磁盤結構

Gorilla 的設計目標之一就是能抵禦單點故障，因此 Gorilla 同樣需要通過持久化存儲做故障恢復。Gorilla 選擇的持久化存儲是 GlusterFS，後者是兼容 POSIX 標準的分佈式文件系統，默認 3 備份。其它分佈式文件系統，如 HDFS 也可以使用。Gorilla 團隊也考慮使用單機 MySQL 或者 RocksDB，但最終沒有選擇，原因是 Gorilla 並不需要使用查詢語言支持。

一個 Gorilla 節點會維持多個分片的數據，於是它會爲每個分片建立一個文件夾。每個文件夾中包含四類文件：

Key Lists

Key Lists 實際上就是時序名稱到 integer identifier 的映射，後者是時序在 TSmap vector 中的偏移值。Gorilla 會週期性地更新 Key Lists 數據。

Append-only Logs

當所有時序數據的樣本點流向 Gorilla 節點時，Gorilla 會將他們壓縮後的數據交織地寫入日誌文件中。但這裏的日誌文件並不是 WAL，Gorilla 也並沒有打算提供 ACID 支持，當日志數據在內存中滿 64 KB 後會被追加到 GlusterFS 中相應的日誌文件中。故障發生時，將有可能出現少量數據丟失，但爲了提高寫吞吐，這個犧牲還算值得。

Complete Block Files

每隔 2 小時，Gorilla 會將數據塊壓縮後複製到 GlusterFS 中。每當一塊數據持久化完成後，Gorilla 就會創建一個 checkpoint 文件，同時刪除相應的日誌文件。checkpoint 文件被用來標識數據塊持久化成功與否。故障恢復時，Gorilla 會通過 checkpoint 和日誌文件載入之前的數據。

容錯

在容錯方面，Gorilla 優先支持以下場景：

高可用

Gorilla 通過在兩個不同區域的 DC 維護兩臺獨立的實例保障服務的可用性。同一組時序數據寫入時，會被髮送給這兩臺獨立的實例上，但不保證兩次寫操作的原子性。當一個區域故障時，讀請求將被嘗試發送到另一個區域。如果該區域的故障持續超過 1 分鐘，讀請求將不再發送給它，直到該區域中的實例數據已經正常寫入 26 小時爲止。

在每個區域內部，一種基於 Paxos 的 ShardManager 用於維護分片與節點之間的關係。當一個節點發生故障時，ShardManager 會將它維護的分片重新分配給集羣內部的其它節點。分片轉移通常能夠在 30 秒內完成，在分片轉移的過程中，寫入數據的客戶端將緩存待寫入的數據，並且最多緩存最近 1 分鐘的數據。當客戶端發現分片轉移操作執行完時，客戶端會立即掏空緩存，將數據寫入到節點中。如果分片轉移速度太慢，讀請求可以被手動或自動地轉發到另一個區域。

當新的分片被分配給一個節點時，該節點需要從 GlusterFS 中讀入所有數據。通常加載和預處理這些數據需要 5 分鐘。當該節點正在恢復數據時，新寫入的時序樣本數據會被放入一個待處理隊列。在老節點發生故障後，新節點加載分片數據完畢之前，讀請求可能會讀到部分數據，並打上標記。如果客戶端發現數據被標記爲部分數據，會再次請求另一個區域中的數據，如果數據完整則返回後者，失敗則返回兩組部分數據。

最後，FB 仍然使用 HBase TSDB 來存儲長期數據，工程師仍然可以通過它來分析過去的時序數據。

NewTools on Gorilla

由於 Gorilla 的數據存放在內存中，這樣讓更多的實時分析成爲可能。

論文地址：http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

翻譯原文：https://zhenghe.gitbook.io/open-courses/papers-we-love/gorilla-a-fast-scalable-in-memory-time-series-database

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/p-kqX2dNdmPvaqjcCe1xyg

猜你喜歡