數(shù)據(jù)傾斜情況下基于MapReduce的Join算法優(yōu)化.ppt

數(shù)據(jù)傾斜情況下 基于MapReduce的Join算法優(yōu)化,報告人：蔡珉星 廈大數(shù)據(jù)庫實驗室 2014-08-16,遇到的問題,目錄,優(yōu)化思路 - 改進Partition Partition在兩表連接中的改進 LEEN算法,Part 1,優(yōu)化思路 - 改進Partition,MapReduce中的Partition： 在Map端輸出時，需要對key進行分區(qū)，來決定輸出數(shù)據(jù)傳輸?shù)侥膫€reducer上進行處理。 默認的partition是通過哈希操作來決定分配到哪個reducer。 哈希Partition的局限 哈希在數(shù)據(jù)均衡的情況下，可以很好的將數(shù)據(jù)平均到各個Reducer上，但在數(shù)據(jù)傾斜情況下，會導致某幾個Key的值大量集聚在單個Reducer上。,Partition,哈希實際上是一種針對鍵的分組均衡分配，不能保證數(shù)據(jù)量均衡分配,Reduce-side Join： Map-side Join(復制連接、半連接)對數(shù)據(jù)集要求較高，一般情況下Join操作是采用Reduce-side Join - 重分區(qū)連接：將鍵相同的數(shù)據(jù)分到同一個reducer，再進行Join。 優(yōu)化重分區(qū)連接: 區(qū)分大小數(shù)據(jù)集，將小數(shù)據(jù)集讀取到內存中，再用小數(shù)據(jù)集來遍歷大數(shù)據(jù)集。 優(yōu)化重分區(qū)連接的精髓就在于Reduce端用小數(shù)據(jù)集遍歷大數(shù)據(jù)集，這部分已經(jīng)沒有什么改進空間。哪里還可以再改進？ Partition: 優(yōu)化重分區(qū)連接采用Hash parition不能保證數(shù)據(jù)量均衡分配。,Join算法優(yōu)化思路,優(yōu)化重分區(qū)連接采用Hash parition，不能保證數(shù)據(jù)量均衡分配,Part 2,Partition在兩表連接中的改進,兩表連接中的改進,數(shù)據(jù)實例： 3個Data節(jié)點 每個節(jié)點輸出75個鍵值,81 - 36% 103 - 46% 41 - 18%,即便可以采用優(yōu)化重分區(qū)，但在Partition時已經(jīng)造成了數(shù)據(jù)分配傾斜！,兩表連接中的改進,均衡Partition 論文LEEN LocalityFairness- Aware Key Partitioning for MapReduce in the Cloud中的算法LEEN給出的Partition：,74 - 33% 74 - 33% 77 - 34%,獲知鍵值的分布,兩表連接中的改進,獲知鍵值的分布 采樣 在執(zhí)行Reducer-side Join之前，先運行一個Job，統(tǒng)計數(shù)據(jù)分布情況。 采樣開銷應盡可能少，同時保證準確性。 Partition方式: 簡單范圍分區(qū) Map端采樣：每個Mapper隨機取x個Sample，有n個Mapper。 Reduce端統(tǒng)計分布：只需要一個Reducer，此時n*x個Sample已是排好序的。,兩表連接中的改進,Partition方式: 簡單范圍分區(qū)（續(xù)） 若執(zhí)行的Join有N個Reducer，可以根據(jù)步長 n*x/N 獲得一個分區(qū)序列。 例如: Samples: 1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 8, 9, 9, 10, 10, 5個Reducer，步進3 分區(qū)序列: 3, 5, 6, 9 Join Partition: key3 3 鍵為6的有兩個可選Reducer 解決: build relation: 隨機選擇一個可選Reducer probe relation: 需發(fā)送到每個可選Reducer R join S - R: probe, S: build?,兩表連接中的改進,傾斜鍵存在大小表的情況 Samples: 1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 10, 5個Reducer，步進3 分區(qū)序列: 3, 5, 6, 6 - 鍵為6的有兩個可選Reducer 3 和 4 R join S，對于鍵6，若 R.6 S.6 可將所有的R.6傳輸?shù)?和4上，然后S.6可以隨機分配到3或4上,1000個A,兩表連接中的改進,進一步的改進：虛擬范圍分區(qū) 實際是N個Reducer，但假定分成 *N 個分區(qū)(為整數(shù))。 例如 Samples: 1, 3, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 10, 11, 11, 11, 15, 16, 5個Reducer Join Partition: 1,3,4,4, 5,5,6,6, 6,6,6,6, 9,10,10,11,11,11, 15,16 = 2，則分成2*5=10個分區(qū) Samples: 1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 10, 11, 11, 11, 15, 16, 10個Reducer Join Partition: 1,3,3, 4, 5,5, 6,6, 6,6, 6,6, 9,10,10, 11, 11,11, 15,16 采用虛擬范圍分區(qū)，數(shù)據(jù)分配更加均衡 處理方式: 輪叫調度 或 當某一節(jié)點完成時，將下一剩余任務分配給該節(jié)點 論文的實驗結果表明虛擬范圍分區(qū)優(yōu)于簡單范圍分區(qū),還有什么地方可以再優(yōu)化？,Reduce階段須在數(shù)據(jù)傳輸、合并完成后才能開始 能否減少網(wǎng)絡傳輸？,Part 2,LEEN算法,LEEN算法,針對Copy Phase的一些考慮,map和reduce任務可在同一個節(jié)點上，copy階段，節(jié)點fetch的數(shù)據(jù)包括自身節(jié)點上的數(shù)據(jù)（不需要網(wǎng)絡傳輸）和其他節(jié)點上的數(shù)據(jù)（需要網(wǎng)絡傳輸）。 若為了降低網(wǎng)絡傳輸，應盡量fetch自身節(jié)點的數(shù)據(jù)。但以自身數(shù)據(jù)量作為Partition依據(jù)，可能導致reduce端數(shù)據(jù)分配不均，如何平衡？,LEEN算法,數(shù)據(jù)實例： 3個Data節(jié)點 每個節(jié)點輸出75個鍵值,22 - 29% 30 - 40% 17 - 22%,Partition后，本地數(shù)據(jù)所占的比例,81 - 36% 103 - 46% 41 - 18%,網(wǎng)絡共需要傳輸?shù)臄?shù)據(jù)量： Total Map output (1 -Locality) 81*(1-29%) + 103*(1-40%) + 41*(1-22%) = 151 151/225 = 67%,LEEN算法,LEEN：異步map和reduce模式 Hadoop中的計算和數(shù)據(jù)傳輸是會重疊的（如一個節(jié)點上運行多個map任務，一個map任務結束后，就會進行數(shù)據(jù)傳輸）。 LEEN為了獲知所有中間數(shù)值的分布情況，采用了異步map和reduce模式（先全部執(zhí)行完map再執(zhí)行reduce）。 map階段對每個中間鍵的結果進行緩存，而不是直接發(fā)送到相應的reducer。 這樣當map結束時，就有了所有的鍵分布信息（出現(xiàn)次數(shù)等），這些鍵將根據(jù)LEEN算法來進行分配（到reducer）。,LEEN算法,LEEN算法：平衡Locality和Fairness Fairness(0): 各個reduce分配的數(shù)據(jù)量的差異，越小越好； Locality(1): 各個reduce分配的數(shù)據(jù)中，來自本地節(jié)點的數(shù)據(jù)，越大越好； LEEN算法 - 啟發(fā)式算法，目標：(Fairness/Locality)的最小值。 其他思路： 因素: Fairness、Locality哪個對Job結果影響更大？(0.2/0.4與0.4/0.8哪個更優(yōu)?) 體現(xiàn): 集群的計算能力與網(wǎng)絡能力。 通用表達式: T = DATA*diff_time_per_data*Fairness + DATA*trans_time_per_data*(1-Locality) 目標: diff_time_per_dat