Distributed data stream processing and edge computing A survey on resource elasticity and future directions

• 参考
• メモ
  • 1. Introduction
  • 2. Background and architecture
    • 2.1. Online data processing architecture
    • 2.2. Data streams and models
    • 2.3. Distributed data stream processing
    • 2.4. Resource elasticity
  • 3. Stream processing engines and tools
    • 3.1. Early stream processing solutions
    • 3.2. Current stream processing solutions
  • 4. Managed cloud systems
    • 4.1. Amazon Web Services (AWS) Kinesis
    • 4.2. Google dataflow
    • 4.3. Azure stream analytics
  • 5. Elasticity in stream processing systems
    • 5.1. Static techniques
    • 5.2. Online techniques
    • 5.3. Change and burst detection
  • 6. Distributed and hybrid architecture
    • 6.1. Lightweight virtualisation and containers
    • 6.2. Application placement and reconfiguration
  • 7. Future directions
    • 7.1. SDN and in-transit processing
    • 7.2. Programming models for hybrid and highly distributed architecture

参考

• Distributed data stream processing and edge computing: A survey on resource elasticity and future directions
• ウェーブレットと多重解像度処理
• 乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－
• Apache Edgent
• Twitter Heron論文

メモ

Twitter Heronの論文を引用しているということでピックアップしてみた。

故障耐性を持ち、分散処理を実現するストリーム処理エンジンでは、処理の表現としてDAG構造を用いるものが多い印象。 一方で、宣言的なハイレベルのAPI（SQLなど）を提供するのは少数か？ （かつて、分散処理ではなかったり、故障耐性を持たなかったりした時代では、CQLが台頭していたが…）

全体的に、リソースアロケーションに関する研究では、Apache Stormのカスタムスケジューラとして実装して見せる論文が多く感じられた。 ただしエッジコンピューティングの前に、そもそもストリーム処理における弾力性（柔軟で安定したスケールアウト・イン）の実現自体がまだ枯れていない印象。

以下、一応、主観的に重要そうな個所に★マークを付与。

1. Introduction

大量のデータが生まれ始めた。 以下のような項目が要因の例として挙げられる。

• 計器化されたビジネス・プロセス
• ユーザアクティビティ
• ウェアラブルアシスタンス
• ウェブサイトトラッキング
• センサー
• 金融
• 会計
• 科学計算

ユースケースとしては、IoTなどが挙げられていた。 興味深い例としては以下。

Rettig, L., Khayati, M., Cudré-Mauroux, P., Piórkowski, M., 2015. Online anomaly
detection over big data streams. In: IEEE International Conference on Big Data (Big
Data 2015), IEEE, Santa Clara, USA, pp. 11131122

多くのツールがデータフローアプローチを取る。 つまりオペレータの有向グラフに変換して処理する。

一方でストリームデータを一定量ためてマイクロバッチするアプローチを取るツールもある。 スケーラビリティと故障耐性を狙った工夫である。

補足：これはSpark Streamingのことを意識した記述だと理解

さらにクラウド上での実行を想定したアプローチが登場。 ★ これにより、弾力性実現を狙う。

Google Dataflow (2015)の論文が引用されていた。 異なる実行モデルが混在しているケースを扱う技術として。

Apache Edgent, https://edgent.apache.org 2017. はインターネットのエッジで動作することを想定したフレームワークである。

過去の調査として、弾力性に注力していないものもあった。

Zhao, X., Garg, S., Queiroz, C., Buyya, R., 2017. Software Architecture for Big Data and
the Cloud, Elsevier  Morgan Kaufmann. Ch. A Taxonomy and Survey of Stream
Processing Systems.

本論文は以下の構成。

• 2章
  • ビッグデータエコシステム。オンラインデータ処理のアーキテクチャ。
• 3章
  • 既存のエンジン。ストリームデータ処理の他のソリューション
• 4章
  • マネージドクラウドソリューション
• 5章
  • 既存の技術がどのようにリソースの弾力性を実現しようとしているのか
• 6章
  • 複数のインフラストラクチャを組み合わせる
• 7章
  • 将来の話

2. Background and architecture

2.1. Online data processing architecture

ここでは「オンライン」という単語を用いているが、以下のように定義して用いている。

Similar to Boykin et al., hereafter use the term online to mean that “data are
processed as they are being generated”.

Fig. 1にストリーム処理アーキテクチャの典型的なコンポーネント関係図がある。（補足：当たり前の内容ではあるが参考になると思う）

コンポーネント関係図

