Prometheus 參考實現(xiàn)的時序數(shù)據(jù)庫 Gorilla 介紹
在大型微服務架構中，服務監(jiān)控和實時分析需要大量的時序數(shù)據(jù)。存儲這些時序數(shù)據(jù)最高效的方案就是使用時序數(shù)據(jù)庫 (TSDB)。設計時序數(shù)據(jù)庫的重要挑戰(zhàn)之一便是在效率、擴展性和可靠性中找到平衡。這篇論文介紹的是 Facebook 內(nèi)部孵化的內(nèi)存時序數(shù)據(jù)庫，Gorilla。Facebook 團隊發(fā)現(xiàn)：
監(jiān)控系統(tǒng)的用戶主要關注的是數(shù)據(jù)的聚合分析，而不是單個數(shù)據(jù)點 對于線上問題的根源分析來說，最近的數(shù)據(jù)比過去的數(shù)據(jù)更有價值
Gorilla ?以可能拋棄少量數(shù)據(jù)為代價，在讀寫高可用方面做了優(yōu)化。為了改進查詢效率，開發(fā)團隊使用了激進的壓縮技術：
delta-of-delta timestamps XOR'd floating point values
相比基于 HBase 的方案，Gorilla 將內(nèi)存消耗縮小 10 倍，并使得數(shù)據(jù)得以存放在內(nèi)存中，進而將查詢時延減少 73 倍，查詢吞吐量提高了 14 倍。這樣的性能改進也解鎖了更多的監(jiān)控、調(diào)試工具，如相關性分析、密集可視化。Gorilla 甚至能夠優(yōu)雅的解決單點到整個可用區(qū)域故障的問題。
介紹
以下是 FB 內(nèi)部對時序數(shù)據(jù)庫的要求：
Write Dominate
對時序數(shù)據(jù)庫的首要限制就是必須一直能夠?qū)懭霐?shù)據(jù)，即寫數(shù)據(jù)的高可用。因為 FB 內(nèi)部的服務集群每秒將產(chǎn)生 1 千萬個采樣數(shù)據(jù)點。相較之下，讀數(shù)據(jù)比寫數(shù)據(jù)要求通常要低好幾個數(shù)量級，因為數(shù)據(jù)的消費者是一些運維、開發(fā)使用的控制面板以及自動化報警系統(tǒng)，它們的請求頻率低且通常只關注部分時序數(shù)據(jù)。由于用戶關注的往往是整組時序數(shù)據(jù)的聚合結(jié)果，而不是單個數(shù)據(jù)點，因此傳統(tǒng)數(shù)據(jù)庫中的 ACID 保證也并不是時序數(shù)據(jù)庫的核心要求，即便在極端情況下，丟棄少量數(shù)據(jù)也不會影響核心用途。
State Transition
FB 內(nèi)部希望能夠及時發(fā)現(xiàn)一些系統(tǒng)的狀態(tài)轉(zhuǎn)移事件，如：
服務新版本發(fā)布 服務配置修改 網(wǎng)絡切換 ...
因此要求時序數(shù)據(jù)庫能支持對較短的時間窗口內(nèi)的采樣數(shù)據(jù)進行細粒度的聚合。具備在十秒級內(nèi)展示捕獲到的狀態(tài)轉(zhuǎn)移事件能夠幫助自動化工具快速發(fā)現(xiàn)問題，阻止其發(fā)生擴散。
High Availability
即便當不同 DC 之間發(fā)生網(wǎng)絡分區(qū)，DC 內(nèi)部的服務也應當能夠?qū)崟r監(jiān)控的數(shù)據(jù)寫入到 DC 內(nèi)部的時序數(shù)據(jù)庫，也能夠從中讀取數(shù)據(jù)。
Fault Tolerance
如果能夠?qū)?shù)據(jù)復制到多個區(qū)域 (regions)，就可以在單個 DC 或整個地理區(qū)域發(fā)生問題時也能正常運作。
Gorilla 正是為滿足以上所有要求而開發(fā)的時序數(shù)據(jù)庫，它可以被理解成是時序數(shù)據(jù)的 write-through cache，由于數(shù)據(jù)都在內(nèi)存中，Gorilla 幾乎可以在 10 毫秒級別內(nèi)處理大部分請求。通過對 FB 內(nèi)部已經(jīng)投入使用很長時間的 Operational Data Store (ODS，基于 HBase 的時序數(shù)據(jù)庫解決方案）的研究，發(fā)現(xiàn)超過 85% 的數(shù)據(jù)查詢只涉及到過去 26 小時內(nèi)產(chǎn)生的數(shù)據(jù)，通過進一步的調(diào)研發(fā)現(xiàn)，如果使用內(nèi)存數(shù)據(jù)庫來代替磁盤（disk-based）數(shù)據(jù)庫，就能夠達到用戶對響應時間的要求。
在 2015 年春，F(xiàn)B 內(nèi)部的監(jiān)控系統(tǒng)共產(chǎn)生超過 20 億組時間序列，每秒產(chǎn)生 1200 萬個，每天 1 萬億個數(shù)據(jù)點。假設每個采樣點需要 16 字節(jié)來存儲，就意味著一天需要 16 TB 內(nèi)存。Gorilla 團隊通過基于 XOR 的浮點數(shù)壓縮算法將每個采樣點所需字節(jié)數(shù)降到 1.37，將內(nèi)存總需求量縮小將近 12 倍。
針對可用性要求，Gorilla 團隊在不同區(qū)域、DC 中部署多個 Gorilla 實例，實例時間相互同步數(shù)據(jù)，但不保證一致性。數(shù)據(jù)的讀取請求將被轉(zhuǎn)發(fā)到最近的 Gorilla 實例。
背景和需求
ODS
ODS 是 FB 線上服務監(jiān)控系統(tǒng)的重要組成部分，它由一個基于 HBash 的時序數(shù)據(jù)庫，數(shù)據(jù)查詢服務以及報警系統(tǒng)共同構成。它的整體架構如下圖所示：
ODS 的消費者主要由兩部分構成：
便于開發(fā)人員分析問題的可交互圖表系統(tǒng) 自動化報警系統(tǒng)
在 2013 年初，F(xiàn)B 的監(jiān)控團隊意識到基于 HBase 的時序數(shù)據(jù)庫無法處理未來的讀負載，盡管圖標分析時數(shù)據(jù)查詢的延遲還可以容忍，但達到幾秒鐘的查詢 90th 分位點已經(jīng)阻塞了自動化報警的正常運作。在眼下其它現(xiàn)成方案都無法滿足要求的情況下，監(jiān)控團隊開始將關注點轉(zhuǎn)向緩存解決方案。盡管 ODS 就使用了簡單的 read-through cache，但這種方案只是緩存多張圖表中共同的時序數(shù)據(jù)，但每當圖表查詢最新的數(shù)據(jù)時，依然還會出現(xiàn) cache miss，這時候數(shù)據(jù)讀取就擊穿到了 HBase。監(jiān)控團隊也考慮過使用 Memcache 作為 write-through cache，但每次寫入大量最新數(shù)據(jù)會對 memcache 引入很大的流量，最終這個方案也被否決了。監(jiān)控團隊需要更加高效的解決方案。
Gorilla 需求
以下是對新的解決方案的要求陳述：
20 億組不同的時序數(shù)據(jù)，每組時序數(shù)據(jù)用一個唯一的字符串標識 每分鐘 7 億個數(shù)據(jù)采樣點 保存 26 小時的全量數(shù)據(jù) 數(shù)據(jù)讀取在 1ms 內(nèi)完成 支持最小采樣間隔為 15s 兩個復制節(jié)點來支持容錯，即使有一個節(jié)點掛掉也能夠繼續(xù)處理讀請求 能夠快速掃描所有內(nèi)存數(shù)據(jù) 支持每年 2 倍的增長
與其他 TSDB 系統(tǒng)比較
由于 Gorilla 的設計是將所有數(shù)據(jù)放在內(nèi)存中，因此它的內(nèi)存數(shù)據(jù)結(jié)構與其它的時序數(shù)據(jù)庫有所不同。也得益于這樣的設計，開發(fā)者也可以將 Gorilla 看作是基于磁盤的時序數(shù)據(jù)庫的 write-through cache。
OpenTSDB
OpenTSDB 是繼續(xù) HBase 的時序數(shù)據(jù)庫解決方案，它與 ODS 的 HBase 存儲層很相似。兩個系統(tǒng)的表結(jié)構設計非常相似，也采用了類似的優(yōu)化、橫向擴容的解決方案。但前面也提到，基于磁盤的解決方案很難支持快速查詢的需求。ODS 的 HBase 存儲層會刻意降低舊數(shù)據(jù)的采樣精度，從而節(jié)省總體空間占用；OpenTSDB 則會保存數(shù)據(jù)的完全精度。犧牲舊數(shù)據(jù)的精度，能夠帶來更快的舊數(shù)據(jù)查詢速度以及空間的節(jié)省，F(xiàn)B 團隊認為這是值得的。OpenTSDB 標識時序數(shù)據(jù)的數(shù)據(jù)模型相比 Gorilla 更加豐富，每組時序數(shù)據(jù)可以標記任意組鍵值數(shù)據(jù)，即所謂的標簽 (tags)。Gorilla 只通過一個字符串來標記時序數(shù)據(jù)，它依賴于上層工中從去抽取標識時序數(shù)據(jù)的信息。
Whisper (Graphite)
Graphite 以 Whisper format 將時序數(shù)據(jù)存儲在本地磁盤上。Whisper format 期望時序數(shù)據(jù)的采樣區(qū)間是穩(wěn)定的，如果采樣區(qū)間發(fā)生抖動，Graphite 就無能為力了。相較之下，如果時序數(shù)據(jù)的采樣區(qū)間是穩(wěn)定的，Gorilla 能夠更高效地存儲數(shù)據(jù)，Gorilla 也能處理區(qū)間不穩(wěn)定的情況。在 Graphite 中，每組時序數(shù)據(jù)都存在一個獨立的文件中，新的樣本點會覆蓋超過一定時間的舊數(shù)據(jù)；Gorilla 也很類似，但區(qū)別在于它將數(shù)據(jù)存儲在內(nèi)存中。由于 Graphite 是基于磁盤的時序數(shù)據(jù)庫，同樣不滿足 FB 內(nèi)部的需求。
InfluxDB
InfluxDB 的數(shù)據(jù)模型表達力比 OpenTSDB 更加豐富，時序中的每一個樣本都可以擁有完整元數(shù)據(jù)，但這種做法也導致它的數(shù)據(jù)存儲需要占用更多的磁盤空間。InfluxDB 也支持集群部署，橫向擴容，運維團隊無需管理 HBase/Hadoop 集群。在 FB 中已經(jīng)有專門的團隊負責運維 HBase 集群，因此對于 ODS 團隊來說這并不是一個痛點。與其它系統(tǒng)類似，InfluxDB 也將數(shù)據(jù)存儲在磁盤中，其查詢效率要遠低于內(nèi)存數(shù)據(jù)庫。
Gorilla 架構
在 Gorilla 中，每條時序樣本數(shù)據(jù)都由一個三元組構成：
string key：用于標識所屬的時序 timestamp (int64)：時間戳 value (float64)：樣本值
Gorilla 采用一種新的時序壓縮算法，將存儲每條時序樣本數(shù)據(jù)所需的空間由之前的 16 字節(jié)降到了平均 1.37 個字節(jié)。
通過將每組時序數(shù)據(jù)通過 string key 分片到某個的 Gorilla 服務，就能比較容易地實現(xiàn)橫向擴容。在 Gorilla 正式上線 18 個月后，存儲 26 小時的數(shù)據(jù)約需要 1.3TB 內(nèi)存，每個集群需要 20 臺機器。在論文寫作時，每個集群已經(jīng)需要 80 臺機器。
Gorilla 通過同時將時序數(shù)據(jù)寫入兩臺位于不同 regions 的機器中，來抵御單點故障、網(wǎng)絡分區(qū)、甚至整個 DC 故障。一旦發(fā)現(xiàn)故障，所有的讀請求將被轉(zhuǎn)發(fā)到備選 region 中的服務上，保證用戶對故障無明顯感知。
時間序列壓縮
Gorilla 對壓縮算法主要有兩個要求：
流式壓縮：無需讀取完整數(shù)據(jù) 無損壓縮：不能損失數(shù)據(jù)精度
對比連續(xù)的樣本數(shù)據(jù)分析，能夠觀察到：
連續(xù)的時間戳之間間隔通常為常數(shù)，如 15 秒 連續(xù)的數(shù)據(jù)值之間的二進制編碼差別較小
因此 Gorilla 對時間戳和數(shù)據(jù)值分別使用不同的壓縮算法。在分析具體算法之前，可以看一下算法的整體流程：
每塊數(shù)據(jù)的開頭記錄起始時間戳 第一條樣本數(shù)據(jù) 時間戳存儲與起始時間戳的差值 數(shù)據(jù)值按原值存儲 從第二條樣本數(shù)據(jù)開始 時間戳存儲 delta of delta 數(shù)據(jù)值按差值存儲
Time Stamps壓縮
通過分析 ODS 中的時序數(shù)據(jù)，Gorilla 團隊觀察到大多數(shù)時序樣本都是按固定區(qū)間到達服務，如 60 秒。盡管偶爾會出現(xiàn) 1 秒鐘的延遲或提早，總體上時間窗口是穩(wěn)定的。
假設連續(xù)時間戳的 delta 為：60, 60, 59, 61，那么 delta of delta 就是：0, -1, 2，于是通過起始時間、第一條數(shù)據(jù)與起始時間的 delta，以及剩下所有樣本點的 delta of delta，就能夠存儲完整的數(shù)據(jù)。
算法中為 D 選擇的區(qū)間在真實數(shù)據(jù)能夠獲得最大的壓縮率。一個時序數(shù)據(jù)可能隨時出現(xiàn)數(shù)據(jù)點丟失，于是可能出現(xiàn)這樣的 delta 序列：60, 60, 121, 59，這時候 delta of delta 就是：0, 61, -62，這時候就需要存儲 10 bits 數(shù)據(jù)。下圖是時序壓縮的統(tǒng)計表現(xiàn)：
Values 壓縮
通過分析 ODS 的數(shù)據(jù)，Gorilla 團隊觀察到大部分相鄰的時序數(shù)據(jù)值之間不會有很大的變化。根據(jù) IEEE 754 中定義的浮點數(shù)編碼格式：
通常相鄰的數(shù)值之間，sign、exponent 以及 mantissa 前面的一些 bits 不會改變，如下圖所示：
因此利用這個，我們可以通過記錄相鄰數(shù)值的 XOR 中不同的信息來壓縮數(shù)據(jù)。完整的算法流程如下：
第一個數(shù)值無壓縮存儲 如果與上一個數(shù)值 XOR 的結(jié)果為 0，即數(shù)值未發(fā)生改變，則存儲 1 bit，'0' 如果與上一個數(shù)值 XOR 的結(jié)果不為 0，則先存儲 1 bit，'1' (Control bit '0')：如果當前 XOR 的區(qū)間在前一個 XOR 區(qū)間里面，那么可以復用前一個 XOR 區(qū)間的位置信息，只存儲區(qū)間內(nèi)部的 XOR 的值 (Control bit '1')：如果當前 XOR 的區(qū)間不在前一個 XOR 區(qū)間里面，則先利用 5 bits 存儲前綴 0 的數(shù)量，再利用 6 bits 存儲區(qū)間的長度，最后存儲區(qū)間內(nèi)部 XOR 的值
具體可參考流程圖中的例子，即：
下圖展示時序數(shù)據(jù)值壓縮算法的統(tǒng)計表現(xiàn)：
59% 的數(shù)值只需要 1 bit 即可以存儲 28% 的數(shù)值只需要 26.6 bits 即可存儲 13% 的數(shù)值需要 39.6 bits 可以存儲
這里有一個 trade-off 需要考慮：每個數(shù)據(jù)塊所覆蓋的時間跨度。更大的時間跨度可以獲得更高的壓縮率，然而解壓縮所需的資源也越多，具體的統(tǒng)計結(jié)果展示如下：
從圖中可以看出在 2 小時之后，繼續(xù)增大跨度帶來壓縮率提升的邊際收益已經(jīng)非常小，因此 Gorilla 最終選擇 2 小時的時間跨度。
內(nèi)存中的數(shù)據(jù)結(jié)構
Gorilla 在內(nèi)存中的數(shù)據(jù)結(jié)構如下圖所示
整個數(shù)據(jù)結(jié)構可以分三層：
ShardMap TSmap TS
ShardMap
每個 Gorilla 節(jié)點上都維護著一個 ShardMap，后者負責將時序名稱的哈希值映射到相應的 TSmap 上。如果 ShardMap 上對應的指針為空，則目標時序數(shù)據(jù)不在當前的節(jié)點 (分片) 上。由于系統(tǒng)中分片的數(shù)量是常數(shù)，且預期數(shù)量級在 3 位數(shù)內(nèi)，因此存儲 ShardMap 的成本很低。ShardMap 的并發(fā)訪問通過一個 read-write spin lock 來控制。
TSmap
TSmap 是時序數(shù)據(jù)的索引。它由以下兩部分構成：
所有 TS 的指針構成的向量，標記為 vector 將時序名稱的哈希值映射到 TS 指針的字典，標記為 map
vector 用于快速掃描所有數(shù)據(jù)；map 用于滿足穩(wěn)定、快速的查詢請求。TSmap 的并發(fā)控制通過一個 read-write spin lock 實現(xiàn)。掃描完整數(shù)據(jù)時，只需要復制 vector，后者是由一批指針構成，速度很快，critical section 很小；刪除數(shù)據(jù)時，通過 tombstoned 標記刪除，被動回收。
TS
每組時序數(shù)據(jù)都由一系列數(shù)據(jù)塊構成，每個數(shù)據(jù)塊保存 2 小時的數(shù)據(jù)，最新的數(shù)據(jù)塊還處于打開狀態(tài)，上面維持著最近的數(shù)據(jù)。最新的數(shù)據(jù)塊中只能往后追加數(shù)據(jù)，一旦時間滿 2 小時，數(shù)據(jù)塊就會被關閉，已經(jīng)關閉的數(shù)據(jù)塊在被清出內(nèi)存之前不允許再被修改。
讀取數(shù)據(jù)時，查詢所涉及的所有數(shù)據(jù)塊將被復制一份，直接返回給 RPC 客戶端，數(shù)據(jù)的解壓縮過程由客戶端完成。
磁盤結(jié)構
Gorilla 的設計目標之一就是能抵御單點故障，因此 Gorilla 同樣需要通過持久化存儲做故障恢復。Gorilla 選擇的持久化存儲是 GlusterFS，后者是兼容 POSIX 標準的分布式文件系統(tǒng)，默認 3 備份。其它分布式文件系統(tǒng)，如 HDFS 也可以使用。Gorilla 團隊也考慮使用單機 MySQL 或者 RocksDB，但最終沒有選擇，原因是 Gorilla 并不需要使用查詢語言支持。
一個 Gorilla 節(jié)點會維持多個分片的數(shù)據(jù)，于是它會為每個分片建立一個文件夾。每個文件夾中包含四類文件：
Key Lists Append-only Logs Complete Block Files Checkpoint Files
Key Lists
Key Lists 實際上就是時序名稱到 integer identifier 的映射，后者是時序在 TSmap vector 中的偏移值。Gorilla 會周期性地更新 Key Lists 數(shù)據(jù)。
Append-only Logs
當所有時序數(shù)據(jù)的樣本點流向 Gorilla 節(jié)點時，Gorilla 會將他們壓縮后的數(shù)據(jù)交織地寫入日志文件中。但這里的日志文件并不是 WAL，Gorilla 也并沒有打算提供 ACID 支持，當日志數(shù)據(jù)在內(nèi)存中滿 64 KB 后會被追加到 GlusterFS 中相應的日志文件中。故障發(fā)生時，將有可能出現(xiàn)少量數(shù)據(jù)丟失，但為了提高寫吞吐，這個犧牲還算值得。
Complete Block Files
每隔 2 小時，Gorilla 會將數(shù)據(jù)塊壓縮后復制到 GlusterFS 中。每當一塊數(shù)據(jù)持久化完成后，Gorilla 就會創(chuàng)建一個 checkpoint 文件，同時刪除相應的日志文件。checkpoint 文件被用來標識數(shù)據(jù)塊持久化成功與否。故障恢復時，Gorilla 會通過 checkpoint 和日志文件載入之前的數(shù)據(jù)。
容錯
在容錯方面，Gorilla 優(yōu)先支持以下場景：
單點故障，如果是臨時故障則客戶端完全無感知，常用于新版發(fā)布 大范圍、區(qū)域性故障：如 region 范圍的網(wǎng)絡分區(qū)
高可用
Gorilla 通過在兩個不同區(qū)域的 DC 維護兩臺獨立的實例保障服務的可用性。同一組時序數(shù)據(jù)寫入時，會被發(fā)送給這兩臺獨立的實例上，但不保證兩次寫操作的原子性。當一個區(qū)域故障時，讀請求將被嘗試發(fā)送到另一個區(qū)域。如果該區(qū)域的故障持續(xù)超過 1 分鐘，讀請求將不再發(fā)送給它，直到該區(qū)域中的實例數(shù)據(jù)已經(jīng)正常寫入 26 小時為止。
在每個區(qū)域內(nèi)部，一種基于 Paxos 的 ShardManager 用于維護分片與節(jié)點之間的關系。當一個節(jié)點發(fā)生故障時，ShardManager 會將它維護的分片重新分配給集群內(nèi)部的其它節(jié)點。分片轉(zhuǎn)移通常能夠在 30 秒內(nèi)完成，在分片轉(zhuǎn)移的過程中，寫入數(shù)據(jù)的客戶端將緩存待寫入的數(shù)據(jù)，并且最多緩存最近 1 分鐘的數(shù)據(jù)。當客戶端發(fā)現(xiàn)分片轉(zhuǎn)移操作執(zhí)行完時，客戶端會立即掏空緩存，將數(shù)據(jù)寫入到節(jié)點中。如果分片轉(zhuǎn)移速度太慢，讀請求可以被手動或自動地轉(zhuǎn)發(fā)到另一個區(qū)域。
當新的分片被分配給一個節(jié)點時，該節(jié)點需要從 GlusterFS 中讀入所有數(shù)據(jù)。通常加載和預處理這些數(shù)據(jù)需要 5 分鐘。當該節(jié)點正在恢復數(shù)據(jù)時，新寫入的時序樣本數(shù)據(jù)會被放入一個待處理隊列。在老節(jié)點發(fā)生故障后，新節(jié)點加載分片數(shù)據(jù)完畢之前，讀請求可能會讀到部分數(shù)據(jù)，并打上標記。如果客戶端發(fā)現(xiàn)數(shù)據(jù)被標記為部分數(shù)據(jù)，會再次請求另一個區(qū)域中的數(shù)據(jù)，如果數(shù)據(jù)完整則返回后者，失敗則返回兩組部分數(shù)據(jù)。
最后，F(xiàn)B 仍然使用 HBase TSDB 來存儲長期數(shù)據(jù)，工程師仍然可以通過它來分析過去的時序數(shù)據(jù)。
NewTools on Gorilla
由于 Gorilla 的數(shù)據(jù)存放在內(nèi)存中，這樣讓更多的實時分析成為可能。
相關性分析引擎，主要用于快速發(fā)現(xiàn)相關性很高的時序數(shù)據(jù)，從而輔助根源分析 監(jiān)控繪圖 聚合分析
論文地址：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