01 What is High-Cardinality

基數(shù)(Cardinality) 在數(shù)學(xué)中定義是用來(lái)代表集合元素個(gè)數(shù)的標(biāo)量，比如對(duì)于有限集合 A = {a, b, c} 的基數(shù)就是 3，對(duì)于無(wú)限集合也有一個(gè)基數(shù)概念，但是今天主要談?wù)摰氖怯?jì)算機(jī)領(lǐng)域，就不在這里展開(kāi)。

在數(shù)據(jù)庫(kù)的上下文里面，基數(shù)并沒(méi)有嚴(yán)格的定義，但大家對(duì)基數(shù)的共識(shí)可借鑒數(shù)學(xué)中的定義：用來(lái)衡量數(shù)據(jù)列包含的不同數(shù)值的個(gè)數(shù)多少。比如說(shuō)一個(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ù)庫(kù)的領(lǐng)域，基數(shù)往往是特指時(shí)間線的個(gè)數(shù)，我們就以時(shí)序數(shù)據(jù)庫(kù)在可觀測(cè)領(lǐng)域的應(yīng)用舉例：一個(gè)典型場(chǎng)景是記錄 API 服務(wù)的請(qǐng)求時(shí)間。舉一個(gè)最簡(jiǎn)單的例子，針對(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ù)庫(kù)而言，一般都有 ID 列，還有比如像 email, order-number 等等常見(jiàn)的列，這些都是 high-cardinality 的列，很少聽(tīng)說(shuō)因?yàn)檫@樣的數(shù)據(jù)建模而引起某些問(wèn)題。事實(shí)也是這樣，在我們熟悉的 OLTP 領(lǐng)域，往往 high-cardinality 并不是一個(gè)問(wèn)題，但在時(shí)序領(lǐng)域，因?yàn)閿?shù)據(jù)模型的原因，往往會(huì)帶來(lái)問(wèn)題，在進(jìn)到時(shí)序領(lǐng)域之前，我們還是先來(lái)討論一下高基的數(shù)據(jù)集到底意味著什么。

在我看來(lái)，高基的數(shù)據(jù)集換個(gè)通俗的說(shuō)法就是數(shù)據(jù)量大，那對(duì)于數(shù)據(jù)庫(kù)而言，數(shù)據(jù)量的增加必然會(huì)對(duì)寫(xiě)入、查詢和存儲(chǔ)三個(gè)方面都帶來(lái)影響。特別注意，在寫(xiě)入時(shí)影響最大的還是索引。

2.1 傳統(tǒng)數(shù)據(jù)庫(kù)的高基數(shù)

以關(guān)系型數(shù)據(jù)庫(kù)中采用的最常見(jiàn)的用來(lái)建立索引的數(shù)據(jù)結(jié)構(gòu) B-tree 為例，通常情況下，插入、查詢的復(fù)雜度是 O(logN)，空間的復(fù)雜度一般來(lái)講是 O(N), 其中的 N 是元素個(gè)數(shù)，也就是我們談到的基數(shù)。自然 N 越大會(huì)有一定影響，但因?yàn)椴迦牒筒樵兊膹?fù)雜度是自然對(duì)數(shù)，所以數(shù)據(jù)量級(jí)不是特別大的情況下，影響并沒(méi)那么大。

所以看起來(lái)高基數(shù)據(jù)并沒(méi)有帶來(lái)什么不可忽視的影響，反而在很多情況下，高基數(shù)據(jù)的索引比低基數(shù)據(jù)的索引選擇性更強(qiáng)，高基索引通過(guò)一個(gè)查詢條件就可以過(guò)濾掉大部分不滿足條件的數(shù)據(jù)，從而減少磁盤(pán) I/O 開(kāi)銷，在數(shù)據(jù)庫(kù)應(yīng)用方面，需要避免過(guò)多磁盤(pán)和網(wǎng)絡(luò)的 I/O 開(kāi)銷。比如 select * from users where gender = "male";，得到的數(shù)據(jù)集就非常多，磁盤(pán) I/O 和網(wǎng)絡(luò) I/O 都會(huì)很大，實(shí)踐中，單獨(dú)使用這個(gè)低基數(shù)索引的意義也并不大。

2.2 時(shí)序數(shù)據(jù)庫(kù)的高基數(shù)

