データストリーム処理アーキテクチャ(DSMS)

データストリーム処理アーキテクチャ(DSMS)

データストリーム管理システム(Data Stream Management System:DSMS)は、連続したデータの流れを管理するコンピュータプログラムとなる。DSMSはデーベース管理システム(DBMS)と似ているが、DBMSが通常のデータベースに格納された静的なデータを扱うのに対して、DSMSはクエリを1度だけ実行するのではなく、インストールされている限り連続的に永久に実行し続ける形態となる。ほとんどのDSMSはデータ駆動型なので、システムにデータが取り込まれる限り、連続的なクエリは新たな結果を生成し続けることになる。

DSMSでの大きな課題は、決められた量のメモリとデータへのランダムアクセスなしで、潜在的に無限量のデータストリームを処理することである。1回のパスで取り込むデータを制限する手法にはいくつかあり、大きく二つの種類に分けることができる。一つにはデータをサマライズしようとする圧縮技術があり、もう一つにはデータを（有限な）部分に分割しようとするウィンドウ技術がある。

圧縮技術の背景にある考え方は、データストリームの全ての（生）データポイントではなく、データの概略だけを保つというものである。アルゴリズムとしてはランダムにデータポイントを選択するサンプリング手法から、ヒストグラムやウェーブレット、スケッチングなどの手法を用いるものまである。一つの単純な圧縮技術の例としては連続的に平均を計算するというものがある。サマリーはデータを正確に反映するものではないので、不正確な結果をもたらす可能性がある。

ウィンドウ技術では、データの概略を使用して全てのデータストリームの特徴を圧縮するのではなく、データの一部分だけを扱う。ているという考え方に基づいている。ウィンドウによりデータストリームは連続的に切り出される。例えば最後のデータ要素を10個だけ取り出し、処理にはそれらだけを考慮する。ウィンドウには他にFIFOリストに似たスライディングウィンドや、直近の10秒のデータだけを考慮するような時間ベースのウィンドウなどがある。

クエリには、たくさんのプロトタイプがあり、標準となるアーキテクチャはない。しかし、ほとんどのDSMSはDBMSのクエリ処理を基にしたクエリ記述をしており、それは演算子の計画に変換される。これらの計画は最適化することができ実行される。

クエリの式はDBMSにおけるSQLのような宣言的言語を使用して実行される。連続的クエリを表現する式にはまだ標準が存在しないので、多くの言語とその派生形が存在する。しかし、 Continuous Query Language (CQL), StreamSQL or EPLなどはSQLを基にしている。他には処理ステップを箱で表現し箱を矢印で接続して流れを表現するグラフィカルなアプローチも存在する。

言語は処理モデルに強く依存する。たとえば、処理にウィンドウを使用するならウィンドウの定義が式に必要である。StreamSQLでは直近10個の要素に対するスライディングウィンドウへのクエリは下記のようになる。

SELECT AVG(price) FROM examplestream [SIZE 10 ADVANCE 1 TUPLES] WHERE value > 100.0

このようにして作成された宣言的なクエリは論理的クエリ計画に変換される。クエリ計画は有向グラフでありノードが演算子でエッジが処理フローを表現する。クエリ計画にある個々の演算子はフィルタリングや集計などの特定の処理に関する意味をカプセル化する。DSMSではリレーショナルデータストリームの処理を行い、演算子は関係代数の処理そのものであるか似たものであり、選択、射影、結合、セットなどの処理がある。この演算子の概念はDSMSによる処理の柔軟性と網羅性を実現する。

論理演算子は処理の意味にだけかかわり、何のアルゴリズムも含んでいないので、論理クエリ計画は対応する実行形式に変換されなければならない。これを物理クエリ計画と言う。論理演算子と物理演算子を区別することにより、一つの論理演算子に複数の実装を行うことができる。例えば結合では入れ子ループ結合やソートマージ結合などのアルゴリズムを実装することができる。これらのアルゴリズムは使用するストリームと処理モデルに強く依存する。最後に、クエリは物理クエリ計画として使用できるようになる。

物理クエリ計画には実行可能なアルゴリズムが含まれるので直接実行することができる。このために物理クエリ計画はシステムにインストールされる。（クエリ計画の）グラフの底はコネクターからセンサまで全ての入力されるソースに接続されている。グラフの頂上はデータの視覚化などの出力シンクに接続されている。ほとんどのDSMSはデータ駆動型なので、ソースからの入力されてくるデータソースをクエリ計画からシンクに押し出すことでクエリが実行される。データ要素が演算子を通過するたびに、演算子はデータ要素に対して特定の演算を実行し、結果を全ての後続する演算子に渡す。

DSMSはStanford大Info-labにて研究されたものが始まりで、Coral8 (2005〜)、StreamBase (2003〜)、Esper (2006〜)等の商用システムが提供されている。