從零寫一個時間序列資料庫

編者按：Prometheus 是 CNCF 旗下的開源監控告警解決方案，它已經成為 Kubernetes 生態圈中的核心監控系統。本文作者 Fabian Reinartz 是 Prometheus 的核心開發者，這篇文章是其於 2017 年寫的一篇關於 Prometheus 中的時間序列資料庫的設計思考，雖然寫作時間有點久了，但是其中的考慮和思路非常值得參考。長文預警，請坐下來慢慢品味。

我從事監控工作。特別是在 Prometheus 上，監控系統包含一個自定義的時間序列資料庫，並且整合在 Kubernetes 上。

在許多方面上 Kubernetes 展現出了 Prometheus 所有的設計用途。它使得持續部署continuous deployments，彈性伸縮auto scaling和其他高動態環境highly dynamic environments下的功能可以輕易地存取。查詢語句和操作模型以及其它概念決策使得 Prometheus 特別適合這種環境。但是，如果監控的工作負載動態程度顯著地增加，這就會給監控系統本身帶來新的壓力。考慮到這一點，我們就可以特別致力於在高動態或瞬態服務transient services環境下提升它的表現，而不是回過頭來解決 Prometheus 已經解決的很好的問題。

Prometheus 的儲存層在歷史以來都展現出卓越的效能，單一伺服器就能夠以每秒數百萬個時間序列的速度攝入多達一百萬個樣本，同時只佔用了很少的磁碟空間。儘管當前的儲存做的很好，但我依舊提出一個新設計的儲存子系統，它可以修正現存解決方案的缺點，並具備處理更大規模資料的能力。

備註：我沒有資料庫方面的背景。我說的東西可能是錯的並讓你誤入歧途。你可以在 Freenode 的 #prometheus 頻道上對我（fabxc）提出你的批評。

問題，難題，問題域

首先，快速地概覽一下我們要完成的東西和它的關鍵難題。我們可以先看一下 Prometheus 當前的做法 ，它為什麼做的這麼好，以及我們打算用新設計解決哪些問題。

時間序列資料

我們有一個收集一段時間資料的系統。

identifier -> (t0, v0), (t1, v1), (t2, v2), (t3, v3), ....

每個資料點是一個時間戳和值的元組。在監控中，時間戳是一個整數，值可以是任意數位。64 位浮點數對於計數器和測量值來說是一個好的表示方法，因此我們將會使用它。一系列嚴格單調遞增的時間戳資料點是一個序列，它由識別符號所參照。我們的識別符號是一個帶有標籤維度label dimensions字典的度量名稱。標籤維度劃分了單一指標的測量空間。每一個指標名稱加上一個唯一標籤集就成了它自己的時間序列，它有一個與之關聯的資料流value stream。

這是一個典型的序列識別符號series identifier集，它是統計請求指標的一部分：

requests_total{path="/status", method="GET", instance=”10.0.0.1:80”}requests_total{path="/status", method="POST", instance=”10.0.0.3:80”}requests_total{path="/", method="GET", instance=”10.0.0.2:80”}

讓我們簡化一下表示方法：度量名稱可以當作另一個維度標籤，在我們的例子中是 __name__。對於查詢語句，可以對它進行特殊處理，但與我們儲存的方式無關，我們後面也會見到。

{__name__="requests_total", path="/status", method="GET", instance=”10.0.0.1:80”}{__name__="requests_total", path="/status", method="POST", instance=”10.0.0.3:80”}{__name__="requests_total", path="/", method="GET", instance=”10.0.0.2:80”}

我們想通過標籤來查詢時間序列資料。在最簡單的情況下，使用 {__name__="requests_total"} 選擇所有屬於 requests_total 指標的資料。對於所有選擇的序列，我們在給定的時間視窗內獲取資料點。

在更複雜的語句中，我們或許想一次性選擇滿足多個標籤的序列，並且表示比相等條件更複雜的情況。例如，非語句（method!="GET"）或正規表示式匹配（method=~"PUT|POST"）。

這些在很大程度上定義了儲存的資料和它的獲取方式。

縱與橫

在簡化的檢視中，所有的資料點可以分布在二維平面上。水平維度代表著時間，序列識別符號域經縱軸展開。

series  ^     |   . . . . . . . . . . . . . . . . .   . . . . .   {__name__="request_total", method="GET"}  |     . . . . . . . . . . . . . . . . . . . . . .   {__name__="request_total", method="POST"}  |         . . . . . . .  |       . . .     . . . . . . . . . . . . . . . .                  ...   |     . . . . . . . . . . . . . . . . .   . . . .     |     . . . . . . . . . .   . . . . . . . . . . .   {__name__="errors_total", method="POST"}  |           . . .   . . . . . . . . .   . . . . .   {__name__="errors_total", method="GET"}  |         . . . . . . . . .       . . . . .  |       . . .     . . . . . . . . . . . . . . . .                  ...   |     . . . . . . . . . . . . . . . .   . . . .   v    <-------------------- time --------------------->

Prometheus 通過定期地抓取一組時間序列的當前值來獲取資料點。我們從中獲取到的實體稱為目標。因此，寫入模式完全地垂直且高度並行，因為來自每個目標的樣本是獨立攝入的。

