首藤一幸, 華井雅俊, 杉野好宏:"分散システムの大規模シミュレーション" (依頼講演),
BI-5. 仮想化ネットワークのテストベッドとその応用 (依頼シンポジウムセッション),
電子情報通信学会 2013年総合大会 講演論文集,
2013年 3月 19〜22日

分散システムの大規模シミュレーション
Large-Scale Simulation of Distributed Systems
首藤一幸
Kazuyuki Shudo

華井雅俊
Masatoshi Hanai

杉野好宏
Takahiro Sugino

東京工業大学Tokyo Institute of Technology

1

はじめに
表 1 各実験プラットフォームで可能な実験の規模
すでに、インターネット上では 100 万 実験プラットフォーム
ノード 数台以上の PC からなる自律分散システム 本研究のターゲット
億 ∼ インターネット , 脳, 経済, 等々を模擬が少なくとも 3 つ稼働しており [4] 、最大 Overlay Weaver (著者ら ) [12] 約 100 万 1 台上で通信遅延とパケットロスを模擬のものは 1,000 万台に達している [8, 5]。 PeerfactSim.KOM
インターネットに接続される機器は多様(TU Darmstadt) [13]10 万以上 [13] 推奨は 1 万程度化しつつ増大を続けており、多くの予想 OverSim (U. Karlsruhe) [1]
10 万 [1] 1 台上で遅延を模擬が 、その、Internet of Things の規模が p2psim (MIT) [10]
1 万 [1] 同上
2020 年には数百億に達すると見ている。 peeremu (NEC) [7]1120 [7] PC 14 台で遅延とパケットロスを模擬
これを想定すると、今後の分散システム
そこで今回、次の通り、これまでとは異なるアプロー
研究は、この数百億という規模を対象としなければならチを採ることとした。
ない。しかし 、現在手に入る実験手法・手段では、10 万ある種の汎用分散処理システムが 、高いスケーラビリ∼100 万ノード という規模が限界である（ 表 1 ）。
ティと耐故障性、および 、ソフトウェアとしての成熟を
つまり、我々は現在、現れつつある規模（ 億 ∼ ）はお達成していることに着目し 、それらを用いた大規模シろか 、すでに稼働している規模（ ∼1,000 万）すら実験
ミュレーション手法を研究、確立する（ 図 2 ）。想定してできないという状況を迎えている。設計・実装し deploy
いる汎用分散処理システムは、MapReduce [2] 処理系、しようとする分散システムが 、インターネットにどの程グラフ処理系 [9, 6] である。これにより、上述した問題
度の負荷をかけるのか、何かを契機に通信量が爆発的にのうちいくつかが解決する：
増えて · · · といったことがないのか、などを調べる実験• スケーラビ リティ
手段を、今、我々は持たない。
例えば 、オープンソースの MapReduce 実装 Hadoop
そこで我々は、億を超える規模のシミュレーションをは 4,500 台のクラスタで稼働している [11]。
可能とする手法、および 、ソフトウェアとしての実装法• 耐故障性を研究している。
例えば 、Hadoop はタスク（ジョブの一部）の再実行機能を備える。一部のマシンが停止してもジョブを2 汎用分散処理システムを用いたシミュレーション完遂できる。
我々は、これまでの研究にて、PC 1 台での約 100 万• ソフトウェアとしての成熟ノード のシミュレーションを達成した（ 表 1 ）。さらに上分散システムのシミュレータより利用者がはるかに多の規模を狙って、複数台でシミュレーションを行う機能く、それだけソフトウェアとして成熟しやすい。例えを開発・実験してきたが、いくつかの問題にぶつかった：
ば Hadoop は数多くの企業が使用している：Facebook,J.P.Morgan, . . .。
• 性能
性能、つまりシミュレーションの進行速度には、後述すノード 間のメッセージ通信が PC をまたいで行われる課題（シミュレーション時間の取り扱い）を解決したるようになり、そこに時間がかかり、シミュレーショ上で取り組む。
ンの進行速度が大きく低下した。
シミュレーション規模は、マシン 1 台あたりのノード• 耐故障性・スケーラビ リティ数に台数を乗じたものとなる。マシン 1 台あたりのノー複数台のうち 1 台でも停止するとシミュレーション
ド 数は、ノード 情報とノード 間メッセージをディスク上が止まる。1 回のシミュレーションには数日かかるに持つのであればディスク容量、メモリ上に持つのであことも普通なので、これでは数十台以上での動作にれば メモリ容量によって制限される。 Hadoop の場合、は耐えない。
ディスク上に持つ。また、1 台あたりのノード 数が多かっ• ソフトウェア開発の困難さたり、メッセージが多くやりとりされると、シミュレーシミュレータ自体が開発困難な分散システムとなっション進行速度が下がるので、それを考慮してマシン台た。そこに耐故障性を持たせることは、さらに困難数とシミュレート対象ノード 数の比を決めることとなる。
である（チェックポインティング ? ）。
Overlay Weaver が数 GB のメモリで 100 万ノード を扱

首藤一幸, 華井雅俊, 杉野好宏:"分散システムの大規模シミュレーション" (依頼講演),
BI-5. 仮想化ネットワークのテストベッドとその応用 (依頼シンポジウムセッション),
電子情報通信学会 2013年総合大会 講演論文集,
2013年 3月 19〜22日
り、ホップ数などの実験結果からトポロジごとの傾向がOverlay
Weaver 向けの peer-to-peerアルゴリズム,見えている。
アプリ
分散アルゴリズム 脳モデル, 交通網モデル,グラフ処理系実装はシミュレート対象をメモリ上に持経済モデル,
…
ケーション
実装
つ。DHT アルゴ リズム Chord をシミュレートできてお…
API 適応ライブラリ
り、1 万ノード で Chord が動作している。

