Context

Snowflake IPO 大火之后大家開(kāi)始慢慢了解到這個(gè)完全基于云架構(gòu)而設(shè)計(jì)的新式數(shù)據(jù)倉(cāng)庫(kù)。

Snowflake 利用云端近似無(wú)限的計(jì)算和存儲(chǔ)資源，基于存算分離的新式架構(gòu)，真正實(shí)現(xiàn)了按需、按量的付費(fèi)模式，極大的降低了用戶的使用成本，讓用戶更加專注于數(shù)據(jù)價(jià)值的挖掘。對(duì)于傳統(tǒng)的數(shù)據(jù)倉(cāng)庫(kù)來(lái)說(shuō)，Snowflake 就像一塊降維打擊的二向箔。?

在業(yè)務(wù)增長(zhǎng)過(guò)程中，用戶的數(shù)據(jù)持續(xù)增長(zhǎng)，從而導(dǎo)致單表變大，查詢的 SQL 模式也可能會(huì)發(fā)生變化，這時(shí)問(wèn)題就出現(xiàn)了：之前比較快的查詢現(xiàn)在變慢了。Snowflake 為了解決這個(gè)問(wèn)題，提供了一個(gè)硬核功能：**Auto Clustering，讓你在建表時(shí)無(wú)需指定任何分區(qū)字段，而查詢則越跑越快**。這里我們就來(lái)探索下 Snowflake 的 Auto Clustering 機(jī)制是如何實(shí)現(xiàn)的。

什么是 Auto Clustering

Snowflake 的 Clustering 功能和傳統(tǒng)數(shù)據(jù)的 Partition 功能類似。但在傳統(tǒng)的數(shù)據(jù)庫(kù)系統(tǒng)中，大多依賴一些靜態(tài)的分區(qū)規(guī)則來(lái)實(shí)現(xiàn)數(shù)據(jù)的物理隔離，如按時(shí)間，按用戶特征 hash 等等，在 Hive 等數(shù)據(jù)倉(cāng)庫(kù)中，最常見(jiàn)到的還是按照時(shí)間分區(qū)。當(dāng)一個(gè)帶有分區(qū)字段相關(guān)查詢過(guò)來(lái)的時(shí)候，分區(qū)的裁剪可以直接忽略掉不匹配的數(shù)據(jù)，這樣就可以大大減少了數(shù)據(jù)的讀取和計(jì)算，從而提高查詢性能。注意：這里的 Clustering 是指分組、聚類的意思，注意不要理解為分布式、集群等概念。

靜態(tài)分區(qū)用法非常簡(jiǎn)單，比如在 Hive 中：

```

-- Create Partition

ALTER TABLE table_name ADD PARTITION (dt='2020-03-26', hour='08') location '/path/table/20200326/08';

-- Then load data into the partition

```

開(kāi)發(fā)人員在建表的時(shí)候必須知道數(shù)據(jù)的分布情況和將來(lái)面對(duì)的查詢模式，增加了用戶的心智負(fù)擔(dān)。它有以下缺點(diǎn)：

• ?靜態(tài)分區(qū)的規(guī)則是固定的，但數(shù)據(jù)卻是隨時(shí)間在變化的，比如業(yè)務(wù)持續(xù)增長(zhǎng)過(guò)程中，按天分區(qū)的表新的分區(qū)會(huì)變大，從而導(dǎo)致分區(qū)分布不均勻。

Snowflake 在設(shè)計(jì)中完全拋棄了傳統(tǒng)的靜態(tài) Partition 概念，而是提出了 Auto Clustering 的新設(shè)計(jì)。簡(jiǎn)而言之，用戶再也不用關(guān)心我的表是如何分區(qū)了，用戶只管寫(xiě)入和查詢就是，數(shù)據(jù)分組，性能優(yōu)化我會(huì)自動(dòng)做！

Micro Partition（微分區(qū)）

雖然拋棄了靜態(tài)分區(qū)，但 Snowflake 里面還是有 Micro-Partition 和 Cluster Key 的概念。

• ?Cluster Key 是排序鍵，可以由多個(gè)字段組成，類似 ClickHouse 的 Order Key。

• ?Micro-Partition 是數(shù)據(jù)的基本組成單元，一個(gè)表的數(shù)據(jù)由多個(gè) Micro-Partition 組成。我們可以將它理解為一個(gè)物理文件，這個(gè)物理文件限制在 50 MB-500 MB 的大?。ㄎ磯嚎s），物理文件采用了列式存儲(chǔ)，不同的列存儲(chǔ)在不同的連續(xù)空間內(nèi)。Snowflake 會(huì)存儲(chǔ) Micro-Partition 的信息到元數(shù)據(jù)服務(wù)中，方便查詢時(shí)通過(guò)元數(shù)據(jù)索引進(jìn)行剪枝，如：

