01 What is High-Cardinality
基數(shù)(Cardinality) 在數(shù)學(xué)中定義是用來代表集合元素個(gè)數(shù)的標(biāo)量,比如對(duì)于有限集合 A = {a, b, c} 的基數(shù)就是 3,對(duì)于無限集合也有一個(gè)基數(shù)概念,但是今天主要談?wù)摰氖怯?jì)算機(jī)領(lǐng)域,就不在這里展開。
在數(shù)據(jù)庫的上下文里面,基數(shù)并沒有嚴(yán)格的定義,但大家對(duì)基數(shù)的共識(shí)可借鑒數(shù)學(xué)中的定義:用來衡量數(shù)據(jù)列包含的不同數(shù)值的個(gè)數(shù)多少。比如說一個(gè)記錄用戶的數(shù)據(jù)表,通常有 UID, Name 和 Gender 這幾個(gè)列,很顯然,UID 的基數(shù)最高,因?yàn)槊總€(gè)用戶都會(huì)被分配一個(gè)唯一的 ID, Name 也算高的,但由于會(huì)遇到重名的用戶,就不如 UID 那么高,而 Gender 一列可能數(shù)值相對(duì)較少。所以在用戶表這個(gè)例子里面,就可以稱 UID 列屬于高基,而 Gender 則屬于低基。
如果再細(xì)分到時(shí)序數(shù)據(jù)庫的領(lǐng)域,基數(shù)往往是特指時(shí)間線的個(gè)數(shù),我們就以時(shí)序數(shù)據(jù)庫在可觀測(cè)領(lǐng)域的應(yīng)用舉例:一個(gè)典型場(chǎng)景是記錄 API 服務(wù)的請(qǐng)求時(shí)間。舉一個(gè)最簡單的例子,針對(duì)不同 instance 的 API 服務(wù)各個(gè)接口的響應(yīng)時(shí)間,就有兩個(gè) label: API Routes 和 Instance, 如果有 20 個(gè)接口,5 個(gè) Instance,時(shí)間線的基數(shù)就是 (20+1)x(5+1)-1 = 125(+1 是考慮到可以單獨(dú)看某個(gè) Instance 所有接口響應(yīng)時(shí)間或某個(gè)接口在所有 Instances 的響應(yīng)時(shí)間), 看上去數(shù)值不大,但要注意算子是乘積,所以只要某個(gè) label 基數(shù)高,或者新增加一個(gè) label,就會(huì)導(dǎo)致時(shí)間線的基數(shù)暴增。
02 Why it matters
眾所周知,對(duì)于大家最熟悉的 MySQL 這類關(guān)系型數(shù)據(jù)庫而言,一般都有 ID 列,還有比如像 email, order-number 等等常見的列,這些都是 high-cardinality 的列,很少聽說因?yàn)檫@樣的數(shù)據(jù)建模而引起某些問題。事實(shí)也是這樣,在我們熟悉的 OLTP 領(lǐng)域,往往 high-cardinality 并不是一個(gè)問題,但在時(shí)序領(lǐng)域,因?yàn)閿?shù)據(jù)模型的原因,往往會(huì)帶來問題,在進(jìn)到時(shí)序領(lǐng)域之前,我們還是先來討論一下高基的數(shù)據(jù)集到底意味著什么。
在我看來,高基的數(shù)據(jù)集換個(gè)通俗的說法就是數(shù)據(jù)量大,那對(duì)于數(shù)據(jù)庫而言,數(shù)據(jù)量的增加必然會(huì)對(duì)寫入、查詢和存儲(chǔ)三個(gè)方面都帶來影響。特別注意,在寫入時(shí)影響最大的還是索引。
2.1 傳統(tǒng)數(shù)據(jù)庫的高基數(shù)
以關(guān)系型數(shù)據(jù)庫中采用的最常見的用來建立索引的數(shù)據(jù)結(jié)構(gòu) B-tree 為例,通常情況下,插入、查詢的復(fù)雜度是 O(logN),空間的復(fù)雜度一般來講是 O(N), 其中的 N 是元素個(gè)數(shù),也就是我們談到的基數(shù)。自然 N 越大會(huì)有一定影響,但因?yàn)椴迦牒筒樵兊膹?fù)雜度是自然對(duì)數(shù),所以數(shù)據(jù)量級(jí)不是特別大的情況下,影響并沒那么大。
所以看起來高基數(shù)據(jù)并沒有帶來什么不可忽視的影響,反而在很多情況下,高基數(shù)據(jù)的索引比低基數(shù)據(jù)的索引選擇性更強(qiáng),高基索引通過一個(gè)查詢條件就可以過濾掉大部分不滿足條件的數(shù)據(jù),從而減少磁盤 I/O 開銷,在數(shù)據(jù)庫應(yīng)用方面,需要避免過多磁盤和網(wǎng)絡(luò)的 I/O 開銷。比如 select * from users where gender = "male";,得到的數(shù)據(jù)集就非常多,磁盤 I/O 和網(wǎng)絡(luò) I/O 都會(huì)很大,實(shí)踐中,單獨(dú)使用這個(gè)低基數(shù)索引的意義也并不大。
2.2 時(shí)序數(shù)據(jù)庫的高基數(shù)
那么時(shí)序數(shù)據(jù)庫究竟有什么不同的地方,使得高基的數(shù)據(jù)列會(huì)引起問題?在時(shí)序數(shù)據(jù)領(lǐng)域,無論是數(shù)據(jù)建模還是引擎設(shè)計(jì),核心會(huì)圍繞時(shí)間線進(jìn)行。正如前面談到的,時(shí)序數(shù)據(jù)庫里面的高基問題,指的是時(shí)間線的數(shù)量大小,這個(gè)大小不僅僅是一個(gè)列的基數(shù),而是所有 label 列的基數(shù)乘積,這樣的擴(kuò)散性就會(huì)非常大,可以理解成在常見的關(guān)系型數(shù)據(jù)庫中,高基是隔離在某個(gè)列中,即數(shù)據(jù)規(guī)模是線性增長,而時(shí)序數(shù)據(jù)庫中的高基是多列的乘積,是非線性增長。讓我們具體來看看在時(shí)序數(shù)據(jù)庫中的高基時(shí)間線是如何產(chǎn)生的,我們先看第一種場(chǎng)景:
2.2.1 Time-series 數(shù)量
我們知道,時(shí)間線數(shù)量實(shí)際上就等于所有 label 基數(shù)的笛卡爾積。
如上圖,時(shí)間線數(shù)量就是 100 * 10 = 1000 條時(shí)間線,如果給這個(gè) metric 再加上 6 個(gè) tag,每個(gè) tag value 的取值有 10 種,時(shí)間線數(shù)量就是 10^9 ,也就是一億條時(shí)間線,可以想象這個(gè)量級(jí)了。
2.3 Tag 擁有無限多的值
第二種情況,比如在云原生環(huán)境里,每個(gè) pod 都有一個(gè) ID,每次重啟時(shí)實(shí)際上 pod 是刪除再重建,它會(huì)生成一個(gè)新的 ID,這就導(dǎo)致這個(gè) tag value 的值會(huì)非常的多,每次全量重啟會(huì)導(dǎo)致時(shí)間線數(shù)量翻一倍。
以上兩種情況,就是時(shí)序數(shù)據(jù)庫所說的高基數(shù)產(chǎn)生的主要原因。
2.4 時(shí)序數(shù)據(jù)庫如何組織數(shù)據(jù)
我們知道高基數(shù)是怎么產(chǎn)生的了,要理解它會(huì)導(dǎo)致什么問題,還要了解主流的時(shí)序數(shù)據(jù)庫是怎么組織數(shù)據(jù)的。
圖中上半部分是數(shù)據(jù)寫入前的表現(xiàn)形式,下半部分的圖則是數(shù)據(jù)存儲(chǔ)后的邏輯上的表現(xiàn)形式,左側(cè)也就是 time-series 部分的索引數(shù)據(jù),右側(cè)則是數(shù)據(jù)部分。
每個(gè) time-series 可以生成一個(gè)唯一的 TSID,索引和數(shù)據(jù)就是通過 TSID 關(guān)聯(lián)起來的,這個(gè)索引,熟悉的朋友可能已經(jīng)看出來了,它就是倒排索引。
再來看下圖,是倒排索引在內(nèi)存中的一個(gè)表現(xiàn)形式:
這是一個(gè)雙層的 map,外層先通過 tag name 找到內(nèi)層 map,內(nèi)層 map 的 K 是 tag value, V 是包含相應(yīng) tag value 的 TSID 的集合。
到這里再結(jié)合前面的介紹,我們可以看出來了,時(shí)序數(shù)據(jù)的基數(shù)越高,這個(gè)雙層 map 就會(huì)越大。
明白了索引結(jié)構(gòu)以后我們就可以試圖去理解高基問題是如何產(chǎn)生的:
為了實(shí)現(xiàn)高吞吐的寫入,這個(gè)索引最好能保留在內(nèi)存中,高基數(shù)則會(huì)導(dǎo)致索引膨脹從而讓你的內(nèi)存中放不下索引。內(nèi)存放不下就要交換到磁盤,交換到磁盤后就會(huì)因?yàn)榇罅康碾S機(jī)磁盤 IO 影響寫入速度。
再來看查詢,從索引結(jié)構(gòu)我們是可以猜到查詢的過程,比如查詢條件 where status = 200 and method="get",流程是先去找 key 為 status 的 map,拿到內(nèi)層的 map 再根據(jù) "200" 獲取所有 TSID 集合,同樣的方式再去查下一個(gè)條件,然后兩個(gè) TSID 集合做交集后得到的新的 TSID 集合再去一個(gè)一個(gè)的按照 TSID 去撈數(shù)據(jù)。
可以看出,問題就核心在于數(shù)據(jù)是按照時(shí)間線來組織的,所以先要拿到時(shí)間線,再按照時(shí)間線去找數(shù)據(jù)。一次查詢涉及到的時(shí)間線越多,查詢就會(huì)越慢。
03 How to solve it
如果我們分析的是對(duì)的,知道了在時(shí)序數(shù)據(jù)領(lǐng)域下引起高基問題的原因,那也就好解決了,再來看一下引起問題的原因:
- 數(shù)據(jù)層面:C(L1) * C(L2) * C(L3) * ... * C(Ln) 引起的索引維護(hù),查詢挑戰(zhàn)。
- 技術(shù)層面:數(shù)據(jù)是按照時(shí)間線來組織的,所以你先要拿到時(shí)間線,再按照時(shí)間線去找數(shù)據(jù),時(shí)間線多就查詢變慢。
那小編拋磚引玉一下分別從兩個(gè)方面來探討解法:
3.1 數(shù)據(jù)建模上的優(yōu)化
#1 去掉不必要的 labels
我們經(jīng)常會(huì)不小心將一些不必要字段設(shè)定成 label,從而導(dǎo)致時(shí)間線膨脹。比如說我們?cè)诒O(jiān)控服務(wù)器狀態(tài)時(shí),經(jīng)常會(huì)有 instance_name, ip, 其實(shí)這兩個(gè)字段沒有必要都成為 label, 有其中一個(gè)很可能就可以了,另外一個(gè)可以設(shè)定成屬性。
#2 根據(jù)實(shí)際的查詢來做數(shù)據(jù)建模
拿物聯(lián)網(wǎng)中的傳感器監(jiān)控為例子:
- 10w 個(gè)設(shè)備
- 100 個(gè)地區(qū)
- 10 種設(shè)備
如果建模到一個(gè) metric 里面,在 Prometheus 里面,就會(huì)導(dǎo)致有 10w * 100 * 10 = 1 億的時(shí)間線。(非嚴(yán)謹(jǐn)計(jì)算)
思考一下,查詢會(huì)按照這種方式進(jìn)行么?比如說查詢某個(gè)某種類型設(shè)備在某個(gè)地區(qū)的時(shí)間線?這個(gè)似乎不太合理,因?yàn)橐坏┲付嗽O(shè)備,那種類也就確定了,所以這兩個(gè) label 之間其實(shí)是不需要做在一起,那可能就變成:
metric_one: 10w 個(gè)設(shè)備
metric_two: 100 個(gè)地區(qū);10 種設(shè)備
metric_three: (假設(shè)某個(gè)設(shè)備可能會(huì)換到不同的地區(qū)采集數(shù)據(jù))10w 個(gè)設(shè)備;100 個(gè)地區(qū)
這樣總計(jì)也就是 10w + 100*10 + 10w*100 ~ 1010w 的時(shí)間線,比起上述要少了 10倍。
#3 將有價(jià)值的高基時(shí)間線數(shù)據(jù)單獨(dú)管理
當(dāng)然如果發(fā)現(xiàn)你的數(shù)據(jù)建模已經(jīng)和查詢非常符合了,由于數(shù)據(jù)規(guī)模太大,依然無法將時(shí)間線減少,那就把和這個(gè)核心指標(biāo)有關(guān)的服務(wù)都單獨(dú)放到一個(gè)更好的機(jī)器上吧。
3.2 時(shí)序數(shù)據(jù)庫技術(shù)上的優(yōu)化
- 第一個(gè)有效的解法是垂直切分,大部分業(yè)界主流時(shí)序數(shù)據(jù)庫或多或少都采用了類似方法,按照時(shí)間來切分索引,因?yàn)槿绻蛔鲞@個(gè)切分的話,隨著時(shí)間的推進(jìn),索引會(huì)越來越膨脹,最后到內(nèi)存放不下,如果按照時(shí)間切分,可以把舊的 index chunk 交換到磁盤甚至遠(yuǎn)程存儲(chǔ),起碼寫入是不會(huì)被影響到了。
- 與垂直切分相對(duì)的,就是水平切分,用一個(gè) sharding key,一般可以是查詢謂詞使用頻率最高的一個(gè)或者幾個(gè) tag,按照這些 tag 的 value 來進(jìn)行 range 或者 hash 切分,這樣就相當(dāng)于使用分布式的分而治之思想解決了單機(jī)上的瓶頸,代價(jià)就是如果查詢條件不帶 sharding key 的話通常是無法將算子下推,只能把數(shù)據(jù)撈到最上層去計(jì)算。
上面兩個(gè)辦法,屬于傳統(tǒng)的解決辦法,只能一定程度緩解問題,并不能從根本上解決問題。
接下來兩個(gè)方案不算是常規(guī)方案,是 GreptimeDB 在嘗試探索的方向,這里只稍微提下不做深入的分析,僅供大家參考:
- 我們可能要思考一下,時(shí)序數(shù)據(jù)庫是不是真的都需要倒排索引,TimescaleDB 采用 B-tree 索引, InfluxDB_IOx 也沒有倒排,對(duì)高基數(shù)的查詢,我們使用 OLAP 數(shù)據(jù)庫常用的分區(qū)掃描結(jié)合 min-max 索引進(jìn)行一些剪枝優(yōu)化,效果會(huì)不會(huì)更好?
- 異步的智能索引了,要智能,就得先采集和分析行為,在用戶的一次次查詢中分析并異步構(gòu)建最合適的索引來加速查詢,比如對(duì)用戶查詢條件中出現(xiàn)頻率非常低的 tag 我們選擇不為它創(chuàng)建倒排。
上面兩個(gè)方案結(jié)合起來看,在寫入的時(shí)候,因?yàn)榈古女惒綐?gòu)建了,所以完全不影響寫入速度。
再來看查詢,因?yàn)闀r(shí)序數(shù)據(jù)有時(shí)間屬性,所以數(shù)據(jù)是可以按照 timestamp 來分桶,在最近的 time bucket 上我們不做索引,解決辦法就是硬掃,結(jié)合一些 min-max 類索引進(jìn)行剪枝優(yōu)化,秒級(jí)掃描千萬行上億行還是可以做到的。
一個(gè)查詢來了,先去預(yù)估會(huì)涉及多少時(shí)間線,涉及少的走倒排,多的不走倒排直接走 scan + filter 的方式。
以上這些想法,我們還在不斷的探索當(dāng)中,還不完善。
04 Conclusion 高基并不總是問題,有時(shí)候高基是必要的,我們需要做的是結(jié)合自身的業(yè)務(wù)情況以及所使用的工具性質(zhì),來構(gòu)建自己的數(shù)據(jù)模型。當(dāng)然有時(shí)候工具有一定場(chǎng)景局限性,比如 Prometheus 默認(rèn)是為每個(gè) metric 下的 label 建立索引,在單機(jī)場(chǎng)景下問題不大,同時(shí)還能方便用戶使用,但放到了大規(guī)模數(shù)據(jù)下就會(huì)捉襟見肘。GreptimeDB 是致力打造在單機(jī)和規(guī)模化場(chǎng)景下的統(tǒng)一解決方案,對(duì)于高基問題的技術(shù)嘗試,我們也在探索,也歡迎大家一起討論。
編輯:黃飛
?
評(píng)論
查看更多