Categories
程式開發

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet)


10月26日,字節跳動技術沙龍 | 大數據架構專場 在上海字節跳動總部圓滿結束。我們邀請到字節跳動數據倉庫架構負責人郭俊,Kyligence 大數據研發工程師陶加濤,字節跳動存儲工程師徐明敏,阿里雲高級技術專家白宸和大家進行分享交流。

以下是 Kyligence 大數據研發工程師陶加濤的分享主題沉澱,《Apache Kylin 原理介紹與新架構分享(Kylin On Parquet)》。

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 1

大家好,我是來自 Kyligence 的大數據開發工程師陶加濤,畢業之後就一直在 Kyligence 從事 Apache Kylin 的商業版本的研發。主要參與實現基於 Spark 的新一代的查詢和構建引擎。今天議程分為三個方面:首先我會簡單介紹下Apache Kylin 以及它的查詢原理,接下來我會介紹我們團隊一直在做的Parquet Storage,這個預計會在今年年底貢獻回開源社區,最後我會介紹社區用戶使用非常廣泛的精確去重以及其在Kylin 中的實現以及一些擴展。

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 2

Kylin 使用場景

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 3

Apache Kylin™ 是一個開源的分佈式分析引擎,提供Hadoop/Spark 之上的SQL 查詢接口及多維分析(OLAP)能力以支持超大規模數據,最初由eBay Inc 開發並貢獻至開源社區,它能在亞秒內查詢巨大的Hive 表。

作為一個 SQL 加速層,Kylin 可以下接各種數據源,例如 Hive/Kafka,上接各種 BI 系統,比如 Tableau,PowerBI,也可以直接進行 Ad hoc 的查詢。

如果你們的產品/業務方找到你,說有一批查詢太慢了希望能夠加速,要求查詢速度要快;查詢並發要高;資源佔用要少;完整支持 SQL 語法並且能夠無縫集成 BI,然後又沒有更多的機器給你,那麼這個時候你可以考慮使用 Apache Kylin。

Apache Kylin 基本原理

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 4

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 5

Kylin 的核心思想是預計算,將數據按照指定的維度和指標,預先計算出所有可能的查詢結果,利用空間換時間來加速查詢模式固定的 OLAP 查詢。

Kylin 的理論基礎是 Cube 理論,每一種維度組合稱之為 Cuboid,所有 Cuboid 的集合是 Cube。其中由所有維度組成的 Cuboid 稱為 Base Cuboid,圖中(time,item,location,supplier)即為 Base Cuboid,所有的 Cuboid 都可以基於 Base Cuboid 計算出來。Cuboid 我們可以理解為就是一張預計算過後的大寬表,在查詢時,Kylin 會自動選擇滿足條件的最合適的 Cuboid,比如上圖的查詢就會去找Cuboid(time,item,location),相比於從用戶的原始表進行計算,從 Cuboid 取數據進行計算能極大的降低掃描的數據量和計算量。

Apache Kylin 查詢基本流程

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 6

下面我來簡單介紹下Kylin 查詢的基本原理,前三步是所有Query engine 的常規操作,我們這邊借助了Apache Calcite 框架來完成這個操作,網上相關的資料有很多這裡不做過多展開,感興趣的讀者可以自行查閱。

這邊介紹重點在最後兩步:Kylin 適配和 Query 執行。為什麼要做 Kylin 適配?因為我們前面得到的查詢計劃是直接根據用戶的查詢轉化來的,這個查詢計劃不能直接查詢預計算過的數據,這裡需要rewrite 這個執行計劃,使得它可以查詢預計算過後的數據(也就是Cube數據),來看下面的例子:

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 7

用戶有一張商品訪問表(stock),其中 Item 商品,user_id 表示商品被哪個用戶訪問過,用戶希望分析商品的 PV。用戶定義了一個 Cube,維度是 item,度量是COUNT(user_id),用戶如果想分析商品的 PV,會發出如下的 SQL:

1SELECT item,COUNT(user_id) FROM stock GROUP BY item;

這條SQL 發給Kylin 後,Kylin 不能直接的用它原始的語義去查我們的Cube 數據,這是因為的數據經過預計算後,每個item 的key 只會存在一行數據,原始表中相同item key 的行已經被提前聚合掉了,生成了一列新的measure 列,存放每個item key 有多少user_id 訪問,所以rewrite 的SQL 會類似這樣:

