distrobuilder で lxc 用のイメージを作る

lxc 3.0 ではコンテナイメージ作成に使われていたテンプレートスクリプトが削除されて、 https://github.com/lxc/lxc-templates に移動された。 今後は distrobuilder を使うのがおすすめらしい。 ということで distrobuilder でイメージを作ってみる。

distrobuilder は go で作られているので go get でビルドする。

$ go get github.com/lxc/distrobuilder/distrobuilder

あとはイメージ作成用のテンプレートを使ってビルドする。 テンプレートは example を参考にする。 ホスト側にイメージ構築用のツールセットが必要になることがあるので適切にセットアップしておく必要がある。 たとえば debian 系ならば debootstrap が必要になる。

以下のコマンドでカレントディレクトリに meta.tar.gzrootfs.tar.gz が出来る。

$ distrobuilder build-lxc debian

あとは lxc でこのファイルをもとにコンテナを構築する。

$ lxc-create --name test --template local -- -m meta.tar.xz -f rootfs.tar.xz

あとはいつもどおりにコンテナを使うことが出来る。

linux kernel library で遊ぶ

AsiaBSDCon 2018 で linux rumpkernel についての発表があったらしく気になっていた。

www.slideshare.net

当日は参加していないのでわからないが、linux kernel をライブラリとして使ってユーザーランドでネットワークの実装を簡単に行いたいという文脈なのだろうか。

プロジェクトのサイトは https://lkl.github.io/ だが非常に簡素、というか情報がないので、 直接リポジトリを見たほうが良い。

https://github.com/lkl/linux

README の FAQ に UML (user mode linux) との違いが書いてあるが、UML はフルのカーネルがユーザーランドで動いているが、 lkl はあくまで自分のコードとリンクして kernel の関数を呼び出すということが主眼になっている。

tools/lkl の中にいくつかサンプル的なコードが散らばっているので見てみるとだいたい使い方はわかる。 hijack ライブラリを使うと LD_PRELOAD を使って libc の syscall を置き換えて lkl の syscall を使わせることができる。 すべての syscall を置き換えているわけでは無いので何が使えるかはコードを見る必要がある。 また lkl で置き換えていない syscall はホスト側が使われるようだ。

lkl 自体は arch の一種として実装されているようだ。 UML も同様だったし linux kernel はこのあたりよく抽象化されている。

実際に lkl をつかって procfs をマウントし内部のファイルを出力するサンプルを書いてみた。 https://github.com/toshipp/play-with-lkl/blob/master/cat_proc.c

lkl の初期化に lkl_start_kernel を呼び出して、lkl のシステムコールを使うには lkl_sys_* を呼び出せば良い。 lkl_start_kernel の引数の lkl_host_ops は lkl が使うホストシステム側のシステムコールなどを保持する構造体で、 posix では以下で実装されている。

https://github.com/lkl/linux/blob/master/tools/lkl/lib/posix-host.c

この構造体を書き換えてやれば posix 以外でも動くだろう。 実際に windows 用のコードもある。

さて、lkl は NOMMU として実装されているが、NOMMU でも vfork はサポートできる。 ただし lkl は vfork を未実装にしているので試しに有効にして使ってみた。

https://github.com/toshipp/play-with-lkl/blob/master/patch/vfork.patch https://github.com/toshipp/play-with-lkl/blob/master/vfork.c

残念ながらこれを起動すると segv で落ちてしまう。

% ./vfork                                                                                                                                                                                          (git)-[master]
[    0.000000] Linux version 4.15.0+ (toshi@toshi-note) (gcc version 7.3.1 20180312 (GCC)) #2 Sat Apr 14 20:25:56 JST 2018
[    0.000000] bootmem address range: 0x7f776f396000 - 0x7f776fd95000
[    0.000000] Built 1 zonelists, mobility grouping off.  Total pages: 2524
...
[    1.380143] Btrfs loaded, crc32c=crc32c-generic
[    1.380235] Warning: unable to open an initial console.
[    1.380261] This architecture does not have kernel memory protection.
zsh: segmentation fault (core dumped)  ./vfork

core を見てみると vfork から最終的に呼び出される copy_thread で使う関数ポインタが NULL になっているようだ。 https://github.com/lkl/linux/blob/master/arch/lkl/kernel/threads.c#L179

もしかするとなんとかできるのかもしれないが、よく考えると vfork なんて使わなくても、 lkl 呼び出し側のコードで pthread_create などを使えば良いだけだと気づいたので深追いはしていない。

Ceph storage backend bluestore について

分散オブジェクトストレージ Ceph はそのバックエンドとして、ファイルシステムを使う filestore の他に、ブロックデバイスを使う bluestore をサポートしている。

bluestore については公式ブログの記事slideshare に概要がある。

大雑把に書くと、メタデータの保存に rocksdb を使い、rocksdb をブロックデバイス上に構成するために、bluefs というシンプルなファイルシステムを使っている。

bluestore は rocksdb に様々なメタデータを保存していて、Ceph のオブジェクトの他にも、例えばブロックデバイスのフリーリストなども入っている。

bluefs は rocksdb を動かすための最小限のファイルシステムで、bluefs 自体のメタデータはすべて journal log に書き込まれている。 そのため起動時にこのログをリプレイすることでメタデータを復元している。

この journal には bluefs が利用している領域についての情報も含まれている。 journal は bluefs 上のファイルとして表現されているため、bluefs を mount するためには journal を再生する必要があるが、journal を open するには mount する必要があるという循環が起こっている。

この解決に bluefs は superblock 上に journal ファイルに関するメタデータを保存しており、この循環を断ち切っている。

LevelDB のルックアップ

今更という感じだが、LevelDB について調べた。

table_format にあるように、LevelDB の SST の中身は block に分かれている。 block のなかは key-value の組が複数個入っている。 block ではキーのプレフィックスを圧縮したり block そのものを圧縮していたりするらしい。

このようなデータ構造では馬鹿正直にデータのルックアップにスキャンをしていたら大変なので index block を持っている。 index block もソースコードを読むと block 構造になっている。

さて、index によってキーが入っていそうな block がルックアップされたとしても、 実際 block を舐めるのはブロック自体の圧縮や、キーのプレフィックス圧縮があるのでまだコストが高い。 そのためオプションだが bloom フィルターを用いてキーがあるかどうか確認できるようになっている。

ここまでで単一の SST 内の検索が可能になった。 LevelDB は複数の SST が DB を構築しているため、SST 自身のルックアップが必要になる。

このルックアップは単純で、SST はキーの上限と下限がわかるので、各 level で二分探索していけば良い。 ただし level-0 では SST 間でキーのオーバーラップがあるらしいのでキーを含む SST 全部を検索対象にする。

また LevelDB は SST になる前のデータを memtable としてメモリ上に持っている。 こちらは skiplist で検索可能になっている。

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 はハッシュテーブルを使っていて、キーに素数をかけてスロット数で割るという単純なものを使っている。 衝突時は前回の結果をインクリメントして同じアルゴリズムを適用する。