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

この記事は、「Overlay Weaver で新しいルーティングアルゴリズムを作る方法(1/3)」のつづきです。

AbstractRoutingAlgorithmの全メソッド解説

前の記事で、AbstractRoutingAlgorithmを継承したMyChordクラスに言及しました。ここでは、MyChordクラスが実装すべきAbstractRoutingAlgorithmクラスのメソッドをすべて解説しますOverlay Weaverに標準で備わっているアルゴリズムを参考にすると分かりやすいかも

その前に前提知識

メソッド解説の前に、ちょっとしたOverlayWeaver用語解説を。

IDAddressPair

IDAddressPairクラスは、一言で言うと、ノードの情報を表します。具体的には、IPアドレスとノードIDのペアを保持しているクラスです。つまり、DHTで言うところの経路表エントリ1つ分に相当します。

Root

Rootは、Routeと間違えないように注意してください。Rootは、簡単に言うと、担当ノードのことです。つまり、この後出てくる「RootCandidates」は、「ルーティング先候補」ではなく「担当ノード候補」ですちなみに、Overlay Weaver独自用語では全くありません

では、ここからメソッド解説です。

distance(ID to, ID from) : BigInteger

このメソッドは、あるID(from)からあるID(to)までのID上の距離を返すメソッドです。Chordなら時計回り距離、KademliaならXORを計算すればOK。

closestTo(ID target, int maxNumber, RoutingContext context) : IDAddressPair[]

これは、経路表の中から目標ID(target)に近いノード(IDAddressPair[])を返すメソッドです。返値の配列には、目的IDに近い順に[0],[1],...とノード情報が入れられます。ここで、この配列の長さはmaxNumberを越えないようにします。

このメソッドが返すノードのリストは、意味を考えると「次のHop先」を示しています。つまり、「目的IDに近づく際に、最も近づけるノード」が[0]に入っており、Hop先の第一候補になります。[1],[2]以降は、二番手、三番手...ということになります。

要するに、このメソッドの戻り値に従ってルーティングが行われるということになります。超重要メソッドです。

あえてChordで言えば、「目的IDから反時計回りにたどって出くわした経路表エントリノード」が[0]から順に入っていることになります。

ちなみに、contextは無視してください。これはKoorde専用であり、普段はnullですので。

また、重要なこととして、closestToの戻り値の先頭(もっとも目標IDに近いと考えられるノード)が自分のIDと一致した場合、自分が一番目標IDに近いノードであると認識し、ルーティングが終了します。

adjustRoot(ID target) : IDAddressPair[]

ChordでclosestToメソッドに従ってルーティングすることを考えてください。すると、目標ID(target)の直前(predecessor)まで近づいてルーティングが終了してしまいます。本当の担当ノードは目標IDの直後(successor)なので、このままではルーティングが正しく終了しないことになります。つまり、最後に微調整が必要です。この「微調整」が「adjustRoot」です。

このメソッドは、IDによるルーティングを行って辿り着いたノード上で呼び出されます。そして、最終的な担当ノード(Root)のIDAddressPairを返します。先のChordの例では、辿り着いたノード(targetのpredecessor)上で呼び出され、本当の担当ノード(successor)のIDAddressPairを返すように実装すればよいわけです。

このように、目標IDに近づくルーティングの終了後の微調整を行うのがadjustRootなのですが、必ずしも必要とは限りません。たとえば、Kademaliaでは一切不要な機能です。なので、実はadjustRootはデフォルトではOFFとなっており、RoutingAlgorithmConfiguration(MyChordConfiguration)のadjustRoot()メソッドを呼んだ結果がtrueの場合のみ呼び出されます。なので、ChordConfigurationでは、adjustRoot()メソッドをオーバーライドして、trueを返すようにしています。

では、adjustRootが不要なとき、MyChrodConfiguration#adjustRoot()がfalseを返すとき、MyChord#adjustRootは何を返せばいいのかというと、どうせ呼び出されないので、nullを返しておけばOKです。

rootCandidates(ID target, int maxNumber) : IDAddressPair[]

このメソッドは担当ノードで呼び出され、担当ノードの候補を返します。

「???」な感じですが、自分が担当ノードだと思われてルーティングされたけど、実は担当は自分じゃないんだよ。なんて時に効果を発揮します。逆に言えば、自分が担当ノードなんだから、自分のIDAddressPairを返せば十分です。ただ、正確には担当ノードの第2候補、第3候補、...をmaxNumberを超えない数だけ戻り値配列に格納すべきです。とはいえ、必須ではありません。また、このも戻り値配列のノードたちは、レプリカを保存する対象にもなりますちょっとこのメソッドメモ怪しい

またもやChordに即して考えてみると、ChordにおけるrootCandidatesメソッドは、「目標ID(target)から時計回りにたどって出くわした経路表エントリノード」を返せばいいことになります。

