本文整理自APMCon 2016中國應用性能管理大會數據庫性能優(yōu)化專場優(yōu)酷廣告基礎設施技術專家 張海雷演講《實時OLAP數據倉庫架構優(yōu)化演進》，主要介紹了Druid實時導入、亞秒響應、支持高并發(fā)、高可用性等諸多特性。
在分享之前先自我介紹一下，我來自于優(yōu)酷土豆廣告團隊，負責廣告團隊的Redis Cluster和Druid集群。Druid大家聽過嗎？這個Druid不是那個阿里的數據庫連接池Druid，Druid是一個開源的持續(xù)實時數據庫。
一、需求背景
我先一下需求背景，最剛剛開始的需求就是為DSP廣告主提供實時多維分析報表。然后我們看一下報表的一些需求指標：
?多維鉆取 16個維度，22個metrics
?海量數據 10億量級
?實時性 延遲為分鐘級別。比較致命的就是實時性，產品那邊給我們技術提供的一個技術指標就是延遲為分鐘級別，我們當前要看到前一分鐘的一些數據。
?多維下的UV 每天獨立訪客千萬量級
在接到這個需求之前，我剛剛也是提到了最初是負責Redis Cluster的運維維護，我們并沒有太多的OLAP經驗。接到需求以后，我們就問了一下同行，搞出來了第一個架構。
最左邊就是日志收集，有兩條線，上面一個線就是離線批量處理的架構，下面是實時的，我們先從實時的開始講。實時的就是日志收集了以后，從kafka帶到了Storm，經過ETL到Redis，最終就是通過應用調用Redis獲取實時的數據。離線就是走HDFS，Hive，經過Hive ETL到Mysql里面去，應用層調用Mysql的數據。離線的話需要今天去弄昨天的數據就走Mysql，今天查實時數據就是走Redis，大致架構就是這樣的。接下來介紹一下具體怎么實現。
二、實時架構
實時架構的話我們是采用預算維度符合的metric度量值，維度組合做key，各項metric按照一定的格式拼裝成value，Redis是一個K-V存儲，這樣的話我們讀取的時候先拼好這些key，在Redis里面獲取這些metrics。我舉一個例子，比如說我們是在線廣告行業(yè)，我們?yōu)閺V告主提供這些報表，一個廣告主去查一個投放在地域維度下的曝光，點擊一些數據他有可能是按照投放加地域組合成一個key，去Redis取出那些曝光。但是這樣是會遇到三個問題。第一個問題就是維度組合膨脹。
因為用K-V存儲的方式必須采用的就是窮舉的方式，預算各種維度的組合。比如說我舉一個例子，假設有4個維度，一個是投放，一個是廣告位，一個是素材，還有剛剛提的地域，我就得是預算一下4個維度所有的組合。有可能就是一階的，也有可能是全階的4個維度的組合，還有三個維度、兩個維度的組合。
有兩個因素決定這個組合一個數量，第一個維度的個數。當維度個數越多，這個組合的數量也是多。還有就是維度組成的稀疏程度，還是以廣告的數據來看，一個投放有可能有多個素材。比如說我們現在有5個廣告，5個投放，5個素材，但是這一個投放并不是說跟5個素材都是相關聯的，只是說跟其中的一個素材或者兩個素材關聯，這樣的話就會產生一定的稀疏，跟所有的關聯那就是很稠密。
另外還有維度的基數，這些概念看起來比較的抽象，我后續(xù)會解釋�？傊畮砹艘粋�問題，增加維度了以后，有可能帶來的就是一個指數式增長。
另外一個問題如何支持Group By查詢？我們都知道Redis不支持Range Scan，它只支持前綴查找。這個前綴查找沒有索引，他是在Redis整個HashTable里面進行Scan，如果我們這個Redis容量很大，比如說我有1千萬，那可能要掃描1千萬才可以得到這個結果，這個是最害怕的地方。我們做法就是在應用層窮舉這個維度組合，然后再采用MGET的方式在Redis中獲取這個數據。
這種方案適合特定場景，我在應用層已經知道了這個廣告投放有什么素材在那些廣告位上面進行投放過。如果說是不可預知的，比如說在那些域名下投放有可能是一個開放的，這個時候這個方案不適用了。
第三個問題，如何實現UV？Redis是支持HyperLogLog的，是一個基數的近似的一個統(tǒng)計。
我現在舉一個例子提上一頁說到的維度組合膨脹的問題，假設我們有3個維度，每一個維度基數都是3，在這里提到一個概念就是維度的基數。什么是基數？就是這個維度的集合當中不重復元素的數量。比如說，這個維度A里面有A1、A2、A3，這個里面有4個值，但是不重復的數量就是A1、A2、A3，這個基數就是3。同樣，緯度B也是B1、B2、B3，緯度3就是C1、C2、C3，最差情況下的組合，我們來算一下就是三階維度，組合是ABC，每一個維度基數就是3。ABC一個組合乘3的3次方，就是27。我們看一下兩種維度的組合，排列方式有ab,ac,bc這些。每一種排列的數量是3的2次方，就是9，這樣加起來就是27。然后，一維有可能每一個都是3，加起來就是9。
那么，我們得到的結論是什么了？增加維度以后，維度組合數量有可能是指數增長，不是線性的。試想一下，增加一個維度變成4個，那么這個量級線性增長。當然，這里列舉的是最差的情況，是現實的數據組合是稀疏的。我這里再提一下，我們當初選擇技術方案的時候在這兒也是遇到一個坑，因為我們當初沒有接觸過大數據，一想16個維度有可能原始日志級是10億，有可能16個維度組合起來，怎么著也得有幾億，覺得這個量比較大，我們想到方案的時候，有可能就是造成一個錯誤的選型。后來實現了以后，雖然原始日志級就是10億，我們選取了維度了以后，我們發(fā)現每一天聚合了以后是500萬，500萬跟當初的技術選型上面肯定有不同的。
三、離線架構
接下來說說離線架構，是采用Hive將多種日志源的數據經過ETL以后寫到Mysql全維度的寬表中。這些就是廣告數據，它是有多種的，有競價，有曝光，有點擊，我們需要在Hive里面join一下，合成寬表的方式。我剛剛提到了全維度寬表，比如說，原始數據它有50個維度，但是我們這里是需要16個維度，我們按照這個16個維度Group By，然后增加一些度量值提取出來寫到Mysql里面去。
瓶頸與挑戰(zhàn)的話也是剛剛提到的那個全維度組合的數據量，當初也是錯誤的預估了這個量。
由于預算所有維度組合的時間成本很大，我們進行功能降級。
我們選取了固定的維度組合，沒有實現完整全維度的OLAP，只選取了固定的某一些組合。還拿我剛剛那個例子講一下，有投放素材廣告位地域，并不是說實現任意一個組合，只實現兩兩一個組合。
然后Mysql這邊也是做了一些降級，按照維度組合作為key組件去分表，其實這個分表的做法，就跟Redis的存儲做法一樣的。
剛剛提到的這個方案有一些缺點。
第一，增加維度了以后，給存儲的容量以及計算量帶來很大的一個挑戰(zhàn)。
第二，Redis不支持范圍查找，Group By查詢需要客戶端窮舉維度組合，這個更適合一個特定應用場景可以做到。
第三，Redis和Mysql是屬于異構的數據庫，如果我有一個查詢是要查歷史和實時相結合的查詢，我需要在那個應用層合并。
基于以上的分析三個缺點，我們著手做改進一個工作。我們當時想了2種，第一種就是HBase替換Redis和Mysql。HBase同樣也是K-V存儲，但是有一個優(yōu)點是HBase支持范圍查找，可以做Group By。另外一種我們調研另外一個方案，也是在廣告領域廣泛應用一個OLAP技術，就是Druid。
四、Druid是什么
Druid其實開源比較早，11年就開源了，今年4月份的時候Druid作者來中國，我們跟他交流創(chuàng)建Druid的目的是什么？當時他們在一個技術創(chuàng)業(yè)公司，提供的方案是為廣告提供實時多維分析。當時他們也是嘗試了很多的方案，跟我剛剛最初提到的Mysql，還有HBase方案都是很像。但是，如果實現真正的OLAP還是有一定的差距。所以，他們就是創(chuàng)立了Druid，是為OLAP而生，我列舉了幾個特點，多快好省高，現在逐一解釋一下。
?多，可以處理海量的數據， Druid官網說可以擴展到PB級，這個量非常大。
?快，亞秒級響應，官網說10億量級下做到亞秒響應，我們實際應用也是亞秒響應，實時導入，導入即可查詢。導入了以后我們就可以查詢到，這個還是非常非常的牛的。
?好，就是高可用，分布式容錯架構，可以做到無宕機。
?省，采用列存儲，高效壓縮。我舉一下我們的例子，我們原始日志是10億量級，我們選取16個維度，22個度量值，每天生成的索引是幾百兆。
?高，它支持高并發(fā)，可以是作為面向用戶的應用
1.Druid支持的查詢
接一下講一下Druid支持的查詢，它是支持這樣幾種查詢：TimeSeries、GroupBy、TopN、Select等常用查詢。
還有二點特別重要，就是支持星型模型，提供一個lookup的功能可以實現和維度表的join。星型模型如上圖中間就是維度表，舉一個例子，我們這個表里面有可能還有一些ID是產品ID，地域ID，當我們給用戶展現的時候，不可能給用戶展現一些ID，展現的時候我們通常是采用ID在維度表里面join獲取ID對應的名稱。但是Druid不支持join，是提供的lookup功能得到查詢結果了以后，得到是一個ID，可以根據ID去找到其中的內容。所以，這就是為什么是適合新型模型。
第三，支持的函數是count和sum。OLAP當中count和sum基本上可以滿足90%以上的需求。比如說我們要求一個曝光數，點擊數這個就是一個sum。當然，還有一些率比如說點擊率，這些都是可以通過后處理的方式去得到。
另外可以采用java的方式實現自定義的UDF，就像剛剛說到的那個轉化率，我得到了一個曝光數一個點擊數，兩者相除可以把這個做到UDF，做到JS的函數里面去。
另外一點，支持可擴展自定義的Aggregator，它的代碼設計的非常靈活，非常容易實現自定義模塊。
比如說阿里貢獻了利用BitMap實現精準的DistinctCount，不知道大家在實際工作場所當中有沒有DistinctCount的需求？這個還是挺重要的。比如說，我要查一天的UV，或者某一種維度下的UV，前面提到了用HyperLogLog，但是只是一個近似查詢，會帶來一定誤差，精準的方式就是采用BitMap。
最后一點，就是支持近似查詢。比如說像HyperLogLog用于計算UV，還有比較牛的DataSketches，同樣也是可以計算UV，但是它與HyperLogLog不同的是，HyperLogLog只可以做并集，它可以把昨天跟今天的合并得到一個總的UV數，但是它做不到一個交集。我現在做一個用戶的留存分析怎么做？就是得到昨天一個集合，跟今天的一個集合做一個交集，HyperLogLog是做不到的，DataSketches 可以做到。
2、數據格式
了解Druid從數據格式開始，Druid是一個實時數據庫，所以這個時間戳非常重要，作為一個數據分片，路由查詢一個重要的維度，所以它單獨提出來。另外，還有一個metric度量值，這是它與其他的大部分的OLAP不同的一點。比如說，其他的好多都沒有把度量值跟維度明確地區(qū)分出來，但是Druid是明確區(qū)分了，這是為了存儲還有計算上面需求而需要的，因為維度是需要進行索引的。我們的索引都是在維度上面做一個過濾，但是，度量值一般就是一個聚合計算，不需要索引。
上圖下面的數據就是一個在線廣告的數據，我是從Druid官網上面拉下來的。最下面就是時間戳，中間4列像媒體廣告主，性別，國家，最后兩個就是點擊，跟扣費價格是一個度量值。
3、Roll-up
Roll-up是Druid非常有用的特性，它保證了低延遲響應時間。Roll-up就是數據導入階段進行的一次聚合，第一層聚合。上圖下面用SQL展示Roll-up 的做法，相當于進行了一次GroupBy，全維度的GroupBy。Roll-up有一個優(yōu)點，它會大大地減少數據集的大小，甚至可能就是百倍以上。我剛剛舉了一個例子，我們原始數據集在10億左右，Roll-up 了以后有500萬，這個Roll-up 減少的數據集大概在20倍，極端的情況下如果你選取的維度比較少的話，減少的數據集有可能是百萬級。缺點就是說它會丟失明細數據，因為你在導入的時候已經做了一層聚合，你看不到明細數據。
4、Druid高效的奧秘-數據布局
接下來會比較有意思，我剛才講的Druid的幾個特性，比如說它能處理海量數據，能擴展到PB級和亞秒級響應，我們來看它為什么能做到這幾點。
同樣還是由剛才列舉的這些數據來看，比如說上面這部分數據，它有投放、廣告位，我們由上一份數據來分析它的維度。然后就是曝光數、點擊數，這是度量值。這樣的一份數據，它是怎么編制成索引的呢？或者說Druid是怎么進行存儲的呢？以投放這維度來分析，首先它會進行一個字典編碼，投放這維度里面有C1，C2，C2，C3。我剛才提到一個概念是基數，它的基數是3，它會把C1, C2, C3構建成一個字典，字典編碼值就是它在這個字典數組中的下標。C1，C2，C3編碼值分別變成了0，1，2，存儲時我們不再存C1，C2，C2，C3，而是0，1，1，2。
同時我們采用倒排索引，最后我列出的這個黃色的部分。說道倒排索引，大家很容易想到Lucene，它其實跟Lucene的倒排索引很像，有一點不同就是Druid的token list采用了BitMap，最新版本的Lucene也采用了BitMap。我們來看一下BitMap是怎么做的，比如說C1，它只出現在第一行它的BitMap就是1000，C2它只出現在第2，3行，C2的BitMap是0110，同理C3只出現在第4行，C3的BitMap是0001。
以上大概就是Druid的索引和數據布局，同理我可以得到下面的廣告位的數據布局。那么度量值怎么存儲呢？剛才提到度量值是不做索引的，它只是用于一個快速的聚合，所以度量值就只是一個原樣存儲。這里只是一個示例，在真實存儲的時候它會加上一些壓縮，后續(xù)我會介紹，接下來講一下它是怎么查詢的。
5、Druid高效的奧秘-BitMap 快速Filter
如果使用BitMap，假設我有一個SQL是上面這個Sele ct Position ,su m (click) fro m t able whe re cast=C2 Gro up By Position，投放是C2，按照廣告位分組，去查其點擊數該怎么做呢？過程如下：
第一步，根據過濾條件cast=C2,找到C2的字典值是1；
第二步，根據字典值1找到BitMap 0110.
第三步，根據BitMap得到offset是1和2。也就是根據BitMap的值0110去看它出現在那幾個位置，這里出現的位置是第2位和第3位，對應下標是1和2。
第四步，我們可以根據這個offset1，2去構建一個curs or游標去進行遍歷。
第五步，單次迭代的時候根據offset1在廣告位position中綠色這部分偏移為1的廣告位是0，在點擊position中，藍色的這部分偏移為1的值是21，這是單次迭代的結果。接下來進行下一次迭代，下一次迭代的時候offset變成2了，在廣告位綠色部分offset為2的偏移后得到的值是1，在點擊藍色部分offset為2的偏移后得到的值是14。對廣告位來說，最后得到的字典編碼為01，我們需要根據字典編碼01去反查p1,p2，0對應21，1對應14，也就是p1廣告位的點擊數是21，p2廣告位的點擊數是14。相對于Lucene原來的parse list采用的skiplist跳表的方式，BitMap執(zhí)行的速度是非常快的。
6、Druid高效的奧秘-列存儲和壓縮
接下來看下列存儲和壓縮，上面講的僅僅是一個查詢的示例，但真正采用的是列存儲和高效的壓縮。列存儲的優(yōu)點就是按列存儲，比如說我要去讀廣告位這一列數據，就不需要讀其他的。另外一點好處列存儲可以采用字典編碼，就是剛剛提到的會把C1，C2，C3編制成0，1，2，會把一個字符串轉換成一個整數。所有的壓縮，我覺得都是基于一個概率了，比如說這個串都很長我把它轉化成一個int，這個時候壓縮效率比較高。
再接下來看一下BitMap的壓縮，BitMap支持兩種不同的壓縮方式，一種是concise BitMap，一種是roaring BitMap。BitMap它的一個優(yōu)點就是計算快，但是它缺點占用空間大，同時它的一個特征就是比較稀疏的。舉一個例子，比如說我們有一億用戶，用戶ID都是整的，比如說就是1到1億，根據這一個億用戶構建一個BitMap。假設我每天活躍的只有2千萬，當用戶ID是1億的第一億個用戶來了，我們?yōu)樗嫿ㄒ粋�BitMap，那它的長度肯定就是一億除了以8，這個空間還是非常大的。但是活躍沒有那么多時候，假設活躍幾百萬我不能不為一億用戶去浪費這樣大一個空間。
剛剛提到了dimension，它的壓縮有字典編碼，還有變長整數編碼，很多的RPC的續(xù)量化方式里面都是用到這個變長整數編碼，Druid里面用到的編碼非常的高效。我下面列舉一下。
前面提到了就是把維度進行字典編碼，在整數基礎上做一個變長整數編碼。怎么做的呢？比如說我的字典是1千，這個維度當中1000個不同的數，它的最大的值就是1千，這1千其實可以用一個短整存儲，2個字節(jié)就可以存儲，而不是用4個字節(jié)，這個壓縮方式是非常非常的高效。
再舉一個例子，一個維度的基數是50%，其實一個字節(jié)就可以存儲。那么這個時候，原來用4個字節(jié)存儲int現在一個字節(jié)壓縮了25%。在其他的變長整數壓縮里面標識一個位占用幾個字節(jié)，但是Druid里面因為它字典的那個是一定的。這個1000就是2個字節(jié)編碼，不用再用位占一個字節(jié)。
metric是按塊壓縮，默認64K。而且，必須是2整數倍，這個是非常非常的有意義的，必須這樣做，他方便定位。
7、Druid架構
下面來看一下Druid的架構，它是由一系列不同的決策節(jié)點組成。有Realtime，有Coordinator，有Broker，還有Historical，下面來分別介紹一下他們每一個節(jié)點的作用。
Realtime：
?實時接收(拉取)數據，生成Segment
?負責實時部分的查詢
?采用類LSM-tree的架構，對寫友好，支撐高并發(fā)和高吞吐量的寫入
?內存增量索引采用ConcurrentSkipListMap
?達到閾值以后，異步線程將內存增量索引持久化成倒排索引
?達到Segment設定的時間粒度時，將這一時間段內的持久化索引合并成Segment
?具體實現有Realtime Node和Indexing Service兩種方式
Coordinator：
?負責協調Segment的均衡加載
?動態(tài)均衡Historical節(jié)點的負載
?根據用戶指定的Load Rule加載指定時間段的Segment
Historical：
?Historical是查詢的主力
?從Deep Storage中拉取Segment，采用mmap的方式Load
?Historical可以配置負載能力
?Scatter/Gather 模型。查詢時分發(fā)給多線程執(zhí)行，每個Segment分配一個線程，然后再聚合。
?Shared-Nothing架構，擴展性強
Broker：
?通過ZooKeeper獲取TimeLine.
?Scatter/Gather模型，把時間段的查詢轉化成Segment的查詢分發(fā)給Historical或者RealTime，然后再在Broker層聚合
?采用Http Restful API提供查詢
?自實現NettyHttpClient，異步Nio的方式
?緩存查詢結果
同時還有一些外部依賴：
Zookeeper：
?LoadQueue，Coordinator分發(fā)Segment的實現是將Segment加到指定節(jié)點的LoadQueue
?Coordinator的failover實現，利用Zookeeper的選主
?時間軸，用于查詢路由分發(fā)到指定的節(jié)點
Deep Storage 用于Segment的備份存儲：
?HDFS、S3和Cassandra等
?使用其他任何對象存儲，自定義模塊實現
Meta信息存儲：
?Mysql
?其他關系型數據庫，自定義模塊實現
所以如何保障他們的高可用？
RealTime：RealTime Node 采用從Kafka中拉取數據的模式，不支持多副本，不能保障高可用，Indexing Service 實現了導入階段多副本，保障高可用
Historical：采用多副本加載
Coordinator：主備模式，采用Zookeeper選主
Broker：利用Zookeeper的節(jié)點發(fā)現以及客戶端負載均衡
接下來是Druid的幾個比較：
Druid vs Elasticsearch：
?Druid在導入過程會對原始數據進行Roll-up，而ES會保留原始數據。
?Druid專注于OLAP，針對數據導入以及快速聚合操作做了優(yōu)化。
?Druid不支持全文檢索。
Druid vs. Key/Value Stores (HBase/Cassandra/OpenTSDB)：
KV存儲的通用方式：
1、預算所有可能的維度組合
2、在事件記錄上進行Range Scan，所有的維度組合作為key，metrics作為value
缺點：
第一種，給空間和計算帶來挑戰(zhàn)，增加維度以后指數式增長。
第二種，所有的維度組合作為ke y ，Range Scan沒有索引的話會掃描大量的數據
Druid vs SQL-on-Hadoop (Impala/Drill/Spark SQL/Presto)：
SQL-on-Hadoop提供了執(zhí)行引擎可以在多種數據格式上進行查詢，它也可以查詢Druid的數據。
查詢模式
?Druid Scatter-Gather模型，算子下放，算子執(zhí)行和存儲在同一節(jié)點，broker只是聚合結果
?SQL-on-Hadoop一般采用MPP，執(zhí)行計劃的不同算子分布在不同節(jié)點執(zhí)行，增加數據序列化以及網絡傳輸的開銷
數據攝入：Druid 支持實時導入
SQL支持：Druid只支持單表，不支持大表之間的Full join
這個是使用Druid一個結構，也是lamda一個架構，也是兩個線，上面這個線通過hadoop生成索引，下面經過ETL實時生成索引。在使用Druid以后的實時部分如下：
?Druid只支持單表，采用把多表預先Joi n成單表
?每種日志維度冗余，采用Storm的Fiel d Grou ping把相同維度的不同日志連接在一起
?Storm中在一定時間窗口內預聚合，減小Druid的壓力
?寫入Kafka時采用Hash分區(qū)，使相同維度組合的數據落在同一分區(qū)
接下來是使用Druid以后的性能表現：
最后是使用Druid以后的數據導入吞吐量：
上圖是吞吐量，這個吞吐量在這里我說明一下，Druid數據是導入一個吞吐量，不是查詢吞吐量，我算了一下，大概最高的時候，峰值達到8萬的量。