入門
Kazuki Ohta
(株) Preferred Infrastructure
最高技術責任者<kzk@preferred.jp>

1
2011年8月6日土曜日

自己紹介l 太田一樹l (株) Preferred Infrastructure, CTOl エンタープライズ検索エンジン「Sedue」「Hadoop徹底入門」
l Hadoopユーザー会の立ち上げ
Hadoop-Gfarm with 三上さんl Hadoop徹底入門の著者
l 個人サイトl http://kzk9.net/l @kzk_moverl 東京大学情報科学科 石川研究室 修士卒業
l 並列I/Oシステムの研究l Project: IOFSL (I/O Forwarding and Scalability Layer)2
2011年8月6日土曜日

Agenda•大規模データ処理とその課題•

Hadoopとは?
– ソフトウェア構成– 内部アーキテクチャ– エコシステム•

MapReduce入門– MapReduceの背景– MapReduceの計算モデル

3
2011年8月6日土曜日

大規模データ処理とその課題

4
2011年8月6日土曜日

大規模データ処理とは?
l 「大量のデータを処理し、その中から知見を抽出すること」
l データを価値に変えるl 例1: バスケット分析l 大量のPOSデータを分析し、商品Aと同時によく買われている商品を分析する (例: ビールとおむつ)l その2つを近くに陳列する事で、収益の向上が見込めるl 例2: 交通流量分析l 自動車には位置情報を収集できるセンサーが搭載されており、そのデータを解析することで、頻繁に渋滞が起こる箇所の特定が可能l 道路の増強を行なうことで、渋滞改善が見込める
5
2011年8月6日土曜日

大規模データ処理の抱える問題点l

大量のデータを保存・処理する際の問題l

問題1: データの保存l 数百TB 〜 数PBレベルのデータを、安全に保存する必要が有るl 1つのディスクに収まらないので、大量のディスクを使用するl 数十〜数千ノード程度のクラスタシステム => 故障率の大幅増加
l ディスクの故障が起きても、データが失われないような設
計が必要

l

問題2: データの処理l 保存されたデータに対して処理を行なう必要が有る
l 処理プログラムの開発の効率性・再利用性・デバッグ環境l データ処理中のノード故障にも対処する必要が有る
6

2011年8月6日土曜日

Hadoopとは?

7
2011年8月6日土曜日

Hadoopとは?
l Google社が保有する大量データ処理基盤技術のOSSク

ローンl Apacheプロジェクトにて全ソースコードが公開

l 大量データの保存技術 “Google File System”l 大量データの処理技術 “MapReduce”l これらの技術を、学術論文を元に再実装

l Java言語で記述されており、Yahoo!では4000台での稼働実績有l 本日は “MapReduce” を中心に解説します85
2011年8月6日土曜日

Hadoop Distributed File Systemとは?
l

大量のコモディティマシンを使用し、大規模データを安全に保存するためのソフトウェアl データは自動的に複数箇所にコピーされ、故障時にもデータが失われる確率が低い (例: 複数ラック, 複数DC)l マスターノードが、大量のスレーブノードを管理・監視

9
2011年8月6日土曜日

MapReduceとは?
l HDFS上に構築された、大量データ処理基盤

l Mapフェーズ, Reduceフェーズの処理を記述するだけで、クラスタ環境での並列処理可能l 処理中のマシンの故障等も自動的にフェイル
オーバー
HDFS

HDFS

10
2011年8月6日土曜日

の開発者• Cloudera (元: Yahoo Research) のDoug Cutting氏が開発– 元々はLuceneのサブプロジェクト– Dougの子供の持っているぬいぐるみの名前から命名• 現在は、Yahoo!を中心にFacebook,
Cloudera等の企業の従業員が主に開発に従事している11
2011年8月6日土曜日

Hadoopの使用事例
l 機械学習処理l ユニークユーザー数算出
l ベイズ推定l 広告ターゲティングl クラスタリングl マーケティングデータ解析
l 回帰分析l Twitter・Blog解析
l ゲノム解析処理l POSデータ解析
l 金融取引データ処理l 時系列バスケット分析l スマートグリッドl センサデータ解析
l 異常値検出・位置情報分析 l ...
l Webログ解析l 国外では Yahoo!, Facebook, eBay, Amazon等、多くの企業が活用
l 国内でも 楽天・クックパッド・リクルート・NTTデータ等が活用
12
2011年8月6日土曜日

