情報科学屋さんを目指す人のメモ（FC2ブログ版）

「Overlay Weaver の使い方」では、Overlay Weaverをエミュレーションモードでシナリオを読み込ませて動作させる手順を紹介しました。今回は、その結果得られたログを読んで、どのようなルーティングが行われたかについて分析する方法を紹介します。経路長の測定も、この記事のようにして行えます。

statusコマンド

Overlay Weaverでのメッセージがどのような経路をたどったかを分析するためには、「status」コマンドが重要です。ここでは、statusコマンドの使い方を知るために、前回の記事のシナリオの一部に注目してみます。

schedule 0 control 29 put key0 value0
schedule 45 control 29 status

この2行では、「put」コマンドと「status」コマンドを、29番目のノードに対して送り込むように指示しています。

まず、putコマンドでは、<key0, value0>ペアの保存メッセージを29番目のノードに対して送りつけています。このputコマンドでどのような経路をたどったかを出力させるためのメッセージが直後のstatusコマンドですstatusコマンドは、直前に行われたputやgetメッセージのルーティング結果(status)を表示するためのコマンドです。ですから、putメッセージの直後にstatusメッセージを送りつけることで、直前のputメッセージに関する情報を取得しています。

ログを読む

これらのコマンドの結果、すなわちログは、前回の設定のままなら「overlayweaver>scenario>test-scenario-lut」に記録されているはずです。見てみます。

control 29 (Fri Oct 29 21:42:31 JST 2010): put key0 value0
control 29 (Fri Oct 29 21:42:31 JST 2010): status
ID and address: 1c15b0ff7dfc2e54a2a6499b09ffdb87dd6616cb:emu29:3997
Routing table:
predecessor:
155feacde4c07ebf0f8fa3013e0dc2c91e5ec272:emu56:3997
successor list: [
1e0ba8c920b2b86eeab01090c4bdc842fde4da4a:emu99:3997
1e3f16f11c60768fa2425a3960e437b9d5d5d9a0:emu69:3997
1f144b7db2a274fae645ceb317515f1230845dbe:emu20:3997
2010edec84a7b48e240b748cf49ed4d7c5ed15fc:emu80:3997
21bd507a9f65ff284d36df3154450f4c4788228e:emu94:3997
23171781a21733b8d89190d0f5842be9a1943365:emu11:3997
251bc9d0326e26bb1b85f8eb2e9c1578caab753b:emu5:3997
2576fc9318d8813d80c4c353d947ea6e73a25e8e:emu40:3997
]
finger table: [
1: 251bc9d0326e26bb1b85f8eb2e9c1578caab753b:emu5:3997
157: 435cf4d3b90de23a8b5f668f26abcd40ef8db411:emu4:3997
159: fb7269a17aa897f4169025ca91536b44675def9f:emu25:3997
]
Last keys & routes:
number of messages: 14 -> 14
key[0]: adb1ef332d1f6e99e809fb9b00a08efcad930e82
route[0] (length: 6): [
1c15b0ff7dfc2e54a2a6499b09ffdb87dd6616cb:emu29:3997 (0)
435cf4d3b90de23a8b5f668f26abcd40ef8db411:emu4:3997 (1)
5ee1296b4f7f76c30299374573e9e2340ea31d80:emu35:3997 (1)
7d45464d80fd088267924f65b96d3ffa971ae425:emu39:3997 (1)
9f0c342f5cd2dc750d5251753e1f2ebe542959eb:emu36:3997 (1)
ac22b1c0ded5533fefc80ed616d770f6d0d03bcb:emu19:3997 (2)
af2d23fc771ce822da7e19534163e87481aa9312:emu59:3997 (2)
]
root candidates[0]: [
af2d23fc771ce822da7e19534163e87481aa9312:emu59:3997
b032398acb30adf04e3bc7c95ac8a1e2438655e4:emu8:3997
b14ff37e59ed0940f745d8c570b2b51219fa2a9d:emu13:3997
b1b965e7af8dfd1dee34482a2dd875fe11041957:emu48:3997
]

以上が、先ほどのputとstatusの実行結果(ログ)です。このうち、最初の一行だけがputコマンドの実行結果です。見ての通り、putコマンドだけでは何が起こったか分かりません。なので、statusコマンドの実行が重要なのです。ここから、statusコマンドの実行結果を解説します。

コマンドを実行したノードについて

ID and address: 1c15b0ff7dfc2e54a2a6499b09ffdb87dd6616cb:emu29:3997

これは、putコマンドを実行(受け取った)ノードのIDAddressPairを表しています。IDAddressPairは、IDとIPアドレスの組を保持しているクラスで、この出力結果では、「1c15b...616cb」までがノードID、「emu29」がIPアドレス(エミュレータ上のノードのホスト名)、「3997」がポート番号を表しています。

この後も、ノードの識別情報としてこのIDAddressPairがたくさん出てくることになります詳しくは「ow.id.IDAddressPair」

経路表(Successor List, Finger Table, Predecessor)