? ? ??? ? 每個(gè)列的區(qū)間索引，最大值、最小值等 (ZoneMap index）

? ? ?? ?? 列分布的直方圖信息

? ? ??? ? 其他..

Clustered Tables

數(shù)據(jù)表建立后，默認(rèn)數(shù)據(jù)是自然序，自然序意味著我們沒(méi)有做任何處理，數(shù)據(jù)就按照流入的順序排列，此時(shí)表處于 Unclustered 狀態(tài)。當(dāng)表經(jīng)歷了 Clustering 后，每個(gè) Micro-Partition 會(huì)按照指定的 Key 進(jìn)行排序，可以理解為給表加了一個(gè)排序鍵，此時(shí)表處于 Clustered 狀態(tài)。?

上圖來(lái)自 Snowflake 文檔。

Clustered 的主要目的是讓大部分的查詢能高效的裁剪數(shù)據(jù)，避免不需要的 IO 讀取和計(jì)算。舉個(gè)例子：

```

select name, country from t1 where type = 2 and date = '11/2';

```

怎樣讓表達(dá)到 Well-Clustered？在原始的數(shù)據(jù)排列中（自然序），上面的 SQL 會(huì)掃描到 4 個(gè) Micro-Partition。而在 Clustered 狀態(tài)下，數(shù)據(jù)已經(jīng)按照 Cluster Key->(date, type) 進(jìn)行排序，所以只會(huì)掃描到 1 個(gè) Micro-Partition，其他的 Micro-Partition 都被引擎結(jié)合了存儲(chǔ)在元數(shù)據(jù)的索引進(jìn)行了裁剪過(guò)濾。

一般來(lái)說(shuō)，大表不會(huì)是靜態(tài)的數(shù)據(jù)，大多會(huì)是時(shí)序數(shù)據(jù)，也就是說(shuō)數(shù)據(jù)不斷地實(shí)時(shí)流入。因此，對(duì)整個(gè)表級(jí)別的數(shù)據(jù)全排序是非常不現(xiàn)實(shí)的，不僅代價(jià)較高，實(shí)時(shí)流入的數(shù)據(jù)也會(huì)影響全排序結(jié)果。另外一種方法是只對(duì)流入的數(shù)據(jù)進(jìn)行排序，這樣雖然新數(shù)據(jù)有比較好的順序，但隨著數(shù)據(jù)在不斷地流入，數(shù)據(jù)整體的順序會(huì)逐漸趨于混亂。

結(jié)合上面的分析，一個(gè)表如果能達(dá)到 Well-Clustered（表數(shù)據(jù)的整體有序度高），這樣查詢才能高效。在這個(gè)前提下，還需要保證“新數(shù)據(jù)能實(shí)時(shí)高效流入”（確保 DML 高效），兩者之間存在一個(gè)平衡點(diǎn)，Snowflake 的做法是優(yōu)先保證新數(shù)據(jù)能實(shí)時(shí)高效流入，新數(shù)據(jù)是不需要對(duì)數(shù)據(jù)整體的有序度“負(fù)責(zé)”，因?yàn)樾聰?shù)據(jù)相比歷史數(shù)據(jù)來(lái)說(shuō)量級(jí)較小，影響的有序度也較小，它只需保證局部有序就行了（確保新數(shù)據(jù)查詢也能高效）。新數(shù)據(jù)在后臺(tái)會(huì)異步進(jìn)行合并，保證“表數(shù)據(jù)的整體有序度高”，也就是說(shuō)，數(shù)據(jù)的整體有序是一個(gè)漸進(jìn)的過(guò)程，而不是整體絕對(duì)有序的。

如何衡量 Well-Clustered ？

Snowflake 引入了幾個(gè)主要的指標(biāo)來(lái)衡量表的 Well-Clustered 程度：?

• ?Overlaps: 在一個(gè) Range 范圍內(nèi)，有多少個(gè) Micro-Partition 有重疊

• ?Depth: 在一個(gè)數(shù)據(jù)點(diǎn)中，有多少個(gè) Micro-Partition 有重疊