補足：ストレージとの関係性はもう少し深堀りしてもよさそう。最近だとDatabricks DeltaやApache Hudiのようなストレージレイヤのミドルウェアが生まれているため。 ★

まず「データソース」ではデータを送り出す（ローダ）、データフォーマット、MQTTのようなプロトコルに関する議論がある。 たいてい、送り出す機能はネットワークのエッジ側に置かれる。

コンポーネントそれぞれが独立して成長できるよう、MQ（ActiveMQ、RabbitMQ、Kestrel）、Pub/Subベースのソリューション（Kafka、DistributedLog）、 あるいはマネージドサービス（Amazon Kinesis Firehose、Azure IoT Hub）が挟まれることが多い。

補足：http://bookkeeper.apache.org/distributedlog/

補足：DistributedLogは2017年にBookKeeperのサブプロジェクト化された。 https://bookkeeper.apache.org/docs/latest/api/distributedlog-api/

大規模データを扱うための技術の代表例として、MapReduceが挙げられていた。

Dean, J., Ghemawat, S. MapReduce: Simplified data processing on large clusters.
Communications of the ACM 51 (1).

本論文で扱う技術は、ストリーム管理システムだったり、CEPと呼ばれる。

補足：ここではストリーム処理とCEPは分けて言及していないようだ。

ストリーム処理のアーキテクチャはデータストレージ機能を内包することがある。 目的は、さらなる処理のためだったり、結果を分析者等に渡すためだったりする。 ★ このとき用いられるストレージは、RDBMS、KVS、インメモリデータベース、NoSQLなどなど。パブリッククラウドにもいろいろな選択肢がある。

補足：ステート管理用のストレージを持つ場合もあるだろう。 ★

2.2. Data streams and models

「データストリーム」の定義は様々。 不連続の信号、イベントログ、モニタリング情報、時系列データ、ビデオ、などなど。

2005年くらいの調査では、時系列データ、キャッシュレジスタ、回転扉あたりのデータモデルが対象だった。 一方最近ではSNS等から生じる非構造データ、準構造データが見受けられる。 データ構造としては、キー・バリュー形式を挙げており、キーがタイムスタンプである。

多くのケースで、ストリーム処理はオペレータのDAG構造を抽象化として用いる。 ★ 論理プランと物理プラン。 物理プラン側で並列度などを含め、クラスタのリソースにオペレータを割り当てることになる。

オペレータは選択性、ステートの軸でカテゴライズできる。

並列度に関するカテゴリもある。

■並列度のカテゴリ

• パイプライン並列
  • アップストリームのオペレータは並列でタプルを処理できる
• タスク並列
  • グラフの中には同じタプルを並列で処理できる箇所がある
• データ並列
  • スプリッタでデータを分割し、マージャで処理されたデータを結合する

気になった論文

Gedik, B., Özsema, H., Öztürk, O., 2016. Pipelined fission for stream programs with
dynamic selectivity and partitioned state. J. Parallel Distrib. Comput. 96, 106120.
http://dx.doi.org/10.1016/j.jpdc.2016.05.003.

2.3. Distributed data stream processing

DBMSと対比し、DSMS（Data Stream Management System）と呼ぶことがある。 ★ DSMSは以下のようなオペレータを持つ。

• join
• aggregation
• filter
• その他分析用の機能

初期のDSMSはSQLライクなインターフェースを提供していた。

CEPはイベント間の関係を明らかにする、などの用途に用いられた。

補足：ここからストリーム処理エンジンの世代説明。一般的な説明をするときに使えそう。 ★

第1世代は、DBMSの拡張として用いられ、単一マシンで実行することを想定していた。（分散処理を考慮していなかった）

第2世代は、分散処理対応 ここでIBM System Sの登場。ゴールはスケーラビリティと効率の改善。

最近（第3世代）では、スケーラブルで故障耐性のある実行を目指している。 ただし、この手の技術は宣言的なインターフェースを持たず、ユーザがアプリケーションを書く必要がある。 UDFを用いることができる。

入力データを離散化（小さなバッチに区切り）し、マイクロバッチ処理を実行するものもあった。

ある程度まとめこまれたデータに対し、繰り返し処理を実行するものもある。 目的はスループット向上。ただし、低レイテンシの要求が厳しくない場合を対象とする。

第4世代は、エッジコンピューティングを含む。 この手の技術として挙げられていたのは以下の通り。

Sajjad, H.P., Danniswara, K., Al-Shishtawy, A., Vlassov, V., 2016. SpanEdge: Towards
unifying stream processing over central and near-the-edge data centers. In: IEEE/
ACM Symposium on Edge Computing (SEC), pp. 168178.

