今後の課題

関根らの研究[15]も構造化オーバーレイでのコンテンツの更新を扱っている. [15]では コンテンツとして, リアルタイムで変動するセンサデータを想定している. そして, DHT にPHT（Prefix Hash Tree）[16][17]を適用することで範囲検索に対応させた構造化オー バーレイにおいて, 負荷の分散やメッセージ数／サイズの削減などを目指している. 本研 究とは想定している環境が異なるが, コンテンツの更新時にノード探索の履歴を利用して メッセージ数を削減するといった, 本研究の提案手法と併用できる手法も考えられてい る. とくに, 本研究の提案手法では5.5節で述べたようにメッセージ数／サイズがネック となっているので, 今後このような手法の導入を検討していく必要がある.

また, 松田の研究[18]では複数属性の範囲を指定して範囲検索を行える構造化オーバー レイを提案している. 本研究の提案手法もPHTを適用すれば範囲検索を行えるようにな

る. しかし, [18]のように同時に複数属性を指定することはできない. したがって, このよ

うなより柔軟な検索に対応するためには本提案手法をさらに改良していく必要がある.

参考文献

[1] “Gnutella.com”, http://www.gnutella.com/.

[2] “Winny - Wikipedia”, http://ja.wikipedia.org/wiki/Winny.

[3] J. Aspnes and G. Shah: “Skip graphs”, In Fourteenth Annual ACM-SIAM Sym-posium on Discrete Algorithms, pp. 384-393 (Jan. 2003).

[4] W. Pugh: “Skip lists: a probabilistic alternative to balanced trees”, Communi-cations of the ACM 33, pp. 668-676, (Jun. 1990).

[5] I. Stoica, R. Morris, D. R. Karger, M. F. Kaashoek, and H. Balakrishnan:

“Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications”, In Proc. of ACM SIGCOMM 2001, pp. 149-160 (Aug. 2001).

[6] P. Maymounkov and D. Mazieres: “Kademlia: A Peer-to-peer Information Sys-tem Based on the XOR Metric”, In Proc. of IPTPS 2002, pp. 53-65 (Mar. 2002).

[7] A. Rowstron and P. Druschel: “Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems”, In Proc. of IFIP/ACM Mid-dleware 2001, pp. 329-350 (Nov. 2001).

[8] B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph: “Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing”, U. C. Berkeley Technical Report, UCB/CSD-01-1141 (Apr. 2001).

[9] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker: “A Scalable Content-Addressable Network”, In Proc. of ACM SIGCOMM 2001, pp. 161-172 (Aug. 2001).

[10] “PlanetLab — An open platform for developing, deploying, and accessing planetary-scale services”, http://www.planet-lab.org/.

[11] 首藤一幸, 田中良夫, 関口智嗣: “オーバレイ構築ツールキットOverlay Weaver”, 先

[12] “Overlay Weaver: An Overlay Construction Toolkit”, http://overlayweaver.sourceforge.net/index-j.html.

[13] B. Bloom: “Space/Time Trade-Offs in Hash Coding with Allowable Errors”, Communications of ACM, vol. 13, no. 7, pp. 422-426 (Jul. 1970).

[14] 首藤一幸: “下位アルゴリズム中立なDHT実装への耐churn手法の実装”, 第19回 コンピュータシステム・シンポジウム (ComSys 2007), pp. 191-198 (Nov. 2007).

[15] 関根理敏, 瀬崎薫: “P2Pネットワークにおける高頻度なデータ更新を考慮した適応

的コンテンツ配置法”, 電子情報通信学会技術研究報告 情報ネットワーク (IN 2006), pp. 197-202 (Mar. 2007).

[16] S.Ramabhadran, S.Ratnasamy, J.M.Hellerstein, and S.Shenker: “Prefix Hash Tree: An Indexing Data Structure over Distributed Hash Tables”, IRB Technical Report (Feb. 2004).

[17] Y. Chawathe, S. Ramabhadran, S. Ratnasamy, A. LaMarca, J. Hellerstein, and S. Shenker: “A Case Study in Building Layered DHT Applications”, In Proc. of ACM SIGCOMM 2005, pp. 97-108 (Aug. 2005).

[18] 松田哲史: “複数属性を持つデータの属性値範囲指定検索用分散ネットワーク構 成方式の提案”, 情報処理学会研究報告 分散システム/インターネット運用技術 (DSM-44), pp. 19-23 (Mar. 2007).

謝辞

本修士論文は, 私が早稲田大学大学院 理工学研究科 村岡洋一研究室に在籍する期間に 行った研究をまとめたものです.