Google関連参考論文&スライド• The Google File System– Sanjay Ghemawat, Howard Gobioff, and Shu-Tak
Leong, SOSP 2003
• MapReduce: Simplified Data Processing on Large
Clusters– Jeffrey Dean and Sanjay Ghemawat, SOSP 2004
• Parallel Architectures and Compilation Techniques(PACT) 2006, KeyNote– http://www.cs.virginia.edu/~pact2006/
program/mapreduce-pact06-keynote.pdf
13
2011年8月6日土曜日

MapReduceに関する学会• 分散システム, HPC, 自然言語処理, 機械学習, etc.
• MAPREDUCE’10– The First International Workshop on MapReduce and its
Applications– HPDC 2010併設– http://graal.ens-lyon.fr/mapreduce/• MAPRED‘2010– The First Internatinal Workshop on Theory and Practice of
MapReduce– CloudCom 2010併設– http://salsahpc.indiana.edu/CloudCom2010/
mapreduce2010.html
14
2011年8月6日土曜日

MapReduce	
  を利⽤用している分野
広告解析

画像・動画処理

バイオインフォマティクス /	
  医療情報ネットワーク処理

機械翻訳

シミュレーション

地理情報処理統計処理

情報抽出、テキスト解析

数値解析

機械学習 / データマイニング

グラフアルゴリズム

検索クエリ分析
情報検索
スパム ・マルウェア判定

http://atbrox.com/2010/05/08/
mapreduce-­‐hadoop-­‐algorithms-­‐in-­‐academic-­‐papers-­‐may-­‐2010-­‐update/

その他:	
  Analyzing	
  Human	  Genomes	
  with	  hadoop
http://www.cloudera.com/blog/2009/10/analyzing-­‐human-­‐genomes-­‐with-­‐hadoop/15
2011年8月6日土曜日

MapReduceの主な適⽤用可能分野
1.
2.
3.
4.
5.

Modeling	
  true	  riskCustomer	
  churn	
  analysis
Recommendation	
  engineAd	
  targetingPoS	
  transaction	
  analysis

6. Analyzing	
  network	
  data	  to	
  predict	
  failure
7. Threat	
  analysis
8. Trade	
  surveillance
9. Search	
  quality
10. Data	
  “sandbox”

Ten	
  Hadoopable	
  Problems
http://www.slideshare.net/cloudera/20100806-­‐
cloudera-­‐10-­‐hadoopable-­‐problems-­‐
webinar-­‐4931616
16
2011年8月6日土曜日

Yahoo!の使⽤用事例
約25000ノード
20%が本番⽤用、60%が研究⽤用
広告最適化、検索インデックス作成、RSSフィード、ス
パムフィルタ、パーソナライズ化

ログデータの分析時間の短縮
過去3年分の解析が 26⽇日 -­‐>	
  20分

分析アプリケーションの開発時間の短縮
C++	
  からPythonに代わり 2-­‐3週	
  -­‐>	
  2-­‐3⽇日
http://www.publickey1.jp/blog/09/hadoophadoop_worldny_2009.html
17
2011年8月6日土曜日

Hadoopに関わる企業•

Cloudera– HadoopをEnterprise向けに提供する企業– 多数のコミッターを抱える– http://cloudera.com/•

Yahoo!, Inc.
– 検索エンジンバックエンド等にHadoopを使用– 米国で最大級の使用事例– Pig, Oozie等の周辺ソフトウェアも開発•

Facebook– ログ解析プラットホーム等にHadoopを使用– Hive等の周辺ソフトウェアも開発
18
5

2011年8月6日土曜日

Hadoopの開発状況

198
2011年8月6日土曜日

Hadoop参考文献• Hadoop公式サイト– http://hadoop.apache.org/core/– Wiki: http://wiki.apache.org/hadoop/• インストール方法・チュートリアル・プレゼン資料など• Hadoop, hBaseで構築する大規模データ処理システム
on Codezine– http://codezine.jp/a/article/aid/2448.aspx• オープンソース分散システム「Hadoop」解析資料– http://preferred.jp/2008/08/hadoop.html• Hadoopユーザー会メーリングリスト– http://groups.google.co.jp/group/hadoop-jp
20
2011年8月6日土曜日

