先進的計算基盤システムシンポジウム SACSIS2013
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2013
2013/5/23

MapReduce を用いたグラフアプリケーションにおける重複メッセージの排除による高速化
黒

松

信

行†

置 田

真 生†

萩 原

兼

一†

本研究は，MapReduce を用いて実装されたメッセージパッシング方式のグラフアプリケーション
を対象に，MapReduce のボトルネックである Map タスクと Reduce タスク間の通信を削減する手法を提案する．まず，1 つの MapReduce ジョブ内におけるメッセージの重複を排除することで，メッセージの数を削減する．さらに，MapReduce ジョブの繰り返しにおけるメッセージパターンの重複に着目し，1 度目のパターンを保存して再利用することでメッセージ量を削減する．PageRank に対して提案手法を適用した結果，既存の高速化手法である in-mapper combining と比べ最大 1.57 倍の高速化を実現した．

Acceleration for Graph Application in MapReducewith Eliminating Redundant Messages
Nobuyuki Kuromatsu,† Masao Okita† and Kenichi Hagihara†
For MapReduce graph applications based on message passing, this papar proposes a new
method to reduce communications between Map tasks and Reduce tasks, which are a bottleneck of a MapReduce job. The proposed method is a combination of the following two
techniques. The first technique reduces the number of messages by removing redundant messages in a MapReduce job. The second technique reduces the size of a message by reusing
message patterns of the first job in iterative jobs after the second. Experimental results showthat the proposed method is up to 1.57 times faster than an existing in-mapper combining
method for PageRank apllications with MapReduce.

1. は じ め にする．そのため，大規模なグラフ問題は MapReduceと親和性が高い．

近年，並列分散処理によるグラフ処理が注目を集め

Jimmy Lin らはメッセージパッシングに基づくグている1) ．例えば，2012 年時点でドメインを持つウェ

ラフアルゴリズムの MapReduce 実装を高速化する手

ブページは 9 億以上存在する2) ．ウェブ上の情報を解法を提案している4) ．このアルゴリズムは次の (i)〜析し役立てるために，ウェブページを頂点，リンクを（iii）の繰り返しである．

辺とみなすグラフ問題が用いられる．しかし，ウェブ
ページの増加に伴って計算機単体によるグラフ解析が不可能になりつつある．
クラスタ上で大規模なデータを並列分散処理する手法として，Google が提唱した MapReduce プログラミ
ングモデル3) がある．MapReduce はデータを key と(i) 全頂点において頂点の内部状態と局所的なグラフ
構造に基づく計算を行う(ii) 全頂点における (i) の結果（以降，メッセージと呼ぶ）をそれぞれの隣接頂点に渡す(iii) 全頂点において受け取ったメッセージをもとに次の内部状態を計算する

value の組（key-value pair，以降 KVP）として扱い，

本論文では，このアルゴリズムを Jimmy パターンと複数のクラスタノード（以降，単にノード）上で並列表記する．PageRank5) をはじめ，センサネットワーに処理する．MapReduce はノードを追加することでク分野などグラフ問題の多くは Jimmy パターンで実扱えるデータ量および実行速度がスケーラブルに向上

装できる6) ．

Jimmy パターンを実装する場合，1 回の繰り返しを† 大阪大学 大学院情報科学研究科
The Graduate School ofInformation Science and Technology ofOsaka Universityⓒ 2013 Information Processing Society of Japan

1 回の MapReduce ジョブで実現する．Map フェー
ズ，Shuﬄe フェーズ，および Reduce フェーズ（2 章で後述）がそれぞれ (i)，(ii)，および (iii) に相当する．

88

先進的計算基盤システムシンポジウム SACSIS2013
Symposium on Advanced Computing Systems and Infrastructures

頂点間のメッセージは Shuﬄe フェーズにおける KVP（以降，中間 KVP）としてノード間で送受信される．
一般に，MapReduce のボトルネックは中間 KVP の
7)

生成と転送であるため ，高速化のためにはメッセー
ジの削減が重要である．Jimmy らの手法は PageRankの MapReduce 実装を 1.69 倍高速化した．
我々は，Jimmy パターンを対象に，中間 KVP の重複を排除することで高速化する新たな手法を提案する．

Jimmy らの既存手法は key の重複に着目して KVPを集約する一方，提案手法は value の重複に着目してSACSIS2013
2013/5/23

Map䝣䜵䞊䝈䝬䞊䝆 䝜䞊䝗
Mapฎ⌮
䝋䞊䝖
(1)
Map䝍䝇䜽
䝻䞊䜹䝹䝕䜱䝇䜽

Shuffle䝣䜵䞊䝈

Reduce䝍䝇䜽
(2)

୰㛫㻷㼂㻼

䝬䞊䝆 䝜䞊䝗
䝋䞊䝖(1)
Map䝍䝇䜽

