作者: 康凱森
日期: 2017-11-02
分類:?OLAP
本文主要介紹Druid Storage的原理蕊程，包括Druid Storage的存儲格式剥懒，不同列的Serde方式啤覆，以及Druid Storage的底層查詢原理。在介紹Druid Storage之前秧荆，我先對Druid的整體架構和核心概念做下簡單介紹亚亲。
What is Druid
Druid是一個開源的實時OLAP系統(tǒng)氏堤，可以對超大規(guī)模數(shù)據(jù)提供亞秒級查詢，其具有以下特點：
列式存儲
倒排索引 （基于Bitmap實現(xiàn)）
分布式的Shared-Nothing架構 （高可用慢蜓，易擴展是Druid的設計目標）
實時攝入 （數(shù)據(jù)被Druid實時攝入后便可以立即查詢）
Why Druid
為了能夠提取利用大數(shù)據(jù)的商業(yè)價值亚再，我們必然需要對數(shù)據(jù)進行分析，尤其是多維分析胀瞪， 但是在幾年前针余，整個業(yè)界并沒有一款很好的OLAP工具，各種多維分析的方式如下圖所示：
其中直接基于Hive凄诞，MR圆雁，Spark的方式查詢速度一般十分慢，并發(fā)低帆谍；而傳統(tǒng)的關系型數(shù)據(jù)庫無法支撐大規(guī)模數(shù)據(jù)伪朽；以HBase為代表的NoSQL數(shù)據(jù)庫也無法提供高效的過濾，聚合能力汛蝙。正因為現(xiàn)有工具有著各種各樣的痛點烈涮，Druid應運而生朴肺，以下幾點自然是其設計目標：
快速查詢
可以支撐大規(guī)模數(shù)據(jù)集
高效的過濾和聚合
實時攝入
Druid 架構
Druid的整體架構如上圖所示，其中主要有3條路線：
實時攝入的過程： 實時數(shù)據(jù)會首先按行攝入Real-time Nodes坚洽，Real-time Nodes會先將每行的數(shù)據(jù)加入到1個map中戈稿，等達到一定的行數(shù)或者大小限制時，Real-time Nodes 就會將內存中的map 持久化到磁盤中讶舰，Real-time Nodes 會按照segmentGranularity將一定時間段內的小文件merge為一個大文件鞍盗，生成Segment，然后將Segment上傳到Deep Storage（HDFS跳昼，S3）中般甲，Coordinator知道有Segment生成后，會通知相應的Historical Node下載對應的Segment鹅颊，并負責該Segment的查詢间雀。
離線攝入的過程： 離線攝入的過程比較簡單财松，就是直接通過MR job 生成Segment媒区，剩下的邏輯和實時攝入相同：
用戶查詢過程： 用戶的查詢都是直接發(fā)送到Broker Node扩然，Broker Node會將查詢分發(fā)到Real-time節(jié)點和Historical節(jié)點，然后將結果合并后返回給用戶帝雇。
各節(jié)點的主要職責如下：
Historical Nodes
Historical 節(jié)點是整個Druid集群的骨干挽牢，主要負責加載不可變的segment，并負責Segment的查詢（注意摊求，Segment必須加載到Historical 的內存中才可以提供查詢）禽拔。Historical 節(jié)點是無狀態(tài)的，所以可以輕易的橫向擴展和快速恢復室叉。Historical 節(jié)點load和un-load segment是依賴ZK的睹栖，但是即使ZK掛掉，Historical依然可以對已經(jīng)加載的Segment提供查詢茧痕，只是不能再load 新segment野来，drop舊segment。
Broker Nodes
Broker 節(jié)點是Druid查詢的入口踪旷，主要負責查詢的分發(fā)和Merge曼氛。 之外，Broker還會對不可變的Segment的查詢結果進行LRU緩存令野。
Coordinator Nodes
Coordinator 節(jié)點主要負責Segment的管理舀患。Coordinator 節(jié)點會通知Historical節(jié)點加載新Segment，刪除舊Segment气破，復制Segment聊浅，以及Segment間的復雜均衡。
Coordinator 節(jié)點依賴ZK確定Historical的存活和集群Segment的分布。
Real-time Node
實時節(jié)點主要負責數(shù)據(jù)的實時攝入低匙，實時數(shù)據(jù)的查詢旷痕，將實時數(shù)據(jù)轉為Segment，將Segment Hand off 給Historical 節(jié)點顽冶。
Zookeeper
Druid依賴ZK實現(xiàn)服務發(fā)現(xiàn)欺抗，數(shù)據(jù)拓撲的感知，以及Coordinator的選主强重。
Metadata Storage
Metadata storage（Mysql） 主要用來存儲 Segment和配置的元數(shù)據(jù)佩迟。當有新Segment生成時，就會將Segment的元信息寫入metadata store, Coordinator 節(jié)點會監(jiān)控Metadata store 從而知道何時load新Segment竿屹，何時drop舊Segment。注意灸姊，查詢時不會涉及Metadata store拱燃。
Deep Storage
Deep storage (S3 and HDFS)是作為Segment的永久備份，查詢時同樣不會涉及Deep storage力惯。
Column
Druid中的列主要分為3類：時間列碗誉，維度列，指標列父晶。Druid在數(shù)據(jù)攝入和查詢時都依賴時間列哮缺，這也是合理的，因為多維分析一般都帶有時間維度甲喝。維度和指標是OLAP系統(tǒng)中常見的概念尝苇，維度主要是事件的屬性，在查詢時一般用來filtering 和 group by埠胖，指標是用來聚合和計算的糠溜，一般是數(shù)值類型，像count,sum直撤，min非竿，max等。
Druid中的維度列支持String谋竖，Long红柱，F(xiàn)loat，不過只有String類型支持倒排索引蓖乘；指標列支持Long锤悄，F(xiàn)loat，Complex嘉抒， 其中Complex指標包含HyperUnique铁蹈，Cardinality，Histogram，Sketch等復雜指標握牧。強類型的好處是可以更好的對每1列進行編碼和壓縮容诬， 也可以保證數(shù)據(jù)索引的高效性和查詢性能。
Segment
前面提到過沿腰，Druid中會按時間段生成不可變的帶倒排索引的列式文件览徒，這個文件就稱之為Segment，Segment是Druid中數(shù)據(jù)存儲颂龙、復制习蓬、均衡、以及計算的基本單元措嵌， Segment由dataSource_beginTime_endTime_version_shardNumber唯一標識躲叼，1個segment一般包含5–10 million行記錄，大小一般在300~700mb企巢。
Segment的存儲格式
Druid segment的存儲格式如上圖所示枫慷，包含3部分：
version文件
meta 文件
數(shù)據(jù)文件
其中meta文件主要包含每1列的文件名和文件的偏移量。（注浪规，druid為了減少文件描述符或听，將1個segment的所有列都合并到1個大的smoosh中，由于druid訪問segment文件的時候采用MMap的方式笋婿，所以單個smoosh文件的大小不能超過2G誉裆，如果超過2G，就會寫到下一個smoosh文件）缸濒。
在smoosh文件中足丢，數(shù)據(jù)是按列存儲中，包含時間列庇配，維度列和指標列霎桅，其中每1列會包含2部分：ColumnDescriptor和binary數(shù)據(jù)。其中ColumnDescriptor主要保存每1列的數(shù)據(jù)類型和Serde的方式讨永。
smoosh文件中還有index.drd文件和metadata.drd文件滔驶，其中index.drd主要包含該segment有哪些列，哪些維度卿闹，該Segment的時間范圍以及使用哪種bitmap揭糕；metadata.drd主要包含是否需要聚合，指標的聚合函數(shù)锻霎，查詢粒度著角，時間戳字段的配置等。
指標列的存儲格式
我們先來看指標列的存儲格式：
指標列的存儲格式如上圖所示：
version
value個數(shù)
每個block的value的個數(shù)（druid對Long和Float類型會按block進行壓縮旋恼，block的大小是64K）
壓縮類型 （druid目前主要有LZ4和LZF倆種壓縮算法）
編碼類型 （druid對Long類型支持差分編碼和Table編碼兩種方式吏口，Table編碼就是將long值映射到int，當指標列的基數(shù)小于256時，druid會選擇Table編碼产徊，否則會選擇差分編碼）
編碼的header （以差分編碼為例昂勒，header中會記錄版本號，base value舟铜，每個value用幾個bit表示）
每個block的header （主要記錄版本號戈盈，是否允許反向查找，value的數(shù)量谆刨，列名長度和列名）
每1列具體的值
Long型指標
Druid中對Long型指標會先進行編碼塘娶，然后按block進行壓縮。編碼算法包含差分編碼和table編碼痊夭，壓縮算法包含LZ4和LZF刁岸。
Float型指標
Druid對于Float類型的指標不會進行編碼，只會按block進行壓縮她我。
Complex型指標
Druid對于HyperUnique虹曙，Cardinality，Histogram鸦难，Sketch等復雜指標不會進行編碼和壓縮處理，每種復雜指標的Serde方式由每種指標自己的ComplexMetricSerde實現(xiàn)類實現(xiàn)员淫。
String 維度的存儲格式
String維度的存儲格式如上圖所示合蔽，前面提到過，時間列介返，維度列拴事，指標列由兩部分組成：ColumnDescriptor和binary數(shù)據(jù)。 String維度的binary數(shù)據(jù)主要由3部分組成：dict圣蝎，字典編碼后的id數(shù)組刃宵，用于倒排索引的bitmap。
以上圖中的D2維度列為例徘公，總共有4行牲证，前3行的值是meituan，第4行的值是dianing关面。Druid中dict的實現(xiàn)十分簡單坦袍，就是一個hashmap。圖中dict的內容就是將meituan編碼為0等太，dianping編碼為1捂齐。 Id數(shù)組的內容就是用編碼后的ID替換掉原始值，所以就是[1,1,1,0]缩抡。第3部分的倒排索引就是用bitmap表示某個值是否出現(xiàn)在某行中奠宜，如果出現(xiàn)了，bitmap對應的位置就會置為1，如圖：meituan在前3行中都有出現(xiàn)压真，所以倒排索引1：[1,1,1,0]就表示meituan在前3行中出現(xiàn)娩嚼。
顯然，倒排索引的大小是列的基數(shù)*總的行數(shù)榴都，如果沒有處理的話結果必然會很大待锈。不過好在如果維度列如果基數(shù)很高的話，bitmap就會比較稀疏嘴高，而稀疏的bitmap可以進行高效的壓縮竿音。
Segment生成過程
Add Row to Map
Begin persist to disk
Write version file
Merge and write dimension dict
Write time column
Write metric column
Write dimension column
Write index.drd
Merge and write bitmaps
Write metadata.drd
Segment load過程
Read version
Load segment to MappedByteBuffer
Get column offset from meta
Deserialize each column from ByteBuffer
Segment Query過程
Druid查詢的最小單位是Segment，Segment在查詢之前必須先load到內存拴驮，load過程如上一步所述春瞬。如果沒有索引的話，我們的查詢過程就只能Scan的套啤，遇到符合條件的行選擇出來宽气，但是所有查詢都進行全表Scan肯定是不可行的，所以我們需要索引來快速過濾不需要的行潜沦。Druid的Segmenet查詢過程如下：
構造1個Cursor進行迭代
查詢之前構造出Fliter
根據(jù)Index匹配Fliter萄涯，得到滿足條件的Row的Offset
根據(jù)每列的ColumnSelector去指定Row讀取需要的列。
Druid的編碼和壓縮
前面已經(jīng)提到了唆鸡，Druid對Long型的指標進行了差分編碼和Table編碼涝影，Long型和Float型的指標進行了LZ4或者LZF壓縮。
其實編碼和壓縮本質上是一個東西争占，一切熵增的編碼都是壓縮燃逻。 在計算機領域，我們一般把針對特定類型的編碼稱之為編碼臂痕，針對任意類型的通用編碼稱之為壓縮伯襟。
編碼和壓縮的本質就是讓每一個bit盡可能帶有更多的信息。
總結
本文主要分享了Druid Storage的眼里握童，既然Druid Storage專門為了OLAP場景設計姆怪，我們在Kylin中是不是可以用Druid Storage 替換掉HBase呢？ 下一篇我將分享《Apache Kylin on Druid Storage 原理和實踐》
原文鏈接：
