[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 に貯められているデータの更新をし、閾値以下であったら更新しない。このエラー閾値はアプリケーション毎に異なり、インターネットモニタリングよりも患者のモニタリングの場合の方が当然閾値がきつくなる。