1

下位アルゴリズム中立な DHT 実装への耐 churn 手法の実装
首

藤

一

幸†

ノードの頻繁な離脱と加入，つまり churn に対する耐性向上は，分散ハッシュ表 (DHT) の大きな課題である．本論文では，いくつかの耐 churn 手法とその効果を示す．ここで示す手法はどれも DHT層に対する実装であり，その下のルーティング層への変更は必要としない．ゆえに，特定のルーティ
ングアルゴリズムに依存せず，様々なアルゴリズムと組み合わせて用いることができる．耐 churn 手法のどれをどういうパラメータで組み合わせて用いるべきかは応用に依存し，一意には定まらない．
適切な手法とパラメータを見出す方法を考察する．

Churn Resilience Improvement Techniques in an Algorithm-neutral DHT
Kazuyuki Shudo†
Churn resilience is an important topic in DHT research. In this paper, I present techniques
to improve churn resilience and eﬀect of them. All the techniques can be implemented in a
DHT layer and require no change to an underlying routing layer. In other words, they do notdepend on a speciﬁc routing algorithm and can work with various algorithms. Which techniques to be applied and what parameters are optimal are dependent on a DHT application.
I last discuss how we can determine it.

1. は じ め にドの信頼性，可用性はまったく期待できない．

分散ハッシュ表 (DHT) とは，中心となるサーバ的ノードの離脱や加入（故障や復帰）がある程度の頻度なノードのない，全ノードが対等な非集中かつ自律的で起こることを前提として，それでもサービスを継続な分散環境でハッシュ表の機能を達成する仕掛けであできることが求められる．頻繁なノードの出入り，つる．ハッシュ表という汎用性の高い機能を提供するたまり churn への耐性は，DHT においても重要な課題

め応用の範囲が広く，様々な名前解決に用いることがである．

そこで，非集中分散システムには，サービス提供

できる．たとえば DNS への応用がさかんに研究されている1) ．

本論文では，DHT を対象としたいくつかの耐 churn
手法，および，その効果を示す．本研究の特色は，こネットワークサービスを提供する側にとって，非集

こで示す手法のどれもが，下位のルーティングアルゴ

中分散 (peer-to-peer) システムを用いたサービス提供

リズムに依存しない点である．どの手法も DHT 層にには，次のメリットがある．

対して実装するものであり，その下のルーティング層• 低い管理・提供コスト• 高いスケーラビリティ• 高い信頼性
ここで，信頼性確保のために，少数のサーバを用いへの変更は必要としない．これにより，どの手法も，
Chord，Kademlia など，それぞれ特性の異なる様々なルーティングアルゴリズムと組み合わせて用いることができる．

る場合と同様に個々のサーバの信頼性を高めるという各手法は構造化オーバレイ構築ツールキット Over-アプローチを採ってしまうと，管理・提供コストがサー

lay Weaver2),3) に実装した．4 章では各手法の効果を示す．
どの耐 churn 手法をどういったパラメータで使い，どう組み合わせて用いるべきかは，一意には定まらな

ビス提供側の台数に比例して高くなってしまい，元の木阿弥である．逆に，サービス受益者，利用者のノードをもサービス提供に用いる場合は，そもそも各ノー

い．DHT の応用に依存する．本論文では最後に，そ† ウタゴエ株式会社
Utagoe Inc.

れを見出す方法を考察する．

情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月

ID

空間

ルーティング
経路上のノード

Tier 2Tier 1

ルーティング
要求
ノード

root

ペアを保持する

key-value

CFS PAST

Key-based Routing Layer (KBR)

DHT
shell

:

ID

Content
sharing

Distributed Grid info.
file system service

Mcast
shell

Application-level

Content
IP Multicast distribution…
router

DHT interface

Mcast interface

DHT

Mcast

図 1 DHT での put，get のためのルーティング
Fig. 1 Routing to put and get to a DHT.

Directory service Messaging service

DHT は構造化オーバレイ（structured overlay）の一応用であるという整理4) に従うと，DHT の put，
get 処理は次のように説明できる（図 1）．
put(key,value) key をキーとしてルーティングを行うと，何ノードかを経由して，key を担当するノード，すなわち root ノードに到達する．そのノードに，