這裡提供一些測量的規模：單一 Prometheus 範例從數萬個目標中收集資料點，每個資料點都暴露在數百到數千個不同的時間序列中。

在每秒採集數百萬資料點這種規模下，批次寫入是一個不能妥協的效能要求。在磁碟上分散地寫入單個資料點會相當地緩慢。因此，我們想要按順序寫入更大的資料塊。

對於旋轉式磁碟，它的磁頭始終得在物理上向不同的磁區上移動，這是一個不足為奇的事實。而雖然我們都知道 SSD 具有快速隨機寫入的特點，但事實上它不能修改單個位元組，只能寫入一頁或更多頁的 4KiB 資料量。這就意味著寫入 16 位元組的樣本相當於寫入滿滿一個 4Kib 的頁。這一行為就是所謂的寫入放大，這種特性會損耗你的 SSD。因此它不僅影響速度，而且還毫不誇張地在幾天或幾個週內破壞掉你的硬體。

關於此問題更深層次的資料，“Coding for SSDs”系列部落格是極好的資源。讓我們想想主要的用處：順序寫入和批次寫入分別對於旋轉式磁碟和 SSD 來說都是理想的寫入模式。大道至簡。

查詢模式比起寫入模式明顯更不同。我們可以查詢單一序列的一個資料點，也可以對 10000 個序列查詢一個資料點，還可以查詢一個序列幾個週的資料點，甚至是 10000 個序列幾個週的資料點。因此在我們的二維平面上，查詢範圍不是完全水平或垂直的，而是二者形成矩形似的組合。

記錄規則可以減輕已知查詢的問題，但對於對等ad-hoc查詢來說並不是一個通用的解決方法。

我們知道我們想要批次地寫入，但我們得到的僅僅是一系列垂直資料點的集合。當查詢一段時間視窗內的資料點時，我們不僅很難弄清楚在哪才能找到這些單獨的點，而且不得不從磁碟上大量隨機的地方讀取。也許一條查詢語句會有數百萬的樣本，即使在最快的 SSD 上也會很慢。讀入也會從磁碟上獲取更多的資料而不僅僅是 16 位元組的樣本。SSD 會載入一整頁，HDD 至少會讀取整個磁區。不論哪一種，我們都在浪費寶貴的讀取吞吐量。

因此在理想情況下，同一序列的樣本將按順序儲存，這樣我們就能通過儘可能少的讀取來掃描它們。最重要的是，我們僅需要知道序列的起始位置就能存取所有的資料點。

顯然，將收集到的資料寫入磁碟的理想模式與能夠顯著提高查詢效率的布局之間存在著明顯的抵觸。這是我們 TSDB 需要解決的一個基本問題。

當前的解決方法

是時候看一下當前 Prometheus 是如何儲存資料來解決這一問題的，讓我們稱它為“V2”。

我們建立一個時間序列的檔案，它包含所有樣本並按順序儲存。因為每幾秒附加一個樣本資料到所有檔案中非常昂貴，我們在記憶體中打包 1Kib 樣本序列的資料塊，一旦打包完成就附加這些資料塊到單獨的檔案中。這一方法解決了大部分問題。寫入目前是批次的，樣本也是按順序儲存的。基於給定的同一序列的樣本相對之前的資料僅發生非常小的改變這一特性，它還支援非常高效的壓縮格式。Facebook 在他們 Gorilla TSDB 上的論文中描述了一個相似的基於資料塊的方法，並且引入了一種壓縮格式，它能夠減少 16 位元組的樣本到平均 1.37 位元組。V2 儲存使用了包含 Gorilla 變體等在內的各種壓縮格式。

   +----------+---------+---------+---------+---------+           series A   +----------+---------+---------+---------+---------+          +----------+---------+---------+---------+---------+    series B          +----------+---------+---------+---------+---------+                               . . . +----------+---------+---------+---------+---------+---------+   series XYZ +----------+---------+---------+---------+---------+---------+    chunk 1    chunk 2   chunk 3     ...

儘管基於塊儲存的方法非常棒，但為每個序列儲存一個獨立的檔案會給 V2 儲存帶來麻煩，因為：

• 實際上，我們需要的檔案比當前收集資料的時間序列數量要多得多。多出的部分在序列分流Series Churn上。有幾百萬個檔案，遲早會使用光檔案系統中的 inode。這種情況我們只能通過重新格式化來恢復磁碟，這種方式是最具有破壞性的。我們通常不想為了適應一個應用程式而格式化磁碟。
• 即使是分塊寫入，每秒也會產生數千塊的資料塊並且準備持久化。這依然需要每秒數千次的磁碟寫入。儘管通過為每個序列打包好多個塊來緩解，但這反過來還是增加了等待持久化資料的總記憶體占用。
• 要保持所有檔案開啟來進行讀寫是不可行的。特別是因為 99% 的資料在 24 小時之後不再會被查詢到。如果查詢它，我們就得開啟數千個檔案，找到並讀取相關的資料點到記憶體中，然後再關掉。這樣做就會引起很高的查詢延遲，資料塊快取加劇會導致新的問題，這一點在“資源消耗”一節另作講述。
• 最終，舊的資料需要被刪除，並且資料需要從數百萬檔案的頭部刪除。這就意味著刪除實際上是寫密集型操作。此外，迴圈遍歷數百萬檔案並且進行分析通常會導致這一過程花費數小時。當它完成時，可能又得重新來過。喔天，繼續刪除舊檔案又會進一步導致 SSD 產生寫入放大。
• 目前所積累的資料塊僅維持在記憶體中。如果應用崩潰，資料就會丟失。為了避免這種情況，記憶體狀態會定期的儲存在磁碟上，這比我們能接受資料丟失視窗要長的多。恢復檢查點也會花費數分鐘，導致很長的重新啟動週期。

