Transactional write の調査: MySQL 編その2

前回は主に redo log を調査した。 InnoDB ではいわゆる redo log は MTR によって実装されていることがわかった。

今回はロールバック周りを見ていく。

redo log があれば ACID を実装することが可能なのは SQLite で調べたとおりだが、InnoDB は MVCC なので、 redo log だけだと最新のページを取得するのにコストが大きい。 そのため InnoDB はページは最新の状態に更新し、古いページを rollback segment に退避するという実装をしている。 rollback はこの rollback segment を使って実行される。

MySQL のドキュメントでは undo log が rollback segment に格納されるとあるが、 ここで言う log というのは MTR のように確実に sync されるわけではない。 つまり rollback segment はプロセスがクラッシュした際に破壊される恐れがある。

ではどのように rollback segment を保護しているのか。 InnoDBMTR の中に rollback segment への書き込み自体を記録することで再構築できるようにしている。

InnoDB ではプロセスクラッシュ時のリカバリは次のように行われる。

  1. redo log の再生

    これにより、データベースファイルのページが最新の状態に復旧される。また rollback segment が復旧される。

  2. 未 commit のトランザクションの rollback

    1 で復旧された rollback segment を使って rollback を行う。

Transactional write の調査: MySQL 編

引き続き trx write の実装について調べていく。 今回は MySQL を見ている。

MySQL はめちゃくちゃたくさんログを書いているしどれが何をしているのかというのは初見ではわかりにくい。 実際にトランザクションに関係するログは、innodb_log_* 系で設定する redo log と、double write buffer、undo log である。

ここでは主に redo について述べていく。 MySQLredo log の実態は mini-transaction (mtr) と呼ばれる構造体からなっている。 mtrSQL レベルのトランザクションではなく、内部的に実行するデータ変更操作を記録するためのもののようだ。

mtr0types.h ではどういう操作を記録しているかが enum として定義されている。

https://github.com/mysql/mysql-server/blob/5.7/storage/innobase/include/mtr0types.h#L54

例えば MLOG_REC_INSERT を見てみると、page_cur_insert_rec_write_log で使われている。 この関数の末尾では mtr の内部バッファにレコードをコピーしている。

https://github.com/mysql/mysql-server/blob/5.7/storage/innobase/page/page0cur.cc#L1128

ということで、mtr はページレベルではなく、内部操作に必要十分なデータのみを記録しているようだ。

実際の mtr のディスクへの書き出しは、様々なタイミングで行われているが、 SQL レベルの commit では innodb_flush_log_at_trx_commit が 1 ならば強制的に sync される。 また MySQL 起動時に定期的に書き出すスレッドが作成されている。

mtr は論理レベルのログなので、パーシャルライトが起こりうる。 これを防止するための機構が double write buffer である。

さて、mtrSQL レベルトランザクションの関係だが、雑に見た感じだと、 SQL の COMMIT が実行されると undo log がパージされることで rollback されないようにしているように見えた。

Transactional write の調査: SQLite wal 編

今回は、SQLite の wal モードについて調べた。

こちらもドキュメントが豊富で、以下の2つが参考になる。

wal モードは、redo log のみを使って永続化を行っている。 書き込みの時に以下のような動作を行う。

  • wal に frame を書き込む。COMMIT 時にはそれを示す値をヘッダフィールドに書く。
  • COMMIT 時に frame 数が規定値(デフォルトでは1000)を超えるか、自分以外のコネクションがいない時にデータベースを閉じる時に checkpoint を行う。

wal のレコードである frame は frame 固有のヘッダと、書き込むページデータからなる。 frame ヘッダには wal ヘッダに含まれる salt と、 wal ヘッダと frame ヘッダと自分以下の全 frame からなる checksum が書かれている。

frame は salt や checksum が正しいもののみ使用可能とみなされる。 wal は連続する frame を再生する必要があるので、連続した frame が全て壊れていないことを保証する必要がある。 そのため各 frame は自身の checksum だけでなく、これまでの frame を含めた checksum をつけているのだと思われる。

checkpoint 作業は wal に含まれる frame を適用することになるが、wal モードでは undo は行わない。 そのため、並行して走っている reader が見ているページを上書きしてはならない。 どこまで適用可能かという値は wal index に read mark として保存されている。

checkpoint が終われば wal header の checkpoint sequence や salt を更新する。 この更新で古い frame が適用されることを防ぐ。 また、他のコネクションがなければ wal の肥大化を防ぐために wal をリセットする。

wal モードでは checkpoint が起こるまでデータベースファイルのページが更新されない。 そのため reader は最新のページを wal から取得する必要があるが、当然スキャンを行うのはパフォーマンスが良くない。 これを解決するために、wal index が存在している。

wal index は標準の実装では memory mapped file を使っている。 index はクラッシュ時には再構築されるため、構造はドキュメントには詳しいことは記載されていない。

