複製による負荷分散を可能にした P2P プロトコル の提案

複製による負荷分散を可能にした P2P プロトコル の提案

著者 佐治, 和弘, 有次, 正義

雑誌名 日本データベース学会letters

巻 5

号 2

ページ 9‑12

発行年 2006‑09‑21

その他の言語のタイ トル

A P2P Protocol with Load Balancing using Replicas: A Proposal

URL http://hdl.handle.net/2298/10949

――――――――――――――――――――――――――――――――――――

複製による負荷分散を可能にした P2P プロトコルの提案

A P2P Protocol with Load Balancing using Replicas: A Proposal

佐治 和弘

    有次 正義

Kazuhiro SAJI  Masayoshi ARITSUGI  

P2P システムに対する効率的な負荷分散は重要な問題で

ある．BATONでは，各ノードが自律的に自身の持つ値の範

囲を調整し，負荷分散を実現している．しかし，システム内 に人気の高いオブジェクトが存在する場合，人気オブジェク トを持つノードのオブジェクト送信負荷が高くなってしま

い，BATONの負荷分散だけでは対応しきれなくなってしま

う恐れがある．本稿では，BATONにSCOPEで提供されて いる複製の分散管理手法を組み合わせ，人気オブジェクトを 持つノードのオブジェクト送信負荷を，複製を持つノードに 分散する P2Pプロトコルを提案，検討し，今後考えなけれ ばならない課題を明らかにする．

It is important to realize efficient load balancing mechanisms in P2P systems. BATON, a P2P system, supports a mechanism in which each node changes the range of objects to be managed autonomously. However, if there are nodes managing objects with high request rates in a network, the mechanism of BATON may fail to achieve good load balance because of the high loads for serving such objects. In this paper, we propose a P2P protocol in which we integrate a method of replica management proposed by SCOPE into BATON and discuss issues for developing a system with good load balance mechanisms.

1.

Structured P2Pシステムの代表的な手法として，DHTを 用 い た 手 法 が い く つ か 提 案 さ れ て お り[1]，Chord[2]， Pastry[3]等のシステムが開発されている．これらのDHTを 用いた手法は，効率的なデータの配置方法と探索方法を提供 するが，データに識別子を割り当てるために用いるハッシュ 関数が似ているデータ同士にも全く異なる識別子を割り当 て，ばらばらにデータを配置するため，レンジクエリをサポ ートするためのデータの配置には不適切である．また，ハッ シュ関数を用いない場合，Chordのようなリング型オーバー レイではデータの偏りがデータの分布に大きく影響してし まうため多くのデータを保持するノードが出現してしまう 恐れがある．

レンジクエリをサポート可能なオーバーレイネットワー クとして，BATON[4]が挙げられる．BATONではP2Pのオ

♥ 学生会員  群馬大学大学院工学研究科情報工学専攻博士 前期課程  kazuhiro@dbms.cs.gunma-u.ac.jp

♦正会員  群馬大学工学部情報工学科  aritsugi@cs.gunma-u. ac.jp

ーバーレイネットワークの構造に平衡2分木を用いており，

DHT を用いた手法ではサポートできなかったレンジクエリ のサポートが可能となっている．また，BATONでは各ノー ドが，自律的に自身が受け持つ値の範囲を調節し，システム 内の各ノードに掛かるクエリ数，アクセス数，管理するデー タ数等の負荷を均一に保つ機能を持つ．

しかし，多くのアクセスを受けるような人気オブジェクト が存在する場合，人気オブジェクトを管理するノードは過負 荷状態となってしまい，値の範囲調節だけでは対応しきれな くなってしまう恐れがある．この問題の解決策の1つとして，

人気のあるオブジェクトの複製を生成して他のノードに持 たせ，負荷を分散する方法が考えられる．しかし複製が多数 存在する場合を考えると，複製の管理は容易ではない．

これらの問題を解決する手法として，本稿ではBATONに

SCOPE[5]で提案されている複製の分散管理手法を組み合わ

せることで，効率的な複製の分散管理の手法と，複製を用い て人気オブジェクトの送信負荷を分散する手法を提案する．

実際にeDonkeyのトラフィックを計測した文献[6]による と，downloadストリームの平均サイズが2.48M bytesなの に対し，non-download ストリームの平均サイズが 16.7K

bytesと計測されており，データダウンロードに使われるデ