性能• Apache Hadoop wins TeraSort Benchmark– http://sortbenchmark.org/– 規定フォーマットの100Tデータをソート– Yahoo!のチームによるレポート• http://sortbenchmark.org/Yahoo2009.pdf– 173 minutes, 3452 nodes• 40 nodes per rack
• 2 quad core Xeon
• 8 GB Memory• 4 Sata Disks• 1Gbps Ethernet, 8Gbps uplinks per rack
• 秒間約570MB/sec
21
2011年8月6日土曜日

性能測定

22
2011年8月6日土曜日

Hadoopのエコシステムl

Hadoopを軸に、大小様々なソフトウェアが開発されている

l

Hive
l SQLライクな言語で大量データの解析が可能
l SELECT user, COUNT(1)FROM log_tbl
WHERE user.sex == “male”
GROUP BY user

l

HBase
l HDFS上に構築された分散データベースl リアルタイム分析処理を可能にするミドルウェア

HiveQL

23
2011年8月6日土曜日

MapReduceとは?

24
2011年8月6日土曜日

問題• Web、大規模インターネットサイト、モバイルキャリア
等では、非常に大規模なデータが蓄積されている– 例えばWebページのサイズを考えてみる• 200億ページ * 20KB = 400 TB– Disk読み込み性能は50MB/sec (SATA)• 1台では読み込むだけでも約100日• 保存するだけでも500Gのディスクが1000個程度必要• このデータを効率的に処理したい25
2011年8月6日土曜日

解決方法
• お金
– とにかく大量のマシンを用意– 1000台マシンがあれば1台で400G処理すればok– 読み込むのに8000秒程度で済む

26
2011年8月6日土曜日

お金だけでは解決しない• プログラミングが非常に困難になる– プロセス起動– プロセス監視– プロセス間通信– デバッグ– 最適化– 故障時への対応• しかも、新しいプログラムを作る度にこれらの問題をいちいち実装する必要がある
27
2011年8月6日土曜日

既存の並列プログラミング環境• MPI (Message Passing Interface)– 並列プログラミングのためのライブラリ• スパコンの世界では主流– プログラマは各プロセスの挙動を記述• 通信プリミティブ(Send, Recv, All-to-All)が提供されており、それを用いてデータ通信を実現• SPMD– 利点• 通信パターンなどをプログラマがコントロールでき、問題に対して最適なプログラムを記述する事ができる
28
2011年8月6日土曜日

MPIプログラムの例

29
2011年8月6日土曜日

MPIの問題点• 問題点– 耐障害性への考慮が少ない• アプリケーションが独自にチェックポイント機能を実装– 1万台以上の環境で計算するには耐えられない• 1台が1000日程度で壊れるとすると、1日で10台程度壊れる• 壊れる度にチェックポイントから戻す必要があり、非常に面倒くさい– 通信パターンなどを記述する作業が多くなり、実際のアルゴリ
ズムを記述するのにたどり着くまで時間がかかる

30
2011年8月6日土曜日

そこでMapReduce• 大体の大規模データ処理を行う問題に特化したプログラミングモデル– アルゴリズムの記述のみにプログラマが集中できる– 世の中の問題全てに対して最適なモデルではない• ライブラリ側で面倒な事を全て担当してくれる– 自動的に処理を分散/並列化– ロードバランシング– ネットワーク転送・ディスク使用効率化– 耐障害性の考慮• 1ノードで失敗したら違うノードで自動的に再実行– MapReduceが賢くなれば、それを使う全てのプログラムが賢くなる31
2011年8月6日土曜日

MapReduce型の処理• WordCount• Grep• Sort• Log Analysis• Web Graph Generation• Inverted Index Construction• Machine Learning– NaiveBayes, K-means, Expectation
Maximization, etc.

32
2011年8月6日土曜日

MapReduce	
  を利⽤用している分野
広告解析

画像・動画処理

バイオインフォマティクス /	
  医療情報ネットワーク処理

機械翻訳

シミュレーション

地理情報処理統計処理

情報抽出、テキスト解析

数値解析

機械学習 / データマイニング

グラフアルゴリズム

検索クエリ分析
情報検索

大量データに対するバッチ処理にマ

スパム ・マルウェア判定

ッチしやすいhttp://atbrox.com/2010/05/08/
mapreduce-­‐hadoop-­‐algorithms-­‐in-­‐academic-­‐papers-­‐may-­‐2010-­‐update/33

2011年8月6日土曜日

