如何构建更好的数据立方体系统(Cube)

看到了kylin关于cube的设计&＃xff0c;难以抑制的觉得这部分设计得太巧妙了&＃xff0c;确实比我们的产品要好上很多&＃xff0c;不得不学习一下&＃xff01;&＃xff01;&＃xff01;

本文不是从实例的角度&＃xff0c;来分析如何构建一个数据立方体&＃xff0c;而是从BI的产品角度出发&＃xff0c;如何构建起一个更好的数据立方体系统。

概念部分

本部分以概念介绍为主&＃xff0c;了解的同学请跳过。

数据立方体是一种多维数据模型&＃xff0c;下面介绍一下多维模型的相关概念&＃xff1a;

• 多维数据模型&＃xff1a;为了满足用户从多角度多层次进行数据查询和分析的需要而建立起来的基于事实表和维度表的数据库模型&＃xff0c;其基本的应用是为了实现OLAP&＃xff08;Online Analytical Processing&＃xff09;

• 立方体&＃xff1a;它是由维度构建出来的多维空间&＃xff0c;包含了所要分析的基础数据&＃xff0c;所有的聚合数据操作都在它上面进行

• 维度&＃xff1a;观察数据的一种角度&＃xff0c;比如在上图中address、item、time都可以被看作一个维度&＃xff0c;直观上来看维度是一个立方体的轴&＃xff0c;比如三个维度可以构成一个立方体的空间

• 维度成员&＃xff1a;构成维度的基本单位&＃xff0c;比如对于time维&＃xff0c;包含Q1、Q2、Q3、Q4四个维度成员

• 层次&＃xff1a;维度的层次结构&＃xff0c;它存在两种&＃xff1a;自然层次和用户自定义层次。比如对于时间维&＃xff0c;可以分为年、月、日三个层次&＃xff0c;也可以分为年、季度、月三个层次。一个维可以有多个层次&＃xff0c;它是单位数据聚集的一种路径

• 级别&＃xff1a;级别组成层次&＃xff0c;比如年、月、日分别是时间维的三个级别

• 度量&＃xff1a;一个数值函数&＃xff0c;可以对数据立方体空间中的每个点求值&＃xff1b;度量值自然就是度量的结果

• 事实表&＃xff1a;存放度量值得表&＃xff0c;同时存放了维表得外键&＃xff0c;所有分析所用得数据最终都来自事实表

• 维表&＃xff1a;对于维度的描述&＃xff0c;每个维度对应一个或多个维表&＃xff0c;一个维度对应一个表的是星型模式&＃xff0c;对应多个表的是雪花模式

数据立方体只是多维模型的一种形象的说法&＃xff0c;它只有三维&＃xff0c;但多维数据模型不仅限于三维&＃xff0c;它可以是n维的。之所以这么叫是为了让用户更容易想象&＃xff0c;方便解释和说明&＃xff0c;同时也为了和传统的关系数据库中的二维表进行区分。所以&＃xff0c;我们可以把任意的n维数据立方体看做是&＃xff08;n-1&＃xff09;维立方体的序列&＃xff0c;比如可以将4-D立方体看做是3-D立方体的序列

多维数据模型的模式主要有星形模式、雪花模式和事实星座模式。

星形模式

它是最常见的模式&＃xff0c;它包括一个大的中心表&＃xff08;事实表&＃xff09;&＃xff0c;包含了大批数据但是不冗余&＃xff1b;一组小的附属表&＃xff08;维表&＃xff09;&＃xff0c;每维一个。如下所示&＃xff0c;从item、time、branch、location四个维度去观察数据&＃xff0c;中心表是Sales Fact Table&＃xff0c;包含了四个维表的标识符&＃xff08;由系统产生&＃xff09;和三个度量。

每一维使用一个表表示&＃xff0c;表中的属性可能会形成一个层次或格。

雪花模式

它是星模式的变种&＃xff0c;将其中某些表规范化&＃xff0c;把数据进一步的分解到附加的表中&＃xff0c;形状类似雪花。

如下所示&＃xff0c;item这个维表被规范化&＃xff0c;生成了新的item表和supplier表&＃xff1b;同样location也被规范化为location和city两个新的表。

事实星座

允许多个事实表共享维表&＃xff0c;可以看作是星形模式的汇集。如下所示&＃xff0c;Sales和Shipping两个事实表共享了time、item、location三个维表。

总体来说&＃xff0c;在数据仓库中多用事实星座模式&＃xff0c;因为它能对多个相关的主题建模&＃xff1b;而在数据集市流行用星形或雪花模式&＃xff0c;因为它往往针对于某一个具体的主题。

