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

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