- ハードウェアページは典型的には4kb
- この単位で書き込む場合、all or nothingで書ける
- DBのファイルはheap fileをよく使う
- ページ単位で読み書きできるAPI
- heap fileの実装はpage dictionaryをよく使う
- link listだと効率が悪い
- page layoutはslotted pageをよく使う
- ページヘッダのあとに格納されているtupleの場所を示す配列を置く
- tupleはpageの後方から配置していく
- arrayとtupleがぶつかるまでは詰めることができる
- page layoutとしてlog structureを使うてもある
- 再構築が必要なので遅いが、append onlyなのでHDFSとかでよく使う
- あとlog compactionが必要なのでwrite amplificationが起こる
- tuple layoutとして複数のテーブルを一つのtupleに突っ込むdenormalizeというものがある
- 例えばjoinするテーブルをまとめておくと1ページ読むだけでデータが手に入るので高速
- その昔はやっていることもあったがむずいので使われなくなった
- google spannerとかは使っている
- mongoとかのdocument dbもある意味ではこれ
- record id は page id + slot offsetを使うのが多い
systemd-resolvedで特定ドメインのDNSSEC検証を無効にする
arch linuxのsystemd 239から、systemd-resolvedでDNSSECでの検証がデフォルトで有効になったらしい。 手元の環境では、自分で所有しているが、実際に存在する名前を使って権威サーバを立てているために、DNSSECでの検証が失敗してアドレスが引けない問題が起きた。
systemd-resolvedではプライベート用に使えるドメインについてはnegative trust anchorに設定してくれているので、このような名前を使うとこのような問題は起こらない。
systemd-resolvedでは権威サーバの検証を行うキーを登録するためのpositive trusted anchorと、指定したドメインの検証を無効化するnagative trust anchorが存在し、/etc/dnssec-trust-anchors.d/*.positiveや/etc/dnssec-trust-anchors.d/*.negativeで設定できる。
今回はnegative trust anchorを使って、プライベート用の権威サーバのDNSSECの検証を無効にすることにした。
そのためには/etc/dnssec-trust-anchors.d/mydns.negativeなどの適当な名前でファイルを作成し、その中に検証を無効化したいドメイン名を記載すれば良い。
たとえばexample.comと記載すれば、そのサブドメインを含めて検証を無効化できる。
設定が終われば、systemd-resolvedを再起動すれば検証がスキップされるようになる。
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.gz と rootfs.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/ だが非常に簡素、というか情報がないので、 直接リポジトリを見たほうが良い。
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 編その２
前回は主に 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 を保護しているのか。 InnoDB は MTR の中に rollback segment への書き込み自体を記録することで再構築できるようにしている。