ータのサイズはそれ以外のメッセージデータのサイズに比 べて非常に大きく，総送信コストの大半がオブジェクトの送 信コストであることがわかる．本稿では，オブジェクト送信 量の多いノードが過負荷状態であると考え，過負荷状態であ るノードで生じたオブジェクト送信作業のいくつかを複製 を持つノードに任せることで，過負荷状態の解消を目指す．

さらに，提案手法では，複製の位置情報を分散管理すること で，1 つのオブジェクトの複製が多数生成された場合も，1 ノードに複製の管理コストが集中することを避けることが できる．

2.

2.1  基本構造

本手法では，オーバーレイネットワークに BATON [4]の 平衡2分木の構造を用いる．図1にBATONの木構造の例と ノード m が持つルーティングテーブルを示す．各ノードに はlevelとnumberが割り当てられる．levelは木構造内での そのノードの高さ，numberは同一level内でのノードに左 から番号を割り振ったものである．ノードの左隣，右隣のノ ードをそれぞれleft adjacentノード，right adjacentノード と呼ぶ．各ノードは親ノード，子ノード，左右の adjacent ノードへのリンクを持つ．また，各ノードは，右ルーティン グテーブルと左ルーティングテーブルを持ち，level L ^のノ ードはそれぞれのテーブルに同じlevelのノードを最大でL 個管理できる．

numberがNのノードの右（左）ルーティングテーブルのj 番目のエントリには，number N+2^j-1（N-2^j-1）のノードへの リンクが置かれる．該当するノードがない時は，ルーティン グテーブルのエントリを空にする．例えば図中のノード m の左ルーティングテーブルには，ノード m と同じlevel 3で，

numberが6-2⁰=5, 6-2¹=4, 6-2²=2のノード l, k, i へのリン クを，右ルーティングテーブルにはlevel 3 で，numberが 6+2⁰=7, 6+2¹=8のノード n, o へのリンクを登録する．

――――――――――――――――――――――――――――――――――――

    図 1  BATON の木構造とルーティングテーブル [4] 

Fig.1 An example of tree structure and routing table  of BATON [4] 

図 2  各ノードの値の範囲の例 [4] 

Fig.2 An example of tree with value ranges of nodes [4] 

木構造内の全ての葉ノードと内部ノードには値の範囲を 割り当てる．各ノードに割り当てられた値の範囲の例を図2 に示す．各ノードは left adjacent ノードの最大値以上から right adjacentノードの最小値未満の値の範囲を管理する．

例えば図中のノード e は，ノード j の最大値 23 以上，ノ ード p の最小値29未満の値の範囲を管理している．

2.2  SCOPEの分散管理手法

先に説明したBATONの平衡2分木の他に，提案手法では 複製の分散管理を行うために SCOPE[5]で用いられている RPT(replica partition tree)を使用する．3ビットの識別子空 間において，オブジェクト101の複製が識別子000のノー ドと識別子111のノードに配置された時のRPTの例を図3 に示す．RPT は各オブジェクトに対して生成される．RPT の各ノードを代表ノード，各代表ノードが持っている2ビッ トの値をパーティションベクトルと呼ぶ．複製の分散管理手 法を，RPTの説明と共に述べる．

BATONのノードが，あるオブジェクトを自身の値の範囲 に含んでいる場合，ノードはそのオブジェクトのPrimaryノ ードであると言う．SCOPEでは，Primaryノードが過負荷 状態となることを避けるためにRPTを構築し，複製の情報を 各ノードに分散して記録する． SCOPEでは識別子空間をパ ーティションに分割し，パーティションごとに代表ノードを 決める．代表ノードは，自身が代表するパーティションをさ らに分割して得られる各サブパーティションにおける複製 の有無をパーティションベクトルに記録する．下位のサブパ ーティションも同様に分割され，最も小さなパーティション の代表ノードのパーティションベクトルは複製を持つノー ドの識別子を直接示す．1回の分割で得られるパーティショ

ンの数とパーティションベクトルの長さは等しくなり，その 長さは2ⁿで設定される．各代表ノードが管理するパーティシ ョンの範囲を図中のSpaceに示す．代表ノードの決定方法を 図3のオブジェクト5=101の代表ノードの決定方法を例と して説明する．ここで，パーティションベクトルの長さは 2¹=2である．

z Original identifier space：識別子空間の101にオブジ ェクト5が割り当てられる．RPTのルートノードが決 まる．

z First level partition：下位2(=3-n)ビットを固定し，上 位1ビットを可変にする．この時，001を値の範囲に含 むBATONのノードと，101を値の範囲に含むBATON のノードがfirst level partitionの代表ノードとなり，

RPTの中間ノードとなる．

