 

  と  を用いた並列分散処理機構の性能比較
菱沼 直子Ý

竹房あつ子ÝÝ

中田秀基ÝÝ

小口 正人Ý

お茶の水女子大学 〒   東京都文京区大塚  
産業技術総合研究所 〒  茨城県つくば市梅園                  


あらまし

クラウドコンピューティングの発展に伴い，大量に生成されるデータを蓄積し，高速に処理することが求められている．このような処理は従来の  では難しいことから，大量に生成されるデータの蓄積には分散 

が，高速な処理には  処理系と分散ファイルシステムが用いられている．しかし，蓄積した大容量データを処理するためには分散  から分散ファイルシステムにデータを転送しなければならず，そのコストが問題となる．  には，  連携機能がある．この連携機能を使用すると転送コストの発生を防ぐことが予想されるが，その性能は明らかでない．我々は，既発表研究において，データを蓄積した分散  上で直接高速データ処理を行う手法を提案し，分散  の   を拡張した並列データ処理機構を実装した．本

稿では，  と本実装との比較を行い，これらの特性を明らかにする．比較実験より並列データ処理機構では，データサイズによらず高速に処理することができ，本提案手法の有効性が示された．
キーワード 分散並列処理， ，分散 ， ，通信データ量               
   Ý   ÝÝ    ÝÝ     Ý  ! " # $   %$ &$   '()(**   +   (#  + ,   & $ -(+,&.
  " ! &/  +/    '()(*
                う はじめに   ! "#$以下  % & 等の分散

ファイルシステムへデータを転送するため，その転送コスト

トワーク上に保存されるようになり，ネットワーク上に存在す  のデータスト
アに利用される  には   ' という機能が実装るデータが爆発的に増加している．このような大容量データは，されており，カウント，集約などの単純なプロセスをデータ保厳密な一貫性が必ずしも必要ではないため結果一貫性を保証す持しているサーバ上で実行している．しかし，る．

チ処理向きのシステムであり，リアルタイムに発生するデー

クラウド技術の普及により，個人が生み出す情報が大量にネッ   や    などの分散
 の枠組みが既に広く使われている． などでサービスが発生してしまう．この問題点に対し，

  はバッ

タを格納しつつ，処理するには不向きである．大容量データな処理系を利用することで，高速に処理することができる．現  には，  連携機能 $以下
   % が実装されている．この機能を用いれば転送コストを削減できると予想されるが，   
も   処理を行うため，その性能は明らかではない．
我々は既発表研究 ( において，リアルタイムに蓄積された在ではこれらの処理に

データに対して高速データ処理を実行する手法を提案した．提を提供するためには，保持しているデータを活用してユーザが必要とする情報を抽出する統計処理やマイニング処理などが不 はそのような処理を念頭に置いて設計されておらず，   のよう可欠となる．データ保持に使用される分散である．

    を用いるのが一般的  を用いる際には分散  から処理を行

しかし，を高速に蓄積可能な案手法では，データアフィニティを考慮してデータを格納している  のデータノード上で直接データ処理を実行す) )  の標準コマンドを機能拡る．我々は，上記手法を，への適応など，ニーズに合った機能を分散ストレージに対して

1 を用いて つの分散  上でユーザ

張し，値を保存している各データノード上で処理をローカル実実行可能になる．

行し，処理結果のみをリクエストの答えとして返す並列データ

が任意の処理を実行可能にする本実装と類似していると考えら処理機構を実装した．

れる．

  * との性能比較を行い，これらの特性を調査する．比較実験

 章で関連研究につい  の概要， 章で既存研究で提案した

1 機能を用いて任意の処理を並列化する手法に関連す0  や /-5   などがある．
0 は /-*-6 な宣言的言語 0/- をサポートしており，0/- のクエリは   のジョブにコンパイルされ   で実行される．これにより，ユーザは  上のデータを /- で操作するように   上でデータ操作が可能になる．0/- は 1 も機能もサポートしている手法の概要と実装した並列データ処理機構についての説明をすため，ユーザが任意の処理を並列化実行することができる．

本稿では，実装した並列データ処理機構とより，複数の値に対してワードカウント処理を実行した際の実
行時間は並列データ処理機構を用いた方が短く，本提案手法の有効性を示すことが出来た．

本稿は以下のように構成される．まず

