10周年のSPコンテンツ!
4
koher @koher
おおお、新幹線で移動してる間に、ブログに今まで見たこともないほどのブックマークが。びっくり。
koher @koher
Skiplistを使ったランキングですが、新幹線の中で考えていて、ふとSkiplistだからすごいのではなく、Indexableだからすごいんだと気づきました。Indexable B-treeも作れそうな気がします。 #appengine #ajn7
Kazunori Sato @kazunori_279
@koher それは思いました。skiplistとb-treeの違いがいまいちよく分かってません><
koher @koher
Skiplistと違ってB-treeだとlogM(N)にできます。底を1000くらいにすれば、2、3回のデータストアアクセスで10万単位のランキングを作れるんじゃないかと。問題は、数KB程度のエンティティの読み書きがどの程度の速度で行えるかです。 #appengine #ajn7
koher @koher
@kazunori_279 B-treeだと1000分木でも作れるので、Datastoreへのアクセス回数が極端に少なくなります。ただし、エンティティのサイズは大きくなるので、データサイズ増大の負荷 < 多数回アクセスの負荷 であれば高速化できるかと思います。
koher @koher
実装してないので確証はないですが、原理的にはSkiplistと同じようにB-treeもIndexableにできるように思います。残念なのは、今週は仕事で時間をとれなさそうなことです…。時間が取れ次第ライブラリとして実装して公開したいと思います。 #appengine #ajn7
Kazunori Sato @kazunori_279
.@koher いいですねそれ! なんか俺様DB実装みたい...既存DBのB-Treeと異なるのは、個々のentityが分散化して保存されることかな。。
Mikio Yoshida @kibayos
これはskip listも同じです。RT @koher: Skiplistと違ってB-treeだとlogM(N)にできます。 #appengine
Mikio Yoshida @kibayos
はい、そう思います。RT @koher: 実装してないので確証はないですが、原理的にはSkiplistと同じようにB-treeもIndexableにできるように思います。残念なのは、 #appengine #ajn7
Mikio Yoshida @kibayos
Skip ListとB-treeのような既存の木構造の検索能力にそう違いはありません。Skip Listは、logM(N) のMは2ですが大きくすることは可能です。本質的な違いはSkip Listが乱数を使って上位のリンク構造を決めている点.で、これが分散化に寄与します。
Mikio Yoshida @kibayos
Skip Listの利点はバランスさせるための処理が不要である点です。既存のバランス木はバランスさせるための処理が必要で、このためアルゴリズムが複雑になります。このため、バランス木の各ノードを異なるマシンに分散化させることが困難になります。
Mikio Yoshida @kibayos
構造化オーバーレイは、木構造を使った探索アルゴリズムをP2Pネットワークに広げた方式と見ることができます。DHTの場合は、ID空間に一様にノードが分布するという前提があり、通常のN分木探索をそのまま適用することができました。
Mikio Yoshida @kibayos
それは、DHTにはノードが一様に分布するという前提があるため、N分木を構成する際にバランスのための処理がはぶけるためです。
koher @koher
.@kibayos Datastore上の実装を考えると、SkiplistでMを増やしても各階層でたどるノードが増えて結局M=2のときと同程度のアクセス回数になりませんか?B-treeだと一つのエンティティにM個のポインタをまとめられます。 #appengine #ajn7
Kazunori Sato @kazunori_279
@kibayos @koher #appengine という既存の分散データストア上にアプリレベルで実装する場合、個々のエンティティのバランスは気にしなくてよいのですよね。。そもそもアプリレベルっていうのが既存skipgraphと違う点の気がします
Mikio Yoshida @kibayos
ところが、構造化オーバーレイにおいて、任意のkeyをノードに割り当て、範囲探索を行うとすると、ノードの持つkeyが一様に分布するという前提は成り立ちません。ここにおいて、バランスの不要なSkip Listが意味を持つのです。
koher @koher
.@kibayos Skiplistも工夫すれば一つのエンティティに同階層の複数ノードへのポインタをまとめられるかもしれませんが、縦のつながりもあるので実装がややこしそうに感じます。 #appengine #ajn7
Mikio Yoshida @kibayos
こうしたSkip Listの持つ特性を生かして生まれたのがSkip Graphです。DHTにはたくさんの方式が有るのに対し、範囲検索に向く構造化オーバーレイはSkip Graphしかないのは、バランス処理がいらないバランス木がSkip Listしかないためです。
koher @koher
@kazunori_279 おっしゃるように #appengine 上での実装では分散は特に気にしなくてもよいと思います。あと、Skiplistでも挿入時にlog N個のノードを書き換えているので、B-treeのバランスさせる処理が特に大きな負荷にはならないと考えています。
Mikio Yoshida @kibayos
B-treeとそう違いないのでは。RT @koher: .@kibayos Skiplistも工夫すれば一つのエンティティに同階層の複数ノードへのポインタをまとめられるかもしれませんが、縦のつながりもあるので実装がややこしそうに感じます。 #appengine #ajn7
Mikio Yoshida @kibayos
いえいえ、B-treeを批判しているつもりはなくて、@kazunori_279 さんの言うよう、現前提ではどっちでもよいと思っています。一連の自分のTLを見てもらえば解りますが、両者の違いを知ってほしいのです。 #appengine
koher @koher
.@kazunori_279 @kibayos 素晴らしいのは、Datastore上での実装ではB-treeの、最大でストレージの半分を無駄にしてしまうという欠点がなくなることです。単純なB-treeなら実装の複雑さもSkiplistと大して変わりません。 #appengine
Kazunori Sato @kazunori_279
@kibayos @koher ではB-TreeでもOKと仮定すると、既存DBのインデックスとの違いは何でしょう。レコードが分散化されている点かな?何10億レコードあってもさくっと平均とれたりするのってすごいと思うのだけど。。
Kazunori Sato @kazunori_279
RT @kumagi: ブログ書いた。みんな大好きLockfreeListについて http://d.hatena.ne.jp/kumagi/20100425 ハザードポインタの次のlockfree資料はHashsetかSkiplistのどちらに需要があるのかしら?
Mikio Yoshida @kibayos
Skip Listと既存のバランス木の違いで、lock freeにできるかも大事な点でした。 #appengine
残りを読む(18)

コメント

ログインして広告を非表示にする
ログインして広告を非表示にする