前言
相對(duì)來說枫弟，MapReduce是一個(gè)款比較 “古老” 的大數(shù)據(jù)離線計(jì)算框架酗钞，但該框架對(duì)批量數(shù)據(jù)離線計(jì)算的思想仍值得借鑒疹瘦！
在處理過程中需要把mapper階段的數(shù)據(jù)傳遞給reducer階段，這個(gè)過程可以廣義地稱為Shuffle镐作，是 MapReduce 框架中最關(guān)鍵的一個(gè)流程锈津。
采用圖解的方式進(jìn)行表達(dá)可以降低理解難度
Shuffle
使用自頂向下的方式進(jìn)行理解Shuffle流程呀酸。
過程總覽
Shuffle流程橫跨了mapper階段和reducer階段，在mapper階段包括Spill過程琼梆，在reducer階段包括Copy過程和Sort過程性誉，如圖所示：
mapper階段的Spill
這個(gè)過程包括輸出(collect)、排序(sort)茎杂、溢寫(spill)艾栋、合并（merge)
collect
Map任務(wù)不斷地以<k,v>對(duì)的形式把數(shù)據(jù)輸出到一個(gè)存在于內(nèi)存中的環(huán)形數(shù)據(jù)結(jié)構(gòu)中。使用環(huán)形數(shù)據(jù)結(jié)構(gòu)是為了更有效地使用內(nèi)存空間蛉顽。這個(gè)數(shù)據(jù)結(jié)構(gòu)其實(shí)就是個(gè)字節(jié)數(shù)組蝗砾，叫kvbuffer。這里不僅用來存放數(shù)據(jù)携冤，還有了一些索引數(shù)據(jù)悼粮，放置索引數(shù)據(jù)的區(qū)域叫kvmeta。數(shù)據(jù)區(qū)域和索引數(shù)據(jù)區(qū)域在kvbuffer中是相鄰不重疊的兩個(gè)區(qū)域曾棕，用一個(gè)分界點(diǎn)來劃分兩者扣猫，分界點(diǎn)是會(huì)動(dòng)態(tài)變化的，每次溢寫（spill）之后都會(huì)變化一次翘地。初始的分界點(diǎn)是0申尤，數(shù)據(jù)的存儲(chǔ)方向是向上增長(zhǎng)，索引數(shù)據(jù)的存儲(chǔ)方向是向下增長(zhǎng)衙耕。
sort
把kvbuffer中的數(shù)據(jù)按照partition值和key兩個(gè)關(guān)鍵字升序排序昧穿，移動(dòng)的只是索引數(shù)據(jù)，排序結(jié)果是Kvmeta中數(shù)據(jù)按照partition為單位聚集在一起橙喘，同一partition內(nèi)的按照key有序时鸵。
spill
Spill線程為這次spill過程創(chuàng)建一個(gè)磁盤文件: 創(chuàng)建一個(gè)類似于“spill13.out”的文件。Spill線程根據(jù)排過序的kvmeta逐個(gè)把partition中的數(shù)據(jù)刷寫到這個(gè)文件中，一個(gè)partition對(duì)應(yīng)的數(shù)據(jù)刷寫完之后順序地刷寫下個(gè)partition饰潜，直到把所有的partition遍歷完初坠。一個(gè)partition在文件中對(duì)應(yīng)的數(shù)據(jù)也叫段(segment)。
但問題來了
所有的partition對(duì)應(yīng)的數(shù)據(jù)都放在這個(gè)文件里彭雾，雖然是順序存放的碟刺，但是怎么直接知道某個(gè)partition的數(shù)據(jù)在這個(gè)文件中存放的起始位置呢？
答案：利用索引
有一個(gè)三元組記錄某個(gè)partition對(duì)應(yīng)的數(shù)據(jù)在這個(gè)文件中的索引：起始位置薯酝、原始數(shù)據(jù)長(zhǎng)度半沽、壓縮之后的數(shù)據(jù)長(zhǎng)度。一個(gè)partition對(duì)應(yīng)一個(gè)三元組蜜托。然后把這些索引信息存放在內(nèi)存中，如果內(nèi)存中放不下了霉赡，后續(xù)的索引信息就需要寫到磁盤文件中了：創(chuàng)建一個(gè)類似于“spill13.index”的文件橄务，存儲(chǔ)了索引數(shù)據(jù)，(不一定在磁盤上創(chuàng)建穴亏，如果內(nèi)存（默認(rèn)1M空間）中能放得下就放在內(nèi)存中蜂挪，即使在磁盤上創(chuàng)建了，和spill13.out文件也不一定在同一個(gè)目錄下嗓化。)
每一次Spill過程就會(huì)最少生成一個(gè) *.out文件棠涮，有時(shí)還會(huì)生成 *.index文件。
索引文件和數(shù)據(jù)文件的對(duì)應(yīng)關(guān)系如下圖所示：
在Spill線程進(jìn)行SortAndSpill工作的同時(shí)刺覆，Map任務(wù)會(huì)繼續(xù)進(jìn)行數(shù)據(jù)的輸出严肪。Map還是把數(shù)據(jù)寫到kvbuffer中，在兩個(gè)指針即將重合時(shí)谦屑，在kvbuffer中剩余空間的中間位置驳糯，用這個(gè)位置設(shè)置為新的分界點(diǎn)，bufindex指針移動(dòng)到這個(gè)分界點(diǎn)氢橙，kvindex移動(dòng)到這個(gè)分界點(diǎn)的-16位置酝枢，然后兩者就可以和諧地按照自己既定的軌跡放置數(shù)據(jù)了，當(dāng)溢寫完成后悍手，空間騰出之后帘睦，不需要做任何改動(dòng)繼續(xù)前進(jìn)。分界點(diǎn)的轉(zhuǎn)換如下圖所示：
變換方向坦康，繼續(xù)~
merge
Map任務(wù)如果輸出數(shù)據(jù)量很大竣付，可能會(huì)進(jìn)行好幾次溢寫，out文件和Index文件會(huì)產(chǎn)生很多滞欠，分布在不同的磁盤上卑笨。最后是merge過程把這些文件合并。merge過程創(chuàng)建一個(gè)叫file.out的文件和一個(gè)叫file.out.Index的文件用來存儲(chǔ)最終的輸出和索引仑撞。
逐個(gè)partition進(jìn)行合并輸出赤兴。對(duì)于某個(gè)partition來說妖滔，從spillXX.index索引列表中查詢這個(gè)partition對(duì)應(yīng)的所有索引信息，每個(gè)對(duì)應(yīng)一個(gè)段插入到段列表中桶良。也就是這個(gè)partition對(duì)應(yīng)一個(gè)段列表座舍，記錄所有的Spill文件中對(duì)應(yīng)的這個(gè)partition那段數(shù)據(jù)的文件名、起始位置陨帆、長(zhǎng)度等等曲秉。
然后對(duì)這個(gè)partition對(duì)應(yīng)的所有的段進(jìn)行合并，目標(biāo)是合并成一個(gè)segment列表疲牵。當(dāng)這個(gè)partition對(duì)應(yīng)很多個(gè)segment時(shí)承二，會(huì)分批地進(jìn)行合并：先從segment列表中把第一批取出來，以key為關(guān)鍵字放置成最小堆纲爸，然后從最小堆中每次取出最小的輸出到一個(gè)臨時(shí)文件中亥鸠，這樣就把這一批段合并成一個(gè)臨時(shí)的段，把它加回segment列表中识啦；再?gòu)膕egment列表中把第二批取出來合并輸出到一個(gè)臨時(shí)segment负蚊，把其加入到列表中；這樣往復(fù)執(zhí)行颓哮，直到剩下的段是一批家妆，輸出到最終的文件中。
最終的索引數(shù)據(jù)仍然輸出到Index文件中冕茅。
Map端的Shuffle過程到此結(jié)束伤极。
reducer階段的Copy和Sort
copy
Reduce任務(wù)拖取某個(gè)Map對(duì)應(yīng)的數(shù)據(jù)，如果在內(nèi)存中能放得下這次數(shù)據(jù)的話就直接把數(shù)據(jù)寫到內(nèi)存中姨伤。Reduce要向每個(gè)Map去拖取數(shù)據(jù)塑荒，在內(nèi)存中每個(gè)Map對(duì)應(yīng)一塊數(shù)據(jù)，當(dāng)內(nèi)存中存儲(chǔ)的Map數(shù)據(jù)占用空間達(dá)到一定程度的時(shí)候姜挺，開始啟動(dòng)內(nèi)存中merge齿税，把內(nèi)存中的數(shù)據(jù)merge輸出到磁盤上一個(gè)文件中。
有些Map的數(shù)據(jù)較小是可以放在內(nèi)存中的炊豪，有些Map的數(shù)據(jù)較大需要放在磁盤上凌箕，這樣最后Reduce任務(wù)拖過來的數(shù)據(jù)有些放在內(nèi)存中了有些放在磁盤上，最后會(huì)對(duì)這些來一個(gè)全局合并词渤。
merge sort
這里使用的Merge和Map端使用的Merge過程一樣牵舱。Map的輸出數(shù)據(jù)已經(jīng)是有序的，Merge進(jìn)行一次合并排序缺虐，所謂Reduce端的sort過程就是這個(gè)合并的過程芜壁。一般Reduce是一邊copy一邊sort，即copy和sort兩個(gè)階段是重疊而不是完全分開的，迭代進(jìn)行的慧妄。
Reduce端的Shuffle過程至此結(jié)束顷牌。
