Hadoopはどのように動くのか ─並列・分散システム技術から読み解くHadoop処理系の設計と実装
第6回 データ処理における並列アルゴリズム[1]
はじめに
前回は,
並列システムや並列アルゴリズムにおける性能指標
並列システムや並列アルゴリズムを評価する場合においては,
- スピードアップ
(Speed-up) - スケールアップ
(Scale-up)
スピードアップは,
これらの指標においては,
スピードアップにおいては,
データ処理の並列アルゴリズムやデータ処理システムは,
並列データ処理系においては,
- ※1)
- 計算機の数を増やしてシステムの処理能力を上げることをスケールアウト
(scale horizontally) と言い, 単一マシンにおいてプロセッサなどの計算資源を増やすことをスケールアップ (scale vertically) と言うことがありますが, これらと混同しないようにご注意ください。これらのスケーラビリティの指標として, 上記2つが存在します。 - ※2)
-
第1回において述べた
「スケーラブルである」 とは, 高いスケーラビリティを有することを意味します。
データ処理のアルゴリズム
データ処理において用いられる主要なオペレータとしては,
選択処理は,
一方,
まとめると,
- 選択処理
(Selection) - スキャン
(Scan) - 索引スキャン
(Index Scan)
- スキャン
- 結合処理
(Join) - ソートマージ結合
(Sort-Merge Join) - ハッシュ結合
(Hash Join) - ネステッドループ結合
(Nested Loop Join)
- ソートマージ結合
以降においては,
選択処理における並列アルゴリズム
選択処理を実現するには,
選択処理は単一のデータを読み出すだけなので,
一方,
また,
- ※3)
- 非クラスタ化索引とは,
索引におけるキーの順番が, 当該キーが参照するレコードの順番と異なるような索引構造です。非クラスタ化索引は, 二次索引とも呼ばれます。クラスタ化索引とは, 索引におけるキーの順番が, 当該キーが参照するレコードの順番と同一であるような索引構造です。
Hadoopなどにおける選択処理
HadoopのMap処理においては,
- ※4)
- 実際には,
JobTrackerなどのマスタがどのMapperがどのブロックを読むかを決定します。このとき, 各計算機は必ずしも同一の計算機からブロックを入力するとは限りません。
おわりに
今回は,
- 参考文献
[1] D. DeWitt, J. Gray, "Parallel database systems: the future of high performance database systems", Communications of the ACM 35, 6, pp.85-98, 1992. [2] D. Taniar, C. H.C. Leung, W Rahayu, S. Goel, High-Performance Parallel Database Processing and Grid Databases [3] J. Liebeherr, E. R. Omiecinski, I. F. Akyildiz, The Effect of Index Partitioning Schemes on the Performance of Distributed Query Processing, IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,VOL.5, NO. 3, JUNE 1993.
バックナンバー
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]