LevelDB雑感

LevelDBが公開されて少し経ちました。
全体ではLog Structured Merge Treeという物を実装しているようですが詳しいところは知りません。

実装を少し読んだのですが内部で使われているSkipListにいくつも思い切った設計がありました。

(参考)togetter「LevelDBを読む人たち」
http://togetter.com/li/136983

SkipListそのものはMulti Reader / Single Writerな実装なのですが
おもしろい事にReaderとWriterが同時に走っても大丈夫なように作られています。

Reader-Reader : 共存可能
Reader-Writer : 共存可能
Writer-Writer : 共存不可

Readerが常に走り続けている状況を想定した上で、Writerの足を止めたくないんでしょうね。
為される事の論理的構造が決まっているからこそ、書き込み途中のデータを読み出せる仕組みにしたんだと思います。

また、削除が行えない仕組みになっていました。SkipListクラスのデストラクタでまとめてメモリ開放を行えますがそれまでの間はメモリ領域も含めてSkipListからは一切開放できないように機能を限定することで、並行データ構造を設計する上で鬼門となる削除周りの複雑さを一気にスキップした感じです。

いくつか不可解な点もあります。
・C++0xなのにstd::mt19937ではなく、簡易乱数生成器を自作している。速度のためだとしてもここをチューニングしても意味なさそう。
・「現時点での最大レベル」を保持する変数への保護がmemory_order_relaxedだけ。atomicにする意義がよく分からない
・「現時点での最大レベル」は実際のところわざわざ保持しなくても常に最大レベルから読み始めても速度落ちなさそう。というかそこのメモリを取り合うコストのほうが高そう
・insert処理がシングルスレッドでしか走らないことを利用してアリーナ型のアロケータを自作している。切り分ける個別のアドレスに削除用領域を残さない分メモリ効率は高そうだけれどこのアロケータ単体で速度を測ったらUbuntu標準のmallocより遅かった…
・アロケータの実装を見るに、freeの分のメモリを節約した事にはなっているが、切り詰めるなら残りサイズでstd::multisetを作って最後までページをしゃぶり尽くす実装などもあり得たがこの実装の判断はどこから？
僕の勘違いもあるとは思いますが、興味深いソースコードです。全体として品質が高く、googleの技術力を感じさせます。

SkipList

SkipListそのものは順序関係のあるデータを検索・挿入・削除がO(log n)となるデータ構造ですが
std::mapなどで実装されている平衡木と比べて

△利点
・乱数により常に負荷分散を行うので、入力データによる偏りを気にしなくて良い
・不変条件を満たす事が比較的容易
▼欠点
・挿入されるアイテム数のlog n程度の最大レベルになるよう調整する必要がある
・アイテム1つ毎に必要になるポインタの個数が最大レベル数に比例して大きくなり二分木より大きくなりがち

といった違いがあります。

木は平衡化のために回転が必須ですが、回転するとどうしても検索途中のスレッドの探索範囲を知らずに変えてしまいます。
SkipListの場合は平衡化の必要がないところがポイントですね。

何故これをLSM-Treeで使おうと思ったかが未だちょっと理解できていないのですが、どこかに解説はないでしょうか。