豪鬼メモ

一瞬千撃

DBサービスを作ろう その8 レプリケーションを踏まえた更新ログの要件

データベースの堅牢性を高めるために、データベース本体とは別に更新内容を保存する、更新ログという手法がある。さらに、更新ログを逐次別サーバに転送して適用すれば、レプリケーションが成立する。この記事では、レプリケーションにも使える更新ログの要件についてまとめる。


Kyoto Tycoonにはレプリケーション機能がある。詳しくはKyoto Tycoon導入ガイドをご覧いただきたい。基本的にはこれと同じ機能をTkrzw-RPCにも実装する。RDBMSの用語で言えば、行レベル更新ログということになる。

更新ログとして記録すべき内容は大きく2種類に分けて考えられる。便宜上、外的ログと内的ログと呼ぼう。外的ログとは、サービスレベルのメソッドとそのパラメータを記録するものだ。例えば、"hoge"レコードの値を1増やすというIncrementメソッドが実行されたとすると、外的ログには「Increment("hoge", 1)」などというレコードを記録する。一方で内的ログは、メソッドを実行した結果としてのデータベース内のレコードの最新状態を記録するものだ。Incrementメソッドの結果として"hoge"レコードの値が"8"になったとすると、「set("hoge", "8")」などというデータを記録する。

外的ログの利点は、バックエンドのデータベース実装やその内容に依存せずに、その利用者であるサーバプログラムの機能だけで実装できることである。欠点は、冪等(べきとう=Idempotent)ではないことだ。冪等とは、同じ操作を何度適用しても同じ結果が得られることだが、上述のIncrementを複数回適用すると結果が変わるのは明らかであり、つまりそれは冪等な操作ではない。冪等でない場合、二重には適用できない。よって、更新ログを適用する際に、どこからどこまで適用するのかを厳密に判断せねばならない。タイムスタンプで管理するにしても、OS上の時間は戻ることがあるので、厳密に管理するのは難しいのだ。

内的ログの利点と欠点は外的ログのそれらを反転したものだ。バックエンドのデータベースの中に更新ログの取得機能を注入して実装する必要があるというのが欠点である。一方で、更新ログの内容が冪等になるので、時間を遡って適用しても問題ない。データベースは整合性が命で、冪等性はその前提となる重要な性質だ。よって、できるなら内的ログを採用すべきだ。そして、現在のところバックエンドも私自身が書いているわけなので、内的ログの実装は可能である。Kyoto Tycoonも内的ログだし、Tkrzw-RPCも内的ログを採用する。

更新ログの即時転送(レプリケーション)を実装しなくても、マシン単体で堅牢性を高めるのに更新ログは役立つ。データベースファイルが壊れた場合に、バックアップファイルだけから復元すると、バックアップを作成してから現在までの更新が失われてしまう。更新ログを取得しておけば、バックアップファイルに更新ログを適用して、最新状態に復元できるのだ。

内的ログの更新ログを実装することを決意した。となると、Tkrzwの全7つのデータベースクラスに内的ログの実装を注入する必要がある。これは正直だるい。しかし、更新ログを記録する機能はRPCで使う場合以外でも堅牢性を高めるのに有用なので、Tkrzw本体の機能として実装しておいて損はないだろう。都合の良いことに、各データベース実装では、任意のコールバックでレコードデータの参照や更新ができるように柔軟性を持たせているので、それを再利用すればよい。つまり、「更新ロガー」のコールバックを注入しておいて、更新用のコールバックに渡したパラメータと返されたデータをそのまま更新ロガーのコールバックにも渡せば良い。更新用のコールバックのインターフェイスは以下のクラスである。

class RecordProcessor {
 public:
  // 既存のレコードがある場合に呼ばれる。
  // 返した値が新たな値になる。REMOVEという特殊値を返すと、レコードが消える。
  std::string_view ProcessFull(std::string_view key, std::string_view value);
  // 既存のレコードがない場合に呼ばれる。戻り値の意味は同じ。
  std::string_view ProcessEmpty(std::string_view key);
};

