Prometheus時序資料庫-記憶體中的存儲結構

Prometheus時序資料庫-記憶體中的存儲結構

前言

筆者最近擔起了公司監控的重任,而當前監控最流行的資料庫即是Prometheus。按照筆者打破砂鍋問到底的精神,自然要把這個開源組件源碼搞明白才行。在經過一系列源碼/資料的閱讀以及各種Debug之後,對其內部機制有了一定的認識。今天,筆者就來介紹下Prometheus的存儲結構。
由於篇幅較長,所以筆者分為兩篇,本篇主要是描述Prometheus監控數據在記憶體中的存儲結構。下一篇,主要描述的是監控數據在磁碟中的存儲結構。

Gorilla

Prometheus的存儲結構-TSDB是參考了Facebook的Gorilla之後,自行實現的。所以閱讀
這篇文章《Gorilla: A Fast, Scalable, In-Memory Time Series Database》
,可以對Prometheus為何採用這樣的存儲結構有著清晰的理解。

監控數據點

下面是一個非常典型的監控曲線。

可以觀察到,監控數據都是由一個一個數據點組成,所以可以用下面的結構來保存最基本的存儲單元

type sample struct {
	t int64
	v float64
}

同時我們還需要注意到的資訊是,我們需要知道這些點屬於什麼機器的哪種監控。這種資訊在Promtheus中就用Label(標籤來表示)。一個監控項一般會有多個Label(例如圖中),所以一般用labels []Label。
由於在我們的習慣中,並不關心單獨的點,而是要關心這段時間內的曲線情況。所以自然而然的,我們存儲結構肯定邏輯上是這個樣子:

這樣,我們就可以很容易的通過一個Labels(標籤們)找到對應的數據了。

監控數據在記憶體中的表示形式

最近的數據保存在記憶體中