SPEとして。

Chan, S., 2016. Apache quarks, watson, and streaming analytics: Saving the world, one
smart sprinkler at a time. Bluemix Blog (June).URL 〈https://www.ibm.com/blogs/
bluemix/2016/06/better-analytics-with-apache-quarks/〉

Pisani, F., Brunetta, J.R., do Rosario, V.M., Borin, E., 2017. Beyond the fog: Bringing
cross-platform code execution to constrained iot devices. In: Proceedings of the 29th
International Symposium on Computer Architecture and High Performance
Computing (SBAC-PAD 2017), Campinas, Brazil, pp. 1724.

クラウドとエッジ。

Hirzel, M., Schneider, S., Gedik, B., An, S.P.L., 2017. extensible language for distributed
stream processing. ACM Trans. Program. Lang. Syst. 39 (1), 5:15:39. http://
dx.doi.org/10.1145/3039207, (URL 〈http://doi.acm.org/10.1145/3039207〉).

2.4. Resource elasticity

クラウドの特徴の一つは、支払えばリソースを使えること。

もうひとつはリソース弾力性である。★ オートスケーリングも可能とする。

オートスケーリングに対応するには、スケールイン・アウトしたリソースに対応する仕組みも必要だが、 オートスケーリングのポリシーも必要。

オートスケーリングの仕組みは、主にバッチ処理についてビッグデータのワークロードに関し、 いくつか提案手法が存在する。★

補足：クラウドベースのオートスケーリングについて以下の論文で触れられているらしい。

Tolosana-Calasanz, R., çngel Ba-ares, J., Pham, C., Rana, O.F., 2016. Resource
management for bursty streams on multi-tenancy cloud environments. Future
Gener. Comput. Syst. 55, 444459. http://dx.doi.org/10.1016/j.future.2015.03.012.

ここでのポイントは、「シビアな遅延があること」。 特にSPEでは、バッチ処理と比べてスケールイン・アウトの要件が厳しい。 例えば、処理を動かし続けるから、データロストしないでスケールイン・アウトさせるのが難しいし、 スケールイン・アウト後のオペレータの再配置が難しい。

補足：つまりバッチ処理におけるスケールアウト・インはある程度実現性があるが、ストリーム処理のスケールアウト・インはまだまだ研究段階？であると言えるのか ★

3. Stream processing engines and tools

SPEの歴史を振り返る。

3.1. Early stream processing solutions

DBMSの拡張として登場。 2000年代。

ただし近年の技術と比べて、大規模データを対象としていない。

NiagaraCQ

2000年。 XMLデータに対し、定期的に繰り返し処理を実行する。

STREAM

2004年。 CQL。Continuous Query Lang.

CQLをクエリプランにコンパイルする。 DAG構造で処理を表す。

実行時には、スケジューラがオペレータをリソースに割り当てる。

チェーンスケジューリングを用いる。

補足：このあたりではUDFについて言及されていない。

Aurora

モニタリングアプリケーション向け。

STREAMと同様に、CQSを利用可能。

トレインスケジューリングを採用。 非直線性。 入力タプルをボックスに集め、それに対し処理を実行する。これによりI/Oオペレーションを減らす。

Medusa

MedusaはAuroraをクエリ処理エンジンとして使いながら、分散処理対応させた。

UDFには対応していない。

3.2. Current stream processing solutions

2種類にわけられる。

• オペレータグラフに基づきタプル単位で処理する（補足：こっちがいわゆるコンティニュアス・ストリーム処理）
• 入力データをある程度の塊に区切り、マイクロバッチ処理として処理する（補足：こっちがいわゆるマイクロバッチ処理によるストリーム処理）

3.2.1. Apache Storm

アプリケーションはTopologyと呼ばれる。 データはチャンクとして取り込まれ、タスクを割り当てられたノードで処理される。 データはタプル群として扱われる。

Nimbusがマスタ機能であり、ZooKeeperと連携しながら、 タスクをスケジューリングする。

WorkerノードにはSupervisorがいて、（複数の）Workerプロセスを管理する。 Workerプロセス内では（複数の）Executorスレッドが起動され、SpoutかBoltの機能を実行する。

Spoutがデータソースからデータを取得し、Boltがタプルを処理する。

フィルタ、アグリゲーション、ジョイン、データベースクエリ、UDFなどを実行する。

並列度を制御するには、Topologyごとに各コンポーネントの並列度、 Executor数を指定する。

Workerノードを追加した際、新しいTopologyをローンチ可能。 また、Workerプロセス数やExecutorスレッド数を変更可能。

一方で、タスク数などを変更するときには、一度Topologyを止める必要がある。 ★ 特にステートを持つオペレータを用いているときは問題が複雑。

性能チューニングは、Executorの入出力キューの長さ、Workerプロセスのキューの長さを変更することで可能。

またTridentを用いたマイクロバッチ処理が可能になっているし、Summingbirdのような 抽象化層が生まれている。

3.2.2. Twitter heron

2015年の論文。

Stormの当時の欠点をいくつも改善しつつAPI互換性を実現した。

補足：なお、現在のApache Storm実装では、Heron論文で挙げられていた課題が多数解決されている。

Topologyはプロセスベースであり、デバッグしやすいさなどを重視。 ★

バックプレッシャ機能も有する。

Stormと同様にアプリケーションがDAGのTopologyで表現され、SpoutとBoltも存在。

各種コンテナサービスと連携する。 Aurora on Mesos、YARN、ECS。

Topologyがローンチされると、Topologyマスタ（TM）と複数のコンテナが立ち上がる。 ZooKeeperを用いてTMが単一であることを保証し、ほかのコンポーネントからTMを発見できるようにする。 TMはゲートウェイ機能にもなるし、スタンバイTMを用いることも可能。

各コンテナは、Heronインスタンス（HI）群、ストリームマネージャ（SM）、メトリクスマネージャ（MM）を起動する。 コンテナ間でSM同士がフルメッシュのNWを構成する。

Spout、BoltはHIが担うことになるが、HI自体はJVMである。これはStormと異なる点である。★ またHIは2スレッドで構成される。 1個目スレッドはユーザ定義の処理内容を実行し、2個目スレッドはほかのコンポーネントととの連絡を担う。

Heronトラッカ（HT)はTopology群の情報を得るための、クラスタ単位のゲートウェイである。

