【IT用語】MapReduceとHadoop

金 裕可里, 木田 直人, 三木光範, 廣安知之

ISDL Report　 No. 20091306001

2009年 7月 2日

1  はじめに

近年, Webページの検索や, 地図の検索を行うためにGoogleのサービスが頻繁に利用されており, 必要不可欠なものとなっている.Web検索は, 莫大なデータを扱うのにも関わらず, 瞬時に検索結果を表示させることを実現している. この事実の裏側では, 想像以上に膨大な計算や多数のコンピュータの働きがある.

Googleはその超巨大なコンピュータネットワークを用いて, 膨大なデータ処理を分散化している. そのため, 大量のデータを瞬時に処理することが可能になっている. そのGoogleの分散処理システムはMapReduce[1]と呼ばれており, Googleの検索技術を支えるコア技術である.

本稿では, MapReduceの原理と, MapReduceを実装し, 誰でも簡単に大規模分散処理を実行できることを目的とした オープンソースソフトウェアのHadoop[2]について述べる.

2  MapReduce

2.1  MapReduceの概要

MapReduceとは, 多数のマシンで効率的にデータ処理を行う目的でGoogleによって考案されたフレームワークである. 開発者は分散処理の難しい部分をMapRduceに任せることで, 少ない労力で大規模な処理を実行できるようになる.

