Togetter/min.tを安心してお使い頂くためのガイドラインを公開しました。

#appengine で skiplist ってすごくね?・その2

まとめました。
4
koher(こひー) @koher

おおお、新幹線で移動してる間に、ブログに今まで見たこともないほどのブックマークが。びっくり。

2010-04-26 00:51:57
koher(こひー) @koher

Skiplistを使ったランキングですが、新幹線の中で考えていて、ふとSkiplistだからすごいのではなく、Indexableだからすごいんだと気づきました。Indexable B-treeも作れそうな気がします。 #appengine #ajn7

2010-04-26 00:56:45
Kazunori Sato @kazunori_279

@koher それは思いました。skiplistとb-treeの違いがいまいちよく分かってません><

2010-04-26 00:57:40
koher(こひー) @koher

Skiplistと違ってB-treeだとlogM(N)にできます。底を1000くらいにすれば、2、3回のデータストアアクセスで10万単位のランキングを作れるんじゃないかと。問題は、数KB程度のエンティティの読み書きがどの程度の速度で行えるかです。 #appengine #ajn7

2010-04-26 01:00:13
koher(こひー) @koher

@kazunori_279 B-treeだと1000分木でも作れるので、Datastoreへのアクセス回数が極端に少なくなります。ただし、エンティティのサイズは大きくなるので、データサイズ増大の負荷 < 多数回アクセスの負荷 であれば高速化できるかと思います。

2010-04-26 01:02:30
koher(こひー) @koher

実装してないので確証はないですが、原理的にはSkiplistと同じようにB-treeもIndexableにできるように思います。残念なのは、今週は仕事で時間をとれなさそうなことです…。時間が取れ次第ライブラリとして実装して公開したいと思います。 #appengine #ajn7

2010-04-26 01:05:50
Kazunori Sato @kazunori_279

.@koher いいですねそれ! なんか俺様DB実装みたい...既存DBのB-Treeと異なるのは、個々のentityが分散化して保存されることかな。。

2010-04-26 01:10:30
Mikio Yoshida @kibayos

これはskip listも同じです。RT @koher: Skiplistと違ってB-treeだとlogM(N)にできます。 #appengine

2010-04-26 01:13:54
Mikio Yoshida @kibayos

はい、そう思います。RT @koher: 実装してないので確証はないですが、原理的にはSkiplistと同じようにB-treeもIndexableにできるように思います。残念なのは、 #appengine #ajn7

2010-04-26 01:21:13
Mikio Yoshida @kibayos

Skip ListとB-treeのような既存の木構造の検索能力にそう違いはありません。Skip Listは、logM(N) のMは2ですが大きくすることは可能です。本質的な違いはSkip Listが乱数を使って上位のリンク構造を決めている点.で、これが分散化に寄与します。

2010-04-26 01:28:49
Mikio Yoshida @kibayos

Skip Listの利点はバランスさせるための処理が不要である点です。既存のバランス木はバランスさせるための処理が必要で、このためアルゴリズムが複雑になります。このため、バランス木の各ノードを異なるマシンに分散化させることが困難になります。

2010-04-26 01:33:52
Mikio Yoshida @kibayos

構造化オーバーレイは、木構造を使った探索アルゴリズムをP2Pネットワークに広げた方式と見ることができます。DHTの場合は、ID空間に一様にノードが分布するという前提があり、通常のN分木探索をそのまま適用することができました。

2010-04-26 01:38:15
Mikio Yoshida @kibayos

それは、DHTにはノードが一様に分布するという前提があるため、N分木を構成する際にバランスのための処理がはぶけるためです。

2010-04-26 01:40:10
koher(こひー) @koher

.@kibayos Datastore上の実装を考えると、SkiplistでMを増やしても各階層でたどるノードが増えて結局M=2のときと同程度のアクセス回数になりませんか?B-treeだと一つのエンティティにM個のポインタをまとめられます。 #appengine #ajn7

2010-04-26 01:41:16
Kazunori Sato @kazunori_279

@kibayos @koher #appengine という既存の分散データストア上にアプリレベルで実装する場合、個々のエンティティのバランスは気にしなくてよいのですよね。。そもそもアプリレベルっていうのが既存skipgraphと違う点の気がします

2010-04-26 01:41:33
Mikio Yoshida @kibayos

ところが、構造化オーバーレイにおいて、任意のkeyをノードに割り当て、範囲探索を行うとすると、ノードの持つkeyが一様に分布するという前提は成り立ちません。ここにおいて、バランスの不要なSkip Listが意味を持つのです。

2010-04-26 01:43:17
koher(こひー) @koher

.@kibayos Skiplistも工夫すれば一つのエンティティに同階層の複数ノードへのポインタをまとめられるかもしれませんが、縦のつながりもあるので実装がややこしそうに感じます。 #appengine #ajn7

2010-04-26 01:43:34
Mikio Yoshida @kibayos

こうしたSkip Listの持つ特性を生かして生まれたのがSkip Graphです。DHTにはたくさんの方式が有るのに対し、範囲検索に向く構造化オーバーレイはSkip Graphしかないのは、バランス処理がいらないバランス木がSkip Listしかないためです。

2010-04-26 01:46:18
koher(こひー) @koher

@kazunori_279 おっしゃるように #appengine 上での実装では分散は特に気にしなくてもよいと思います。あと、Skiplistでも挿入時にlog N個のノードを書き換えているので、B-treeのバランスさせる処理が特に大きな負荷にはならないと考えています。

2010-04-26 01:50:40
Mikio Yoshida @kibayos

B-treeとそう違いないのでは。RT @koher: .@kibayos Skiplistも工夫すれば一つのエンティティに同階層の複数ノードへのポインタをまとめられるかもしれませんが、縦のつながりもあるので実装がややこしそうに感じます。 #appengine #ajn7

2010-04-26 01:51:19
Mikio Yoshida @kibayos

いえいえ、B-treeを批判しているつもりはなくて、@kazunori_279 さんの言うよう、現前提ではどっちでもよいと思っています。一連の自分のTLを見てもらえば解りますが、両者の違いを知ってほしいのです。 #appengine

2010-04-26 01:54:28
koher(こひー) @koher

.@kazunori_279 @kibayos 素晴らしいのは、Datastore上での実装ではB-treeの、最大でストレージの半分を無駄にしてしまうという欠点がなくなることです。単純なB-treeなら実装の複雑さもSkiplistと大して変わりません。 #appengine

2010-04-26 01:57:30
Kazunori Sato @kazunori_279

@kibayos @koher ではB-TreeでもOKと仮定すると、既存DBのインデックスとの違いは何でしょう。レコードが分散化されている点かな?何10億レコードあってもさくっと平均とれたりするのってすごいと思うのだけど。。

2010-04-26 01:58:02
Kazunori Sato @kazunori_279

RT @kumagi: ブログ書いた。みんな大好きLockfreeListについて http://d.hatena.ne.jp/kumagi/20100425 ハザードポインタの次のlockfree資料はHashsetかSkiplistのどちらに需要があるのかしら?

2010-04-26 01:59:35
Mikio Yoshida @kibayos

Skip Listと既存のバランス木の違いで、lock freeにできるかも大事な点でした。 #appengine

2010-04-26 02:03:13
残りを読む(18)

コメント