key-value ペアを保持させる．
get(key) key をキーとしてルーティングを行うとroot ノードに到達する．そのノードから，key と結びつけられている value を受け取る．
ここで，DHT を構成するノードの離脱や加入があると，put したはずの値を get できないという問題が起こりうる．get 失敗の原因は，より直接的には以下のとおりである．

(1)(2)

put 後に（root ノード等の離脱により）keyvalue ペアが消滅した．
root ノードが key-value ペアを保持していない．
( a ) put が済んだ後で加入したノードが新たな root になった．
(b)

Network

Routing runtime interface
Routing algorithm interface

Routinglayer

Routing algorithm

図 3 Overlay Weaver の構造
Fig. 3 Components organizing runtime of Overlay
Weaver.

か示す．

3. 耐 churn 手法
ここでは，耐 churn 手法を述べる．各手法は，構造化オーバレイ構築ツールキット Overlay Weaver2),3)に実装し，その効果を測定した．

Overlay Weaver は，Dabek らの抽象化（図 2）4)に従い，ルーティング層の上に DHT やマルチキャス
トなどの高レベルサービス層が載るという構造を採っている（図 3）．この構造には，ルーティング層と高レベルサービスを自由に組み合わせられるという利点がある．たとえば，同一の DHT 実装に対して，様々なルーティング層の実装やアルゴリズムを組み合わせられるということである．
そこで，耐 churn 手法が DHT 層だけに対する実装
であるならば，ルーティングアルゴリズムに依存する

経路表が不完全といった理由で，put 時

ことなく，様々なアルゴリズムと組み合わせて用いるのルーティングが root ノードに到達しことが可能となる．これは当然であるように聞こえるが，そうでもない．耐 churn 手法は他のノードとの

なかった．

(3)

Storage

Higher-levelservices

Routing driver

Directory service interface Messaging service interface

OS/Hardware

Other
services

Applications

Routing service interface

ing
Correspond I
to KBR AP

2. churn 問題

KBR API

図 2 Key-based routing (KBR) (Dabek et al.4) の Fig. 1)
Fig. 2 Key-based routing (KBR) (Figure 1 from Dabek etal.4) ).

Application

注 アルゴリズムによっては、空間を円環としてとらえることが適切とは限らない。

CAST DOLR

DHT

Tier 0

要求元ノードI3 Scribe SplitStream Bayeux OceanStore

ルーティング経路上のノードが要求の転送中に通信をともなうため，他ノードの情報を得るために，離脱した (recursive ルーティング5) でのみ発生

ルーティングアルゴリズム固有の表（たとえば Pastryする)．

の leaf set）を参照するものも多い．耐 churn 手法をたとえば，key-value ペアを保持している root ノー

アルゴリズムに依存させないためには，ルーティング

ドが離脱してしまえば，その値は get しようがない．

層からはアルゴリズム中立な API を提供するように

しかし，put 後に root ノードが離脱してしまった場

し，ルーティング層内部への直接アクセスは注意深く合でも，別のノードに複製を作っておき，get でそれ避けなければならない．

ら複製の値を得られるならば，get を成功させることはできる．3 章で，こういった耐 churn 手法をいくつ

3.1 ルーティング層の API
Dabek らの抽象化でも，DHT 層に耐 churn 手

情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月

法として複製機能を実装できるよう，配慮がなさ

頭 2 ビットを変化させて 4 通りの値を作ればよい：

れている．ルーティング層が上位層に対して手続き

key ⊕ 010..(2 進)，key ⊕ 100..，key ⊕ 110..．しかし

replicaSet(key,max rank) を提供しているのはそのためである．この手続きは，key に対する複製を作

この方法には，通信の回数が増すという難点があるた成すべきノードの順序付きリストを返す．返されるリであれば，1 度のルーティングと複製数だけの put 要

ストは，key に対する root として適切な順にノード求で済むところ，この方法では複製の数と同じ回数のを並べたものである．つまり，先頭のノードが離脱しルーティングが必要となる．

め，今回は採用していない．root 候補リストへの複製た場合には次のノードが root となり，そのノードが今回の実装では，root 候補ノード群への put 要求

離脱した場合にはまた次のノードが root となる，とは，put 要求元ノード，root ノードのどちらが行うこいうリストである．