OLAP的多维分析操作包括&＃xff1a;钻取&＃xff08;Drill-down&＃xff09;、上卷&＃xff08;Roll-up&＃xff09;、切片&＃xff08;Slice&＃xff09;、切块&＃xff08;Dice&＃xff09;以及旋转&＃xff08;Pivot&＃xff09;&＃xff0c;下面还是以上面的数据立方体为例来逐一解释下&＃xff1a;

钻取&＃xff08;Drill-down&＃xff09;&＃xff1a;在维的不同层次间的变化&＃xff0c;从上层降到下一层&＃xff0c;或者说是将汇总数据拆分到更细节的数据&＃xff0c;比如通过对2010年第二季度的总销售数据进行钻取来查看2010年第二季度4、5、6每个月的消费数据&＃xff0c;如上图&＃xff1b;当然也可以钻取浙江省来查看杭州市、宁波市、温州市……这些城市的销售数据。

上卷&＃xff08;Roll-up&＃xff09;&＃xff1a;钻取的逆操作&＃xff0c;即从细粒度数据向高层的聚合&＃xff0c;如将江苏省、上海市和浙江省的销售数据进行汇总来查看江浙沪地区的销售数据&＃xff0c;如上图。

切片&＃xff08;Slice&＃xff09;&＃xff1a;选择维中特定的值进行分析&＃xff0c;比如只选择电子产品的销售数据&＃xff0c;或者2010年第二季度的数据。

切块&＃xff08;Dice&＃xff09;&＃xff1a;选择维中特定区间的数据或者某批特定值进行分析&＃xff0c;比如选择2010年第一季度到2010年第二季度的销售数据&＃xff0c;或者是电子产品和日用品的销售数据。

旋转&＃xff08;Pivot&＃xff09;&＃xff1a;即维的位置的互换&＃xff0c;就像是二维表的行列转换&＃xff0c;如图中通过旋转实现产品维和地域维的互换。

Kylin的Cube算法

以下内容为全文引用&＃xff0c;有兴趣的同学可以去参考连接查看原文。

也可称为“逐层算法”&＃xff0c;通过启动N&＃43;1轮MapReduce计算。第一轮读取原始数据&＃xff08;RawData&＃xff09;&＃xff0c;去掉不相关的列&＃xff0c;只保留相关的。同时对维度列进行压缩编码&＃xff0c;第一轮的结果&＃xff0c;我们称为Base Cuboid&＃xff0c;此后的每一轮MapReuce&＃xff0c;输入是上一轮的输出&＃xff0c;以重用之前的计算结果&＃xff0c;去掉要聚合的维度&＃xff0c;计算出新的Cuboid&＃xff0c;以此向上&＃xff0c;直到最后算出所有的Cuboid。

如上图所示&＃xff0c;展示了一个4维的Cube构建过程

此算法的Mapper和Reducer都比较简单。Mapper以上一层Cuboid的结果&＃xff08;Key-Value对&＃xff09;作为输入。由于Key是由各维度值拼接在一起&＃xff0c;从其中找出要聚合的维度&＃xff0c;去掉它的值成新的Key&＃xff0c;并对Value进行操作&＃xff0c;然后把新Key和Value输出&＃xff0c;进而Hadoop MapReduce对所有新Key进行排序、洗牌&＃xff08;shuffle&＃xff09;、再送到Reducer处&＃xff1b;Reducer的输入会是一组有相同Key的Value集合&＃xff0c;对这些Value做聚合计算&＃xff0c;再结合Key输出就完成了一轮计算。

每一轮的计算都是一个MapReduce任务&＃xff0c;且串行执行&＃xff1b;一个N维的Cube&＃xff0c;至少需要N次MapReduce Job。

算法优点

• 此算法充分利用了MapReduce的能力&＃xff0c;处理了中间复杂的排序和洗牌工作&＃xff0c;故而算法代码清晰简单&＃xff0c;易于维护&＃xff1b;

• 受益于Hadoop的日趋成熟&＃xff0c;此算法对集群要求低&＃xff0c;运行稳定&＃xff1b;在内部维护Kylin的过程中&＃xff0c;很少遇到在这几步出错的情况&＃xff1b;即便是在Hadoop集群比较繁忙的时候&＃xff0c;任务也能完成。

算法缺点

• 当Cube有比较多维度的时候&＃xff0c;所需要的MapReduce任务也相应增加&＃xff1b;由于Hadoop的任务调度需要耗费额外资源&＃xff0c;特别是集群较庞大的时候&＃xff0c;反复递交任务造成的额外开销会相当可观&＃xff1b;

