探索Snowflake auto clustering 設計

語言: CN / TW / HK

Context

Snowflake IPO 大火之後,大家都開始慢慢了解到這個完全基於雲端計算設計的新式資料倉庫。 Snowflake 的核心在於基於雲端近似無限的計算儲存資源,提供了極致彈性且高效的計算引擎 並且搭配 低成本且同樣彈性伸縮的儲存,大大減少了使用者的心智負擔和資料的計算儲存成本,讓使用者更加專注於發揮資料對業務的價值。對於傳統的資料倉庫來說, Snowflake 就像一塊降維打擊的 二向箔。

在業務增長的過程中,客戶的資料持續增長,從而導致單表變大,對大表的高效分析依賴於一套高效能的查詢引擎。 Snowflake 有一個非常核心的功能: Auto Clustering , 極大地提升了大表的查詢效率。 我們這裡主要探索下, SnowflakeAuto Clustering 功能是如何設計的。

什麼是 Auto Clustering

注意: 這裡的 Clustering 是指分組、聚類 的意思,注意不要理解為分散式、叢集等概念。

Snowflake 的 Clustering 功能 和傳統資料的 Partition 分割槽功能類似。但在傳統的資料庫系統中,大多依賴一些靜態的分割槽規則來實現資料的物理隔離,如按時間,按使用者特徵hash等等,在hive等資料倉庫中,最常見到的還是按照時間分割槽。當一個帶有分割槽欄位相關的查詢過來的時候,分割槽的裁剪可以直接忽略掉不匹配的資料,這樣就可以大大減少了資料的讀取和計算量,從而提高查詢效能。

靜態分割槽用法非常簡單,比如在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 的新設計。簡而言之,使用者再也不用關心我的表是如何如何分割槽了,使用者只管插入和查詢就是了,資料分組,效能優化我會自動做!!!

How ?

Micro Partition (微分割槽)

雖然拋棄了靜態分割槽,但snowflake 裡面還是有 Micro-PartitionCluster Key 的概念。

  • Cluster Key 是排序鍵,可以由多個欄位組成,類似ClickHouse 的 Order Key
  • Micro-Partition 是資料的基本組成單元,一個表的資料是由多個 Micro-Partitions 組成的。 我們可以將它理解為一個物理檔案,這個物理檔案限制在 50MB-500MB 的大小(未壓縮),物理檔案採用了列式儲存,不同的列儲存在不同的連續空間內。Snowflake 會儲存 Micro-Partition 的資訊到元資料服務中,方便查詢的時候通過元資料索引進行剪枝,如:
    • 每個列的區間索引, 最大值最小值等 (ZoneMap index)
    • 列分佈的直方圖資訊
    • 其他..

注: 鑑於 Micro-Partition 的大小可能到500MB, 個人認為 Micro-Partition 的內部按道理應當劃分類似Parquet的pages(clickhouse的mrk),每個page有自己的索引,這樣就可以在 Micro-Partition 內部提高查詢過濾的效能。不過看 Snowflake 目前的設計來說,微分割槽級別索引是最小粒度了,暫時沒有微分割槽內部pages索引了,具體原因未知,文章末尾會提到個人的一些猜測。

Clustered Tables

資料表建立後,預設資料是自然序,自然序意味著我們沒有做任何處理,資料就按照流入的順序排列,此時表處於 Unclustered 狀態。當 表經歷了 Clustering後,每個 Micro-Partitions 會按照指定的 key 進行排序, 可以理解為給表加了一個排序鍵,此時表處於 Clustered 狀態。

上圖來自Snowflake文件。

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

舉個例子:

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

在原始的資料排列中(自然序),上面的SQL會掃描到 4個 微分割槽。而在 Clustered 狀態下,資料已經按照 Cluster Key -> (date, type) 進行排序,所以只會掃描到 1個 微分割槽,其他的微分割槽都被引擎結合了儲存在元資料的索引進行了裁剪過濾。

怎樣讓表達到 Well-Clustered ?

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

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

如何衡量 Well-Clustered ?

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

Micro-Partitions
Micro-Partitions

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

