MapReduce原理及shuffle機制

一、環形緩衝區

1.數據在環形緩衝區以KV的形式存在，索引和數據同向增長，當增長到緩衝區大小（默認128M）的80%時（只是80%左右，不是必須80%）開始溢寫

2.索引佔用四個int長度，以一個四元組的形式存在：value的起始位置，key的起始位置，partition值，value的長度。每進一條數據，指針每次向下跳動4個格子，然後補齊上面的值

3.發生在環形緩衝區的排序是對索引的排序，再具體是對partition值和key進行排序，將相同的partition放到一起，同一個partition內按照key進行排序（快排）

4.當第一次溢寫後，索引和數據文件相遇，然後以中間空出來的空間的中間位置作爲新的分界線，反向增長。

 二、maptask機制後半段（溢寫之後）

1.對多次溢寫的文件進行merge，合併分區，分區內數據進行排序。

2.在merge後只會有一個file.out文件和一個fiile.index文件，一個存放最終輸出，一個存放最終索引。

3.在這裏逐一將相同的partition的數據放到一個裏面，一個一個partition進行合併，每個partition裏面的數據按照key進行排序，每次取出最小的放到臨時文件，最後輸出到最終文件

三、shuffle

這裏借用網圖做一個整體流程梳理（注意：shuffle過程只是圖的中間部分，準確描述爲map方法結束後，reduce方法開始前，這裏展示的圖只是爲了幫助更好的從全局理解整個過程）

1.每個map讀取的數據進入環形緩衝區（kvbuffer，默認100M）後，索引和數據同向增加

2.當到達環形緩衝區內存的80%左右時，開始溢寫（溢寫前會對數據進行分區排序）

3.數據溢寫的同時，索引和數據會以上次相遇的剩餘空間的中間位置作爲分界線，反向存放數據

4.每個map會溢寫多次，在磁盤上生成多個文件。 Combiner（可選過程，會在map階段先聚合一次，所以如果要取平均數這樣的數據，這個過程不可以有的，因爲平均數這個值不可以累加）存在的時候，這些文件會在各個map中獨立進行merge（這裏第二次會對數據文件進行分區排序）

5.最終每個map對應生成一個文件提供給reduce

6.reduce將數據copy到內存裏面，如果內存不夠，會直接溢寫到磁盤裏，這裏需要注意：①當若干個map任務，只要有一個全部執行成，reduce就會去找對應的partition的數據進行copy，不是非要等到map全部執行完畢。②每個reduce的線程並行度是5，就是默認會有5個線程同時去map端拉去所對應的數據。③如果從某個map拉去數據失敗，斷開連接等情況，reduce會去其他的map下載數據，這個可以延長下載時間來避免數據不完整，公司一般都會增大這個時間mapreduce.reduce.shuffle.read.timeout，默認180000秒。

7.在reduce中進行merge，這次的區別是將來自多個map端輸出的數據進行分區，排序，shuffle結束。然後進入自定義的reduce方法中進行邏輯處理