本研究を行う機会を与えて頂き, 日頃より御指導, 御助言を賜った村岡洋一教授に心より 感謝の意を表します.

また, Overlay Weaverの開発者でありますウタゴエ株式会社 首藤一幸博士に深謝致しま

す.

公私に渡り相談相手となって頂いた村岡研究室の先輩方, 同期の友人, 後輩たちに厚く御 礼申し上げます.

最後に, 研究生活を暖かく見守ってくれ, 精神的に支えてくれた家族, 友人に深く感謝致し ます.

付録

以下の発表で本研究成果を報告することが決定しています.

一杉孝之, 村岡洋一: “DHTにおけるデータの更新操作を考慮した検索方式の提案”, 第19

回 データ工学ワークショップ (DEWS 2008) (Mar. 2008).

この発表原稿を巻末に添えます.

におけるデータの更新操作を考慮した検索方式の提案

一杉 孝之^† 村岡 洋一^†

†早稲田大学大学院理工学研究科 〒169–8555東京都新宿区大久保3–4–1 E-mail: †[email protected], ††[email protected]

あらまし 近年, 構造化オーバーレイネットワークの研究が盛んに行われている. その中の一つである分散ハッシュ テーブル（DHT:Distributed Hash Table）は分散Map構造をなす. 従来のDHTではデータの取得／追加／削除の操 作に着目しているが,更新の操作への配慮に欠けている. 例えば,更新前のデータと更新後のデータを同じkeyに割り 当てた場合,取得者はデータを取得するまでそれらを判別できない. 一方,異なるkeyに割り当てた場合には,元のkey では更新後のデータを取得できなくなり, 取得者はなんらかの手段で新しいkeyについての知識を手に入れる必要が ある. 本研究では以下の3つの要件を満たす, DHTの新しい検索方式を提案する. 1)上記の更新操作の問題を解決. 2) 属性検索が可能. 3)ルーティング・アルゴリズムに非依存.

キーワード P2Pネットワーク,構造化オーバーレイネットワーク,分散ハッシュテーブル,更新操作,情報検索

Takayuki HITOSUGI^† and Yoichi MURAOKA^†

† Graduate School of Science and Engineering, Waseda University Okubo 3–4–1, Shinjuku-ku, Tokyo, 169–8555 Japan

E-mail: †[email protected], ††[email protected]

Abstract In late years the research of the structured overlay network is often performed. Distributed Hash Ta-ble(DHT) that is one of these network models makes distributed map structure. We suggest a new search method of DHT satisfying three following matters in this study. One) It solves a problem of the update operation in DHT.

Two) An attribute search is possible. Three) It non-depends on routing algorithm.

Key words P2P Network, Structured Overlay Network, DHT, Update Operaion, Informaion Retrieval

1. は じ め に

今や,情報の爆発的な増加やコンテンツの多様化などによっ て,従来の集中管理型のクライアント・サーバモデルだけでな く自律分散型のP2Pネットワークも利用されるようになって

いる. P2Pネットワークのように下位ネットワークレイヤの上

に重なって別のトポロジを形成するネットワークのことをオー バーレイネットワークという. とくにGnutella [1]やWinny [2]

などのようにオーバーレイネットワークのトポロジに数学的な 制約を持たないネットワークは非構造化オーバーレイと呼ば れる. これらは探索をfloodingで行うため,ノード数が膨大な ネットワークにおいてトラフィックが溢れる可能性があり,さら に探索が成功する保証がない.そこで近年では,構造化オーバー レイと呼ばれる,トポロジに数学的な制約を持つオーバーレイ ネットワークが注目されている. 構造化オーバーレイには分 散ハッシュテーブル（DHT:Distributed Hash Table）やSkip

Graph [3]があげられる. これらはノード数に対してスケーラブ

ルかつ確実な探索を実現している. Skip Graphは, skip list [4]

をP2Pネットワークに適応させた構造化オーバーレイであり, 標準で範囲検索が可能である. 一方, DHTは分散Map構造 を形成する. DHTでは, Chord [5], Kademlia [6], Pastry [7], Tapestry [8], CAN [9]などといった様々なルーティングアルゴ リズムが考案されており,システム構築時に目的に合わせてト ポロジとノードの探索方法の選定をできるという利点がある.

現在は,分散環境のテストベッドとして利用できる

Planet-Lab [10]や,オーバーレイネットワークの構築ツールキットであ

るOverlay Weaver [11] [12]が公開されており,分散ネットワー クシステムの構築の敷居が低くなってきている. そのため,構 造化オーバーレイの利用が今後増えていくことが期待される.