補足：詳しくは、 Twitter Heron論文 を参照。

3.2.3. Apache S4

2010年。

並列処理の管理にアクターモデルを用いる。 ★

プロセッシングエレメント（PE）がイベント交換と処理を担う。

分散型で、シンメトリックなアーキテクチャを採用。 プロセッシングノード（PN）は機能性に関し同一。 ZooKeeperがPNのコーディネーションのために用いられる。

アプリ開発者は、PEの処理内容を定義しないとならないが、 その際キーに基づく処理を作りこむことが多い。（キーのハッシュに基づく処理の割り当て） ほかにキーを用いないPEは、例えば入力データを扱うPEである。

3.2.4. Apache samza

2017年。

Apache Kafkaをメッセージング、YARNをデプロイメント、リソース管理、セキュリティ機能のために用いる。

データフローを定義して用いるが、コンシューマを定義する。 ネイティブではDAG構造による処理の定義に対応していない。 ★

Heronと同じくシングルスレッドモデル。

各コンテナはローカルのステート管理用のKVSを持つ。 KVSはほかのマシンに転送される。これにより故障耐性を有する。

3.2.5. Apache flink

2015年。

DAG型のデータフローを定義する。 「ストリーム」は中間結果で、「トランスフォーメーション」が複数のストリームを入力とし、複数のストリームを出力とする。

並列度はストリームとオペレータの並列度に依存する。 ストリームはパーテイションに分割され、オペレータはサブタスクに分割される。 サブタスクは異なるスレッドに割り当てられる。

ジョブマスタ（JM）とタスクマネージャ（TM）。 JMがタスクのスケジューリング、チェックポイントなどに責任を持つ。 TMがサブタスクを実行する。

ワーカはJVMであり、サブタスクごとの独立したスレッドを実行する。 ★

スロットの概念があり、Stormと異なりメモリ管理機能を有する。 ★

3.2.6. Spark streaming

2012年。

イミュータブルなデータセットの抽象表現であるResilient Distributed Datasets (RDDs) のDAGでアプリケーションを表現。 故障耐性向上のため、RDDのリネージを利用。

トラディショナルなストリーム処理エンジンでは、タプルの継続的な処理を担うオペレータのグラフによるモデルを採用しており、 故障耐性を担保するのが難しい。 そのようなエンジンでは、セクションのレプリケーション、もしくはアップストリームでのバックアップで実現する。

Spark Streamingでは故障耐性を実現するのに際し、RDDを使ったマイクロバッチ処理をベースとし、 RDDの故障耐性を利用することとした。

3.2.7. Other solutions

System S（IBM Streams）はオペレータのDAGをアプリケーション構造に採用。 ★ 構造化、非構造化データの両方に対応。 SPL（ストリーム処理言語）に対応。 ストリーム処理コア（SPC）を有効活用するようSPLのコンパイルと最適化も実施する。

