Chord の最短経路長は 2
Kazuyuki Shudo
consistent hashing を採用した key-value ストア (転送なし) も、
構造化オーバレイの枠組みの中に据えて考えるといいんじゃないの？
というような話をしてきました：
scale outの技術
http://www.shudo.net/article/UNIX-magazine-200904-scaleout/
セクション「クラウドと構造化オーバレイネットワーク」
ようやく、そういう構造化オーバレイを具現化できつつあります。
しかし、Chord をベースにした場合、どうやっても経路長は 2までしか縮まりません。
つまり、1回のホップは避けられません。
これは Chord 自体に由来します。
これをなんとか 1にできないか？ホップなしにできないか？と考えてます。
Chord マニアの皆様 :)
以下について何かお気づきの点がございましたら、
コメント頂けますと幸いです。
Chord のアルゴリズムがもともと、こういう手順となっているので：
(1) find_predecessor(id) <- Chord の SIGCOMM 2001 論文の Figure 4
目的 ID の predecessor (or 目的 ID そのものを ID とするノード) を探して
(2) find_successor(id)
その successor に到達する
(偶然、問い合わせ元ノード自身が目的 ID の predecessor でない限りは)
最短の経路長は 2となります。
とすると次は、Chord のアルゴリズムを若干イジって、
最短経路長を 1にしてしまえばいいのではないか？
と考えるわけです。
いっそ、
目的 ID の successor ではなくて、
目的 ID の predecessor (or 目的 ID そのものを ID とするノード) を
担当ノードとしてしまえば、最短経路長を 1とできるのに、と思います。
Chord でのルーティングの最後の一歩、find_successor(id) って、
何なんでしょうね。
find_predecessor(id) だけでは問題があるんでしょうか。
今思いついた 1つの仮説は、こういうものです。
Chord において、確実に保守されているのは successor だけで、
finger table はショートカットリンクに過ぎません。
(successor はノード加入時にきちんと設定されますが、
finger table など他は stabilization で徐々に設定されます。)
find_predecessor(id) までは finger table を参照してノードを辿っています。
これだと心許ないので、最後に、確実に保守されている successor を辿る、と。
余談：
ここまで考えて、Chord のバグ (?) らしきものに、またひとつ気づきました：
finger table がまだ完璧ではなかった場合、
find_predecessor(id) で、
目的 ID の本当の predecessor に到達できるとは限りません。
なのに、find_successor(id) では、
そこで得たノードの successor に到達するようになっています。
Overlay Weaver の Chord 実装は、大丈夫です。
find_predecessor(id) 相当の処理でも、
finger table だけでなくて successor list も使って、
目的 ID の本当の predecessor に到達するようにしてます。
あと、find_successor(id) 相当の処理でも、
到達先が担当ノードではないと思われるようなら、補正を行います。
find_predecessor(id) では finger table だけを辿るから確実性の点で不安、
ということだとすると、
find_predecessor(id) の過程で successor も使うようにすればいい？
でもそれをやろうとしても、結局
finger table でショートカット + successor で確実性を担保、
の 2ステップ必要となって、最短の経路長は 2までしか減らない？？？
首藤一幸
Yusuke Doi
2010年3月20日17:06 Kazuyuki Shudo <20...@shudo.net>:
> 皆様、首藤です。
> 今思いついた 1つの仮説は、こういうものです。
> Chord において、確実に保守されているのは successor だけで、
> finger table はショートカットリンクに過ぎません。
> (successor はノード加入時にきちんと設定されますが、
> finger table など他は stabilization で徐々に設定されます。)
>
> find_predecessor(id) までは finger table を参照してノードを辿っています。
> これだと心許ないので、最後に、確実に保守されている successor を辿る、と。
僕が持っていた仮説も同じようなものでした。つまり、あらゆるshortcutは「絶対に目的地を追い越さないように」実行する、というモデルです。従って、Chordは元来性能を2の次にした設計で、successor-predecessor間だけ正確に維持できていれば確実にルーティングできる、という哲学かなと。そう考えると、hop数を1にする、というのはChordではない何か、ということなのではないかと思います。で、find_successor(id)で転送した先が本来の担当ノードでなければ、そこからまた再帰がはじまる(からいいじゃん)、という原理だと理解しています。
> Overlay Weaver の Chord 実装は、大丈夫です。
> find_predecessor(id) 相当の処理でも、
> finger table だけでなくて successor list も使って、
> 目的 ID の本当の predecessor に到達するようにしてます。
> あと、find_successor(id) 相当の処理でも、
> 到達先が担当ノードではないと思われるようなら、補正を行います。
これも、正しいルーティングのために維持すべき状態を増やすことによって制約を緩めている例だと思います。現実解としては僕も似たような実装をしました。
> find_predecessor(id) では finger table だけを辿るから確実性の点で不安、
> ということだとすると、
> find_predecessor(id) の過程で successor も使うようにすればいい？
> でもそれをやろうとしても、結局
> finger table でショートカット + successor で確実性を担保、
> の 2ステップ必要となって、最短の経路長は 2までしか減らない？？？
というわけで、これは1方向性routingの宿命かと思います。
ルーティングに失敗する中間状態を許容することにより、この制約は解けるかなと。
(一種のCAP定理でしょうか)
どいゆうすけ
Akito Fujita
最初から successor を探しに行けば良いのではないでしょうか？
それで困らないように finger table の生成方法を見直すのと、
双方向の探索（ＩＤが増加する方向だけでなく減少する方向も）が
必要だと思いますが…
PS Chord がまず predecessor を見つけてから successor を探すのは、
ＩＤが増加する方向にしか探索しないのでＩＤ空間中で
ターゲットとなるノードが存在するできるだけ小さな範囲を
決めるためだと僕は理解しましたが…
- Akito
> --
> このメールは Google グループのグループ「Overlay Network (Japanese)」の登録者に送られています。
> このグループに投稿するには、overlay-n...@googlegroups.com にメールを送信してください。
> このグループから退会するには、overlay-network...@googlegroups.com にメールを送信してください。
> 詳細については、http://groups.google.com/group/overlay-network-ja?hl=ja からこのグループにアクセスしてください。
>
>
KOBARA Makoto
小原です。
大変ご無沙汰しております。
>今思いついた 1つの仮説は、こういうものです。
(どいさんも同じことを書いていらっしゃいますが)
私がChordの論文を読んでいろいろやっていた当時(5年くらい前でしょうか)、
感じた印象を思い出しながら書くと、こういう感じです。
1) ノードは、第一に、輪の前後とのつながりを維持。
このつながりをたどってゆけば、他のノードへも到達できる。
(ここが一番「堅い」ところ)
2) 毎度つながりを前後にたどってゆくのはダサいので(という表現は正確では
ないですが)、近道を設ける。
近道(FingerTable)は、(目的地を追い越さないように)歩幅を倍々で大きく
したものを用意して、テキトウに維持する。
1)と2)を混ぜたものとか、逆向きのFingerTableも設けるとか、
色々な発想はあるかもしれませんが(色々考えた覚えがありますが)、
一般論としては、
「どこか堅いところはシンプルに持っておく」という考え方は
基本的に重要だという結論です。
(異常系の処理が、どんどん複雑になってしまうため。
これはChordやOverlayNetworkの話題に限った話ではありませんが)
あとは、
ルーティングに失敗するような状況がどれだけ発生するのか、
ルーティング失敗のペナルティが(上位層にとって)どう影響するのか、
といった(非機能)要件を設定できれば、
色々な工夫の妥当性は、色々と議論できるかと。
たとえば、1Hop化のために何かを削っても問題ない(こういう前提なら1Hop化
のための工夫は妥当)、というような。
----------------------------------------
KOBARA Makoto
kobara...@gmail.com