Googleでの使用率3422
2011年8月6日土曜日

MapReduceの計算モデル

35
2011年8月6日土曜日

MapReduceの実行フロー36
2011年8月6日土曜日

MapReduceの実行フロー• 入力読み込み– <key, value>*• Map– map: <key, value><key’, value’>*• Shuffle– shuffle: <key’, reducers>

destination reducer• Reduce– reduce: <key’, <value’> * ><key’’, value’’>*• 出力書き出し– <key’’, value’’>*37
2011年8月6日土曜日

例: ワードカウント• 擬似コード

map(string key, string value) {foreach word in value:emit(word, 1);}
reduce(string key, vector<int> values) {int result = 0;
for (int i = 0; I < values.size(); i++)result += values[i];emit(key, result);}
38
2011年8月6日土曜日

MapReduceの実行フロー<k, v>*<k’, v’>*<k, v>*

Map

Data<k, v>*<k’, v’>*<k, v>*

Map

Data<k, v>*<k’, v’>*<k, v>*

Data<k’, <v’>*>*

Map<k’’, v’’>*

Reduce

Data

ReduceData

Shuffle<k’, <v’>*>*<k’’, v’’>*39
2011年8月6日土曜日

入力文書: doc1

例: ワードカウント

foo foo foo
bar bar buzz

Data

Data

Data

Map

Map

Reduce

Data

ReduceData

ShuffleMap
40

2011年8月6日土曜日

入力文書: doc1

例: ワードカウント

foo foo foo
bar bar buz

Data

Map

doc1: foo
doc1: foo

Data

Map

doc1: foo
doc1: barData
doc1: bar
doc1: buz
2011年8月6日土曜日

Reduce

Data

ReduceData

ShuffleMap
41

入力文書: doc1

例: ワードカウント

foo foo foo
bar bar buz
doc1: foo
doc1: foo

Map

Data
doc1: foo
doc1: bar

Map

Data
doc1: bar
doc1: buz

Data

Reduce

Data

ReduceData

ShuffleMap
42

2011年8月6日土曜日

入力文書: doc1

例: ワードカウント

foo foo foo
bar bar buz
doc1: foo
doc1: foo

foo: 1
foo: 1

Map

Data
doc1: foo
doc1: bar

bar: 1
foo: 1

Data

Reduce

Data

Map

Data
doc1: bar
doc1: buz

Data

Reducebar: 1
buz: 1

Map
43

2011年8月6日土曜日

入力文書: doc1

例: ワードカウント

foo foo foo
bar bar buz
foo: 1
foo: 1Data

Mapbar: 1
foo: 1Data

Mapbar: 1
buz: 1

Data

bar: <1, 1>
buz: <1>

ReduceData

foo: <1, 1, 1>

Reduce

Data

Map
44

2011年8月6日土曜日

入力文書: doc1

例: ワードカウント

foo foo foo
bar bar buz

Data

Map

bar: <1, 1>
buz: <1>

Reduce
Data

Map

Data

foo: <1, 1, 1>

Reduce
Data

Data

Map
45

2011年8月6日土曜日

入力文書: doc1

例: ワードカウント

foo foo foo
bar bar buz

Data

Map

bar: <1, 1>
buz: <1>

bar: 2
buz: 1

ReduceData

Mapfoo: <1, 1, 1>

Data
foo: 3

Reduce
Data

Data

Map
46

2011年8月6日土曜日

入力文書: doc1

例: ワードカウント

foo foo foo
bar bar buz

Data

bar: 2
buz: 1Map
Reduce

Data

Data

Map

foo: 3

Reduce
Data

Data

Map
47

2011年8月6日土曜日

MapReduceの特徴• データ通信– 各Map処理、Reduce処理は完全に並列に実行可能– マシンを増やせばその分処理能力が増える• 耐故障性– 失敗したMap, Reduce処理は他のノードで再実行される– 遅いMap, Reduce処理についても同じ• ローカリティ– データのある場所で計算を始めれば、ネットワークを使う必要がなくなる• Moving Computation is Cheaper Than Moving Data48
2011年8月6日土曜日

100TBソートの実行時間内訳
出典: YahooのTeraSortレポート

49
2011年8月6日土曜日

