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

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

機能原理

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

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

DSMS にとって最大の課題の 1 つは、固定量のメモリを使用し、データへのランダムアクセスなしで、潜在的に無限のデータストリームを処理することです。1 回のパスでのデータ量を制限するにはさまざまなアプローチがあり、2 つのクラスに分けることができます。1 つは、データを要約しようとする圧縮手法であり、もう 1 つは、データを (有限の) 部分に分割しようとするウィンドウ手法です。

あらすじ

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

ウィンドウズ

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

クエリ処理

プロトタイプが多数存在するため、標準化されたアーキテクチャはありません。ただし、ほとんどの DSMS は、宣言型言語を使用してクエリを表現し、演算子のプランに変換することで、DBMS のクエリ処理に基づいています。これらのプランは最適化して実行できます。クエリ処理は、多くの場合、次の手順で構成されます。

継続的クエリの作成

クエリの作成は、主にDBMS のSQLなどの宣言型言語を使用して行われます。継続的なクエリを表現するための標準化されたクエリ言語はないため、多くの言語とバリエーションがあります。ただし、それらのほとんどは、 Continuous Query Language (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 はデータ駆動型であるため、クエリは、入力データ要素をソースからクエリプランを介してシンクにプッシュすることによって実行されます。データ要素が演算子を通過するたびに、演算子はデータ要素に対して特定の操作を実行し、結果をすべての後続演算子に転送します。

例

AURORA、^[2] StreamBase Systems, Inc.
ホートンワークスデータフロー
IBM ストリーム
NIAGARAクエリエンジン^[3]
NiagaraST: ポートランド州立大学の研究データストリーム管理システム
Odysseus は、データストリーム管理システム用のオープンソース Javaベースのフレームワークです。
パイプラインDB
PIPES 2016年12月24日アーカイブWayback Machine、webMethods Business Events
Qストリーム
SAS イベントストリーム処理
SQLストリーム
ストリーム^[4]
ストリームグローブ
ストリームインサイト
テレグラフCQ ^[5]
WSO2 ストリームプロセッサ

参照

参考文献

^ 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 。
^ Abadi; et al. Aurora : データストリーム管理システム。SIGMOD 2003。CiteSeerX 10.1.1.67.8671。
^ Jianjun Chen、David J. DeWitt、Feng Tian、Yuan Wang (2000)。「NiagaraCQ: インターネットデータベース向けのスケーラブルな継続的クエリシステム」(PDF)。コンピューターサイエンス学部。ウィスコンシン大学マディソン校。SIGMOD。2018年11 月 21 日閲覧。
^ Arasu, A.、他著「STREAM: スタンフォードデータストリーム管理システム」。技術レポート。2004 年、Stanford InfoLab。
^ 「Chandrasekaran, S. et al, 「TelegraphCQ: 不確実な世界のための継続的なデータフロー処理」 CIDR 2003」(PDF) 。 2014年2月7日時点のオリジナル(PDF)からアーカイブ。 2011年8月26日閲覧。

Aggarwal, Charu C. (2007).データストリーム: モデルとアルゴリズム. ニューヨーク: Springer. ISBN 978-0-387-47534-9。
Golab, Lukasz; Özsu, M. Tamer (2010).データストリーム管理. ウォータールー、米国: Morgan and Claypool. ISBN 978-1-608-45272-9。

外部リンク

情報フローの処理: データストリームから複合イベント処理まで - データストリームと複合イベント処理システムに関する調査記事
SQL によるストリーム処理 - SQL によるストリーミングデータ管理の概要

[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 。

[aurora-2] Abadi; et al. Aurora : データストリーム管理システム。SIGMOD 2003。CiteSeerX 10.1.1.67.8671。

[niagaracq-3] Jianjun Chen、David J. DeWitt、Feng Tian、Yuan Wang (2000)。「NiagaraCQ: インターネットデータベース向けのスケーラブルな継続的クエリシステム」(PDF)。コンピューターサイエンス学部。ウィスコンシン大学マディソン校。SIGMOD。2018年11 月 21 日閲覧。

[StandfordStream-4] Arasu, A.、他著「STREAM: スタンフォードデータストリーム管理システム」。技術レポート。2004 年、Stanford InfoLab。

[telegraphcq-5] 「Chandrasekaran, S. et al, 「TelegraphCQ: 不確実な世界のための継続的なデータフロー処理」 CIDR 2003」(PDF) 。 2014年2月7日時点のオリジナル(PDF)からアーカイブ。 2011年8月26日閲覧。