探索 Snowflake Automatic Clustering 設計

Context

Snowflake IPO 大火之後大家開始慢慢了解到這個完全基於雲架構而設計的新式數據倉庫。

Snowflake 利用雲端近似無限的計算和存儲資源，基於存算分離的新式架構，真正實現了按需、按量的付費模式，極大的降低了用戶的使用成本，讓用戶更加專注於數據價值的挖掘。對於傳統的數據倉庫來說，Snowflake 就像一塊降維打擊的二向箔。

在業務增長過程中，用戶的數據持續增長，從而導致單表變大，查詢的 SQL 模式也可能會發生變化，這時問題就出現了：之前比較快的查詢現在變慢了。Snowflake 爲了解決這個問題，提供了一個硬核功能：**Auto Clustering，**讓你在建表時無需指定任何分區字段，而查詢則越跑越快。這裏我們就來探索下 Snowflake 的 Auto Clustering 機制是如何實現的。

什麼是 Auto Clustering

Snowflake 的 Clustering 功能和傳統數據的 Partition 功能類似。但在傳統的數據庫系統中，大多依賴一些靜態的分區規則來實現數據的物理隔離，如按時間，按用戶特徵 hash 等等，在 Hive 等數據倉庫中，最常見到的還是按照時間分區。當一個帶有分區字段相關查詢過來的時候，分區的裁剪可以直接忽略掉不匹配的數據，這樣就可以大大減少了數據的讀取和計算，從而提高查詢性能。注意：這裏的 Clustering 是指分組、聚類的意思，注意不要理解爲分佈式、集羣等概念。

靜態分區用法非常簡單，比如在 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

開發人員在建表的時候必須知道數據的分佈情況和將來面對的查詢模式，增加了用戶的心智負擔。它有以下缺點：

• 靜態分區的規則是固定的，但數據卻是隨時間在變化的，比如業務持續增長過程中，按天分區的表新的分區會變大，從而導致分區分佈不均勻。

Snowflake 在設計中完全拋棄了傳統的靜態 Partition 概念，而是提出了 Auto Clustering 的新設計。簡而言之，用戶再也不用關心我的表是如何分區了，用戶只管寫入和查詢就是，數據分組，性能優化我會自動做！

Micro Partition (微分區)

Micro Partition（微分區）

雖然拋棄了靜態分區，但 Snowflake 裏面還是有 Micro-Partition 和 Cluster Key 的概念。

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

