[StreamDS/StreamShedder] Data Stream Load Shedding - Dynamically Managing Channel Capacity by Amit Ahuja

今年は、DSMS における Load Shedding にも本格的に取り組んでいきたいので、以下の本を誰か一人に読んでもらいたいと思います。本の内容は、ある研究者が提案している一手法なので、この周辺の研究の様々な手法を紹介しているわけではないことには注意が必要ですが、論文の書き方、数理的なモデルの構築方法、アルゴリズムの書き方は、Load Shedding に関わらない人にとっても多いに参考になると思います。

Data Stream Load Shedding - Dynamically Managing Channel Capacity by Amit Ahuja　(Amazon)

[当研究の大枠]

当研究では以下の2つの Load Shedding を取り上げているが、特に (1) の手法に焦点を当てて論じている。

(1) intra-stream load shedding: ある特定のストリームの中で重要度の低い属性を間引くことで、与えられた通信チャネルの限界容量を越えないようにする。この研究では、間引く単位は、”タプルではなく”、”属性”単位で間引くこと、そして、Source で間引いたデータを recovery する機能、の2つがユニークだと主張する。

(2) inter-stream load shedding: 単一のチャネルを複数のストリームが流れ、その総和がチャネルの限界容量をコ越える際の問題。すべてのストリームを管理する central load shedder というコンポーネントが存在し、それが各ストリームのデータ転送レートを監視し、どのストリームのどの属性をどのくらい間引けば（ぎりぎり）限界容量を越えないかを判断する

[分散を用いた属性のランキング決め]

ストリームの属性の判断の仕方は、すべての属性のデータの「分散」を求めて、分散が大きいものはより重要度が高く、小さいものは「重要度が小さい」とする。トレーニングセットを用いて、ストリームのデータセットのすべての分散を計算し、タプル中の各属性のランクを決める (3.2.3.2)

[属性のランキングを決める上での工夫]

タプルの属性のランクを決める上で、ある属性（例えば砂漠上の降水量）が偶然そのトレーニングセットで突発的な変化（ある時間帯だけ瞬間的に雨が降った、等）が含まれている場合には、その属性のランキングが高まってしまい、より重要な属性（例えば砂漠の温度の変化）を落としてしまう可能性がある。ランキングの精度を高めるために、当研究では "移動平均 (Moving Average）" を使用している。移動平均には、スライディングウィンドウ中に存在するあるデータリスト（時系列順に揃っているデータ）の各データに対して、すべて同じ重みをつけて計算する Simple Moving Average (SMA) と、より新しいデータにより高い重みを付けて計算する Exponential Moving Average (EMA) が存在する。EMA の計算方法は p35 の (3.2) によって計算される.(3.2.2, p33-) 後の評価では、SMA 及び EMA を比較するが、当然ながら EMA の方がより良い結果を得ている。

[間引く量]

Load Shedding では、「何を間引くか？」と「どれくらい間引くか？」の２つの課題があるが、3.2.3.1 に記載されているが、バンド幅を B とし、ストリームのデータレートを R とすると、当然、 (R-B) の分だけ取り除く必要があり、かつ上記の属性のランキング決定に基づいてどの属性を何個取り除くかを決定する。属性によってバイト数が異なるため、それももちろん考慮する。

[適応的な Load Shedding Schema の変更方法]

