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 の良いところが見えた。

tcmu でブロックデバイスを作る

tcmu は LIO のバックエンドの一つで、UIO を使って SCSI をコマンドをユーザーランドと通信する。 ドキュメントがかなり詳しく書いているのでわかりやすい。 https://www.kernel.org/doc/Documentation/target/tcmu-design.txt

SCSI コマンドやデータのやり取りは、UIO デバイスmmap したメモリ領域に書き込むことで行う。 このメモリ領域は、メタデータ、コマンドキュー、データ領域にわけられている。 キューにコマンドがエンキューされたことは、UIO デバイスを read または poll することで検知できる。 またコマンドを処理したことをカーネルに伝えるには、UIO デバイスに 4 byte write してやることで実現する。

NBD と違い、SCSI コマンドを解釈する必要があるので実装は面倒くさいが、 カーネルとの通信は mmap した領域に書き込むだけなのでオーバーヘッドが少ないことが予想される。

いつものように rust でメモリバックエンドのデバイスを実装してみた。

github.com

SCSI コマンドは linux がデバイスを動かせる最低限しか実装していない。 それでもかなり面倒くさかったのでデバイスを作る開発者には頭が下がる。

さて、fio でのベンチマークは以下となる。 バージョンやパラメータが以前と異なるが、まあ大きく問題ではないはず。

rw: (g=0): rw=randrw, bs=(R) 4096B-4096B, (W) 4096B-4096B, (T) 4096B-4096B, ioengine=libaio, iodepth=64
...
fio-3.1
Starting 3 processes
rw: Laying out IO files (8 files / total 250MiB)
rw: Laying out IO files (8 files / total 250MiB)
rw: Laying out IO files (8 files / total 250MiB)
Jobs: 3 (f=24): [m(3)][100.0%][r=166MiB/s,w=167MiB/s][r=42.4k,w=42.7k IOPS][eta 00m:00s]
rw: (groupid=0, jobs=3): err= 0: pid=1031: Sun Oct 15 02:40:33 2017
   read: IOPS=50.0k, BW=195MiB/s (205MB/s)(11.5GiB/60020msec)
    slat (nsec): min=1006, max=8783.3k, avg=11616.59, stdev=53570.35
    clat (usec): min=20, max=300906, avg=1902.37, stdev=8166.04
     lat (usec): min=26, max=300908, avg=1914.10, stdev=8167.55
    clat percentiles (usec):
     |  1.00th=[   347],  5.00th=[   486], 10.00th=[   529], 20.00th=[   594],
     | 30.00th=[   668], 40.00th=[   734], 50.00th=[   938], 60.00th=[  1188],
     | 70.00th=[  1729], 80.00th=[  2245], 90.00th=[  2704], 95.00th=[  3032],
     | 99.00th=[  4359], 99.50th=[ 74974], 99.90th=[149947], 99.95th=[160433],
     | 99.99th=[210764]
   bw (  KiB/s): min= 1680, max=150592, per=33.35%, avg=66720.66, stdev=21592.10, samples=360
   iops        : min=  420, max=37648, avg=16680.15, stdev=5398.03, samples=360
  write: IOPS=49.0k, BW=195MiB/s (205MB/s)(11.4GiB/60020msec)
    slat (nsec): min=1489, max=8732.8k, avg=12720.29, stdev=53613.83
    clat (usec): min=9, max=301225, avg=1910.20, stdev=8189.98
     lat (usec): min=24, max=301228, avg=1923.05, stdev=8191.48
    clat percentiles (usec):
     |  1.00th=[   347],  5.00th=[   486], 10.00th=[   529], 20.00th=[   594],
     | 30.00th=[   676], 40.00th=[   734], 50.00th=[   947], 60.00th=[  1188],
     | 70.00th=[  1729], 80.00th=[  2245], 90.00th=[  2704], 95.00th=[  3064],
     | 99.00th=[  4424], 99.50th=[ 74974], 99.90th=[149947], 99.95th=[160433],
     | 99.99th=[210764]
   bw (  KiB/s): min= 1480, max=150488, per=33.35%, avg=66684.45, stdev=21528.53, samples=360
   iops        : min=  370, max=37622, avg=16671.08, stdev=5382.13, samples=360
  lat (usec)   : 10=0.01%, 50=0.01%, 100=0.06%, 250=0.37%, 500=6.07%
  lat (usec)   : 750=34.44%, 1000=12.39%
  lat (msec)   : 2=21.49%, 4=24.07%, 10=0.30%, 20=0.23%, 50=0.07%
  lat (msec)   : 100=0.33%, 250=0.20%, 500=0.01%
  cpu          : usr=4.07%, sys=16.96%, ctx=1419522, majf=0, minf=43
  IO depths    : 1=0.1%, 2=0.1%, 4=0.1%, 8=0.1%, 16=0.1%, 32=0.1%, >=64=100.0%
     submit    : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
     complete  : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.1%, >=64=0.0%
     issued rwt: total=3002198,3000568,0, short=0,0,0, dropped=0,0,0
     latency   : target=0, window=0, percentile=100.00%, depth=64