ともできる．どちらが行っても通信の回数は同一だが，今 回 ，耐 churn 手 法 を 実 装 す る た め に ，こ の

ノード ID の数値とネットワーク近接性の間に何か関係

replicaSet に近い機能を Overlay Weaver に用意した．ルーティングの結果としてただ 1 つの root ノードが得られるのではなく，root ノード候補のリストをがある場合は，効率に差が出る．たとえば proximity

identifier selection (PIS)6) を採用していてノード IDの数値的な近さがネットワーク近接性を反映している得られるようにした．replicaSet との違いは，ローなら，root ノードが要求を行った方が効率が良い．今カルに呼ばれる手続きではなく，ルーティングの結果

回の実装は近接性を考慮していないため，差は出ない．

としてリストが得られるという点，および，複製だけ複製に関するパラメータは次の 2 つである．

でなくいくつかの耐 churn 手法に用いられるという点• 複製数• 複製の put 要求を put 要求元ノードと root ノーである．また，Dabek らの抽象化は実証がともなっていなかったところ（6 章），本論文ではアルゴリズム
非依存な耐 churn 手法の有効性を示す．

複製数が 1 の場合，root ノードにだけ key-value ペ

ルーティング層の内部では，Routing algorithm 部
が ，replicaSet

ドのどちらが行うかと同じ意味を持つ手続き

アを保持させる．
複製とキャッシュの違いには注意されたい．キャッをシュは，get/put 時に key-value ペアを取り扱うノー

Routing driver に提供する．
以下，次の 4 手法を述べる．このうち上 3 つは，root
候補のリストを活用する．
• 複製• 加入時委譲

ドが性能向上を目的としてその値を保持しておくとい• 複数 get• 自動再 put
3.2 複製
put 時，key を担当する root ノードだけでなく，他のいくつかのノードに key-value ペアを保持させる．

3.2.1 複製群の一貫性
本研究が前提とする Overlay Weaver の DHT 実装
は，本論文で示すどの耐 churn 手法を施しても，保証できるのは eventual consistency7),8) までである．
まず，churn 状況下で複製を作成，維持するので，

rootCandidates(ID target,int maxNumber)

うものである．偶然，churn 耐性向上に寄与することはあっても，耐 churn を狙った手法ではない．とはいえ，キャッシュを複製として活用することも考えられる．

これにより，put 後に root ノードが離脱した場合で同一の key に対する value がノードによって異なるとも，get 時には他のノードから値を取得できる．複製いう状況が懸念される．上書きされるべき古い value

は，root 候補としての順位に沿って，いくつかのノーが残ってしまう場合や，複数ノードからの put のタイドに保持させる．つまりルーティングの結果として得ミングが近く競合状態が起きるといった場合である．

られる root ノード候補に保持させる．こうすること

当該 DHT 実装ではこれらの問題は起きない．同一で，put 時に root だったノードが離脱した場合でも，の key に対して複数の value が結び付き，put による
value の削除は起きないからである．これは，Bamboo9) やそれを用いる OpenDHT7) と同様の設計である．get では，put された value すべてが得られる．

ルーティングの結果，次に root として適切なノードに到達し，そのノードは複製を保持しているため getは成功する．

root 候補リストではなく，何らかの手順で key かそれでも，DHT に対する remove 操作が一部の複ら導出される複数の値をキーとして複製を put して製に対して失敗し，削除したつもりの value が得られおくという方法も考えられる．たとえば，key の先てしまうことは起こりうる．この場合にどう解決する

情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月

か，つまり，どの value を選択するかは，当該 DHT

複数 get のパラメータは，get 要求先ノード数であ実装を利用する側に任されている．DHT 実装の側かる．これが 1 の場合，root ノードにだけ要求する．

ら解決の手がかりは提供していないが，Dynamo8) の3.5 自動再 put
各ノードが，自身が保持している key-value ペアをように vector clock といった手がかりを提供することを検討している．

3.3 加入時委譲
DHT に新たに加入してきたノードに対して，そのノードが root となるような key-value ペアを他のノードから委譲する．これにより，put 後に加入したノー