我們能夠從現有的設計中學到的關鍵部分是資料塊的概念，我們當然希望保留這個概念。最新的資料塊會保持在記憶體中一般也是好的主意。畢竟，最新的資料會大量的查詢到。

一個時間序列對應一個檔案，這個概念是我們想要替換掉的。

序列分流

在 Prometheus 的上下文context中，我們使用術語序列分流series churn來描述一個時間序列集合變得不活躍，即不再接收資料點，取而代之的是出現一組新的活躍序列。

例如，由給定微服務範例產生的所有序列都有一個相應的“instance”標籤來標識其來源。如果我們為微服務執行了捲動更新rolling update，並且為每個範例替換一個新的版本，序列分流便會發生。在更加動態的環境中，這些事情基本上每小時都會發生。像 Kubernetes 這樣的叢集編排Cluster orchestration系統允許應用連續性的自動伸縮和頻繁的捲動更新，這樣也許會建立成千上萬個新的應用程式範例，並且伴隨著全新的時間序列集合，每天都是如此。

series  ^  |   . . . . . .  |   . . . . . .  |   . . . . . .  |               . . . . . . .  |               . . . . . . .  |               . . . . . . .  |                             . . . . . .  |                             . . . . . .  |                                         . . . . .  |                                         . . . . .  |                                         . . . . .  v    <-------------------- time --------------------->

所以即便整個基礎設施的規模基本保持不變，過一段時間後資料庫內的時間序列還是會成線性增長。儘管 Prometheus 很願意採集 1000 萬個時間序列資料，但要想在 10 億個序列中找到資料，查詢效果還是會受到嚴重的影響。

當前解決方案

當前 Prometheus 的 V2 儲存系統對所有當前儲存的序列擁有基於 LevelDB 的索引。它允許查詢語句含有給定的標籤對label pair，但是缺乏可伸縮的方法來從不同的標籤選集中組合查詢結果。

例如，從所有的序列中選擇標籤 __name__="requests_total" 非常高效，但是選擇  instance="A" AND __name__="requests_total" 就有了可伸縮性的問題。我們稍後會重新考慮導致這一點的原因和能夠提升查詢延遲的調整方法。

事實上正是這個問題才催生出了對更好的儲存系統的最初探索。Prometheus 需要為查詢億萬個時間序列改進索引方法。

資源消耗

當試圖擴充套件 Prometheus（或其他任何事情，真的）時，資源消耗是永恆不變的話題之一。但真正困擾使用者的並不是對資源的絕對渴求。事實上，由於給定的需求，Prometheus 管理著令人難以置信的吞吐量。問題更在於面對變化時的相對未知性與不穩定性。通過其架構設計，V2 儲存系統緩慢地構建了樣本資料塊，這一點導致記憶體占用隨時間遞增。當資料塊完成之後，它們可以寫到磁碟上並從記憶體中清除。最終，Prometheus 的記憶體使用到達穩定狀態。直到監測環境發生了改變——每次我們擴充套件應用或者進行捲動更新，序列分流都會增加記憶體、CPU、磁碟 I/O 的使用。

如果變更正在進行，那麼它最終還是會到達一個穩定的狀態，但比起更加靜態的環境，它的資源消耗會顯著地提高。過渡時間通常為數個小時，而且難以確定最大資源使用量。

為每個時間序列儲存一個檔案這種方法也使得一個單個查詢就很容易崩潰 Prometheus 進程。當查詢的資料沒有快取在記憶體中，查詢的序列檔案就會被開啟，然後將含有相關資料點的資料塊讀入記憶體。如果資料量超出記憶體可用量，Prometheus 就會因 OOM 被殺死而退出。

在查詢語句完成之後，載入的資料便可以被再次釋放掉，但通常會快取更長的時間，以便更快地查詢相同的資料。後者看起來是件不錯的事情。

最後，我們看看之前提到的 SSD 的寫入放大，以及 Prometheus 是如何通過批次寫入來解決這個問題的。儘管如此，在許多地方還是存在因為批次太小以及資料未精確對齊頁邊界而導致的寫入放大。對於更大規模的 Prometheus 伺服器，現實當中會發現縮減硬體壽命的問題。這一點對於高寫入吞吐量的資料庫應用來說仍然相當普遍，但我們應該放眼看看是否可以解決它。

重新開始

到目前為止我們對於問題域、V2 儲存系統是如何解決它的，以及設計上存在的問題有了一個清晰的認識。我們也看到了許多很棒的想法，這些或多或少都可以拿來直接使用。V2 儲存系統相當數量的問題都可以通過改進和部分的重新設計來解決，但為了好玩（當然，在我仔細的驗證想法之後），我決定試著寫一個完整的時間序列資料庫——從頭開始，即向檔案系統寫入位元組。