䝬䞊䝆
䝋䞊䝖
(3)

Mapฎ⌮

䝻䞊䜹䝹䝕䜱䝇䜽

ධຊ
䝕䞊䝍

䝬䞊䝆
䝋䞊䝖
(3)
ධຊ
䝕䞊䝍

୰㛫㻷㼂㻼

KVP を統合する．

䝟䞊䝔䜱䝅䝵䞁1
Reduceฎ⌮䝻䞊䜹䝹䝕䜱䝇䜽䝟䞊䝔䜱䝅䝵䞁2୰㛫㻷㼂㻼䝬䞊䝆 䝜䞊䝗
Mapฎ⌮
䝋䞊䝖
(1)
Map䝍䝇䜽
䝻䞊䜹䝹䝕䜱䝇䜽

Reduce䝣䜵䞊䝈

Reduce
ฎ⌮
䝻䞊䜹䝹
䝕䜱䝇䜽

ศᩓ䝣䜯䜲䝹䝅䝇䝔䝮

本稿では 2 章で MapReduce の仕組みについて述べる．3 章では PageRank アプリケーションのアルゴリ

図 1 MapReduce ジョブの処理の流れ
Fig. 1 A flow of a MapReduce job

ズムを，4 章では Jimmy パターンを高速化する既存手法を紹介する．続く 5 章で提案手法の詳細を示し，

た KVP はパーティション毎にまとめられ，一定サイ

6 章で実験結果を示す．最後に 7 章で本稿をまとめる．

ズごとにディスクに書き込まれる．これをスピルファ
イルと呼ぶ．スピルファイルの書き込みは Map 処理

2. MapReduceとオーバラップして実行される．Map タスクは全入力

1 回の MapReduce 実行を MapReduce ジョブ（以降，単にジョブ）と呼ぶ．ジョブは複数の Map タスクを処理した後，全スピルファイルの内容を key でソートし，再びディスクに書き出す（図 1(1)）．

と Reduce タスクから構成される．Map タスクの数は

Shuﬄe フェーズでは Reduce タスクの入力データ

入力データ量に比例して自動的に決定され，Reduceを作成する．まず，いずれかの Map タスクが完了すタスクの数はユーザが指定する．ジョブの処理の流れ

ると，Reduce タスクは自身が担当するパーティショ

を図 1 に示す．1 回のジョブの流れは Map フェーズ，ンに属する中間 KVP をその Map タスクから転送すShuﬄe フェーズ，Reduce フェーズの 3 つのフェーズ

る（図 1(2)）．次に，Reduce 処理の入力データを生に分類できる．結果を得るためにジョブを繰り返し実成するため，集めた中間 KVP を key ごとにソート行する場合もある．

し，1 つのファイルにまとめディスクに書き出す（図入力データは一定量ごとにブロックに分割され，分1(3)）．この転送およびソートは未完了の Map タス

散ファイルシステム（DFS）を構成するノード上に分クとオーバラップして実行される．全 Map タスクの散している．Map タスクは入力データの局所性に基結果をソートするまで Shuﬄe フェーズは続く．

3)

づいてノードに割り当てられる ．一方，Reduce タ

Reduce フェーズでは，key ごとに集められた中間

スクは局所性に関係なく各ノードに割り当てられる．

KVP を Reduce タスクが集約処理することで最終的同一のプログラムを繰り返し実行しても，ジョブごとな結果を求める．

にノードに割り当てられるタスクは変化する．出力結
果は DFS に保存される．

3. PageRank

Reduce フェーズにおける負荷分散を実現するため，

PageRank ではウェブを有向グラフ G = (V, E) とMapReduce はパーティションの概念を備える．パー

みなす．V および E はそれぞれウェブページを要素とティションとは，KVP の key 空間を特定の規則で分割する頂点集合およびリンクを要素とする辺集合である．

した区分である．デフォルトの規則は key のハッシュ

PageRank の計算方法は以下の式 (1)〜(3) である5) ．

値であるが，ユーザが自由に変更できる．各 Reduce

式 (1) で各頂点に対し初期値のランクを与え，式 (3)タスクが 1 つのパーティションに属する中間 KVP をを満たすまで式 (2) の計算を繰り返す．

処理するため，パーティション数が Reduce タスク数と等しく，負荷が均等に分散するような規則をユーザが決める必要がある．

Map フェーズでは，各 Map タスクが 1 つの入力ブ

PR (v; 1) =1|V |PR (v; t) =(1 − d)
+d
|V |

(1)

∑

PR (u; t − 1)|Nout (u)|(2)

u∈Nin (v)

ロックに対して任意の Map 処理を実行する．得られⓒ 2013 Information Processing Society of Japan89

先進的計算基盤システムシンポジウム SACSIS2013
Symposium on Advanced Computing Systems and Infrastructures

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