1 SELECT item,SUM(M_C) FROM stockGROUP BY item;

為什麼這裡還會有一步 SUM/ GROUP BY 的操作,而不是直接取出數據直接返回就 OK 了呢?因為可能查詢擊中的Cuboid 不止item 一個維度,即擊中的不是最精確的Cuboid,所以還需從這些維度中再聚合一次,但是部分聚合的數據量相比起用戶原始表中的數據,還是減少了非常多的數據量和計算。並且如果查詢精確的命中Cuboid,我們是可以直接跳過 Agg/GROUP BY 的流程,如下圖:

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 8

上圖是無預計算的場景,全部需要現場計算,Agg 和Join 因為都會牽涉到shuffle 操作,故當數據量很大的時候,性能就會比較差,同時也會佔用更多的資源,這也會影響查詢的並發。

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 9

而進行了預計算過後,原來最耗時的兩步操作 Agg/Join 在後面改寫過的執行計劃上都消失了(Cuboid 精準匹配),甚至更進一步,我們在定義cube 的時候還可以選擇按order by 的列進行排序,那麼Sort 操作也不用計算,整個的計算只是一個stage,沒有一次shuffle,啟動很少的task 就可以完成計算,查詢的並發度也能夠提高。

Kylin On HBase

基本原理

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 10

在目前開源版本的實現中,構建完的數據是存儲在HBase 中的,在上面小節中,我們得到了一個能夠查詢Cube 數據的邏輯執行計劃,Calcite 框架會根據這個邏輯執行計劃生成對應的物理執行計劃,最終每個算子都會通過代碼生成生成自己算子的可執行代碼,這個過程是一個迭代器模型,數據從最底層的TableScan 算子向上游算子流動,整個過程就像火山噴發一樣,故又名Volcano Iterator Mode。而這個 TableScan 生成的代碼會從 HBase 中取出 Cube 數據,當數據返回到 Kylin 的 Query Server 端之後,再被上層的算子一層層消費。

Kylin On HBase瓶頸

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 11

這套方案對於簡單的SQL 並沒有什麼大問題,因為在精確匹配Cuboid 的情況下,從HBase 取回數據後,在Kylin Query Server 端並不會做太多計算,但當一些比較複雜的查詢,例如一句查詢join 了兩個子查詢,每個子查詢都命中了各自的cube,並在最外層做一些比較複雜的Aggregate 操作,比如COUNT DISTINCT 等,在這種情況下,Kylin Query Server 端不僅要從 HBase拉回大量的數據,並且還要在 Kylin Query Server 端計算 Join/Aggregate 等非常耗時耗資源的操作,當數據量變大,Kylin 的Query Server 端就可能會 OOM,解決的方式是提高Query Server 端的內存,但這是個垂直擴容的過程,這就成了一個單點瓶頸,而大數據方案中存在單點瓶頸,是一個非常嚴重的問題,可能直接導致公司在架構選型的時候一鍵pass 掉這個方案。

另外這套方案在使用中還有很多其他的局限:

  1. 例如 HBase 的運維是出了名的難,一旦 HBase 性能不好,那麼可想而知 Kylin 的性能也不會好。
  2. HBase 的資源隔離能力也比較弱,當某個時刻有比較大的負載的時候,其他使用HBase 的業務也會受到影響,體現到Kylin 可能會是查詢的性能比較不穩定,benchmark 會有毛刺,解釋起來比較麻煩並且需要集群metric 的支持,對前線人員要求比較高。
  3. HBase 裡存儲的都是經過編碼後的 Byte Array 類型,序列化反序列化的開銷也不能忽視。而對於我們開發人員來說,Calcite 代碼生成比較難以調試,並且我們 HBase 的技能樹修的比較少,想對 HBase 做源碼級別的性能改進也比較困難。

Kylin On Parquet

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 12

由於上述 Kylin on HBase 方案的諸多局限性,我們公司很早的時候就在商業版本中研發新一代基於 Spark + Parquet 的方案用以替代開源的方案。下面介紹下該方案的整體架構:

其實整體來說,新的設計非常簡潔:使用visitor 模式遍歷之前生成的能夠查詢Cube 數據的邏輯執行計劃樹,執行計劃樹的節點代表一個算子,裡面其實無非就是保存了一些信息,比如要掃哪個表,要filter/project 哪些列等等。將原來樹上的每一個算子都翻譯成一個Spark 對於Dataframe 的一個操作,每個上游節點都問自己的下游節點它處理完之後的一個DF,一直到最下游的TableScan節點,由它生成初始的DF,可以簡單理解成cuboidDF= spark.read.parquet(path),得到初始的DF之後,向它的上游返回,上游節點再對這個下游的DF apply 上自己的操作,再返回給自己的上游,最後最上層節點對這個DF 進行collect 就觸發了整個計算流程。這套框架的思想很簡單,不過中間 Calcite 和 Spark 的 gap 的坑比我們想像的要多一些,比如數據類型/兩邊支持函/行為定義不一致等等。後期我們也有打算替換 Calcite 為 Catalyst,整套的架構會更加精緻自然。

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 13

這一套 Kylin On Parquet 的方案,依託了 Spark:

  1. 所有計算都是分佈式的,不存在單點瓶頸,可以通過橫向擴容提高系統的計算能力;
  2. 資源調度有各種方案可以選擇:Yarn/K8S/ Mesos,滿足企業對於資源隔離的需求;
  3. Spark 在性能方面的努力可以天然享受到,上文提到 Kylin On HBase 的序列化反序列化開銷,就可以由 Spark 的 Tungsten 項目進行優化;
  4. 減少了 HBase 的依賴,帶來了運維極大的方便,所有上下游依賴可以由 Spark 幫我們搞定,減少了自己的依賴,也方便上雲;
  5. 對於開發人員來講,可以對每個算子生成的DF 直接進行進行collect,觀察數據在這一層有沒有出現問題,並且Spark + Parquet 是目前非常流行的SQL On Hadoop 方案,我們團隊對這兩個項目也比較熟悉,維護了一個自己的Spark 和Parquet 分支,在上面進行了很多針對於我們特定場景的性能優化和穩定性提升的工作。

目前該方案正在貢獻回開源社區,等貢獻完之後可以出詳細的benchmark 報告,由於現在沒有貢獻完成,所以這裡沒有兩套方案直接的性能對比數字,但是我們企業版對比開源的數字十分亮眼,查詢穩定性提升也十分明顯,TPCH 1000 下,目前的Kylin On HBase 實現對於一些複雜的查詢無法查詢出結果,Kylin On Parquet 則能在一個合理的時間內查詢出結果。

下面介紹去重分析,去重分析在企業日常分析中的使用頻率非常高,如何在大數據場景下快速地進行去重分析一直是一大難點。 Apache Kylin 使用預計算+ Bitmap 來加速這種場景,實現在超大規模數據集上精確去重的快速響應。

Kylin 中的精確去重

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 14

下面還是由一個例子來引出我們後續的討論:

還是上面的商品訪問表,這次我們希望求商品的 UV,這是去重非常典型的一個場景。我們的數據是存儲在分佈式平台上的,分別在數據節點 1 和 2 上。

我們從物理執行層面上想一下這句SQL 背後會發生什麼故事:首先分佈式計算框架啟動任務,從兩個節點上去拿數據,因為SQL group by 了item 列,所以需要以item 為key 對兩個表中的原始數據進行一次shuffle。我們來看看需要 shuffle 哪些數據:因為 select/group by了 item,所以 item 需要 shuffle 。但是,user_id 我們只需要它的一個統計值,能不能不 shuffle 整個 user_id 的原始值呢?

如果只是簡單的求 count 的話,每個數據節點分別求出對應 item 的 user_id 的 count,然後只要 shuffle 這個 count 就行了,因為 count 只是一個數字,所以 shuffle 的量非常小。但是由於分析的指標是count distinct,我們不能簡單相加兩個節點user_id 的count distinct 值,我們只有得到一個key 對應的所有user_id 才能統計出正確的count distinct 值,而這些值原先可能分佈在不同的節點上,所以我們只能通過shuffle 把這些值收集到同一個節點上再做去重。而當 user_id 這一列的數據量非常大的時候,需要 shuffle 的數據量也會非常大。我們其實最後只需要一個 count 值,那麼有辦法可以不 shuffle 整個列的原始值嗎?我下面要介紹的兩種算法就提供了這樣的一種思路,使用更少的信息位,同樣能夠求出該列不重複元素的個數(基數)。

