分布式計算 Spark 入門介紹

Spark是一個通用的分布式內存計算框架，本文主要研討Spark的核心數據結構RDD的設計思路，及其在內存上的容錯。內容基于論文

• Zaharia, Matei, et al. "Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing1
• Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2012. PDF，PPT，中文翻譯
</ul>

論文提出了 彈性分布式數據集（RDD，Resilient Distributed Datasets） ，這是一種分布式的內存抽象，允許在大型集群上執行基于內存的計算（In-Memory Computing），與此同時還保持了MapReduce等數據流模型的容錯特性。

現有的數據流系統對兩種應用的處理并不高效：一是 迭代式算法 ，這在圖應用和機器學習領域很常見；二是 交互式數據挖掘工具 。這兩種情況下，將數據保存在內存中能夠極大地提高性能。為了有效地實現 容錯 ，RDD提供了一種高度受限的共享內存，即RDD是 只讀 的，并且 只能通過其他RDD上的批量操作來創建 。盡管如此，RDD仍然足以表示很多類型的計算，包括MapReduce和專用的迭代編程模型（如Pregel）等。論文中實現的RDD在迭代計算方面比Hadoop快二十多倍，同時還可以在5-7秒的延時內交互式地查詢1TB的數據集。

第一作者Matei Zaharia是UC Berkeley AMP Lab的PHD，MIT講師，Spark母公司Databricks的創始人。



背景

1. 迭代式算法的特點在于，它是給定問題y=f(x)，已知x和y，想要得到的是f的參數。所以需要從一個參數的initial值開始，掃描很多遍數據，比如說迭代100次，去逼近參數（類似數值分析中牛頓迭代法解方程的做法）。
2. Hadoop對迭代式問題沒有很好的解決，Disk－IO花費時間太多。Spark針對復雜分布式計算任務中，HDFS的反復讀寫特別耗時的問 題，給常用數據一種共享的狀態（內存的讀寫是TB級別的），特別適合交互式數據分析任務（對時間忍受很差），以及復雜的圖算法(pagerank)
</ol>

內存上的有效容錯

1. RDD是一種抽象數據集，中間數據不用的時候不需要具象化，對RDD使用persist()/cached()函數可以使其持久化。
2. 主流的容錯方法有兩種 1)logging（記錄細粒度update）2)快照（缺點就是代價太大）。
3. Hadoop采用數據持久化的方式進行容錯，HDFS每次讀寫都要做replica，代價是很大的。
4. 對于Spark，內存是易失的，某個機器down掉了，內存中的RDD就沒了。因此我們需要知道如果一個點failed，這個點的數據從哪里來。 其采用記錄RDD的血統（lineage）這種方式來進行容錯，可以根據lineage來重新計算缺少的部分。lineage有五點信息，包括數據在哪， 操作，優先使用什么，hash策略等。
5. 為了做容錯，RDD這種數據結構有兩種限制：1) immutable（只需記錄lineage就可以恢復）2) 是一種paritioned collections of record，只能從coarse-grained deterministic transformations（相當于從A到B只有一種走法，不能是隨機的）得到。
</ol>

和內存數據庫的區別

1. 數據庫是細粒度的，每一條record的價值都很大，通常不需要統計群體的情況
2. spark是粗粒度的，是“apply same operation to many items”，一次操作中大批數據都要參與進來。對于大數據來說任意一條數據是沒有意義的，群體特征才有意義。
3. 檢索任務（細粒度）涉及到剪枝，分析任務（粗粒度）涉及到全盤掃描或下采樣。
4. RAMCloud適合transaction事務級別（內存數據庫Redis），而Spark適合做batch批處理
</ol>

Spark實例：PageRank

1. Spark可以方便地做Join操作（link和rank兩張表)，而join的容錯恢復是比較難的，不是narrow dependence，而是wide dependence
2. Spark對用戶提供了三種interface: 1) RDD 2)RDD的操作 3)RDD切分的控制。主要有兩種不同類型的Flow: Data Flow(對數據進行改變，例如transformation and actions)和Control Flow(并不對數據進行改變，partitioning and persistence)
</ol> </div> 來自：http://suanfazu.com/t/fen-bu-shi-ji-suan-spark-ru-men-jie-shao/243