SACSIS2013
2013/5/23(2) および式 (3) を計算

struct Vertex{
double rank //現在のランク PR (v; t)int vertices // |V |List<String> adjacency //Nout (v)}struct Message{
String f rom //メッセージを作成した頂点の識別子
double message //Mv}

これを MapReduce を用いて単純実装した疑似コー
ドを図 2 に示す．ジョブの入出力形式は，頂点を keyとし，その頂点の内部状態および局所的グラフ構造を

value とする KVP である．以降では，a および b をそれぞれ key および value とする KVP を < a, b >と表記する．
ブロック数を m とすると，V は m 個の部分集合に

void map(String v, Vertex N ){ // < v, N > を入力
Message M
M.f rom ← v
M.message ← N.rank / |N.adjacency|//u ∈ Nout (v) に Mv を渡す
foreach (String u :N.adjacency)
emit(u, M ) // 中間 KVP< u, M > として出力//Nout (v) を次の繰り返しへ持ち越す
emit(v, N )}分割され，任意の Map タスク p が部分集合 V (p) を担当する．p は各 v ∈ V (p) について図 2 の関数 mapを実行する．
関 数 map が 生 成 す る 中 間 KVP の 種 類 は ，<u, Mv > および < v, N > の 2 種である（図 2：17 行
目および 19 行目）．v の内部情報および局所的グラフ構造（N ）は Reduce の計算には不要な情報であるが，ジョブの出力 KVP を加工せずそのまま次のジョ

void reduce(String v, List<Object> [X1 , X2 , ...]){
Vertex N
double s ← 0
foreach(Object X :[X1 , X2 , ...])
if(isVertex(X)) //構造体 Vertex かどうか
N ←X
else
s ← s+X.message
N.rank ← (1 − d)/N.vertices+d · s //ランクの更新
emit(v, N ) // 結果の KVP< v, N > として出力// 式 (3) による終了判定（省略）}
図 2 MapReduce における PageRank の単純実装
Fig. 2 A naive implementation of PageRank∑

ブの入力 KVP とするために Reduce タスクへ送信する必要がある．
中間 KVP の key は，メッセージを受け取る頂点を表す．パーティション数を r とすると，V は Map
フェーズとは異なる基準で r 個の部分集合に分割され，任意の Reduce タスク q が部分集合 V (q) を担当する．

q は各 v ∈ V (q) について図 2 の関数 reduce を実行
し，更新されたランクを含む KVP を出力する．

4. 既存の高速化手法
Jimmy パターンを高速化する既存手法4) のうち，
in-mapper combining（以降，IMC）と Schimmy に|PR (v; t − 1) − PR (v; t)| < 

(3)

v∈V

PR (v; t) は繰り返し t(t > 0) 回目の PageRank における v ∈ V のランクを表す，Nout (v) = {u|v → u ∈E} および Nin (v) = {u|u → v ∈ E} である（u → v

ついて示す．IMC は中間 KVP 数を削減し，Schimmy
は中間 KVP のデータ量を削減する．なお，両手法は適用条件を満たせば Jimmy パターン以外に対しても適用可能である．

4.1 In-Mapper Combining

は u から v への有向辺を表す）．d は減衰係数8) を表

IMC は 1 つの Map タスクが生成する中間 KVP のし，リンクを持たないページのランクが増加し続ける

key の重複に着目し，主記憶上で KVP を集約してかことを防ぐ． は収束の閾値であり，パラメータとしらディスクへ出力する．IMC を適用できる条件は，中て指定する．なお G は変化しないと仮定とする．

間 KVP をあらかじめ集約しても Reduce の計算内容

3.1 PageRank の MapReduce 実装
PageRank は Jimmy パターン（1 章）で実装できる．入力は G，出力は全ての v ∈ V に対する PR (v; t)が変化しないことである．

IMC は Map タスクにおいて次のように実装する．
(I)である．全ての v は内部状態として PR (v; t) をもち，以下の処理を繰り返す（t > 1）．

(i) Mv = PR (v; t)/|Nout (v)|(ii) 全ての u ∈ Nout (v) に対して Mv をメッセージ
として渡す(iii) 受け取った全ての Mw (w ∈ Nin (v)) をもとに，式ⓒ 2013 Information Processing Society of Japan関数 map が生成する中間 KVP を主記憶上に
保存

(II)

中間 KVP を key ごとに分類し，同一 key を持
つ KVP 群を集約して 1 つの KVP に変換(III) 全入力 KVP を処理した後，集約した KVP をディスクへ出力

3.1 節の PageRank に IMC を適用すると，同一頂

90先進的計算基盤システムシンポジウム SACSIS2013
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2013
2013/5/23

点に渡すメッセージ群を集約できる．ある Map タ
スク p が生成する中間 KVP において，任意の頂点