コールバックの戻り値を保存するのだが、当然パラメータのキーも保存する。冪等を前提とすると、パラメータの値は保存しなくていよい。また、全レコードを消すClear操作専用のコールバックも用意する。

class UpdateLogger {
 public:
  // レコードの新しい値か返された場合に呼ばれる。
  Status WriteSet(std::string_view key, std::string_view value);
  // 特殊値Removeが返された場合に呼ばれる。
  Status WriteRemove(std::string_view key);
  // Clearメソッドが呼ばれた場合に呼ばれる。
  Status WriteClear();
};

このようなDependency Injection方式にしておくことで、テストも簡単になるし、Tkrzw-RPCの更新ログの具体的な形式をTkrzwのデータベースが知る必要がなくなる。さらに、Tkrzw以外のデータベースにも、UpdateLoggerが注入できるラッパーを書けば、対応できるようになる。

Writeが呼ばれた際に記録するデータの形式を設計する。以下の属性をシリアライズしたデータを保存することになるだろう。

  • タイムスタンプ
  • オリジンサーバID(サーバ固有の値)
  • データベースID(サーバ上の何番目のデータベースか)
  • 操作タイプ(SetかRemoveかClear)
  • キー(サイズとデータ)
  • 値(サイズとデータ)

全てのサーバにはIDを割り当てておく。オリジンサーバIDとは、該当の更新操作をクライアントから受け付けたサーバのIDである。これをもたせておくと、デュアルマスタなどの、循環構造のレプリケーションが可能になる。レプリケーション時に受け取った更新ログのオリジンサーバIDが自分と同じだった場合に無視することで、無限ループを断ち切ることができる。実際には、転送量を減らすために、更新ログの送信時に相手のサーバIDを調べて送信を省略することになる。

Tkrzw-RPCのサーバは複数のデータベースを同時に運用できるので、そのIDが必要になる。0を起点とするインデックスだ。レプリケーションに参加する全てのサーバは同じ構成でデータベースを運用していることを前提とする。とはいえ、実際にはチューイングを変えてもよいし、データベースクラスすら変えてもよい。アーカイブ専用のスレーブでは圧縮を有効にするとかもできる。

操作タイプはSetかRemoveかClearである。Setの場合、キーと値を後続に取る。Removeの場合、キーのみを後続に取る。Clearの場合、後続には何も取らない。その他の操作タイプも追って追加するかもしれないが、当面はこの3種で良いだろう。

シリアライズをどうするかも考える。プロトコルバッファでシリアライズするのが楽なのだが、ここでは空間効率を優先して独自形式を採用する。以下のデータを並べる。

  • マジックデータ : 固定長1バイト。0xFF。
  • 操作タイプ : 固定長1バイト。0xA1=Set、0xA2=Remove、0xA3=Clear。
  • タイムスタンプ : 固定長5バイト。UNIX時間のセンチ秒。
  • オリジンサーバID : バイトデルタエンコード。典型的には1バイト。
  • データベースID : バイトデルタエンコード。典型的には1バイト。
  • キー : バイトデルタエンコードのサイズと、任意のバイト列
  • 値 : バイトデルタエンコードのサイズと、任意のバイト列
  • チェックサム : 固定長1バイト。

マジックデータと操作タイプの組み合わせは、万が一データが壊れた場合の検出に有用だ。末尾に置くチェックサムには、251を法とするチェックサムを使い、最後に1を足す。チェックサムのおかげでランダムノイズが確率的に検出できるのと、その変域が1以上であることで、書き込み途中で力尽きたログが確実に検出できる。更新ログが何らかの理由で途中で壊れていた場合、それ以降全てを無視するのではなく、次のレコードまで読み飛ばして処理を続けたくなるが、その際の誤検出の確率は、マジックデータで1/256になり、操作タイプで3/256になり、チェックサムで1/251になるので、0.0000182%だ。実際にはそれを次のレコードが見つかるまでのバイト数だけ行うので、平均256バイトくらいだとすると、0.0046%か。ファイルの末尾以外では、そうして発見された次のレコードの候補の次のレコードも同様に検査できるので、実質の誤検出率はゼロと言って良い。

