データストリーム管理システム

データストリーム管理システム(DSMS) は、連続的なデータ ストリームを管理するコンピュータソフトウェア システムです。これはデータベース管理システム(DBMS) に似ていますが、DBMS は従来のデータベースの静的データ用に設計されています。DBMS では柔軟なクエリ処理も提供されるため、必要な情報をクエリを使用して表現できます。ただし、DBMS とは異なり、DSMS は、一度だけ実行されるのではなく、永続的にインストールされる継続的なクエリを実行します。したがって、クエリは明示的にアンインストールされるまで継続的に実行されます。ほとんどの DSMS はデータ駆動型であるため、新しいデータがシステムに到着する限り、継続的なクエリでは新しい結果が生成されます。この基本概念は複合イベント処理に似ており、両方のテクノロジは部分的に融合しています。

機能原理

DSMSの重要な特徴の一つは、メインメモリなどの限られたリソースしか利用できない状況でも、柔軟な処理を提供することで、潜在的に無限かつ急速に変化するデータストリームを処理できることです。次の表は、DSMSの様々な原理と、従来のDBMSとの比較を示しています。

データベース管理システム（DBMS） データ ストリーム管理システム (DSMS)
永続データ（リレーション） 揮発性データストリーム
ランダムアクセス シーケンシャルアクセス
1回限りのクエリ 継続的なクエリ
（理論上）無制限の二次ストレージ 限られたメインメモリ
現在の状態のみが関係する 入力順序の考慮
比較的低い更新率 潜在的に非常に高い更新レート
時間の制約はほとんどない リアルタイム要件
正確なデータを想定 古くて不正確なデータを想定
計画可能なクエリ処理 可変データ到着とデータ特性

処理およびストリーミングモデル

DSMSにとって最大の課題の一つは、固定量のメモリを使用し、データへのランダムアクセスを一切行わない状況で、潜在的に無限のデータストリームを処理することです。1回のパスで処理するデータ量を制限する方法はいくつかあり、大きく分けて2つの種類があります。一つは、データを要約する圧縮技術、もう一つは、データを（有限の）部分に分割するウィンドウ技術です。

あらすじ

圧縮技術の背後にある考え方は、データストリームの（生の）データポイントすべてではなく、データの概要のみを保持することです。アルゴリズムは、サンプリングと呼ばれるランダムなデータポイントの選択から、ヒストグラム、ウェーブレット、スケッチを用いた要約まで多岐にわたります。圧縮の簡単な例の一つは、平均の連続計算です。各データポイントを記憶する代わりに、概要には合計と項目数のみが保持されます。平均は、合計を項目数で割ることで計算できます。ただし、概要はデータを正確に反映することはできないことに注意してください。したがって、概要に基づく処理は不正確な結果を生成する可能性があります。

ウィンドウズ

ウィンドウ技術は、データストリーム全体の特性を圧縮するためにシノプシスを使用する代わりに、データの一部のみを対象とします。このアプローチは、最新のデータのみが関連するという考えに基づいています。したがって、ウィンドウはデータストリームの一部、例えば最後の10個のデータストリーム要素を継続的に切り出し、処理中にこれらの要素のみを考慮します。このようなウィンドウには、FIFOリストに似たスライディングウィンドウや、ばらばらの部分を切り出すタンブリングウィンドウなど、様々な種類があります。さらに、ウィンドウは、例えば最後の10個の要素を考慮する要素ベースのウィンドウや、例えば最後の10秒間のデータを考慮する時間ベースのウィンドウに分類することもできます。ウィンドウの実装方法も様々です。例えば、システム全体のウィンドウにタイムスタンプや時間間隔を使用する方法や、各処理ステップにバッファベースのウィンドウを使用する方法などがあります。スライディングウィンドウによるクエリ処理は、異なるウィンドウ間および／または各ウィンドウ範囲内の並列性を活用することで、並列プロセッサに実装するのに適しています。[ 1 ]

クエリ処理

プロトタイプが多数存在するため、標準化されたアーキテクチャは存在しません。しかし、ほとんどのDSMSはDBMSのクエリ処理をベースとしており、宣言型言語を用いてクエリを表現し、演算子のプランに変換します。これらのプランは最適化され、実行されます。クエリ処理は通常、以下のステップで構成されます。

継続的なクエリの作成

DBMSでは、クエリの作成は主にSQLなどの宣言型言語を用いて行われます。継続的クエリを表現するための標準化されたクエリ言語は存在しないため、多くの言語とそのバリエーションが存在します。しかし、それらのほとんどは、継続的クエリ言語（CQL）、StreamSQL、ESPなど、 SQLに基づいています。また、各処理ステップをボックスとして扱い、処理フローをボックス間の矢印で表現するグラフィカルなアプローチもあります。

言語は処理モデルに大きく依存します。例えば、処理にウィンドウを使用する場合、ウィンドウの定義を明示的に記述する必要があります。StreamSQLでは、最後の10要素をスライディングウィンドウとして扱うクエリは次のようになります。 

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