SPLについては以下の論文が気になる。

Hirzel, M., Schneider, S., Gedik, B., An, S.P.L., 2017. extensible language for distributed
stream processing. ACM Trans. Program. Lang. Syst. 39 (1), 5:1–5:39. http://
dx.doi.org/10.1145/3039207, (URL： http://doi.acm.org/10.1145/3039207 ).

ESC（以下の論文参照）もオペレータを中心としたDAGによるアプリケーション表現を採用。 並列処理の管理にはアクタモデルを採用。 ★

Satzger, B., Hummer, W., Leitner, P., Dustdar, S., 2011. Esc: Towards an elastic stream
computing platform for the cloud. In: IEEE International Conference on Cloud
Computing (CLOUD), pp. 348–355.

TimeStream（2013）もDAGによるアプリケーション表現を採用。

GoogleのMillWheel。2013年。 こちらもデータ変換等のグラフを抽象化してアプリケーションを作成する。 ホストの動的なセット上で動作することを想定しており、 リソース使用状況に応じて処理単位を分割する、などの挙動をとる。

Efficient Lightweight Flexible （ELF） ストリーム処理システム（2014年）は 非中央集権的アーキテクチャを採用。 各マシンがそれぞれウェブサーバからデータを取得し、それぞれがバッファツリーにデータを保持する。 各マシンで処理されたデータは、オーバレイ構成のDHTを用いて、Reduce処理される。

4. Managed cloud systems

4.1. Amazon Web Services (AWS) Kinesis

ファイアホースを使うと、RedshiftやS3等に対し、ストリームデータを格納できる。 ★ ファイアホースはバッファリングを行う。

CloudWatchと連携すると、各サービスのメトリクスを集められる。

Amazon Kinesis Streamsはストリーム処理の仕組み。 ストリームデータはシャードに分けられて分散処理される。 シャードには固定のキャパシティが存在する。 単位時間あたりのオペレーション数やデータサイズである。

4.2. Google dataflow

プログラミングモデルであり、マネージドサービスである。 ETLなどを含むバッチ処理とストリーム処理の両方を対象とする。 ★

ステップや変換を有向グラフにしたもので処理を定義する。 「PCollection」が入出力データの抽象表現である。 PCollectionには固定サイズのデータ、もしくはストリームデータをタイムスタンプで区切ったものが与えられる。 トリガを用いていつ出力するかを制御する。

SDKもある。Apache Beamプロジェクト配下でリリースされている。

Dataflowサービスは、ジョブを実行するためにGCE、GCSを管理する。

オートスケールや動的なリバランス機能を使って、オンザフライでリソースアロケーションを調整できる。 （論文当時）バッチ処理のオートスケールはリリースされていたが、ストリーム処理のオートスケールは実験段階だった。

補足：ステートフルなオペレータでも問題なくスケールアウト・インされるのか？要確認。 ★

4.3. Azure stream analytics

Azure Stream Analytics（ASA）のジョブ定義は、 入力、クエリ、出力で定義される。

Azure Event Hub、Azure IoT Hub、Blobサービスなどとの連携も可能。

T-SQLの亜種を用いた分析処理が可能。

書き出し（Sink）は色々と対応している。 Blob、Table、Azure SQL DB、Event Hub、Service Queueなど。

本論文執筆時点で、UDFには対応していない。

Streaming Units（SU）の単位で分散処理される。 なお、SUはCPU、メモリなどを包含した単位。

5. Elasticity in stream processing systems

弾力性は、モニタリング、分析、計画、実行（MAPE）プロセスで実現される。

弾力性の実現には互いに関係する2種類の課題が存在する。

• アプリケーションワークロードに合致するITリソースを確保したり、解放したりする：elastic resource management
• 追加・解放されたリソースに合わせ、アプリケーションを調整する

スケールアウト・イン計画に基づき、アプリケーション調整を行うのをelasticity actionsと呼ぶ。

水平、垂直の両方向のスケールの仕方が存在する。

オートスケールに対応するため、アプリケーションには調整が必要になることがある。 例えば、実行グラフの調整、中間クエリの並列度の調整、など。 ★

水平分散はしばしば、処理グラフの適応（補足：つまり、グラフ形状の最適化）、オペレータの持つステートの出力（補足：つまりステートも引き継がないといけない）が必要になる。 ★

ウィンドウ化、もしくはシーケンス化されたオペレータを用いる場合、（ステート管理が必要になるため） 並列処理（のスケールアウト・インが）難しくなる。

ストリーム処理ではロングランなジョブを無停止で動かしたい、ということがあり、 ますますスケールアウト・インするときの扱いが難しい。 ★

弾力性の実現アプローチには、staticとonlineの2種類がある。

staticでは並列度やオペレータの位置を（補足：あらかじめというニュアンスがある？）最適化する。そのためにグラフを最適化する。

onlineではリソースプールの変更、新しいリソースを活用するためのアプリケーションの動的変更を含む。

5.1. Static techniques

2008年あたりの論文によると、初期タスクアサインと中間処理の並列度の最適化アプローチでは、 水平スケールが可能だった。

R-Storm（2015年）ではStormのカスタムスケジューラを提案。 ★ CPU、メモリなどのリソースプールに基づき、スケジューリングする。 これは要は、ナップサック問題に帰着する。 ★ 当該論文では、従来手法が計算量大きすぎるとし、ここでは 「タスクを必要リソースのベクトル、ノードをリソースバジェットのベクトル」と見立て、 ベクトル間のユークリッド距離で最適解を求める手法を提案した。 タスク間の通信にはヒューリスティックスを利用。

SBON（Stream Based Overlay Network）（2006年）では、 レイテンシを考慮しながらネットワークを構成する。 コストスペースという多次元ユークリッド空間を定義し、 適応的な最適化手法を利用する。

Zhouらが提案した手法（2006年）では通信コストを最小化する。 ロードバランスも考慮。 クエリを分割し、極力アサインされるノードを減らす。

ほかにも、 AhmadやÇetintemel (2004年）の論文では ネットワークバンド幅を最小化するアルゴリズムが提案されている。

5.2. Online techniques

ストリーム処理で弾力性を実現するには、以下の2個の要素が必要。★

• リソース使用状況、サービスレベルのメトリクス（エンドツーエンドのレイテンシなど）などを 観測する仕組み
• スケーリングポリシー

多くのソリューションはアプリケーション（というより、オペレーション）をブラックボックスとして扱い、 メトリクスから最適化を行う。

SattlerやBeierはこれらの手法は信頼性向上にもつながる、としている（2013） その観点でいえば、タスクがボトルネックになった際に、オペレーショングラフのリライトを起こすべき、となる。 （補足：つまり、入力に対して、処理が追い付かなくなってきたとき、など）

ステートフルなオペレータの最適化は非常に困難。 調整が走っている間、オペレータのステートは適切にパーティション化されていないといけない。 ★ （補足：しかもストリーム処理なのでレイテンシも気にされることになる）

補足：以下、関連論文の紹介が続く。

Fernandezらの論文（2013）では、オペレーションのステートをストリーム処理エンジンと統合するアプローチを提案した。 つまりステートはタプルの形式で定期的にチェックポイントされるようになり、 オペレータのスケールの最中、新旧のオペレータ間でリパーティションされるようになる。 ★ CPU使用状況がメトリクスとして管理され、複数のオペレータがボトルネックになっていることがわかるとスケールアウトを実行するようになっている。

T-Storm (Xu etら。2014年) = Traffic Aware Storm。 通信コストを減らすようなスケジュールをカスタムスケジューラを導入して実現。

Anielloらの論文（2013）でも同様のアプローチを提案。 オフラインで動作するスタティックなスケジューラと動的なスケジューラの両方を提案。

Lohrmannらの論文（2015）では、リソース使用を抑えつつ、与えられたエンドツーエンドの レイテンシを守るためのスケジューリングを実現する方法を提案。 ノードは均一であることを前提としている。 Rebalance（パーティション再アサイン）とResolveBottleneck（スケールアウト）の2種類の方法を使って実現。

ESCストリーム処理エンジンは、タスクスケジューリング、性能モニタ、リソースプール管理が協調して動作する。 またUDFを実行するプロセスは、ゲートウェイ機能（PEマネージャ）と実行機能（PEワーカ）の両方を内包。 マネージャはワーカのロードバランス機能を持っている。 リソース状況がひっ迫すると、PEマネージャごとPEワーカを止め、スケールアウトを実行する。

StreamCloud（2012）は、クエリをサブクエリに分け、独立した複数の計算クラスタに割り当てる。 ステートフルなオペレータに依存して分割度合いが決まる。 リソース管理の仕組みと、ロードバランスの機能を持つ。

Heinzeらの論文(2014)では、リソースの配置（再配置）を行う際に レイテンシのスパイクを考慮に入れる。 オペレータの配置は、「インクリメンタルなビン・パッケージング問題」とみなすことができる。 ここでは主にCPU使用率やキャパシティを対象とする。（メモリやネットワークも考慮はするようだ）

補足：ここからIBM Streams（System S?）の関連論文が数件続く。

Gedikらの論文(2014) では、IBM Streamsを対象として自動並列化を狙った。 ステートフルなオペレータも含むエラスティックな自動並列化を提案。 スプリッタにおけるブロッキング時間やスループットをメトリクスとし、並列度を決める。 データスプリッタでは、ステートレスの場合はラウンドロビンに従い、 そうでなければハッシュベースになる。

Tang and Gedik (2013) らの論文では、IBM Streamsを対象とし、 タスクやパイプラインの並列化を提案。 オペレータのパイプラインのスレッドを管理。スレッドを追加することでスループットを向上させる。

Gedik等の論文(2016) では、IBM Streamsを対象とし、パイプライン並列、データ並列の両方を実現する手法を提案。 チェーンのようにつながったデータフローグラフを分割する。 その際、オペレータがレプリケート可能かどうかを考慮し、並列化する。

Wu and Tanの論文 (2015) では、以下の点に関する検討を実施。

• 大きなサイズのステートを管理
• ワークロードの変動
• マルチテナントの実現

彼らはChronoStreamを提案。 弾力性とオペレータマイグレーションの実現のため、アプリケーションレベルのステートを 計算ノードレベルのステートに分割し、スライス化する。 スライス化されたステートは、チェックポイントされ、ほかのノードに複製される。 スライスごとに計算の進捗は管理される。（このあたりがSparkのDStreamと異なる）

Xuらの論文（2016）では、Stela（Stream Processing Elasticity）を提案。 スケールアウト・インの後のスループットを最適化し、計算がストップするのを極力防ぐ。 Expected Throughput Percentage (ETP)をメトリクスとして使用。 オペレータの処理速度が変わった場合に最終的にどんなスループットになるのか？の値。 本手法はStormのスケジューラの拡張として提供されている。

Hidalgoらの論文では、オペレータの分割で並列化を実現する。 その際、オペレータの状態を管理するため以下の2種の手法を使用 ★。

• short-termアルゴリズム
  • トラフィックのピークを検知するために短期間のロードを観測
  • 下限上限で管理
• long-termアルゴリズム
  • トラフィックパターンを把握するため長期間のロードを観測
  • マルコフチェーンモデルで管理

上記に基づき、当該オペレータが過負荷、安定、負荷不足なのかを予測する。 ★

ここ最近、コンテナや軽量な仮想化技術の利用に関する研究も盛んである。

Pahl and Lee らの論文(2015) では、コンテナをエッジ、クラウドコンピューティングの 弾力性を高めるための研究を実施。

Ottenwälderらの論文 (2013) では、オペレータ配置とマイグレーションを支援するため、 システムの特徴と移動体パターンの予測を用いる。 クラウドコンピューティングとフォグコンピューティングの両方を含む。 移動体は、近くのブローカに接続する。 これによりネットワークコストを低減し、エンドツーエンドのレイテンシも改善する。 オペレータのマイグレーション計画は動的に変わる。 その際タイムグラフモデルが用いられる。

以下に、ツール群の比較表を引用する。 ★

ツール比較表

5.3. Change and burst detection

入力データの変化、バーストを検知すること。（補足：というのが重要、ということ） それ自体は弾力性の実現ではないが、トリガとして関係することがある。

Zhu and Shashaの論文 (2003) では、移動ウェーブレットツリー・データ構造を用いて、 それらを検知する。ウィンドウの取り方は3種類。 ランドマーク（固定）、移動式、過去分を減衰。

参考：ウェーブレットと多重解像度処理

そのほか、Krishnamurthyらの論文(2003) では、Sketchを用いる。

参考：乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－

6. Distributed and hybrid architecture

旧来の多くの分散ストリーム処理の技術は、クラスタを対象としていた。 最近の研究では、エッジを考慮したものが登場している。

インターネットのエッジであるマイクロデータセンタは、しばしば「Cloudlets」と呼ばれる。 データ転送量の低減、エンドツーエンドのレイテンシ改善、クラウドからのオフロードが目的。

ただし、多くの手法はまだ模索段階。

6.1. Lightweight virtualisation and containers

軽量な仮想化、もしくはコンテナを利用する、というのがしばしば挙がる。

Yanguiらの論文(2016)は、クラウド・フォグコンピューティングのPaaSを提案。 Cloud Foundaryを拡張。

Morabito and Beijarの論文 (2016) は、エッジ・コンピューテーション・プラットフォームを 提案した。リソースの弾力性を実現するため、コンテナを利用する。 シングルボードのコンピュータをゲートウェイとして利用する。 データ圧縮などに利用する。

Petroloらの論文（2016）も、同様にゲートウェイデザインを提案。 ワイヤレスセンサーネットワーク向け。

Hochreinerらの論文 (2016) では、エラスティックなストリーム処理の仕組みとして、VIennaエコシステムを提案。 プロセッシンググラフを書くためのグラフィカルなユーザインターフェースも供える。

6.2. Application placement and reconfiguration

モバイルクラウドとヘテロジーニアスメモリに関するGaiらの論文（2016)　では、 ハイブリッドシナリオでのタスクスケジューリングについて触れられている。

Benoitらの論文 (2013)、Roh等の論文（2017）では、ヘテロジーニアス・ハードウェアやハイブリッドアーキテクチャにおける コンピュータリソース使用に関するスケジューリングについて取り扱っている。

Cardelliniらの論文 (2016)では、 Optimal Distributed Stream Processing Problem (ODP)向けに ヘテロジーニアスなリソースを考慮した integer programming formulation を提案。 Stormを拡張し、ODPベースのスケジューラを採用。 ネットワークレイテンシを推測。

地理分散されたVMに、ストリーム処理のオペレータを配置する問題は、NP困難（ないし、NP完全）である。（2016、2017） しかし、コストアウェアなヒューリスティックは提案されている。(Gu et al., 2016; Chen et al.,）

SpanEdge（Sajjad et al. (2016) ）は、中央とエッジのデータセンタを使うストリーム処理ソリューション。 マスタ・ワーカ構成のアーキテクチャであり、hubワーカ（中央）とspokeワーカ（エッジ）を持つ。 スケジューラはローカルタスクを各エッジ上のワーカで実行しようとする。 ★

Mehdipourらの論文 (2016) は、クラウドとフォグの間の通信を最小化するように動く。 IoTデバイスからのデータを処理する。

Shenらの論文(2015) は、CiscoのConnected Streaming Analytics（CSA）を 利用する。データセンタとエッジの両方を利用する。 ★ CSAが継続的クエリのためのクエリ言語を提供する。

Geelytics（Chengらの論文 2016）は、IoT環境のためのシステム。複数の地理分散されたデータProducer、結果Consumer、計算リソースを活用する。 それらはクラウドもしくはネットワークエッジのいずれかに置かれる。 マスタ・ワーカアーキテクチャであり、Pub/Subモデルのサービスを採用。 アプリはオペレータのDAG。 スコープ限定されたタスクが特徴的。 各タスクのスコープの粒度をユーザが指定可能。 データProducerの地理情報に基づきresultタスクを配置する。

7. Future directions

大きな組織におけるビッグデータソリューションは、 バッチとオンラインの両方を有することになる。 ★ また複数のデータセンタにまたがることもあり、それらの中で弾力的にリソースを使用できることが理想的である。

ここでは将来の展望を述べる。

7.1. SDN and in-transit processing

SDN等を通じて、ネットワーク経路の途中で計算を行う。 このアプローチは、セキュリティとリソース管理の課題をはらむ。 例えば、IoTデバイスからデータセンタの経路の途中で計算させることは、攻撃可能な個所を増やすことにつながる。 また状況に合わせたリソース配置も困難だ。

既存の多くの研究では、複数のオペレータの配置においては、 レイテンシやバンド幅などのネットワーク・メトリクスに着目する。 一方で、ネットワークがプログラム可能であることは考慮されていない。

コグニティブ・アシスタンスのユースケースでは、データセンターで機械学習モデルが学習され、 その後エッジ側で推論される。 ★ このときのひとつの課題は、結果的に生じるコンセプト変動である。

7.2. Programming models for hybrid and highly distributed architecture

Boykinら（2014）、Google Cloud Dataflow（2015)のように、ハイレベルの抽象化を実現したものがある。 これらのソリューションは単一のクラスタやデータセンタでの利用に限られているが、 一部これをエッジコンピューティングまで拡張する取り組みが生じている。 そのような条件下で、リソース使用を効率的に管理する手法に関する研究が多く行われるだろう。

Apache Beam（2016）のプロジェクトでは、ユニファイドなSDKを提供。 Apache SparkやApache Flinkに対応。 一方で、エッジ・フォグ・データセンタコンピューティングを横断するユニファイドなSDKはない。

Apache Edgent （2017) がインターネット・エッジでの計算・分析を可能にする。 ★

参考：Apache Edgent