Hadoopはどのように動くのか ─並列・分散システム技術から読み解くHadoop処理系の設計と実装

第8回 データ処理における並列アルゴリズム[3]

この記事を読むのに必要な時間:およそ 3 分

Impala/Prestoにおける結合処理

並列データ処理系であるClouderaのImpalaやFacebookを中心に開発が進められているPrestoは,結合方法としておもに並列ハッシュ結合を用います。

Impalaの並列ハッシュ結合においては,上述のようなパーティション並列性の活用に加えて,パイプライン並列性を活用します。パイプライン並列性を活用するハッシュ結合方法は,1990年代に並列データベースの分野で数多く研究されてきており,複数のデータを結合する際に,たとえば図2に示すように,先に複数のデータに対してハッシュ表を構築(ビルド,Build)し,その後,当該ハッシュ表に対してパイプラインで参照(プローブ,Probe)を行うことにより,複数の結合を同時に行います。このようにすることにより,各ノードにおける結合処理の並列度を高めることができ,たとえば複数のCPUの利用率を高めることが可能となります図3(a⁠⁠。ただし,同時に複数のハッシュ表をメモリ上に置いておく必要があるため,データが大きい場合はハッシュ表を保持するメモリを大量に使いすぎてしまい,最悪の場合は結合処理を正常に完了できない可能性があります。

図2 Impalaにおける並列ハッシュ結合

図2 Impalaにおける並列ハッシュ結合

図3 結合処理の並列度

図3 結合処理の並列度

一方,Prestoの並列ハッシュ結合においては,基本的には上述のパーティション並列性を活かした方法が用いられます。すなわち,複数のデータを結合する際は,図4に示すように,2つのデータにおいてハッシュ結合を行い,その結果データからハッシュ表を構築して,次のハッシュ結合を行う,という風に処理を進めていきます。この方法は,Impalaの方法に比べて,各ノードにおける結合処理の並列度は低いですが図3(b⁠⁠,メモリの使用量が少なくなるため,より安定的に結合処理を行える可能性があります。

図4 Prestoにおける並列ハッシュ結合

図4 Prestoにおける並列ハッシュ結合

また,Apache Sparkにおいては,事前に定義されている結合オペレータにより,Prestoと同様のハッシュ結合が行われます。ただし,パイプライン型のハッシュ結合を実行するオペレータを新たに定義することにより,Impalaと同様の結合方法を実現することは可能であると考えられます。Hadoop MapReduceにおいては,通常はReduce側で並列ソートマージ結合を行うReduce-side Joinですが,ブロードキャスト結合を用いることにより,Map側で並列ハッシュ結合を行うことも可能です。

ImpalaやPrestoの高速性の理由

ImpalaやPrestoはHadoop MapReduceと比べて高速であると言われていますが,その理由はおもに次の2つであると考えられます。

1つ目は,アルゴリズムの違いからくるものです。すなわち,先ほどもかんたんに述べたとおり,多くの場合,ハッシュ結合はソートマージ結合よりも高速であるためです。集約処理においても,Hadoop MapReduceは整列処理フレームワークを活用したソートベースの集約を行い,一方,ImapalaやPrestoはハッシュベースの集約を行うため,同様にアルゴリズムの差から性能差が生じていると考えられます。

2つ目は,システムの設計思想の違いからくるものです。Hadoop MapReduceは,二次記憶に中間状態を記録しながら処理を進めるため,どのような処理でもそれなりに動作するように設計されています。すなわち,Hadoop MapReduceはロバスト性や耐障害性を重視した設計ですが,その反面,総計のI/O量は必然的に多くなり,必ずしも高い性能は期待できません。一方,ImpalaやPrestoは,最初の読み出し以外においては,基本的にはメモリ上で処理を行います※2⁠。この戦略は,当然,クエリ処理における中間データがメモリに収まり,かつ,クエリ処理の途中で障害が発生しない場合は良いのですが,そうでない場合は,当該クエリを正常に終了することができません。すなわち,ロバスト性や耐障害性をある程度妥協し,高速性を重視した設計であると考えられます。たとえば,Impalaのクエリ処理においてロバスト性や耐障害性を考慮した設計がなされているとすると,当然,総計のI/O量は増加し,Hadoop MapReduceとの性能差はおもにアルゴリズムから起因するものとなり,それほど大きなものにはならない可能性があります※3⁠。

※2)
処理によっては,一部ディスクを用いるような実装にはなっているようです。
※3)
ImpalaやPrestoにおいては,LLVMやJVM JITによりランタイムコード生成を行うような実装になっており,著者が以前に実験した環境においては,そのような実装の差も少なからず高速性の差に寄与していました。

おわりに

今回は,ハッシュ結合における具体的な並列アルゴリズムを説明しました。次回は,これまで説明してきたアルゴリズムの性能を定量的に見積り,その見積りを用いた問合わせ最適化について説明する予定です。

参考文献
[1]D. Taniar, C. H.C. Leung, W Rahayu, S. Goel. High-Performance Parallel Database Processing and Grid Databases
[2]M. Kitsuregawa, H. Tanaka, T. Moto-Oka. "Application of hash to data base machine and its architecture", New Generation Computing, Volume 1, Issue 1, pp 63-74, 1983.
[3]M. Kitsuregawa, Y. Ogawa. "Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)", In Proc. VLDB, pp.210-221, 1990.
[4]D. J. DeWitt, R. H Katz, F. Olken, L. D. Shapiro, M. R. Stonebraker, D. A. Wood. "Implementation techniques for main memory database systems", In Proc. SIGMOD, pp.1-8, 1984

著者プロフィール

山田浩之(やまだひろゆき)

日本アイ・ビー・エム株式会社を経て,ヤフー株式会社にて分散型全文検索エンジンの研究開発に従事。2008年上期未踏IT人材発掘・育成事業において高性能分散型検索エンジンの開発によりスーパークリエータに認定。現在は東京大学生産技術研究所にて高性能並列データ処理系の研究開発に従事。博士(情報理工学)。

著書に『検索エンジン自作入門』。