QueueLinker : A Framework for Parallel Distributed Data-Stream Processing

　モバイルデバイスやセンサの発達と普及により，データの生成量が大規模化するに加えて，情報のリアルタイム化が進んでいる．このようなリアルタイムに発生し続けるデータの列はデータストリームと呼ばれている．データストリームは，データが到着してから可能な限り早く解析を行うことで価値が増す．顕著な例であるアルゴリズム取引では，数マイクロ秒の処理レイテンシの差が取引の勝敗を分けるとまで言われている．アプリケーションによっては，大量のデータストリームを処理するために並列分散処理も必要になる．これらの要求を満たすアプリケーションを容易に実現するために，データストリーム処理を補助するためのフレームワークが求められている．

 そこで本研究では，データストリームのための並列分散処理フレームワークQueueLinkerを開発した．研究においては，データストリームに対して関係代数演算を適用する処理であるContinuous Queryの低レイテンシ処理を実現するため，（1）関係代数オペレータへのスレッド・CPUコアの割り当て手法，（2）分散処理時にオペレータバックアップを活用して低レイテンシ処理を実現する方法を提案した．また，アプリケーションとして，（3）QueueLinkerを用いた超高速並列分散Webクローラの実装方法を示した．

 QueueLinkerはProducer-Consumerモデルを採用した，データストリームのための並列分散処理フレームワークである．モジュールの実装とモジュール間の接続関係の記述を与えることで，データストリームの並列分散処理を実現することができる．スレッド間や計算機間のデータの転送はQueueLinkerが自動的に行うため，ユーザが記述する必要はない．

 並列処理時には，計算リソースの割り当てが問題になる．本研究では，データストリームに対するContinuous Queryの低レイテンシ処理を実現するため，スレッド・CPUコアの関係代数オペレータへの割り当て方法を提案した．オペレータのCPU使用統計を取り，処理あふれが起きないようにCPUを割り当てつつ，通信回数を削減することでレイテンシを削減する．Continuous Queryに対して，低レイテンシ並列処理の定義付けを行ったのは本研究が初めてだと考えている．

 分散処理においては計算機障害に備えて，バックアップを保持するセカンダリが必要になる．本研究では，プライマリとセカンダリを異なる計算機構成とし，双方を同時に計算させて先に出力された計算結果を利用することで，処理レイテンシを削減する方法を提案した．既存研究ではセカンダリは障害時にしか利用されていなかった．

 さらに，QueueLinkerの並列分散能力を示すために，並列分散WebクローラのQueueLinkerによる実装方法を示した．このクローラを構成するQueueLinkerモジュールはすべてデータ並列で動作可能である．ハッシュ分割により，モジュールごとに任意数のスレッド・計算機の割り当てができ，容易にスケールアウトが可能となっている．実験の結果，毎秒4,000ページ以上のダウンロード速度を実現できた．