第5章分布式處理
　　5.1CPU多核和POSIX Thread
　　為了提高任務的計算處理能力，下面分別從硬件和軟件層面研究新的計算處理能力。
　　在硬件設備上，CPU技術不斷發(fā)展，出現(xiàn)了SMP(對稱多處理器)和NUMA(非一致性內(nèi)存訪問)兩種高速處理的CPU結構。處理器性能的提升給大量的任務處理提供了很大的發(fā)展空間。圖5.1是SMP和NUMA結構的CPU，CPU核數(shù)的增加帶來了計算能力的提高，但是也隨之帶來了大量的問題需要解決，比如CPU緩存一致性問題、NUMA內(nèi)存分配策略等，目前已經(jīng)有比較不錯的解決方案。
　　圖5.1SMP和NUMA架構CPU
　　在軟件層面出現(xiàn)了多進程和多線程編程。進程是內(nèi)存資源管理單元，線程是任務調(diào)度單元。圖5.2是進程和線程之間的區(qū)別。
　　圖5.2進程與線程
　　總的來說，線程所占用的資源更少，運行一個線程所需要的資源包括寄存器、棧、程序計數(shù)器等。早期不同廠商提供了不同的多線程編寫庫，這些線程庫差異巨大，為了統(tǒng)一多種不同的多線程庫，共同制定了POSIX Thread多線程編程標準，以充分利用多個不同的線程庫。組成POSIX Thread的API分成以下4個大類：
　�。�1） 線程管理。線程管理主要負責線程的create、detach、join等，也包括線程屬性的查詢和設置。
　�。�2） mutexes。處理同步的例程(routine)稱為mutex，mutex提供了create、destroy、lock和unlock等函數(shù)。
　�。�3） 條件變量。條件變量主要用于多個線程之間的通信和協(xié)調(diào)。
　�。�4） 同步。同步用于管理讀/寫鎖以及barriers。
　　5.2MPI并行計算框架
　　MPI(Message Passing Interface)是一個標準且可移植的消息傳遞系統(tǒng)，服務于大規(guī)模的并行計算。MPI標準定義了采用C、C++、Fortran語言編寫程序的函數(shù)語法和語義。目前有很多經(jīng)過良好測試和高效率的關于MPI的實現(xiàn)，廣泛采用的實現(xiàn)有MPICH。下面以MPICH為例展開對MPI的講解。
　　MPICH是一個高性能且可以廣泛移植的MPI實現(xiàn)。圖5.3為MPICH的架構圖。
　　圖5.3MPICH架構
　　如圖5.3所示，應用程序通過MPI結構連接到MPICH接口層，圖中的ROMIO是MPI.IO的具體實現(xiàn)版本，對應MPI標準中的高性能實現(xiàn)。MPICH包括ADI3、CH3 Device、CH3 Interface、Nemesis、Nemesis NetMod Interface。
　　（1) ADI3。ADI是抽象設備接口(abstract device interface)，MPICH通過ADI3接口層隔離底層的具體設備。
　�。�2) CH3 Device。CH3 Device是ADI3的一個具體實現(xiàn)，使用了相對少數(shù)目的函數(shù)功能。在CH3 Device實現(xiàn)了多個通信channel，channel提供了兩個MPI進程之間傳遞數(shù)據(jù)的途徑以及進程通信。當前包括兩個channel，即Nemesis和Sock，其中Sock是一個基于UNIX Socket的channel，而Nemesis支持多種方法，不僅僅局限于Socket通信。
　�。�3) CH3 Interface。CH3 Inferface用于定義訪問Nemesis的接口規(guī)范。
　　（4） Nemesis。Nemesis允許兩個MPI進程之間的網(wǎng)絡通信采取多種方法，包括TCP、InfiniBand等。
　　5.3Hadoop MapReduce
　　Hadoop是一個由Apache基金會開發(fā)的分布式系統(tǒng)基礎架構。Hadoop框架*核心的設計就是HDFS和MapReduce，HDFS為海量的數(shù)據(jù)提供了存儲，而MapReduce為海量的數(shù)據(jù)提供了計算。
　　HDFS(Hadoop Distributed File System)有高容錯性的特點，并且設計用來部署在低廉的硬件上； 而且它提供高吞吐量來訪問應用程序的數(shù)據(jù)，適合有著超大數(shù)據(jù)集的應用程序。HDFS放寬了POSIX的要求，可以用流的形式訪問文件系統(tǒng)中的數(shù)據(jù)。
　　MapReduce是Google公司提出的一個軟件框架，用于大規(guī)模數(shù)據(jù)集(大于1TB)的并行運算�！癕ap”和“Reduce”概念以及它們的主要思想都是從函數(shù)式編程語言借來的，還有從矢量編程語言借來的特性。
　　當前的軟件實現(xiàn)是指定一個Map函數(shù)，用來把一組鍵值對映射成一組新的鍵值對，指定并發(fā)的Reduce函數(shù)，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。
　　處理流程如下：
　　（1） MapReduce框架將應用的輸入數(shù)據(jù)切分成M個模塊，典型的數(shù)據(jù)塊大小為64MB。
　�。�2） 具有全局*的主控Master以及若干個Worker，Master負責為Worker分配具體的Map或Reduce任務并做全局管理。
　　（3） Map任務的Worker讀取對應的數(shù)據(jù)塊內(nèi)容，從數(shù)據(jù)塊中解析Key/Value記錄數(shù)據(jù)并將其傳給用戶自定義的Map函數(shù)，Map函數(shù)輸出的中間結果Key/Value數(shù)據(jù)在內(nèi)存中緩存。
　�。�4） 緩存的Map函數(shù)產(chǎn)生的中間結果周期性地寫入磁盤，每個Map函數(shù)中間結果在寫入磁盤前被分割函數(shù)切割成R份，R是Reduce的個數(shù)。一般用Key對R進行哈希取模。Map函數(shù)完成對應數(shù)據(jù)塊處理后將R個臨時文件位置通知Master，Master再轉交給Reduce任務的Worker。
　�。�5） Reduce任務Worker接到通知時將Map產(chǎn)生的M份數(shù)據(jù)文件pull到本地(當且僅當所有Map函數(shù)完成時Reduce函數(shù)才能執(zhí)行)。Reduce任務根據(jù)中間數(shù)據(jù)的Key對記錄進行排序，相同Key的記錄聚合在一起。
　�。�6） 所有Map、Reduce任務完成，Master喚醒用戶應用程序。
　　5.4Spark
　　Spark是UC Berkeley AMP Lab所開源的類Hadoop MapReduce的通用的并行計算框架，Spark基于Map.Reduce算法實現(xiàn)的分布式計算，擁有Hadoop MapReduce所具有的優(yōu)點； 不同于MapReduce的是中間輸出和結果可以保存在內(nèi)存中，從而不再需要讀/寫HDFS，因此Spark能更好地適用于數(shù)據(jù)挖掘與機器學習等需要迭代的Map.Reduce的算法。
　　Spark*主要的結構是RDD(Resilient Distributed Datasets),它表示已被分區(qū)、不可變的并能夠被并行操作的數(shù)據(jù)集合，不同的數(shù)據(jù)集格式對應不同的RDD實現(xiàn)。RDD必須是可序列化的。RDD可以緩存到內(nèi)存中，每次對RDD數(shù)據(jù)集操作之后的結果都可以存放到內(nèi)存中，下一個操作可以直接從內(nèi)存中輸入，省去了MapReduce大量的磁盤I/O操作。這很適合迭代運算比較常見的機器學習算法、交互式數(shù)據(jù)挖掘。
　　與Hadoop類似，Spark支持單節(jié)點集群或多節(jié)點集群。對于多節(jié)點操作，Spark可以采用自己的資源管理器，也可以采用Mesos集群管理器來管理資源。Mesos為分布式應用程序的資源共享和隔離提供了一個有效平臺(參見圖5.4)。該設置允許Spark與Hadoop共存于節(jié)點的一個共享池中。
　　圖5.4Mesos集群管理器
　　5.5數(shù)據(jù)處理技術的發(fā)展
　　數(shù)據(jù)處理從早期的共享分時單CPU操作系統(tǒng)處理到多核并發(fā)處理，每臺計算機設備的處理能力在不斷增強，處理的任務復雜度在不斷增加，任務的處理時間在不斷減少。
　　然而，隨著大數(shù)據(jù)技術的不斷發(fā)展，一臺計算設備無法勝任目前大數(shù)據(jù)計算的龐大的計算工作。為了解決單臺計算機無法處理大規(guī)模數(shù)據(jù)計算的問題，連接多臺計算機設備整合成一個統(tǒng)一的計算系統(tǒng)，對外提供計算服務。早期Google公司的分布式計算框架MapReduce采用的思想就是連接多臺廉價的計算設備，以此來提供進行大規(guī)模計算任務的能力。但是MapReduce是建立在磁盤之上的并行計算框架，由于機械磁盤本身的局限性，MapReduce仍然有很大的計算延遲。Spark提出了把計算結果存放在內(nèi)存中,利用內(nèi)存作為存儲介質(zhì)的方法極大地縮短了系統(tǒng)的響應時間,降低了計算任務返回結果的延遲。為了滿足大規(guī)模機器學習計算任務的需求,也設計了大量的分布式機器學習框架來訓練機器模型參數(shù),比如Parameter Server;針對圖計算場合,Google公司設計實現(xiàn)了Pregel圖計算框架，用于處理*短路徑、Dijstra等經(jīng)典圖計算任務； 為了滿足實時計算任務需求，設計實現(xiàn)了流計算框架，比如Spark Streaming、Storm、Flink等實時計算框架。
　　總之，目前處理技術在往大規(guī)模、低延遲方向發(fā)展，內(nèi)存空間的擴大以及內(nèi)存存儲成本的降低給大規(guī)模數(shù)據(jù)處理提供了極好的發(fā)展契機。
　　5.6習題
　　1. 簡述CPU技術的發(fā)展趨勢。
　　2. 簡述MPICH并行計算框架。
　　3. 簡述MapReduce的原理。
　　……