z Second level partition：下位1ビットを固定し，上位2 ビットを可変にする．この時，001，011，101，111を 値 の 範 囲 に 含 む BATON の ノ ー ド が second level partitionの代表ノードとなり，RPTの葉ノードとなる．

図 3  RPT の例 [5] 

Fig.3 An example of RPT [5] 

RPTの各代表ノードは，下位のサブパーティションの複製 の有無を，パーティションベクトルを使用して示す．下位の パーティションに複製が存在する時はパーティションベク トルの対応するビットに1を立て，存在しないときはパーテ ィションベクトルの対応するビットを0とする．RPTの葉 ノードのパーティションベクトルは各識別子における複製 の有無を直接示している．図 3 において，オブジェクトの Primaryノードであるルートノード101は，下位サブパーテ ィション000〜011に複製が存在することをパーティション ベクトルの左側のビットに1を立てることで示し，サブパー ティション100〜111に複製が存在することをパーティショ ンベクトルの右側のビットに1を立てることで示している．

2.3  オペレーション 2.3.1  Subscribe

複製を持つノードをそのオブジェクトの Subscriber と呼 ぶ．Subscribeオペレーションは，Subscriberが複製の位置

を Primary ノードに知らせるために行う処理である．本稿

ではオブジェクトを受信した際に，検索要求のクエリを発行 したノードに複製を配置する．この手法はオーナ複製法と呼 ばれており[7]，Gnutella でも用いられている方式である．

Subscriber は自身の識別子の下位ビットをオリジナルデー

タの識別子と一致させることで，RPTの葉ノードとなる代表 ノードを探す．図3において，ノード 010がオブジェクト 101の複製を持ってSubscriberとなった時，ノード010は まず，下位1ビットをオブジェクト101の識別子と一致させ て，RPTの葉ノードである代表ノードが011であると判断 し， Subscribeオペレーションを送る．オペレーションを受 け取った代表ノード011は，パーティションベクトルの左側

――――――――――――――――――――――――――――――――――――

のビットに1を立てる．同様の処理をRPTのルートノード，

またはノード001のような既に1の立っているパーティショ ンベクトルを持つ代表ノードに辿り着くまで続ける．ノード 010が複製を消去する時はUnsubscribeオペレーションを実 行する．ノード010は代表ノード011を探索し，ノード011 はパーティションベクトルの左側のビットを0にする．同様 の処理をRPTのルートノード，またはパーティションベク

トルに2つ以上1が立っている代表ノードに辿り着くまで続

ける．

BATONでは各ノードが値の範囲を持ち，範囲は動的に変

化する．本システムでは複製を持つノードの値の範囲が変化 しても RPTを維持し，複製の位置を代表ノードを辿って把 握できるように，複製をノードの値の1つにマッピングする．

例えば図2のノードdが複製を生成した時，複製は5，6，7 のいずれかの値にマッピングされる．値の範囲が変化し，ノ ード d の値の範囲が 5〜6となり，代わりにノード i の値 の範囲が8〜11から7〜11に変化した時，値7の管理はノー ド d からノード i に移るので，値7にマッピングされてい た複製とパーティションベクトルはノード i に移動する．複 製のマッピングにはSubscriber が管理する値の範囲の内か らランダムに1つの値を選ぶ．

2.3.2  Exact Match Query

データ v を探索するExact match queryを発行，または 受け取ったノードはBATONのSearch exactアルゴリズム に従ってデータ v の探索を行う．探索は， v の値を範囲内 に含むノード，もしくは v の複製を持つノードに辿り着く まで行われる．探索に必要なステップ数はO(logN)である．

探索後，ノードはオブジェクト送信要求を発行したノード に，要求されたオブジェクトを返す．ここで Primary ノー ドが過負荷状態になっている時は，オブジェクトの送信作業 をSubscriberに頼む．Primaryノードはまずシステム内に おけるオブジェクトの複製の有無をパーティションベクト ルから確認し，複製が存在すれば下位の代表ノードにオブジ ェクト送信要求を転送する．要求を受けた代表ノードは，パ ーティションベクトルから Subscriberの位置を判断し，下 位の代表ノードにオブジェクト送信要求を送る．オブジェク ト送信要求はRPTを辿りSubscriberまで届けられる．代表 ノードを持つBATONのノードが図3の識別子011〜101を 値の範囲に持つ場合，ノードは，自身の持つ4つのパーティ ションベクトルの中から，ビット1が立っていて，最も下位 にある，Space[100,111]の代表ノード101のパーティション ベクトルを参照し，下位の代表ノード111にオブジェクト送 信要求を送る．

