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