て述べ， 章でる研究としてる． 章で本実装と     との比較について述べ， /-5  は /- の 1 を機能拡張し， & 章で本論文のまとめと今後の課題を述べる．
を用いることで並列型データ処理を実行可能にしている．これ 関 連 研 究らの実装は本研究でユーザが任意の処理を並列実行するため，  は，書き込み性能を重視した分
散  である．  を用いた研究として + がある．こ1 として 4  ファイルを転送する機能を実装している点，今後の拡張方向として /- を用いる点で類似している．しかし，0 や /-5  は並列化に   を用いの研究は，既存のクラウドストレージが読み出し性能と書き込ているが，本実装は処理を複数のデータノード上へ転送するこ

み性能のどちらか一方を重視している点に着目し，同一クラウとで並列化している点が異なる．

本研究で用いた

ドストレージ内で読み出しと書き込み両方の性能を両立可能な 

"  ! を提案し，実装した．読み出し最適化と

 



書き込み最適化のストレージエンジンを選択可能で，それぞれ

   は， 6 社が開発し，  プロ

適切な方へリクエストの振り分けを行うことで両者共に性能がジェクトとしてオープンソース化された分散データベース管理

出せるように工夫した仕組みを備えている．

システムである, - . は，/- をベースにした並列  である．!!0 / " と呼ばれる機能を用いて，/- クエリの並列実行をサポートしている．また，, - は 12$1 *3 2!% と呼ばれる，クライアントが発行する
/- クエリの中にシェルコマンドを埋め込むことができる機の能を提供する．ユーザが実行したい処理をプラグインとして定える．

 ．  の主な特徴として，耐障害性，

非中央集中型で単一故障点がないこと，一貫性の程度をユーザが自由に設定可能であることが挙げられる．必要とする一貫性のレベルをクライアントがクエリに記述することで，自由に はもちろん，他/- でもあまり見られない，  固有の特徴と言設定することが出来るという点は，

義し，リクエストの答えとして処理結果のみを取得する点で本1 3 $1 % と類似してい
る．1 は，/- 中でデータに適用可能な関数をユーザが独ᵬᵿᶋᶃᵬᶍᶂᶃ

提案手法におけるᵨᶍᶀᴾᵲᶐᵿᶁᶉᶃᶐ

自にプラグインとして定義できる機能である．

4

 上でデータ処理を可能にする並列分散処理フレームワークである．  と同様にリングトポ
ロジを利用し，,, により隣接ノードの情報を保持している．
4 も本実装と同様にユーザが定義した 40 プログラムをは，

ᵲᵿᶑᶉᵲᶐᵿᶁᶉᶃᶐ
ᵢᵿᶒᵿᵬᶍᶂᶃ
ᵡᵿᶑᶑᵿᶌᶂᶐᵿ

ジョブとして，各データノードに転送し，実行する実装になっ を機能拡張しているのに対し，4 はシンプルな  をベースにしている点が本研究とᵲᵿᶑᶉᵲᶐᵿᶁᶉᶃᶐ
ᵢᵿᶒᵿᵬᶍᶂᶃ
ᵡᵿᶑᶑᵿᶌᶂᶐᵿ

ᵲᵿᶑᶉᵲᶐᵿᶁᶉᶃᶐ
ᵢᵿᶒᵿᵬᶍᶂᶃ
ᵡᵿᶑᶑᵿᶌᶂᶐᵿ

ている．我々は既存の分散
異なる．

 などをはじめとする大規模アプリケーションは，展開するサービスによってストレージに対して様々なニーズがある．
現状の分散ストレージでは複数アプリケーションの異なるニー
ズをつのシステム上で満たすことができない．そこで，様々なアプリケーションのニーズに対応する分散ストレージとして#  が研究されている．通常の分散  を拡張し，ア

プリケーションはトラッキングやアクセスログやコンテキスト

図   の概要

    の概要を示す．  * は   0 .7& から標準で実装されている機能であり，  のデータノードを   の 868  として動作させるものである．通常の   はデータの入出力は   に対して行うが，    ではストレージ
図

に

))

  の代わりに   を用いており， に蓄積されたデータに対して   を用いて処理する．
ストレージに   を用いることで，耐障害性を高くする
として

Ṟ

ṡ
ᶌᶍᶂᶃᵟ

ことができる．この実装を用いれば転送コストを削減できるこ  のプログラミングモデルの制約とが予想されるが，があることや，小さなデータの扱いには不向きであるという課
題がある．

ᶌᶍᶂᶃᵠ

ᶌᶍᶂᶃᵢ

    を用いた場合の処理の例を図 

Ṡ

ṟ
ᶌᶍᶂᶃᵡ

ᵡᵿᶑᶑᵿᶌᶂᶐᵿᵫᵿᶎἧỹὊἌᵡᵿᶑᶑᵿᶌᶂᶐᵿ

ᵰᶃᶂᶓᶁᶃ
ἧỹὊἌᵭᵰ   でのデータ分割イメージ