v を key とする KVP の集合を K(p|v)，その各要

b
a

c

2

2

1

e
f

素の value の集合を U (p|v) とする（ただし構造体

2

1

g

1

Vertex を表す value を除く）．U (p|v) は，全てのhiu ∈ Nin (v) ∩ V (p) から v が受け取るメッセージ集

33

合に等しい．したがって，U (p|v) の全要素を加算しj

1てから v に渡しても計算結果は変化しない．そこでK(p|v) を 1 つの < v, ΣM ∈U (p|v) M > に集約できる．

3

d

k

2

a

1

䝟䞊䝔䜱䝅䝵䞁1䛻ᒓ䛩䜛㡬Ⅼa

図 3 PageRank を求めるグラフの例
Fig. 3 An example of graph in PagerRank

ただし，IMC を適用すると関数 map の計算と出力をオーバラップできない．IMC では Map タスクの全もう一方の < u, N > を無視して記述する．

入力データを処理するまで (III) のディスク出力を開5.1 RRSP

始できないためである．集約効率が低い入力データを

RRSP はある Map タスク p が生成する中間 KVP

処理する場合，出力が Map タスクにおけるボトルネッの value の重複に着目する．頂点 v が頂点 u と頂点クになりうる．

w それぞれにメッセージ Mv を渡すと仮定する．この4.2 Schimmy

とき，2 つの中間 KVP< u, Mv > と < w, Mv > がSchimmy はジョブの実行中に変化しない静的なデー生成される．これらの KVP のパーティションが同じタに着目し，全ノードが静的なデータをあらかじめロー

とき，Mv は p からある 1 つの Reduce タスクに対しカルディスクに保持することで Shuﬄe フェーズのデーて 2 重に送信される．図 3 のグラフを例に PageRank

タ転送量を削減する．Schimmy を適用できる条件は，の場合を考えると，頂点 b と頂点 g が属するパーティ

静的なデータが存在することである．

ション 2 を担当する Reduce タスクは，< b, Ma > と

3.1 節の PageRank に Schimmy を適用すると，関数 map が出力する構造体 Vertex のデータ量を削減< g, Ma > の 2 つを受け取る．しかし，b と g のランクを計算する上で Ma は 1 つで十分である．

できる．G が静的であるため，隣接リスト Nout (v) は

そこで RRSP は，ある Map タスクが生成する中ジョブの繰り返しにおいて変化しない．したがって，

間 KVP をパーティションおよび value で分類し，同Nout (v) をあらかじめノードが保持していれば，中間一のパーティションおよび value をもつ KVP 群を 1

KVP として Nout (v) を出力する必要はない．

つの KVP に統合する．統合後の KVP の key およびしかし，あるノードが実行する Map タスクは実行のたびに変化するため，各ノードが全ての v ∈ V に関する Nout (v) を保持する必要がある．したがって，

value は，それぞれ統合前の KVP 群の key を要素とする集合および統合前の KVP の value とする．

PageRank は RRSP を効果的に適用できるアルゴリ

グラフが大規模化するにつれ各ノードが保持するデーズムである．その理由は，頂点 v を入力とする関数 map

タ量が増大する．その結果，事前にデータを配布するが出力する中間 KVP の value が全て同一の Mv とな

コストが増大し，またディスク容量を超えて保持できるためである．ある Map タスク p が生成する統合前のない可能性も生じる．

中間 KVP の集合 K(p) は K(p) = {< u, Mv > |v ∈5. 提 案 手 法
我々は Jimmy パターンに対して，重複情報を排除して中間 KVP の数とデータ量を削減する手法を提案すV (p), u ∈ Nout (v)} となる．r 個の Reduce タスク
Q = {q1 , q2 , · · · , qr } がある場合，統合後の中間 KVPの集合 K(p)0 は K(p)0 = {< V (q) ∩ Nout (v), Mv >|v ∈ V (p), q ∈ Q} となる．

る．提案手法は 2 つの手法 RRSP（Removing Redun-

なお，統合によって key を変更すると，パーティショ

dant messages to the Same Partition）および IRS

ンが変化する可能性がある．その結果，統合後の中間（In-Reducer Schimmy）の組み合わせである．5.2 節

KVP が統合前と異なる Reduce タスクに送信され，正で後述する IRS の特徴により，提案手法はジョブの繰

しい実行結果が得られない．

り返しにおける 2 回目以降にしか適用できない．

統合前のパーティションを保持するため，統合後の提案手法を PageRank の MapReduce 実装（3.1

KVP の value に int 型の付加情報を追加する．さら節）に適用する場合，対象となる中間 KVP の種類に，パーティションの規則を key のハッシュ値ではな

は < u, Mv > のみである．本章では，簡単のために

くこの付加情報に変更する．

ⓒ 2013 Information Processing Society of Japan91