Hadoop MapReduce• Master/Slave アーキテクチャ• JobTracker– Master– JobをTaskに分割し、Taskを各TaskTrackerに分配• Job: MapReduceプログラムの実行単位• Task: MapTask, ReduceTask– 全てのTaskの進行状況を監視し、死んだり遅れたりした
Taskは別のTaskTrackerで実行させる• TaskTracker– Slave– JobTrackerにアサインされたTaskを実行• 実際の計算処理を行う
50
2011年8月6日土曜日

MapReduce Architecture
JobTracker
TaskTracker

5151
2011年8月6日土曜日

Hadoopのシステム構成
Master-Slaveアーキテクチャ

52
2011年8月6日土曜日

MapReduce用の上位言語

53
2011年8月6日土曜日

Hive• SQLライクな言語で、MapReduceジョブを記述– Javaを書かずに、必要なデータを得るためのジョブを簡単に作成できる
hive> CREATE TABLE shakespeare (freq INT, word STRING)ROW FORMAT DELIMITED FIELDS TERMINATED BY ‘\t’ STOREDAS TEXTFILE;
hive> LOAD DATA INPATH “shakespeare_freq”
INTO TABLE shakespeare;hive> SELECT * FROM shakespeare LIMIT 10;
hive> SELECT * FROM shakespeare
WHERE freq > 100 SORT BY freq ASC
LIMIT 10;54
2011年8月6日土曜日

Pig• MapReduce用のDSL (Domain Specific Language)
Pig Latin
A = LOAD ‘myfile’AS (x, y, z);
B = FILTER A by x> 0;
C = GROUP B BY x;
D = FOREACH A GENERATE
x, COUNT(B);
STORE D INTO ‘output’;

pig.jar:•parses•checks•optimizes•plans execution•submits jar
to Hadoop•monitors job progress

Execution Plan
Map:
FilterReduce:Count

55
2011年8月6日土曜日

Enjoy Hadoop J
Thank you!

56
2011年8月6日土曜日

57
2011年8月6日土曜日

第二部

58
2011年8月6日土曜日

Hadoopと既存システムとの連携

59
2011年8月6日土曜日

既存システムとHadoopの住み分け• データセンターでは既に様々なコンポーネントが存在している– データベース– データウェアハウス
– ファイルサーバー– バックアップシステム• Hadoopはそのようなコンポーネントの1つでしかない– その中にhadoopをどのようにfitさせれば良いか？

60
71
2011年8月6日土曜日

RDBMS vs Hadoop
RDBMS

HadoopTransactions/secondConcurrent Queries

1000’s

n/a

100’s

10’s

Update Patterns

Read / Write

Append Only

Join Complexity

100’s of tables

Arbitrary keys

Schema Complexity

Structured

Structured or
Unstructured

Total Data Volume

100’s of TBs

10’s of PBs

Per Job Data
Volume10’s of TBs

10’s of PBs

Processing Freedom

SQL

Hardware Profile

High-end servers

MapReduce,
Streaming, Pig,
Hive, etc.
Commodity /Utility Hardware
61
72

2011年8月6日土曜日

Hadoopの適用例

62
2011年8月6日土曜日

Hadoopのアーキテクチャ

63
2011年8月6日土曜日

Hadoopの内部構成• Hadoop Distributed File System (HDFS)– GFSのクローン– MapReduceプログラムの入力や出力に使用• Hadoop MapReduce– MapReduce実現するためのサーバー,ライブラリ64
2011年8月6日土曜日

HDFS
•

Master/Slave アーキテクチャ– Masterが落ちるとシステム全
体が停止– ファイルはブロック単位に分割して保存• 高スループット向き、低レ
イテンシ操作は苦手•

NameNode– Master– ファイルのメタデータ(パス・権限など)を管理•

DataNode– Slave– 実際のデータ(ブロックを管理)
65

2011年8月6日土曜日

http://hadoop.apache.org/core/docs/current/hdfs_design.html
66
53

2011年8月6日土曜日

HDFS Clientのブロック図67
2011年8月6日土曜日

データ配置のアルゴリズム(1)• あるデータをレプリケーション付きで書き込みたいと
き、どのノードに配置するか？
– 転送量を少なく– なるべく安全に (異なるラック・異なるDC)

68
55
2011年8月6日土曜日

データ配置のアルゴリズム(2)• Hadoopが使用しているアルゴリズム– 1つ目は必ずローカルに書く– 2つ目は異なるDC(Rack)に書く– 3つ目は同じDC(Rack)の違うノードに書く– 4つ目移行はランダム(1)
2011年8月6日土曜日

