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

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

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

はじめに

前回は,結合処理の並列化における基本戦略について説明し,ソートマージ結合における具体的な並列アルゴリズムを説明しました。今回は,ImpalaやPrestoに加えて,Apache SparkやHadoop MapReduceのMap Joinにおいても用いられているハッシュ結合における具体的な並列アルゴリズムを説明します。

ハッシュ結合における並列アルゴリズム

ハッシュ結合は,2つのデータにおいて同一の属性値をもつレコードを見つける方法として,レコードのハッシュ値を用いるものです※1)⁠すなわち,当該方法においては,一方のデータのすべてのレコードの結合キーに対してハッシュ関数を用いてハッシュ値を計算し,当該ハッシュ値からなるハッシュ表を事前に構築しておき,他方のデータのレコードの結合キーに対して同一のハッシュ関数から得られたハッシュ値を用いてハッシュ表を参照することにより,同一の属性値を持つ一方のレコードを見つけ出します。

ハッシュ結合は,多くの場合,ソートマージ結合よりも高速な結合処理アルゴリズムであると考えられています。この理由については,後の回でそれぞれの計算量を見ながらまたくわしく述べる予定です。ハッシュ結合についてもう少しくわしく知りたい方は,Wikipediaなどを参照してください。

ハッシュ結合の並列化は,前回説明した並列化の基本的な方法を適用して,次のように行うことができます。

並列ハッシュ結合1
  1. 各計算機において,双方のデータを読み出し,それぞれを結合キーで分割し,当該分割データを各ノードに分配。この際,分配先のノードにおいて分割データを二次記憶に格納
  2. 各計算機でハッシュ結合を実行(一方のデータからハッシュ表を構築して,他方のデータを用いてハッシュ表を参照)

上記の方法は,1.において,分割データを各ノードの二次記憶に格納するため,総計のI/O量が多くなる傾向があります。このため,次のような改良方法が用いられることがあります図1)⁠

図1 並列ハッシュ結合

図1 並列ハッシュ結合

並列ハッシュ結合2
  1. 各計算機において,まず一方のデータを読み出し,結合キーで分割し,当該分割データを各ノードに分配。分配先のノードにおいては,データを二次記憶に格納せずに,そのままハッシュ表を構築(ハッシュ表自体は,場合によっては,二次記憶に格納)
  2. 各計算機において,他方のデータを読み出し,結合キーで分割し,当該分割データを各ノードに分配。当該分割データは,分配先のノードにおいて,二次記憶に格納せずに,そのままハッシュ表を参照して結合を実施

この方法においては,並列ハッシュ結合1と比較して,1.のフェーズにおける書き込みと2.のフェーズにおける読み出しのI/O量を削減できる可能性があります。

並列ソートマージ結合と同様に,いずれの並列ハッシュ結合においても,たとえば結合キーに偏りがある場合においては,ハッシュ表の大きさにばらつきが出てしまい,必ずしも結合処理を複数の計算機に均等に分割することは困難です。この問題に対しては,実際のデータの分布などに応じてハッシュ表を動的に分割することにより負荷分散処理を行う手法が提案されています[2])⁠

なお,上述のような並列ハッシュ結合の方法は,1980年代に東京大学で研究開発されていたGraceなる並列データベースマシンにおいて初めて提案されたことから,⁠Parallel)Grace Hash Join(コラム参照)と呼ばれることがあります。

※1)
前回述べたとおり,等結合を対象として話を進めていきます。

Grace Hash Join

データを動的にハッシュ分割(クラスタリング)してそれぞれのパーティション(クラスタ)で独立に結合を行う,というアイデアはGraceという並列データベースマシンで文献[3]によって提案されたものですが,当時のGraceはデータをハッシュ分割して,それぞれのクラスタにおいて独自のハードウェアソータを用いてソートマージ結合を行うものでした。その後,文献[4]において,クラスタリングの際にメモリ上で結合の一部の処理(一部のデータに対してハッシュ表の構築と当該表への参照)を行うという方法が提案され,当該方法においては結合方法としてハッシュ結合が用いられていました。文献[4]においては,従来のGraceのクラスタリング方法との正当な比較を行うため,Graceにおけるソートマージ結合の部分をハッシュ結合に変更をしたものをGrace Hash Joinと名づけ,自らの手法をHybrid Hash Joinとして,それらの比較を行いました。このような経緯から,データを動的にハッシュ分割をして各ノードでハッシュ結合をするようなシンプルな並列ハッシュ結合の方法をGrace Hash Joinと呼ぶようになったと考えられます。

著者プロフィール

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

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

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

コメント

コメントの記入