Hadoop Mapreduce 中的FileInputFormat類的文件切分演算法和host選擇演算法

文件切分演算法

文件切分演算法主要用於確定InputSplit的個數以及每個InputSplit對應的數據段。 FileInputFormat以文件為單位切分成InputSplit。對於每個文件，由以下三個屬性值確定其對應的InputSplit的個數。

• goalSize：根據用戶期望的InputSplit數據計算，即totalSize/numSplit。totalSize為文件總大小；numSplit為用戶設定的Map Task個數，預設情況下是1.
• minSize：InputSplit的最小值，由配置參數mapred.min.split.size確定，預設是1.
• blockSize:文件在HDFS中存儲的block大小，不同文件可能不同，預設是64MB.

這三個參數共同決定InputSplit的最終大小，計算方式：
splitSize = max{mainSize,min{goalSize,biockSize}}

一旦確定splitSize值後，FileInputFormat將文件依次切成大小為splitSize的InputSplit，最後剩下不足splitSize的數據塊單獨成為一個InputSplit。

host選擇演算法

InputSplit切分方案確定之後，需要確定每個InputSplit的元數據信息。元數據信息通常由四部分組成：<file,start,length,host>，分別表示InputSplit所在的文件、起始位置、長度以及所在的host（節點）列表。其中，前面三項容易確定，難點在於host列表的選擇方法。

Hadoop將數據本地性按照代價劃分為三個等級：node locality、rack locality和data center locality。在進行任務調度時，會依次考慮這三個節點的locality，即有限讓空閑資源處理本節點上的數據，如果節點上沒有任何可處理的數據，則處理同一個機架上的數據，最差的情況是處理其他機架上的數據，但是必須位於同一個數據中心。

FileInputFormat設計了一個簡單有效的啟髮式演算法：首先按照rack包含的數據量對rack進行排序，然後在rack內部按照每個node包含的數據量對node排序，最後取前N個node的host作為InputSplit的host列表，這裡的N為block的副本數。當任務調度器調度Task時，只要將Task調度給位於host列表中的節點，就認為該Task滿足本地性。

當使用基於FileInputFormat實現InputFormat時，為了提高Map Task的數據本地性，應儘量使InputSplit大小與bolck大小相同。