Prometheus將最近的數據保存在記憶體中,這樣查詢最近的數據會變得非常快,然後通過一個compactor定時將數據打包到磁碟。數據在記憶體中最少保留2個小時(storage.tsdb.min-block-duration。至於為什麼設置2小時這個值,應該是Gorilla那篇論文中觀察得出的結論

即壓縮率在2小時時候達到最高,如果保留的時間更短,就無法最大化的壓縮。

記憶體序列(memSeries)

接下來,我們看下具體的數據結構

type memSeries stuct {
	......
	ref uint64 // 其id
	lst labels.Labels // 對應的標籤集合
	chunks []*memChunk // 數據集合
	headChunk *memChunk // 正在被寫入的chunk
	......
}

其中memChunk是真正保存數據的記憶體塊,將在後面講到。我們先來觀察下memSeries在記憶體中的組織。

由此我們可以看到,針對一個最終端的監控項(包含抓取的所有標籤,以及新添加的標籤,例如ip),我們都在記憶體有一個memSeries結構。

定址memSeries

如果通過一堆標籤快速找到對應的memSeries。自然的,Prometheus就採用了hash。主要結構體為:

type stripeSeries struct {
	series [stripeSize]map[uint64]*memSeries // 記錄refId到memSeries的映射
	hashes [stripeSize]seriesHashmap // 記錄hash值到memSeries,hash衝突採用拉鏈法
	locks  [stripeSize]stripeLock // 分段鎖
}
type seriesHashmap map[uint64][]*memSeries

由於在Prometheus中會頻繁的對map[hash/refId]memSeries進行操作,例如檢查這個labelSet對應的memSeries是否存在,不存在則創建等。由於golang的map非執行緒安全,所以其採用了分段鎖去拆分鎖。

而hash值是依據labelSets的值而算出來。

數據點的存儲

為了讓Prometheus在記憶體和磁碟中保存更大的數據量,勢必需要進行壓縮。而memChunk在記憶體中保存的正是採用XOR演算法壓縮過的數據。在這裡,筆者只給出Gorilla論文中的XOR描述

更具體的演算法在論文中有詳細描述。總之,使用了XOR演算法後,平均每個數據點能從16bytes壓縮到1.37bytes,也就是說所用空間直接降為原來的1/12!

記憶體中的倒排索引

上面討論的是標籤全部給出的查詢情況。那麼我們怎麼快速找到某個或某幾個標籤(非全部標籤)的數據呢。這就需要引入以Label為key的倒排索引。我們先給出一組標籤集合

{__name__:http_requests}{group:canary}{instance:0}{job:api-server}   
{__name__:http_requests}{group:canary}{instance:1}{job:api-server}
{__name__:http_requests}{group:production}{instance:1}{job,api-server}
{__name__:http_requests}{group:production}{instance:0}{job,api-server}

可以看到,由於標籤取值不同,我們會有四種不同的memSeries。如果一次性給定4個標籤,應該是很容易從map中直接獲取出對應的memSeries(儘管Prometheus並沒有這麼做)。但大部分我們的promql只是給定了部分標籤,如何快速的查找符合標籤的數據呢?
這就引入倒排索引。
先看一下,上面例子中的memSeries在記憶體中會有4種,同時記憶體中還夾雜著其它監控項的series

如果我們想知道job:api-server,group為production在一段時間內所有的http請求數量,那麼必須獲取標籤攜帶
({__name__:http_requests}{job:api-server}{group:production})的所有監控數據。
如果沒有倒排索引,那麼我們必須遍歷記憶體中所有的memSeries(數萬乃至數十萬),一一按照Labels去比對,這顯然在性能上是不可接受的。而有了倒排索引,我們就可以通過求交集的手段迅速的獲取需要哪些memSeries。

注意,這邊倒排索引存儲的refId必須是有序的。這樣,我們就可以在O(n)複雜度下順利的算出交集,另外,針對其它請求形式,還有並集/差集的操作,對應實現結構體為:

type intersectPostings struct {...}  // 交集
type mergedPostings struct {...} // 並集
type removedPostings struct {...} // 差集

倒排索引的插入組織即為Prometheus下面的程式碼

Add(labels,t,v) 
	|->getOrCreateWithID
		|->memPostings.Add
		
// Add a label set to the postings index.
func (p *MemPostings) Add(id uint64, lset labels.Labels) {
	p.mtx.Lock()
	// 將新創建的memSeries refId都加到對應的Label倒排里去
	for _, l := range lset {
		p.addFor(id, l)
	}
	p.addFor(id, allPostingsKey) // allPostingKey "","" every one都加進去

	p.mtx.Unlock()
}

正則支援

事實上,給定特定的Label:Value還是無法滿足我們的需求。我們還需要對標籤正則化,例如取出所有ip為1.1.*前綴的http_requests監控數據。為了這種正則,Prometheus還維護了一個標籤所有可能的取值。對應程式碼為:

Add(labels,t,v) 
	|->getOrCreateWithID
		|->memPostings.Add
func (h *Head) getOrCreateWithID(id, hash uint64, lset labels.Labels){
	...
	for _, l := range lset {
		valset, ok := h.values[l.Name]
		if !ok {
			valset = stringset{}
			h.values[l.Name] = valset
		}
		// 將可能取值塞入stringset中
		valset.set(l.Value)
		// 符號表的維護
		h.symbols[l.Name] = struct{}{}
		h.symbols[l.Value] = struct{}{}
	}
	...
}

那麼,在記憶體中,我們就有了如下的表

圖中所示,有了label和對應所有value集合的表,一個正則請求就可以很容的分解為若干個非正則請求並最後求交/並/查集,即可得到最終的結果。

總結

Prometheus作為當今最流行的時序資料庫,其中有非常多的值得我們借鑒的設計和機制。這一篇筆者主要描述了監控數據在記憶體中的存儲結構。下一篇,將會闡述監控數據在磁碟中的存儲結構,敬請期待!

歡迎大家關注我公眾號,裡面有各種乾貨,還有大禮包相送哦!