次にMapReduceの処理の流れについて述べる. MapReduceは, Fig.1 にあるように, Map処理, シャッフル, Reduce処理の３つの手順から構成されている.

  1. Map処理 入力データ（キーと値のペア）を受け取り, 任意の形式に変換することで, 必要な情報を抽出する. 全てのMap処理は並列実行することができる.

  2. シャッフル

    Mapによって作られたデータを整理し, データを任意の順に並べ替える.

  3. Reduce処理

    データをまとめて最終的に手に入れたい結果を作り上げるプロセスで, データ全体についての整理された処理結果を得る.

    Fig.1: MapReduceの流れ（参考文献[3]より参照）

    MapReduceのデータ処理をより理解するため, 次節に具体例を述べる.

    2.2  MapReduce処理の具体例（転置インデックスの作成）

    転置インデックスとは, 単語とその単語があるWebページをリストとしたものである. 検索エンジンを実現するにあたって, まず必要なものとなる.

    2.2.1  Map

    まず, Fig.3 に示すように, 入力ファイル（Googleが持つ全Webページ）を 複数のファイルに分割する. 分割は一般的に16〜64MBごとに行われる. 入力ファイルが仮に1MBだとすると, 分割されたファイルは数万に及ぶ. 次に, これらのファイルが, 手の空いているPCに対して順に分配される. 各PCはファイルからデータ （キー＝Webページのアドレス, 値＝各Webページの全テキストデータ）を 次々と読み込み, 開発者が用意したMapを呼び出す.

    Mapは新たなデータ（キー＝テキストデータを分割してできた単語, 値＝その単語があるWebページのアドレス）を 出力する. PCはしばらくこれをメモリ上に蓄えるが, 定期的に中間ファイルに保存する. 中間ファイルは Fig.2 の分割関数と呼ばれる関数に従って, あらかじめ指定した数（R）のファイルに分割される.

    Fig.2: Map処理の流れ（参考文献[3]より参照）

    2.2.2  シャッフル

    Fig.4 に示すように, Mapで中間ファイルが生成されると, ネットワークを経由して, Reduce処理をするPCにその場所が伝えられ, シャッフルが始まる.

    シャッフルでは, 中間ファイルに書き込まれたキー（テキストデータを分割した単語）に従って, 全てのデータが整理される. キーはシャッフルによって辞書順にちいさいものから順に選ばれるので Reduceの出力は必ずキーの順にソートされていると言える.

    Fig.3: シャッフル処理の流れ（参考文献[3]より参照）

    2.2.3  Reduce

    Fig.5 に示すように, Reduceは, シャッフルの終わったグループから順に始められる. 各グループの中間ファイルには複数のキー（テキストデータを分割してできた単語）が 書き込まれているので, 同じキーを持つすべての値が集められてReduceが呼び出される.

    Reduceに渡されるReduceの出力はグループごとに 一つのファイルとしてGoogleの巨大分散ファイルシステムのGFS（Google File System）に書き込まれる. 結果としてグループの数（R個）の出力ファイルが生成される.

    Fig.4: Reduce処理の流れ（参考文献[3]より参照）

    2.3  MapReduceが有効な処理

    MapReduceが有効に働く処理に, 以下のものがある.

    • 検索エンジンの転置インデックス作成

    • grep

    • ソート

    • 平均値と分散計算

    • PageRank 計算

    • PageRank の高いウェブページを検索

    • ドキュメント内のリンクの収集

    • ログ解析

    これまでに述べたMapReduceはGoogle独自の技術であり, 誰もが使えるものではない. しかし, 同様の技術を実現しているHadoopと呼ばれるオープンソースソフトウェア（OSS）がある. 次章では分散処理を誰にでも簡単に行うことのできるHadoopに ついて述べる.

    3  Hadoop

    Hadoopとは,大量のデータを手軽に複数のマシンに分散して処理できるオープンソースのプラットフォームである. Hadoopにおけるデータ分散処理のベースとなっているのは前章で述べたMapReduceである.

    Hadoopとは,面倒な分散処理を,プログラマが「簡単に」扱えることを目的としたプラットフォームである.

    3.1  Hadoopの構造

    HadoopはGoogleの基盤ソフトウェアであるGFS(Google File System)と, Mapreduceのオープンソース実装である. HadoopはHDFS(Hadoop Distributed File Systm), Hadoop Mapreduceから構成されている. Fig.6 にあるように, Googleの基盤ソフトウェアに対応させると, 前者は, GFS, 後者はMapreduceに対応する. 分散データベースBig TableもhBaseと呼ばれる オープンソース実装によって実装された.

    Fig.5: Google, Hadoop基盤技術の対応関係（参考文献[2]より参照）

    3.2  HDFSの概要

    HDFSの構造はGFSの構造を踏襲している. GFSとは多数のPC上に構築される分散ファイルシステムのことである. PCを追加するだけで, システムを停止することなくディスク容量・読み込み性能・書き込み性能を拡大でき, スケーラビリティがあるといえる. また, 大容量であり, 数百TBクラスの大規模なディスクの提供を可能にしている. さらに, 障害を自動的に監視・検出・修復が可能である.

    GFSの特徴としては同じファイルを異なるマシンに重複して持たせることで, 一部のマシンが故障してもファイルが失われないという点が挙げられる（冗長化）. Googleでは何万台ものサーバーが常時稼動しているので, 1日に多くのマシンが壊れる. それに耐えられるような耐故障性の高い分散ファイルシステムを持つことは 巨大データを扱う上で必須である.

    3.3  Hadoop MapReduce

    Hadoop MapReduce の構造はGoogle MapReduceの構造を踏襲している. Hadoopのみがもつ機能として, ファイルの分散キャッシュ機能と先に延べたHadoop Streamingがある.

    3.3.1  Hadoop Streaming

    Hadoop はすべてJava で記述されており, MapReduce 処理を書く場合も基本的にはJava でプログラムを書くことが想定されている. ただしHadoop Streamingという拡張パッケージを用いると, C/C++・Ruby・Python など任意の言語と標準入出力を用いて MapReduce 処理を書くことも出来る.

    3.4  Hadoopの利点

    HadoopではMap関数とReduce関数を実装する. Shuffleはすでに実装されているため, 利用者が作るのはMapとReduceだけでよい. Hadoopの仕組みにのっとって機能を実装さえすれば, 自動で分散処理が行えるのだ. 1台では処理にかなり時間がかかるような大量のデータも,Hadoopによって,複数マシンに分散させることで, 驚くべきスピードで処理を行うことができる.例えば,今まで1台でやっていた,あるログ集計処理を, Hadoop (マスタ1台,スレーブ19台)で行うようにしたところ,従来は6時間6分35秒だったのが, Hadoopを使うと,5分34秒になったという結果がでている. 分散コンピューティングと聞くと, 研究室レベルでの活用とか, GoogleやYahoo!, IBMといった大企業しか使えないのではないかと思われがちだ. Hadoopの流儀にしたがって機能を実装すれば簡単に分散処理を実現できる.

    4  まとめ

    MapReduceとHadoopは莫大になったデータをより効率的に, 安価に, 簡単に 処理できるようにするために編み出された工夫である. MapReduceはプログラミングモデルの名前であり, HadoopはMapReduceを活かして作られたオープンソースのプラットフォームである. これらの利点から, Yahoo!をはじめとする様々な企業が積極的に導入しており, 改良も進んでいる.

    5  今後の展望

    米国Amazon. com傘下のAmazon Web Services（AWS）は4月2日, 「Amazon Elastic MapReduce」の ベータ版をリリースしたと発表した. Hadoopクラスタのセットアップはかなり複雑な作業であった. しかし, Amazon Elastic MapReduceは, Hadoopクラスタを大幅に利用しやすくすることを 目指したサービスであるのだ.

    同社によると, Elastic MapReduceを使えば,

    • 手軽なポイント＆クリック操作でHadoopジョブを作成, 実行, 監視, 制御できる.

    • ハードウェアを大量購入することもなく, （ハードウェアを）ラックに収めてネットワークにつないで 管理するといった作業も必要もない.

    • リソースが足りなくなることや, 組織内のほかのメンバーとの共有について心配することもない. 監視もチューニングも不要

    • システムやアプリケーション・ソフトウェアのアップグレードに時間をかける必要もない.

    • 時間単位課金で実行できる.

    という機能がある.

    References

    [1]
    Jeffrey Dean, Sanjay Ghemawat：MapReduce: Simplified Data Processing on Large Clusters, OSDI'04: Sixth Symposium on Operating System Design and Implementation, December, 2004
    [2]
    エヌ・ティ・ティ レゾナント株式会社, 株式会社Preferred Infrastructure：Hadoop調査報告書, 2008
    [3]
    西田圭介：Googleを支える技術 巨大システムの内側の世界, 技術評論社, 2008

    Copyright

    Copyright (C) 2008 Mitsunori Miki, All rights reserved.
Copyright (C) 2008 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2008 Yukari Kin, All rights reserved.
Copyright (C) 2008 Naoto Kida, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.
In no event shall the authors be liable for any damages caused in any way
out of the use of this document．



    4. File translated from TEX by TTH, version 3.67.
    On 02 Jul 2009, 18:10.
    Back to Top