夢とガラクタの集積場

落ちこぼれ三流エンジニアである管理人の夢想＝『夢』と、潰えた夢＝『ガラクタ』の集積場です。

Apache Spark Streamingの論文を読んでみます（５章

Spark

以下論文を読んでみようの続きで、今回は第５章です。

「Discretized Streams: A Fault-Tolerant Model for Scalable Stream Processing」
（http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-259.pdf）

内容としては、「Fault and Straggler Recovery」ということで、
障害復旧について記述した章になります。

5. Fault and Straggler Recovery

D-Streamsの決定論的な性質は伝統的なストリーム処理技術では使用するのが困難な
２つの強力な復旧技術（ロスト状態の並列復旧、「遅いノード」に応じた投機的実行）を実行可能にしている。

5.1 並列復旧

ノード障害が発生した際、D-StreamsはRDDとタスクを同じように別ノードでの並行実行による復旧を許容している。
システムは定期的にRDD状態のチェックポイントを取得し、別Workerノードに非同期でレプリケーションを行っている。

例えば、ページビューカウントプログラムを走らせており、
システムが１分ごとにチェックポイントを取得するよう設定されていたとする。
すると、ノード障害が発生した際、システムは障害によってロストしたRDDパーティションを検知し、
ロストしたパーティションを最後のチェックポイントから再算出するタスクを実行させる。

多くのタスクが別々のRDDパーティションに対して実行することができるため、
クラスタ全体が状態の復旧を並列して行うことが可能となる。
そのため、並列復旧はシステム全体のレプリケーションを取ることなく素早い状態復旧が可能となっている。

並列復旧は既存のストリーム処理に適用するのは難しい。
なぜなら、「record-at-a-time」システムにおいて適用するためには
基本的なレプリケーション確保であっても複雑かつコストの高い記録プロトコルが必要となるため。
このレプリケーション／復旧処理はMapReduceのような決定論的なバッチ処理においてはシンプルになり、実行可能。

並列復旧の効果を下記の図に示す。

この図はシングルノードの上流バックアップ方式（シンプルな解析モデル）と並行復旧のコストについて比較したものである。
１分前のチェックポイントから復旧させることを前提としている。

上流バックアップのグラフにおいて、１つのアイドルマシンを受信レコードを処理しなおすことで復旧させる処理に割り振っている。
復旧には元々システムの負荷が高かった場合長い時間がかかる。
なぜなら、新しいレコードは復旧処理中も常時送信され続けるからである。

仮に、障害発生前にシステムの負荷割合が「λ」だったとする。
１分の復旧処理を行う間に、λ分だけ新しいレコードを処理することに費やされる形になる。
こうして１分ごとにλ分だけ新規処理を継続する状態で復旧に必要となる時間をt{\small up}とすると、λとt{\small up}の関係はt{\small up} =\lambda+t{\small up}\lambdaとなる。
そのため、復旧にかかる時間はt{\small up}=\frac\lambda{1-\lambda}で記述できる。

他のグラフは他のマシン上で復旧処理を新規レコードを受信しながら並列実行した場合のグラフとなる。
障害発生前にクラスタ内にN個のマシンがいた場合、N-1個のマシンが復旧処理を実施できる。
そのため、各マシンは毎分\frac\lambda{N}の時間をかけて復旧処理を行う形になる。
その上で、新規レコードを処理するために毎分\frac N{N-1} \lambda分の処理を行う必要がある。
復旧に必要となる時間をt{\small par}とすると、λとt{\small par}の関係はt{\small par}=\frac\lambda{N}+t{\small par}\frac N{N-1} \lambdaとなる。
そのため、復旧にかかる時間はt{\small par}\simeq \frac\lambda{N(1-\lambda)}で記述できる。

上記の結果より、並行復旧はノード数が増えるほど復旧時間が短縮されることがわかる。

5.2 Straggler Mitigation

障害と並んで大規模クラスタにおいて重要な関心ごととなるのは「遅いノード」問題となる。
幸いなことに、D-Streamsは「遅いノード」の軽減をバッチ処理システムと同様に投機的処理を行うことで対応できる。

このような投機的処理は「record-at-a-time」システムで実行するのは難しい。
なぜなら、ノードの状態も含めたコピーが必要となるからである。だが、「遅いノード」のコピーを取得するのは難しい。
実際、ストリーム処理のレプリケーションはFlux等においては２つのレプリカを同期させることに焦点を当てており、投機的ではない。

現状私たちは「遅いノード」を検知するためにシンプルな閾値を使用している。
ジョブ中の中間タスクの終了タイミングが１．４倍以上の時間がかかった場合、遅いノードとしてマークする。
よりよりアルゴリズムがあるのかもしれないが、現状十分な対応が行われており、「遅いノード」も秒単位の遅延で復旧が可能となっている。
＝＝＝＝＝
ある意味この章はそれまでの内容を順当になぞってきた感じではあります。
では、次回に１投稿にまとめてしめます。