図

ᵦᵢᵤᵱ

図

ᵢᶃᶄᶇᶌᶃᴾᶒᶆᶃᴾ ᵆᵏᵇᶎᶐᶍᶁᶃᶑᶑᴾᵶ

   の処理過程ᶔᵿᶊᶓᶃᴾᵟᵆᵐᵇ

ᶐᶃᵿᶊᴾᶂᵿᶒᵿ

ᵡᶊᶇᶃᶌᶒ    では値の入力を   から行
い，通常の   と同様に  フェーズ   フェー
ズを実行し，処理結果を   もしくは   上に書き出すことが可能である．  の 9 9 ! コマンド
$次章で述べる% を利用して図  のように   のリングを分割し，レンジ のデータは   が担当し， は  ，は  : は   が担当する．この時，  の実装
上，レンジ のデータは   が元々保持しているため，デーに示す．

タの転送が発生せず各データを保存しているノード上でローカ
ルに 処理を実行する仕組みとなっている．

 既発表研究  に蓄積された大容量データに対して統計処理やマ
イニング処理等を行う場合は，  から処理の対象となる値を取得した後，分散ファイルシステムや   処理
系を用いて処理を行う流れになる．しかし，  の読み
出し処理性能はあまり高くない上に，対象とする値のデータサ  から分散ファイルシステム等へ転送する際に大きな転送遅延が生じてしまう．そこで我々は ( において，  に蓄積された大容量データに対して，デー
イズが大きいとタアフィニティを考慮して高速データ処理を可能にするための手法を提案した．

ᶐᶃᵿᶊᴾᶂᵿᶒᵿ

ᵆᵒᵇᶔᵿᶊᶓᶃᴾᵟᶐᶃᶎᶊᶇᶁᵿ

ᶔᵿᶊᶓᶃᴾᵠḚᶐᶃᵿᶊᴾᶂᵿᶒᵿ

ᶎᶐᶍᶁᶃᶑᶑ
ᵶᵆᵑᵇᶔᵿᶊᶓᶃᴾᵠᶐᶃᵿᶊᴾᶂᵿᶒᵿ

図ᶔᵿᶊᶓᶃᴾᵟḚᶐᶃᶎᶊᶇᶁᵿ

提案手法の概要

ドへリクエストを送信する．

$% 各データノード上にある，異なる値 : に対して定2 を並列実行し，処理結果を新たな値 ;:; とす

る．各値のレプリカに対しても同様の処理を行う．

$% 処理結果である値 ;:; をリクエストの答えとして返す．
図 では値  のレプリカの処理は省略している．
  並列データ処理機構の概要

前節で説明した手法を実現させるために実装した並列デー  の標準読み出しコマ

タ処理機構について説明する．

ンド  と    を拡張し，読み出し処理のリク  に保存された複数の異なる値

エストを送信すると，に対して，実行時に指定した処理を各データノード上で実行し，処理結果のみをリクエストの答えとして返す機能を実装し

1 を 40 で定義し，読み出しリクエストと共に定義した処理の 4  ファイルをデータノード上へ転送すた．本実装ではここでいうデータアフィニティとは，各値が保存されている
データノード上で処理を実行する事を意味している．

1 $1 3 % でユーザが実行したい処理をプラグインとして定義可能にする．定義された処理を，処理対象データを保持している各データノード上でローカルに実行し，処理結果のみをクライアントに返すことで転送コストを削減し，高速データ処理を実現する．
提案手法の概要を図 に示す．

$ % 1 として，任意の処理 2 をプラグインとして定義する．

ᶔᵿᶊᶓᶃᴾᵟḚᵮᶐᶍᶖᶗᶎᶐᶍᶁᶃᶑᶑᴾ
ᵆᵑᵇᵶᶎᶐᶍᶁᶃᶑᶑᴾ
ᵶ

義された処理  提案手法の概要

提案手法では，ᵆᵑᵇ$% クライアントからデータを格納している各データノー

ることでユーザが指定した任意の処理を実行可能にしている．

  の主な標準読み出しコマンドの内容は表 に示す．
表  の主な標準読み出しコマンド



指定した一つの値を取得

  

 を指定して対応する
それぞれの  を取得   の  を指定し複数の  を取得)) を用いて説明する．
$ % 実行したい処理 の 4  ファイルを作成する．
$% 読み出しリクエスト共に実行したい処理 2 の 4 
ファイルを転送する．4  ファイルを転送しない場合は通常の本実装の概要を図読み出しが実行される．

