第13回　Hadoopの設計と実装～並列データ処理系Hadoop MapReduce［1］

はじめに

第一部では、Hadoopなどの並列データ処理系の基礎である並列データベース技術や分散システム技術を解説してきました。第二部では、実際の処理系により焦点を当て、それらの設計と実装を見ていきます。

第二部では、最初の4回を用いて、Apache Hadoopの並列データ処理系であるHadoop MapReduceを始めとし、当該処理系のリソース管理を行うYARNおよび、汎用的な並列データ処理系であるTezについて解説を行う予定です。

今回は、MapReduceにおける設計方針や特徴について解説します。

MapReduceとは

MapReduceは、複数の計算機上で効率的に処理を行うためのデータ処理用のプログラミングモデルと、そのプログラミングモデルが動作する処理系の実装であり、GoogleのJeff Deanらにより開発が始められました。MapReduceの代表的なランタイム処理系には、Googleで利用されている実装（以下、Google MapReduce［1］）のほかに、オープンソース実装であるApache Hadoopがあります。一般的に、MapReduceは以下のような特性を有します。

高い性能スケーラビリティ（スケーラビリティについては第6回を参照してください）
高い耐障害性（たとえば、ジョブの実行中に一部の計算機が故障してもジョブが動作し続ける特性。くわしくは第11回を参照してください）
上記2つの特徴を実現する機能をプログラマから隠蔽した抽象化インターフェース

現在のMapReduceの多くは、上記の3つの特徴を満たすために、ユーザによって指示された処理を実行するMapReduce処理系と、高速なファイルの読み書きが可能な分散ファイルシステムによって構成されます（図1・※1⁠）⁠。以下では、上記の3つの特徴がそれぞれどのような設計方針により実現されているかについて解説します。

高い性能スケーラビリティを実現する設計方針

MapReduceにおいては、次の2つの設計方針により、高い性能スケーラビリティを実現します。

ディスクドライブの入出力性能を最大限に活用する
ネットワーク入出力を最小限に抑える

MapReduceが用いる分散ファイルシステムにおいては、通常、64MBから1GB程度のブロックと称される入出力単位でディスクドライブにアクセスを行うため[2]⁠、従来のNFS（Network File System）などの分散ファイルシステムと比較して、ディスクドライブの有する高いシーケンシャルアクセス性能を活用することができます。

また、各計算機においては、自計算機のローカルにあるデータの走査を基本とすることにより、無共有型のアーキテクチャ（第2回）において、高いスケーラビリティ（第6回）を実現することが可能です。たとえば、各計算機のディスク性能が100MB/sであり、1000台の計算機により各々が並列にディスクを走査する場合は、100GB/s（＝100MB/s×1000）に近い性能を出すことが可能です。

一方、走査でなく、索引などを用いてアクセスを行う場合は、問い合わせに必要なデータのみにアクセスすることができる反面、多くの場合、ランダムアクセスとなり、ディスクドライブの高いシーケンシャルアクセス性能を活用できません。また、特に並列構成においては、グローバル索引（第6回）と称される索引を必要とし、当該ケースにおいては、ネットワークを介した計算機間のインタラクションが発生する場合があるため、計算機の数に比例してスループットを上げることが必ずしも容易ではありません。

また、MapReduceにおいては、ネットワーク入出力を最小限に抑えるべく、転送データの圧縮を始めとする種々の効率化技法が用いられています。たとえば、MapReduceで集約処理を行う場合、Mapの出力データを集約キーによってネットワークを介して分配し、Reduce側でキーごとの集約を行うのが通常ですが、可換則と結合則を満たす集約処理の場合は、Map側で集約処理を可能な限り行う、いわゆる部分集約という処理を行い、ネットワークへのデータ転送量の削減を試みています。

なお、このような方針は、近年の計算機構成を考慮して設計されていると考えられます。すなわち、近年におけるコモディティサーバは複数のコアや複数のディスクドライブを有することが一般的であり、たとえば、4台のディスクドライブを有する計算機においては400MB/s（＝100MB/s×4）程度の読み込み性能が出せる可能性があります。一方、ネットワークスイッチにおいては、10GbpsのEthernetスイッチが普及しつつあるものの、1Gbps（＝128MB/s）のものがいまだ主流であり、つまり、多くの場合、ネットワークスイッチのI/O性能が各計算機のI/O性能よりも低いと想定されるため、上記のような設計方針になっていると見ることができます。

高い耐障害性を実現する設計方針

複数の計算機から構成されるシステムにおいては、計算機の数に比例してシステム全体の故障率が上がるため、高い耐障害性を有する必要があります。すなわち、上記の設計方針により、複数の計算機を活用した高い性能スケーラビリティが得られるものの、たとえば、ジョブの処理の途中に計算機が故障してしまった場合に、当該処理をはじめから再開していては、高い性能を実現できているとはいえません。

MapReduceでは、分散ファイルシステムにおいてレプリケーション（第11回）を用いることにより、ブロックの高い可用性を実現します。また、MapReduce処理系が中間データを二次記憶に適宜書き出すことにより（第11回⁠）⁠、ジョブの処理の途中に障害が発生した場合であっても、一部の処理だけを再度実行すればいいような設計となっています。

抽象化インターフェース

上記の2つの特徴を実現する機能を有する並列データ処理系であれば、高い性能を実現できますが、処理系を用いるプログラマが当該機能を都度記述するのは、困難であり非効率的であると考えられます。MapReduceにおいては、map()とreduce()なる2つの関数だけをプログラマに定義させ、その他の処理はすべて処理系で行うという設計方針をとります。map()とreduce()は制限されたインターフェースであるものの、記述できる処理の内容は幅広く、当該特性がHadoopがフレームワークと称される所以でしょう。すなわち、MapReduceは、プログラマに高い記述性と生産性を提供しつつ、高いデータ処理性能を提供するソフトウェアであるといえます。

おわりに

今回は、Hadoop MapReduceの設計方針における特徴について説明しました。次回は、Hadoop MapReduceの実装における特徴について説明します。

参考文献: ［1］Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation - Volume 6、 OSDI⁠’04、 pages 10?10、 Berkeley、 CA、 USA、 2004. USENIX Association.