ClickHouse 在 UBA 系統中的字典編碼優化實踐

ClickHouse UBA 版本是位元組跳動內部在開源版本基礎上為火山引擎增長分析專門深度定製優化的版本。本文介紹在字典編碼方向上的優化實踐，作者系位元組跳動資料平臺研發工程師 Jet He，長期致力於 OLAP 引擎開發優化，在 OLAP 領域、使用者行為線上分析等有豐富的經驗。

背景

雖然 ClickHouse 列存已經有比較好的儲存壓縮率，但面對海量資料時，磁碟空間的佔用跟常用的 Parquet 格式相比仍然有不少差距。特別是對於低基數列時，Parquet 的儲存空間會更加有優勢。

同時，大多這類資料的事件屬性都有低基數的特徵，例如事件屬性中的城市、性別、品牌等等。Parquet 會自動對低基數列做字典編碼，因此會獲得更高的儲存效率。

同時 ClickHouse 官方也提供了一種字典編碼的解決方案即 LowCardinality 型別，網上也有一些測試 Benchmark 資料，效果不錯，可以進一步降低儲存空間和提升查詢、IO 效能。

上圖是內部 LowCardinality 的儲存結構，寫入過程中，會構建一個字典，列資料通過 Positions 表示，數值是字典中每個 Unique 值的 Index。其他更加詳細的介紹可以參考官方文件。

但在內部環境中通過驗證測試發現，原始的 LowCardinality 列存在以下兩個致命問題：

1. 在 LowCardinality 列比較多的情況下(平均 300+)，Part Merge 耗時嚴重，在大量實時寫入的場景下，Merge 速度跟不上寫入速度，最終會導致叢集不可用；
2. 使用者資料中事件屬性多種多樣，UBA 版本通過動態 Map 列實現使用者屬性的自由上報，也會導致某些屬性基數非常大，不再適合做字典編碼，否則會同時導致儲存、計算效能下降。

如果以上兩個問題得不到解決，那麼字典編碼功能就無法上線使用。需要一種解決方案，能夠做到支援大量的列做字典編碼的同時需要保證內部 Part 的 Merge 速度，另外就是面對高基數列時需要一個 Fall back 方案，讓高基數列時不再做字典編碼，改用原始列儲存。原作者在做字典編碼技術分享時也提到了針對高基數列時 Fall back 到原始列的構想，但社群版本中目前沒有付諸實現。

解決方案

首先來看針對 LowCardinality 列 Part Merge 的優化方案。

這裡先介紹下 ClickHouse 的 Part Merge 過程。ClickHouse 的資料組織是以 Part 形式存在的，每個 Part 對應磁碟的一個數據目錄，每次寫入都會生成一個 Part，Part 目錄下包含各個列的資料檔案。因此每次寫入的時候最好是大批量的寫入，才能有較好的寫入吞吐。

ClickHouse 有常駐 Worker 執行緒不斷的做 Part 的 Merge，將小 Part 不斷地 Merge 成大 Part，從而提升查詢效能。如果 Part 不能及時 Merge 會造成嚴重的效能問題，更有甚者還會造成 Inodes 耗盡。

當統一把事件屬性列（Map 列）改為 LowCardinality 列時，發現 Part Merge 耗時嚴重，Part 數會不斷增長，最終會導致叢集不可用。通過 Profile 發現，在 LowCardinality 列 Part Merge 時，耗時主要發生在字典構造上，具體如下圖灰色部分所示：

即在做 Part Merge 過程中，首先會通過 Primary Key 列做排序，然後從每個 Part 中獲取對應的 Row 寫入到一個新的 Part 中。例如一次從 Part1 中取 3 行寫入到新 Part 中，下一次從 Part2 中取 5 行寫入到新 Part 中，寫入到新 Part 時，LowCardinality 首先做構建新的字典，並生成好倒排索引，形成一個新的 LowCardinality 列，然後通過 Column 的 Insert 介面完成寫入。另外在構建字典的過程中，是通過一個 HashTable 實現，這樣在做 Merge 時這塊的效能損耗較大，所以優化的關鍵點就是在於字典的構建過程。

這裡實現了一種先構建字典後做具體 Merge 的思路，即多個 Part 的 Merge 過程中，詞典只需要構建一次，然後接下來的 Merge 只需要將 Index 直接 Append 寫入到新 Part 即可。

整個過程可以分為兩個過程：

01 -Dictionary Merge

首先進行字典的 Merge，在 Merge 的過程中，先將待 Merge 的幾個 Part 中的字典部分做 Merge，生成一個字典，同時記錄下每個 Part 這個列中 Index 的變化，這個變化類似一個轉換矩陣;