続いて、「Routing Table:」以降が経路表の中身を表しています。今回利用したアルゴリズムはChordですから、Routing Tableはつまり「Successor List」「Finger Table」「Predecessor」のことを指し、この内容が順番に書かれています。IDAddressPairの見方が分かっていれば、見ての通りだと思います。いちよ説明しておくと、

predecessor:
155feacde4c07ebf0f8fa3013e0dc2c91e5ec272:emu56:3997

これがPredecessorノードで、

successor list: [
1e0ba8c920b2b86eeab01090c4bdc842fde4da4a:emu99:3997
1e3f16f11c60768fa2425a3960e437b9d5d5d9a0:emu69:3997
1f144b7db2a274fae645ceb317515f1230845dbe:emu20:3997
2010edec84a7b48e240b748cf49ed4d7c5ed15fc:emu80:3997
21bd507a9f65ff284d36df3154450f4c4788228e:emu94:3997
23171781a21733b8d89190d0f5842be9a1943365:emu11:3997
251bc9d0326e26bb1b85f8eb2e9c1578caab753b:emu5:3997
2576fc9318d8813d80c4c353d947ea6e73a25e8e:emu40:3997
]

これがSuccessor Listを手前(Successor Node)から順に出力している部分です。

finger table: [
1: 251bc9d0326e26bb1b85f8eb2e9c1578caab753b:emu5:3997
157: 435cf4d3b90de23a8b5f668f26abcd40ef8db411:emu4:3997
159: fb7269a17aa897f4169025ca91536b44675def9f:emu25:3997
]

そしてこれがFinger Tableです。標準でIDは160bitで、1bitごとにFinger Tableのエントリが設けられ、そのうちの1番目、157番目、159番目が表示されているノードで埋められていることが分かります。

ルーティングの経路

肝心のputメッセージのルーティングがどのような経路をたどって行われたかは、「Last keys & routes:」以降に記述されています。「number of message」と配列の添え字「[0]」の説明は割愛します。

key[0]: adb1ef332d1f6e99e809fb9b00a08efcad930e82

このkey[0]以降の部分は、探索対象のIDを表しています。そして、その次の部分、

route[0] (length: 6): [
1c15b0ff7dfc2e54a2a6499b09ffdb87dd6616cb:emu29:3997 (0)
435cf4d3b90de23a8b5f668f26abcd40ef8db411:emu4:3997 (1)
5ee1296b4f7f76c30299374573e9e2340ea31d80:emu35:3997 (1)
7d45464d80fd088267924f65b96d3ffa971ae425:emu39:3997 (1)
9f0c342f5cd2dc750d5251753e1f2ebe542959eb:emu36:3997 (1)
ac22b1c0ded5533fefc80ed616d770f6d0d03bcb:emu19:3997 (2)
af2d23fc771ce822da7e19534163e87481aa9312:emu59:3997 (2)
]

が、経路を表しています。「length:」の後の数字が「経路長」を表しており、ここでは経路長6となっています。「route[0]」の次の行から7つ並んでいるのが、putメッセージを受け取ったノードから、最終的にデータの保存先となったノードまでの全7ノードです。Chordリング状をだんだん近づいていることが、IDを見ると分かります。

このあたりを見ると、うまくアルゴリズムが動作しているか大まかな推測が出来ます。

最後に、次の部分です。

root candidates[0]: [
af2d23fc771ce822da7e19534163e87481aa9312:emu59:3997
b032398acb30adf04e3bc7c95ac8a1e2438655e4:emu8:3997
b14ff37e59ed0940f745d8c570b2b51219fa2a9d:emu13:3997
b1b965e7af8dfd1dee34482a2dd875fe11041957:emu48:3997
]

これが何を表しているかは、説明が難しいです。「Overlay Weaver で新しいルーティングアルゴリズムを作る方法(2/3)」の「rootCandidatesメソッド」で説明していますが、ざっくり言うと、担当ノードの候補たちを優先順に並べたものです。一番優先度の高い、一番上のノードが実際の担当ノードになっていることが、先ほどの経路の最後のノードと一致していることから分かります。そして、それ以降のb03, b14, b1bで始まるノードは、Chordリング状を時計回りに担当ノードからたどった位置にあります。つまり、実際の担当ノードが離脱してしまった場合の「次の担当ノード」になるのがb03で、それも離脱してしまった場合はb14で…というわけです。

まとめ

以上で、「Overlay Weaver の使い方」の記事も含めて、Overlay Weaverを動かして、ログを取る方法を最低限解説しました。大体の流れが把握できてと思います。

まだこの記事だけでは分からないことがたくさんあると思いますが、この記事を軸にそれぞれ調べてみると、何も資料のない状態から作業するのに比べたらずいぶんと楽が出来ると思います。そして、その楽できた時間で、効率よくいろいろとやってみてください。

Effective Java 第2版 (The Java Series)
Googleを支える技術 巨大システムの内側の世界
Winnyの技術