MapReduce 具有部分代数性质的整体度量的立方体生

生成一个数据立方体,该立方体的每一个结点都是一个整体度量的聚合函数(如 COUNT( DISTINCT ) ),如何使用 MapReduce 生成该数据立方体?

解法:

(1)生成该立方体的所有结点 Ri ,表示为数据立方体集合 C = {R1, R2, R3, ...}。

(2)度量(聚集函数)分为代数度量和整体度量,代数度量是可任意分布化的度量,整体度量是无法分布化的度量。本文认为,很多整体度量具有部分代数度量的性质。

即对于 a 列, M(D) = M'[A(D)],D是一个数据集合,M是整体度量,M'是一个代数度量,A是另一个整体度量。满足这样性质的就称为对 a 具有部分代数性质。

如 COUNT_DISTINCT(a)。其中 M=COUNT_DISTINCT(a),M'=COUNT(),A=GROUP_BY(a)

因此,对于整体度量来说,就是按值进行分区,即按“分区因子”进行分发。

(3)在处理每个立方体结点时(SELECT agg() FROM data GROUP BY a WHERE ...),按值分区采取一道取样估算的MapReduce作业,估算按 a 分发到 reduce 端的数据量,r 为一个 reduce 所处理的数据占总数据的百分比,取样的数量 N > 100 / r,通常取 2000 / r。如果当前结点的数据量大于 0.75rN(一个 reducer 所能容纳数据的 75%),我们就把这个结点Ri标记为 “reduce不友好”。同时“reduce不友好”的结点会有一个分区因子,值为 s / rN。

至此,立方体结点的集合 C 被改写为带标注的立方体结点的集合 Ca = {R1a, R2a, R3a, ...},Ria 是带有分区因子的结点。

(4)已经获得了具有标注的立方体,我们把 Ca 中的结点划分为若干个“批处理区域” Bia, 每一个批处理区域包含若干个结点 Ca = {B1a, B2a, B3a, ...}。

“批处理区域”的约束条件为:

1、一个父结点“reduce友好”的结点,必须属于一个包含它的至少一个父结点的“批处理区域”;

2、没有两个父结点“reduce不友好”的结点能够属于同一个“批处理区域”;

3、任意两个“批处理区域”的差不能多于2。

有两种“批处理区域”划分算法

1、贪心算法:即将晶格最底下的(粒度最大的)结点作为初始“批处理区域”,找出符合约束条件的结点数最少的情况,作为一个“批处理区域”。

2、枚举算法:通过定义 cost(产生终间数据量)彻底枚举 cost 最小的情况作为一个“批处理区域”,注意这种情况只适用于结点较少的情况。

(5)执行真正的 MapReduce 立方体生成算法。

Map:输入为每个元组,输出的 Key 为 每个“批处理区域”的最底层结点和“分区因子”,Value为元组本身。每条元组输出 | {B1a, B2a, B3a, ...}| 次。

Shuffle:“批处理区域”相同且“分区因子”相同的元组被分发到同一个 reduce,每个 reduce 获得可构成一个小立方体的元组集,若干个 reduce 构成一个“批处理区域”。

Reduce:在 reduce 端对这个小立方体进行自底向上的立方体生成(BUC),这里所采用的度量是 A 。所以,每一个 reduce 会在 HDFS 物化一个小立方体。

Post:将 reduce 输出的数据,按相同的批处理区域进行聚合,这里所采用的度量是 M',合并成一系列的中号立方体。

(6)将中号立方体进行聚合,生成整体大立方体,写入到数据库,用作报表分析。

该解法有如下问题:

1、C = {R1, R2, R3, ...} 如何生成?

2、Ca = {B1a, B2a, B3a, ...} 在数据量较大的情况下如何生成?

3、Map 端产生的数据依然是元始数据的数倍。|{B1a, B2a, B3a, ...}| 倍。

4、Post 处理的数据量大时如何处理?

5、结果写入数据库如何查询?

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/c389d10f9c8ef983a67ae2ddfae6b998.html