問題:
生成一個數據立方體,該立方體的每一個結點都是一個整體度量的聚合函數(如 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、結果寫入數據庫如何查詢?