Hadoop是一個開源的分布式并行計算平臺，它主要由MapReduce的算法執(zhí)行和一個分布式的文件系統(tǒng)兩部分組成。
Hadoop起源于Doug Cutting大牛領(lǐng)導開發(fā)的Nutch搜索引擎項目的子項目。現(xiàn)在是Apache軟件基金會管理的開源項目。
本文主要介紹Hadoop及相關(guān)技術(shù)，從Hadoop的起源開始講述，主要涵蓋了MapReduce算法思想，基本框架，運行流程和編程粒度等內(nèi)容，以期給入門者提供一個關(guān)于Hadoop的技術(shù)簡介和研究參考。關(guān)于Hadoop的安裝指南和編程范例并不在本文敘述范圍內(nèi)，有需要者請參考其它資料。
因筆者水平實在太有限了，文中如有疏漏錯誤請不吝指出，萬分感謝。本人資料多數(shù)來源于互聯(lián)網(wǎng)的技術(shù)文檔，附錄列出引文列表，特此致謝原文作者。最后，發(fā)自內(nèi)心、無與倫比地感謝Google、Apache軟件基金會和Doug Cutting帶給我們?nèi)绱撕喖s、優(yōu)雅的技術(shù)。OK，讓我們開始吧!去尋找那神奇的小飛象。
目錄
引言——Hadoop從何而來
算法思想——Hadoop是怎么思考的
基本架構(gòu)——Hadoop是如何構(gòu)成的
運行流程——Hadoop是如何工作的
任務(wù)粒度——Hadoop是如何并行的
參考文獻
1. 引言——Hadoop 從何而來
自從Google工程師Jeffrey Dean提出MapReduce編程思想，MapReduce便在Google的各種Web應(yīng)用中釋放著魔力。然而，也許出于技術(shù)保密的目的，Google公司并沒有透露其MapReduce的實現(xiàn)細節(jié)。
幸運的是，Doug Cutting開發(fā)的Hadoop作為MapReduce開源實現(xiàn)，讓MapReduce這么平易近人地走到了我們面前。2006年1月，Doug Cutting因其在開源項目Nutch和Lucene的卓越表現(xiàn)受邀加入Yahoo公司，專職在Hadoop項目上進行開發(fā)。現(xiàn)在，Doug Cutting大牛已經(jīng)加盟Cloudera(一家從事Hadoop產(chǎn)品商業(yè)化及技術(shù)支持的公司)。注：Hadoop 名稱的來歷——Hadoop 原本是小Doug Cutting 的大象玩具。
作為Google MapReduce技術(shù)的開源實現(xiàn)，Hadoop理所當然地借鑒了Google的Google File System文件系統(tǒng)、MapReduce并行算法以及BigTable。因此，Hadoop也是一個能夠分布式處理大規(guī)模海量數(shù)據(jù)的軟件框架，這一點不足為奇。當然，這一切都是在可靠、高效、可擴展的基礎(chǔ)上。Hadoop的可靠性——因為Hadoop假設(shè)計算元素和存儲會出現(xiàn)故障，因為它維護多個工作數(shù)據(jù)副本，在出現(xiàn)故障時可以對失敗的節(jié)點重新分布處理。
Hadoop的高效性——在MapReduce的思想下，Hadoop是并行工作的，以加快任務(wù)處理速度。Hadoop的可擴展——依賴于部署Hadoop軟件框架計算集群的規(guī)模，Hadoop的運算是可擴展的，具有處理PB級數(shù)據(jù)的能力。
雖然Hadoop自身由Java語言開發(fā)，但它除了使用Java語言進行編程外，同樣支持多種編程語言，如C++。
Hadoop的長期目標是提供世界級的分布式計算工具，也是對下一代業(yè)務(wù)(如搜索結(jié)果分析等)提供支持的Web擴展(web-scale)服務(wù)。
2. 算法思想——Hadoop 是怎么思考的
MapReduce 主要反映了映射和規(guī)約兩個概念，分別完成映射操作和規(guī)約操作。映射操作按照需求操作獨立元素組里面的每個元素，這個操作是獨立的，然后新建一個元素組保存剛生成的中間結(jié)果。因為元素組之間是獨立的，所以映射操作基本上是高度并行的。規(guī)約操作對一個元素組的元素進行合適的歸并。雖然有可能規(guī)約操作不如映射操作并行度那么高，但是求得一個簡單答案，大規(guī)模的運行仍然可能相對獨立，所以規(guī)約操作也有高度并行的可能。
MapReduce 把數(shù)據(jù)集的大規(guī)模操作分配到網(wǎng)絡(luò)互聯(lián)的若干節(jié)點上進行，以實現(xiàn)其可靠性;每個節(jié)點都會向主節(jié)點發(fā)送心跳信息，周期性地把執(zhí)行進度和狀態(tài)報告回來。假如某個節(jié)點的心跳信息停止發(fā)送，或者超過預(yù)定時隙，主節(jié)點標記該節(jié)點為死亡狀態(tài)，并把先前分配到它的數(shù)據(jù)發(fā)送到其它節(jié)點。其中，每個操作使用命名文件的原子操作，避免并行線程之間沖突;當文件被改名時，系統(tǒng)可能會把它復制到任務(wù)名以外的其它名字節(jié)點上。
由于規(guī)約操作的并行能力較弱，主節(jié)點盡可能把規(guī)約操作調(diào)度在同一個節(jié)點上，或者距離操作數(shù)據(jù)最近(或次近，最近節(jié)點出現(xiàn)故障時)的節(jié)點上。MapReduce 技術(shù)的優(yōu)勢在于對映射和規(guī)約操作的合理抽象，使得程序員在編寫大規(guī)模分布式并行應(yīng)用程序時，幾乎不用考慮計算節(jié)點群的可靠性和擴展性等問題。
應(yīng)用程序開發(fā)人員把精力集中在應(yīng)用程序本身，關(guān)于集群的處理問題等交由MapReduce 完成。
3. 基本架構(gòu)——Hadoop 是如何構(gòu)成的
Hadoop 主要由HDFS(Hadoop Distributed File System)和MapReduce 引擎兩部分組成。最底部是HDFS，它存儲Hadoop 集群中所有存儲節(jié)點上的文件。HDFS 的上一層是MapReduce 引擎，該引擎由JobTrackers 和TaskTrackers組成。
3.1 HDFS
HDFS 可以執(zhí)行的操作有創(chuàng)建、刪除、移動或重命名文件等，架構(gòu)類似于傳統(tǒng)的分級文件系統(tǒng)。需要注意的是，HDFS 的架構(gòu)基于一組特定的節(jié)點而構(gòu)建(參見圖2)，這是它自身的特點。HDFS 包括唯一的NameNode，它在HDFS 內(nèi)部提供元數(shù)據(jù)服務(wù);DataNode 為HDFS 提供存儲塊。由于NameNode 是唯一的，這也是HDFS 的一個弱點(單點失敗)。一旦NameNode 故障，后果可想而知。正所謂皮之不存，毛將焉附?
制塊上。通常的策略是，對于最常見的3 個復制塊，第一個復制塊存儲在同一機架的不同節(jié)點上，最后一個復制塊存儲在不同機架的某個節(jié)點上。
請注意，只有表示DataNode 和塊的文件映射的元數(shù)據(jù)經(jīng)過NameNode。當外部客戶機發(fā)送請求要求創(chuàng)建文件時，NameNode 會以塊標識和該塊的第一個副本的DataNode IP 地址作為響應(yīng)。此外，NameNode 還會通知其他將要接收該塊副本的DataNode。
NameNode 在FsImage 文件中存儲所有關(guān)于文件系統(tǒng)名稱空間的信息，該文件和一個包含所有事務(wù)的記錄文件將存儲在NameNode 的本地文件系統(tǒng)上。FsImage 和EditLog 文件也有副本，以防止文件損壞或NameNode 系統(tǒng)故障。
DataNode
Hadoop 集群包含一個NameNode 和N(N>=1)個DataNode。DataNode通常以機架的形式組織，機架通過一個交換機將所有系統(tǒng)連接起來。通常，機架內(nèi)部節(jié)點之間的傳輸速度快于機架間節(jié)點的傳輸速度。
DataNode 響應(yīng)來自HDFS 客戶機的讀寫請求，也響應(yīng)NameNode 發(fā)送的創(chuàng)建、刪除和復制塊的命令;NameNode 獲取每個DataNode 的心跳消息，每條消息包含一個塊報告，NameNode 據(jù)此驗證塊映射和其他文件系統(tǒng)的元數(shù)據(jù)。如果 DataNode 無法發(fā)送心跳消息，NameNode 將采取修復措施，重新復制在該節(jié)點上丟失的塊。
3.2 Hadoop Map/Reduce
Hadoop Map/Reduce 引擎由JobTracker(作業(yè)服務(wù)器)和Task Tracker(任務(wù)服務(wù)器)組成。
Job Tracker
Job Tracker(Google 稱為Master)是負責管理調(diào)度所有作業(yè)，它是整個系統(tǒng)分配任務(wù)的核心。它也是唯一的，這與HDFS 類似。因此，簡化了同步流程問題。
Task Tracker
Task Tracker 具體負責執(zhí)行用戶定義操作，每個作業(yè)被分割為任務(wù)集，包括Map任務(wù)和Reduce 任務(wù)。任務(wù)是具體執(zhí)行的基本單元， Task Tracker 執(zhí)行過程中需要向Job Tracker 發(fā)送心跳信息，匯報每個任務(wù)的執(zhí)行狀態(tài)，幫助Job Tracker 收集作業(yè)執(zhí)行的整體情況，為下次任務(wù)分配提供依據(jù)。
在Hadoop 中，客戶端(任務(wù)的提交者)是一組API，用戶需要自定義自己需要的內(nèi)容，由客戶端將作業(yè)及其配置提交到Job Tracker，并監(jiān)控執(zhí)行狀況。
與HDFS 的通信機制相同，Hadoop Map/Reduce 也使用協(xié)議接口來實現(xiàn)服務(wù)器間的通信。實現(xiàn)者作為RPC 服務(wù)器，調(diào)用者經(jīng)由RPC 的代理進行調(diào)用。客戶端與Task Tracker 以及Task Tracker 之間，都不再有直接通信。難道客戶端就不需要了解具體任務(wù)的執(zhí)行狀況嗎?不是。難道Task Tracker 相互無需了解任務(wù)執(zhí)行情況嗎?也不是。由于整個集群各機器的通信比HDFS 復雜的多，點對點直接通信難以維持狀態(tài)信息，所以統(tǒng)一由Job Tracker 收集整理轉(zhuǎn)發(fā)。
這里提供一個示例，幫助您理解它。假設(shè)輸入域是：我愛中國云計算網(wǎng)，我愛云計算技術(shù)論壇。在這個域上運行Map 函數(shù)將得出以下的鍵/值對列表：
如果對這個鍵/值對列表應(yīng)用Reduce 函數(shù)，將得到以下一組鍵/值對：結(jié)果是對輸入域中的單詞進行計數(shù)，這無疑對處理索引十分有用。但是，現(xiàn)在假設(shè)有兩個輸入域，第一個是“我愛中國云計算網(wǎng)”，第二個是“我愛云計算技術(shù)論壇”。您可以在每個域上執(zhí)行Map 函數(shù)和Reduce 函數(shù)，然后將這兩個鍵/值對列表應(yīng)用到另一個Reduce 函數(shù)，這時得到與前面一樣的結(jié)果。換句話說，可以在輸入域并行使用相同的操作，得到的結(jié)果是一樣的，但速度更快。這便是MapReduce 的威力;它的并行功能可在任意數(shù)量的系統(tǒng)上使用。圖5 演示了MapReduce 的思想。
一個代表客戶機在單個主系統(tǒng)上啟動的MapReduce 應(yīng)用程序稱為JobTracker。類似于NameNode，它是Hadoop 集群中惟一負責控制MapReduce 應(yīng)用程序的系統(tǒng)。在應(yīng)用程序提交之后，將提供包含在HDFS 中的輸入和輸出目錄。
JobTracker 使用文件塊信息(物理量和位置)確定如何創(chuàng)建其他TaskTracker 從屬任務(wù)。MapReduce 應(yīng)用程序被復制到每個出現(xiàn)輸入文件塊的節(jié)點。將為特定節(jié)點上的每個文件塊創(chuàng)建一個惟一的從屬任務(wù)。每個TaskTracker 將狀態(tài)和完成信息報告給JobTracker。
5. 任務(wù)粒度——Hadoop 是如何并行的
Map 調(diào)用把輸入數(shù)據(jù)自動分割成M 片，并且分發(fā)到多個節(jié)點上，使得輸入數(shù)據(jù)能夠在多個節(jié)點上并行處理。Reduce 調(diào)用利用分割函數(shù)分割中間key，從而形成R片(例如，hash(key) mod R)，它們也會被分發(fā)到多個節(jié)點上。分割數(shù)量R 和分割函數(shù)由用戶來決定。
由上的分析可知，我們細分map 階段成M 片，reduce 階段成R 片。在理想狀態(tài)下，M 和R 應(yīng)當比worker 機器數(shù)量要多得多。每個worker 執(zhí)行許多不同的工作來提高動態(tài)負載均衡，并且能夠加快故障恢復的速度，這個失效機器上執(zhí)行的大量map 任務(wù)都可以分布到所有其他worker 機器上執(zhí)行。
但是在具體編程中，實際上對于M 和R 的取值有一定的限制，因為master 必須執(zhí)行O(M+R)次調(diào)度，并且在內(nèi)存中保存O(M*R)個狀態(tài)。(對影響內(nèi)存使用的因素還是比較小的：O(M*R)塊狀態(tài)，大概每對map 任務(wù)/reduce 任務(wù)1 個字節(jié)就可以了)。
進一步來說，用戶通常會指定R 的值，因為每一個reduce 任務(wù)最終都是一個獨立的輸出文件。在實際中，我們傾向于調(diào)整M 的值，使得每一個獨立任務(wù)都是處理大約16M 到64M 的輸入數(shù)據(jù)(這樣，上面描寫的本地優(yōu)化策略會最有效)，另外，我們使R 比較小，這樣使得R 占用不多的worker 機器。我們通常會用這樣的比例來執(zhí)行MapReduce: M=200，000，R=5，000，使用2，000 臺worker 機器。
本節(jié)內(nèi)容參考MapReduce: Simplified Data Processing on Large Clusters 原文