DHT 上に put する．通常の put と同様に複製も作る．
この自動再 put は，通常の put，get のタイミングとは関係なく，平常時に，各ノードが自律的に行う．
key-value ペアは，加入時委譲を行うことで若干の補充はなされるものの，ノードの離脱によって減ってドが root となるような get 要求にも応えられるよういく．自動再 put はこの補充を狙った処理である．
自動再 put には，ある程度，加入時委譲と同様の効になる．
今回の実装では，新規加入ノードの方から，自身が果もある．つまり，自動再 put によって，put 後に加担当すべき key-value ペアを保持していそうなノード

入したより適切な root ノードに対して key-value ペ

いくつかに対して問合せを行う．具体的には，加入のアが渡される．ただし，自動再 put 処理には時間間隔ためのルーティングで得た root 候補のリスト（3.1 節）があるため，加入時委譲や複数 get とは異なり，自動に対し，先頭から順にいくつかのノードに問い合わせ

再 put が起こるより前の get 要求は救えない．

る．問合せを受けたノードは，新規加入ノードの方が複製数が 1，つまり root ノードだけが key-value ペ

root として適切であるような key-value ペアを返す．

アを保持する場合，自動再 put には意味がないように

新規加入ノードは返された key-value ペアを保持する．

見えるが，それでも加入時委譲と同様の効果はある．

この受け渡しの際，元から保持していた方を削除す

自動再 put のパラメータは，時間間隔である．具るわけではないので，委譲というより実際はコピーを

くつの root 候補ノードに対して問い合わせるか，で体的には，自ノードが保持している key-value 群を再put する処理と処理の間に，指定した時間だけの休止
時間をとる．また，複数ノードの自動再 put 処理が同期してしまわないよう，休止時間は乱数で増減させて

ある．

いる．

3.4 複 数 get
get 時，root ノードに対してだけでなく，いくつかのノードに対して key に対応する key-value ペアを問
い合わせ，要求する．具体的には，ルーティングの結churn 耐性向上 4 手法のうち，この自動再 put だけが，ルーティングの結果得られる root ノード候補のリスト（3.1 節）を使わない．
3.6 各手法が対象とする get 失敗の原因

果として得られる root ノード候補に対して問い合わ

表 1 に，それぞれの耐 churn 手法が，2 章で述べた
get 失敗原因のどれを対象としたものかを整理する．
複製は，ノード離脱にともなって DHT から keyvalue ペアが消滅してしまうことを防ぐ．自動再 put
は，ノード離脱にともなう複製数の減少を補う．ただ行っている．
加入時委譲のパラメータは，新規加入ノードからいせる．これにより，put 後に DHT に加入したノード
が root となった場合でも，新ノード加入前の root に対しても get を要求するので，値を取得できる場合がある．

put 後に加入したノードが root になるというこのし，複製数が 1 の場合，この補充効果はない．

状況は，前述の加入時委譲でも救うことができる．ど

加入時委譲と複数 get は，root ノードそのものがちらの手法でも救えるということは，両手法の効果は

key-value ペアを保持していない，という状況への対策である．加入時委譲はその状況を防ぎ，複数 get は重複するということである．
複数 get は，何らかの理由で，put 時のルーティン

その状況でも key-value ペアを取得できるようにする．

グが最適な root ノードではなく次善のノードに到達

root ノードが key-value ペアを保持しないという状

してしまった場合にも有効である．ルーティングアル

況は，自動再 put でも救える場合がある（3.5 節）．

ゴリズムによっては，経路表が完全でない場合に root
ノードに到達しないことは起こりうる．この場合，次recursive ルーティングの最中に経路上のノードが離脱するとルーティングを完遂できないという失敗原

善のノードが key-value ペアを保持してしまうが，こ因に対しては，今回は解決を与えていない．複数の問の手法によって，次善のノードに対しても get を要求

合せを並行して送出するといった対策がありうる．

できることがある．

情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月

表 1 各耐 churn 手法が対象とする get 失敗原因
Table 1 Causes of get failure each technique treats.

key-value ペアが消滅
root が key-value ペアを保持せず:
新ノードが root に
put 時 root 不到達
経路上ノードが離脱

複製
√

加入時委譲

複数 get√√√

自動再 put√（複製が前提）√√入させることで，DHT に加入しているノード数をつ

4. 各手法の効果

ねに 1000 に保つ．ノード数を保つというこの churn