Load Shedding Scheme (間引く戦術）自体は、静的に決められるものではなく、ある時間間隔 (インターバル）を持って再評価し、その時間帯で最適な Scheme に更新する必要がある (3.2.3.3, p41). この再評価のインターバルだが、短すぎるとパフォーマンスに影響を与えるし、長すぎると短期的な変化に対応できない。そこで、当研究では、まず、初期値のある程度短いインターバルをもって計算。次の再評価の時に、前回の Scheme （属性のランキングなど）と比較し、差がほとんどなかったら、インターバルの時間を2倍に設定する。次の評価の際に、 Scheme と設定した閾値以上異なる場合には、インターバルを初期値にリセット。このアルゴリズムが p42 に記載されており、"Adaptive Load Shedding Scheme Re-evaluation Algorithm" と呼んでいる。

[間引いたデータの復旧方法]

エンドユーザーは、Load Shedding が実行されたときに、ソース側で間引かれた属性を要求する場合がある。Shed したすべてのデータをディスクに保存しておくことは無理なのでエラー閾値（Error Threshold Value: 返された値が間違っている場合）とソースサイドにおける計算・ディスク容量とのトレードオフ（保存するにもCPUパワーは当然使う）になる。この問題のために、当研究では、「Euclidean Distance」と 「Synopsis Recovery Algorithm」の２つを提案している。

　後者は、Synposis、つまりサマリーデータ (Synopsis Recovery Matrix と呼ぶ）を保存しておき、Shed しようとしているデータと最も直近ののデータの差がエラー閾値以上であったら、Synopsis に貯められているデータの更新をし、閾値以下であったら更新しない。このエラー閾値はアプリケーション毎に異なり、インターネットモニタリングよりも患者のモニタリングの場合の方が当然閾値がきつくなる。

StreamShedder 続き

松浦君の卒論テーマに関して。

このエントリ の論文では、オンラインとオフラインのジョブの resource sharing 手法を提案しています。この論文との差異を述べてください。

StreamShedder

松浦君が行っている StreamShedder の研究へのコメント

■ SSD にどのくらいデータを退避させれば良いか.
データ受信部の CPU とネットワークがぎりぎり耐えられるぐらいのデータ量が学習モードで把握できるはずなので、その分 SSD に退避させればよい

■ SSD に退避できないぐらいのトラフィックがきたときは
　 どうするか？
- 捨てる？

■ 負荷情報はどのように具体的に何からとるか？
- 実装は何を使う？ vmstat ?
- 突発的な負荷の変化以外に、学習していけばどのような周期でデータレートが変化するかがわかるはずなので、それも活用すべき

■ 高頻度に、”高データレート”→”低データレート”、”低データレート”→”高データレート”のモードを
　を繰り返すときに、ナイーブに実装すると、処理が「ストリーム処理」と「バッチ処理」の切り替えが頻繁におきてしまう。どのように対処するか？　マクロ的なスケジューリングも大事

■ ストリーム処理→バッチ処理、バッチ処理→ストリーム処理にコンテキスト切り替えするときの、どのように状態を保存するか？特に、バッチ処理の途中で、モードが変化してはまずい

■ この階層型の Load Shedding がどのようなタイプのアプリケーションに効果的かをはっきりさせるべき。例えば、SSD による退避で、後か結果を知っても意味のないタイプのアプリケーションがあるはず。
どのようなアプリに効き、どのようなアプリに効かないかを明らかにすべき

■ この研究の定量的な評価をどのように行うか？アプリケーションとしては、Twitter のほかには何を使うか？

SEDA の論文（続き）

このエントリのさらに続き

- Matt Welsh による SEDA の過負荷時の制御手法について論じた論文. DSMS における Load Shedding に関しても大いに関係してくる。
Matt Welsh and David Culler, "Adaptive Overload Control for Busy Internet Servers"

- SEDA の肝は 2.2 章に書かれているが、ソフトウェアをステージに分割し、開発者に明示的にキューのコントロールを許すことによって、アプリケーションに特化したパフォーマンスコントロールが可能になること。System S 自身はキュー自身は見えていないので、その部分は UDOP (User-Defined Operator) で実装する必要がある。また、ステージ化することのその他の利点は、パフォーマンスのボトルネックを発見するのが容易になること。ステージごとのキューの状態（常に満杯になっているか？）を監視することで、容易にボトルネックがわかるし、そこのキューだけを制御しさえすれば良くなる。

- ニュースサイトなどではある突発的な事故などが起きると、システムの想定するリクエスト数の百倍、千倍のリクエストが到着することがある (これを Slashdot Effect とかつては呼んでいた）。しかし、これらを想定して Capacity Planning していては Over Spec なシステム構築となる。よって、ソフトウェア的にそれらを回避する必要がある。

- 回避方法としては、コネクション数やスレッド数の上限を設定しておき、リクエストを受け付けない方法と、もう一つは、結果のクオリティを下げる方法がある。後者は例えば、HTML を通常版と軽量版 (Ethernet パケットに収まるぐらい。例えば、画像も解像度を低くするなど）の２つを用意しておき、過負荷時には軽量版の HTML ファイルをクライアントに返す方法などがある。

- この従来の手法は、コネクション数とスレッド数をサーバー管理者が Web サーバーの設定ファイルなどに設定する必要があるが、これは経験的に決められたものであり、必ずしも最適値にならない。よって、低い値にしまいすぎて、スループットが出なかったり、大きくしすぎると、常にシステムが満杯状態で、すべてのリクエストに対してレスポンスタイムが悪くなるという事態に陥ってしまう。

- このようなケースは、Web サイトの運営者側からすると宜しくない状況で、レスポンス時間が長いと、顧客が離れていってしまう恐れが高まる。運営者からすると、平均的にすべてのユーザーに悪いレスポンスタイムを返すよりも、一部のユーザー（例えば１０％）には、きっぱりと、「今は混んでるから後から来てね」と断り、他の90％に対して、それなりに acceptable なレスポンスを返してしまった方が良いだろう。

- この論文では、上記のような問題に対して、パフォーマンスコントロールを柔軟に可能にするフレームワークを SEDA 上に構築。Web Mail システム Arashi を構築して評価している。

- SEDA のキューに入ってくるメッセージの処理時間（レスポンスタイム）をモニタリングし、その傾向によって性能制御する仕組みを設計。例えば、レスポンスタイムが悪くなってきたら、ある一定数の確率でリクエストを Drop したり、他のサーバーに割り振ったりする。

- キューを監視するコントローラを設定し、リクエストがキューに入った時間と、処理を完了し、クライアントに結果を返すまでの end-to-end の時間を測定。その TAT (Turn around time) がある閾値以上になったときには、Load Shedding アルゴリズムを発動させ、一部のリクエストを優先して処理し、一部はあきらめることによって、全体のレスポンスタイムの中央値を良くする手法を提案。

ClickStream の分析ツール

ClickStream の分析ツールのオープンソースソフトウェアは、ここに
リストアップされている. いずれも、Apache などのログから、グラフ視覚ツール graphviz を用いて視覚化。
Apache2Dot
Visitors
Web Utilization Miner
Statviz
"StatViz can actually show you these reports LIVE... If you configure the logfile to "php://stdin" then StatViz will read the log lines from STDIN. It will then periodically generate reports as the log is processed, thus allowing you to watch your traffic patterns in real-time" だそうで、リアルタイムに視覚化することも可能。

クリックストリームの過去の研究は、ここ (PDF) などが参考になるので、見てみてください。

Predicting Online Task Completion with Clickstream Complexity Measures: A Graph-Based Approach
http://www.net-question.com/chairerbc/fichiers/KSN06.pdf

ここによると、Click Fraud (Wikipedia) の Real-time Detection にも System S が使えそうです。

"As pay-per-click advertising becomes the fastest growing segment of all　advertising tools, malicious click fraud is keeping pace and shows no signs of　containment.　Advertisers are demanding resolution to this problem because it can cost them millions of dollars. Successful search engines, marketing companies and e-businesses know that fighting click fraud means quickly recognizing patterns, either through statistical algorithms automated for online filtering, or manual offline analysis. These analyses require comprehensive processing of terabytes of dynamic, detailed data in near real-time to quickly detect and stop the fraud from spreading."

また、Google でも Click Fraud Detection の対策をしているようです.

Botnet （悪意のあるコンピュータプログラム）による Click Fraudによる非常に深刻らしく、Fraud の31％が Botnet によることを示したグラフ（http://www.techcrunch.com/2009/01/27/report-click-fraud-at-record-high/）

ClickStream

Web サイトでのユーザーの行動履歴 ClickStream はWikipedia によると、売買されているものらしい。しかし、このデータ自体は場合によっては個人を特定できてしまう。AOL は一時期、研究用途に限り、検索クエリのログデータを Web 上で公開していたが、個人が特定できることがわかり、裁判沙汰になったことがある。

ユーザーのクリックストリームデータは、ユーザー（顧客）の嗜好や行動パターンなどの分析に非常に意味があり、以下のようにも書かれている。StreamWeb プロジェクトでは、このクリックストリームをリアルタイムで即座に解析することによって、よりビジネスの差別化につながれる技術基盤を作れると良いだろう。

As discussed in Van den Poel & Buckinx (2005), clickstream analysis can be used to predict whether a customer is likely to purchase from an e-commerce website. Clickstream analysis can also be used to improve customer satisfaction with the website and with the company itself. Both of these uses generate a huge business advantage. It can also be used to assess the effectiveness of advertising on a web page or site

Control Theory (制御理論）の Shedding への応用

SEDA の論文にも語られているが、負荷への適応に制御理論を使う研究が存在する。Check this out later.

Load Shedding に関する既存研究

Load Shedding に関する論文をいくつか読んでいる。


Data Triage : An Adaptive Architecture for Load Shedding in TelegraphCQ, Frederic .et.al, ICDE 2005,

TelegraphCQ (UC Berkeley の DSMS システム) が対象にしているのは、Continuos Query で、SQL の拡張版のようなクエリ言語。たとえば、R, S, T というデータストリームがあるときに、以下のように JOIN クエリを記述することができる。
SELECT * FROM R, S, T WHERE R.a = S.b AND S.c = T.d
このクエリを、Load が Bursty な時に Drop するのではなく、データのサマリーを求めるように Query を書き換える規則を提案。

評価実験では、正解セットが与えられ、ロードを Bursty な状態にしたときに、提案する Data Triage (彼らの Load Shedding 技術）が、他の既存手法（単に Drop する方法、Summarize する方法）と比較して、エラー率が低いことを示している。特にどのドメインのデータか、実アプリケーションかは示していないところが少し弱い。

Utility-driven Load Shedding for XML Stream Processing, Mingzhu et.al, WWW 2008

WWWにもこの種の論文が載ったということで、非常に頼もしい。この論文は、データストリームが XML 形式の時の Load Shedding 手法を提案。RSS (Rich Site Summary) やセンサーデータのフォーマットは XML 形式が採用されていることが多いはずであり、実用性は高い。

　この論文では、XML データ全体を Random に Drop するのではなく、XML の構造上、重要な要素、重要でない要素を分類し (Utilityまたは Preferenceと呼び、ユーザが XQuery で指定する）、かつ、その要素を頂点とするサブツリーの処理にかかるクエリの処理を計算し、投資対効果 (ROI)を計算。ROI が低いものに関しては、処理をスキップするようにする。論文で取り上げられている例は、例えば、オンラインショッピングサイトの注文データ。注文データには、商品ID, 顧客ID、そして顧客のメールアドレス、顧客の詳細情報（住所、電話番号など）、コメント。これに対して、Bursty な状況では、とりあえず、顧客の詳細情報を含むような XML のサブツリーは処理せず、他の要素のみを処理する。

Load Shedding in a Data Stream Manager, Nesime Tatbul (Brown University), VLDB 2003 (PDF)

DSMS における Load Shedding を最初に提唱した論文。

Staying FIT: Efficient Load Shedding Techniques for Distributed Stream Processing, Nesim Tatbul (ETH Zurich), VLDB 2007

上記論文の同一筆者。既存の Shedding 技術はシングルノードを仮定しているが、この論文では複数ノードで DSMS が分散して稼動する場合を仮定。

ヒューリスティックスを用いた性能最適化

Zipf の法則というものを知っていますか？ 一般化したものは Power Law といいますが、様々な分野で起こる現象のヒューリスティックス（経験則）です。

Zipf のひとつのインスタンスに、パレートの法則や80:20 の法則というものがあります。たとえば、２割の顧客がその店の８割の売り上げに貢献している、などです。インターネットの検索キーワードにもこの法則が成り立つことがわかっていて、２割のキーワードが全体の８割に近くになります。

このようなヒュースリティックスは、パフォーマンスの最適化、たとえば、キャッシュのポリシーの設計方法などに大きく参考になります。たとえば、われわれは、データストリーム処理システムにおける性能最適化を研究していきますが、過負荷時に処理を間引く技術分野として Load Shedding といわれる分野があります。まだまだ発展途上の研究分野ですが、Power Law の経験則を用いた Load Shedding などは良い研究テーマになると思われます。