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 が分散して稼動する場合を仮定。