上面的圖從上到下展示了四種表 Cluster 的狀態(tài)，第一種情況是 4 個(gè)Micro-Partition 完全重疊，這種情況是最糟糕的，因?yàn)樗鼪](méi)有任何區(qū)分度，命中了 A-Z 這個(gè) Range 的查詢會(huì)不可避免地掃描四個(gè)分區(qū)。隨著 Depth 指標(biāo)的下降，表中 Micro-Partition 變得逐漸離散，Overlaps 指標(biāo)也在下降，表也逐漸變得更加 Well-Clustered。

當(dāng)然，在實(shí)際的表分布中，Micro-Partition 的分布要達(dá)到最下面那樣規(guī)整（全局有序）是不現(xiàn)實(shí)的，因?yàn)樗枰拈_(kāi)銷太大了。

• levels：Micro-Partition 所屬的級(jí)別

為了減少寫(xiě)放大，Micro-Partition 的合并策略和 LSM-tree 類似，Micro-Partition 在后臺(tái)不斷地合并后形成新的 Micro-Partition，每次合并完成后，Micro-Partition 的 Level 值就會(huì)自增（clickhouse 也有類似的 Part 合并邏輯），所以 Level 表示的就是 Micro-Partition 經(jīng)歷過(guò)的合并次數(shù)（用來(lái)衡量經(jīng)歷過(guò)的合并成本）。新數(shù)據(jù)流入的 Micro-Partition Level 默認(rèn)是 0，Level 越低的 Micro-Partition 中，Overlaps 和 Depth 指標(biāo)相對(duì)來(lái)說(shuō)會(huì)越高，在不斷合并的過(guò)程中，Micro-Partition 變得越來(lái)越離散，表也變得更加 Well-Clustered。

注意：Micro-Partition 只會(huì)和同 Level 的 Micro-Partition 合并， Level 存在最大值，避免寫(xiě)放大太嚴(yán)重。Auto Clustering 是如何進(jìn)行的

Auto Clustering 是如何進(jìn)行的

Auto Clustering 主要分為兩大任務(wù)：?

• Part-Selection 任務(wù)

• Part-Merge 任務(wù)

這塊和 ClickHouse 的邏輯很類似，但明顯的區(qū)別是 Snowflake 對(duì)云實(shí)在太偏愛(ài)了，上面所有的任務(wù)都可以在云端拉起獨(dú)立的進(jìn)程進(jìn)行，而不需要占用用戶的計(jì)算資源，并且這兩個(gè)進(jìn)程也是微服務(wù)化的，可以按需彈性伸縮。

Part-Selection 任務(wù)

Selection 任務(wù)會(huì)從某個(gè) Level 中選擇出 Micro-Partition 列表集合，選擇的策略是啟發(fā)式的。

上面提到的 2 個(gè)指標(biāo)可以構(gòu)建一個(gè)啟發(fā)式的算法：

1.? Level 低的 Micro-Partition 被選擇的優(yōu)先級(jí)高，因此新流入的數(shù)據(jù)能有較高優(yōu)先級(jí)合并到下個(gè) Level，Level 越高的 Micro-Partition 除非在有充足的資源情況下，否則不會(huì)被合并。

2.? Depth 高的 Micro-Partition 被選擇的優(yōu)先級(jí)高。

因此 Selection 的目標(biāo)就是降低 Level 中 Micro-Partition 的平均深度，AvgDepth。AvgDepth 又是如何計(jì)算的呢？

下面四個(gè) Micro-Partition 的情況下：

我們對(duì)每個(gè)端點(diǎn)進(jìn)行分析，如果沒(méi)有 overlap，depth 忽略，因?yàn)?depth 的目的就是衡量 overlap 的程度，引入 depth=0 會(huì)導(dǎo)致數(shù)據(jù)有偏差，此時(shí) depth 表示一個(gè)端點(diǎn)覆蓋了幾個(gè)分區(qū)。

最終的計(jì)算方式是：

```

AvgDepth = Sum(DepthOfOverflapPoint) / OverflapPointsCnt

```

Snowflake 沒(méi)有公開(kāi)具體的 Selection 算法，不過(guò)大概是 Level+AvgDepth 結(jié)合的一個(gè)公式進(jìn)行排序，我們假設(shè)它是以每個(gè) Level 的 AvgDepth 排序選擇某個(gè) Level，然后去順序遍歷此 Level 下的所有端點(diǎn)，超過(guò)了 AvgDepth 的連續(xù)端點(diǎn)會(huì)被選擇作為 Range。

