2011-10-31
MongoDB の BSON
ペーパードライバーにはヒマなエリアへ出張中. 各種中毒メディア群も数周して飽きたため, 前から読みたかった MongoDB でも調べよう...としたけれど, 思ったよりコードサイズがあるなあ. ちょっとだけ眺めて気を済まそう...
ウェブっ子でない同士諸兄に説明しておくと, MongoDB は JSON のようなオブジェクトに 適当な ID を割り振り, その ID をキーに JSON (のようなもの)を検索できるようにした データベースのこと. ID 以外の JSON のフィールドにもインデクスをつけて 検索できるぶん便利な子だとされている. (教科書情報.) 今日は手始めに MongoDB 内の JSON 表現たる "BSON" を眺めた.
MongoDB は, 自身が内部で使っている JSON 相当のデータ表現を BSON (Binary JSON) と呼び, あわよくば広く使ってもらおうと bsonspec.org でフォーマットを文書化している. 広く使われているのかは知らない. 個人的にはBSON のデザインはいまいちだという主張におおむね同意しつつ, 一方で実装には多少の頑張りも見られたので紹介したい. なお BSON のコードは MongoDB のツリーに入っている.
Traversability
BSON はデータ表現がもつ特徴のひとつに traversability を挙げている. traversability というのは, 要するに JSON のオブジェクトツリー内にある特定の要素を 特定する式...たとえば foo.bar[5].baz なんてのを与えたとき, baz の値をずばっと取り出せることだと思えばいい.
JSON のパーサやその類似品を書いたことがあるひとにとって, これは当たり前のことに思えるかもしれない: JS のオブジェクトリテラルを表現できるオブジェクトモデルを用意し, パースの結果としてそのモデルに基づいたツリーを作る...そんな実装なら, できあがったツリーが traversale でないはずがないよね.
ただ典型的な実装と違い, MongoDB の BSON パーサは明示的なツリー構造をもたない. もっといえば, この BSON 実装にはパーサがない. 明示的なツリー構造がないのに traversability はある. これが BSON の主な見所です.
BSONObj, BSONObjIterator, BSONElement
MongoDB の BSON はパースすべきメモリブロックのポインタを持つだけの オブジェクトとして表現されている. (bsonobj.h)
class BSONObj {
public:
...
explicit BSONObj(const char *msgdata) {
init(msgdata);
}
...
private:
void init(const char *data) {
_objdata = data;
...
}
...
const char *_objdata;
boost::intrusive_ptr< Holder > _holder;
...
};
"_objdata" が BSON データの先頭を指している. "_holder" はヒープの寿命をトラックしているが, とりあえず無視していい. こんな素朴なつくりながら, BSONObj は BSON ツリーのルート要素を表している. 仕様の言葉 でいうと document, JSON でいう object, 要するに文字列をキーとした連想配列ですね.
仕様の "e_list" にあるとおり, document の中にはキーの文字列とその値の対である "element" が並んでいる.
// from http://bsonspec.org/#/specification
document ::= int32 e_list "\x00" BSON Document
e_list ::= element e_list
| ""
element ::= "\x01" e_name double Floating point
...
この element のリストをたどるには BSONObjIterator を使う. (bsoniterator.h)
class BSONObjIterator {
public:
BSONObjIterator(const BSONObj& jso) {
int sz = jso.objsize();
...
_pos = jso.objdata() + 4;
_theend = jso.objdata() + sz - 1;
}
...
};
要素をたどる next() メソッドはこんなかんじ.
BSONElement next() {
assert( _pos <= _theend );
BSONElement e(_pos);
_pos += e.size();
return e;
}
名前と値の対をあらわす BSONElement をつくり, その(バイナリ上の)サイズを読みながらカーソルを進めている.
BSONElement はこんな定義をもつ: (bsonelement.h)
class BSONElement {
public:
...
explicit BSONElement(const char *d) : data(d) {
fieldNameSize_ = -1;
totalSize = -1;
...
}
const char *data;
mutable int fieldNameSize_; // cached value
mutable int totalSize; /* caches the computed size */
};
メンバ変数につけるアンダースコアの有無ははっきりしてほしいというかいつもつけてほしいけれどそれはさておき, コメントも // と /* */ を混ぜないでほしいけれどそれもさておき, BSONElement も事実上バイト列へのポインタだけを持つクラスなのがわかる. BSONObj と似たつくり.
バイト列上に占める BSONElement の大きさは, データの中を調べればわかる. (bson-inl.h)
inline int BSONElement::size() const {
if ( totalSize >= 0 ) // 計算済ならそれを返す
return totalSize;
int x = 0;
switch ( type() ) { // type tag によって大きさがかわる
...
case NumberInt:
x = 4; // int なら 4 byte だとか.
break;
...
}
totalSize = x + fieldNameSize() + 1; // BSONType
return totalSize;
}
仕様によると型タグである type() は element バイト列のの先頭に入っているはず...
BSONType type() const { return (BSONType) *data; }
たしかにフィールドの先頭を調べていた. 同じく仕様によればフィールド名は cstring 型だから当然...
int fieldNameSize() const {
if ( fieldNameSize_ == -1 )
fieldNameSize_ = (int)strlen( fieldName() ) + 1;
return fieldNameSize_;
}
const char * fieldName() const {
if ( eoo() ) return ""; // no fieldname for it.
return data + 1; // +1 して type tag を読みとばす.
}
strlen() で長さが測れる. 便利ですね.
こんな風に, BSONObj や BSONObjIterator は JSON ツリー構造のノードに相当する BSONElement を必要に応じて作ってはかえしている. この BSONElement はスタックに確保される. BSONObj も BSONElement も外側から与えられたバイト列のポインタを持っているだけ. どれも動的なメモリ確保が必要ない軽量なオブジェクトだとわかる.
BSONElement は自分自身のサイズや型をバイト列の中から読み取る. そういう意味で BSONElement を BSON のパーサと考えてもいい. でもデータ全体を先頭から読まず, 自分に渡された部分的なバイト列の先頭付近だけ必要なときに調べる怠惰なつくり. パーサと呼ぶのはちょっと気がひける.
さて BSONObjIterator::next() を使い, 自分のたどりたい document 内の element を探しだして BSONElement を取り出すことができた. 今度はこの BSONElement の値からネストした document をとりだすところをみてみよう.
inline BSONObj BSONElement::Obj() const { return embeddedObjectUserCheck(); }
inline BSONObj BSONElement::embeddedObjectUserCheck() const {
if ( MONGO_likely(isABSONObj()) )
return BSONObj(value());
....
}
value() は...
class BSONElement {
public:
...
const char * value() const {
return (data + fieldNameSize() + 1);
}
...
};
バイト列の中で値をあらわす位置のポインタを求め, BSONObj を作っていた. 数値のようなプリミティブな型もだいたい似たような仕組みでとりだしている:
/** Return double value for this field. MUST be NumberDouble type. */
double _numberDouble() const {return *reinterpret_cast< const double* >( value() ); }
/** Return double value for this field. MUST be NumberInt type. */
int _numberInt() const {return *reinterpret_cast< const int* >( value() ); }
/** Return double value for this field. MUST be NumberLong type. */
long long _numberLong() const {return *reinterpret_cast< const long long* >( value() ); }
こんな風に BSONObj -> BSONObjIterator -> BSONElement -> (BSONObj やプリミティブ) などと BSON のツリーをたどり, 必要な値をとりだせばよいようす.
遅延評価
上でみたとおり, MongoDB の BSON 実装は構造をルートからトラバースしながら 必要に応じてデータをパースする, ある種の遅延評価になっていることがわかった. これなら事前にデータ構造を作らなくてすむ. 余計なデータのコピーもおきないし, データ構造のために動的なメモリ確保をすることもない. 効率はよさそうだ.
ただオブジェクトグラフをつくらない制限はある. たとえば BSONElement を包含する親の BSONObj を辿ることはできない. BSONObjIterator を逆順に辿ることもできない. それでも不要なフィールドをスキップしつつ子に向かってトラバースはできるから, たとえば foo.bar[5].baz であらわされた値をとりだすくらいなら問題ない. MongoDB の中で使う分にはこれでいいのだろう.
Baked Data と Mapped IO
プログラムの中で直列化表現をそのまま使いまわすテクニックは, 計算資源にとぼしいジャンルでよく使われる. "Data Baking" なんて呼ぶこともあるらしい. MongoDB は BSON に限らず baked data をうまく使っている. たとえば BTree はより積極的に直列化表現を使いまわしている. (気がむいたらそのへんの話も書きます.)
こうした baked data の多用は MongoDB のストレージ実装と関係が深い. MongoDB はストレージのキャッシュを自分でもたず仮想記憶にぜんぶ任せている. (Wiki による.) 要するに mmap() したファイルを直接読み書きすることでストレージ操作をしている. BSONObj なら, この mapped I/O をそのままトラバースできる.
MongoDB の売りの一つである in-place replacement も mapped IO と baked data の恩恵を受けているのだろう. サイズが同じデータ同士なら, BSONObj があらわすメモリブロックに新しい BSONObj をコピーするだけでいい. BSONObj は自身のサイズも該当メモリアドレスも知っている. 加えて, BSON/JSON なら大きな document ツリーの部分木も自然に表現できるから, たとえばカウンタをふやすような小さいサイズの操作はその部分木だけ書き換えれば済む.
MongoDB はこの in-place replacement を性能上の優位の一つとして押し出している. CouchDB みたいな追記主体のアプローチとどちらが良いのかは用途次第だろうけれど, デザインに一貫性はあるとおもった. もともと私は MongoDB みたいなデータベースなんて Berkeley DB に 直列化した JSON を出し入れすればできあがり, なんてタカをくくっていた. でもレコードのデータ表現だけですら工夫の余地があるのを見て襟を正した.
逆に MongoDB のストレージエンジンをとりかえようとしたら けっこう苦労しそう. Wiki を読むと現行の実装はあくまで ストレージエンジンの一つと言いたげな気配が伝わってくるけれど, ほんとに新しい実装が増える日は来るのかな?
まとめ
- MongoDB の BSON は遅延評価を頼りに部分バイト列を参照するだけのオブジェクトを使っていた.
- パースの遅延評価はヒープ上のオーバーヘッドがすくなく, 同時にまあまあ traversable という特徴がある.
- メモリブロックを直接参照するデザインは mapped IO を中心にした MongoDB のストレージとも相性がよい気がする.
- MongoDB っていってみたかった.