147
Spark RDDs(彈性分布式數據集):為內存中的集群計算設計的容錯抽象
本文是閱讀《Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing》過程中，抽了局部一些關注點翻譯出來的文章，沒有將全文都翻譯。希望這些碎片化甚至不通順的記錄，可以幫助讀者取代閱讀原論文。
第一節
主要介紹了現有的集群計算框架存在的問題，然後介紹了RDD的幾個設計亮點，對比了Spark的不同之處和優勢點
解決現存迭代式算法和交互式數據挖掘倆問題 iterative algorithms and interactive data mining tools.
嚴格的內存分享，粗粒度而非細粒度 based on coarsegrained transformations rather than fine-grained updates to shared state
Dryad 和 MR 是現有的集群計算框架 他們能分布式 能容錯 但是沒能利用好分布式內存
導致他們在多次利用中間數據的計算上不夠效率
有很多迭代式機器學習和圖算法 PageRank K-means LR
還有一點 就是幫助交互式數據挖掘
現有的解決計算之間（如兩個MR job下麵）重用數據的方法 是存到一個外部分布式文件係統裏
這帶來了很大的間接消耗在 數據備份，磁盤IO，以及序列化 而這些主宰了執行時間
已經出現的針對這一問題的特殊框架：Pregel 迭代式圖計算 把中間數據存內存 HaLoop提供迭代MR接口
但他們隻針對一部分特殊計算組件，對數據分享做的很含蓄，沒有提供更抽象，通用的重用
RDD的一個原文定義：
RDDs are fault-tolerant, parallel data structures that let users explicitly persist intermediate results in memory, control their partitioning to optimize data placement, and manipulate them using a rich set of operators.
第二節
介紹RDD
RDD是隻讀，分區記錄的集合
transformations：從現有的存儲文件生成RDD或由別的RDD生成新RDD
RDD不用一直物化，他充分知道自己是怎麼被計算出來的，他的lineage血緣
persistence and partitioning 是RDD另兩個方麵
持久化指用戶可以指定他們要哪個RDD，存儲策略是什麼
分區指用戶可以決定key來讓RDD分區在機器之間，這對於 位置優化(placement optimizations)很有用
Spark編程API，對RDD進行的actions，如：count()，collect()，save()
且是懶式的，所以可以管道式變換 (pipeline transformations)
用戶可以持久化RDD，Spark默認是放內存裏，RAM不夠大就放磁盤上
用戶可以指定持久化策略，比如隻存硬盤上或在不同機器上複製，設置flag，最後用戶可以設定優先級，哪個內存裏的數據先放到硬盤上
RDD與分布式內存(DSM)的對比：
DSM是一個很通用的抽象，他的普遍性導致了比較難實現容錯和高效
RDD不適合大塊的寫，但是更高效和容錯，且沒有檢查的開銷，因為可以借助血緣恢複，且丟失的分區在重新計算的時候，也是在不同節點上並行的，比回滾整個程序快很多
對於大塊數據的操作，RDD會調度到本地數據執行，提高效率。數據太大就存硬盤。
RDD不適合大塊的寫，但是更高效和容錯，且沒有檢查的開銷，因為可以借助血緣恢複，且丟失的分區在重新計算的時候，也是在不同節點上並行的，比回滾整個程序快很多
對於大塊數據的操作，RDD會調度到本地數據執行，提高效率。數據太大就存硬盤。
RDD不支持的場景：
RDD適合批處理，具體是對數據集裏所有元素進行同一個操作，這樣他執行轉換和恢複就很快，原因是不記錄大量log
不適合異步細粒度更新，比如web引用的存儲和增量web爬蟲
不適合異步細粒度更新，比如web引用的存儲和增量web爬蟲
第三節
Spark編程接口
選用Scala是因為他的簡明(交互式)和高效(靜態類型)，而RDD並沒有函數式編程的需求
RDD是靜態類型對象
join適合key-value的RDD
拿邏輯回歸裏的梯度下降和PageRank，介紹了下迭代式計算的方式和RDD上的寫法
第四節
RDD的表示
如何表示RDD之間的依賴：窄依賴，一個父RDD最多被一個子RDD用(map);寬依賴，多個子RDD(join)
窄依賴：在一個集群節點上管道式執行，計算所有父分區。如map->filter;錯誤恢複很高效
寬依賴：要求所有父分區可用，在所有節點上進行類mapreduce操作
第五節
實現
每個Spark程序在Mesos上是一個獨立的應用，有自己的驅動，worker以及Mesos分配的共享資源
下麵講幾個實現中的有趣部分：任務調度，允許交互式的Spark解釋器，內存管理，檢查支持(checkpointing)
任務調度
Spark的任務調度類似Dryad
每當用戶進行一次action，首先會檢查RDD的血緣圖，建立一個stages的DAG，按stage來執行這次action
每個stage都盡量包括盡可能多的管道式變換的窄依賴，stages之間的界限，就是寬依賴的洗操作，或者任何已經準備好了的分區。調度器就一個個執行這些stage，直到目標RDD生成出來
下麵講幾個實現中的有趣部分：任務調度，允許交互式的Spark解釋器，內存管理，檢查支持(checkpointing)
任務調度
Spark的任務調度類似Dryad
每當用戶進行一次action，首先會檢查RDD的血緣圖，建立一個stages的DAG，按stage來執行這次action
每個stage都盡量包括盡可能多的管道式變換的窄依賴，stages之間的界限，就是寬依賴的洗操作，或者任何已經準備好了的分區。調度器就一個個執行這些stage，直到目標RDD生成出來
調度器布置任務是基於數據本地化分配的，采用延遲調度。
對於寬依賴，目前是物化中間結果在節點上，保持住父分區來簡化錯誤恢複，和MR的map outputs相似
任務失敗則重跑，如果丟失了如shuffle這樣的中間結果會重新計算，目前不容忍調度失敗
lookup操作提供隨機訪問元素，根據key在哈希分區上找
解釋器整合
在scala解釋器的基礎上，做了改變：
class shipping：讓工作節點通過http獲得class的bytecode
修改了的code generation邏輯：為了讓work節點能拿到引用，直接指向每行的實例(可能翻譯不準確,理解不是很到位)
內存管理
Spark提供三種持久化RDD的存儲選擇：以反序列化java對象的方式存內存，以序列化數據的方式存內存，存磁盤
第一種最快，jvm可以本地化取RDD元素，第二種是高效內存化的方式
內存策略是LRU，新的RDD不夠空間的時候，貫徹最近最少原則。同時，給予用戶對RDD“持久性優先級”的控製
目前RDD有自己單獨的內存空間，將來打算調研用一個統一的內存管理者在不同的實例之間分享式RDD
支持檢查(checkpointing, 翻譯為檢查可能不太妥當，見諒)
盡管從RDD錯誤恢複的時候會使用血緣，但如果血緣鏈很長，就會很耗時，所以有必要對一些RDD進行 穩定存儲時的檢查
所以是為了長血緣鏈提供的，比如PageRank，短的不值得。
API是persist裏的一個REPLICATE flag，主導權在用戶手裏，也在調研自動化檢查。因為調度器知道每個數據集大小，第一次計算出來的耗時，所以應該可以做到優化最少恢複時間的選擇。
同時，RDD的隻讀特性有利於檢查，不需要中止和影響別的程序
對於寬依賴，目前是物化中間結果在節點上，保持住父分區來簡化錯誤恢複，和MR的map outputs相似
任務失敗則重跑，如果丟失了如shuffle這樣的中間結果會重新計算，目前不容忍調度失敗
lookup操作提供隨機訪問元素，根據key在哈希分區上找
解釋器整合
在scala解釋器的基礎上，做了改變：
class shipping：讓工作節點通過http獲得class的bytecode
修改了的code generation邏輯：為了讓work節點能拿到引用，直接指向每行的實例(可能翻譯不準確,理解不是很到位)
內存管理
Spark提供三種持久化RDD的存儲選擇：以反序列化java對象的方式存內存，以序列化數據的方式存內存，存磁盤
第一種最快，jvm可以本地化取RDD元素，第二種是高效內存化的方式
內存策略是LRU，新的RDD不夠空間的時候，貫徹最近最少原則。同時，給予用戶對RDD“持久性優先級”的控製
目前RDD有自己單獨的內存空間，將來打算調研用一個統一的內存管理者在不同的實例之間分享式RDD
支持檢查(checkpointing, 翻譯為檢查可能不太妥當，見諒)
盡管從RDD錯誤恢複的時候會使用血緣，但如果血緣鏈很長，就會很耗時，所以有必要對一些RDD進行 穩定存儲時的檢查
所以是為了長血緣鏈提供的，比如PageRank，短的不值得。
API是persist裏的一個REPLICATE flag，主導權在用戶手裏，也在調研自動化檢查。因為調度器知道每個數據集大小，第一次計算出來的耗時，所以應該可以做到優化最少恢複時間的選擇。
同時，RDD的隻讀特性有利於檢查，不需要中止和影響別的程序
第六節
評估
在迭代式機器學習和圖計算中，節省的主要耗時在於避免了IO開銷和反序列化開銷
迭代式機器學習評估
kmeans和邏輯回歸，前者重在計算，後者重在反序列化和IO開銷
Spark在第一次之後的迭代中速度是非常快的。而在第一次迭代中，也稍快於hadoop，因為hadoop在master和slave之間的心跳機製
等等別的對比，以及已有的應用場景介紹
第七節
討論
介紹了一些相關的係統
RDD的設計還有利於debug
第八節
相關工作
詳細歸類了各種類似係統
詳細歸類了各種類似係統
第九節
總結
略
(全文完)
最後更新：2017-04-03 16:48:57