ツリーデータベースを実装するにあたり、具体的にどういうデータ構造を使うかを検討する。並列化についてもここで検討する。
前々回の議論で、B+木のノードを管理するためのキャッシュ機構は32個のスロットに分割して管理し、最大32の並列性を実現すると述べた。今回はノードオブジェクトを取り出した後の操作をどう並列化するかについて検討する。普通、ツリー系のアルゴリズムは順序関係があるので変更操作を並列化するのは難しい。ある要素を変更するとして、その要素の位置は他の要素との関係性によって決まるわけで、他の要素が同時に書き換えられるとしたら何を基準に自分の位置を決めるのか。しかし、B+木においては、影響範囲がノードの中に限定される操作に限っては、ノード単位で並列化することができる。例えば、"A" より大きいキーのレコードを持つリーフノード1と "B" より大きいリーフノード2があったとして、そのデータベースに "A1" と ”B1" を同時に追加することができる。それぞれにスレッドは、内部ノードを辿って、A1が属するリーフノード1とB1が属するリーフノード2をそれぞれ特定する。内部ノードの検索は読み取り操作なので同時に行っても問題ない。そしてそれぞれにリーフノードは独立しているので、同時に変更しても問題ない。よって、リーフノードはノード毎のreader-writerロックで保護するという方針で良いだろう。ということで、ノードの構造体は以下のようなメンバを持つだろう。
struct LeafNode {
TreeDBMImpl* impl;
int64_t id;
int64_t prev_id;
int64_t next_id;
std::vector<TreeRecord*> records;
size_t page_size;
bool dirty;
bool on_disk;
std::shared_timed_mutex mutex;
LeafNode(TreeDBMImpl* impl);
~LeafNode();
};前々回も述べたが、この構造体はデータベースの中身と自身のデータの一貫性を担保する責任を持つので、コンストラクタでデータベースにアクセスするためにTreeDBMImplのポインタを受け取り、デストラクタではそれを使ってデータベースへの書き込みを行う。データメンバとしては、リーフノードの書式で記載した属性を表現すべく、自分のID、前のノードのID、次のノードのID、レコードのベクタを持つ。そのノードに属するレコード群を保持するために使うのはベクタである。鋭い方は、中間への挿入や削除のコストが O(N) だから非効率だと気づくだろう。教科書には、挿入や削除のコストを気にするならツリーを使えと書いてある。しかし、ここでstd::setとかでデータを持つとメモリ使用量がバカにならないので、挿入や削除のコストを飲んでベクタを選択する次第だ。読み取りは普通に二分探索でできるから早い。新しいレコードの挿入位置の決定はstd::upper_boundで行うことで、レコードが常にソート済であることは保証される。
もう一つ気づいて欲しいのが、レコードのベクタの要素がポインタ型であることだ。これはわざとで、TreeRecord*の実態は実は既にレコードがシリアライズされた状態の文字列を指すchar*である。普通に構造体として表現すると、キーの値の整数型で4バイト、キーの文字列のポインタで8バイト、キーの文字列自体の領域とそれを確保する際のフットプリント、値の整数型で4バイト、値の文字列のポインタで8バイト、値の文字列自体の領域とそれを確保する際のフットプリントの分だけメモリを食う。それはでかすぎるので、シリアライズした単一の文字列としてデータを保持して、必要に応じてパースしてキーと値のstring_viewを返した方が効率的だ。あと、そのchar*の確保はnewではなくmallocで行う。なぜなら値のサイズが変わった時にdeleteとnewを繰り返すのではなく、reallocしたいからだ。ただ、この種の最適化は弊害になる場合もあるので、性能実験してから最終決定をすべきだ。
データベースならではの属性として、page_sizeとdirtyとon_diskというのがある。page_sizeは、そのノードをシリアライズした時のサイズを管理する。レコードが追加される時に、キーと値のサイズとそれにかかるフットプリントをpage_sizeに足す。レコードが削除される場合には同じ値を引く。この値が閾値を超えて、かつレコードが2個以上である場合には、ノードの分割が発生する。dirtyは、一度でもレコードの挿入や削除や行った場合に真になり、その場合にだけデストラクタがデータの書き戻しを行う。on_diskは、そのノードが新しく作られたのか、それともデータベースから読み込まれたのかを保持する。そのノードが消滅する際に、そのノードがデータベースから読まれたものなら、データベースから該当のレコードを削除する操作を行う必要がある。そうでなければ、そのノードはデータベース上には存在していないはずなので、削除操作はしない。
一方で、内部ノードは以下のような構造体になるだろう。
struct InnerNode {
TreeDBMImpl* impl;
int64_t id;
int64_t heir_id;
std::vector<TreeLink*> links;
bool dirty;
bool on_disk;
InnerNode(TreeDBMImpl* impl);
~InnerNode();
};データベースへのアクセサとしてTreeDBMImpl*を持つ。自分のIDと長子のIDも持つ。それ以外の子ノードに関してはリンクのベクタとして持つ。これがベクタである理由と、要素がポインタである理由は、リーフノードのレコードで述べた理由と全く同じである。dirtyとon_diskの役割も同じだ。
特質すべきは、mutexを持っていないことだ。つまり内部ノードの排他制御はノード単位ではしないということだ。じゃあどうするのか。ここからが並列化の議論である。リーフノードの読み取りや更新の操作は頻繁に行われるが、内部ノードに関しては読み取り操作が圧倒的に多い。なぜなら、リーフノードが分割されたり結合されたりする頻度は多くないからだ。なので、通常の状態においては、内部ノードは常に読み取り専用として扱い、ノーガードでアクセスさせることで、ロックのコストを下げる。言い換えると、リーフノードの分割や結合に伴う木の再構築処理は通常の読み取りや書き込みの処理とは全く別のタイミングで行うことにする。リーフノードの更新操作によって、そのリーフノードの分割や結合が必要であることが検出された場合、そのノードIDを集合に登録する。その集合をスレッドセーフに扱うためにAtomicSetというクラスを設計したりもしているのだが、その詳細ついては割愛しよう。そして、通常のリーフノードの操作が終わった後に、その集合が空でないことが検出された場合、データベース全体をロックして、リーフノードの分割や結合とそれに伴う内部ノードの再起的な分割と結合を一気に行う。つまり、木の再構築は並列して行わない。この割り切りをすると、実装がとてもすっきりして、再構築を伴わない処理のコストが下がる分だけ、全体の性能は上がると期待している。