那么時(shí)序數(shù)據(jù)庫(kù)究竟有什么不同的地方，使得高基的數(shù)據(jù)列會(huì)引起問(wèn)題？在時(shí)序數(shù)據(jù)領(lǐng)域，無(wú)論是數(shù)據(jù)建模還是引擎設(shè)計(jì)，核心會(huì)圍繞時(shí)間線進(jìn)行。正如前面談到的，時(shí)序數(shù)據(jù)庫(kù)里面的高基問(wèn)題，指的是時(shí)間線的數(shù)量大小，這個(gè)大小不僅僅是一個(gè)列的基數(shù)，而是所有 label 列的基數(shù)乘積，這樣的擴(kuò)散性就會(huì)非常大，可以理解成在常見(jiàn)的關(guān)系型數(shù)據(jù)庫(kù)中，高基是隔離在某個(gè)列中，即數(shù)據(jù)規(guī)模是線性增長(zhǎng)，而時(shí)序數(shù)據(jù)庫(kù)中的高基是多列的乘積，是非線性增長(zhǎng)。讓我們具體來(lái)看看在時(shí)序數(shù)據(jù)庫(kù)中的高基時(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 擁有無(wú)限多的值

第二種情況，比如在云原生環(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ù)庫(kù)所說(shuō)的高基數(shù)產(chǎn)生的主要原因。

2.4 時(shí)序數(shù)據(jù)庫(kù)如何組織數(shù)據(jù)

我們知道高基數(shù)是怎么產(chǎn)生的了，要理解它會(huì)導(dǎo)致什么問(wèn)題，還要了解主流的時(shí)序數(shù)據(jù)庫(kù)是怎么組織數(shù)據(jù)的。

圖中上半部分是數(shù)據(jù)寫(xiě)入前的表現(xiàn)形式，下半部分的圖則是數(shù)據(jù)存儲(chǔ)后的邏輯上的表現(xiàn)形式，左側(cè)也就是 time-series 部分的索引數(shù)據(jù)，右側(cè)則是數(shù)據(jù)部分。

每個(gè) time-series 可以生成一個(gè)唯一的 TSID，索引和數(shù)據(jù)就是通過(guò) TSID 關(guān)聯(lián)起來(lái)的，這個(gè)索引，熟悉的朋友可能已經(jīng)看出來(lái)了，它就是倒排索引。

再來(lái)看下圖，是倒排索引在內(nèi)存中的一個(gè)表現(xiàn)形式：

這是一個(gè)雙層的 map，外層先通過(guò) tag name 找到內(nèi)層 map，內(nèi)層 map 的 K 是 tag value, V 是包含相應(yīng) tag value 的 TSID 的集合。

到這里再結(jié)合前面的介紹，我們可以看出來(lái)了，時(shí)序數(shù)據(jù)的基數(shù)越高，這個(gè)雙層 map 就會(huì)越大。

明白了索引結(jié)構(gòu)以后我們就可以試圖去理解高基問(wèn)題是如何產(chǎn)生的：

為了實(shí)現(xiàn)高吞吐的寫(xiě)入，這個(gè)索引最好能保留在內(nèi)存中，高基數(shù)則會(huì)導(dǎo)致索引膨脹從而讓你的內(nèi)存中放不下索引。內(nèi)存放不下就要交換到磁盤(pán)，交換到磁盤(pán)后就會(huì)因?yàn)榇罅康碾S機(jī)磁盤(pán) IO 影響寫(xiě)入速度。

再來(lái)看查詢，從索引結(jié)構(gòu)我們是可以猜到查詢的過(guò)程，比如查詢條件 where status = 200 and method="get"，流程是先去找 key 為 status 的 map，拿到內(nèi)層的 map 再根據(jù) "200" 獲取所有 TSID 集合，同樣的方式再去查下一個(gè)條件，然后兩個(gè) TSID 集合做交集后得到的新的 TSID 集合再去一個(gè)一個(gè)的按照 TSID 去撈數(shù)據(jù)。

可以看出，問(wèn)題就核心在于數(shù)據(jù)是按照時(shí)間線來(lái)組織的，所以先要拿到時(shí)間線，再按照時(shí)間線去找數(shù)據(jù)。一次查詢涉及到的時(shí)間線越多，查詢就會(huì)越慢。

03 How to solve it

如果我們分析的是對(duì)的，知道了在時(shí)序數(shù)據(jù)領(lǐng)域下引起高基問(wèn)題的原因，那也就好解決了，再來(lái)看一下引起問(wèn)題的原因：

- 數(shù)據(jù)層面：C(L1) * C(L2) * C(L3) * ... * C(Ln) 引起的索引維護(hù)，查詢挑戰(zhàn)。

- 技術(shù)層面：數(shù)據(jù)是按照時(shí)間線來(lái)組織的，所以你先要拿到時(shí)間線，再按照時(shí)間線去找數(shù)據(jù)，時(shí)間線多就查詢變慢。

那小編拋磚引玉一下分別從兩個(gè)方面來(lái)探討解法：

3.1 數(shù)據(jù)建模上的優(yōu)化

#1 去掉不必要的 labels

我們經(jīng)常會(huì)不小心將一些不必要字段設(shè)定成 label，從而導(dǎo)致時(shí)間線膨脹。比如說(shuō)我們?cè)诒O(jiān)控服務(wù)器狀態(tài)時(shí)，經(jīng)常會(huì)有 instance_name, ip， 其實(shí)這兩個(gè)字段沒(méi)有必要都成為 label, 有其中一個(gè)很可能就可以了，另外一個(gè)可以設(shè)定成屬性。