(3)

(2)

69
56

NameNodeの問題•

NameNodeがシステム全体のボトルネックになる– 大量のメタデータアクセスを裁く必要が有り、CPUパワーが必要– 大量のファイルを保存した場合、それに応じたメタデータを保持する必要が有り、メモリを大量に必要とする– 多数のデータノードからのハートビートメッセージを処理する必要が有
り、大量のネットワーク接続を処理する必要が有る– Googleでも同様の問題を抱えている• http://queue.acm.org/detail.cfm?id=1594206•

解決策– マルチマスター化? GoogleはBigTableにGoogleFileSystemのメタデー
タを置いているらしい?
70

2011年8月6日土曜日

Hadoop MapReduce• Master/Slave アーキテクチャ• JobTracker– Master– JobをTaskに分割し、Taskを各TaskTrackerに分配• Job: MapReduceプログラムの実行単位• Task: MapTask, ReduceTask– 全てのTaskの進行状況を監視し、死んだり遅れたりした
Taskは別のTaskTrackerで実行させる• TaskTracker– Slave– JobTrackerにアサインされたTaskを実行• 実際の計算処理を行う
71
2011年8月6日土曜日

MapReduce Architecture
JobTracker
TaskTracker

7259
2011年8月6日土曜日

MapReduceの短所• 処理は全てMapReduceの枠内に収める必要が有る• Shuffleフェーズで大規模に通信が発生– 全Mapper <-> 全Reducerの通信– ネットワーク輻輳が起こり計算が進まなくなる– Shuffleフェーズで渡されるデータ量(Mapの出力)を削減するのが高速化へのポイント
Map
ReduceMap

ShuffleReduceMap
73
2011年8月6日土曜日

Hadoopの周辺プロジェクト74
2011年8月6日土曜日

Hive• SQLライクな言語で、MapReduceジョブを記述– Javaを書かずに、必要なデータを得るためのジョブを簡単に作成できる
hive> CREATE TABLE shakespeare (freq INT, word STRING)ROW FORMAT DELIMITED FIELDS TERMINATED BY ‘\t’ STOREDAS TEXTFILE;
hive> LOAD DATA INPATH “shakespeare_freq”
INTO TABLE shakespeare;hive> SELECT * FROM shakespeare LIMIT 10;
hive> SELECT * FROM shakespeare
WHERE freq > 100 SORT BY freq ASC
LIMIT 10;75
61
2011年8月6日土曜日

例: HiveによるJoin操作• MapReduceを使用して、大規模なデータ同士のjoinを簡単に実行できるhive> INSERT OVERWRITE TABLE merged
SELECT s.word, s.freq, k.freq FROM
shakespeare s JOIN shakespeare2 k ON
(s.word = k.word)
WHERE s.freq >= 1 AND k.freq >= 1;
hive> SELECT * FROM merged LIMIT 20;
76
62
2011年8月6日土曜日

Hive

Hiveによるjoinを使用したシステム構築例

77
2011年8月6日土曜日

Pig• MapReduce用のDSL (Domain Specific Language)
Pig Latin
A = LOAD ‘myfile’AS (x, y, z);
B = FILTER A by x> 0;
C = GROUP B BY x;
D = FOREACH A GENERATE
x, COUNT(B);
STORE D INTO ‘output’;

pig.jar:•parses•checks•optimizes•plans execution•submits jar
to Hadoop•monitors job progress

Execution Plan
Map:
FilterReduce:Count

78
2011年8月6日土曜日

例: Pigによるデータ操作• Deta-flow指向言語– データ型としてset, associative array, tuple等をサポート• スクリプト例:# 入力データの生成
named_events = FOREACH events_by_time GENERATE $1
as event, $2 as hour, $3 as minute;# 12時台のイベント
noon_events = FILTER named_events BY hour = ’12’;# uniqueなイベント
distinct_events = DISTINCT noon_events;
79
65
2011年8月6日土曜日

hBase: 分散データベース• 列指向データベース– Google BigTableのデザインを踏襲して実装– データに対するinteractiveなアクセスを提供• 非常に大規模なデータを扱うのに適している– 数TB〜数PB• 制約されたアクセスモデル– keyでのlookup– transactionは行単位となっており、通常のRDBMSと比べると非常に制限されている
80
66
2011年8月6日土曜日

