從零寫一個時間序列資料庫
我從事監控工作。特別是在 Prometheus 上，監控系統包含一個自定義的時間序列資料庫，並且集成在 Kubernetes 上。
在許多方面上 Kubernetes 展現出了 Prometheus 所有的設計用途。它使得 持續部署 ， 彈性伸縮 和其他 高動態環境 下的功能可以輕易地訪問。查詢語句和操作模型以及其它概念決策使得 Prometheus 特別適合這種環境。但是，如果監控的工作負載動態程度顯著地增加，這就會給監控系統本身帶來新的壓力。考慮到這一點，我們就可以特别致力於在高動態或 瞬態服務 環境下提升它的表現，而不是回過頭來解決 Prometheus 已經解決的很好的問題。
Prometheus 的存儲層在歷史以來都展現出卓越的性能，單一伺服器就能夠以每秒數百萬個時間序列的速度攝入多達一百萬個樣本，同時只佔用了很少的磁碟空間。儘管當前的存儲做的很好，但我依舊提出一個新設計的存儲子系統，它可以修正現存解決方案的缺點，並具備處理更大規模數據的能力。
備註：我沒有資料庫方面的背景。我說的東西可能是錯的並讓你誤入歧途。你可以在 Freenode 的 #prometheus 頻道上對我（fabxc）提出你的批評。
問題，難題，問題域
首先，快速地概覽一下我們要完成的東西和它的關鍵難題。我們可以先看一下 Prometheus 當前的做法 ，它為什麼做的這麼好，以及我們打算用新設計解決哪些問題。
時間序列數據
我們有一個收集一段時間數據的系統。
identifier -> (t0, v0), (t1, v1), (t2, v2), (t3, v3), ....每個數據點是一個時間戳和值的元組。在監控中，時間戳是一個整數，值可以是任意數字。64 位浮點數對於計數器和測量值來說是一個好的表示方法，因此我們將會使用它。一系列嚴格單調遞增的時間戳數據點是一個序列，它由標識符所引用。我們的標識符是一個帶有 標籤維度 字典的度量名稱。標籤維度劃分了單一指標的測量空間。每一個指標名稱加上一個唯一標籤集就成了它自己的時間序列，它有一個與之關聯的 數據流 。
這是一個典型的 序列標識符 集，它是統計請求指標的一部分：
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 個序列幾個周的數據點。因此在我們的二維平面上，查詢範圍不是完全水平或垂直的，而是二者形成矩形似的組合。
記錄規則可以減輕已知查詢的問題，但對於 點對點 查詢來說並不是一個通用的解決方法。
我們知道我們想要批量地寫入，但我們得到的僅僅是一系列垂直數據點的集合。當查詢一段時間窗口內的數據點時，我們不僅很難弄清楚在哪才能找到這些單獨的點，而且不得不從磁碟上大量隨機的地方讀取。也許一條查詢語句會有數百萬的樣本，即使在最快的 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 存儲帶來麻煩，因為：
- 實際上，我們需要的文件比當前收集數據的時間序列數量要多得多。多出的部分在 序列分流 上。有幾百萬個文件，遲早會使用光文件系統中的 inode。這種情況我們只能通過重新格式化來恢復磁碟，這種方式是最具有破壞性的。我們通常不想為了適應一個應用程序而格式化磁碟。
- 即使是分塊寫入，每秒也會產生數千塊的數據塊並且準備持久化。這依然需要每秒數千次的磁碟寫入。儘管通過為每個序列打包好多個塊來緩解，但這反過來還是增加了等待持久化數據的總內存佔用。
- 要保持所有文件打開來進行讀寫是不可行的。特別是因為 99% 的數據在 24 小時之後不再會被查詢到。如果查詢它，我們就得打開數千個文件，找到並讀取相關的數據點到內存中，然後再關掉。這樣做就會引起很高的查詢延遲，數據塊緩存加劇會導致新的問題，這一點在「資源消耗」一節另作講述。
- 最終，舊的數據需要被刪除，並且數據需要從數百萬文件的頭部刪除。這就意味著刪除實際上是寫密集型操作。此外，循環遍曆數百萬文件並且進行分析通常會導致這一過程花費數小時。當它完成時，可能又得重新來過。喔天，繼續刪除舊文件又會進一步導致 SSD 產生寫入放大。
- 目前所積累的數據塊僅維持在內存中。如果應用崩潰，數據就會丟失。為了避免這種情況，內存狀態會定期的保存在磁碟上，這比我們能接受數據丟失窗口要長的多。恢複檢查點也會花費數分鐘，導致很長的重啟周期。
我們能夠從現有的設計中學到的關鍵部分是數據塊的概念，我們當然希望保留這個概念。最新的數據塊會保持在內存中一般也是好的主意。畢竟，最新的數據會大量的查詢到。
一個時間序列對應一個文件，這個概念是我們想要替換掉的。
序列分流
在 Prometheus 的 上下文 中，我們使用術語 序列分流 來描述一個時間序列集合變得不活躍，即不再接收數據點，取而代之的是出現一組新的活躍序列。
例如，由給定微服務實例產生的所有序列都有一個相應的「instance」標籤來標識其來源。如果我們為微服務執行了 滾動更新 ，並且為每個實例替換一個新的版本，序列分流便會發生。在更加動態的環境中，這些事情基本上每小時都會發生。像 Kubernetes 這樣的 集群編排 系統允許應用連續性的自動伸縮和頻繁的滾動更新，這樣也許會創建成千上萬個新的應用程序實例，並且伴隨著全新的時間序列集合，每天都是如此。
series
^
| . . . . . .
| . . . . . .
| . . . . . .
| . . . . . . .
| . . . . . . .
| . . . . . . .
| . . . . . .
| . . . . . .
| . . . . .
| . . . . .
| . . . . .
v
<-------------------- time --------------------->所以即便整個基礎設施的規模基本保持不變，過一段時間後資料庫內的時間序列還是會成線性增長。儘管 Prometheus 很願意採集 1000 萬個時間序列數據，但要想在 10 億個序列中找到數據，查詢效果還是會受到嚴重的影響。
當前解決方案
當前 Prometheus 的 V2 存儲系統對所有當前保存的序列擁有基於 LevelDB 的索引。它允許查詢語句含有給定的 標籤對 ，但是缺乏可伸縮的方法來從不同的標籤選集中組合查詢結果。
例如，從所有的序列中選擇標籤 __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- 為前綴編號的 塊 。每個塊中顯然保存了索引文件和含有更多編號文件的 chunk 文件夾。chunks 目錄只包含不同序列 數據點的原始塊 。與 V2 存儲系統一樣，這使得通過時間窗口讀取序列數據非常高效並且允許我們使用相同的有效壓縮演算法。這一點被證實行之有效，我們也打算沿用。顯然，這裡並不存在含有單個序列的文件，而是一堆保存著許多序列的數據塊。
index 文件的存在應該不足為奇。讓我們假設它擁有黑魔法，可以讓我們找到標籤、可能的值、整個時間序列和存放數據點的數據塊。
但為什麼這裡有好幾個文件夾都是索引和塊文件的布局？並且為什麼存在最後一個包含 wal 文件夾？理解這兩個疑問便能解決九成的問題。
許多小型資料庫
我們分割橫軸，即將時間域分割為不重疊的塊。每一塊扮演著完全獨立的資料庫，它包含該時間窗口所有的時間序列數據。因此，它擁有自己的索引和一系列塊文件。
t0 t1 t2 t3 now
+-----------+ +-----------+ +-----------+ +-----------+
| | | | | | | | +------------+
| | | | | | | mutable | <--- write ---- ┤ Prometheus |
| | | | | | | | +------------+
+-----------+ +-----------+ +-----------+ +-----------+ ^
+--------------+-------+------+--------------+ |
| query
| |
merge -------------------------------------------------+
每一塊的數據都是 不可變的 。當然，當我們採集新數據時，我們必須能向最近的塊中添加新的序列和樣本。對於該數據塊，所有新的數據都將寫入內存中的資料庫中，它與我們的持久化的數據塊一樣提供了查找屬性。內存中的數據結構可以高效地更新。為了防止數據丟失，所有傳入的數據同樣被寫入臨時的 預寫日誌 中，這就是 wal 文件夾中的一些列文件，我們可以在重新啟動時通過它們重新填充內存資料庫。
所有這些文件都帶有序列化格式，有我們所期望的所有東西：許多標誌、偏移量、變體和 CRC32 校驗和。紙上得來終覺淺，絕知此事要躬行。
這種布局允許我們擴展查詢範圍到所有相關的塊上。每個塊上的部分結果最終合併成完整的結果。
這種橫向分割增加了一些很棒的功能：
- 當查詢一個時間範圍，我們可以簡單地忽略所有範圍之外的數據塊。通過減少需要檢查的數據集，它可以初步解決序列分流的問題。
- 當完成一個塊，我們可以通過順序的寫入大文件從內存資料庫中保存數據。這樣可以避免任何的寫入放大，並且 SSD 與 HDD 均適用。
- 我們延續了 V2 存儲系統的一個好的特性，最近使用而被多次查詢的數據塊，總是保留在內存中。
- 很好，我們也不再受限於 1KiB 的數據塊尺寸，以使數據在磁碟上更好地對齊。我們可以挑選對單個數據點和壓縮格式最合理的尺寸。
- 刪除舊數據變得極為簡單快捷。我們僅僅只需刪除一個文件夾。記住，在舊的存儲系統中我們不得不花數個小時分析並重寫數億個文件。
每個塊還包含了 meta.json 文件。它簡單地保存了關於塊的存儲狀態和包含的數據，以便輕鬆了解存儲狀態及其包含的數據。
mmap
將數百萬個小文件合併為少數幾個大文件使得我們用很小的開銷就能保持所有的文件都打開。這就解除了對 mmap(2) 的使用的阻礙，這是一個允許我們通過文件透明地回傳虛擬內存的系統調用。簡單起見，你可以將其視為 交換空間 ，只是我們所有的數據已經保存在了磁碟上，並且當數據換出內存後不再會發生寫入。
這意味著我們可以當作所有資料庫的內容都視為在內存中卻不佔用任何物理內存。僅當我們訪問資料庫文件某些位元組範圍時，操作系統才會從磁碟上 惰性載入 頁數據。這使得我們將所有數據持久化相關的內存管理都交給了操作系統。通常，操作系統更有資格作出這樣的決定，因為它可以全面了解整個機器和進程。查詢的數據可以相當積極的緩存進內存，但內存壓力會使得頁被換出。如果機器擁有未使用的內存，Prometheus 目前將會高興地緩存整個資料庫，但是一旦其他進程需要，它就會立刻返回那些內存。
因此，查詢不再輕易地使我們的進程 OOM，因為查詢的是更多的持久化的數據而不是裝入內存中的數據。內存緩存大小變得完全自適應，並且僅當查詢真正需要時數據才會被載入。
就個人理解，這就是當今大多數資料庫的工作方式，如果磁碟格式允許，這是一種理想的方式，——除非有人自信能在這個過程中超越操作系統。我們做了很少的工作但確實從外面獲得了很多功能。
壓縮
存儲系統需要定期「切」出新塊並將之前完成的塊寫入到磁碟中。僅在塊成功的持久化之後，才會被刪除之前用來恢復內存塊的日誌文件（wal）。
我們希望將每個塊的保存時間設置的相對短一些（通常配置為 2 小時），以避免內存中積累太多的數據。當查詢多個塊，我們必須將它們的結果合併為一個整體的結果。合併過程顯然會消耗資源，一個星期的查詢不應該由超過 80 個的部分結果所組成。
為了實現兩者，我們引入 壓縮 。壓縮描述了一個過程：取一個或更多個數據塊並將其寫入一個可能更大的塊中。它也可以在此過程中修改現有的數據。例如，清除已經刪除的數據，或重建樣本塊以提升查詢性能。
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)，所以在嵌套地為每個列表進行 暴力求解 下，運行時間為 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 內存的專用 裸機伺服器 更能反映出我們的用戶群體。
我們部署了兩個 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 伺服器的攝入率大大降低。序列分流的高壓導致了無法採集更多的數據。
那麼現在每秒可以攝入的 絕對最大 樣本數是多少？
但是現在你可以攝取的每秒絕對最大樣本數是多少？
我不知道 —— 雖然這是一個相當容易的優化指標，但除了穩固的基線性能之外，它並不是特別有意義。
有很多因素都會影響 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、浮點數、序列化格式的同學。
via: https://fabxc.org/blog/2017-04-10-writing-a-tsdb/
作者：Fabian Reinartz 譯者：LuuMing 校對：wxy
本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive
對這篇文章感覺如何？
You may also like
More in:Linux中國
如何通過 VLC 使用字幕
Unix 桌面：在 Linux 問世之前
Valve 對於 Ubuntu 的 Snap 版本的 Steam 並不滿意：原因何在
Wine 9.0 發布，實驗性地加入了 Wayland 驅動
