豪鬼メモ

一瞬千撃

DBMのローカルシャーディング

データベースの文脈において、シャーディングとは普通はデータベースを行で水平分割して複数の計算機に割り当てることを意味する。今回は敢えてそれをローカルで行う機能について考えてみたい。つまり、単一の計算機上でデータベースファイルを複数に分けて運用するのだ。


一般にデータベースの水平分割と言えば、レコードの特定の属性に着目して、行単位でデータベースを分割する。例えばログのデータベースを発生年ごとに分割して管理するようなのが典型だ。データベースを分割することで、データの更新や検索にかかる負荷が小さくなる。

シャーディングは水平分割の一種なのだが、わざわざシャーディングと言った場合、スキーマドメイン依存の知識を使わない手法についての言及であることが多い。典型的には、主キーにハッシュ関数を適用した結果を元に各レコードが所属する部分集合(=シャード)を決めるような手法が用いられる。主キーからそのレコードが所属するシャードが特定できれば、該当のシャードだけを操作することで処理の効率化が図れる。また、個々のシャードを別の計算機に配置すれば分散処理が実現できるし、同一のレコードを複数のシャードに重複して記録して障害耐性を持たせることもできる。

今回ここで考察するのは、分散処理のためのシャーディングではない。単にDBMのファイルを複数に分割して運用する機能をローカルシャーディングと呼び、その設計と実装について考察する。DBMは単一のファイルでデータベースが実現できるお手軽さが売りではあるのだが、ローカルシャーディングでファイルを分割すると以下のような利点がある。

  • マルチスレッドの並列処理性能が上がる
  • 計算量がシャード数で分割される。
  • データベースの再構築が効率的に行える
  • データ構造やファイルシステムの実装から来る最大ファイルサイズの制限を回避できる

順に掘り下げていこう。まずはマルチスレッドの並列処理性能に関してだ。ハッシュテーブルやB+木をDBMとして実装するにあたり、そのマルチスレッドでの並列処理性能が最大化するように既に最大限の努力をしている。ハッシュテーブルではバケット単位で排他制御を行い、B+木ではページ単位で排他制御を行っている。しかし、それでもスレッド同士が互いをブロックし合う確率はそれなりにある。ローカルシャーディングを行った場合、異なるデータベースファイルに対する操作は完全に独立して行われるため、並列処理性能は理想に近づく。シャード数が10の場合、スレッドがブロックされる確率は1/10になる。

検索や更新にかかる計算量も低くなる。O(1) であるハッシュテーブルの計算量はそれ以上向上しないが、O(log N)であるB+木やスキップリストの計算量は、レコード数をN、シャード数をSとすると、O(log (N/S)) になる。処理対象のファイルはシャーディング用のハッシュ関数で限定され、その処理は O(1) で済む。そして個々のファイルのサイズはシャード数の分だけ小さくなるので、当然全体の計算量はシャード数の分だけ低くなる。

データベースの再構築の計算量は、ハッシュテーブルで N であり、B+木やスキップリストで N*log(N) である。例によってハッシュテーブルの計算量はシャーディングを適用しても変わらないが、B+木やスキップリストでは N*log(N/S) になる。また、再構築に必要な一時ファイルの空間計算量は全てのデータ構造で N であるが、シャーディングを適用すると N/S になる。各シャードを順に再構築できるからだ。これは大規模なデータベースを構築する際には重要な特性だ。

最大ファイルサイズに関しては、Tkrzwの場合はデフォルトで最大32GB、チューニングを変えればいくらでも大きいファイルを扱えるので、シャーディングの特筆すべきメリットというほどではない。とはいえデフォルトである4バイトのアドレスで合計4GB以上のデータベースを扱えるようになるので、空間効率の向上には多少寄与する。


シャーディングを実現するクラスの実装は単純だ。DBMインターフェイスを実装したプロクシクラスを用意して、中にDBMの具象クラスのインスタンスの配列を持たせる。ファイルを開く際には00000,00001といった接尾辞をつけた複数のファイルを作り、各DBMインスタンスに割り当てる。レコードに対する操作では、キーにハッシュ関数を掛け、その値を配列の要素数で割ってDBMインスタンスを決め、それに処理を移譲する。例えばレコードを検索するGetメソッドの実装は以下のようになる。

Status ShardDBM::Get(std::string_view key, std::string* value) {
  const int32_t shard_index = SecondaryHash(key) % dbms_.size();
  auto dbm = dbms_[shard_index];
  return dbm->Get(key, value);
}

シャーディング用のハッシュ関数にはFNVハッシュを使う。ファイル内のハッシュテーブルにはMurmurハッシュを使っているので、それとかぶらないもので、単純かつ高速なのがいい。


ローカルシャーディングによって本当に並列処理性能が向上するのか、確かめてみよう。"00000000" から "09999999" までのランダムに生成したキーを持つレコードを1000万件書き込む。値も同じような8バイトの文字列である。さらに、そのデータベースに対して1000万回検索してから、全てのレコードを削除する。10スレッドで並列して処理を行い、それぞれの操作にかかる時間を測定する。まずはシャード数1の結果から。

class Set Get Remove memory usage file size
HashDBM 2,281,733 QPS 3,711,545 QPS 2,577,823 QPS 181.0 MB 182.8 MB
TreeDBM 715,372 QPS 2,398,091 QPS 625,034 QPS 385.7 MB 119.8 MB
SkipDBM 510,634 QPS 866,662 QPS 839,042 QPS 420.5 MB 122.5 MB