效能與資源使用這種最關鍵的部分直接影響了儲存格式的選取。我們需要為資料找到正確的演算法和磁碟布局來實現一個高效能的儲存層。

這就是我解決問題的捷徑——跳過令人頭疼、失敗的想法，數不盡的草圖，淚水與絕望。

V3—宏觀設計

我們儲存系統的宏觀布局是什麼？簡而言之，是當我們在資料資料夾裡執行 tree 命令時顯示的一切。看看它能給我們帶來怎樣一副驚喜的畫面。

$ tree ./data./data+-- b-000001|   +-- chunks|   |   +-- 000001|   |   +-- 000002|   |   +-- 000003|   +-- index|   +-- meta.json+-- b-000004|   +-- chunks|   |   +-- 000001|   +-- index|   +-- meta.json+-- b-000005|   +-- chunks|   |   +-- 000001|   +-- index|   +-- meta.json+-- b-000006    +-- meta.json    +-- wal        +-- 000001        +-- 000002        +-- 000003

在最頂層，我們有一系列以 b- 為字首編號的塊block。每個塊中顯然儲存了索引檔案和含有更多編號檔案的 chunk 資料夾。chunks 目錄只包含不同序列資料點的原始塊raw chunks of data points。與 V2 儲存系統一樣，這使得通過時間視窗讀取序列資料非常高效並且允許我們使用相同的有效壓縮演算法。這一點被證實行之有效，我們也打算沿用。顯然，這裡並不存在含有單個序列的檔案，而是一堆儲存著許多序列的資料塊。

index 檔案的存在應該不足為奇。讓我們假設它擁有黑魔法，可以讓我們找到標籤、可能的值、整個時間序列和存放資料點的資料塊。

但為什麼這裡有好幾個資料夾都是索引和塊檔案的布局？並且為什麼存在最後一個包含 wal 資料夾？理解這兩個疑問便能解決九成的問題。

許多小型資料庫

我們分割橫軸，即將時間域分割為不重疊的塊。每一塊扮演著完全獨立的資料庫，它包含該時間視窗所有的時間序列資料。因此，它擁有自己的索引和一系列塊檔案。

t0            t1             t2             t3             now +-----------+  +-----------+  +-----------+  +-----------+ |           |  |           |  |           |  |           |                 +------------+ |           |  |           |  |           |  |  mutable  | <--- write ---- ┤ Prometheus | |           |  |           |  |           |  |           |                 +------------+ +-----------+  +-----------+  +-----------+  +-----------+                        ^       +--------------+-------+------+--------------+                              |                              |                                                  query                              |                                                    |                            merge -------------------------------------------------+

每一塊的資料都是不可變的immutable。當然，當我們採集新資料時，我們必須能向最近的塊中新增新的序列和樣本。對於該資料塊，所有新的資料都將寫入記憶體中的資料庫中，它與我們的持久化的資料塊一樣提供了查詢屬性。記憶體中的資料結構可以高效地更新。為了防止資料丟失，所有傳入的資料同樣被寫入臨時的預寫紀錄檔write ahead log中，這就是 wal 資料夾中的一些列檔案，我們可以在重新啟動時通過它們重新填充記憶體資料庫。

所有這些檔案都帶有序列化格式，有我們所期望的所有東西：許多標誌、偏移量、變體和 CRC32 校驗和。紙上得來終覺淺，絕知此事要躬行。

這種布局允許我們擴充套件查詢範圍到所有相關的塊上。每個塊上的部分結果最終合併成完整的結果。

這種橫向分割增加了一些很棒的功能：

• 當查詢一個時間範圍，我們可以簡單地忽略所有範圍之外的資料塊。通過減少需要檢查的資料集，它可以初步解決序列分流的問題。
• 當完成一個塊，我們可以通過順序的寫入大檔案從記憶體資料庫中儲存資料。這樣可以避免任何的寫入放大，並且 SSD 與 HDD 均適用。
• 我們延續了 V2 儲存系統的一個好的特性，最近使用而被多次查詢的資料塊，總是保留在記憶體中。
• 很好，我們也不再受限於 1KiB 的資料塊尺寸，以使資料在磁碟上更好地對齊。我們可以挑選對單個資料點和壓縮格式最合理的尺寸。
• 刪除舊資料變得極為簡單快捷。我們僅僅只需刪除一個資料夾。記住，在舊的儲存系統中我們不得不花數個小時分析並重寫數億個檔案。

每個塊還包含了 meta.json 檔案。它簡單地儲存了關於塊的儲存狀態和包含的資料，以便輕鬆了解儲存狀態及其包含的資料。

mmap

將數百萬個小檔案合併為少數幾個大檔案使得我們用很小的開銷就能保持所有的檔案都開啟。這就解除了對 mmap(2) 的使用的阻礙，這是一個允許我們通過檔案透明地回傳虛擬記憶體的系統呼叫。簡單起見，你可以將其視為交換空間swap space，只是我們所有的資料已經儲存在了磁碟上，並且當資料換出記憶體後不再會發生寫入。

