01 What is High-Cardinality

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

在數(shù)據(jù)庫的上下文里面，基數(shù)并沒有嚴(yán)格的定義，但大家對基數(shù)的共識可借鑒數(shù)學(xué)中的定義：用來衡量數(shù)據(jù)列包含的不同數(shù)值的個數(shù)多少。比如說一個記錄用戶的數(shù)據(jù)表，通常有 UID, Name 和 Gender 這幾個列，很顯然，UID 的基數(shù)最高，因為每個用戶都會被分配一個唯一的 ID, Name 也算高的，但由于會遇到重名的用戶，就不如 UID 那么高，而 Gender 一列可能數(shù)值相對較少。所以在用戶表這個例子里面，就可以稱 UID 列屬于高基，而 Gender 則屬于低基。

如果再細(xì)分到時序數(shù)據(jù)庫的領(lǐng)域，基數(shù)往往是特指時間線的個數(shù)，我們就以時序數(shù)據(jù)庫在可觀測領(lǐng)域的應(yīng)用舉例：一個典型場景是記錄 API 服務(wù)的請求時間。舉一個最簡單的例子，針對不同 instance 的 API 服務(wù)各個接口的響應(yīng)時間，就有兩個 label: API Routes 和 Instance, 如果有 20 個接口，5 個 Instance，時間線的基數(shù)就是 (20+1)x(5+1)-1 = 125（+1 是考慮到可以單獨看某個 Instance 所有接口響應(yīng)時間或某個接口在所有 Instances 的響應(yīng)時間）， 看上去數(shù)值不大，但要注意算子是乘積，所以只要某個 label 基數(shù)高，或者新增加一個 label，就會導(dǎo)致時間線的基數(shù)暴增。

02 Why it matters

眾所周知，對于大家最熟悉的 MySQL 這類關(guān)系型數(shù)據(jù)庫而言，一般都有 ID 列，還有比如像 email, order-number 等等常見的列，這些都是 high-cardinality 的列，很少聽說因為這樣的數(shù)據(jù)建模而引起某些問題。事實也是這樣，在我們熟悉的 OLTP 領(lǐng)域，往往 high-cardinality 并不是一個問題，但在時序領(lǐng)域，因為數(shù)據(jù)模型的原因，往往會帶來問題，在進(jìn)到時序領(lǐng)域之前，我們還是先來討論一下高基的數(shù)據(jù)集到底意味著什么。

在我看來，高基的數(shù)據(jù)集換個通俗的說法就是數(shù)據(jù)量大，那對于數(shù)據(jù)庫而言，數(shù)據(jù)量的增加必然會對寫入、查詢和存儲三個方面都帶來影響。特別注意，在寫入時影響最大的還是索引。

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 是元素個數(shù)，也就是我們談到的基數(shù)。自然 N 越大會有一定影響，但因為插入和查詢的復(fù)雜度是自然對數(shù)，所以數(shù)據(jù)量級不是特別大的情況下，影響并沒那么大。

所以看起來高基數(shù)據(jù)并沒有帶來什么不可忽視的影響，反而在很多情況下，高基數(shù)據(jù)的索引比低基數(shù)據(jù)的索引選擇性更強(qiáng)，高基索引通過一個查詢條件就可以過濾掉大部分不滿足條件的數(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 都會很大，實踐中，單獨使用這個低基數(shù)索引的意義也并不大。

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

那么時序數(shù)據(jù)庫究竟有什么不同的地方，使得高基的數(shù)據(jù)列會引起問題？在時序數(shù)據(jù)領(lǐng)域，無論是數(shù)據(jù)建模還是引擎設(shè)計，核心會圍繞時間線進(jìn)行。正如前面談到的，時序數(shù)據(jù)庫里面的高基問題，指的是時間線的數(shù)量大小，這個大小不僅僅是一個列的基數(shù)，而是所有 label 列的基數(shù)乘積，這樣的擴(kuò)散性就會非常大，可以理解成在常見的關(guān)系型數(shù)據(jù)庫中，高基是隔離在某個列中，即數(shù)據(jù)規(guī)模是線性增長，而時序數(shù)據(jù)庫中的高基是多列的乘積，是非線性增長。讓我們具體來看看在時序數(shù)據(jù)庫中的高基時間線是如何產(chǎn)生的，我們先看第一種場景：

2.2.1 Time-series 數(shù)量

我們知道，時間線數(shù)量實際上就等于所有 label 基數(shù)的笛卡爾積。

如上圖，時間線數(shù)量就是 100 * 10 = 1000 條時間線，如果給這個 metric 再加上 6 個 tag，每個 tag value 的取值有 10 種，時間線數(shù)量就是 10^9 ，也就是一億條時間線，可以想象這個量級了。

2.3 Tag 擁有無限多的值

第二種情況，比如在云原生環(huán)境里，每個 pod 都有一個 ID，每次重啟時實際上 pod 是刪除再重建，它會生成一個新的 ID，這就導(dǎo)致這個 tag value 的值會非常的多，每次全量重啟會導(dǎo)致時間線數(shù)量翻一倍。

以上兩種情況，就是時序數(shù)據(jù)庫所說的高基數(shù)產(chǎn)生的主要原因。

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

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

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

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

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

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

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

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

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

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

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

03 How to solve it

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

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

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

那小編拋磚引玉一下分別從兩個方面來探討解法：

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

#1 去掉不必要的 labels

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

#2 根據(jù)實際的查詢來做數(shù)據(jù)建模

拿物聯(lián)網(wǎng)中的傳感器監(jiān)控為例子：

- 10w 個設(shè)備

- 100 個地區(qū)

- 10 種設(shè)備

如果建模到一個 metric 里面，在 Prometheus 里面，就會導(dǎo)致有 10w * 100 * 10 = 1 億的時間線。（非嚴(yán)謹(jǐn)計算）

思考一下，查詢會按照這種方式進(jìn)行么？比如說查詢某個某種類型設(shè)備在某個地區(qū)的時間線？這個似乎不太合理，因為一旦指定了設(shè)備，那種類也就確定了，所以這兩個 label 之間其實是不需要做在一起，那可能就變成：

metric_one: 10w 個設(shè)備

metric_two: 100 個地區(qū);10 種設(shè)備

metric_three: (假設(shè)某個設(shè)備可能會換到不同的地區(qū)采集數(shù)據(jù)）10w 個設(shè)備;100 個地區(qū)

這樣總計也就是 10w + 100*10 + 10w*100 ~ 1010w 的時間線，比起上述要少了 10倍。

#3 將有價值的高基時間線數(shù)據(jù)單獨管理

當(dāng)然如果發(fā)現(xiàn)你的數(shù)據(jù)建模已經(jīng)和查詢非常符合了，由于數(shù)據(jù)規(guī)模太大，依然無法將時間線減少，那就把和這個核心指標(biāo)有關(guān)的服務(wù)都單獨放到一個更好的機(jī)器上吧。

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

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

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

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

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

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

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

上面兩個方案結(jié)合起來看，在寫入的時候，因為倒排異步構(gòu)建了，所以完全不影響寫入速度。

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

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

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

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

編輯：黃飛

?