夢とガラクタの集積場

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

Apache Spark Streamingの論文を読んでみます(2章

こんにちは。

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

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

内容としては、「 Goals and Background」ということで、
そもそもの背景とSpark Streamingが目指すもののゴールについて書かれた章・・・となります。

論文第1章を読んでみるとこれってバッチ処理とリアルタイム処理を融合して実現する
「ラムダアーキテクチャ」(http://www.databasetube.com/database/big-data-lambda-architecture/)を
実現するのに最適な基盤だなぁ、とも思いつつ、実際の訳に入っていきます。

2. ゴールと背景

多くの重要なアプリケーションが大量データをリアルタイムに処理することで実現できる。
私たちの今回の施策のターゲットは数百ノードのマシン上で動作して、秒単位の遅延で実現したいアプリケーションとなる。
例としては以下のような感じ。

  • サイトアクセス統計

FacebookはPumaという分散統合システムを構築しており、ユーザに対して最適な広告を常時算出している。
遅延は10〜30秒程で毎秒100万のイベントを処理している。

  • スパム検知

TwitterのようなSNSは新たなスパムをリアルタイムに検出するために
統計機械学習アルゴリズムを常時実行している。

データセンターのオペレータはFlumeのようなログ収集プロダクトを使用して数百ノードの監視を常時行っている。

  • ネットワーク侵入検知

NIDSのようなシステムにおいて、毎秒数百万のイベントを解析して不正なアクティビティがないか監視を行っている。

これらのアプリケーションにおいては0.5〜2.0秒程の遅延で実現可能なD-Streamsは十分だと考えている。
D-Streamsを使用することで元のシステムよりより小さいタイムスケールで傾向をつかむことができ、
かつ障害復旧向けのレプリケーションも不要であるためマシンコストも削減可能。

尚、私たちは数百ミリ秒のレイテンシで対応が必要なリアルタイムトレーディングについては意図的に対象としていない。

秒単位のレイテンシに加えて、私たちが実現を目指すものは
耐障害性(障害や「遅いノード」問題から早期復旧)と効率性(基本的な処理のために必要となるハード以上に大きなリソースを極力消費しない)です。

耐障害性は私たちがターゲットとしている規模のシステムにおいて重要なファクターとなる。
加えて、障害復旧は高速(時間に厳しいストリーム処理では数秒での復旧が必要)である必要がある。
効率性も同じようにターゲットとしている規模のシステムにおいては重要なファクター。
例えば、常時処理をレプリケーションする必要があるシステムを数百ノード規模のクラスタで実行した場合、
どれだけのリソースが追加で必要になるか考えて欲しい。

2.1 既存のストリーム処理システム

分散ストリーム処理を実現するプロダクトはいくつかあるが、
ほとんどの既存システムは同じ「record-at-a-time」処理モデルを採用している。
このモデルにおいては、ストリーム処理は常時実行される状態を持つオペレーションに分割されて表現され、
そのオペレーションはメッセージを受信する度に処理を行い、内部情報を更新し、出力を送信している。
(例:全ウィンドウのページビューテーブル等)
下記の図(a)はその概要を示したものである。

この「record-at-a-time」処理モデルはレイテンシを最小化する。
だが、状態を持ったオペレーションをネットワークを介して非決定的論的に結合しているため、
効率的な耐障害性を提供するのは困難となる。

私たちは今回のアプローチを記述する前にまずはこの困難さについて明確化する。

2.2 障害や「遅いノード」問題に対する耐性を確保するための取組

「record-at-a-time」システムにおいては復旧方式はロストした状態の再構築や「遅いノード」の排除となる。
既存のシステムにおいてはこれらは2つのアプローチ
レプリケーション」か「上流データのバックアップ」で行われてきた。
このアプローチには障害復旧の際の所要時間とコストでトレードオフがある。

レプリケーション方式(データベースで取られるアプローチ)においては、
2つの演算描画グラフをレプリケートし、入力イベントは両方に送信する。

しかしながら、単にレプリケーションを行うだけでは不足で、2つのレプリケーション間で
同期をとって処理を行う必要がある(FluxやBorealisのDPC等)上、レプリケートされたタスクは
お互いに同じ順序で上流からイベントを受信し続ける必要がある。

例えば、オペレータが2つの親オペレータの結果を結合して出力するものだとする。
(順序はどちらか片方から受信した順番)
その場合、親オペレータは同じ順序で結果を出力する必要が出てくるため、
高速での復旧は可能だが、非常にコストが高くなる。

上流データのバックアップアプローチにおいては、
各ノードはあるタイミングから送信したメッセージをコピーして保持しておく必要がある。
ノード障害が発生した場合、待機系のマシンが役割を引き継ぎ、親ノードはメッセージを再送する必要がある。
このアプローチはノード障害発生時に情報を再計算・ストリーム間の送信も
再送する必要があるため、障害発生時に復旧時間が長くなる。

現状最も広まっているStormのようなメッセージキューイングシステムも同じアプローチをとっている。
このアプローチをとった場合「少なくとも1回処理する」という障害対応しか提供できない上、
ユーザ側でその対応について記述する必要があるという問題が生じる。
(Storm-Tridentの場合は毎回の結果は自動的にDB等のデータストアにバックアップすることで
 プログラミングモデルを単純化している。だが、その状態更新をトランザクション的に実行するために同期コストが高くなる。)

ここで重要なことは、「レプリケーション」「上流データのバックアップ」の両方のアプローチとも、
「遅いノード」問題については対処を行っていないことである。

もし「レプリケーション」のアプローチにおいてノードの処理が遅くなった場合、
メッセージを同じ順で処理し、同期が必要になる関係上システム全体が遅くなる。
同種の問題は「上流データのバックアップ」アプローチにおいても発生する。

現状、「遅いノード」を検知する手段は障害として扱う他なく、
それは遅くなったのが一過性かもしれない状況下において影響が大きくコストも大きくなる。

そのため、伝統的なストリーム処理プロダクトは小さめのクラスタか、
リソース的に余裕があるクラスタで有効になるケースが多くなる。
大規模なクラスタに適用した場合、障害や「遅いノード」という問題に苦しめられることになる。
=====
障害復旧の内容的には・・・微妙かもしれません。
Stormやその他ストリーム処理プロダクトを利用する際にはデータキャッシュ等も併用して
データロスト時の影響を押えこんでいるため上記のような復旧に伴う多大な処理は不要であることと、
処理に失敗したメッセージのみが再処理される形になるため復旧時間もそれほどかかりません。

ただ、メッセージ単位の処理/管理になるため効率が悪い上、Storm単体で全部できるかというと
そういうわけでもないのも確かです。

とはいえ、こうまで丸めて書いてしまうと都合がいい面を取り出してきてまとめたように
見えてしまうのですが、まぁそれは論文というわけで比較が必要なため仕方がない話なのでしょう。
いろんなプロダクトのプレスリリース等でも都合がいい比較が行われるわけですしね。

では、続きを読んでいきます。