Spark
Spark是一個小巧玲珑的項目，由Berkeley大學的Matei為主的小團隊所開發。使用的語言是Scala，項目的core部分的代碼只有63個Scala文件，充分體現了精簡之美。
Spark要解決的問題是，在當前的分布式計算框架中不能有效處理的兩類問題：iterative（迭代計算）和 interactive（交互式）計算。
目前最流行的Hadoop 系統實現了DAG（有向無環圖）的data flow 式的計算，不能處理有環的計算，也就是輸入同時做為輸出的循環計算。
Spark更適合於迭代運算比較多的ML（machiningleaning和DM（data mining）運算。Google 的Pregel 的分布式圖計算中，就含有大量的迭代計算。
那麼Spark是如何實現的呢？其主要的思想就是RDD（Resilient Distributed Dataset），把所有計算的數據保存在分布式的內存中。在迭代計算中，通常情況下，都是對同一的數據集做反復的迭代計算，數據保存在內存中，將大大提高性能。 RDD就是數據partition方式保存在cluster 的內存中。操作有兩種： transformation 和 action， transform就是把一種RDD轉換為另一個RDD，和Hadoop的 map 操作很類似，只是定義operator比較豐富（map， join，filter， groupByKey 等操作）， action 就類似於hadoop 的reduce，其輸出是一個aggregation函數的值如count，或者是一個集合（collection）。
Spark 的設計思想並沒有什麼獨特之處，核心就是內存計算。關鍵的問題是，如何處理fault tolerance這個核心的問題？我們知道hadoop 的核心就是 MapReduce，其計算模型是：
Input(HDFS) --> output(HDFS), 其輸入和輸出都是在persistent的 disk上保存，並且有replication. 如果輸入和輸出節點都崩潰，其還有副本，選擇一個新節點重新計算。
如果數據保存在內存中，一旦宕機，數據永久丟失。通常的處理方法就是做checkpoint 和 log updates across machine兩種方法。
Spark並沒有提供一個比較好fault tolerance的方法，其論文中提到的lineage(血統）的方法： logging the transformations used to build a dataset，就是log 每次操作（lineage）用來恢復。
我們看一下Spark操作模型：
Input（RAM） ---> output(RAM) 的計算模型。
在論文中，Spark提到了兩種依賴（Dependency）。
一種是Narrow Dependencies這個計算完全在本地的內存中，對於所謂的Lineage的容錯方法對這種情況是沒有用的，因為輸入和輸出在同一個節點，一旦該節點宕機，數據全丟。論文中提到的work around方式是replication；
對與Wide Dependencies，這種計算的輸入和輸出在不同的節點上，lineage方法於：輸入節點完好，而輸出節點宕機的情況有效的，通過只重新計算宕機的分區即可。在輸入節點宕機的情況下，顯然重試是無效，需要向上追溯其祖先看是否可以重試（這就是lineage，血統的意思）。
Spark 論文最後提到了，提供了一種checkpoint 的標志。至於何時做chenkpoint，由用戶根據業務自己決定。在論文Discussion部分，提到今後的研究就是如何實現自動的checkpoint操作。MPI的fault tolerance的方法，就是做各種checkpoint的策略，這個在高性能計算已經研究了好多年了，並有很多方法。
最後感歎，很多的研究，轉了一圈，最後又回到了起點。