先進的計算基盤システムシンポジウム SACSIS2013
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2013
2013/5/23

5.1.1 IMC と RRSP の比較
RageRank を対象に IMC および RRSP の中間
KVP の削減率を比較する．入力グラフ G における頂点の出次数の平均を e，Map タスクの数を m，Re-

duce タスクの数を r とする．1 つの Map タスクが担当する頂点数の平均は |V |/m である．各頂点は平均

e 個のメッセージを生成するため，単純実装における表 1 実験環境
Table 1 The experimenatal environment

CPU
主記憶
ハードディスクネットワークOS
Hadoop
HDFSIntel Xeon 3.2GHz 4 cores
DDR3-SDRAM 1333MHz ECC 8 GB
SATA 6 Gb/s 7200 rpm 1TB
Gigabit Ethernet
CentOS 5.6
バージョン 1.0.1
上記 Hadoop に同梱版

1 つの Map タスクが出力する中間 KVP 数の平均は
e|V |/m となる．

の配布を兼ねて単純実装を実行する．任意の Reduce

IMC は 1 つの Map タスクが生成する中間 KVP のタスク q は，入力された KVP から v と L(q|v) の対

うち，同一の key をもつ KVP 群を 1 つの KVP に変

応表を作成し，ローカルディスクに保存する．2 回目換する．PageRank では中間 KVP の key は頂点を表以降では，提案手法を実行する．q は < ∅, Mv > をすため，Map タスクが生成する中間 KVP 数は最大受け取り Mv の送信元情報（v ）と対応表から L(q|v)|V | となる．したがって IMC の削減率 DI は式 (4) とを復元し，ランクを計算する．

予測できる．

ただし，IRS では任意の q をジョブの繰り返しにお|V |いて同一のノードに割り当てる必要がある．しかし，m
DI = e|V | =
e

(4)

m

MapReduce の標準スケジューラはその保証がない．

一方，RRSP は 1 つの Map タスクが生成する中間

そこで q に対するノードを固定するジョブスケジュー

KVP のうち，value が同一かつパーティションが同一

ラを実装した．このジョブスケジューラのデメリットの KVP 群を 1 つの KVP に統合する．PageRank でとして，本来の MapReduce が備える Reduce タスク

は任意の頂点 v から生成するメッセージは同一であるの耐故障性は失われる．性能面でのデメリットはない．

ため，v をもとに生成する中間 KVP 数は最大 r 個となる．したがって RRSP の削減率 DR は式 (5) と予
測できる．

DR =

6. 評

価

PageRank を対象に提案手法と IMC の比較実験を
r
e

(5)

行った．実行には MapReduce を実装したオープン
ソースソフトウェアである Hadoop9) を用いた．実験

PageRank の MapReduce 実装では，一般に r < m

環境を表 1 に示す．Map タスクのブロックの大きさが成り立つ．よって，IMC と比較して RRSP は中間

は 64 MB とし，Reduce タスクの数はノード数と同KVP 数をより削減すると期待できる．

数にした．パーティションの規則はデフォルトである．

なお，RRSP の処理は map 関数ごとに閉じている
ため，MapReduce の標準実装と同様に計算と出力のオーバラップが可能である．

PageRank の閾値  = 0.005 とした．
なお，5 章で示したように，提案手法は 1 回目のジョブには適用できない．提案手法を用いる場合でも，15.2 IRS

回目のジョブは図 2 の単純実装と同様の実装を用いる．

IRS は，RRSP 適用後の実装に Schimmy を応用す

2 回目以降のジョブに RRSP と IRS を適用する．

ることで，中間 KVP のデータ量を削減する．Jimmy
らの利用法（4.2 節）との相違点は，Reduce タスクでSchimmy を利用する点である．

6.1 ウェブの一部分を用いた実験
実際のウェブの一部分から作成したグラフデータを用いて提案手法を評価する．英語版 Wikipedia10) のPageRank を対象にした場合，統合後の中間 KVP“Portals” ページを始点とし幅優先探索でクロールしはパーティション f ごとに < V (q) ∩ Nout (v), Mv >た結果をもとに，|V | = 999, 991，|E| = 46, 174, 713である（q は f を担当する Reduce タスク）．グラフのグラフデータを作成した．

G とパーティション規則が固定であれば，L(q|v) =このデータ量は 295 MB であり，Map タスク 5 個

V (q) ∩ Nout (v) はジョブの繰り返しにおいて変化しな

分の入力データに相当する．そこで，ノードを 5 台用

い．あらかじめ q が L(q|v) を保持していれば，L(q|v)

いて PageRank を実行した．ランクが収束するまでを中間 KVP に含める必要はない．この場合，q へ送に繰り返したジョブの回数は 10 回である．

信する中間 KVP は < ∅, Mv > に変更できる．
そこで，PageRank の 1 回目の繰り返しでは，L(q|v)ⓒ 2013 Information Processing Society of Japan