橫軸對(duì)應(yīng)的就是 Key 的 Range，縱軸表示 Depth，計(jì)算方式大概是：遍歷所有的 Micro-Partition，將 Micro-Partition 的 Range 的 Depth 進(jìn)行求和（即上面的 DepthOfOverflapPoint )，得出對(duì)應(yīng)端點(diǎn)的 Y 值（這里應(yīng)該可以用差分?jǐn)?shù)組的數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化）

選擇的策略是什么？

上圖是選擇了兩個(gè) Micro-Partition 列表的集合示例，選擇的方式是順序遍歷所有的端點(diǎn)，如果端點(diǎn)的 Depth 超過(guò)了 AvgDepth，就會(huì)被選擇，連續(xù)選擇的端點(diǎn)構(gòu)成一個(gè) Range。

為什么不直接選最高的 Depth？

可以發(fā)現(xiàn)最高點(diǎn) Depth 雖然最高，但覆蓋的 Range 變窄，這樣導(dǎo)致選擇的 Micro-Partition 數(shù)量太小，對(duì)降低 AvgDepth 的影響較少。

選擇的結(jié)果是什么？

看有多少個(gè)符合條件的波峰，上圖是兩個(gè)符合條件的波峰，這兩個(gè)波峰互不重合，可以作為選擇的結(jié)果集合，集合中內(nèi)包含了 Micro-Partition 的 batches。

ClickHouse 中也有類似的選擇策略算法，建議讀者有時(shí)間也可以去了解下。

Part-Merge 任務(wù)

接收到 Selection 的列表后，Part-Merge 可以獨(dú)立地進(jìn)行 Micro-Partition 的排序和合并，類似一個(gè)歸并排序的過(guò)程。合并后的 Micro-Partition 就是一個(gè)全局有序的大 Micro-Partition 了。值得一提的是，合并后的分區(qū)如果超過(guò)了 500 MB 的閾值上限，就會(huì)被分裂成更小的 Micro-Partition，這和 ClickHouse 存儲(chǔ)一個(gè)大的分區(qū)文件是不同的。

猜測(cè)可能是：

1. Snowflake 和 ClickHouse 不一樣， 它不再維護(hù) Micro-Partition 內(nèi)部的稀疏索引，稀疏索引的最小粒度就是 Micro-Partition。

?2. 在云端對(duì)象存儲(chǔ)中，讀取整個(gè) Micro-Partition 比在 Micro-Partition 內(nèi)部進(jìn)行部分 Range 雖然 IO 開(kāi)銷稍大，但差異不會(huì)太大，而且對(duì)象存儲(chǔ)一般都有對(duì)象級(jí)別的 Cache，所以 Snowflake 的元數(shù)據(jù)只存儲(chǔ)了 Micro-Partition 粒度的索引。

其他

• 收費(fèi)

Snowflake 的 Auto Clustering 雖然沒(méi)有使用客戶的計(jì)算資源，但費(fèi)用還是要算在用戶頭上的，在 Billing & Usage 頁(yè)面可以看到對(duì)應(yīng)的計(jì)費(fèi)情況。

• ?易用性

目前，市面上大部分?jǐn)?shù)據(jù)倉(cāng)庫(kù)都需要用戶在建表時(shí)指定分區(qū)字段，預(yù)先判斷數(shù)據(jù)的分布情況，這無(wú)疑加重了用戶的使用負(fù)擔(dān)，如果查詢模式跟分區(qū)無(wú)關(guān)，做查詢優(yōu)化則非常困難，Auto Clustering 則很好的解決了這些問(wèn)題。

Databend 社區(qū)也在研發(fā) Auto Clustering 功能，通過(guò)技術(shù)創(chuàng)新不斷提升產(chǎn)品的易用性和智能性。

相關(guān)配圖，參考文章來(lái)源：

? Automatic Clustering at Snowflake

? How does automatic clustering work in Snowflake

? zero-to-snowflake-automated-clustering-in-snowflake

關(guān)于Databend

Databend 是一款開(kāi)源、彈性、低成本，基于對(duì)象存儲(chǔ)也可以做實(shí)時(shí)分析的新式數(shù)倉(cāng)。期待您的關(guān)注，一起探索云原生數(shù)倉(cāng)解決方案，打造新一代開(kāi)源 Data Cloud。

• Databend 文檔：https://databend.rs/

• twitter：https://twitter.com/Datafuse_Labs

• Slack：https://datafusecloud.slack.com/

• Wechat：Databend

• GitHub ：https://github.com/datafuselabs/databend

文章首發(fā)于公眾號(hào)： Databend