Run status group 0 (all jobs):
   READ: bw=195MiB/s (205MB/s), 195MiB/s-195MiB/s (205MB/s-205MB/s), io=11.5GiB (12.3GB), run=60020-60020msec
  WRITE: bw=195MiB/s (205MB/s), 195MiB/s-195MiB/s (205MB/s-205MB/s), io=11.4GiB (12.3GB), run=60020-60020msec

Disk stats (read/write):
  sdb: ios=2966618/2964788, merge=26473/26652, ticks=4184010/4205964, in_queue=8400100, util=99.91%

これを見ると NBD を使った実装よりも遅いことがわかる。 perf などで調べてみたが、UIO デバイスへの write、すなわち kernel への command completion の通知が重いらしい。

Samples: 31K of event 'cycles:ppp', Event count (approx.): 29291463791
  Children      Self  Command   Shared Object       Symbol
+   71.40%     0.22%  tcmu-mem  [kernel.vmlinux]    [k] entry_SYSCALL_64_fastpath
+   70.75%     0.22%  tcmu-mem  libpthread-2.26.so  [.] __libc_write
+   70.08%     0.08%  tcmu-mem  [kernel.vmlinux]    [k] sys_write
+   69.78%     0.56%  tcmu-mem  [kernel.vmlinux]    [k] vfs_write
+   69.09%     0.24%  tcmu-mem  [kernel.vmlinux]    [k] __vfs_write
+   68.79%     0.58%  tcmu-mem  [uio]               [k] uio_write
+   67.84%     0.20%  tcmu-mem  [target_core_user]  [k] tcmu_irqcontrol
+   56.89%     2.83%  tcmu-mem  [target_core_user]  [k] tcmu_handle_completions
+   31.39%     0.00%  tcmu-mem  [unknown]           [k] 0x0000000000000001
+   22.22%    21.87%  tcmu-mem  libc-2.26.so        [.] __memmove_avx_unaligned_erms
+   21.27%     0.83%  tcmu-mem  [target_core_mod]   [k] target_complete_cmd
+   20.45%     1.52%  tcmu-mem  [kernel.vmlinux]    [k] preempt_schedule
+   20.28%     1.17%  tcmu-mem  [kernel.vmlinux]    [k] ___preempt_schedule
+   19.63%     1.66%  tcmu-mem  [kernel.vmlinux]    [k] try_to_wake_up
+   19.47%     1.28%  tcmu-mem  [kernel.vmlinux]    [k] __schedule
+   19.05%     0.59%  tcmu-mem  [kernel.vmlinux]    [k] queue_work_on
+   18.86%     0.40%  tcmu-mem  [kernel.vmlinux]    [k] preempt_schedule_common
+   17.40%     1.08%  tcmu-mem  [kernel.vmlinux]    [k] _raw_spin_unlock
+   16.96%     1.89%  tcmu-mem  [kernel.vmlinux]    [k] __queue_work
+   15.17%     0.77%  tcmu-mem  [kernel.vmlinux]    [k] insert_work
+   14.36%     0.12%  tcmu-mem  [kernel.vmlinux]    [k] wake_up_process
+   13.08%     4.32%  tcmu-mem  tcmu-mem            [.] tcmu_mem::main

NBD で複数ソケットを使う

NBD では 4.10 から一つのブロックデバイスに対して複数のソケットをアサインすることができるようになった。

github.com

github.com 前回使ったコードを適当に変更して複数ソケットをマルチスレッドでさばくようにした。

また fio で適当に計測してみた。

# of fio threads # of nbd threads ios(r/w)
1 1 8313625/8309306
1 4 9939814/9935338
2 2 12332608/12329740
2 4 10418903/10416638
4 1 10956949/10836467
4 2 10441119/10353829
4 4 8330135/8235491
# of fio threads # of nbd threads type MiB/s
1 1 READ 181MiB/s
1 1 WRITE 180MiB/s
1 4 READ 216MiB/s
1 4 WRITE 216MiB/s
2 2 READ 268MiB/s
2 2 WRITE 268MiB/s
2 4 READ 226MiB/s
2 4 WRITE 226MiB/s
4 1 READ 239MiB/s
4 1 WRITE 239MiB/s
4 2 READ 227MiB/s
4 2 WRITE 227MiB/s
4 4 READ 181MiB/s
4 4 WRITE 182MiB/s

計測したマシンが hyper thread こみで 4 コアなので、fio と nbd のスレッドを同じにしつつ、合計で 4 にするのが一番性能が出るみたいだ。 以前測った lio よりもスループットが出ている。 ついでなので lio でも同じ傾向がないか fio 2 スレッドで試したが、どうにも速度が出ないようだ。

Run status group 0 (all jobs):
   READ: bw=187MiB/s (197MB/s), 187MiB/s-187MiB/s (197MB/s-197MB/s), io=32.9GiB (35.4GB), run=180001-180001msec
  WRITE: bw=187MiB/s (197MB/s), 187MiB/s-187MiB/s (197MB/s-197MB/s), io=32.9GiB (35.4GB), run=180001-180001msec

Disk stats (read/write):
  sdb: ios=8632558/8631694, merge=0/5, ticks=169527/171223, in_queue=334347, util=78.51%