6.1.1 実行時間の比較
各手法を用いた場合の総実行時間を図 4 に示す．単92

先進的計算基盤システムシンポジウム SACSIS2013
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2013
2013/5/23

1200
5,000

1.2
4372.20

1088

800
600

660
596

400

䝕䞊䝍㌿㏦㔞 䠄GB䠅ᐇ⾜᫬㛫 䠄⛊䠅

1.0

4,500

1.05

4,000
3,500

0.8

3,000
2,500

0.6

2,000
0.4

1,500

200

637.55

1,000

0.2

0

500

201.58

༢⣧ᐇ⿦

ᥦ᱌ᡭἲ

IMC

Wikipedia をもとに生成したグラフに対する PageRank の総実行時間（ジョブ 10 回の合計）
Fig. 4 Total execution time of 10 MapReduce jobs to
calculate PageRank for a part of the Web

0.08

0.01

0.0
༢⣧ᐇ⿦

図4

୰㛫KVPᩘ 䠄୓䠅

1000

0

IMC

ᥦ᱌ᡭἲ

䝕䞊䝍㌿㏦㔞 䠄GB䠅୰㛫KVPᩘ 䠄୓䠅

図6

2 回目以降のジョブにおけるデータ転送量および中間
KVP 数
Fig. 6 Transﬀerd data size and the number of intermediate
KVP in a job after the second iteration120
111.00108.11106.003080Map䝍䝇䜽
60

66.00

Reduce䝍䝇䜽

25

65.33

5.87
53.78

40
20
0
1ᅇ┠
༢⣧ᐇ⿦

2ᅇ┠௨㝆
IMC

ᐇ⾜᫬㛫 䠄⛊䠅ᐇ⾜᫬㛫 䠄⛊䠅

100

ᥦ᱌ᡭἲ

20
16.64

12.73

10

7.37

1 回目のジョブの実行時間と，2 回目以降のジョブ

5.93

0
IMC
㛵ᩘmap

し，提案手法は 1.83 倍高速である．

11.35

3.7

5

図 5 ジョブの平均実行時間
Fig. 5 Average execution time of a of job

純実装と比較して IMC が 1.65 倍高速であることに対

13.23

2.87
15

ᥦ᱌ᡭἲ
䝕䜱䝇䜽ฟຊ

0

IMC
䛭䛾௚

ᥦ᱌ᡭἲ

㛵ᩘreduce

図7

2 回目以降のジョブにおける Map タスクおよび Reduce タ
スクの平均処理時間の内訳
Fig. 7 Average breakdowns of a Map task and a Reducetask in a job after the second iterationの平均実行時間を図 5 に示す．2 回目以降のジョブにおいて，提案手法は単純実装と比べ約 2.0 倍高速であ間の内訳を図 7 に示す．図のディスク出力は，4.1 節

る．したがって，ジョブの繰り返し回数が十分大きけ(III) の処理に要する時間である．生成する KVP 数

れば，PageRank の総実行時間も最大約 2 倍の高速化の減少によって，提案手法における関数 map の処理が期待できる．また，2 回目以降の提案手法は IMC

時間は IMC と比較して平均 3.9 秒短縮した．さらに，と比較して 1.21 倍高速である．したがって，今回の提案手法はディスク出力を関数 map とオーバラップ

実験では，ジョブの繰り返し回数が 6 回以上のとき提するため，ディスク出力時間は見かけ上存在しない．

案手法の方が高速である．

Map タスクのその他は主に中間 KVP のマージソー

6.1.2 実行の詳細比較トであり，これも KVP 数の削減によって平均 1.9 秒

本節における比較の対象は，全て 2 回目以降のジョ

短縮した．

ブの実験結果とする．

提案手法における関数 reduce の処理時間は IMC とまず，Shuﬄe フェーズにおける中間 KVP のデータ比較して平均 1.4 秒減少した．この理由は，IRS のオー

転送量および中間 KVP 数を図 6 に示す．図 6 が示す

バヘッドより入力 KVP 数の減少による関数 reduce

とおり，提案手法は IMC と比較して中間 KVP をよりの時間短縮が大きいためと考えられる．Reduce タス

削減する．提案手法のデータ転送量および中間 KVP

クのその他は，主にデータ転送とマージソートである．

数は，IMC の場合のそれぞれ 16.8%および 31.6%に6.2 ランダム生成データを用いた実験減少する．

提案手法のスケーラビリティを評価するため，ラン

次に，Map タスクおよび Reduce タスクの処理時ⓒ 2013 Information Processing Society of Japan

ダムに生成したグラフデータに対する PageRank の93

SACSIS2013
2013/5/23

2

2

1.8

1.8

1.6

1.6

㏿ᗘྥୖ⋡

