DBサービスを作ろう その7 シャーディング最強説

シャーディングによってデータベースを分割することで、通常運用の並列処理性能を向上させることができる。それだけでなく、バックアップ作成などの、他のスレッドをブロックさせうる操作の影響を最小限に留めることができる。その運用方法について説明する。

Tkrzwのデータベースの全てのクラスは、ShardDBMというアダプタクラスを介して利用することができる。ShardDBMな内部的に任意の数にデータベースを分割して管理するが、利用者にとってのインターフェイスは変わらない。すなわち透過的にシャーディングをするクラスである。Tkrzw-RPCのサーバもこのShardDBMを使っている。

実際にサーバを立てて見よう。ハッシュデータベースを100個に分割するシャーディングを行う。個々のシャードには200万個のバケットを持たせ、合計2億バケットのデータベースにする。さらに、追記更新モードで堅牢性を向上させる。

$ tkrzw_server --async --threads 4 \
  "casket.tkh#num_shards=100,num_buckets=1M,update_mode=appending"

このデータベースに、1億個のレコードを格納する。4スレッドの各々に2500万回ずつの操作を行わせ、100回分の操作をバッチで送り込むことにしよう。

$ tkrzw_dbm_remote_perf sequence --set_only --multi 100 --threads 4 --iter 25000000

この操作は128秒で終わる。RPCで1億件の更新をしているのに、たった128秒で終わるというのはなかなかのものではないか。

本題はここからだ。上記の操作の直後に、このデータベースをSynchronizeする。すなわち、全てのダーティバッファをストレージ（SSD）に書き込ませ、その完了を待つ。

$ tkrzw_dbm_remote_util sync --hard

この操作には、1.7秒の時間がかかった。もしシャーディングしない場合、全てのデータベース操作が1.7秒の間はブロックされることになる。しかし、ここでは100個にシャーディングしているので、個々のシャードがブロックしている時間は1/100の0.017秒であり、ほとんど無視できる時間だ。スレッドがブロックされる確率も1/100になる。ここまで影響を軽微にできるなら、1分に1回Synchronizeするような運用もできるだろう。

バックアップを取ろう。syncサブコマンドは "key=value" の形式でパラメータを送れるが、"make_backup" を送ると、バックアップファイルが作成される。パラメータの値でバックアップファイルの接尾辞を指定できるが、空白の場合は現在日時のYYYYMMDDhhmmss形式が指定される。

$ tkrzw_dbm_remote_util sync "make_backup="

これは3.44秒かかった。1シャードあたりは0.034秒だ。この場合も、オンラインで運用して大丈夫そうだ。シャーディングしない場合にはBtrFSのスナップショットを使う方法などの工夫をしたくなるが、ブロック時間が0.034秒ならその必要はないだろう。

データベースの再構築（Rebuild）でも、シャーディングの恩恵がある。Tkrzwの売り文句の一つは、他のスレッドを止めずに再構築ができることであり、これと追記モードを組み合わせると、性能と堅牢性が両立できる。詳しくは公式文書のTipsをご覧頂きたい。さて、実際に実行してみよう。

$ tkrzw_dbm_remote_util rebuild

これは74.2秒かかった。1シャードあたりの時間は0.7秒ということになるが、処理中も他のスレッドをブロックしない設計なので、ブロック時間はほぼゼロだ。データベースの再構築はデータベース全体の再生成を伴うのだが、その間の更新は古いデータベースと新しいデータベースの両方に適用される。つまり、再構築中の更新処理の負荷は2倍になるのだが、100分割して実行すれば、負荷が上がる操作の確率が1/100になる。また、シャーディングしない場合には再構築には元のデータベースファイルとほぼ同じサイズの一時ファイルを作るが、そのサイズも1/100になるという利点がある。この特性によって、データベースの再構築をオンラインで定期的に行うことが可能になる。1日1回実行しでもいいし、3時間に1回とかでもいい。絶対壊れない追記型データベースとして運用することの欠点は定期的な再構築が必要なことだが、再構築をブロックせずに行えることでそれを克服し、最強になるのだ。

実際に、再構築処理が続けられている状態で、他の端末からデータベースの検索や更新を行ってみてほしい。ブロックせずに処理できることが確認できる。

$ tkrzw_dbm_remote_util get 00000001
bcdefghi
$ tkrzw_dbm_remote_util get 00000002
cdefghaj
$ tkrzw_dbm_remote_util set --multi 00000001 yuutei 00000002 miyaou 00000003 kimukou
$ tkrzw_dbm_remote_util get --multi 00000001 00000002 00000003
00000001    yuutei
00000002    miyaou
00000003    kimukou

シャーディングを駆使すると、オンメモリデータベースにあたかもファイルデータベースであるかのような堅牢性を持たせることができる。Tkrzwのオンメモリデータベースにはファイルを関連付けることができ、そうすると、起動時にそのファイルからレコードのデータを読み込み、終了時に更新データの下記戻しを行うようになる。この時点で、メモリ消費量が多いということ以外は、ファイル上のデータベースと遜色なく使うことができると言える。しかも性能は圧倒的に高い。とはいえ、プロセスやOSが突然死した場合にはメモリ上の更新データは失われてしまうので、ファイルデータベースほど堅牢とはいえない。ただし、Synchronizeメソッドを定期的に呼んで更新内容をファイルに同期させられるのなら、話は変わってくる。ファイルデータベースを運用している場合でもSynchronizeを定期的に呼ぶことは推奨されるが、それは、デバイスと同期させないとファイルであってもデータが失われる可能性があるからだ。この構造は、オンメモリデータベースでも変わらない。