當然,在實際的表分佈中,微分割槽的分佈要達到最下面那樣規整(全域性有序)是不現實的,因為所需要的開銷太大了。

  • levels: 微分割槽所屬的級別

為了減少寫放大,微分割槽的合併策略和 LSM-tree 類似,微分割槽在後臺不斷地合併後形成新的微分割槽,每次合併完成後,微分割槽的 Level 值就會自增(clickhouse也有類似的 Part 合併邏輯),所以 Level 表示的就是微分割槽經歷過的合併次數(用來衡量經歷過的合併成本)。新資料流入的微分割槽 Level 預設是0, Level 越低的微分割槽中, OverlapsDepth 指標相對來說會越高,在不斷合併的過程中,微分割槽變得越來越離散,表也變得更加 Well-Clustered

注意: 微分割槽只會和同Level的微分割槽合併, Level 存在最大值,避免寫放大太嚴重。

Auto Clustering 是如何進行的?

Auto Clustering 主要分為兩大任務:

  • Part-Selection 任務
  • Part-Merge 任務

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

Part-Selection 任務

Selection 任務會從某個 Level 中選擇出微分割槽列表集合,選擇的策略是啟發式的。

上面提到的2個指標可以構建一個啟發式的演算法:

  1. Level 低的優先順序的微分割槽被選擇的優先順序高,因此新流入的資料能有較高優先順序合併到下個Level,Level越高的微分割槽除非在有充足的資源情況下,不會被合併。
  2. Depth 高的微分割槽被選擇的優先順序高。

因此Selection的目標就是降低 Level 中微分割槽的平均深度, AvgDepth

這裡引入一個 AvgDepth 的計算邏輯:

下面四個微分割槽的情況下:

我們對每個端點進行分析,如果沒有overlap,depth忽略,因為depth的目的就是衡量overflap的程度,引入depth = 0會導致資料有偏差,此時depth表示一個端點覆蓋了幾個分割槽。

最終的計算方式是:

AvgDepth = Sum(DepthOfOverflapPoint) / OverflapPointsCnt

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

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

橫軸對應的就是Key的Range, 縱軸表示 Depth,計算方式大概是:遍歷所有的微分割槽,將微分割槽的 Range 的 Depth 進行求和 (即上面的 DepthOfOverflapPoint ),得出對應端點的 Y 值 (這裡應該可以用差分陣列的資料結構進行優化)

  • 選擇的策略是什麼 ?

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

  • 為什麼不直接選最高的Depth ?

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

  • 選擇的結果是什麼 ?

看有多少個符合條件的波峰,上圖是兩個符合條件的波峰,這兩個波峰互不重合,可以作為選擇的結果集合,集合中內包含了微分割槽的 batches。

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

Part-Merge 任務

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

我猜測可能是:

  1. Snowflake 和 ClickHouse不一樣, 它不再維護微分割槽內部的稀疏索引, 稀疏索引的最小粒度就是微分割槽。
  2. 在雲端物件儲存中,讀取整個微分割槽 比 在微分割槽內部進行部分Range 雖然IO開銷稍大,但差異不會太大, 而且物件儲存一般都有物件級別的Cache,所以Snowflake的元資料只儲存了微分割槽粒度的索引。

其他

Selection 和 Merge 進行不會對原始資料持有鎖,也就是說在這兩個過程中都不會卡主使用者資料的查詢和插入。這個優化其實很簡單,就是在合併之後,持有對 合併涉及的微分割槽的鎖,然後標記下新的微分割槽為Active狀態,老的微分割槽為Outdate狀態,非同步GC刪除,一些標誌位的更新,涉及鎖開銷可以忽略不計。

  • 自動合併服務

就是上面講的 Selection 和 Merge 做成兩個獨立的服務非同步執行。 Snowflake 舊版本提供了 手動 Cluster,後面廢棄了,我猜測更多是讓使用者使用便捷,不用去Care Clustering這層操作,因為這些事情後臺會自動做了,不當地頻繁clustering反而增加了不必要的開銷。

  • 收費

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