ハッシュデータベースをオンラインで再構築する方法について検討してみる。オンラインというのはすなわちサービスを提供しながら、ダウンタイムを発生させずに行う処理である。
そもそもなぜデータベースの再構築をせねばならないかというと、データベースファイルの空間効率が更新を繰り返すにしたがって悪化していくからである。インプレース更新の場合、既存のレコードの値を変更する際には同じ領域に書き込みを行う。新しい値が古い値より短い場合、差分の領域はパディングになる。パディングは実効データとはみなされないので、その存在自体が空間効率を悪化させる。新しい値が古い値より長い場合、同じ領域には書き込めないので、ファイルの末尾に新しい領域を確保して書き込みを行った上で、もとの領域はフリーブロックになる。フリーブロックは再利用されるが、完全に同じ大きさのレコードが嵌め込まれるわけではないため、やはりパディングが生じる。こうしてフリーブロックやパディングが蓄積されていき、空間効率は少しずつ悪化していく。ファイルシステムにおけるフラグメントと同じ構造だ。データベースを再構築して空間効率を理想化する操作は、ファイルシステムにおけるデフラグと同じことだ。追記更新の場合はいわずもがな、既存レコードの全ての更新操作が空間効率の悪化につながるので、より高い頻度での再構築が求められることになる。
ちなみにKCでは、データベースが更新される度に別の場所で少しずつレコードの詰め直しを行う「インクリメンタルデフラグ」なる機能を持たせていたのだが、性能や並列性や永続性への悪影響がそこそこあったので、今回は廃止する。追記更新のデータベースではインクリメンタルデフラグは実現できないこともある。それよりは、オンラインでデータベースの再構築ができた方が便利だ。
オンライン処理というのは、ユーザからのリクエストが送られたらそれに対して即座に（もしくはなる早で）レスポンスを返す仕組みのことだ。例えばログイン処理がそれにあたる。ユーザIDと認証情報のデータベースを参照して、認証情報が一致すればログインを許可するわけだが、その応答は即座でなければならない。その対極であるオフライン処理もしくはバッチ処理と呼ばれるやり方は、複数のリクエストを記録しておいて一気に処理して、その結果が出来次第に報告するという仕組みだ。統計をとったり機械学習のトレーニングをしたりといったユースケースではバッチ処理の方が向いていて、その方がスループットが高くできる。話をオンライン処理に戻すと、リクエストに対するレスポンスにはタイムアウトが設定されるのが通常で、ユースケースによって0.1秒なり5秒なり30秒なりに応答することが求められる。一定割合以上のリクエストがタイムアウトするとサービスのダウンタイムとみなされ、ユーザは怒り狂い、運用の責任者は始末書を書く羽目になる。24時間稼働のオンラインシステムで使われるデータベースにおいて、リクエストのタイムアウトを起こさずに再構築するにはどうすればよいか。それが今回の課題だ。
データベースの再構築は、基本的には以下の手順で行う。
- 既存のデータベースファイルの状態を見て、新しいデータベースのチューニングを決める。
- 既存のデータベースファイルの全てのレコードを走査して、新しいデータベースファイルに記録する。
- 古いデータベースファイルを新しいデータベースファイルに置き換える。
１のチューニングに関しては、ハッシュデータベースの場合にはバケット数くらいしかパラメータがないので単純だ。既存のデータベースのレコード数の2倍くらいを新しいデータベースのバケット数に設定すればよい。２のコピー操作はちょっと厄介だ。レコードをひとつずつコピーしている間にも、既存のデータベースは更新され続けるからだ。ユーザからの更新要求を止めずに処理し続けつつも、新旧両者の一貫性を保たねばならない。３に関しても単純だ。renameシステムコールでファイルを置き換えるだけでアトミック性は確保できる。スレッドの排他制御に関しては慎重に検討する必要がある。
今回の実装における戦略はこんな感じだ。
- あるスレッドが再構築を始めたら、メタデータのミューテクスをロックして、他のスレッドは同時に再構築等のメタな操作ができないようにする。
- 一時ファイルとして新しいデータベースファイルを作り、バケット数などに相応のチューニングをする。
- インプレース更新のデータベースは追記更新モードに切り替える。
- 内部イテレータを使って既存の全てのレコードを新しいデータベースに登録する。この内部イテレータは他の更新スレッドをブロックしない。
- 上記のコピー操作を行なっている間になされた既存データベースへの更新を新しいデータベースに反映させる。
- 上記の反映操作を行なっている間になされた既存データベースへの更新を新しいデータベースに反映させる。
- 反映操作の量が十分に少なくなるまで上記を繰り返す。
- テーブルロックをかけ、全ての更新スレッドを止めた状態で、最後の反映操作を行い、その後にrenameで新旧ファイルを置き換える。
- テーブルロックを解除する。
- メタデータロックを解除する。
要点は、インプレース更新のデータベースを追記更新モードに切り替えるところだ。今回の実装で追記更新をサポートし、しかもそれを同じデータ構造で実現しているところがここで生きてくる。追記更新のデータベースをインプレース更新のデータベースとみなすことはできないが、インプレース更新のデータベースを追記更新のデータベースとみなすことはできる。追記更新のデータベースは同じレコードのデータが重複して存在して、連結リストを辿らないとどれが最新かわからないので、インプレース更新のイテレータが破綻してしまう。一方で、インプレース更新のデータ構造の特徴である無効化されたレコードは連結リストからは除外されているので、追記更新のデータベースとみなしても問題ない。なお、一度でも追記モードで更新を行ったデータベースはもうインプレース更新のデータベースには戻れない。
追記更新のデータベースが空のデータベースに対する変更操作ログの集合とみなせるということは前回述べた。そして最初から任意の時点までそのログを再生することでその時点でのデータベースの状態を復元する「タイムマシン」機能があることも述べた。さらに言うと、この再生操作は、「最初から」でなくても良い。既存のレコードのコピーを始めた時点でのファイルサイズを知っていれば、そこから先に増えた操作ログのみを新しいデータベースに対して再生することで、既存レコードのコピー中に行われた更新操作だけを新しいデータベースに適用することができる。そしてその再生操作を行う直前にも既存データベースのファイルサイズを取得しておけば、ログ再生による反映操作の間に行われた更新だけをまた再生することができる。これを繰り返していけばいずれ再生しなければいけない操作ログの量は減っていき、それが一定以下になれば、許容時間内に処理を終えられるようになる。そうなった時にテーブルロックをして、ファイルの置き換えを完了させる。
テーブルロックの確保はハッシュロックの記事で述べたLockAllメソッドで行う。そしてファイルの置き換えが終わった後にロックのリハッシュ操作を行ってからUnlockAllメソッドでテーブルロックを解除すれば、全ては通常の状態に戻る。
再構築中に受け取る更新リクエストの量が多すぎていつまで経っても反映が追いつかないリスクがある。これはもう、いかんともしがたい。これはどんな再構築手法を使おうとも、更新リクエストをブロックさせる以外には解法がない。再構築処理が通常処理をブロックせずに行えるのは、システムの現状の負荷が許容負荷の半分以下であるという条件がつくということだ。それを前提として、「反映操作中に受け取った更新を反映させる」のループは定数回で抜けるようにする。その後は更新リクエストをブロックした状態で再構築処理を進めることになる。シャーディングすればこの問題は緩和できるけど。
既存データベースの全てのレコードを走査するための内部イテレータについて、もう少し掘り下げて検討してみよう。インプレース更新のデータベースでは、無効マークの活用で各レコードのデータのユニーク性が保証されているので、ファイルを前から読んでいくだけで全てのレコードを1度ずつ読み込める。この操作はシーケンシャルアクセスなので効率的だ。一方で追記更新のデータベースでは、各レコードのデータのユニーク性は保証されていないので、各レコードの最新のデータを知るには、バケットから連結リストを辿ることが必要になる。これはランダムアクセスなので遅い。データベースの再構築のような大規模の処理をランダムアクセスでやるのはちょっと遅すぎて厳しい。そこで、別の方法が求められる。データベースファイルを後ろから読めばいいのだ。追記更新ではフリーブロックプールを利用しないので、古い情報より新しい情報は常に後ろにあることが保証されている。インプレース更新のデータベースを追記更新モードに切り替えた場合でも、その時点ではユニーク性が保証されているので、その後の更新を追記更新で行えば、同一レコードの最新情報が後ろにあるという保証ができる。
データベースファイル内のレコード群は全体が単方向連結リストであるとみなせる。データベースファイル内における各レコードは自分のサイズを知っているので、そのサイズ分だけ読み込み位置を進めれば、次のレコードが読み込める。ただし、これは単方向であり、前のレコードに戻ることはできない。つまり後ろから順にレコードを読むことはできない。なので、まず前から順にレコードを読んでいって、各レコードのオフセットを別ファイルに記録しておく。それは固定長の数値が並んでいるだけのファイルなので、後ろから読んでいける。オフセットファイルの後から要素を一つ読んだらそれに基づいてデータベースファイル内の要素を読んでコピー操作を行えばよい。オフセットファイルの作成は前からのシーケンシャルアクセスで、コピー操作は後ろからのシーケンシャルアクセスなので、少々冗長ではあるが、ランダムアクセスは発生しない。ファイルへのランダムアクセスは、ファイル全体がファイルシステムのキャッシュに乗らない規模だと、ストレージのハードウェアへのランダムアクセスが発生し、それはHDDでもSSDでも激烈に遅い。シーケンシャルアクセス2回の方が遥かにマシなのだ。レコードのフォーマットを双方向リンクリストに改めればいいと思うかもしれない。でもそうすると更新時に直前のレコードをロックしないといけなくなるから並列性が確保できない。前後関係の一貫性は並列化の最大の敵である。各レコードの末尾に自らのサイズを固定長で書くという案もあるが、フットプリントが4バイト増えるのはあまり嬉しくない。てことで、悩ましいが、再構築にシーケンシャルアクセス2回を要するのは悪くない落とし所だと思う。ややこしい話だが、インプレース更新であったデータベースからの初回のコピーだけは前から読むイテレータが使えるので、シーケンシャルアクセス1回で済む。その操作をしてる間に受け付けた更新は追記更新として記録されるので、それは後ろから読まねばならない。
既存のデータベースファイルを後ろから読むとして、個々の操作をどう処理するかを定義しておこう。まず前提として削除操作が最新状態であるレコードの集合を記録する別の一時データベースファイルを作る。その上で、「Set」操作を読み込んだ場合、既に削除済みデータベースにそのレコードがなければ、新しいデータベースにレコードを追加する。新しいデーターベースに既にそのレコードがあるなら、何もしない「Remove」操作を読み込んだ場合、削除済みデータベースにそのレコードを登録する。無効マークである「No-operation」操作を読み込んだ場合には、何もしない。こうすると、同一レコードのデータの重複を排除して最新状態のみにした上で、新しいデータベースの内容を既存のデータベースの内容と同期できる。
追記更新のデータベースの同期処理は、よくあるデータベースサーバのレプリケーション機構と同じ構造である。空間効率の改善を目的とする場合には後ろから読まざるを得ないが、レプリケーションを目的とする場合には前から順に読んでいっても問題ない。これを応用してレプリケーション機能付きデータベースサービスが実装できるはずだ。ただ、デュアルマスター構成を考えるなら、更新ログの中に発信源のデータベースIDを入れないといけない。しかし、機能の肥大化は避けたいので、今は考えないものとする。
