順序付きデータベースの重要なデータ構造であるB+木だが、それを並列に更新する方法についておさらいして、それを保護するミューテクスの種類について考察してみよう。最近実装したアップグレード付き共有ロックを活用して性能向上できるかについても検討する。
B+木は、キーの順序の観点で隣接する複数のレコードをページという単位でまとめた上で、ページに木構造のインデックスを張ったデータ構造だ。言い換えると、レコードの実データを含むページは木の末端のノード（リーフノードと呼ぶ）に位置し、キーと子ノードのIDを格納するインデックス用のページは末端以外のノード（内部ノードと呼ぶ）に位置することになる。
リーフノードと内部ノードの各々にはユニークなIDが割り振られる。各々のノードは、IDをキーにして、ノードの内容をシリアライズした文字列を値にしたkey-valueデータとして、ハッシュデータベースに格納される。ハッシュデータベースとのデータのやり取りは「ページスロット」と呼ばれる機構によって隠蔽される。ページスロットに対してIDを指定すると、そのノードのデータが取得できるようになっている。スロットは内部にキャッシュを持ち、頻繁に利用されるノードを優先してメモリ上に保持することで、性能向上を図っている。ダブルLRUなどという小賢しいアルゴリズムなのだが、詳細については設計時の記事をご覧いただきたい。ページスロットは内部ノード用に32個、リーフノード用に32個の合計64個に分割され、それによって並列性を高めている。
さて、B+木に対する並列の更新操作を実現するにあたり、Tkrzwでは以下のミューテクスを用いている。
- 各リーフノードを保護するshared_mutex
- 各ページスロットを保護するmutex
- ツリー全体を保護するshared_mutex
リーフノードを保護する必要性については自明だろう。そのノードに属するレコードに更新操作を行う場合には、排他ロックがかけられる。そのノードに属するレコードの参照操作を行う場合には、共有ロックがかけられる。ノードのデータはオンメモリの状態で操作されるので、これを保護するミューテクスはスピンロックで差し支えない。よって、前回実装したSpinSharedMutexクラスを利用するのは合理的だ。
ページスロットは内部にキャッシュを持つので、参照操作においても更新を伴う。キャッシュに乗っていないページが要求されればデータベースに問い合わせて最新データを取得した上でキャッシュを更新する。その際には古いキャッシュを捨てるが、それが更新済みであった場合にはデータベースに書き戻す。よって、全ての操作が排他ロックによって保護されなければならない。そうすると単体では並列性を確保できないので、ページスロットは多数に分割されているのだ。特定のページにアクセスが集中するならキャッシュがよく効くので直列でも高速だし、アクセスが集中しないならスロット分割が有効に機能して並列性が向上するという算段である。
ページスロットに対して、キャッシュに乗っていないIDのノードを要求した場合、そのスレッドはファイルアクセスを待つのでブロックする可能性がある。その状態で、別のスレッドが同じページスロットに対して操作を行うと、ミューテクスがそのスロットをブロックする。ここで、ミューテクスがstd::mutexであれば、内部的にセマフォを使った待機が行われるはずで、その場合はCPUの負荷は小さい。ミューテクスが自前のSpinMutexであれば、ビジーループになるので、CPU負荷が上がってしまう。現状の実装では、衝突率が1/32とそんなに高くはないので、SpinMutexを使っている。下層のファイルクラスの実装に合わせたミューテクスクラスを選択するというのも合理的だとは思っている。つまり、メモリマップI/OであればSpinMutexを、そうでなければstd::mutexを使うということだ。このあたりは今後の課題で、実験を通してベストプラクティスを探らねばなるまい。
ツリー全体を保護するミューテクスは、ツリーの再構築中に通常操作が行われないようにするためのものだ。ツリーの再構築が起きる際に排他ロックを行い、それ以外の操作では共有ロックをかける。B+木の再構築は、レコードの追加や削除によってページサイズが大きくなりすぎたり小さくなりすぎた際に発生する。ページが大きくなって分割された場合、その上位の内部ノードのインデックスも更新されるが、内部ノードも分割されるかもしれないので、その影響は木の根まで波及しうる。ページの結合処理でも同様だ。理想的には分割が波及しうる部分木の最上位のノードより下だけをロックするべきだ。しかし、Tkrzwの実装では、ページの分割や統合が発生した場合には、木の全体をロックしてしまう。ページの分割や統合の頻度はそんなに高くないという割り切りがあるからだ。この割り切りのおかげで、内部ノードはミューテクスを持たなくて済むし、内部ノードを辿る操作でロックとアンロックを繰り替えさなくて済むようになるので、全体的なスループットが向上する。
ツリーの再構築は、ほとんどの場合で、メモリ上だけで完結する。ページが分割されたとして、元のページも新しいページもキャッシュに乗っているので、ファイルアクセスは発生しない。また、上位の内部ノードにインデックスのエントリが一つ増えたり減ったりするが、その内部ノードもキャッシュに乗っているので、ファイルアクセスは発生しない。よって、ツリーを保護するミューテクスはスピンロックでOKだ。
ツリーを保護するミューテクスは、共有ロックから排他ロックにアップグレードできると便利だ。リーフノードの操作は共有ロックを獲得した状態で行われるわけだが、その結果としてページを分割もしくは統合しなきゃならないことがわかったとする。ここで排他ロックを獲得せねばならないわけだが、共有ロックを手放してから排他ロックを確保するという手順だと、その間に別のスレッドに割り込まれる可能性がある。共有ロックを排他ロックにアップグレードできるなら、以下のように処理を単純化することができそうだ。
// 木全体の共有ロックを確保する
tree_mutex.lock_shared();
// リーフノードを更新する
leaf_node.update(...);
// 必要であれば木を再構築する
if (leaf_node.should_be_divide()) {
// 排他ロックにアップグレード
tree_mutex.upgrade();
// 木の再構築
reorganize_tree(...);
// 排他ロックのアンロック
tree_mutex.unlock();
} else {
// 共有ロックのアンロック
tree_mutex.unlock_shared()
}しかし、残念ながら確実なアップグレードは実現できないということは前回述べた。よって、複数のスレッドが同時にページの分割ないし統合の是非を検出することを踏まえて再構築処理を実装することが必要となる。Tkrzwでは、再構築が必要なノードのIDをアトミックなset構造で管理することで、整合性を確保している。ページの分割や統合の必要性を検出したスレッドは、そのIDを登録するだけで良い。そして、毎回のクエリを処理する直前に、直前までのクエリによって再構築対象のIDが登録されているどうかを調べて、あればそれを処理すればよい。その際に、再構築処理は排他ロックの中で行い、それが終わったらアンロックして、その後に共有ロックをかけて通常処理に入る。
// 再構築が必要であれば行う
if (!reorg_ids().IsEmpty()) {
// 木全体の排他ロックを獲得する
tree_mutex.lock();
// 木の再構築
reorganize_tree(...);
// 排他ロックのアンロックする
tree_mutex.unlock();
}
// 木全体の共有ロックを確保する
tree_mutex.lock_shared();
// リーフノードを更新する
int64_t reorg_id = leaf_node.update(...);
// 再構築対象を登録
if (reorg_id > 0) {
reorg_id.Insert(reorg_id);
}
// 共有ロックをアンロックする
tree_mutex.lock_shared();ここまでは、従来の実装の解説であった。一見効率が悪そうだが、これが意外にうまく動くのだ。木の再構築は性能を安定化させるために実行されるに過ぎず、タイミングが多少ずれても問題ない。特にreorg_idsのIsEmptyメソッドがロックフリーであることが性能上重要だ。再構築処理を行わない多くクエリで、全く排他ロックを掛けずに、共有ロックだけで処理を進めることができる。
ところで、確実なアップグレードはできないが、確実なダウングレードはできる。よって、せっかくアップグレード付きの共有ロックを実装したのだから、ダウングレードを使って効率化してみよう。再構築処理で排他ロックを獲得した場合には、アンロックしてから共有ロックを獲得し直すのではなく、ダウングレードすると良い。
// 再構築が必要であれば行う
if (!reorg_ids().IsEmpty()) {
// 木全体の排他ロックを獲得する
tree_mutex.lock();
// 木の再構築
reorganize_tree(...);
// 排他ロックをダウングレードする
tree_mutex.downgrade();
} else {
// 木全体の共有ロックを確保する
tree_mutex.lock_shared();
}
// リーフノードを更新する
int64_t reorg_id = leaf_node.update(...);
// 再構築対象を登録
if (reorg_id > 0) {
reorg_id.Insert(reorg_id);
}
// 共有ロックをアンロックする
tree_mutex.lock_shared();とはいえ、これで高速化するかというと怪しいものがある。シングルスレッドで考えれば、実行する命令の数が減った分だけ高速化するだろうが、マルチスレッドで考えると、ロックを手放せるチャンスを自分から逸しているとも言えるからだ。直前までのクエリの尻拭いと現在のクエリの処理は無関係とも言えるのだ
性能測定してみる。B+木に1000万レコードおよび1億レコードを格納する操作を、旧バージョンとダウングレードを利用した新バージョンで比較する。結果の単位はQPSだ。差が微妙なので、10回実行して最善値を採用した。
| unlock/lock_shared 1-thread | 1773491 |
| unlock/lock_shared 4-thread | 2431366 |
| downgrade 1-thread | 1786876 |
| downgrade 4-thread | 2241303 |
結果としては、ダウングレードを使うと、シングルスレッドではほぼ同じ性能で、マルチスレッドだとむしろ遅くなることがわかった。ロック周りの命令数は減っているはずなのに、マルチスレッドだと遅くなる。直感に反する気もするが、事実は認めねばならない。
まとめ。スピンロックの導入に合わせて、B+木の並列操作の保護に使うのに適切であるかどうかを再検討した。新たに実装したスピンロックによるミューテクス実装を活用する方向で問題なさそうだ。すなわち、リーフノードはSpinSharedMutexで保護し、スロット化されたページキャッシュはSpinMutexで保護し、ツリー全体はSpinSharedLockで保護する。
ツリー全体を保護するSpinSharedLockにて、アップグレード機能を適用できるか検討したが、それは現実的ではないことがわかった。ダウングレード機能は適用できることが分かったが、実装と性能評価をしてみたら、むしろ遅くなってしまった。よって、普通にロックとアンロックを繰り返す従来の実装を維持することにした。