Index Merge 過程中將這個轉換矩陣逐個 Apply 到 Part 中的 Index，有時這個轉換矩陣為空，例如 Unique 值很少的列，基本可以保證每個 Part 的字典基本一樣，如果轉換矩陣為空這步操作會直接跳過。

02 -Index Merge

Index Merge 過程跟之前的 Merge 過程一致，只不過這裡不再做字典構建了，會直接將列中的 Index Append 到新列的 Index 中，如下圖所示：

經過這個 Merge 優化後，LowCardinality 的 Merge 效能有明顯提升，在大量寫入的場景也能應付自如，寫入的 Part 可以得到及時 Merge。

具體的效能優化測試資料如下表所示，Merge 速度的是在表寫入過程中統計得出，寫入大量大概 10 億左右：

可以看出在基數 10 萬以內時效能提升非常明顯，當基數 100 萬+時，效能提升不明顯，並且在 1000 萬時還會導致效能回退。這裡也不難理解，因為當基數變大時，Merge 過程中轉換矩陣會變得很大，轉換矩陣的 Apply 的過程就會變成一個新的瓶頸點。解決這一問題的只有 Fall back 方案，即將高基數列自動不做字典編碼。

Fall back 方案在內部做了很多討論，也跟原作者討論了可能的實現方案。

最終通過 LowCardinality 內部封裝的方式實現。如下圖所示：

Stream 可以理解為檔案流，通過 Version 值標識該列是否是已經是 Fall back 的列。

內部複用了 Index Stream，如果發生了 Fall back 那麼這個 Stream 裡面的值便是原始列的值。Fall back 可以發生在實時寫入過程中和 Part Merge 過程中。如果此列發生了 Fall back 後續的所有 Part 都將是 Fall back 的。

Fall back 後，一個高基數列的 Merge 速度和儲存效能對比，連續寫入 1 億條記錄的統計：

從表中可以看出，Fall back 後的列基本跟原始列效能接近，至少保證 Merge 和儲存效能沒有退化。如果不做 Fall back，儲存空間佔用會比原始列還要多，Merge 效能無法支撐實時寫入。

通過 Merge 優化和自動 Fall back 解決了 LowCardinality 列的兩大絆腳石，接下來看下我們在內部一些大應用上的測試驗證效果。

效能驗證

下面是在內部某些大 APP 上的驗證結果。

1、磁碟佔用

資料表是內部某些 APP 某個時間段的資料。

從上表中可以看出，列越多，資料量越大，儲存空間下降就會越明顯，最高可以節省一半的資料儲存空間。在資料量非常的大 APP 場景下，上線 LowCardinality 後可以節省大量的儲存資源。

2、針對某個 APP，獲取其典型的 10 個業務 SQL，做查詢效能測試。

下面是兩個資料表分別查詢的對比測試結果： 從上圖可以看出，有兩個 SQL 導致查詢效能有回退現象，其餘 SQL 都是 LowCardinality 的表查詢效能更優，耗時更短。

3、10 個查詢對應的磁碟資料讀取量：

可以看出，基本上所有 SQL 讀取的資料量都有明顯的減少，對磁碟 IO 的壓力會降低很多。SQL8 對應的查詢列已經做了 Fall back，所以跟原始列讀取資料量持平。

下圖是查詢時對應的記憶體使用量：

其中除了 SQL8 發生了 Fall back 外，其他查詢均是 LowCardinlity 表記憶體使用量較大。由於 LowCardinality 列計算過程中，如 filter，需要讀取的 Part 字典並將列反解出來，每個 Part 的字典是獨立存在的，這樣在計算過程中會多佔用些記憶體。這塊也是後續優化的重點。

小結

目前 ClickHouse UBA 版已經全面啟用了字典編碼列，並且在火山引擎增長分析（DataFinder）服務的多個客戶環境中已經上線。

從實踐反饋看，我們為客戶節省了大量儲存資源，同時在大多數場景下查詢效能也有提升明顯。總體上由於字典位於每個 Part 中獨立儲存，查詢過程中無法做到在壓縮域直接計算，因而會造成個別場景下查詢效能不佳，並且記憶體使用量上會增加。

下一步工作的重點將是優化 LowCardinality 的計算過程，例如把字典做成 Part 間共享的，可以減少計算過程中記憶體佔用，進一步擴充套件複雜場景在可以直接在壓縮域做計算。

參考文獻

http://github.com/yandex/clickhouse-presentations/raw/master/meetup19/string_optimization.pdf

http://clickhouse.com/docs/en/sql-reference/data-types/lowcardinality/

火山引擎增長分析

一站式使用者分析與運營平臺，為企業提供數字化消費者行為分析洞見，優化數字化觸點、使用者體驗，支撐精細化使用者運營，發現業務的關鍵增長點，提升企業效益。

歡迎關注同名公眾號「位元組跳動資料平臺」