hBase: 単一行へのアクセス• 単一行への、keyによるアクセスが非常に高速– 特にWebアプリケーションでは重要になるデータlookup
の形式

81
67
2011年8月6日土曜日

hBase: MapReduceの入力•

各rowがMapReduceの入力となる– MapReduceジョブで、sort/search/indexing等を行うことが出来る。

•

hBaseのsequentialなscanを得意としているため、MapReduceジョブの速度は低下しない– オンラインデータ処理と高速なバッチ処理の両方が実現可能になる。

82
2011年8月6日土曜日

More and more projects...
• fuse-HDFS: HDFSをfuseマウントするプログラム• Zookeeper: 分散合意エンジン• Sqoop: RDBMSからHDFSへの取り込みエンジン• Avro: Serialization + RPCフレームワーク• Scribe, Flume: ログ収集フレームワーク• Mahout: MapReduceを使用した機械学習ライブラリ• Oozie: ワークフローエンジン• ...
• 全て現実問題を解決するために、企業手動で開発
83
2011年8月6日土曜日

Hadoopの使用方法

84
2011年8月6日土曜日

インストール (CDH)• Cloudera Distribution for Hadoopが便利– Apache Projectで配布されているものに、Cloudera社が独
自にbugfix & security fixを施したパッケージ (無料)– yum/apt等のパッケージシステム経由でのインストール• yum install hadoop-0.20-*– Hive/Pig/Hbase/Flume等の周辺ソフトも含まれている85
2011年8月6日土曜日

HDFSの操作方法# ls
alias dfsls='~/hadoop/bin/hadoop dfs -ls‘
# ls -ralias dfslsr='~/hadoop/bin/hadoop dfs -lsr‘# rm
alias dfsrm='~/hadoop/bin/hadoop dfs -rm‘
# rm -ralias dfsrmr='~/hadoop/bin/hadoop dfs -rmr'# catalias dfscat='~/hadoop/bin/hadoop dfs -cat‘# mkdir
alias dfsmkdir='~/hadoop/bin/hadoop dfs -mkdir‘
86
2011年8月6日土曜日

HDFSの操作方法• HDFS上にファイルを転送
alias dfsput='~/hadoop/bin/hadoop dfs -put‘
dfsput <local-path> <hdfs-path>• HDFS上からファイルを転送

alias dfsget='~/hadoop/bin/hadoop dfs -get‘
dfsget <hdfs-path> <local-path>87
77
2011年8月6日土曜日

HadoopStreaming• 標準入出力を介してMapReduce処理を書けるようにするための仕組み– sh ・ C++ ・ Ruby ・ Pythonなど、任意の言語でMapReduceが可能になる– http://hadoop.apache.org/core/docs/r0.15.3/streaming.html• Hadoop Streamingは単純なwrapperライブラリ– 指定したプログラムの標準入力に<key, value>を渡す– 標準出力から結果を読み込み、それを出力• Amazon, Facebook等でもStreamingをよく使用している– http://wiki.apache.org/hadoop/PoweredBy
88
2011年8月6日土曜日

使い方• 実行方法./bin/hadoop jar contrib/hadoop-0.20.2-streaming.jar-inputinputdir[HDFSのパス]-output

outputdir[HDFSのパス]-mapper map[mapプログラムのパス]-reduce[reduceプログラムのパス]

reduce-inputformat[TextInputFormat| SequenceFileAsTextInputFormat]-outputformat [TextOutputFormat]

89
79
2011年8月6日土曜日

例: Rubyによるワードカウント$ ./bin/hadoop
jar contrib/hadoop-0.20.2-streaming.jar-input wcinput-output wcoutput-mapper /home/hadoop/kzk/map.rb-reducer /home/hadoop/kzk/reduce.rb-inputformat TextInputFormat-outputformat TextOutputFormat