Bitmap 算法

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 15

第一種要介紹的算法是一種精確的去重算法,主要利用了 Bitmap 的原理。Bitmap 也稱之為 Bitset,它本質上是定義了一個很大的 bit 數組,每個元素對應到 bit 數組的其中一位。例如有一個集合[2,3,5,8]對應的Bitmap 數組是[001101001],集合中的2 對應到數組index 為2 的位置,3 對應到index 為3 的位置,下同,得到的這樣一個數組,我們就稱之為Bitmap。很直觀的,數組中 1 的數量就是集合的基數。追本溯源,我們的目的是用更小的存儲去表示更多的信息,而在計算機最小的信息單位是bit,如果能夠用一個bit 來表示集合中的一個元素,比起原始元素,可以節省非常多的存儲。

這就是最基礎的 Bitmap,我們可以把 Bitmap 想像成一個容器,我們知道一個 Integer 是32位的,如果一個 Bitmap 可以存放最多 Integer.MAX_VALUE 個值,那麼這個 Bitmap 最少需要 32 的長度。一個 32 位長度的 Bitmap 佔用的空間是512 M (2^32/8/1024/1024),這種 Bitmap 存在著非常明顯的問題:這種 Bitmap 中不論只有 1 個元素或者有 40 億個元素,它都需要佔據 512 M 的空間。回到剛才求UV 的場景,不是每一個商品都會有那麼多的訪問,一些爆款可能會有上億的訪問,但是一些比較冷門的商品可能只有幾個用戶瀏覽,如果都用這種Bitmap,它們佔用的空間都是一樣大的,這顯然是不可接受的。

升級版 Bitmap:Roaring Bitmap

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 16

對於上節說的問題,有一種設計的非常的精巧 Bitmap,叫做 Roaring Bitmap,能夠很好地解決上面說的這個問題。我們還是以存放Integer 值的Bitmap 來舉例,RoaringBitmap 把一個32 位的Integer 劃分為高16 位和低16 位,取高16 位找到該條數據所對應的key,每個key 都有自己的一個Container 。我們把剩餘的低 16 位放入該Container 中。依據不同的場景,有 3 種不同的 Container,分別是 Array Container、Bitmap Container 和 Run Container,下文將介紹前面兩種 Container,最後一種 Container 留待讀者自己去探索。

Roaring Bitmap:Array Container

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 17

ArrayContainer 是 Roaring Bitmap 初始化時默認的Container。Array Container 適合存放稀疏的數據,Array Container 內部的數據結構是一個 short array,這個 array 是有序的,方便查找。數組初始容量為 4,數組最大容量為 4096。超過最大容量 4096 時,會轉換為 Bitmap Container。這邊舉例來說明數據放入一個Array Container 的過程:有0xFFFF0000 和0xFFFF0001 兩個數需要放到Bitmap 中,它們的前16 位都是FFFF,所以他們是同一個key,它們的後16 位存放在同一個Container 中;它們的後16 位分別是0 和1,在Array Container 的數組中分別保存0 和1 就可以了,相較於原始的Bitmap 需要佔用512M 內存來存儲這兩個數,這種存放實際只佔用了2+4=6 個字節(key佔2 Bytes,兩個value 佔4 Bytes,不考慮數組的初始容量)。

Roaring Bitmap:Bitmap Container

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 18

第二種 Container 是 Bitmap Container,其原理就是上文說的 Bitmap。它的數據結構是一個 long 的數組,數組容量固定為 1024,和上文的 Array Container 不同,Array Container 是一個動態擴容的數組。這邊推導下1024 這個值:由於每個Container 還需處理剩餘的後16 位數據,使用Bitmap 來存儲需要8192 Bytes(2^16/8),而一個long 值佔8 個Bytes,所以一共需要1024 (8192/8)個long 值。所以一個 Bitmapcontainer 固定佔用內存 8 KB(1024 * 8 Byte)。當 Array Container 中元素到 4096 個時,也恰好佔用 8 k(4096 * 2 Bytes)的空間,正好等於 Bitmap 所佔用的 8 KB。而當你存放的元素個數超過 4096 的時候,Array Container 的大小占用還是會線性的增長,但是 BitmapContainer 的內存空間並不會增長,始終還是佔用 8 K,所以當 ArrayContainer 超過最大容量(DEFAULT_MAX_SIZE)會轉換為 Bitmap Container