• 由于Mapper不做预聚合&＃xff0c;此算法会对Hadoop MapReduce输出较多数据; 虽然已经使用了Combiner来减少从Mapper端到Reducer端的数据传输&＃xff0c;所有数据依然需要通过Hadoop MapReduce来排序和组合才能被聚合&＃xff0c;无形之中增加了集群的压力;

• 对HDFS的读写操作较多&＃xff1a;由于每一层计算的输出会用做下一层计算的输入&＃xff0c;这些Key-Value需要写到HDFS上&＃xff1b;当所有计算都完成后&＃xff0c;Kylin还需要额外的一轮任务将这些文件转成HBase的HFile格式&＃xff0c;以导入到HBase中去&＃xff1b;

• 总体而言&＃xff0c;该算法的效率较低&＃xff0c;尤其是当Cube维度数较大的时候&＃xff1b;时常有用户问&＃xff0c;是否能改进Cube算法&＃xff0c;缩短时间。

也被称作“逐段”(By Segment) 或“逐块”(By Split) 算法

从1.5.x开始引入该算法&＃xff0c;利用Mapper端计算先完成大部分聚合&＃xff0c;再将聚合后的结果交给Reducer&＃xff0c;从而降低对网络瓶颈的压力。

主要思想

对Mapper所分配的数据块&＃xff0c;将它计算成一个完整的小Cube 段&＃xff08;包含所有Cuboid&＃xff09;&＃xff1b;

每个Mapper将计算完的Cube段输出给Reducer做合并&＃xff0c;生成大Cube&＃xff0c;也就是最终结果&＃xff1b;下图解释了此流程

与旧算法的不同之处

• Mapper会利用内存做预聚合&＃xff0c;算出所有组合&＃xff1b;Mapper输出的每个Key都是不同的&＃xff0c;这样会减少输出到Hadoop MapReduce的数据量&＃xff0c;Combiner也不再需要&＃xff1b;

• 一轮MapReduce便会完成所有层次的计算&＃xff0c;减少Hadoop任务的调配。

举一个例子

一个cube有4个维度&＃xff1a;A&＃xff0c;B&＃xff0c;C&＃xff0c;D;每个Mapper都有100万个源记录要处理;Mapper中的列基数是Car&＃xff08;A&＃xff09;&＃xff0c;Car&＃xff08;B&＃xff09;&＃xff0c;Car&＃xff08;C&＃xff09;和Car&＃xff08;D&＃xff09;; 

当将源记录聚集到base cuboid&＃xff08;1111&＃xff09;时&＃xff0c;使用旧的“逐层”算法&＃xff0c;Mapper将向Hadoop输出1百万条记录;使用快速立方算法&＃xff0c;在预聚合之后&＃xff0c;它只向Hadoop输出[distinct A&＃xff0c;B&＃xff0c;C&＃xff0c;D]记录的数量&＃xff0c;这肯定比源数据小;在正常情况下&＃xff0c;它可以是源记录大小的1/10到1/1000; 

当从父cuboid聚合到子cuboid时&＃xff0c;从base cuboid&＃xff08;1111&＃xff09;到3维cuboid 0111&＃xff0c;将会聚合维度A;我们假设维度A与其他维度是独立的&＃xff0c;聚合后&＃xff0c;cuboid 0111的维度约为base cuboid的1 / Card&＃xff08;A&＃xff09;;所以在这一步输出将减少到原来的1 / Card&＃xff08;A&＃xff09;。

总的来说&＃xff0c;假设维度的平均基数是Card&＃xff08;N&＃xff09;&＃xff0c;从Mapper到Reducer的写入记录可以减少到原始维度的1 / Card&＃xff08;N&＃xff09;; Hadoop的输出越少&＃xff0c;I/O和计算越少&＃xff0c;性能就越好。

子立方体生成树(Cuboid Spanning Tree)的遍历次序

在旧算法中&＃xff0c;Kylin按照层级&＃xff0c;也就是广度优先遍历(Broad First Search)的次序计算出各个Cuboid&＃xff1b;在快速Cube算法中&＃xff0c;Mapper会按深度优先遍历&＃xff08;Depth First Search&＃xff09;来计算各个Cuboid。深度优先遍历是一个递归方法&＃xff0c;将父Cuboid压栈以计算子Cuboid&＃xff0c;直到没有子Cuboid需要计算时才出栈并输出给Hadoop&＃xff1b;最多需要暂存N个Cuboid&＃xff0c;N是Cube维度数。

• 采用DFS&＃xff0c;是为了兼顾CPU和内存&＃xff1a;