分散システム シミュレータ
シミュレータ

汎用分散処理システム(MapReduce, グラフ処理系, …)PCクラスタ,スーパーコンピュータ

…

〜 数千台

研究・開発
対象

図 1 シミュレータの構造えるので（ 表 1 ）、少なくとも、1 台あたり 100 万ノード 程度を想定している。マシン 100 台を用いて 1 億ノード、1,000 台を用いて 10 億ノード のシミュレーションが可能になると見込んでいる。

3手法
汎用分散処理システムを用いた分散システムシミュ
レーションには、次の課題がある。

3.1 ノード と通信の表現
汎用分散処理システムの上で、分散システムのノード、および メッセージとその送受信を表現する必要がある。
例えば MapReduce であれば 、基本的なデータ表現形式である key-value ペアや、map 、shuﬄe 、reduce 処理で表現することとなる。
3.2 時間の取り扱い
シミュレーション上のノード 間通信はマシン間通信のタイミングで行われる。MapReduce 処理系やグラフ処
理系では 、マシン間通信は全マシンが同期して一斉に行う（ Bulk Synchronous Parallel モデル ）。このため、ノード 間通信の処理は、全マシンが一斉に行うこととなる。このままでは、任意のタイミングでのノード 間通信をシミュレートできない。
この問題に対して、2 つの方法を試している。1 つは、同期の際に進めるシミュレーション時間上の時間幅を調整することで、シミュレーション速度と正確さのトレードオフを調整する手法である。もう 1 つは Virtual Time
[3] である。これは、メッセージ受信処理を投機的に行ってしまい、もしそれより先に受信しておくべきメッセージが後から発覚した場合には、受信を取り消す、という手法である。時間を正確に扱える。
4

シミュレータの実装と実験
MapReduce 処理系 Hadoop を 用いた実装 [15] と 、Pregel [9] にならった自前のグラフ処理系を用いた実装[14] を進めている。時間の扱いは Virtual Time で行う。
MapReduce 実装はシミュレート対象をデ ィスク上に持つ。100 万ノード、何種類かのネットワークトポロジ
で Gnutella のフラッデ ィングをシミュレートできてお5

まとめ
これまで（ ∼100 万）を大きく上回る規模（ 億 ∼ ）の実験を可能とするシミュレーション手法の確立、および 、シミュレータの開発・提供を目指して、研究を進めている。シミュレータの最初の版が動作しつつあり、今後、スケーラビ リティや性能を評価していく。
参考文献[1] Ingmar Baumgart, Bernhard Heep, and Stephan Krause.
OverSim: A ﬂexible overlay network simulation framework.
In Proc. 10th IEEE Global Internet Symposium (GI’07),
May 2007.

[2] Jeﬀrey Dean and Sanjay Ghemawat. MapReduce: Simpliﬁed data processing on large clusters. In Proc. OSDI’04,
December 2004.
[3] David R. Jeﬀerson. Virtual time. ACM Transactions on
Programming Languages and Systems, Vol. 7, No. 3, pp.
404–425, July 1985.
[4] Raul Jimenez, Flutra Osmani, and Björn Knutsson. Subsecond lookups on a large-scale Kademlia-based overlay. In
Proc. IEEE P2P’11, August 2011.
[5] Konrad Jünemann, Philipp Andelﬁnger, Jochen Dinger,and Hannes Hartenstein. Bitmon: A tool for automatedmonitoring of the bittorrent dht. In Proc. IEEE P2P’10,August 2010.
[6] U Kang, Charalampos E. Tsourakakis, and Christot Faloutsos. PEGASUS: A peta-scale graph mining system - implementation and observations. In Proc. ICDM’09, December
2009.
[7] Daishi Kato and Toshiyuki Kamiya. Evaluating DHT implementations in complex environments by network emulator.
In Proc. IPTPS 2007, February 2007.
[8] Live Monitoring of the BitTorrent DHT. http://dsn.tm.
kit.edu/english/2936.php.
[9] Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik,James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz
Czajkowski. Pregel: A system for large-scale graph processing. In Proc. OSDI’10, October 2010.
[10] p2psim:
a simulator for peer-to-peer
http://pdos.csail.mit.edu/p2psim/.

protocols.

[11] Apache Hadoop Project. Hadoop wiki - poweredby. http://wiki.apache.org/% linebreak[2]hadoop/PoweredBy.
[12] Kazuyuki Shudo, Yoshio Tanaka, and Satoshi Sekiguchi.
Overlay Weaver: An overlay construction toolkit. Computer
Communications (Special Issue on Foundations of Peer-toPeer Computing), Vol. 31, No. 2, pp. 402–412, February
2008.
[13] Dominik Stingl, Christian Groß, Julius Rückert, LeonhardNobach, Aleksandra Kovacevic, and Rralf Steinmetz. PeerfactSim.KOM: a simulation framework for peer-to-peer systems. In Proc. 2011 Int’l Conf. on High Performance Computing & Simulation (HPCS 2011), pp. 577–584, July 2011.
[14] 華井雅俊, 首藤一幸. 分散グラフ処理系を用いた大規模分散システムシミュレーション手法. 電子情報通信学会 技術研究報告
CPSY2012-27, pp. 109–114, August 2012.
[15] 杉野好宏, 華井雅俊, 首藤一幸. Mapreduce による大規模分散システムのシミュレーション . インターネットコンファレンス 2012
(IC2012) 論文集, pp. 21–27, November 2012.