skip listと修復処理、両方向Chordまで

Mikio Yoshida @kibayos

skip graphの前にskip listがまだ解ってない自分を発見した。

くまぎ @kumagi

@kibayos 詳しくお願いします。

Mikio Yoshida @kibayos

.@kumagi お、そうですか。レベルを1上げる際に使う確率pが1/2でない場合の検索コスト、使用する乱数によって受ける検索コストの分布傾向、検索の原理についてのN分木とのフォーマルな比較、そして、分散化に向くと言われる性質など。

Mikio Yoshida @kibayos

skip listをskip graphと同じようにネットワーク分散させた場合、つまり、ノード障害、通信障害が起こる前提でのあるべきroutingについても解ってなかったのです。ましてや範囲検索はもっと。

くまぎ @kumagi

@kibayos 1/2より上げると検索速度向上で、トレードオフでメモリ消費量肥大化までは分かりますが、どれぐらいの向上なのかは知らないです。乱数が偏ると何か変わるのかも知らないです。N分木と比べて探索範囲が1方向にしか狭くならないので更新と検索を並列化できる。

くまぎ @kumagi

@kibayos 分散化は、SkipListなら更新時に書き換える箇所が一箇所で良いからパフォーマンスよさそうですね。分散SkipListはちょっと効率不明ですが。

くまぎ @kumagi

分散SkipListって実装例あるのかしら。やっぱりChordのようになるんじゃなかろうか？

kumagi @kumagi_bot

分散SkipListは、直前のノードがすぐ次のノードへの生存確認を定期的に行って、死んでるようなら次へ次へ、とやる感じ？

Mikio Yoshida @kibayos

@kumagi これ一個一個が深い話になりますよ。確率pと検索コストの関係は原論文に出ていますが、pを小さくすると検索コストも小さくなるという単純な話ではないんです。乱数は一様に分布したとしても、検索コストにはばらつきが出ますし、並列化についてもいろいろ解ってないことが多いと。

Mikio Yoshida @kibayos

@kumagi ノード障害、通信障害が起こらない前提、例えばマルチコアな環境なら、お得意のlock-freeで構造の整合性は担保できますね。ネットワーク分散させた場合はDDLLの手法を使うことで整合性はなんとかなります。そのためのDDLL。

Mikio Yoshida @kibayos

@kumagi_bot その生存確認中にそのノードが死んだらどうします？

kumagi @kumagi_bot

@kibayos 次のノードを多重に持っておいて、そちらに繋ぎ変えですね。ChordのSuccessorListそのもの。

Mikio Yoshida @kibayos

@kumagi_bot そのつなぎ替え処理をしようとしているノードが死んだら、ということなんですが。でも、これはiterative routingでなんとかなります。

くまぎ @kumagi

@kibayos DDLLというか双方向である必要が無いのでかなり簡単になりそうではありますね。

kumagi @kumagi_bot

@kibayos 自分が死んだ場合は、predecessorが同様の処理でsuccessorと繋がると思います。

Mikio Yoshida @kibayos

@kumagi いいつっこみを入れてくれるのでうれしいです。ここではskip listといえど双方向を想定しています。双方向にすることによって、安定化がやりやすくなるのです。DDLLだと。不思議でしょ。

くまぎ @kumagi

@kibayos 安定化というのは、リバランスという事でしょうか。双方向にしたほうが(円環してくる必要がないので)任意のノードを起点とした範囲検索を速そうとは思うんですが、安定化しやすいというのは不思議です。

Mikio Yoshida @kibayos

@kumagi_bot この話はChordに限らないのですが、routingについての認識がずれてるような。

kumagi @kumagi_bot

@kibayos あー、クエリが途中で紛失するんですか。確かにそれはIterativeにしていく他ないですね。(たしか)Kademliaのように。

Mikio Yoshida @kibayos

@kumagi 構造化オーバーレイにおいて、安定化(stabilization)は障害箇所の復旧を意味します。話を単純にすると、一方向のリンクからなるオーバーレイと双方向のリンクからなるオーバーレイではどちらが安定化をやりやすいか、という根源的な話になるんです。

Mikio Yoshida @kibayos

@kumagi 障害箇所だけではなく不整合をはらんだ箇所を整合化させる処理も安定化でした。Chordではそういう状態が明示的に起こります。

くまぎ @kumagi

@kibayos 双方向のリストのほうが安定化をしやすい…んですか？一時期Azureで使われてるとか言っていた双方向Chordもそういった理由によるんですか…？

Mikio Yoshida @kibayos

@kumagi またまたいいつっこみ。この場合、並行join/leaveと安定化は別に考えましょう。双方向にした場合の深刻な問題は並行join/leaveなのです。lock-freeでもトピックになっているでしょ。マルチコアでも難しいことなので、この大変さは解ってもらえるはず。

Mikio Yoshida @kibayos

@kumagi Azureについて懐疑的だったのは、両方向リングにしたときに並行join/leaveで起こりうる不整合を回避する方法があるのか、だったのです。kumagiがきらいな2フェーズコミットくらいしかないと思いました。DDLLでこの問題を解決したんです。

kota abe @kotabe

Azureの双方向リングはfinger tableの話で，successor と predecessor による双方向リングとは別の話な気が． @kibayos @kumagi