這意味著我們可以當作所有資料庫的內容都視為在記憶體中卻不佔用任何實體記憶體。僅當我們存取資料庫檔案某些位元組範圍時，作業系統才會從磁碟上惰性載入lazy load頁資料。這使得我們將所有資料持久化相關的記憶體管理都交給了作業系統。通常，作業系統更有資格作出這樣的決定，因為它可以全面了解整個機器和進程。查詢的資料可以相當積極的快取進記憶體，但記憶體壓力會使得頁被換出。如果機器擁有未使用的記憶體，Prometheus 目前將會高興地快取整個資料庫，但是一旦其他進程需要，它就會立刻返回那些記憶體。

因此，查詢不再輕易地使我們的進程 OOM，因為查詢的是更多的持久化的資料而不是裝入記憶體中的資料。記憶體快取大小變得完全自適應，並且僅當查詢真正需要時資料才會被載入。

就個人理解，這就是當今大多數資料庫的工作方式，如果磁碟格式允許，這是一種理想的方式，——除非有人自信能在這個過程中超越作業系統。我們做了很少的工作但確實從外面獲得了很多功能。

壓縮

儲存系統需要定期“切”出新塊並將之前完成的塊寫入到磁碟中。僅在塊成功的持久化之後，才會被刪除之前用來恢復記憶體塊的紀錄檔檔案（wal）。

我們希望將每個塊的儲存時間設定的相對短一些（通常設定為 2 小時），以避免記憶體中積累太多的資料。當查詢多個塊，我們必須將它們的結果合併為一個整體的結果。合併過程顯然會消耗資源，一個星期的查詢不應該由超過 80 個的部分結果所組成。

為了實現兩者，我們引入壓縮compaction。壓縮描述了一個過程：取一個或更多個資料塊並將其寫入一個可能更大的塊中。它也可以在此過程中修改現有的資料。例如，清除已經刪除的資料，或重建樣本塊以提升查詢效能。

t0             t1            t2             t3             t4             now +------------+  +----------+  +-----------+  +-----------+  +-----------+ | 1          |  | 2        |  | 3         |  | 4         |  | 5 mutable |    before +------------+  +----------+  +-----------+  +-----------+  +-----------+ +-----------------------------------------+  +-----------+  +-----------+ | 1              compacted                |  | 4         |  | 5 mutable |    after (option A) +-----------------------------------------+  +-----------+  +-----------+ +--------------------------+  +--------------------------+  +-----------+ | 1       compacted        |  | 3      compacted         |  | 5 mutable |    after (option B) +--------------------------+  +--------------------------+  +-----------+

在這個例子中我們有順序塊 [1,2,3,4]。塊 1、2、3 可以壓縮在一起，新的布局將會是 [1,4]。或者，將它們成對壓縮為 [1,3]。所有的時間序列資料仍然存在，但現在整體上儲存在更少的塊中。這極大程度地縮減了查詢時間的消耗，因為需要合併的部分查詢結果變得更少了。

保留

我們看到了刪除舊的資料在 V2 儲存系統中是一個緩慢的過程，並且消耗 CPU、記憶體和磁碟。如何才能在我們基於塊的設計上清除舊的資料？相當簡單，只要刪除我們設定的保留時間視窗裡沒有資料的塊資料夾即可。在下面的例子中，塊 1 可以被安全地刪除，而塊 2 則必須一直保留，直到它落在保留視窗邊界之外。

                      | +------------+  +----+-----+  +-----------+  +-----------+  +-----------+ | 1          |  | 2  |     |  | 3         |  | 4         |  | 5         |   . . . +------------+  +----+-----+  +-----------+  +-----------+  +-----------+                      |                      |             retention boundary

隨著我們不斷壓縮先前壓縮的塊，舊資料越大，塊可能變得越大。因此必須為其設定一個上限，以防資料塊擴充套件到整個資料庫而損失我們設計的最初優勢。

方便的是，這一點也限制了部分存在於保留視窗內部分存在於保留視窗外的塊的磁碟消耗總量。例如上面例子中的塊 2。當設定了最大塊尺寸為總保留視窗的 10% 後，我們保留塊 2 的總開銷也有了 10% 的上限。

總結一下，保留與刪除從非常昂貴到了幾乎沒有成本。

如果你讀到這裡並有一些資料庫的背景知識，現在你也許會問：這些都是最新的技術嗎？——並不是；而且可能還會做的更好。

在記憶體中批次處理資料，在預寫紀錄檔中跟蹤，並定期寫入到磁碟的模式在現在相當普遍。

我們看到的好處無論在什麼領域的資料裡都是適用的。遵循這一方法最著名的開源案例是 LevelDB、Cassandra、InfluxDB 和 HBase。關鍵是避免重複發明劣質的輪子，採用經過驗證的方法，並正確地運用它們。

脫離場景新增你自己的黑魔法是一種不太可能的情況。

索引

研究儲存改進的最初想法是解決序列分流的問題。基於塊的布局減少了查詢所要考慮的序列總數。因此假設我們索引查詢的複雜度是 O(n^2)，我們就要設法減少 n 個相當數量的複雜度，之後就相當於改進 O(n^2) 複雜度。——恩，等等……糟糕。