我們自己在Kylin 中實踐使用Roaring Bitmap 時,我們發現Array Container 隨著數據量的增加會不停地resize 自己的數組,而Java 數組的resize 其實非常消耗性能,因為它會不停地申請新的內存,同時老的內存在復製完成前也不會釋放,導致內存佔用變高,所以我們建議把 DEFAULT_MAX_SIZE 調得低一點,調成 1024 或者 2048,減少 ArrayContainer 後期 reszie 數組的次數和開銷

Roaring Bitmap:Container 總結

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 19

用一張圖來總結3種Container 所佔的存儲空間,可以看到元素個數達到4096 之前,選用Array Container 的收益是最好的,當元素個數超過了4096 時,ArrayContainer 所佔用的空間還是線性的增長,而Bitmap Container 的存儲佔用則與數據量無關,這個時候Bitmap Container 的收益就會更好。而 Run Container 佔用的存儲大小完全看數據的連續性,因此只能畫出一個上下限範圍 (4Bytes,128KB)。

再看去重場景

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 20

我們回到剛剛的去重場景,看看使用了 Bitmap 會給我們帶來什麼增益:無優化 case 下,每個 item 對應的 user_id 就可以看成存儲原始值的一個集合;在使用Bitmap 優化的 case 下,每個 item 對應的 user_id 就可以看成一個 Bitmap 實例,Bitmap 實例佔用的空間都會比直接存儲原始值的集合要小(大部分情況下),這就達到了我們開始提的減少 shuffle 數據量的需求

Kylin 精確去重在用戶行為分析中的妙用

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 21

Bitmap 不僅支持高效的 OR 操作,還支持高效的 AND 的操作,例如上圖中的例子,我們可以直接使用之前建立的 Bitmap 來分析用戶行為。

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 22

為了便於在 SQL 中做“與”操作,Kylin 提供了一個自定義函數:“intersect_count”(詳見Apache Kylin官方文檔)。顧名思義這個函數就是求交集以後的結果數。

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 23

可以看到在其他Query engine 中,計算用戶的兩天留存率,需要join 兩個子查詢,並且有三個count distinct 的Aggregate,可想而知這個性能不會太好,而Kylin 只需要直接使用intersect_count 函數就可以支持此類分析。

Apache Kylin 原理介紹與新架構分享(Kylin On Parquet) 24

QA集錦

提問:Kylin on Parquet 怎麼使用 Spark,通過 Thrift Server 嗎?

回答:Kylin 在啟動的時候時候會往 Yarn 上提交一個常駐的 SparkContext,Kylin 作為driver 端,後續的查詢都發到這上面去進行計算。

提問:Bitmap 對於非數字的數據怎麼處理?

回答:會對這些類型的數據建立全局字典,得到每個數據對應的一個 ID,用以建立 Bitmap。

提問:全局字典怎麼用,查詢的時候每次都要用到全局字典嗎?

回答:全局字典只在構建的時候使用,用以生成 Bitmap,構建完成之後 Cube 數據上就會多一個 Bitmap 列,查詢的時候就直接對 Bitmap 進行聚合就可以了。

提問:構建的 Cube 佔用的空間會不會很大?

回答:這個要分情況來討論,如果沒有任何剪枝,Cube 就會有”維度的詛咒”,空間膨脹的會非常厲害,所以Kylin 有一套剪枝機制,例如ABC 三個維度一定會分析,那麼ABD 這樣的Cuboid 就可以剪枝掉,這個具體可以查看Kylin 官網文檔。

作者介紹

陶加濤,Kyligence 大數據研發工程師。

本文轉載自公眾號字節跳動技術團隊(ID:toutiaotechblog)。

原文鏈接

https://mp.weixin.qq.com/s/fpjAnfwFCOIOU0dDqs1Q3g