本論文におけるデータの更新とは古いデータを残しておいた まま新しいデータを追加することを指す. 従来のDHTの研究 ではデータの取得・公開・削除の動作にばかり着目し,更新の 動作への配慮が欠けている. 例えば,更新前のデータと更新後 のデータを同じkeyに割り当てた場合,取得者はデータを取得 するまでそれらを判別できない. 一方,異なるkeyに割り当て た場合には,元のkeyでは更新後のデータを取得できないため,

— 1 —

研究では,これを解決する手法を提案し,実験による評価および 考察を行うことが目的である. この提案手法は以下の3つの要 件を満たす.

• データの更新時の問題を解決する.

• 属性検索が可能である.

• ルーティング・アルゴリズムに非依存である.

本稿では,まず2.節で従来のDHTにおける更新操作の具体 的な問題点を述べ, 3.節でそれを解決する手法を提案する. そ して, 4.節で提案手法の評価を行い,その後の節で今後の課題 と本研究のまとめについて述べる.

2. 従 来 研 究

本節では,従来のDHTでデータを更新した場合の動作を説 明し,その問題点について述べる. 更新の動作のことを本論文 ではupdateと呼ぶことにする.

説明にあたって, DHTで公開済みの任意のデータをt(t∈ N) 回 更 新 す る こ と を 考 え る. こ の デ ー タ を 含 む pairを

⟨key0, data0⟩, 更 新 後 の デ ー タ をdata1, data2,· · ·, datat と おく.

2. 1 same keys

更新後の全データに対して同じkeyを割り当てるアプロー チについて述べる. まず,一意のkeyであるkeycを用意する. key0=keycかどうかはここでは問わない. 1<=i <=t(i∈N) となるすべてのiに対して⟨keyc, datai⟩をputすれば,keycの 知識を持つノードは更新後の全データを取得できる. もちろん, key0の知識を持つノードは初期のデータdata0を取得できる. しかし,更新後のデータを取得するとき, get要求先のノードは keycに対応付けられている複数のデータのうち要求元のノード が欲しているものを判断できないので,要求元のノードは一度 それらすべてをダウンロードしなくてはならない. そのため,余 分なデータも同時にダウンロードすることで無駄なトラフィッ クが生じてしまう.

2. 2 different keys

same keysではkeyとしてkey0とkeycのみを使用したが, 今度は更新後の各データに対してkeyを新たに用意してみる. これらのkeyをkey1, key2,· · ·, keytとおく. 例えば, 更新後

key value key0 data0

data1

data2

keyc data3

· · · datat

表1 same keysにおけるDHTのMapの例 Table 1 example of Map in DHT of same keys

key3 data3

· · · · · · keyt datat

表2 different keysにおけるDHTのMapの例 Table 2 example of Map in DHT of different keys

key value key0 data0

key1 data1

key2 data2

data3

· · · · · · keyt datat

表3 group keysにおけるDHTのMapの例 Table 3 example of Map in DHT of group keys

のデータdatat+1を追加する場合にはkeyt+1を新たに用意す ることになる. ここで, 1<=i <=t(i∈N)となるすべてのiに 対して⟨keyi, datai⟩^をputすれば, get要求で使うkeyを使い 分けることで,取得時に欲しいデータのみのダウンロードが可 能となる.よって,先に述べた無駄なトラフィックが生じる問題 を防げる. しかしながら,この手法では取得元のノードは取得 したいデータに対応するkeyの知識を持つ必要があり,更新後 のデータが増える度に新しく生成するkeyの知識をどのように オーバーレイネットワーク上に広めていくかが課題となる.

2. 3 group keys

same keysとdifferent keysでは,t個の更新後のデータに対 してkeyを1個またはt個用意したが,いくつか用意するとい う選択肢も存在する. 例えば,更新後のデータを任意の方法で グループ分けしてそのグループごとに新しいkeyを割り当てる という案が考えられる. しかし,この方法でも結局は上記と同 様の問題が発生する.

2. 4 問題点のまとめ

従来のDHTでデータを更新する場合には,データの取得時 に余分なデータも同時にダウンロードしてしまいトラフィック 量が増える,もしくは新しいkeyの知識をオーバーレイネット ワーク上に広めなくてはならない,という問題が生じてしまう. この問題はデータを頻繁に更新する環境で顕著に顕れることが 予想される.

3. 提 案 手 法

本節では,前節で述べた問題点を解決する手法を提案する. 3. 1 検索フレーム

本提案手法では検索システムに下記の3つのフレームを設 ける.

• 各バージョンのデータを扱うversionフレーム

• バージョンの管理を行うhistoryフレーム

— 2 —