快速回顧一下“演算法 101”課上提醒我們的，在理論上它並未帶來任何好處。如果之前就很糟糕，那麼現在也一樣。理論是如此的殘酷。

實際上，我們大多數的查詢已經可以相當快響應。但是，跨越整個時間範圍的查詢仍然很慢，儘管只需要找到少部分資料。追溯到所有這些工作之前，最初我用來解決這個問題的想法是：我們需要一個更大容量的倒排索引。

倒排索引基於資料項內容的子集提供了一種快速的查詢方式。簡單地說，我可以通過標籤 app="nginx" 查詢所有的序列而無需遍歷每個檔案來看它是否包含該標籤。

為此，每個序列被賦上一個唯一的 ID ，通過該 ID 可以恆定時間內檢索它（O(1)）。在這個例子中 ID 就是我們的正向索引。

範例：如果 ID 為 10、29、9 的序列包含標籤 app="nginx"，那麼 “nginx”的倒排索引就是簡單的列表 [10, 29, 9]，它就能用來快速地獲取所有包含標籤的序列。即使有 200 多億個資料序列也不會影響查詢速度。

簡而言之，如果 n 是我們序列總數，m 是給定查詢結果的大小，使用索引的查詢複雜度現在就是 O(m)。查詢語句依據它獲取資料的數量 m 而不是被搜尋的資料體 n 進行縮放是一個很好的特性，因為 m 一般相當小。

為了簡單起見，我們假設可以在恆定時間內查詢到倒排索引對應的列表。

實際上，這幾乎就是 V2 儲存系統具有的倒排索引，也是提供在數百萬序列中查詢效能的最低需求。敏銳的人會注意到，在最壞情況下，所有的序列都含有標籤，因此 m 又成了 O(n)。這一點在預料之中，也相當合理。如果你查詢所有的資料，它自然就會花費更多時間。一旦我們牽扯上了更複雜的查詢語句就會有問題出現。

標籤組合

與數百萬個序列相關的標籤很常見。假設橫向擴充套件著數百個範例的“foo”微服務，並且每個範例擁有數千個序列。每個序列都會帶有標籤 app="foo"。當然，使用者通常不會查詢所有的序列而是會通過進一步的標籤來限制查詢。例如，我想知道服務範例接收到了多少請求，那麼查詢語句便是 __name__="requests_total" AND app="foo"。

為了找到滿足兩個標籤選擇子的所有序列，我們得到每一個標籤的倒排索引列表並取其交集。結果集通常會比任何一個輸入列表小一個數量級。因為每個輸入列表最壞情況下的大小為 O(n)，所以在巢狀地為每個列表進行暴力求解brute force solution下，執行時間為 O(n^2)。相同的成本也適用於其他的集合操作，例如取並集（app="foo" OR app="bar"）。當在查詢語句上新增更多標籤選擇子，耗費就會指數增長到 O(n^3)、O(n^4)、O(n^5)……O(n^k)。通過改變執行順序，可以使用很多技巧以優化執行效率。越複雜，越是需要關於資料特徵和標籤之間相關性的知識。這引入了大量的複雜度，但是並沒有減少演算法的最壞執行時間。

這便是 V2 儲存系統使用的基本方法，幸運的是，看似微小的改動就能獲得顯著的提升。如果我們假設倒排索引中的 ID 都是排序好的會怎麼樣？

假設這個例子的列表用於我們最初的查詢：

__name__="requests_total"   ->   [ 9999, 1000, 1001, 2000000, 2000001, 2000002, 2000003 ]     app="foo"              ->   [ 1, 3, 10, 11, 12, 100, 311, 320, 1000, 1001, 10002 ]             intersection   =>   [ 1000, 1001 ]

它的交集相當小。我們可以為每個列表的起始位置設定游標，每次從最小的游標處移動來找到交集。當二者的數位相等，我們就新增它到結果中並移動二者的游標。總體上，我們以鋸齒形掃描兩個列表，因此總耗費是 O(2n)=O(n)，因為我們總是在一個列表上移動。

兩個以上列表的不同集合操作也類似。因此 k 個集合操作僅僅改變了因子 O(k*n) 而不是最壞情況下查詢執行時間的指數 O(n^k)。

我在這裡所描述的是幾乎所有全文搜尋引擎使用的標準搜尋索引的簡化版本。每個序列描述符都視作一個簡短的“文件”，每個標籤（名稱 + 固定值）作為其中的“單詞”。我們可以忽略搜尋引擎索引中通常遇到的很多附加資料，例如單詞位置和和頻率。

關於改進實際執行時間的方法似乎存在無窮無盡的研究，它們通常都是對輸入資料做一些假設。不出意料的是，還有大量技術來壓縮倒排索引，其中各有利弊。因為我們的“文件”比較小，而且“單詞”在所有的序列裡大量重複，壓縮變得幾乎無關緊要。例如，一個真實的資料集約有 440 萬個序列與大約 12 個標籤，每個標籤擁有少於 5000 個單獨的標籤。對於最初的儲存版本，我們堅持使用基本的方法而不壓縮，僅做微小的調整來跳過大範圍非交叉的 ID。