wal.c には WalIndexHdrWalCkptInfo 構造体が定義されていてなんとなく使い方がわかる。 index はハッシュテーブルを使っていて、キーに素数をかけてスロット数で割るという単純なものを使っている。 衝突時は前回の結果をインクリメントして同じアルゴリズムを適用する。

Transactional write の調査: SQLite rollback journal 編

プログラミングをしていると、電源断などの障害時でも不整合が起こらないようにデータを保存したいという要求がしばしばある。 通常こういう要求は DBMS やライブラリなどで担保することになるわけであるが、データ自体が DBMS に収まらない場合、 2 phase commit が必要になったり、システムプログラミングをしていると DBMS を使えなかったりする。 そんなときにデータを正しく書く方法が知りたくなったので、有名所の実装を調べていくことにする。

ここでは電源断などを考えることにする。 このときデータを守る方法としては、write ahead logging や rollback journal などの方法がある。 (論文などをサーベイしていないのでもっといろいろな方法があるかもしれない) これらの方法は、理屈としては難しいものではないが、ディスクデバイスにどのような仮定を持つかによって実装が難しいものになる。

例えば WAL の場合、1セクタ内に複数レコード r1, r2 を書いているとして、r1 を書き終えて、r2 を書いている際に電源断が起こったとする。 このとき、ディスクデバイスは、r1 を残してくれるのだろうか?

以降では、transactional write という用語を、電源断時に commit or rollback して整合性を保った状態に保つことができる write ということにする。 (この用語はもっと適したものがあるかもしれない)

今回は、ドキュメントが豊富な SQLite の rollback journal について調べてみる。

rollback journal については、Atomic Commit In SQLiteに詳しく記述されている。

SQLite は、先ず書き込み対象のページを rollback journal として書き出して、その後にデータベースファイルを書き換え、 最後に journal を削除する。

SQLite はこの書き込みに対してセクタへの書き込みはアトミックではないと思っている。

SQLite has traditionally assumed that a sector write is not atomic.

しかし、セクタ内への書き込みは linear だと仮定していて、必ず書き込みは先頭または末尾から書き始めて、途中で電源が起きた場合、その地点までは書き込まれ、それ以降は変更されないという仮定のようだ。

また新しいバージョンでは SQLiteファイルシステム抽象化レイヤの VFS から書き込みを atomic であると主張することもできる。

IO でどのような仮定が使えるかというのは sqlite3.h で定義されている。 ただし unix 向けの os_unix.c では、SQLITE_IOCAP_POWERSAFE_OVERWRITESQLITE_IOCAP_BATCH_ATOMIC が基本的に使われる。 (android 環境では ATOMIC 系もサポートされているようだ)

#define SQLITE_IOCAP_ATOMIC                 0x00000001
#define SQLITE_IOCAP_ATOMIC512              0x00000002
#define SQLITE_IOCAP_ATOMIC1K               0x00000004
#define SQLITE_IOCAP_ATOMIC2K               0x00000008
#define SQLITE_IOCAP_ATOMIC4K               0x00000010
#define SQLITE_IOCAP_ATOMIC8K               0x00000020
#define SQLITE_IOCAP_ATOMIC16K              0x00000040
#define SQLITE_IOCAP_ATOMIC32K              0x00000080
#define SQLITE_IOCAP_ATOMIC64K              0x00000100
#define SQLITE_IOCAP_SAFE_APPEND            0x00000200
#define SQLITE_IOCAP_SEQUENTIAL             0x00000400
#define SQLITE_IOCAP_UNDELETABLE_WHEN_OPEN  0x00000800
#define SQLITE_IOCAP_POWERSAFE_OVERWRITE    0x00001000
#define SQLITE_IOCAP_IMMUTABLE              0x00002000
#define SQLITE_IOCAP_BATCH_ATOMIC           0x00004000

SQLITE_IOCAP_POWERSAFE_OVERWRITE は先程の linear の仮定を示している。 SQLITE_IOCAP_BATCH_ATOMIC は f2fs の atomic write api を使う方法で、 なんとこれを使うと、journal なしで直接データベースファイルを更新する。 ファイルシステム側で transacional write を担保しているわけだ。

さて、先の journal の作り方だと、journal を作っている最中に電源断を起こすと不正な journal ができてしまう。 当然そのような journal を使ってしまうとデータベースが破損してしまう。 これを防ぐために、journal は最初にヘッダにレコード数を0と記録する。 次にレコードを書き終えた後、ヘッダを更新する。

レコード数を記録するフィールドはヘッダ先頭の magic の直後に位置していて、 linear の仮定からレコード数を書き換えている間に電源断が起きても、破損に気づくことができる。 (しかしレコード数は4バイトなので中途半端に書かれていた時に困らないか?)

この動作はファイルシステムが先ずファイルサイズを更新してからデータを書くということを仮定している。 昨今のジャーナリングファイルシステムだとデータを書いてからメタデータを更新するので、自前でヘッダにレコード数を書かなくても良い。 このために SQLITE_IOCAP_SAFE_APPEND を使うことができる。