㏿ᗘྥୖ⋡

先進的計算基盤システムシンポジウム SACSIS2013
Symposium on Advanced Computing Systems and Infrastructures

1.4
1.2

1.4
1.2

1

1

0.8

0.8
25

50

25

75

50

60䝜䞊䝗

40䝜䞊䝗

60䝜䞊䝗

20䝜䞊䝗

図 8 DS-L に対する提案手法と IMC の単純実装に対する速度向上率（実線：提案手法，破線：IMC）
Fig. 8 Speedup with proposed method and IMC for DS-L

表 2 ランダムに生成したグラフに対する PageRank の総実行時間（単位：秒，n：実行ノード数，e：平均出次数）
Table 2 Total execution time of PageRank for random
generated graphs

n
60

DS-L

40

20

60

DS-S

40

20

e
25
50
75
25
50
75
25
50
75
25
50
75
25
50
75
25
50
75

単純実装

1,376
2,543
3,865
2,026
3,966
6,299
4,076
8,696
1,4684
844
1,267
2,031
1,125
1,942
3,106
2,163
3,880
6,450

75

ᖹᆒฟḟᩘ

ᖹᆒฟḟᩘ

IMC
1,342
2,329
3,471
1,903
3,509
5,354
3,820
7,563
12,132
839
1,196
1,894
1,125
1,786
2,773
2,082
3,411
5,418

40䝜䞊䝗

図9

DS-S に対する提案手法と IMC の単純実装に対する速度向上率（実線：提案手法，破線：IMC）
Fig. 9 Speedup with proposed method and IMC for DS-S
表 3 提案手法および IMC の中間 KVP 数の削減率
Table 3 Reduction rate of the number of intermediate
KVP with proposed method and IMC
ノード数

削減率

提案手法

1,216
1,957
2,807
1,672
2,868
4,084
3,088
5,311
7,736
774
1,017
1,519
987
1,365
2,016
1,656
2,504
3,914

20䝜䞊䝗

60
DS-L

40
20
60

DS-S

40
20

DI
DR
DI
DR
DI
DR
DI
DR
DI
DR
DI
DR

25
1.00
0.78
0.96
0.70
0.96
0.52
0.96
0.79
0.97
0.71
0.97
0.54

平均出次数
50
75

0.96
0.62
0.96
0.52
0.96
0.33
0.93
0.62
0.93
0.52
0.93
0.33

0.96
0.51
0.96
0.40
0.96
0.24
0.97
0.52
0.97
0.41
0.97
0.25

実装に対する提案手法と IMC の速度向上率を図 8 および図 9 に示す．表 2 より，全条件において提案手法
は IMC より速く，最大約 1.57 倍高速であった（DS-Lに対して e = 75 かつ n = 20）．

6.2.1 頂点数による性能変化
性能を評価する．

図 8 および図 9 より，n ≥ 40 かつ e が一定のとき入力として |V | =1 億のグラフデータ DS-L と|V | を増大しても提案手法の速度向上率はほぼ変化し|V | =5 千万のグラフデータ DS-S を生成した．各頂ない．この理由は，表 3 が示すように，DR が変化し点の隣接頂点はランダムに決定している．乱数にはないためである．これは DR の予測値が |V | に依存しJava の Random クラス（一様分布）を用いた．DS-Lないこと（式 (5) 参照）からも妥当である．

と DS-S のそれぞれで平均出次数 e を 25，50，およ

しかし，n = 20 かつ e ≥ 50 のとき，|V | が増大

び 75 とする計 6 種類のデータを用意した．DS-L のすると提案手法の速度向上率は増大する．この理由は

データ量は e = 25, 50, 75 の場合でそれぞれ 24 GB，

Shuﬄe フェーズのオーバラップにある．DS-L に対し

44 GB，および 66 GB であり，DS-S のデータ量はそて既存実装および IMC を実行した場合，全てのデー

れぞれ 12 GB，22 GB，および 33 GB である．

タ転送を Map フェーズとオーバラップできず，関数

実行ノード数 n を 20，40，および 60 と変更しながreduce の開始までに待ち時間が発生していた．一方ら，6 種類のデータに対して PageRank を実行する．

で，DS-L に対して提案手法を実行した場合は，データ全ての場合においてランクが収束するまでに 5 回ジョ転送量が十分少なく，データ転送を完全にオーバラッ

ブを繰り返した．
提案手法および IMC の総実行時間を表 2 に，単純ⓒ 2013 Information Processing Society of Japan

プできた．このように，中間 KVP の削減は転送待ち
時間短縮の観点からも有用である．

94

先進的計算基盤システムシンポジウム SACSIS2013
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2013
2013/5/23