map.rb#!/usr/bin/env rubywhile !STDIN.eof?
line = STDIN.readline.strip
ws = line.split
ws.each { |w| puts "#{w}\t1“ }endreduce.rb#!/usr/bin/env rubyh = {}
while !STDIN.eof?
line = STDIN.readline.strip
word = line.split("\t")[0]
unless h.has_key? wordh[word] = 1
elseh[word] += 1
end
end
h.each { |w, c| puts "#{w}\t#{c}“ }

90
2011年8月6日土曜日

MapReduceアルゴリズム(1) Join操作

91
2011年8月6日土曜日

Join操作とは?
• ２つのデータセットが有ったときに、片方のデータがもう片方のデータを参照している。このとき、参照ではなくデータ自体で情報を結合したい。
• 例:
– 入力:
• EMP: 42, 太田, loc(13)• LOC: 13, 本郷三丁目– 出力• EMP: 42, 太田, loc(13), 本郷三丁目

92
2011年8月6日土曜日

MapReduceによるjoin• Map-Side Join
– 片方の表がメモリに載る範囲で有る場合、mapperに全てのデータを持たせてそこでjoinを行う– 両方のテーブルが大量のデータの場合に対応出来無い• Reduce-Side Join
– reducer側でjoinを行う– 次スライド以降で説明

String getLocation(int locId) {// メモリ上の構造 or 外部データベースを参照}
void map(k, v) {int locId = parse_locid(v);String location = getLocation(locId);}
map-side join
93
41

2011年8月6日土曜日

Reduce-Side Join: データ構造• Union構造

class Record {enum Type { emp, loc }Type type;// EMP用メンバ
String empName;int empId;// LOC用メンバ
String locationName;
int locId;};
94

2011年8月6日土曜日

Reduce-Side Join: Mapper• 各テーブル毎にmapperを走らせ、同じreducerを使用する。mapperではデータtypeを設定する。keyはlocIdを指定。

void map(k, v) { // employee用
Record r = parse(v);r.type = Type.emp;
emit (r.locId, r);}void map(k, v) { // location用
Record r = parse(v);r.type = Type.loc;
emit (r.locId, r);}95
43

2011年8月6日土曜日

Reduce-Side Join: Reducer• valuesのなかで、Type.locのモノに場所情報が入っているので、それをemployeesに付与する。
void reduce(k, values) {Record thisLocation; List<Record> employees;for (Record v in values) {if (v.type == Typ.loc)
thisLocation = v;
else
employees.add(v);}for (Record e in employees) {e.locationName = thisLocation.locationName;emit(e);}}2011年8月6日土曜日

96

MapReduceアルゴリズム(2) グラフアルゴリズム

97
2011年8月6日土曜日

例: MapReduceでの並列BFS•

グラフ上の1頂点から、1つ以上の頂点集合までの最短パスを求める•

アルゴリズム– DistanceTo(StartNode) == 0
– DistanceTo(n) == 1
• ただしnはStartNodeから辿れる– DistanceTo(m) = 1 + min(DistanceTo(n), n ∈ S)
• 頂点集合Sから辿れる全ての頂点m•

MapReduce型に落とすにはどのようにすればいいか？
– 行列の保持方法– Mapper, Reducerではどのような処理が必要か?

98
2011年8月6日土曜日

ノード1からの距離を可視化
3

1

2

2

2

3

3
3

4

4
99
2011年8月6日土曜日

隣接リストでデータを保持
隣接行列を構築し、ゼロを取り除く

1

1
0

2
1

3
0

4
1

2

1

0

1

1

3

1

0

0

0

4

1

0

1

0

1: 2, 42: 1, 3, 4
3: 1
4: 1, 3100
2011年8月6日土曜日

Parallel BFS by MapReduce
•

Map
– 入力
• Key: 頂点n• Value: D (startからの距離), S (nから到達可能なノード一覧)– 出力• Sに含まれる全てのノードmについて(m, D + 1)を出力•

Reduce– 入力: ノードmにへの経路列– 出力: 経路の中で最短のものを出力する•

MapReduce1回で、1 hop進める事ができる。出力を同じMapReduceプロ
グラムの入力として再度使用し、収束するまでジョブを走らせ続ける。

101
2011年8月6日土曜日

まとめ• Hadoopはグーグルの基盤技術のOSSクローン– 様々な企業/団体によって開発・改良・利用されており、新しい周辺プロジェクトがどんどん誕生している• MapReduceは大量データ処理に適したモデル– ジョブの失敗や並列化等を自動的に行ってくれる– 全てではないが、非常にフィットするアルゴリズムが有る– 例としてJOIN操作やグラフ上の探索問題等を解くことが出来る– 単一マスター, Shuffle時のネットワーク転送問題• 是非、余っているマシン等で試してみて下さい:-)102
2011年8月6日土曜日

Enjoy Playing Around
Hadoop J
Thank you!

103
2011年8月6日土曜日