各 代 表 ノ ー ド 間 の オ ブ ジ ェ ク ト 送 信 要 求 の 送 信 に は Search exactを使って，O(logN)ノードを経由して送られる．

RPTを辿ってSubscriberを見つけるために，Search Exact を送信する回数は平均でO(logN)なので，Subscriber発見の ために必要となるホップ数は，平均でO^（log²N^{）となる．}

Exact match queryによる探索が，オブジェクトの複製を見 つけないままPrimaryノードに辿り着いた場合，Primaryノ ードはオブジェクト送信要求をSubscriberに送るか，自身が 要 求 さ れ た オ ブ ジ ェ ク ト の 送 信 を 行 う か 判 断 す る ． Subscriberに送信要求を送る場合，複製発見までに多くのノ ードを経由する必要があるので，Primaryノードが過負荷状 態である場合以外では，Primaryノードがオブジェクトの送 信を行うのが望ましい．本稿では，単位時間あたりのオブジ ェクト送信回数が閾値Ａ を越えたPrimaryノードは，Ａ+1 回目以降のオブジェクト送信処理のa% をSubscriberに行

わせることで負荷を分散する．

2.3.3  Range Query

Range queryもExact match queryと同様の方法で処理 される．まず検索する範囲を値の範囲に含むノードをExact match query で1つ探し，そこから左右のadjacentノード を辿り，残りの検索範囲を持つノードを探す．検索範囲がX 個のノードでカバーされている時，検索に必要なホップ数は O(logN) + O(X)である．

2.3.4  Update

更新処理は，Primaryノードがオブジェクトを更新した時，

またはPrimaryノードがSubscriberからオブジェクトの更 新要求を受け取った時に始まる．更新の通知は Primary ノ ードからRPTを辿り，全てのSubscriberに送られる． RPT を使うことにより Primary ノードは複製の位置の管理コス トをパーティションベクトル維持のみに抑えることができ，

更新情報も1レベル下位の代表ノードに送るだけで済むため，

Primary ノードにかかる更新情報データの送信負荷を分散

することができる．

2.3.5  Network Restructuring

ネットワークの再構築はオーバーレイネットワークの平 衡木のバランスが崩れた時に行われるadjacent linkを経由 してノードをシフトしていく作業であり，BATONで提供さ れている機能である．ネットワーク再構築の際には，ノード 間のオブジェクトの移動は起きず，変更されるのはノードの level，number，ルーティングテーブルであり，RPTにも影 響はない．

2.3.6  Join and Departure

ノードの参加・離脱はBATONのオペレーションを使用す る．また，ノードの参加・離脱時にノード間で値の範囲の移 動が起きた際には，移動が起こった識別子にマッピングされ ているオブジェクト，複製，パーティションベクトルも共に 移動する．

2.3.7  Data Insertion and Deletion

オブジェクトの挿入と削除するオブジェクトの発見には，

BATONのオペレーションを使用する．オブジェクトの削除

が行われた時，Primaryノードはネットワーク内に存在する オブジェクトの複製を削除する必要があるので，削除命令を 送信する．PrimaryノードはRPTを辿り，全てのSubscriber に通知を送る．通知を受け取った各レベルの代表ノードはパ ーティションベクトルの値から複製の位置を判断し，下位レ ベルの代表ノードに削除命令を送信する．削除命令を送信後，

代表ノードは削除されたオブジェクトに関するパーティシ ョンベクトルを削除する．

2.4  Node failure

ノードがFailした際には，BATON，SCOPEの修復作業 を実行し，オーバーレイネットワークとRPTの修復処理を 行う．Failしたノードのオブジェクトの複製が他ノードに存 在する場合は，修復されたノードはRPTを辿り，オブジェ クトをSubscriberノードから修復することが可能である．

3.

提案手法の有効性を示すためにシミュレータを用いて評 価実験を行い，提案手法で示した複製を用いた手法と，

BATONで提案されている複製を用いない手法を比較した．

0〜1023の識別子空間中に256個のノードと1000個のオブ ジェクトを配置した．各オブジェクトには0〜1023のいずれ かの値をランダムに割り当て，オブジェクトの識別子に重複

――――――――――――――――――――――――――――――――――――

はないものとする．以上の状態で3000回のSearch Exactを 発生させる．オブジェクト k に対するSearch Exactオペレ ーションの発生確率QkはZipf法則[8]に従い，以下とした．

∑

−

= ₁₀₀₀−

1 m

k m

Q k

α α

