Load Shedding

最近、DSMS (Data Stream Management System、つまりストリームコンピューティングのこと) における Load Shedding 技術に注目していて、論文を読んだり、新たな手法を模索している。

Load Shedding で重要なのは、システムのキャパシティぎりぎりにロードを如何に保てるかと、間引いた後に出力の品質を如何に下げないかだ。大きく分けて２つ手法があるが、確率的にランダムに、入力タプルを落とす (Random Dropという) やり方と、データやアプリケーションの特性を生かした (Semantic Dropという）やり方がある。

いくつか論文を読んでいて 思いついたアイデアを列挙する。

(1) Semantic Load Shedding for Internet Search Queries
検索クエリの特性 (Zipf 法則)を生かした Semantic Load Shedding

(2) Compensating Load Shedded Data with Eventual Consistency
Load Shedding は基本的に間引いたものは捨てるのが普通。捨てないで、Bursty ではない状況の時に、あとから処理をするという手法もありなのではなかろうか。アプリケーションに依存するだろうが。。。分散システムの世界において、データの複製間の一貫性として Strong Consistency（常に２つの複製データの一貫性は保たれている）, Weak Consistency（一貫性が保たれていないこともある） そして、Eventual Constitency （最終的には保たれている）の3つがある。Load Shedding においても、この最後の Eventual Consistency の考え方が適応できそうだ。

(3) Efficient Load Shedding with GPU
GPU を用いた Load Shedding. これは Load Shedding というよりは Load Balancing に近い。非常に Bursty な状況では, CPU 処理ではなく GPU に処理をまかせる

(4) Load Shedding with Differential XML Processing
XML データの処理。Load Shedding に差分XML処理の技術を生かす. (WWW 2005 などの論文を参考にする)