ここまでが、ルーティングに関わる超コアなメソッドたちでした。

join(IDAddressPair[] neighbors) : void

このメソッドは、「ノードがオーバレイネットワークへ参加(Join)する時に呼び出されます」。より正確に言うと、自分のIDを既存のオーバレイネットワーク上で探索(lookup)し、自分のIDの担当ノードを発見した後、その担当ノード上でrootCandidatesメソッドを呼び出した結果がneighborsに格納されてjoinメソッドがjoinしたノード上で呼び出されます。

したがって、「neighborsを初期経路表エントリにしてね」というだけのメソッドです。joinに必要な通信は他のクラスがやってくれます。したがって、このメソッドの実装では、neighborsを経路表エントリに格納するだけでOKです。

join(IDAddresspair joiningNode, IDAddressPair lastHop, boolean isRootNode) : void

このメソッドは、先ほど紹介したjoinメソッドとは対照的に、「ノードが参加(join)する前に行う探索(lookup)の経路上のノードで呼び出されます」つまり、参加しようとしたノード上で呼ばれるわけではありません。

joiningNode引数は、まさしくこれからJoinしようとしているノードのIDAddressPairが入っています。そして、lastHopは、今行われている探索において、どこからこのノードへHopしてきたかを示しています。最後のisRootNodeは、参加しようとしているノードの担当ノード上でこのメソッドが呼び出される場合のみtrueになり、探索中の経路の場合はfalseとして呼び出されます。

このメソッドはいろいろなことができるメソッドですが、必ずしも必要不可欠なメソッドではありません。戻り値もないことですし。

この二つのjoinメソッドがJoin操作で重要なメソッドです。

touch(IDAddressPair from) : void

このメソッドは「ノード(from)と通信したときに呼び出されます」。したがって、通信に成功したノード(from)を経路表に積極的に追加することが可能です。ただ、なにもしなくっても問題ありません。

forget(IDAddressPair node) : void

このメソッドは、touchとは真逆で「ノード(node)との通信が失敗したときに呼び出されます」。名前の通り、通信に失敗したノードなんて忘れろ(forget)というメソッドです。なので、forgetが呼び出された場合は経路表からnodeを削除します。touchとは異なり、何もしないで放置してしまうと、通信に失敗し続けて終わらないので、確実に経路表から削除してください。

reset() : void

このメソッドは、アルゴリズムの状態をリセットするメソッドです。そんなに呼び出されるメソッドではありません。具体的には、経路表の内容をクリアすればOKです。

suspend(), resume(), stop()

これらのメソッドは、それぞれノードの動作を「一時停止」「再開」「停止」させるときに呼び出されます。具体的には、ChordでいうところのStabilizerのような勝手に実行されるものを「一時停止」したり「再開」したり「停止」しろというメソッドです。

とりあえずアルゴリズムを作る分には、あとまわしにしていいメソッドたちです。具体的な利用方法はChordを参考に。

toReplace(IDAddressPair existingEntry, IDAddressPair newEntry) : boolean

このメソッドは、簡単に言えば「無意味なメソッド」です。このメソッドは外部から一切呼び出されていません。つまり、自分でアルゴリズム中から呼び出さない限り、無視できるメソッドです。とりあえずreturn falseとでも書いておけば十分です。

getRoutingTableString(int verboseLevel) : String

とりあえずverboseLevelは無視するとして、経路表の中身を文字列にまとめて返すメソッドです。statusコマンドを通じて経路表の情報を取得しようとした場合に呼び出されます。Chordでは、successor listの中身はこれこれ、finger tableの中身はこれこれという情報が文字列にまとめられています。めんどくさければreturn "";にでもして後回しに出来ますが、アルゴリズムを分析するに当たっては、確実に必要となるメソッドだと思われます。

getRoutingTableHTMLString() : String

こちらは、getRoutingTableStringのHTML版です。ただの文字列ではなく、HTMLで返してあげてください。これは、getRoutingTableStringとは異なり、あんまり使わないので本当にreturn "";で十分です。

最低限実装すべきメソッド

ここまでで、AbstractRoutingAlgorithmの実装すべき全メソッドの解説が終了しました。ただ、適当にreturnしておけばいいだけのメソッドも多いです。

本当に考えて実装しないといけない最低限のメソッドは、次の通りです。

• distance
• closestTo
• rootCandidates
• adjustRoot
• join 2つ
• touch
• forget

たったこれだけでDHTのルーティングアルゴリズムが実装できるわけです。

つづく

次の記事「Overlay Weaver で新しいルーティングアルゴリズムを作る方法(3/3))」につづく

雲の世界の向こうをつかむ クラウドの技術
クラウドを実現する技術
クラウド大全 第2版 サービス詳細から基盤技術まで