以上が SQLite rollback journal の動作となる。

64ZiB ほしい!

SCSI プロトコルでは、デバイスの容量を取得するために、READ CAPACITY(10) や READ CAPACITY(16) を提供している。 これらのコマンドは、Logical Block Address(LBA) とロジカルブロックのバイト数でのサイズを返すことができる。 (10) と (16) の違いは、それぞれ返せる LBA の最大サイズが、4バイトか8バイトかの違いである。

さて Linux では最大 4096 バイトのブロックサイズに対応している。 そのため、READ CAPACITY(16) を使えば、最大で 0xffffffffffffffff000 バイト、すなわち 64ZiB までのデバイスカーネルに提供することができる。

TCMU では SCSI コマンドはパススルーでユーザーランドに渡されてくるのでこのようなありえないぐらい大きなサイズのデバイスを作ることができる。

雑に実装して見たところ、カーネルはめでたく 64ZiB のデバイスを認識してくれた。

[ 5857.003525] sd 4:0:0:0: [sdb] 18446744073709551615 4096-byte logical blocks: (75.6 ZB/64.0 ZiB)
[ 5857.004058] sd 4:0:0:0: [sdb] Write Protect is off
[ 5857.004060] sd 4:0:0:0: [sdb] Mode Sense: 17 00 10 00
[ 5857.004833] sd 4:0:0:0: [sdb] Write cache: enabled, read cache: enabled, supports DPO and FUA
[ 5857.011876] sd 4:0:0:0: [sdb] Attached SCSI disk

しかしながら lsblk でみると、16 EiB のブロックデバイスとして認識される。

$ lsblk | grep sdb                                                                                                                                                         
sdb              8:16   0    16E  0 disk

これは Linuxシステムコールなどが loff_t を使っており、64bit 環境ではそのサイズに制限されるためだ。 したがって残念ながら、通常の使い方では 64ZiB のブロックデバイスをユーザーランドに提供することはできない。

VirtIO と TCMU

VirtIO は準仮想化のフレームワークで、ゲストOSで特別なハードウェアを用意して VMM と直に通信する方法を提供してくれる。 実装的には virtqueue というメモリ空間をゲストと VMM で共有することでデータ送受信を可能にしているらしい。

ここまでは良いのだが、virtqueue への読み書きはあくまでメモリ上の操作なので、ゲスト、VMM 双方で処理可能になったか知る必要がある。 現状の linux カーネルでは drivers/virtio/virtio_pci_*.cdrivers/virtio/virtio_mmio.c で実装されているらしい。

前者は PCI サブシステムを利用していて、通知は io 命令でやっているように見えた。 後者は ARM のために用意されたようで特定のメモリアドレスへの読み書きを実行することで通知を行うらしい。

いずれにしても VMM が特権命令、あるいは特別なメモリアドレスをトラップすることで通知を認識しているようだ。

さて、巨視的視点に立つと、VirtIO、特にブロックデバイスの実装である virtio_blk と TCMU は、 カーネルに対してユーザーランドからブロックデバイスを提供するときに、 メモリ空間を共有しその空間への更新の通知のみを特別な方法で行うという点で類似のアーキテクチャを取っている。

TCMU は LIO のバックエンドのため、フロントエンドがないと直接はユーザープロセスの IO を扱うことができない。 また、TCMU をゲスト OS で利用する場合、バックエンドのユーザーランドプロセスは結局 VirtIO などを通じて VMM で IO を処理しなくてはならない。

一方、virtio_blk は直接デバイスを提供しているのでユーザーランド(VMM)へのオーバーヘッドは vmenter/vmexit がだけになる。

このように考えると、ゲストにストレージを提供するのであれば VMM で実装してやるのがいいのかなと思った。

tcmu と IO スケジューラ

前回、tcmu でブロックデバイスを作ってみたが、思ったより性能が出なかった。 IO completion が遅いのだと思ってスレッド化してみたが、もとより少々遅くなってしまった。

ところがふと、IO スケジューラを確認してみると、cfq スケジューラを使っていることがわかった。 これを deadline に変えてみると性能がかなり上がった。

手元の 4.13 では NBD はデフォルトで blk-mq スケジューラを利用している。 tcmu も blk-mq でベンチマークを取るのがフェアだと思ったので試してみた。

tcmu を提供する lio も scsi ドライバの一種なので、blk-mq を有効にするにはカーネルの起動パラメータに scsi_mod.use_blk_mq=1 をつける必要がある。

この状態で試すと、以下のようになった。

# of fio threads read write
2 270MB/s 270MB/s
4 276MB/s 276MB/s
8 242MB/s 242MB/s

一方、NBD は以下のようになった。

# of fio threads read write
2 282MB/s 282MB/s
4 237MB/s 237MB/s
8 194MB/s 194MB/s

ということでいい感じに性能が出るようになる上に、fio のスレッド数を増やしても割と性能が安定している。 雑なベンチマークではあるが、ようやく tcmu の良いところが見えた。