3 章で示した耐 churn 手法の効果を計測した．計算機 1 台の上で 1000 ノードを動作させ，churn を発生させて，DHT の get が成功した回数を数えた．
実験には，Overlay Weaver が提供する分散環境エ

モデルは，Rhea らの実験10) と同じものである．加藤らの churn モデル11),12) はこれとは異なり，離脱直後に加入を起こさないため，ノード数が変動する．

churn の 頻 度 は 平 均 2 回/秒 と し ，ポ ア ソ ン 分

ミュレータを用いた．このエミュレータは，計算機布に従って発生させた．ノードの平均生存時間は（Java 仮想マシン）1 台上で多数のノードを動作させ，1000(ノード)/2(ノード/秒) = 500 秒 となる．
通信のタイムアウトは 3 秒，ルーティングのタイム
アウトは 10 秒と設定した．つまり，1 度のルーティ
ング（put や get）のうちに 4 回，離脱済みのノード

それらノードを与えられたシナリオに従って制御できる．ここで動作するコードは，通信部分を除き，実環境で動作するものと同一のものである．
このエミュレータが提供する通信層は，送信されたへの通信を試みると，確実にルーティングがタイムア

メッセージを，計算機の性能が許す限りの速さで宛先ウトする．通信のタイムアウトが起きた場合には，経ノードに届ける．ここで，メッセージのコピーは行わ

路表から通信相手のノードを削除する．

れないため，帯域幅は無限大となっている．つまり，実験には 2.8 GHz Pentium D プロセッサ，x86-64

LAN やインターネットなど物理的な通信媒体に起因

用 Linux 2.6.21，x86 用 Java 2 SE 5.0 Update 12 のする帯域幅の制限や通信遅延がない，理想的な通信環

HotSpot Server VM を用いた．Overlay Weaver の版は 0.6.4 である．すべての実験は 6 回行い，最良値と最悪値を捨て，残り 4 回分の値を平均したものを結果として採用した．
4.2 結
果

境を模していることになる．メッセージが失われることがないため，churn による get 失敗はノードの離脱と加入という通信環境とは無関係の原因によってのみ起こる．このため，本実験の結果，つまり get 成功率

図 4 に結果を示す．実験は，Overlay Weaver が提への通信環境の影響は小さいと考える．

4.1 条
件
今回は，ノードの離脱と加入が頻繁に起こる churnのシナリオを生成して使用した．すべての実験で同一のシナリオを用いた．
シナリオの内容は次のとおりである．
( 1 ) 1000 ノードを起動する．
( 2 ) 1000 ノードを 0.15 秒ごとに DHT に加入させる．

供するすべてのルーティングアルゴリズムと，itera-

tive/recursive ルーティング5) の全組合せに対して行った．ここでは，Chord，Pastry，Kademlia を iterative
ルーティングで用いた際の結果を示す．
グラフの縦軸が，get 1,000 回のうち成功した回数を示す．この値が 1,000 に近いほど良い結果である．
横軸は，複製の数（1〜4）を表す．各アルゴリズムについて，横に 2 つのグラフが並んでいる．左は自動再(3)1000 通りの key-value ペアを 0.2 秒ごとに put
する．
( 4 ) 1000 通りの key-value ペアを 0.2 秒ごとに getする．
put，get を行うノードは，シナリオ生成時に乱数でput なし，右は自動再 put ありの結果である．自動再put の間隔は，平均 30 秒とした．
グラフ中の 4 本の線は，それぞれ，加入時委譲と複数 get のパラメータが異なる．加入時委譲のパラメー
タは，新規加入ノードから問い合わせる先のノード数選んだ．

であり，0（加入時委譲なし）または 2 とした．複数

churn は，put 開始時から get 終了までの間，起こし続けた．ノードを離脱させた直後に別のノードを加

get のパラメータは，get 要求先ノードの数であり，1（複数 get なし）または 2 とした．グラフ中に “数字-情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月

1000

1000
900
800
数
功700
成
te
g 600
500
400

Chord

900

自動再putなし

800
数
功700
成
te
g 600

0-1
2-1
0-2
2-2

500
400
複製数 1

2

3

Chord

自動再putあり

複製数 1

4

0-1
2-1
0-2
2-2