実験ではα=1とし，Primaryノードは5回目以降のオブジ ェクト送信処理の75%をSubscriberに任せることとした．

図 4  複製未使用時の各ノードのオブジェクト送信回数   Fig.4 Number of object sending in BATON 

図 5  提案手法における各ノードのオブジェクト送信回数  Fig.5 Number of object sending in our proposal  シミュレーション時に各ノードが送信したオブジェクト の総数を図4，5に示す．図4は複製未使用時のオブジェク ト送信回数である．人気オブジェクトを持つノードの送信回 数が他に比べ大きくなっていることがわかる．これに対して 本手法によるオブジェクト送信回数を示した図5では，ノー ド間のオブジェクト送信回数の偏りが解消されていること がわかる．

複製を用いることによるシステムの変化を表1にまとめる．

提案手法で複製を利用する場合は，Primaryノードを探索し てからさらに Subscriberを探しに行くため，ホップ数の最 大値が増大してしまう．ただし，ホップ数の平均値は小さく なった．これは，探索の途中で複製を持つノードを偶然見つ けるケースが提案手法では増えたためと思われる．複製を管 理するために増加するコストを計測するために，Subscribe オペレーションのメッセージ数と，1ノードが持つパーティ ションベクトル数を計測した．いうまでもないが，これらの コストは複製を利用することにより発生してしまったもの である．これらの値をなるべく小さく抑えつつ，複製の分散 管理を実現して，複製を利用した P2P の効果的な負荷分散 を実現することは，今後の課題の1つである．

表 1  実験結果  Table 1 Experimental results

提案手法 複製未使用

ホップ数平均値 4.52 4.96

ホップ数最大値 22 12

Subscribeメッセージ数合計 15645 0

Subscribeメッセージ数平均 61.11 0

パーティションベクトル数平均 24.87 0

4. おわりに

本稿では，BATONにSCOPEで提供されている複製の分 散管理手法を組み合わせることで，人気オブジェクトを持つ ノードのオブジェクト送信負荷を，複製を持つノードに分散 する P2P プロトコルを提案し，シミュレーションにより提 案手法の有効性と問題点を示した．

今後の課題として，複製の配置方法の改善が挙げられる．

提案手法ではRPTを用いて複製の分散管理を実現できるが，

RPTを使用しての複製の探索や，レンジクエリの複製による サポートを行う時，複製を発見するまでに多くのノードを経 由しなければならないことが問題として挙げられる．また，

単純な複製の配置方法を含めたより詳細な比較，評価実験を 行い，複製の管理にSCOPEの分散管理手法を用いることの 有効性をさらに明確にすることも必要である．

[文献］

[1]H. Balakrishnan, M. F. Kaashoek, D. Karger, R. Morris and I. Stoica: “Looking up data in P2P systems”, CACM, 46, 2, pp. 43-48 (2003).

[2]I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M.

F. Kaashoek and H. Balakrishnan: “Chord: A scalable peer-to-peer lookup protocol for internet applications”, IEEE/ACM Trans. Networking, 11, 1, pp.17-32 (2003).

[3]A. I. T. Rowstron and P. Druschel: “Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems”, Proc. Middleware, LNCS 2218, pp.329-350 (2001).

[4]H. V. Jagadish, B. C. Ooi and Q. H. Vu: “BATON: A balanced tree structure for peer-to-peer Networks”, Proc.

31st VLDB, pp.661-672 (2005).

[5]X. Chen, S. Ren, H. Wang and X. Zhang: “SCOPE:

Scalable consistency maintenance in structured P2P system”, Proc. IEEE INFOCOM, pp.1502-1513 (2005).

[6]K. Tutschku: “A measurement-based traffic profile of the eDonkey filesharing service”, Proc. PAM2004, LNCS 3015, pp.12-21 (2004).

[7]Q. Lv, P. Cao, E. Cohen, K. Li and S. Shenker: “Search and replication in unstructured peer-to-peer networks”, Proc. Supercomputing, pp.84-95 (2002).

[8]Zipf, G.K.: Human Behavior and the Principle of Least Effort, Addison-Wesley (1949).

佐治 和弘  Kazuhiro SAJI 

群馬大学大学院工学研究科博士前期課程在学中．2005 群馬 大学工学部情報工学科卒．日本データベース学会学生会員．

有次 正義  Masayoshi ARITSUGI 

群馬大学工学部情報工学科助教授．1991九州大学工学部情報 工学科卒．1996同大大学院博士後期課程了．博士（工学）．

データベースシステム，分散並列データ処理等に興味を持つ．