儘管維持排序好的 ID 聽起來很簡單，但實踐過程中不是總能完成的。例如，V2 儲存系統為新的序列賦上一個雜湊值來當作 ID，我們就不能輕易地排序倒排索引。

另一個艱鉅的任務是當磁碟上的資料被更新或刪除掉後修改其索引。通常，最簡單的方法是重新計算並寫入，但是要保證資料庫在此期間可查詢且具有一致性。V3 儲存系統通過每塊上具有的獨立不可變索引來解決這一問題，該索引僅通過壓縮時的重寫來進行修改。只有可變塊上的索引需要被更新，它完全儲存在記憶體中。

基準測試

我從儲存的基準測試開始了初步的開發，它基於現實世界資料集中提取的大約 440 萬個序列描述符，並生成合成資料點以輸入到這些序列中。這個階段的開發僅僅測試了單獨的儲存系統，對於快速找到效能瓶頸和高並行負載場景下的觸發死鎖至關重要。

在完成概念性的開發實施之後，該基準測試能夠在我的 Macbook Pro 上維持每秒 2000 萬的吞吐量 —— 並且這都是在開啟著十幾個 Chrome 的頁面和 Slack 的時候。因此，儘管這聽起來都很棒，它這也表明推動這項測試沒有的進一步價值（或者是沒有在高隨機環境下執行）。畢竟，它是合成的資料，因此在除了良好的第一印象外沒有多大價值。比起最初的設計目標高出 20 倍，是時候將它部署到真正的 Prometheus 伺服器上了，為它新增更多現實環境中的開銷和場景。

我們實際上沒有可重現的 Prometheus 基準測試設定，特別是沒有對於不同版本的 A/B 測試。亡羊補牢為時不晚，不過現在就有一個了！

我們的工具可以讓我們宣告性地定義基準測試場景，然後部署到 AWS 的 Kubernetes 叢集上。儘管對於全面的基準測試來說不是最好環境，但它肯定比 64 核 128GB 記憶體的專用裸機伺服器bare metal servers更能反映出我們的使用者群體。

我們部署了兩個 Prometheus 1.5.2 伺服器（V2 儲存系統）和兩個來自 2.0 開發分支的 Prometheus （V3 儲存系統）。每個 Prometheus 執行在配備 SSD 的專用伺服器上。我們將橫向擴充套件的應用部署在了工作節點上，並且讓其暴露典型的微服務度量。此外，Kubernetes 叢集本身和節點也被監控著。整套系統由另一個 Meta-Prometheus 所監督，它監控每個 Prometheus 的健康狀況和效能。

為了模擬序列分流，微服務定期的擴充套件和收縮來移除舊的 pod 並衍生新的 pod，生成新的序列。通過選擇“典型”的查詢來模擬查詢負載，對每個 Prometheus 版本都執行一次。

總體上，伸縮與查詢的負載以及取樣頻率極大的超出了 Prometheus 的生產部署。例如，我們每隔 15 分鐘換出 60% 的微服務範例去產生序列分流。在現代的基礎設施上，一天僅大約會發生 1-5 次。這就保證了我們的 V3 設計足以處理未來幾年的工作負載。就結果而言，Prometheus 1.5.2 和 2.0 之間的效能差異在極端的環境下會變得更大。

總而言之，我們每秒從 850 個目標裡收集大約 11 萬份樣本，每次暴露 50 萬個序列。

在此系統執行一段時間之後，我們可以看一下數位。我們評估了兩個版本在 12 個小時之後到達穩定時的幾個指標。

請注意從 Prometheus 圖形介面的截圖中輕微截斷的 Y 軸

堆記憶體使用（GB）

記憶體資源的使用對使用者來說是最為困擾的問題，因為它相對的不可預測且可能導致進程崩潰。

顯然，查詢的伺服器正在消耗記憶體，這很大程度上歸咎於查詢引擎的開銷，這一點可以當作以後優化的主題。總的來說，Prometheus 2.0 的記憶體消耗減少了 3-4 倍。大約 6 小時之後，在 Prometheus 1.5 上有一個明顯的峰值，與我們設定的 6 小時的保留邊界相對應。因為刪除操作成本非常高，所以資源消耗急劇提升。這一點在下面幾張圖中均有體現。

CPU 使用（核心/秒）

類似的模式也體現在 CPU 使用上，但是查詢的伺服器與非查詢的伺服器之間的差異尤為明顯。每秒獲取大約 11 萬個資料需要 0.5 核心/秒的 CPU 資源，比起評估查詢所花費的 CPU 時間，我們的新儲存系統 CPU 消耗可忽略不計。總的來說，新儲存需要的 CPU 資源減少了 3 到 10 倍。

磁碟寫入（MB/秒）

迄今為止最引人注目和意想不到的改進表現在我們的磁碟寫入利用率上。這就清楚的說明了為什麼 Prometheus 1.5 很容易造成 SSD 損耗。我們看到最初的上升發生在第一個塊被持久化到序列檔案中的時期，然後一旦刪除操作引發了重寫就會帶來第二個上升。令人驚訝的是，查詢的伺服器與非查詢的伺服器顯示出了非常不同的利用率。

在另一方面，Prometheus 2.0 每秒僅向其預寫紀錄檔寫入大約一兆位元組。當塊被壓縮到磁碟時，寫入定期地出現峰值。這在總體上節省了：驚人的 97-99%。