ハッシュテーブルはSetで228万QPS、Getで371万QPSということで、申し分なく高速である。それに比べるとB+木とスキップリストは遅い。計算量で不利な上に、並列処理性能でも劣るので仕方ない。その割には大健闘しているという見方もできるけれど。さて、では同じ操作をシャード数10でやるとどうなるだろう。

class Set Get Remove memory usage file size
HashDBM 5,163,622 QPS 6,321,919 QPS 5,653,435 QPS 181.3 MB 182.8 MB
TreeDBM 2,373,253 QPS 3,739,910 QPS 2,263,250 QPS 387.5 MB 119.9 MB
SkipDBM 564,395 QPS 1,712,049 QPS 1,220,438 QPS 387.8 MB 122.5 MB

なんと、ハッシュテーブルはSetで516万QPS、Getで632万QPSを叩き出した。既にO(1)であるハッシュテーブルの計算量はシャーディングをしても変わらないのだが、並列処理性能が上がることで全体のスループットが改善する。そして、B+木のSetが231万QPS、Getが373万QPSに到達した。計算量が改善したとともに、並列処理性能も上がったおかげだ。順序ありのデータベース実装でここまで高速なのは、なかなか素晴らしいことではないか。スキップリストのSetは今のところマージソートの並列化対応を入れていないのでシャーディングしても性能が改善しない。一方、Getはかなり改善して171万QPSまで出るようになる。


ところで、B+木やスキップリストのような順序付きのデータベースをシャーディングするにあたって、順序が台無しになってしまっては困る。シャーディングはハッシュ関数を使うので、シャード間に順序関係はない。したがって、検索時に順序を回復する必要がある。

ややこしい話なので、図で説明していこう。まず、B+木やスキップリスト(スキップリスト付き連結リスト)のデータベースは、キーの昇順でソートされたレコードの集合であると考えることができる。例えば、1から8までのキーを持つレコード群が単一シャードのファイルに保存されていることを想定しよう。

(1, a), (2, b), (3, c), (4, d), (5, e), (6, f), (7, g), (8, h)

このデータベースを検索して、3以上5以下のレコードを取得することを考える。その場合、まずイテレータを作って、それをキーが3のレコードに飛ばして、そこからレコードを次々と読み込み、5を超えるキーを読んだ時点で処理を終了する。実際のコードはこんな感じになる。

auto iter = dbm.MakeIterator();
iter.Jump("3");
std::string key, value;
while (iter.Get(&key, &value).IsOK()) {
  if (key > "5") break;
  std::cout << key << ":" << value << std::endl;
  iter.Next();
}

さて、これがシャーディングされている場合にどうなるか。シャード内でのレコードの順序は保証されるが、シャード間の順序は制御できない。よって、データベースの中身はこんな感じになる。

shard-0: (3, d), (6, f)
shard-1: (2, b)
shard-2: (5, e), (8, h)
shard-3: (1, a), (4, d), (7, g)

このような、ソートされた部分集合のリストから、元々の単一のソート済みの集合を取り出すことが必要になる。ここですぐに気づくのは、外部記憶を使ったマージソートのマージ部分と全く同じアルゴリズムが利用できるということだ。すなわち、各シャードを先頭から順に読み込む「リーダ」を用意して、各リーダの現在のキーを基準にしたヒープ木を構築するのだ。ヒープの先頭は常に最小の要素になる。したがって、先頭リーダからレコードを読み込むとともに、そのリーダは次のキーを基準としてヒープ木に再登録するという処理を繰り返せば、最終的にソート済みのレコード群が得られる。各シャードのDBMのイテレータはここで言うリーダそのものである。

シャーディングは透過的に行う。すなわち、アプリケーション側のコードは、シャーディングをしていてもしていなくても全く同じである。よって、全シャードのイテレータを内部に持つプロクシクラスを用意する。プロクシのJumpメソッドが発行された際には、内部のイテレータ全てでJumpメソッドを発行する。プロクシに対するGetが発行された際には、先頭の内部イテレータを使ってレコードを参照する。プロクシに対するNextが発行された際には、先頭の内部イテレータから次のキーを取り出し、ヒープ木を再構築する。

シャーディングをしていない場合の順序付きレコード検索の計算量はレコード数Nとレコード抽出数Mに対して O(log N + M) である。一方、ヒープ木の再構築の計算量はシャード数Sに大して O(log S) であり、それをM回行うことになる。したがって、シャーディングをした場合の順序付きレコード検索の計算量は、O(S * log(N/S) + M * log S) となる。よって、SやMが大きい場合には検索性能が悪化することにはなる。ただし、多くの場合でSやMは小さいので、検索性能はシャーディングをしてもしなくてもだいたい同じだと言えそうだ。それでいて、並列処理性能は劇的に改善するので、全体のスループットはかなり上がるはずだ。ローカルシャーディングはかなり有効な手法だと言えるだろう。


まとめ。データベースファイルを分割するローカルシャーディングの手法について考察するとともに、性能テストを通して実際に性能が向上することを確かめた。ローカルシャーディングをうまく使うと、複数のマシンを使った分散処理をせずとも、理論的にはCPUのコア数までは並列処理性能を高めることができる。分散処理をするにしても単体のスループットを最大化した上で行った方が得であろう。

この機能は既にTkrzwに実装されていて、ShardDBMというクラスとして利用できる。これをもってDBMとして実現したかった機能は全て作り終えている。一通りのドキュメントも揃えたし、あとはリリースするだけだ。