1、Ch. 1. Ch. 1. 并行計算技術簡介并行計算技術簡介n提高計算機性能有哪些基本技術手段提高字長，流水線微體系結構技術，提高集成度，提升主頻n迫切需要發展并行計算技術的主要原因單處理器性能提升達到極限爆炸性增長的大規模數據量超大的計算量/計算復雜度n有哪些主要的并行計算分類方法？按數據和指令處理結構：弗林(Flynn)分類按并行類型按存儲訪問構架按系統類型按計算特征按并行程序設計模型/方法Ch. 1. Ch. 1. 并行計算技術簡介并行計算技術簡介n并行計算有哪些方面的主要技術問題？多核/多處理器網絡互連結構技術存儲訪問體系結構分布式數據與文件管理并行計算任務分解與算法設計并行程序設計模

2、型和方法數據同步訪問和通信控制可靠性設計與容錯技術并行計算軟件框架平臺系統性能評價和程序并行度評估n如何評估程序的可并行度(Amdahl定律)Ch. 1. Ch. 1. 并行計算技術簡介并行計算技術簡介nMPI功能與特點nMPI程序結構nMPI基本編程接口nMPI編程實例處理數據的能力大幅落后于數據增長海量數據隱含著更準確的事實n什么是MapReduce？基于集群的高性能并行計算平臺(Cluster Infrastructure)并行程序開發與運行框架(Software Framework)并行程序設計模型與方法(Programming Model & Methodology)n為什么MapR

3、educe如此重要？高效的大規模數據處理方法改變了大規模尺度上組織計算的方式第一個不同于馮諾依曼結構的、基于集群而非單機的計算方式的重大突破目前為止最為成功的基于大規模計算資源的并行計算抽象方法Ch.2.Ch.2. MapReduceMapReduce簡介簡介n大數據分而治之的并行化計算n大數據任務劃分和并行計算模型 n主要設計思想：為大數據處理過程中的兩個主要處理操作提供一種抽象機制n典型的流式大數據問題的特征nMap和Reduce操作的抽象描述提供一種抽象機制，把做什么和怎么做分開，程序員僅需要描述做什么，不需要關心怎么做n基于Map和Reduce的并行計算模型和計算過程Ch.2.Ch.2

4、. MapReduceMapReduce簡介簡介n主要需求、目標和設計思想實現自動并行化計算為程序員隱藏系統層細節nMapReduce提供統一的構架并完成以下的主要功能任務調度數據/代碼互定位出錯處理分布式數據存儲與文件管理Combiner和Partitioner向“外”橫向擴展，而非向“上”縱向擴展失效被認為是常態把計算處理向數據遷移順序處理數據、避免隨機訪問數據為應用開發者隱藏系統層細節平滑無縫的可擴展性Ch.3. Google MapReduceCh.3. Google MapReduce基本構架基本構架nGoogle MapReduce并行處理的基本過程n失效處理n帶寬優化n計算優化n

5、用數據分區解決數據相關性問題nGoogle GFS的基本設計原則廉價本地磁盤分布存儲多數據自動備份解決可靠性為上層的MapReduce計算框架提供支撐nGoogle GFS的基本構架和工作原理GFS Master的主要作用GFS ChunkServer的主要作用數據訪問工作過程GFS的系統管理技術Ch.3. Google MapReduceCh.3. Google MapReduce基本構架基本構架nBigTable的基本作用和設計思想nBigTable設計動機和目標需要存儲多種數據海量的服務請求商用數據庫無法適用nBigTable數據模型多維表一個行關鍵字(row key)一個列關鍵字(co

6、lumn key)一個時間戳(time stamp)nBigTable基本構架子表服務器子表存儲結構SSTable（對應于GFS數據塊）子表數據格式子表尋址nHDFS的基本特征nHDFS基本構架 NameNode的作用 DataNode的作用nHDFS數據分布設計nHDFS可靠性與出錯恢復nHDFS的安裝和啟動nHDFS文件系統操作命令nHadoop MapReduce基本構架與工作過程 JobTracker的作用 TaskTracker的作用 MapReduce作業執行過程nHadoop MapReduce主要組件文件輸入格式InputFormat輸入數據分塊InputSplits數據記錄讀