また，提案手法と同様に，他の条件を固定して |V |MapReduce ジョブの繰り返しにおける静的なデータを増大しても，IMC の速度向上率および DI の実測値をあらかじめローカルディスクに保持することで KVPは変化しない．なお，m は入力データ量に比例し，入のデータ量を削減した．

力データは隣接リストであるためそのデータ量は |V |PageRank の MapReduce 実装に提案手法を適用し，および e に比例する．式 (4) より DI の予測値は次の既存の高速化手法である IMC と比較して最大 1.57 倍式 (6) となり，|V | に比例する（k は定数）．

の高速化を達成した．さらに，PageRank に対しては，

DI = k|V |(6)

一般に提案手法が IMC より高速であることおよび入この実験では，DS-S に対してすでに DI が上限値（1）力グラフの辺密度が高いほど提案手法の性能が向上すに近いため，DS-L に対する DI は増加しなかった．

ることを示した．

6.2.2 辺密度による性能変化
図 8 より，他の条件を固定して e を増大すると速度向上率は増大する．提案手法と IMC を比較すると，提案手法の速度向上率はより大きく増大する．図 9 も同様の傾向を示す．
この理由は，e が増大すると DR が減少するためである（表 3）．式 (5) より，予測値も e に反比例する．
これは e が大きいほど同一メッセージを value とする
中間 KVP 数が増加するためである．なお DI は実測値および予測値ともに e によらず一定である（式 (6)）．
以上より，入力グラフの辺密度が高いほど提案手法の性能は向上する．

6.2.3 ノード数による性能変化
図 8 より，他の条件を固定して n を増大すると速度向上率は減少する．提案手法と IMC を比較すると，提案手法の速度向上率はより大きく減少する．図 9 も同様の傾向を示す．
この理由は，n が増大すると DR が増大するためである（表 3）．本実験では r = n としたため，式 (5)より予測値も n に比例する．n が大きいほど 1 つのパーティションに送信されるメッセージが減少するためである．なお，DI は実測値および予測値ともに nによらず一定である．
式 (5) より，n に関わらず r を一定に設定すれば，

DR の増大を回避し速度向上を期待できる．しかし，その場合 Reduce フェーズの負荷が r 個のノードに集中し，n − r 個のノードが遊休状態になる．n に対して r が少ない場合は実行効率が低下し，速度向上率は減少する．したがって，n が増大した場合には適切なr を設定する必要がある．

7. ま と め
本論文は Jimmy パターンを高速化する手法を提案
した．具体的には，まず，1 つの MapReduce ジョブ
において，2 つのノード間で転送される中間 KVP の

value が重複することに着目し，同一の value をもつ
KVP を統合することで KVP 数を削減した．次に，ⓒ 2013 Information Processing Society of Japan

今後の課題は，提案手法を用いる場合の適切な Re-

duce タスク数の決定，および Jimmy パターン以外のアプリケーションへの提案手法の応用である．
謝辞 本研究の一部は科学研究費補助金（基盤研究(B)23300007，若手研究 (B)23700036）の支援による．

参

考

文

献

1) Lumsdaine, A., Gregor, D., Hendrickson, B.
and Berry, J. W.: Challenges in Parallel Graph
Processing, Parallel Processing Letters, Vol. 17,
No. 1, pp. 5–20 (2007).
2) https://www.isc.org/solutions/survey/: The
ISC Domain Survey (2012).
3) Dean, J. and Ghemawat, S.: MapReduce:
simplified data processing on large clusters,
CACM , Vol. 51, No. 1, pp. 107–113 (2008).
4) Lin, J. and Schatz, M.: Design patterns
for eﬃcient graph algorithms in MapReduce,
8th Workshop on Mining and Learning with
Graphs, MLG ’10, ACM, pp. 78–85 (2010).
5) Page, L., Brin, S., Motwani, R. and Winograd,
T.: The PageRank Citation Ranking: Bringing
Order to the Web., Technical Report 1999-66,
Stanford InfoLab (1999).
6) Cudre-Mauroux, P., Aberer, K. and Feher,
A.: Probabilistic Message Passing in Peer DataManagement Systems, 22nd Int’l Conf. Data
Engineering, ICDE ’06 , IEEE, p. 41 (2006).
7) Wang, G., Butt, A., Pandey, P. and Gupta,
K.: A simulation approach to evaluating design
decisions in MapReduce setups, Int’l Sympo.
Modeling, Analysis Simulation of Computer
and Telecommunication Systems, MASCOTS’09 , IEEE, pp. 1 –11 (2009).
8) Boldi, P., Santini, M. and Vigna, S.: PageRank as a function of the damping factor, 14thInt’l Conf. World Wide Web, WWW ’05,
ACM, pp. 557–566 (2005).
9) White, T.: Hadoop: The Definitive Guide, Yahoo! Press, USA (2010).
10) http://en.wikipedia.org/wiki/: Wikipedia. thefree encyclopedia (2012).

95