• Micro-Partition 是數據的基本組成單元，一個表的數據由多個 Micro-Partition 組成。我們可以將它理解爲一個物理文件，這個物理文件限制在 50 MB-500 MB 的大小（未壓縮），物理文件採用了列式存儲，不同的列存儲在不同的連續空間內。Snowflake 會存儲 Micro-Partition 的信息到元數據服務中，方便查詢時通過元數據索引進行剪枝，如：

  • 每個列的區間索引，最大值、最小值等 (ZoneMap index）

• • 列分佈的直方圖信息

• • 其他..

Clustered Tables

數據表建立後，默認數據是自然序，自然序意味着我們沒有做任何處理，數據就按照流入的順序排列，此時表處於 Unclustered 狀態。當表經歷了 Clustering 後，每個 Micro-Partition 會按照指定的 Key 進行排序，可以理解爲給表加了一個排序鍵，此時表處於 Clustered 狀態。

上圖來自 Snowflake 文檔。

Clustered 的主要目的是讓大部分的查詢能高效的裁剪數據，避免不需要的 IO 讀取和計算。

舉個例子：

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

怎樣讓表達到 Well-Clustered？在原始的數據排列中（自然序），上面的 SQL 會掃描到 4 個 Micro-Partition。而在 Clustered 狀態下，數據已經按照 Cluster Key->(date, type) 進行排序，所以只會掃描到 1 個 Micro-Partition，其他的 Micro-Partition 都被引擎結合了存儲在元數據的索引進行了裁剪過濾。

一般來說，大表不會是靜態的數據，大多會是時序數據，也就是說數據不斷地實時流入。因此，對整個表級別的數據全排序是非常不現實的，不僅代價較高，實時流入的數據也會影響全排序結果。另外一種方法是隻對流入的數據進行排序，這樣雖然新數據有比較好的順序，但隨着數據在不斷地流入，數據整體的順序會逐漸趨於混亂。

結合上面的分析，一個表如果能達到 Well-Clustered（表數據的整體有序度高），這樣查詢才能高效。在這個前提下，還需要保證 “新數據能實時高效流入”（確保 DML 高效），兩者之間存在一個平衡點，Snowflake 的做法是優先保證新數據能實時高效流入，新數據是不需要對數據整體的有序度 “負責”，因爲新數據相比歷史數據來說量級較小，影響的有序度也較小，它只需保證局部有序就行了（確保新數據查詢也能高效）。新數據在後臺會異步進行合併，保證 “表數據的整體有序度高”，也就是說，數據的整體有序是一個漸進的過程，而不是整體絕對有序的。

如何衡量 Well-Clustered ？

如何衡量 Well-Clustered ？

Snowflake 引入了幾個主要的指標來衡量表的 Well-Clustered 程度：

• Overlaps: 在一個 Range 範圍內，有多少個 Micro-Partition 有重疊

• Depth: 在一個數據點中，有多少個 Micro-Partition 有重疊

上面的圖從上到下展示了四種表 Cluster 的狀態，第一種情況是 4 個 Micro-Partition 完全重疊，這種情況是最糟糕的，因爲它沒有任何區分度，命中了 A-Z 這個 Range 的查詢會不可避免地掃描四個分區。隨着 Depth 指標的下降，表中 Micro-Partition 變得逐漸離散，Overlaps 指標也在下降，表也逐漸變得更加 Well-Clustered。

當然，在實際的表分佈中，Micro-Partition 的分佈要達到最下面那樣規整（全局有序）是不現實的，因爲所需要的開銷太大了。

• levels：Micro-Partition 所屬的級別

爲了減少寫放大，Micro-Partition 的合併策略和 LSM-tree 類似，Micro-Partition 在後臺不斷地合併後形成新的 Micro-Partition，每次合併完成後，Micro-Partition 的 Level 值就會自增（clickhouse 也有類似的 Part 合併邏輯），所以 Level 表示的就是 Micro-Partition 經歷過的合併次數（用來衡量經歷過的合併成本）。新數據流入的 Micro-Partition Level 默認是 0，Level 越低的 Micro-Partition 中，Overlaps 和 Depth 指標相對來說會越高，在不斷合併的過程中，Micro-Partition 變得越來越離散，表也變得更加 Well-Clustered。

注意：Micro-Partition 只會和同 Level 的 Micro-Partition 合併， Level 存在最大值，避免寫放大太嚴重。

Auto Clustering 是如何進行的

Auto Clustering 是如何進行的

Auto Clustering 主要分爲兩大任務：

• Part-Selection 任務

• Part-Merge 任務

這塊和 ClickHouse 的邏輯很類似，但明顯的區別是 Snowflake 對雲實在太偏愛了，上面所有的任務都可以在雲端拉起獨立的進程進行，而不需要佔用用戶的計算資源，並且這兩個進程也是微服務化的，可以按需彈性伸縮。

Part-Selection 任務

Part-Selection 任務

Selection 任務會從某個 Level 中選擇出 Micro-Partition 列表集合，選擇的策略是啓發式的。

上面提到的 2 個指標可以構建一個啓發式的算法：

1. Level 低的 Micro-Partition 被選擇的優先級高，因此新流入的數據能有較高優先級合併到下個 Level，Level 越高的 Micro-Partition 除非在有充足的資源情況下，否則不會被合併。

2. Depth 高的 Micro-Partition 被選擇的優先級高。

因此 Selection 的目標就是降低 Level 中 Micro-Partition 的平均深度，AvgDepth。

AvgDepth 又是如何計算的呢？

下面四個 Micro-Partition 的情況下：

我們對每個端點進行分析，如果沒有 overlap，depth 忽略，因爲 depth 的目的就是衡量 overlap 的程度，引入 depth=0 會導致數據有偏差，此時 depth 表示一個端點覆蓋了幾個分區。

最終的計算方式是：

AvgDepth = Sum(DepthOfOverflapPoint) / OverflapPointsCnt

Snowflake 沒有公開具體的 Selection 算法，不過大概是 Level+AvgDepth 結合的一個公式進行排序，我們假設它是以每個 Level 的 AvgDepth 排序選擇某個 Level，然後去順序遍歷此 Level 下的所有端點，超過了 AvgDepth 的連續端點會被選擇作爲 Range。

• 上面的曲線是如何構建的？

橫軸對應的就是 Key 的 Range，縱軸表示 Depth，計算方式大概是：遍歷所有的 Micro-Partition，將 Micro-Partition 的 Range 的 Depth 進行求和（即上面的 DepthOfOverflapPoint )，得出對應端點的 Y 值（這裏應該可以用差分數組的數據結構進行優化）

• 選擇的策略是什麼？

上圖是選擇了兩個 Micro-Partition 列表的集合示例，選擇的方式是順序遍歷所有的端點，如果端點的 Depth 超過了 AvgDepth，就會被選擇，連續選擇的端點構成一個 Range。

• 爲什麼不直接選最高的 Depth？

可以發現最高點 Depth 雖然最高，但覆蓋的 Range 變窄，這樣導致選擇的 Micro-Partition 數量太小，對降低 AvgDepth 的影響較少。

• 選擇的結果是什麼？

看有多少個符合條件的波峯，上圖是兩個符合條件的波峯，這兩個波峯互不重合，可以作爲選擇的結果集合，集合中內包含了 Micro-Partition 的 batches。

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

Part-Merge 任務

Part-Merge 任務

接收到 Selection 的列表後，Part-Merge 可以獨立地進行 Micro-Partition 的排序和合並，類似一個歸併排序的過程。合併後的 Micro-Partition 就是一個全局有序的大 Micro-Partition 了。值得一提的是，合併後的分區如果超過了 500 MB 的閾值上限，就會被分裂成更小的 Micro-Partition，這和 ClickHouse 存儲一個大的分區文件是不同的。

猜測可能是：

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

2. 在雲端對象存儲中，讀取整個 Micro-Partition 比在 Micro-Partition 內部進行部分 Range 雖然 IO 開銷稍大，但差異不會太大，而且對象存儲一般都有對象級別的 Cache，所以 Snowflake 的元數據只存儲了 Micro-Partition 粒度的索引。

其他

• 收費

Snowflake 的 Auto Clustering 雖然沒有使用客戶的計算資源，但費用還是要算在用戶頭上的，在 Billing & Usage 頁面可以看到對應的計費情況。

• 易用性

目前，市面上大部分數據倉庫都需要用戶在建表時指定分區字段，預先判斷數據的分佈情況，這無疑加重了用戶的使用負擔，如果查詢模式跟分區無關，做查詢優化則非常困難，Auto Clustering 則很好的解決了這些問題。

Databend 社區也在研發 Auto Clustering 功能，通過技術創新不斷提升產品的易用性和智能性。

相關配圖，參考文章來源：

• Automatic Clustering at Snowflake

• How does automatic clustering work in Snowflake

• zero-to-snowflake-automated-clustering-in-snowflake

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/AbaSaZN-1Z9oMTba_K9J8g