磁碟大小（GB）

與磁碟寫入密切相關的是總磁碟空間佔用量。由於我們對樣本（這是我們的大部分資料）幾乎使用了相同的壓縮演算法，因此磁碟佔用量應當相同。在更為穩定的系統中，這樣做很大程度上是正確地，但是因為我們需要處理高的序列分流，所以還要考慮每個序列的開銷。

如我們所見，Prometheus 1.5 在這兩個版本達到穩定狀態之前，使用的儲存空間因其保留操作而急速上升。Prometheus 2.0 似乎在每個序列上的開銷顯著降低。我們可以清楚的看到預寫紀錄檔線性地充滿整個儲存空間，然後當壓縮完成後瞬間下降。事實上對於兩個 Prometheus 2.0 伺服器，它們的曲線並不是完全匹配的，這一點需要進一步的調查。

前景大好。剩下最重要的部分是查詢延遲。新的索引應當優化了查詢的複雜度。沒有實質上發生改變的是處理資料的過程，例如 rate() 函數或聚合。這些就是查詢引擎要做的東西了。

第 99 個百分位查詢延遲（秒）

資料完全符合預期。在 Prometheus 1.5 上，查詢延遲隨著儲存的序列而增加。只有在保留操作開始且舊的序列被刪除後才會趨於穩定。作為對比，Prometheus 2.0 從一開始就保持在合適的位置。

我們需要花一些心思在資料是如何被採集上，對伺服器發出的查詢請求通過對以下方面的估計來選擇：範圍查詢和即時查詢的組合，進行更輕或更重的計算，存取更多或更少的檔案。它並不需要代表真實世界裡查詢的分布。也不能代表冷資料的查詢效能，我們可以假設所有的樣本資料都是儲存在記憶體中的熱資料。

儘管如此，我們可以相當自信地說，整體查詢效果對序列分流變得非常有彈性，並且在高壓基準測試場景下提升了 4 倍的效能。在更為靜態的環境下，我們可以假設查詢時間大多數花費在了查詢引擎上，改善程度明顯較低。

攝入的樣本/秒

最後，快速地看一下不同 Prometheus 伺服器的攝入率。我們可以看到搭載 V3 儲存系統的兩個伺服器具有相同的攝入速率。在幾個小時之後變得不穩定，這是因為不同的基準測試叢集節點由於高負載變得無響應，與 Prometheus 範例無關。（兩個 2.0 的曲線完全匹配這一事實希望足夠具有說服力）

儘管還有更多 CPU 和記憶體資源，兩個 Prometheus 1.5.2 伺服器的攝入率大大降低。序列分流的高壓導致了無法採集更多的資料。

那麼現在每秒可以攝入的絕對最大absolute maximum樣本數是多少？

但是現在你可以攝取的每秒絕對最大樣本數是多少？

我不知道 —— 雖然這是一個相當容易的優化指標，但除了穩固的基線效能之外，它並不是特別有意義。

有很多因素都會影響 Prometheus 資料流量，而且沒有一個單獨的數位能夠描述捕獲品質。最大攝入率在歷史上是一個導致基準出現偏差的度量，並且忽視了更多重要的層面，例如查詢效能和對序列分流的彈性。關於資源使用線性增長的大致猜想通過一些基本的測試被證實。很容易推斷出其中的原因。

我們的基準測試模擬了高動態環境下 Prometheus 的壓力，它比起真實世界中的更大。結果表明，雖然執行在沒有優化的雲伺服器上，但是已經超出了預期的效果。最終，成功將取決於使用者反饋而不是基準數位。

注意：在撰寫本文的同時，Prometheus 1.6 正在開發當中，它允許更可靠地設定最大記憶體使用量，並且可能會顯著地減少整體的消耗，有利於稍微提高 CPU 使用率。我沒有重複對此進行測試，因為整體結果變化不大，尤其是面對高序列分流的情況。

總結

Prometheus 開始應對高基數序列與單獨樣本的吞吐量。這仍然是一項富有挑戰性的任務，但是新的儲存系統似乎向我們展示了未來的一些好東西。

第一個配備 V3 儲存系統的 alpha 版本 Prometheus 2.0 已經可以用來測試了。在早期階段預計還會出現崩潰，死鎖和其他 bug。

儲存系統的程式碼可以在這個單獨的專案中找到。Prometheus 對於尋找高效本地儲存時間序列資料庫的應用來說可能非常有用，這一點令人非常驚訝。

這裡需要感謝很多人作出的貢獻，以下排名不分先後：

Bjoern Rabenstein 和 Julius Volz 在 V2 儲存引擎上的打磨工作以及 V3 儲存系統的反饋，這為新一代的設計奠定了基礎。

Wilhelm Bierbaum 對新設計不斷的建議與見解作出了很大的貢獻。Brian Brazil 不斷的反饋確保了我們最終得到的是語意上合理的方法。與 Peter Bourgon 深刻的討論驗證了設計並形成了這篇文章。

別忘了我們整個 CoreOS 團隊與公司對於這項工作的贊助與支援。感謝所有那些聽我一遍遍嘮叨 SSD、浮點數、序列化格式的同學。