by 清華大學
為什么并行計算侦香？
- 計算量大
- 單進程算得不夠快勒虾，多CPU算
- 內(nèi)存需求大
- 單機內(nèi)存不夠大
- 內(nèi)存隨機訪問比硬盤隨機訪問快100,000倍
- I/O 量大
- 單個硬盤讀寫太慢爵赵，多個硬盤讀寫
并行計算的挑戰(zhàn)
- 編程困難
- 并行性識別與表達，難寫
- 同步語句土涝，難寫對
- 性能調(diào)優(yōu)難江醇，難寫快 （并行計算目標就是提升性能省艳，性能調(diào)優(yōu)難）
-負載平衡- 局部性 （高速緩存cache，使用cache可以快10倍左右）
- 容錯難
并行計算中的局部性
矩陣相乘嫁审，按列訪問會造成cache失效
分塊算法跋炕，得到更高的局部性
高可用性
大數(shù)據(jù)處理系統(tǒng)通常是由大量不可靠服務器組成的，如果處理1個10天的大數(shù)據(jù)處理任務時在第8天機器壞掉怎么辦律适？
重新計算不一定能解決問題
傳統(tǒng)的容錯方法不適用
- 鎖步法（性能會有較大影響）辐烂，多版本編程（多個人來編程遏插，對比結(jié)果，軟件容錯）
檢查點設置與恢復（保存程序狀態(tài)纠修，從保存狀態(tài)位置繼續(xù)執(zhí)行胳嘲，IO量大）
大數(shù)據(jù)處理并行系統(tǒng)
內(nèi)存計算需求
Map Reduce成功之處
- 用戶只需要編寫串行程序
- 自動并行化和分布式執(zhí)行
- 自動容錯
- 自動負載平衡
用戶對系統(tǒng)提出了更高的要求 - 更復雜的多階段任務
- 交互式查詢
Map Reduce 的局限性 - 表達能力有限
- 只有Map 和Reduce兩種操作
- 復雜任務通常需要迭代的 MapReduce
- 需要將中間結(jié)構(gòu)保存在硬盤上
- 大量I/O操作造成性能急劇下降
- 引入的I/O操作多，只能做離線分析扣草，很難支持數(shù)據(jù)的交互式查詢
MapReduce 文件傳遞數(shù)據(jù)
如果能用內(nèi)存保存數(shù)據(jù)了牛？
比采用硬盤方案快10-100倍
In Memory Computing
內(nèi)存計算的可行性
問題：
- 內(nèi)存是否足夠大能夠裝下所需要的數(shù)據(jù)？
- 內(nèi)存有多貴辰妙？與硬盤相比性價比如何鹰祸？
- 數(shù)據(jù)保存在硬盤上，可以保證數(shù)據(jù)的可用性密浑，放在內(nèi)存里如何容錯蛙婴？
- 如何高效表示內(nèi)存里的數(shù)據(jù)？
input -> iter1 -> memory -> iter2 -> memory
單位芯片上集成的晶體管數(shù)量隨著時間（每兩年）可以成倍增長
各個內(nèi)存層次的延遲
DRAM比硬盤快100,000倍尔破，但是DRAM比片上cache慢6-200倍
內(nèi)存計算的實例：SPARK
SPARK設計理念：著重效率和容錯
如何抽象多臺機器的內(nèi)存街图？
- 分布式共享內(nèi)存（DSM）
- 統(tǒng)一地址空間
- 很難容錯
- 分布式鍵-值存儲（Piccolo，RAMCloud）
- 允許細粒度訪問
- 可以修改數(shù)據(jù)（mutable）
- 容錯開銷大
DSM和鍵值對的容錯機制
- 副本或Log
- 對數(shù)據(jù)密集應用來說開銷很大
- 比內(nèi)存寫要慢10-100倍
解決方案
- RDD（Resilient Distributed Datasets）
- 基于數(shù)據(jù)集合懒构，而不是單個數(shù)據(jù)
- 由確定性的粗粒度操作產(chǎn)生（map,filter,join等）
- 數(shù)據(jù)一旦產(chǎn)生餐济，就不能修改（immutable）
- 如果要修改數(shù)據(jù)，要通過數(shù)據(jù)集的變換來產(chǎn)生新的數(shù)據(jù)集
高效容錯方法
- 數(shù)據(jù)一旦是確定性的產(chǎn)生胆剧，并且產(chǎn)生后不會變化
- 就可以通過“重復計算”的方法恢復數(shù)據(jù)
-
只要記住rdd生成過程就可以了絮姆，這樣一次log可以用于很多數(shù)據(jù)，在不出錯的時候幾乎沒有開銷
image.png
大數(shù)據(jù)處理并行系統(tǒng)
用編程模型上的限制獲取好的容錯能力和高性能
K-V 對赞赖，細粒度修改； HDFS 只能添加數(shù)據(jù)
RDD 高吞吐率冤灾，不允許做細粒度修改前域，換取好的容錯能力和好的性能
SPARK 編程接口
- 基于Scala 語言
- 類似Java的一種函數(shù)語言
- 可以在Scala控制臺上交互式地使用Spark
- 現(xiàn)在也支持Java 和Python
- 基于RDD的操作
- Transformation： 從現(xiàn)有RDD產(chǎn)生新的RDD
- map, reduce, filter, groupBy, sort, distinct, sample ...
- Action: 從RDD返回一個值
-
count, collect, first ,foreach ...
image.png
- Transformation： 從現(xiàn)有RDD產(chǎn)生新的RDD
SPARK 編程實例--LOG挖掘
將數(shù)據(jù)從文件系統(tǒng)中調(diào)入內(nèi)存，然后進行交互式的查詢
lines = spark.textFile("hdfs://...")
errors = lines.filter(_.startsWith("ERROR"))
messages = errors.map(_.split('\t')(2))
cachedMsgs = messages.cache()
cachedMsgs.filter(_.contains("foo")).count // 包含foo的信息的數(shù)目
cachedMsgs.filter(_.contains("bar")).count
SPARK 實現(xiàn)技術(shù)
延遲估值（Lazy Evaluation）
val lines = sc.textFile("data.txt") //transformation
val lineLengths = lines.map(s => s.length) //transformation
val totalLength = lineLengths.reduce((a,b) => a+b) //action, trigger computation
- 前面兩行都不會觸發(fā)計算（Transformation）
- 最后一行的reduce會引發(fā)計算韵吨，生成DAG
有向無環(huán)圖
RDD性能的提高
對需要重用的RDD使用Persist和Cache提高性能
SPARK 應用和生態(tài)環(huán)境
SPARK 局限性
只能復制一份匿垄，標記少數(shù)節(jié)點。操作為網(wǎng)絡操作归粉、內(nèi)存拷貝操作椿疗、IO操作（由于數(shù)據(jù)是只讀的）-> 效率低，大量內(nèi)存拷貝糠悼。
每次細粒度的數(shù)據(jù)更新届榄，由于spark基于粗粒度RDD只讀的數(shù)據(jù)對象模型，需要RDD變換倔喂，即有大量數(shù)據(jù)的復制铝条，導致處理效率不高