タイムスタンプが5バイトなのは、4バイトでUNIX時間を表すと2106年にオーバーフローするからである。5バイトにすれば36812年まで問題を先送りにできる。さすがにそれはオーバースペックなので、100で割ったセンチ秒で扱って、トレーサビリティを向上させる。2318年が上限になるが、現行システムの寿命としては十分だろう。

ところで、人間と機械の両方にとって扱いやすいデータ系列としては、UNIX時間を基準にするのが現実的だが、UNIX時間が戻る可能性には注意を要する。手動もしくはITP等による自動調整でシステムの時間は戻る。閏秒の際には同じ時刻が2秒続くが、その間に秒未満の情報がどうなるかは実装依存だ。更新ログのタイムスタンプは常に増加し続けるか、少なくとも減らないことが必要だが、UNIX時間をそのまま記録するとそれに違反することになる。よって、更新ログを記録する際には、直前に使ったタイムスタンプと現在取得したタイムスタンプの大きい方を使うことになる。つまり、時間が戻った場合には、同じタイムスタンプのログが連続することになる。時間の逆行が大きい場合、何百万個も続くかもしれない。それらはタイムスタンプ上では区別できないが、更新が発生した順序と記録の順序に一貫性がありさえすれば、問題ない。更新ログを適用する際には、時間の逆行も考えて十分に猶予を持ったところから始めればよいのだ。冪等性がここで重要となる。

生成した更新ログをどうやってファイルに書き込むか、ローテーションはどうするか、またその更新を読み出し側にどうやって通知するかなどの実装の詳細は、レプリケーションの実装時に追って詰める。とりあえず今は、更新ログの仕様に問題がないかだけを確認したい。

更新ログを読み込むには、おそらくローテーションによって複数に分割された更新ログのファイルの接頭辞を指定するとともに、オプションとして、起点となるタイムスタンプとサーバIDを指定する。読み込んだ更新ログを適用する際には、データベースIDを使って対象のデータベースを特定した上で、ログの個々のレコードを読み込んで、その操作タイプに応じてSet、Remove、Clearを呼べば良い。バックアップファイルに更新ログを適用するユーティリティコマンドは以下のように実行するだろう。

$ ls tkrzw-ulog.*
casket-ulog.1631289371 casket-ulog.1631292834 casket-ulog.1631219232

$ tkrzw_dbm_util --db_id 0 --since 1631209232 casket-backup-20210819.tkh casket-ulog
set=2342342, remove=54829, elapsed_time=18.752

Tkrzw-RPCで、他のサーバ側から更新ログを取得するレプリケーション機能を有効にしつつ、かつ自分も更新ログを記録するには、以下のように設定するのかな。詳細は変わると思うけど。

$ tkrzw_server --server_id 1 --replication "master=host01:1978,since=1631209232" \
  --ulog_prefix casket-ulog  --ulog_max_size 100Mi \
  "casket.tkh#num_buckets=10M"

ところで、サーバの普通のアクセスログにはローテーション機能をつけないのに、更新ログにはローテーション機能をつけるというのは、一貫性に欠ける態度だと思われるかもしれない。というか、私も思う。しかし、更新ログは、ログという名前は付いているが、実際にはデータベースの一部なので、ローテーションまで面倒を見てやらないとどうしようもない。そして、普通のログは標準出力などのファイル以外の出力先も想定しないといけないので、そもそもローテーションできるとは限らない。標準出力をローテーションしたファイルに書き込むApacheのrotatelogとかを組み合わせるかもしれないし、標準出力でできる事には余計なことをしない方がUNIX的なのだ。


まとめ。データベースの更新ログの仕様を考えた。更新ログがあると、バックアップファイルからの障害復旧時に最新状態まで復元できるという利点がある。更新ログを他のサーバに転送すれば、レプリケーションも実現できる。Kyoto CabinetやKyoto Tycoonでも実装した機能なので、この設計で問題ないだろう。