2

3

4

(a) Chord

1000
900
数800
功700
成
te
g 600
500
400

1000
900
800
数
功700
成
te600
g
500
400

Pastry
自動再putなし

0-1
2-1
0-2
2-2

複製数 1

2

3

Pastry
自動再putあり

複製数 1

4

0-1
2-1
0-2
2-2

2

3

4

(b) Pastry

1000
900
800
数
功700
成
te
g600

1000

Kademlia

900

自動再putなし

0-1
2-1
0-2
2-2

500
400
複製数

数800
功700
成
te
g600

1

2

3

4

500

Kademlia

400
複製数

1

0-1
2-1
0-2
2-2

自動再putあり

234(c) Kademlia
図 4 各手法の効果
Fig. 4 Results of presented techniques.

数字” とあるのは，両パラメータを表しており，“加入
時委譲-複数 get” という順に並んでいる．

4.3 考
察
図 4 のグラフから次を読み取ることができる．
• 複製数が多いほど，get 成功率が上がっている．
• 加入時委譲と複数 get は，どちらも，行った方がget 成功率が上がっている．
• 自動再 put なしの場合，Pastry と Kademlia では，複数 get（get 要求先：2）よりも加入時委譲（問合せ先：2）の方が効果が高かった．Chord では逆に，複数 get の方が効果が高かった．
• 自動再 put を行うと，複数 get や加入時委譲による差がほとんど見られなくなった．

• 複製数 3 よりも 4 の方が結果が悪い場合がある．
この傾向は，recursive ルーティングでもまったく同様であった．また，Tapestry の傾向は，アルゴリ
ズム上の類似点が多い Pastry と同様であった．
なお，耐 churn 手法の適用にもかかわらず get の失敗が起きているのは，次の原因によるものであった．

• 耐 churn 手法が追いつかなかった．

情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月

複製を保持する全ノードの離脱，新たな root に対する自動再 put より早い get，など．
• 新たに加入したノードの経路表が不完全で，適切な root に到達しなかった．

• タイムアウトが多数回起き，ルーティングを完遂できなかった（4.1 節）．
これらの結果はアルゴリズム間の優劣を表すものではない点に注意されたい．各アルゴリズムには固有のパラメータ（例：Chord の stabilize 間隔）があ

表 2 各耐 churn 手法の処理（通信）タイミング
Table 2 DHT processes in which each technique isinvolved.
加入
複製
加入時委譲
複数 get
自動再 put

put
√

get

平常時

√
√
√

き続ける．つまり，加入，put，get が起きなくても費り，churn 耐性に影響を与えるものもある．今回は，Overlay Weaver 0.6.4 の既定のパラメータを用いた．
ここまでで，今回示した各手法の効果を確認できた．
しかし，各手法を採用するか否か，またそのパラメータを決めるためには，効果だけでなく，費用対効果を用がかかり続ける．
ここでたとえば，DNS のような，加入や put より
get の頻度がはるかに高いような応用を想定した場合，複数 get の通信費用は高くつくが，複製と加入時委譲の費用は相対的に安くあがる．すると，頻度の低い手調べる必要がある．次章では，費用対効果を考察する．

法については，たとえば複製数を増やすといった，1回あたりの費用が高くつくパラメータ設定が可能とな

5. 費用対効果

る．一方で，センサデータの保持といった，get と比本章では，耐 churn 手法の費用対効果を算出する方法を考察する．

較して put もそれなりに起きるような応用であれば，複製の通信費用も無視できない．

まず，効果は get 成功率として表れるので，定量的このように，耐 churn 手法の費用を算出するためにに表すとしたら，get 成功率の関数とすることが適切

は，加入，put，get それぞれの頻度を何かしら仮定すだと考える．

る必要がある．定量的な算出には，key-value ペアの続いて，費用について検討する．耐 churn 手法の適用によって増加しうる費用には，次がある．

値やサイズも含めて，応用に則したシナリオや，現実のトレースデータを用いた実験が必要となる．

• 通信の回数と量• 加入，put，get に要する時間• メモリやストレージの消費量• プロセッサの処理
従来研究10),11) は，通信量と get に要する時間

4 章の実験で用いたシナリオ（4.1 節）は，加入，put，
get の回数が同じという人工的なものであり，この実験について通信量を調べることにはあまり意味がない．

