作者: 康凱森
日期: 2017-11-02
分類:?OLAP
本文主要介紹Druid Storage的原理，包括Druid Storage的存儲格式，不同列的Serde方式，以及Druid Storage的底層查詢原理。在介紹Druid Storage之前，我先對Druid的整體架構(gòu)和核心概念做下簡單介紹。
What is Druid
Druid是一個開源的實時OLAP系統(tǒng)，可以對超大規(guī)模數(shù)據(jù)提供亞秒級查詢，其具有以下特點：
列式存儲
倒排索引 （基于Bitmap實現(xiàn)）
分布式的Shared-Nothing架構(gòu) （高可用，易擴展是Druid的設(shè)計目標）
實時攝入 （數(shù)據(jù)被Druid實時攝入后便可以立即查詢）
Why Druid
為了能夠提取利用大數(shù)據(jù)的商業(yè)價值，我們必然需要對數(shù)據(jù)進行分析，尤其是多維分析， 但是在幾年前，整個業(yè)界并沒有一款很好的OLAP工具，各種多維分析的方式如下圖所示：
其中直接基于Hive，MR，Spark的方式查詢速度一般十分慢，并發(fā)低；而傳統(tǒng)的關(guān)系型數(shù)據(jù)庫無法支撐大規(guī)模數(shù)據(jù)；以HBase為代表的NoSQL數(shù)據(jù)庫也無法提供高效的過濾，聚合能力。正因為現(xiàn)有工具有著各種各樣的痛點，Druid應(yīng)運而生，以下幾點自然是其設(shè)計目標：
快速查詢
可以支撐大規(guī)模數(shù)據(jù)集
高效的過濾和聚合
實時攝入
Druid 架構(gòu)
Druid的整體架構(gòu)如上圖所示，其中主要有3條路線：
實時攝入的過程： 實時數(shù)據(jù)會首先按行攝入Real-time Nodes，Real-time Nodes會先將每行的數(shù)據(jù)加入到1個map中，等達到一定的行數(shù)或者大小限制時，Real-time Nodes 就會將內(nèi)存中的map 持久化到磁盤中，Real-time Nodes 會按照segmentGranularity將一定時間段內(nèi)的小文件merge為一個大文件，生成Segment，然后將Segment上傳到Deep Storage（HDFS，S3）中，Coordinator知道有Segment生成后，會通知相應(yīng)的Historical Node下載對應(yīng)的Segment，并負責該Segment的查詢。
離線攝入的過程： 離線攝入的過程比較簡單，就是直接通過MR job 生成Segment，剩下的邏輯和實時攝入相同：
用戶查詢過程： 用戶的查詢都是直接發(fā)送到Broker Node，Broker Node會將查詢分發(fā)到Real-time節(jié)點和Historical節(jié)點，然后將結(jié)果合并后返回給用戶。
各節(jié)點的主要職責如下：
Historical Nodes
Historical 節(jié)點是整個Druid集群的骨干，主要負責加載不可變的segment，并負責Segment的查詢（注意，Segment必須加載到Historical 的內(nèi)存中才可以提供查詢）。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的查詢結(jié)果進行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ù)轉(zhuǎn)為Segment，將Segment Hand off 給Historical 節(jié)點。
Zookeeper
Druid依賴ZK實現(xiàn)服務(wù)發(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的內(nèi)容就是將meituan編碼為0，dianping編碼為1。 Id數(shù)組的內(nèi)容就是用編碼后的ID替換掉原始值，所以就是[1,1,1,0]。第3部分的倒排索引就是用bitmap表示某個值是否出現(xiàn)在某行中，如果出現(xiàn)了，bitmap對應(yīng)的位置就會置為1，如圖：meituan在前3行中都有出現(xiàn)，所以倒排索引1：[1,1,1,0]就表示meituan在前3行中出現(xiàn)。
顯然，倒排索引的大小是列的基數(shù)*總的行數(shù)，如果沒有處理的話結(jié)果必然會很大。不過好在如果維度列如果基數(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到內(nèi)存，load過程如上一步所述。如果沒有索引的話，我們的查詢過程就只能Scan的，遇到符合條件的行選擇出來，但是所有查詢都進行全表Scan肯定是不可行的，所以我們需要索引來快速過濾不需要的行。Druid的Segmenet查詢過程如下：
構(gòu)造1個Cursor進行迭代
查詢之前構(gòu)造出Fliter
根據(jù)Index匹配Fliter，得到滿足條件的Row的Offset
根據(jù)每列的ColumnSelector去指定Row讀取需要的列。
Druid的編碼和壓縮
前面已經(jīng)提到了，Druid對Long型的指標進行了差分編碼和Table編碼，Long型和Float型的指標進行了LZ4或者LZF壓縮。
其實編碼和壓縮本質(zhì)上是一個東西，一切熵增的編碼都是壓縮。 在計算機領(lǐng)域，我們一般把針對特定類型的編碼稱之為編碼，針對任意類型的通用編碼稱之為壓縮。
編碼和壓縮的本質(zhì)就是讓每一個bit盡可能帶有更多的信息。
總結(jié)
本文主要分享了Druid Storage的眼里，既然Druid Storage專門為了OLAP場景設(shè)計，我們在Kylin中是不是可以用Druid Storage 替換掉HBase呢？ 下一篇我將分享《Apache Kylin on Druid Storage 原理和實踐》
原文鏈接：