• 从父Cuboid计算子Cuboid&＃xff0c;避免重复计算&＃xff1b;

• 只压栈当前计算的Cuboid的父Cuboid&＃xff0c;减少内存占用。

上图是一个四维Cube的完整生成树&＃xff1b;

按照DFS的次序&＃xff0c;在0维Cuboid 输出前的计算次序是 ABCD -> BCD -> CD -> D -> &＃xff0c; ABCD, BCD, CD和D需要被暂存&＃xff1b;在被输出后&＃xff0c;D可被输出&＃xff0c;内存得到释放&＃xff1b;在C被计算并输出后&＃xff0c;CD就可以被输出&＃xff1b;ABCD最后被输出。

使用DFS访问顺序&＃xff0c;Mapper的输出已完全排序&＃xff08;除了一些特殊情况&＃xff09;&＃xff0c;因为Cuboid ID位于行键的开始位置&＃xff0c;而内部Cuboid中的行已排序&＃xff1a;

由于mapper的输出已经排序&＃xff0c;Hadoop的排序效率会更高&＃xff0c;

此外&＃xff0c;mapper的预聚合发生在内存中&＃xff0c;这样可以避免不必要的磁盘和网络I / O&＃xff0c;并且减少了Hadoop的开销;

在开发阶段&＃xff0c;我们在mapper中遇到了OutOfMemory错误;这可能发生在&＃xff1a;

• Mapper的JVM堆大小很小;

• 使用“dictinct count”度量&＃xff08;HyperLogLog占用空间&＃xff09;

• 生成树太深&＃xff08;维度太多&＃xff09;;

• 给Mapper的数据太大

我们意识到Kylin不能认为Mapper总是有足够的内存;Cubing算法需要自适应各种情况;

当主动检测到OutOfMemory错误时&＃xff0c;会优化内存使用并将数据spilling到磁盘上;结果是有希望的&＃xff0c;OOM错误现在很少发生;

优缺点

优点

它比旧的方法更快;从我们的比较测试中可以减少30&＃xff05;到50&＃xff05;的build总时间;

它在Hadoop上产生较少的工作负载&＃xff0c;并在HDFS上留下较少的中间文件;

Cubing和Spark等其他立方体引擎可以轻松地重复使用该立方体代码;

缺点

该算法有点复杂;这增加了维护工作;

虽然该算法可以自动将数据spill到磁盘&＃xff0c;但它仍希望Mapper有足够的内存来获得最佳性能;

用户需要更多知识来调整立方体;

我们知道&＃xff0c;RDD&＃xff08;弹性分布式数据集&＃xff09;是Spark中的一个基本概念。N维立方体的集合可以很好地描述为RDD&＃xff0c;N维立方体将具有N &＃43; 1个RDD。这些RDD具有parent/child关系&＃xff0c;因为parent RDD可用于生成child RDD。通过将父RDD缓存在内存中&＃xff0c;子RDD的生成可以比从磁盘读取更有效。下图描述了这个过程

改进

• 每一层的cuboid视作一个RDD

• 父亲RDD被尽可能cache到内存

• RDD被导出到sequence file

• 通过将“map”替换为“flatMap”&＃xff0c;以及把“reduce”替换为“reduceByKey”&＃xff0c;可以复用大部分代码

Spark中Cubing的过程

下图DAG&＃xff0c;它详细说明了这个过程&＃xff1a;

在“Stage 5”中&＃xff0c;Kylin使用HiveContext读取中间Hive表&＃xff0c;然后执行一个一对一映射的“map”操作将原始值编码为KV字节。完成后Kylin得到一个中间编码的RDD。

在“Stage 6”中&＃xff0c;中间RDD用一个“reduceByKey”操作聚合以获得RDD-1&＃xff0c;这是base cuboid。接下来&＃xff0c;在RDD-1上做一个“flatMap”&＃xff08;一对多map&＃xff09;&＃xff0c;因为base cuboid有N个子cuboid。以此类推&＃xff0c;各级RDD得到计算。在完成时&＃xff0c;这些RDD将完整地保存在分布式文件系统&＃xff0c;但可以缓存在内存中用于下一级的计算。当生成子cuboid时&＃xff0c;它将从缓存中删除。

性能测试

在所有这三种情况下&＃xff0c;Spark都比MR快&＃xff0c;总体而言&＃xff0c;它可以减少约一半的时间。

参考连接&＃xff1a;

https://blog.csdn.net/bbbeoy/article/details/79073725

https://blog.csdn.net/Forlogen/article/details/88634117

http://cxy7.com/articles/2018/06/09/1528549073259.html