7、入RecordReaderMapperCombinerPartitioner & ShuffleReducer文件輸出格式OutputFormatn容錯處理與計算性能優化nHBase的邏輯模型nHBase數據模型nHBase物理存儲格式nHBase子表服務器nHBase主服務器n單機方式n單機偽分布方式n集群分布模式n程序開發與提交作業基本過程n集群分布方式下遠程提交作業n基本算法n復雜算法或應用n用復合鍵讓系統完成排序n把小的鍵值對合并成大的鍵值對nHadoop內置的數據類型n用戶自定義數據類型需要實現Writable接口作為key或者需要比較大小時則需要實現WritableComparab

8、le接口nHadoop內置的文件輸入格式TextInputFormatKeyValueTextInputFormatnHadoop內置的RecordReaderLineRecordReaderKeyValueLineRecordReadern用戶自定義InputFormat和RecordReader的方法NewInputFormat extends FileInputFormatNewRecordReader extends RecordReaderjob.setInputFormatClass(NewInputFormat.class)nHadoop內置的文件輸出格式TextOutputFo

9、rmatKeyValueTextOutputFormatnHadoop內置的RecordWriterLineRecordWritern用戶自定義OutputFormat和RecordWriter的方法NewOutputFormat extends FileOutputFormatNewRecordWriter extends RecordWriterjob.setOutputFormatClass(NewOutputFormat.class)n定制Partitionero Class NewPartitionerNewPartitioner extends HashPartitioner /

10、override the method getPartition getPartition(K key, V value, int numReduceTasks) o Job. setPartitionerClassJob. setPartitionerClass(NewPartitioner)n定制Combinero public static class NewCombinerNewCombiner extends Reducer / 實現reduce方法 public void reduce(Text key, Iterable values, Context context) thro

11、ws IOException, InterruptedException oJob. setCombinerClass(NewCombiner)Job. setCombinerClass(NewCombiner) nMapReduce子任務的順序化執行n具有數據依賴關系的MapReduce子任務的執行nMapReduce前處理和后處理步驟的鏈式執行ChainMapper.addMapper（）ChainReducer.addMapper（）n用DataJoin類實現Reduce端Join連接主鍵GroupKey與記錄標簽TagDataJoinMapperBaseDataJoinReducerB

12、aseTaggedMapOutputMapper需要實現的抽象方法abstract Text generateInputTag(String inputFile)abstract TaggedMapOutput generateTaggedMapOutput(Object value)n用文件復制實現Map端Join 用distributed cache將一個或多個小數據量文件分布復制到所有節點上Job類中：public void addCacheFile(URI uri) 將一個文件放到distributed cache file中Mapper或Reducer的context類中： publ

13、ic Path getLocalCacheFiles() 獲取設置在distributed cache files中的文件路徑Replicated Joins方法的變化使用n帶Map端過濾的Reduce端Joinn多數據源連接解決方法的限制n全局作業參數的傳遞Configuartion類專門提供以下用于保存和獲取屬性的方法mapper/reducer類初始化方法setup()從configuration對象中讀出屬性n全局數據文件的傳遞(見上distributed cache的使用）n查詢任務相關信息n劃分多個輸出文件集合n輸入輸出到關系數據庫n從數據庫中輸入數據 DBInputFormat：

14、提供從數據庫讀取數據的格式DBRecordReader：提供讀取數據記錄的接口n向數據庫中輸出計算結果 DBOutputFormat：提供向數據庫輸出數據的格式DBRecordWriter：提供向數據庫寫入數據記錄的接口DBConfiguration提供數據庫配置和創建連接的接口創建數據庫連接：public static void configureDB(Job job, String driverClass, String dbUrl, String userName, String passwd)指定寫入的數據表和字段: public static void setOutput(Job job, String tableName, String. fieldNames)n鄰接矩陣n鄰接表nPageRank的基本設計思想和設計原則nPageRank的簡化模型及其缺陷nPageRank的隨機瀏覽模型n隨機瀏覽模型的PageRank公式n用MapReduce實現PageRankPhase1：GraphBuilderPhase2：PageRankIterPhase3：RankviewerPageRank迭代終止條件n單源最短路徑nDijkst