kylin cubing algorithm(算法)

看到这一块的视频,结合光方博客的一些文档及自己的一点理解,记个笔记,以备不时之需。

  • by layer cubing

   1.on MR

     这个算法的对cube的计算就像它的名字一样是按player进行的。

以一个n维cube(即事实表有n个维度)为例:

player-1:以source data(源数据)为基础计算出一个n维的cuboid;

player-2:以上一层的n维cuboid维基础,计算出n个n-1维的cuboid;

... ...

player-k+1:以上一层的n-k+1维cuboid为基础,计算出n!/[(n-k)!k!]=kylin cubing algorithm(算法)个n-k维的cuboid;

... ...

player-n+1:以上一层的1维cuboid为基础,计算出1个0维的cuboid。

kylin cubing algorithm(算法)

用官网上一个4维cube的例子来说明一下具体过程。

在player-1,根据源数据得到1个4-D的cuboid;然后cong中任意取出三个维度得到4个3-D cuboids;接着从3-D cuboids出发,任意取出其中两个维度得到6个2-D cuboids;再以2-D cuboids为基础,任意取出其中一个维度得到4个1-D cuboids;最后根据1-D cuboids 计算出一个0-D cuboid。

cuboids的构建的思想和组合数的概念一致:从含有i个维度的i-D cuboids 中取出i-1个维度构成一个新的cuboid。有次每一层cuboids 的数量变很容易得到。以(n-2)-D cuboids 为例:(n-1)-D cuboids 有n个,故总共可以计算出n*kylin cubing algorithm(算法)个(n-2)-D cuboids;而分析(n-1)-D cuboids发现,每两个(n-1)-D cuboids 有且只有一个维度是不同的,即每两个(n-1)-D cuboids 构建出的2*kylin cubing algorithm(算法)个(n-2)-D cuboids中会出现两个维度相同的(n-2)-D cuboids,因此重复的n*kylin cubing algorithm(算法)个(n-2)-D cuboids中有kylin cubing algorithm(算法)个重复的(n-2)-D cuboids,n*kylin cubing algorithm(算法)-kylin cubing algorithm(算法)=kylin cubing algorithm(算法)即为(n-2)-D cuboids的个数。

优点:

  • 这个算法的原理很清晰,主要就是利用了MR,sorting、grouping、shuffing全部由MR完成,开发人员只需要关注cubing的逻辑
  • 由于hadoop的成熟,该算法的运行很稳定

缺点:

  • cube的维度越高,需要的MR任务越多(n-D cube 需要n+1 个MR)
  • 太多的shuffing操作(mapper端不做聚合,所有在下一层中具有相同维度的值有combiner 和reducer聚合)
  • 对hdfs读写比较多(每一层MR的结果会写到hdfs然后下一层MR从hdfs 读取数据)

   2.on Spark

    “by-layer” Cubing把一个大任务划分为许多步骤,每一步骤的计算依赖于上一个步骤的输出结果,所以当某一个步骤的计算出现问题时,可以再次读取上一步骤的结果重新计算,而不用从头开始。使得“by-layer” Cubing算法稳定可靠,当换到spark上时,便保留了这个算法。因此在spark上这个算法也被称为“By layer Spark Cubing”.

kylin cubing algorithm(算法)

如上图所示,与在MR上相比,每一层的计算结果不再输出到hdfs,而是放在RDD中。由于RDD存储在内存中,从而有效避免了MR上过多的读写操作。

  • fast cubing

与by layer cubing 的操作对象是数据的整体不同的是 fast cubing 算法则是将整体数据切分一个个segment,然后对每个片段进行计算得到一个个cube segment(拥有所有cuboids),最后把这些小的cube片段聚合成一个大的cube segment,cubing结束。

kylin cubing algorithm(算法)

所以 fast cubing 也被称为by segment cubing。如上图所示,该算法的核心思想可以认为是把by layer 中所有的计算全部放在mapper端计算整体数据的一个segment得到一个cube segment (所有计算的结果即cuboids ,存储在内存中),这个cube segment 是最终我们要得到的cube的一部分,所以最后对所有cube segment 进行聚合操作即可得到最中我们需要的cube。

优点:

  • 作为对by player on MR的改进,他的速度更快
  • 减轻了hadoop的工作压力,减少了输出到hdfs上的中间文件
  • 代码可以很容易的被其他计算引擎如spark 重用

缺点:

  • 算法较复杂,增加了维护工作量
  • 尽管数据可一溢写到磁盘,但是在mapper端扔需要有足够的内存资源才能有比较好的结果。
上一篇:jQuery与js的length属性


下一篇:[转] WinForm自定义函数FindControl实现按名称查找控件