（lookup latency）に着目してきた．他の費用が重視さとはいえ，複製数を n とすると，1 とした場合とDabek らの階層モデル（図 2）4) も，複製機能を実装するための API を定義している（3.1 節）．そこでは，階層モデルおよび層間の API が提案，考察されており，実証はともなっていない．
本論文では，類似の API を用いつつ，手続きの種比較して n 倍のストレージ（かメモリ）を消費する．

類を増やすことなく，複製に加えて，加入時委譲，複データ量が多い場合，組み込み用途などで容量が限ら

数 get，自動再 put といったいくつかの耐 churn 手法

れる場合には，費用として充分に高価なものとなりうを実装できることを示した．また，4 章では，様々なる．つまり，費用を考える際には，応用の環境を想定

ルーティングアルゴリズムと組み合わせた場合の各手することが欠かせない．

法の効果を示した．

れていないのは，現在の PC や LAN，インターネットで動作する DHT を想定すると，それらはボトルネッ
クとならないからであると推測する．

6. 関 連 研 究ることは，put の回数が多いほど複製の費用は高くな

Rhea らは，彼らの DHT 実装 Bamboo9) に実装
した耐 churn 手法を評価した10) ．実験には，ネット
ワークエミュレータ ModelNet を用い，40 台の PC
で 1000 ノードを動作させている．経路表中に残る離応用ごとに異なる，系の振舞いも考慮する必要があ
る．表 2 に，耐 churn 手法それぞれについて，処理
および通信が起きるタイミングを示す．この表から判り，get の回数が多いほど複数 get の費用は高くなる

脱ノードの情報を，能動的かつ定期的に検出するか，ということである．また，自動再 put では，put され通信失敗をもって受動的に検出するかを比較している．

ている key-value ペアの数に応じた通信が継続的に起また，TCP にならった通信タイムアウト時間の調整

情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月

や proximity neighbor selection（PNS）6) の効果を，動作させ，Chord，Pastry，Kademlia での各手法のget に要する時間という形で計測し，評価している．
それらの手法は，Dabek らの階層モデルでいうと，DHT 層ではなく，その下のルーティング層に実装する効果を示した（4 章）．
続いて，各手法の採否やパラメータを決める際に欠かせない費用対効果を算出する方法を考察した．効果手法である☆ ．それに対し，本論文で述べた各手法は，は 4 章に示したが，費用は，系の振舞い，具体的には，DHT 層が対象である．Rhea らの手法10) は，Bamboo の実装や Pastry 由来のアルゴリズムを前提としているのに対し，本論文の各手法は，DHT 層への実装であるため，自然と，様々なルーティングアルゴリ

加入，put，get の頻度に大きく依存するため，何かしらの応用を想定してエミュレーションシナリオを作成する必要がある，という結論を得た．
今後は，DNS，センサネットワークなど，具体的な応用を想定し，効果に加えて費用も計測し，耐 churnズムと組み合わせて用いることができる．
本論文の手法と Rhea らの手法は，対象とする層が手法の採否やパラメータ設定の方法論を確立していく．

異なるため，競合はせず，組み合わせて用いることが謝辞 日頃から議論させていただいている加藤大志

できる．実際に，Overlay Weaver の通信層は，実環

氏，門林雄基氏，土井裕介氏，藤田昭人氏，吉田幹氏，

境では，彼らの提案する TCP スタイルのタイムアウ

WIDE プロジェクト IDEON ワーキンググループの

ト時間の調整手法を採用している．

諸氏に深く感謝いたします．

加藤らは，彼らが開発したネットワークエミュレー
タ peeremu を用いて，いくつかの DHT 実装を評価
した11),12) ．評価対象は，Bamboo，Chord，Accor-