Synchronizeを呼ぶまでは安心できないという点では、ファイルもオンメモリも同じなのだ。オンメモリデータベースの本質的な問題は、Synchronizeでデータ全体を書き出さねばならす、それに時間がかかることだ。Synchronizeの実行中は他のスレッドはブロックされてしまう。シャーディングはこの問題を緩和してくれる。データベースを100個に分割すれば、ブロックされる時間も1/100になるのだ。ということで、オンメモリデータベースを立てよう。ファイルの拡張子を「.tkmt」にすると、オンメモリのTinyDBMのインスタンスが作られ、そのファイルが関連付けられる。

$ tkrzw_server --async --threads 4 \
  "casket.tkmt#num_shards=100,num_buckets=1M"

これにも1億件のレコードを格納しておく。コマンドはファイルデータベースの場合と全く同じだ。かかる時間もほぼ同じで、120秒ほどで済む。このデータベースに対して、同じく上述のコマンドでSynchronizeメソッドを呼ぶと、13秒ほどかかる。1シャードあたりだと0.13秒で、ブロックされる確率が1%であることを考えれば、オンラインサービスでも許容範囲であることは多いだろう。

シャード数を増やすほどに並列性が上がるなら、シャード数を千個とか万個とかにすればいいじゃないかと思うだろう。実際のところ、300個くらいなら普通に実用範囲だ。単一プロセスが開けるファイルディスクリプタの数までシャード数を増やすことも考えられる。とはいえ、CPUコア数以上に並列性は上がらないので、通常の検索や更新処理の性能向上は10シャードくらいで頭打ちになる。SynchronizeやRebuildのブロック時間を下げたいなら、シャード数は多ければ多いほどよいということにはなるが、あんまり多いとシャード毎のオーバーヘッドが通常運用の時間効率や空間効率を下げてしまう。よって、2個から1000個の範囲が現実的なところだろう。データの内容やアクセスパターンによって最適値は変わってくる。

ところで、SynchronizeやRebuildなどの時間がかかる操作をgRPCのワーカスレッドでそのまま処理すると、そのスレッド自体がブロックする。同期APIの場合は他のワーカスレッドが他のコネクションを捌くので良いのだが、非同期APIの場合はそういうわけにはいかない。非同期APIでは、単一のワーカスレッドが複数のコネクションを捌くので、ワーカスレッドが長時間ブロックすると、そのワーカスレッドのその他のコネクションの操作がブロックしてしまう。よって、非同期APIの場合には、ワーカスレッドからさらにバックグラウンドスレッドを立てて、SynchronizeやRebuildを呼ぶ必要がある。Trkzw-RPCの最新版（0.7.3）ではその実装を入れている。

シャーディングを施すとイテレータの順序がどうなるのか気になる人もいるだろう。ハッシュ系のデータ構造の場合には元々順不同なので、全レコードに一回ずつアクセスできる限りは問題ない。ツリー系のデータ構造の場合には順序が重要なので、シャーディングした場合でもその順序は保持されてほしいところだ。よって、ヒープソートをしながら最小もしくは最大レコードを返し続けるイテレータがShardDBM実装されている。確認するために、TreeDBMを10シャードで運用したサーバを立ててみよう。

$ tkrzw_server --async --threads 4 \
  "casket.tkt#num_shards=10,num_buckets=1M"

これにも1億レコードを入れておく。私の環境では170秒ほどかかった。その状態で、「00000100」をキーの下限とするレコードを20個取り出す。

$ tkrzw_dbm_remote_util list --move jumplowerinc --jump_key 00000100 --items 20
00000100    cbedgfah
00000101    dcfehgbi
00000102    edgfahcj
00000103    fehgbidk
00000104    gbadcfeh
00000105    hcbedgfi
00000106    adcfehgj
00000107    bedgfihk
00000108    edgfahcj
00000109    fehgbidk
00000110    gfahcjel
00000111    hgbidkfm
00000112    ehgjalcn
00000113    fihkbmdo
00000114    gjalcnep
00000115    hkbmdofq
00000116    gnapcret
00000117    hobqdsfu
00000118    apcretgv
00000119    bqdsfuhw

個々のレコードはハッシュ関数によってまちまちのシャードに入れられているのに、ちゃんと順序通りにレコードが取り出せている。普通に考えると、シャーディングとレコードの順序は相容れないものだが、ヒープソートを噛ませることでうまいことバランスを取っている。イテレータの内部では、レコードを取り出す毎にシャード数に応じたストリームを要素とするヒープ木を再構築しているので、シャード数をNとするとlog Nの計算量がかかることになる。この理由で、シャード数を多くしすぎるとイテレータが多少遅くなる。とはいえ対数スケールなので、100個と200個には15%の違いしかないけれど。

まとめ。Tkrzw-RPCにて、データベースにシャーディングを施して運用する方法を紹介した。シャーディングしていいならどんなデータベース実装でも並列化するので、ある意味でチートなのかもしれないが、実際に役立つのだから仕方ない。並列処理性能は上がるし、データベース全体をブロックするはず管理系コマンドも体感的にほとんどブロックさせずに実行できるし、それでいて順序アクセス機能は失われないので、めっちゃ良いことが多い。ぜひ使ってみてほしいところだ。

ここまでの開発で、データベースサービスとしての実用的な実装はできている。普通にオンライン系システムのバックエンドとして使えるレベルになっていると思う。あとは、レプリケーションかな。そこが一番大変なんだけど。