このストリームは、最後の 10 個のタプルの「価格」の平均値を継続的に計算しますが、価格が 100.0 を超えるタプルのみを考慮します。

次のステップでは、宣言型クエリが論理クエリプランに変換されます。クエリプランは有向グラフであり、ノードは演算子、エッジは処理フローを記述します。クエリプラン内の各演算子は、フィルタリングや集計などの特定の操作のセマンティクスをカプセル化します。リレーショナルデータストリームを処理するDSMSでは、演算子はリレーショナル代数の演算子と同等または類似しており、選択、射影、結合、集合演算などの演算子が存在します。この演算子の概念により、DSMSは非常に柔軟で多用途な処理が可能になります。

クエリの最適化

論理クエリプランは最適化可能ですが、これはストリーミングモデルに大きく依存します。継続的クエリを最適化するための基本的な概念は、データベースシステムのものと同じです。リレーショナルデータストリームがあり、論理クエリプランがリレーショナル代数のリレーショナル演算子に基づいている場合、クエリオプティマイザは代数的同値性を用いてプランを最適化できます。例えば、選択演算子は結合演算子ほど計算負荷が高くないため、ソースにプッシュダウンすることが考えられます。

さらに、DBMS のようなコストベースの最適化手法もあり、複数の同等のクエリ プランからコストが最も低いクエリ プランが選択されます。1 つの例は、連続する 2 つの結合演算子の順序を選択することです。DBMS では、この決定は主に関係するデータベースの特定の統計によって行われます。しかし、データ ストリームのデータは事前​​に不明であるため、DSMS にはそのような統計はありません。ただし、データ ストリームを一定時間観察して何らかの統計を取得することは可能です。これらの統計を使用して、後でクエリを最適化することもできます。そのため、DBMS とは対照的に、一部の DSMS では実行中でもクエリを最適化できます。したがって、DSMS では、実行中のクエリ プランを新しいものに置き換えるために、いくつかのプラン移行戦略が必要です。

クエリの変換

論理演算子は操作のセマンティクスのみを担当し、アルゴリズムは含まれていないため、論理クエリプランは実行可能なものに変換する必要があります。これは物理クエリプランと呼ばれます。論理演算子プランと物理演算子プランを区別することで、同じ論理演算子を複数の実装で実行できます。例えば、結合は論理的には同じですが、ネストループ結合やソートマージ結合などの異なるアルゴリズムで実装できます。これらのアルゴリズムは、使用されるストリームと処理モデルに大きく依存することに注意してください。最終的に、クエリは物理クエリプランとして利用可能になります。

クエリの実行

物理クエリプランは実行可能なアルゴリズムで構成されているため、直接実行できます。このため、物理クエリプランはシステムにインストールされます。クエリプランのグラフの下部は、入力ソース（センサーへのコネクタなど）に接続されます。グラフの上部は、出力シンク（視覚化など）に接続されます。ほとんどのDSMSはデータ駆動型であるため、クエリは、入力データ要素をソースからクエリプランを介してシンクにプッシュすることによって実行されます。データ要素が演算子を通過するたびに、演算子はデータ要素に対して特定の操作を実行し、その結果をすべての後続演算子に転送します。

例

参照

参考文献

  1. ^ De Matteis, Tiziano; Mencagli, Gabriele (2016年3月25日). 「データストリームにおけるウィンドウベースのステートフル演算子のための並列パターン：アルゴリズム的スケルトンアプローチ」 . International Journal of Parallel Programming . 45 (2): 382– 401. doi : 10.1007/s10766-016-0413-x . S2CID  255600 .
  2. ^ Abadi; et al. Aurora: データストリーム管理システム. SIGMOD 2003. CiteSeerX 10.1.1.67.8671 . 
  3. ^ Jianjun Chen、David J. DeWitt、Feng Tian、Yuan Wang (2000). 「NiagaraCQ: インターネットデータベース向けのスケーラブルな継続的クエリシステム」(PDF) . コンピュータサイエンス学部.ウィスコンシン大学マディソン校. SIGMOD . 2018年11月21日閲覧。
  4. ^ Arasu, A., et al. STREAM: スタンフォードデータストリーム管理システム。 技術レポート。2004年、Stanford InfoLab。
  5. ^ 「Chandrasekaran, S. et al, "TelegraphCQ: Continuous Dataflow Processing for an Uncertain World." CIDR 2003」(PDF) 。 2014年2月7日時点のオリジナル(PDF)からアーカイブ。 2011年8月26日閲覧。
  • アガーワル、チャル・C. (2007). 『データストリーム：モデルとアルゴリズム』 ニューヨーク: シュプリンガー. ISBN 978-0-387-47534-9。
  • Golab, Lukasz; Özsu, M. Tamer (2010). 『データストリーム管理』 ウォータールー、アメリカ合衆国: Morgan and Claypool. ISBN 978-1-608-45272-9。
「 https://en.wikipedia.org/w/index.php?title=Data_stream_management_system&oldid=1320617581」より取得