GoogleのMapReduceアルゴリズムを
Javaで理解する
特集:いま再注目の分散処理技術(前編)
株式会社ガリレオ
小山博史
2008/7/8
最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画(編集部)
いま注目の大規模分散処理アルゴリズム
| 今回の主な内容 ・ いま注目の大規模用分散処理アルゴリズム ・ お題【文章で使用されている英字をカウントする】 ・ MapReduceアルゴリズムで実装すると…… ・ MapReduceアルゴリズムを使う利点とは? ・ Apache HadoopとJava関連の分散処理技術 |
最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです(参考「見えるグーグル、見えないグーグル」)。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。
その詳細は「MapReduce : Simplified Data Processing on Large Clusters」というタイトルの論文で「Google Research Publications : MapReduce」から参照できるので、調べてみました。MapReduceを理解するためのサンプルプログラムをJavaで実装して、その利点を探ってみましょう。
お題【文章で使用されている英字をカウントする】
「文章で使用されている英字をカウントする」プログラムを通して、MapReduceを理解してみましょう。例えば、ある英語の文章から、各英字がどれくらい使われているのかを計算したい場合を考えてみましょう。説明を単純にするために、英字以外の文字が入力された場合のエラー処理などは考えていません。読者なら、どんなプログラムを作るでしょうか?
単純にプログラムを書くと、以下のようになります。
package sample; |
![]() |
| 図1 文字数を保持するハッシュテーブル charCount |
ポイントとしては、あらかじめ各文字をカウントする結果を格納する配列を用意しておいて、文字列を先頭から読んで、文字単位でカウントアップをしています。charCountは一種のハッシュテーブル(連想配列、キーとなる文字列と値をセットで保存できるデータ)です。「英字のbyte値やchar値」をキーとして、対応する値を参照したり格納したりしています。
ハッシュ関数は「英字のbyte値やchar値」を「int型の整数値」に変換するだけなので、わざわざ関数にはせずに、「int index = (int)b;」とか、「int index = (int)c;」のようにしています。
| 実行結果 |
a:3 |
では、これを分散処理で実行するためには、どうすればいいでしょうか?
MapReduceアルゴリズムで実装すると……
「文章で使用されている英字をカウントする」プログラムをMapReduceアルゴリズムで実装してみましょう。
分散処理をどのように実行するかも気になりますが、MapReduceアルゴリズムを利用する場合は、まずは「自分が実行させたい処理をどのように実現すればいいのか」という点から理解していくのが早道です。ここでは分散処理そのものではなく、分散処理されるプログラムがどういうものかを理解することに主眼を置くことにします。
■ Mapで分散処理&Reduceでまとめ処理
MapReduceの論文では、図2のようなシステムを構築して実行する方法について報告がされています。
![]() |
| 図2 MapReduceの実行の概要(「MapReduce : Simplified Data Processing on Large Clusters」より引用) |
図2を見て分かるように、入力データを分割して「Map処理」を行うプログラムで分散処理をさせ、その結果を「Reduce処理」を行うプログラムへ渡して、そちらも分散処理をしています。 分散処理を行うプログラムを開始したり停止したりする制御やデータ入出力の同期といったことは「Masterプログラム」が行っています。先ほども述べましたが、本稿ではMasterプログラムの詳細については考えず、MapフェイズとReduceフェイズで動作するプログラムがどういったものなのかを中心に説明をします。
■ MapReduce処理サンプルの実行本体「MapReduceCharCounterApp」クラス
まず、次のようなMapReduceCharCounterAppクラスを作成することにします。先ほどのSimpleWordCounterクラスの代わりにMapReduceCharCounterクラスを使っているだけです。
public class MapReduceCharCounterApp { |
このプログラムを見て分かるように、MapReduceCharCounterクラスでは、count()メソッドとgetCharCount()メソッドを持ちます。
■ 値を保持する「MapEntry」クラス
MapReduceCharCounterクラスから説明をしてもいいのですが、アルゴリズムの説明上、まずはMapEntryクラスというものを用意するところから説明をします。このクラスでは、keyとなる文字と、keyと対応する値であるvalueを保持する単純なものです。単純化のため、アクセッサメソッドは使っていません。
MapEntryオブジェクトについてはソートをする必要があるので、Comparableインターフェイスを実装するようにしています。これを実装すると、equals()メソッドやhashCode()メソッドについても考慮が必要になります(Comparableの実装については、拙著「Javaコレクションフレームワーク 」(ソフトバンククリエイティブ)などをご覧ください)。
public class MapEntry implements Comparable<MapEntry> { |
![]() |
| 図3 MapEntryのクラス図 |
次ページでは、引き続きMapReduceアルゴリズムのサンプルをJavaで実装し、MapReduceアルゴリズムを使う利点について述べます。
| 1-2 |
| INDEX 「特集:いま再注目の分散処理技術(前編)」 | ||
| Page1 | ||
| いま注目の大規模分散処理アルゴリズム お題【文章で使用されている英字をカウントする】 MapReduceアルゴリズムで実装すると…… |
||
| Page2 | ||
| MapReduceアルゴリズムを使う利点とは? Apache HadoopとJava関連の分散処理技術 |
||
いま再注目の分散処理技術 バックナンバー 連載インデックスへ»
- 第1回 GoogleのMapReduceアルゴリズムをJavaで理解する
- 第2回 イロイロな分散処理技術とイマドキのWebサービス
- 最終回 MapReduceのJava実装Apache Hadoopを使ってみた
| Java Solution全記事一覧 |
ホワイトペーパー(TechTargetジャパン)
- 究極の問題解析ツール、逆コンパイラJD-Eclipseとは (2010/3/8)
ライブラリ内で例外が発生! そのクラスのソースコードを調べたい!! 自動で逆コンパイルしてくれる無料Eclipseプラグインがあります - いまさら聞けない「Webサービス」の常識 (2010/2/26)
昨今では企業システムでも使われる「Webサービス」の概念やJava標準のJAX-WSを紹介しJBoss WSでサンプルを作成 - Android 2.1の新機能で作る、美しく燃える“待ち受け” (2010/2/24)
新しく追加された、動く壁紙「Live Wallpaper」機能のサンプル動画を表示し、構成、設定ファイル、実装の仕方を解説します - AWS ToolkitでTomcatクラスタをEC2上に楽々構築 (2010/2/17)
Eclipseで開発したWebアプリを、Google App Engine並みに簡単に、Amazon EC2上にデプロイできる無料プラグインを紹介します
|
|
スキルアップ/キャリアアップ(JOB@IT)
スポンサーからのお知らせ
- - PR -
| 仮想環境の構築とデータ保護の特効薬?! 実績と信頼性の高いパッケージで安心運用 New! |
| 仮想環境のバックアップもこれまでどおり 「まるごと取ってまるごと戻す」簡単運用 |
| おばかアプリ選手権、第4弾開催中!! ムダにカッコよくてくだらない作品求ム! |
| 社内ファイルサーバを“クラウド”に統合 VPN直結「クラウド型ストレージ」を紹介 |
| その数、なんと400台以上! グループ内 サーバの「統合管理」によるメリットは? |
| 美人!? まあまあ? 気になる いやし系!! PV急増で「美人時計」がとった手段とは? |
| .NET編集長が実践する「技術情報検索術」 サンプル・コードを簡単に探す“技”は? |
| 進化を続ける富士通ストレージETERNUS DX 製品開発者の自信を裏付けるものとは何か |
| 運用管理の課題を“2つの観点”から分析 ユーザー満足度の高い「仮想環境」とは? |
- - PR -
お勧め求人情報

**先週の人気講座ランキング**
〜Java編〜
| ◆ | おばかアプリ選手権、第4弾開催中!! ムダにカッコよくてくだらない作品求ム! |
| ◆ | 社内ファイルサーバを“クラウド”に統合 VPN直結「クラウド型ストレージ」を紹介 |
| ◆ | Twitterのアカウントはなぜ突破された? メールによる新手の攻撃手法とその対策 |

| ◆ | もう仮想化のお試しフェイズは終わりだ! Hyper-V 2.0が基幹システムも仮想化 |
| ◆ | 美人!? まあまあ? 気になる いやし系!! PV急増で「美人時計」がとった手段とは? |
| ◆ | クライアント企業から求められる人材 ⇒IT技術と経営戦略を併せ持つ「戦略家」 |

| ◆ | .NET編集長が実践する「技術情報検索術」 サンプル・コードを簡単に探す“技”は? |
| ◆ | 業務効率と情報セキュリティ対策を両立! 手間なく確実に機密情報を守る方法とは? |
| ◆ | 直属上司が海外にいるのエンジニアに見る 【実例】場所に捉われないワークスタイル |

| ◆ | 「仮想化工房」のマイスターが選んだのは VMware、Hyper-V、そしてVirtageだった! |
| ◆ | 進化を続ける富士通ストレージETERNUS DX 製品開発者の自信を裏付けるものとは何か |
| ◆ | 運用管理の課題を“2つの観点”から分析 ユーザー満足度の高い「仮想環境」とは? |

| ◆ | 【CTC事例】約30の基幹システムを統合! 膨大なバッジジョブを制御した方法は? |









