Hadoopはどのように動くのか ─並列・分散システム技術から読み解くHadoop処理系の設計と実装
第7回 データ処理における並列アルゴリズム[2]
はじめに
前回は,
結合処理の並列化方法
結合処理は,
等結合処理における並列化の基本的な方法は,
- データごとに,
結合に用いる属性値 (結合キー) を用いて, 前述の分割方法 (第5回) により, レコードを複数の計算機に分配し - 各計算機において,
通常の単一計算機内での結合アルゴリズム (serial join algorithm) を用いて結合処理を行う
1.により結合キーが同一のレコードは同じ計算機に分配されるので,
なお,
- ※1
- 第5回で述べたとおり,
通常は, データは分割関数により事前に複数の計算機に分配されているため, 結合のために当該データをさらにもう一度分割し直す当該処理は 「再」 分割処理となるわけです。 - ※2
- Fragment-and-Replicate Joinとも呼ばれます。
ソートマージ結合における並列アルゴリズム
ソートマージ結合は,
ソートマージ結合の並列化は,
- 並列ソートマージ結合1
- 各計算機のデータを読み出し,
結合キーで分割 (場合によっては, 当該分割データをローカルに一時的に保存) - 各計算機における当該分割データを各ノードに分配
- 各計算機でソートマージ結合を実行
- 各計算機のデータを読み出し,
上記の方法は,
- 並列ソートマージ結合2
- 各計算機のデータを読み出し,
結合キーで分割しつつ, それぞれの分割データをメモリ空間上でキー順に整列 (場合によっては, 当該整列データをローカルに一時的に保存) - 各計算機における整列済み当該分割データを各ノードに分配
- 各計算機で各々のデータにおいて
(マルチウェイで) マージ処理を行い, 各々の整列済みデータを用いて結合を行う
- 各計算機のデータを読み出し,
いずれの結合方法においても,
Hadoop MapReduceにおける結合処理
並列ソートマージ結合2を見ると,
Hadoop MapReduceの大枠としては,
なお,
Hadoop MapReduceにおける整列処理
Hadoop MapReduceのフレームワーク自体は,
整列処理フレームワークとしてのHadoop MapReduceは,
TeraSortにおいては,
- ※3
- Sort Benchmark Home Pageを見ると,
2009年と2013年で2度ワールドレコードを記録しているようです。
おわりに
今回は,
- 参考文献
- [1] D. Taniar, C. H.
C. Leung, W Rahayu, S. Goel, High-Performance Parallel Database Processing and Grid Databases - [2] J. L. Wolf, D. M. Dias, P. S. Yu. "A Parallel Sort Merge Join Algorithm for Managing Data Skew", IEEE Transactions on Parallel and Distributed Systems, Volume 4 Issue 1, pp.
70-86, 1993. - [3] Winning a 60 Second Dash with a Yellow Elephant, http://
sortbenchmark. org/ Yahoo2009. pdf, 2009.
バックナンバー
Hadoopはどのように動くのか ─並列・分散システム技術から読み解くHadoop処理系の設計と実装
- 第22回[最終回] まとめと本連載で解説できなかったこと
- 第21回 Sparkの設計と実装[2]~Sparkにおけるデータ共有の仕組みと耐障害性の実現方法
- 第20回 Sparkの設計と実装[1]~登場の背景とデータ処理の特徴
- 第19回 Impalaの設計と実装[3]
- 第18回 Impalaの設計と実装[2]
- 第17回 Impalaの設計と実装[1]
- 第16回 並列データ処理系 Apache Tez
- 第15回 計算機クラスタのためのリソース管理基盤 Hadoop YARN
- 第14回 Hadoopの設計と実装~並列データ処理フレームワークHadoop MapReduce[2]
- 第13回 Hadoopの設計と実装~並列データ処理系Hadoop MapReduce[1]