#2 根據(jù)實(shí)際的查詢來(lái)做數(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)行么？比如說(shuō)查詢某個(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ī)模太大，依然無(wú)法將時(shí)間線減少，那就把和這個(gè)核心指標(biāo)有關(guān)的服務(wù)都單獨(dú)放到一個(gè)更好的機(jī)器上吧。

3.2 時(shí)序數(shù)據(jù)庫(kù)技術(shù)上的優(yōu)化

- 第一個(gè)有效的解法是垂直切分，大部分業(yè)界主流時(shí)序數(shù)據(jù)庫(kù)或多或少都采用了類似方法，按照時(shí)間來(lái)切分索引，因?yàn)槿绻蛔鲞@個(gè)切分的話，隨著時(shí)間的推進(jìn)，索引會(huì)越來(lái)越膨脹，最后到內(nèi)存放不下，如果按照時(shí)間切分，可以把舊的 index chunk 交換到磁盤(pán)甚至遠(yuǎn)程存儲(chǔ)，起碼寫(xiě)入是不會(huì)被影響到了。

- 與垂直切分相對(duì)的，就是水平切分，用一個(gè) sharding key，一般可以是查詢謂詞使用頻率最高的一個(gè)或者幾個(gè) tag，按照這些 tag 的 value 來(lái)進(jìn)行 range 或者 hash 切分，這樣就相當(dāng)于使用分布式的分而治之思想解決了單機(jī)上的瓶頸，代價(jià)就是如果查詢條件不帶 sharding key 的話通常是無(wú)法將算子下推，只能把數(shù)據(jù)撈到最上層去計(jì)算。

上面兩個(gè)辦法，屬于傳統(tǒng)的解決辦法，只能一定程度緩解問(wèn)題，并不能從根本上解決問(wèn)題。

接下來(lái)兩個(gè)方案不算是常規(guī)方案，是 GreptimeDB 在嘗試探索的方向，這里只稍微提下不做深入的分析，僅供大家參考：

- 我們可能要思考一下，時(shí)序數(shù)據(jù)庫(kù)是不是真的都需要倒排索引，TimescaleDB 采用 B-tree 索引， InfluxDB_IOx 也沒(méi)有倒排，對(duì)高基數(shù)的查詢，我們使用 OLAP 數(shù)據(jù)庫(kù)常用的分區(qū)掃描結(jié)合 min-max 索引進(jìn)行一些剪枝優(yōu)化，效果會(huì)不會(huì)更好？

- 異步的智能索引了，要智能，就得先采集和分析行為，在用戶的一次次查詢中分析并異步構(gòu)建最合適的索引來(lái)加速查詢，比如對(duì)用戶查詢條件中出現(xiàn)頻率非常低的 tag 我們選擇不為它創(chuàng)建倒排。

上面兩個(gè)方案結(jié)合起來(lái)看，在寫(xiě)入的時(shí)候，因?yàn)榈古女惒綐?gòu)建了，所以完全不影響寫(xiě)入速度。

再來(lái)看查詢，因?yàn)闀r(shí)序數(shù)據(jù)有時(shí)間屬性，所以數(shù)據(jù)是可以按照 timestamp 來(lái)分桶，在最近的 time bucket 上我們不做索引，解決辦法就是硬掃，結(jié)合一些 min-max 類索引進(jìn)行剪枝優(yōu)化，秒級(jí)掃描千萬(wàn)行上億行還是可以做到的。

一個(gè)查詢來(lái)了，先去預(yù)估會(huì)涉及多少時(shí)間線，涉及少的走倒排，多的不走倒排直接走 scan + filter 的方式。

以上這些想法，我們還在不斷的探索當(dāng)中，還不完善。

04 Conclusion 高基并不總是問(wèn)題，有時(shí)候高基是必要的，我們需要做的是結(jié)合自身的業(yè)務(wù)情況以及所使用的工具性質(zhì)，來(lái)構(gòu)建自己的數(shù)據(jù)模型。當(dāng)然有時(shí)候工具有一定場(chǎng)景局限性，比如 Prometheus 默認(rèn)是為每個(gè) metric 下的 label 建立索引，在單機(jī)場(chǎng)景下問(wèn)題不大，同時(shí)還能方便用戶使用，但放到了大規(guī)模數(shù)據(jù)下就會(huì)捉襟見(jiàn)肘。GreptimeDB 是致力打造在單機(jī)和規(guī)?；瘓?chǎng)景下的統(tǒng)一解決方案，對(duì)于高基問(wèn)題的技術(shù)嘗試，我們也在探索，也歡迎大家一起討論。

編輯：黃飛

?