dion，FreePastry であり，十数台の PC を用いて最大で 1000 ノード規模の実験を行っている．churn 時の get 成功率と，get に要する時間を計測している．
そもそも churn 耐性を高めずに済ませるスーパノー
ドというアプローチもある．通常のノードの中から，性能やネットワーク帯域幅，それまでの稼働時間などに応じて，強力かつ安定稼働しそうなノードをスーパノードとして選出する．DHT（オーバレイ）の構築，
維持はスーパノードだけが行い，通常のノードはスーパノードからサービスを受ける．
これにより，DHT に要求される churn 耐性をある程度下げることができる．また，伝統的な DHT アル
ゴリズムは，全ノードが双方向に通信できることを前提とするので，NA(P)T などの理由で双方向通信が困
難なノードはスーパノードとしない，つまり DHT に加入させないことで，DHT の利用が容易になるという利点もある．しかしそれでも，ノードの離脱と加入を想定しないわけにはいかない．

7. ま と め
本論文では，DHT を対象としたいくつかの耐 churn
手法と，それらの効果を示した．各手法は，Dabek らの階層モデルでいうと DHT 層に対して実装するものであり，そのため，様々なルーティングアルゴリズムと組み合わせて用いることができる．各手法を Overlay

Weaver に実装し，いくつかのアルゴリズムとともに☆

Bamboo はそもそもこの階層モデルを採っていない．

参 考

文

献

1) Pappas, V., Massey, D., Terzis, A. and Zhang,
L.: A Comparative Study of the DNS Design
with DHT-Based Alternatives, Proc. INFOCOM 2006 (2006).
2) 首藤一幸，田中良夫，関口智嗣：オーバレイ構
築ツールキット Overlay Weaver，情報処理学会
論文誌: コンピューティングシステム， Vol.47,
No.SIG12（ACS 15） (2006).
3) Overlay Weaver: An Overlay Construction
Toolkit. http://overlayweaver.sf.net/.
4) Dabek, F., Zhao, B., Druschel, P., Kubiatowicz, J. and Stoica, I.: Towards a Common API for Structured Peer-to-Peer Overlays,
Proc. IPTPS’03 (2003).
5) 首藤一幸，加藤大志，門林雄基，土井裕介：構造化オーバレイにおける反復探索と再帰探索の比較，情報処理学会研究報告, 2006-OS-103-2 (2006).
6) Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S., Shenker, S. and Stoica, I.: The Impact of DHT Routing Geometry on Resilienceand Proximity, Proc. SIGCOMM 2003 (2003).
7) Rhea, S., Godfrey, B., Karp, B., Kubiatowicz,
J., Ratnasamy, S., Shenker, S., Stoica, I. andYu, H.: OpenDHT: A Public DHT Service and
Its Uses, Proc. ACM SIGCOMM 2005 (2005).
8) DeCandia, G., Hastorun, D., Jampani, M.,
Kakulapati, G., Lakshman, A., Pilchin, A.,
Sivasubramanian, S., Vosshall, P. and Vogels,
W.: Dynamo: Amazon’s Highly Available Keyvalue Store, Proc. SOSP 2007 (2007).
9) The Bamboo Distributed Hash Table.
http://www.bamboo-dht.org/.
10) Rhea, S., Geels, D., Roscoe, T. and Kubiatowicz, J.: Handling Churn in a DHT, Proc.

情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月

USENIX ’04 (2004).
11) Kato, D. and Kamiya, T.: Evaluating DHT
Implementations in Complex Environments by
Network Emulator, Proc. IPTPS 2007 (2007).
12) 加藤大志，神谷俊之：ネットワークエミュレー
タによる大規模 DHT 性能評価手法の提案，分散システム/インターネット運用技術シンポジウム
2006 (2006).
(平成 19 年 7 月 23 日受付)
(平成 19 年 11 月 19 日採録)

首藤 一幸（正会員）

1996 年早稲田大学理工学部情報学科卒業．1998 年同大学助手．2001
年同大学大学院理工学研究科情報科学専攻博士後期課程修了．同年産業技術総合研究所入所．2006 年ウタゴエ（株）取締役最高技術責任者．博士（情報科学）．分
散処理方式，プログラミング言語処理系，情報セキュ
リティ等に興味を持つ．SACSIS2006 最優秀論文賞．

IPA 未踏ソフトウェア創造事業スーパークリエータ認定．情報処理学会平成 18 年度論文賞．情報処理学会
平成 19 年度山下記念研究賞．日本ソフトウェア科学会，IEEE–CS，ACM 各会員．

情報処理学会論文誌: コンピューティングシステム,
Vol.49, No.SIG2 (ACS 21), pp.1-9, 2008年 3月