$% 各データノード上にある，異なる値 : に対して転送した処理 2 を並列実行し，処理結果を新たな値 ;:; とする．
$% 処理結果である値 ;:; をリクエストの答えとして返す．

    を含む 4

 ファイルを事前に作成しておく．

& は，1 を実行する際のプログラム例を示している．文
4= 形式でクラス名，4  ファイル名を指定しておく．また，ユーザの定義した 1 に必要な任意の実
行オプションも同様に 4= 形式で指定することができる．こ図字列  には，の  を，   を拡張した    
関数に渡すことで，コマンドリクエストとともに指定した
ファイルが

4 

  のデータノードへ送信され，データノー

ド上で指定した処理を実行することができる．

各値のレプリカに対しても実行時に指定した処理を実行し，リクエストの答えをハッシュ値$9% で返して整合性が保たれていない場合はバックグラウンドで同期処理を実行する．

   

 との比較    と前章で述べた並列データ処理機構の性
能比較を行う．

       実 験 環 境( 台からなるクラスタに，提案手法による機能拡張を行った   をインストールした．今回の開発では，  バージョン 77. を用いた．測定に用いたノードの性能を表  に示す．

     

ノード数が最大     !  "  
#$

"

表

      

(" " 

!!

"" 

)*+, -+, ( . !$/)*+, -+, ( . ! '$/

"  %

図

マシンスペック# $%& !'!

   の一例

0  

1$2



''$2 3 ''(0 4 54)  **

4") +4) ',% 5$#  実験概要・評価

& 

" '

()( )(* )(+ 

" .' ()(/

,)(- ()(*)( + , 0"%/)(- (

" .' ()( 1)(*)(+ 1  ,)((    と並列データ処理機構の比較を行う前に，    の基本性能を調査した．測定に用いたパラメータ設定を表  に示す．図 ' にデータノード数を  台，
 台，( 台と変化させた場合の実行時間の変化を示す．グラフよᵑᵎ 'ᵐᵓ % 00"+  5,- +  ,-+  " ,-+4  3,- "
図リクエストプログラムの例

ܱᘍ଺᧓ᵹᶑᶃᶁᵻ

2 + - 3+4 $ & 4 ,,

ᵐᵎ
ᵖӨ

ᵏᵓ

ᵓӨ

ᵏᵎ

ᵑӨ

ᵓ

並列データ処理機構の
いる．図
は，
と

40 の ,< は以下のようになってᵎ

 に 1 の定義例を示す．並列データ処理機構で      ᵏ    の図3るように拡張した．   メソッドは，表のコマンドを  のデータノード側で値を取得するために呼び出されるメソッドである．ユーザは，  !
である  を継承したクラス   を作成し，そのクラスの  メソッド内に任意の処理を実装する．また，ᵏᵎᵎᵎ

ノード数・データサイズを変化させた場合の実行時間  メソッドを拡張し，各値に対して任意の処理ができ呼びだされた際にᵏᵎᵎᶂᵿᶒᵿᴾᶑᶇᶘᶃᵹᵩᵠᵻ      

ᵏᵎ

り，データノード数が 台， 台の場合よりも ( 台の方が実行   

時間が短いことが分かる．この結果より，も並列データ処理機構同様に台数増加に伴って性能向上するス
ケールアウトする性質があるといえる．

  上 に 保 存 さ れ て い る 値 $テ キ ス ト デ ー

次に，

))

% ... 個に対して，実装した並列データ処理機構と    を用いて     を ... 回実行するのにかかる時間を測定する．一つのテキストデータサイズを 〜 
タまで変化させた場合の実行時間の変化を調査する．
表 お わ り に
我々は既発表研究において，大容量データを高速処理する際に発生するコストを抑えつつリアルタイム処理を可能にするため，分散測定に用いたパラメータ設定

 の実装の つである    を拡張

データノード数

661

してデータアフィニティを考慮した並列データ処理機構を実装

処理を行う値の数'''した．この実装は一つの値の大きさ

26 '26 ''26 02

対して，値を保存している各データノード上で事前に指定した

  に保存された複数の異なる値に処理をローカル実行し，処理結果のみをリクエストの答えとし( + 台，( 台とし，一つの値の大きさを "〜 " まで変化させた場合のそれぞれの実行時間を示す．縦軸が実行時間 $%，横軸は値の大きさ $% を表す． 図 (，+ より，値の大きさ，ノード数に関わらず並列データܱᘍ଺᧓ᵹᶑᶃᶁᵻ

図 ， にデータノード数を

ᵑᵎ
ᵐᵕ
ᵐᵒ
ᵐᵏ
ᵏᵖ
ᵏᵓ
ᵏᵐ
ᵗ
ᵔ
ᵑ
ᵎ

能比較を行い，これらの特性を調査した．比較結果より，並列データ処理機構は値の大きさ，データノード数に関わらず，高>  以外の処理での比較や，よ今後の課題としては，り大規模な環境での比較を行うことがあげられる．実装の課題

# や 0 9 などの集約演算処理を実行可能にすとしては，るため，集約演算処理のフェーズを追加することがあげられる．
本実装でこのような機能を追加する場合には

/-$ / " -99% と呼ばれる /- ライクな言語を利用して集約演算する手法が考えられる．

図1

ܱᘍ଺᧓ᵹᶑᶃᶁᵻ

としてい性能を出すことが出来た．

ᵦᵿᶂᶍᶍᶎᴾᵡᵿᶑᶑᵿᶌᶂᶐᵿ
ɳЗἙὊἑϼྸೞನ

ᵏ

ᵑᵎ
ᵐᵕ
ᵐᵒ
ᵐᵏ
ᵏᵖ
ᵏᵓ
ᵏᵐ
ᵗ
ᵔ
ᵑ
ᵎ

  のストレージ  を用いた     という機能があり，本稿では並列データ処理機構と     の性て返す仕組みとなっている．これに対し

ᵏᵎᵏᵎᵎ
ᶂᵿᶒᵿᴾᶑᶇᶘᶃᵹᵩᵠᵻ

ノード数が

ᵏᵎᵎᵎ

台の場合の実行時間ᵦᵿᶂᶍᶍᶎᴾᵡᵿᶑᶑᵿᶌᶂᶐᵿ
ɳЗἙὊἑϼྸೞನ

ᵏ
図7

ᵏᵎ
ᵏᵎᵎ
ᶂᵿᶒᵿᴾᶑᶇᶘᶃᵹᵩᵠᵻ

ᵏᵎᵎᵎ

ノード数が 1 台の場合の実行時間

処理機構を用いた場合の方が高速に処理していることが分かる．
これは，今回の実験ではデータサイズが比較的小さい値で行っ    を用いた場合，  を行たため，う際の入出力にかかる時間がオーバーヘッドとなったためと

 の時は    と並列データ処理機構との実行時間の差は  秒程度になって考えられる．データサイズがいた．
以上の結果より，並列データ処理機構はデータサイズによらず高速に処理することができ，本提案手法の有効性が示された．

文

献

8 9 4!5:   (!0*5! ;  " 4  */      6; 40 )$(   "  <6 <*! 6 % 6 ((! " '64 * ' '!
8 9 =# !6 > ?: @< 6  ! :" :  ?5: 5#:! A** B4(4%6 ' !
8 9 ?: 4: C  ! 4: 2!
:>&&:#!:! &:#&!
8 9 B!  !$: ! ;0>  *@ (     * ; ) (  C : :C           D) *  " E*   +)A' ,6 E*! ! =%)- 4"6 2 5*6 46 46 '" '!
89 ? F:!6> ?: @< 6  ! G? ! A** B4(4%6 ' '!
89 : # 2 :5 ! ; 4 : 6; ''1 ?:
4: C  !
839 ?: 4: C  ! 4: 2&  !
:>&&#*!:! &:#& &   !
819 %!: 6 4!?5C6 !%56 0!:! ;) *" C  4Æ"#  # ( *** ( "    #  E*  ; ) ( ! 40)00 ' 6  6  #6 B  ' !
879 !%5  6 !:! ;4 *     2: <  F  < F 5*; (  C
: : 4* ) *      C "! 406 ' ! ! !
8 '9 ? :6 G  ? ! ;( >   **"< H   #   ( ***/  "@= #*; ) (  C : : )===&40 ) "*    * 6 *  $   " +$  ,6 6 ' > 3 " 1
8 9 %44$4F4 )56 %4$40) :! ;B#"( ***  # (     5>  (   * * E #; ) ( ! )===&)(B :) *    4*  : ) ))+4)%? ' ,6! " 1 )===6 ' !
9 !$ #6 4!4!<6 ?!:6 4! :  : 
!0!<! ; > 4 <  # 5"<*  ;) ( ! )! ' '6 # ! ! " !
8 9 4!?:6 B!! 6 %!B6 I!:6 (!:556 !4:6
!6 (!F5J  !0 :! ;<>   : *" <  "  C   5; ) ( ! E2 =!
6 +4 ''7,6  "  7!
8 9 =!  6 (!(*56  B!*/! ;H&0>  *  :  *C" #6 *  :6  ***/#*  "@ C; ) ( ! E2 ="! 6 +4 ''7,6 ' "!
8)&)