Resilient Distributed Datasetsに関する論文を読んでみます（１章
こんにちは。
前回、前々回でApache Spark、Spark Streamingの概要がわかりました。
ですが、内部で使用している共有分散メモリ機構であるResilient Distributed Datasets(RDDs)が
鍵となる割に概要しか資料からはわからなかったため、論文を読むことでもう一段階理解を深めてみます。
読んだ論文は以下です。
「Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing」
（http://www.cs.berkeley.edu/~matei/papers/2012/nsdi_spark.pdf）
あと、内容が理解できればいいので、全文訳というわけではありません。
Abstract
本論文において、プログラマが大規模クラスタ上でのメモリ上計算を耐障害性を確保した上で
実行するための抽象化された分散メモリである弾力性のある分散データセット（RDDs）を提示する。
RDDsは現状のクラスタ上のコンピューティングが以下の２つの非効率を抱えていることから開発された。
1.インタラクティブなアルゴリズム（機械学習、グラフ描画）
2.インタラクティブなデータマイニング
上記の２ケースにおいて、データをメモリ上に確保したままで処理することで性能を劇的に向上させることができる。
その上で、効率的に耐障害性を確保するためにRDDsは詳細な更新が不可で『荒い変換のみ可能』な制限されたデータセットとして提供される。
しかしながら、『制限されたデータセット』であっても最近の反復計算ジョブ・・・
Google Pregel（グラフ計算）その他の計算モデルに対しては十分適用可能だと考える。
本論文ではRDDsを分散処理基盤であるSpark上で実現し、性能評価した結果を記述する。
1.イントロダクション
昨今、MapReduceやDryadといったクラスタコンピューティング基盤が大規模データ解析に使用されている。
これらの基盤はユーザが分散方法、耐障害性を気にすることなく高レベルの演算を記述するだけで分散並列処理を可能としている。
これらの基盤はクラスタ上のリソースに対するアクセスを抽象化して提供しますが、分散メモリを活用するための抽象化は行っていない。
そのため、複数の計算を越えて結果を再利用する場合かなりの非効率を生んでいる。
データの再利用による効率化はページランク算出、K-Meansクラスタリング、論理回帰等を含む機械学習／グラフ計算に対して共通的な性質となる。
別の有用なデータマイニングユースケースとして、あるデータセットに対するアドホックなクエリを発行して検索を行うものがある。
だが、残念ながら現状の多くのクラスタコンピューティング基盤においては
異なる計算（例：MapReduceのジョブ間）をまたがってデータを持ち越す場合、
外部ストレージ（例：分散ファイルシステム、HDFS）に対してデータを保存し、それを用いて持ち越す手段しか提供されていない。
この外部ストレージに対する書込読込（データレプリケーション、ファイルIO、シリアライズも伴う）のオーバーヘッドは
分散並列処理にかかる時間の支配的な要素となってしまっている。
この問題は広く認識されており、研究者は以下のように特定用途に特化した基盤においてはメモリ上にデータを保持して計算を効率化することを行ってきた。
・Pregel：インタラクティブなグラフ描画のための基盤。内部のデータをメモリ上に保持することで計算を効率化している。
・HaLoop：反復MapReduceのインタフェースをサポートするメモリ上で演算するための基盤
だが、これらの基盤はHaLoopの反復MapReduceのように限られたコンピューティングパターンのみしかサポートしていない。
加えて、「データを共有する」ことが前提となっており、柔軟性に欠ける。
そのため、これらの基盤は汎用的なデータ再利用のための抽象化は提供せず、アドホックなクエリの繰り返し実行のようなユースケースにも対応しない。
本論文では幅広いユースケースに適用可能なデータ再利用抽象化基盤である弾力性のある分散データセット（RDDs）を提示する。
RDDsは耐障害性を保持し、並列利用可能で、ユーザが明示的に内部データとして保存させることができる。
データ配置は最適化され、豊富なオペレーションセットをサポートしている。
RDDsによるメインチャレンジとして、効率的な耐障害性を提供することがあげられる。
現状存在しているクラスタ上のメモリ保持基盤としては分散共有メモリ、KVS、データベース、Piccoloといったものがあげられる。
これらは特定のインタフェースに沿ったきめ細やかな更新（例：テーブル中のセルを更新）をサポートしている。
これらのインタフェースの基に耐障害性を提供する際に取る手段は「マシン間のレプリケーション」か「更新結果のログ記録」となる。
この２つのアプローチはデータ集約型のアプローチとなり、クラスタ内ネットワークを使用して大容量のデータをコピーする必要があるために負荷が大きくなる。
帯域幅がメモリ＞＞ネットワーク＞ストレージという状況で行われるコピーのため、ストレージによってコピーの速度は大きく制限される。
これらのアプローチとは対照的に、RDDsは「荒い変換インタフェース（map、filter、join等）」のみしかサポートしない。
このインタフェース群を通してオペレーションを行うとRDDsに保持される大量データに対して全てインタフェースによる変換がおこなわれる。
RDDsはデータそのものを記録するのではなく、「RDDsを構築するためにデータに対して行った変換」を記録することで効率的な耐障害性を実現している。
もしRDD中の一部分がロストした場合、RDDはそのデータが他のRDDからどのように変換されて生じたデータかを保持しているため、
コストの大きなレプリケーションなしに迅速に再計算／復旧させることができる。
「荒い変換インタフェース」しか持たないRDDsは一見使えないように見えるかもしれないが、
並列アプリケーションにおいて行われる実際のオペレーションは全てのデータに同じ演算を並列実行することで実現されるため、実質的にうまく適応する。
実際に、RDDsを用いることで分散システム上で並列コンピューティングを行う際に適切に処理できることを示す。
適用可能な計算はこれまで提案されてきたMapRedude、DryadLINQ、SQL、Pregel、HaLoopといったものに加え、
これまでは存在しなかったインタラクティブなデータマイニングといったアプリケーションにも及ぶ。
これまでは新しいフレームワークを導入することでしか解決しなかった新たなコンピューティングニーズに対して
RDDsを用いることで抽象化し、共通的に解決できることを示す。
我々はSparkというシステム上でRDDsを実現した。
Sparkはカリフォルニア大学バークレー校や他の複数の企業で研究／実アプリケーションとして使用されている。
SparkはScala上でDryadLINQのような使用しやすいプログラミングインタフェースを提供する。
加えて、Scalaインタプリタを用いてビッグデータに対するクエリをインタラクティブに実行可能。
我々はSparkがメモリ上のデータへのインタラクティブな汎用データマイニングを可能とする初のシステムだと考えている。
我々はRDDsとSparkをもちいてユーザアプリケーションの評価を行った。
結果、インタラクティブなアプリケーションにおいてSparkはHadoopの20倍高速に、
実世界のデータ解析を行うアプリケーションにおいて４０倍高速な結果となった。
その際、１ＴＢのデータを検索するのに必要なレイテンシが5〜7秒となっている。
RDDがより汎用的に使用できることを示すために我々はPregelとHaLoopのプログラミングモデルをSpark上で
実現するためのライブラリを作成した。（各々200行程）
この論文は以下の構成からなる。
２．RDDs概要
３．Spark概要
４．RDDsの内部構造
５．実装
６．検証結果
７．RDDが各種クラスタ上のプログラミングモデルに適用可能であることの議論
８．関連研究
＝＝＝＝
とりあえず、１章はこんな感じでした。
２章、３章、４章と７章あたりはSparkとRDDを理解するのに必要な内容のようですね。
その他の章は・・まぁ、余裕があったら読んでみます。
では、以後は次回以降の投稿で。
色々並行しているので間が挟まることもあります＾＾；
