USENIX FAST16の論文のメモ書きです。BetrFS 0.1というのがあったが、それをベースに0.2を作ったという話。

WOD(write optimized dictionary)というのがあって、文字通り書き込みに最適化されたディレクトリなんだけど、これまで削除、リネーム、シーケンシャル書き込みが遅かった。それをlate-binding journaling, zoning, range deletionの3つで解決した。

journalingというのはファイルシステム用語で、一度ジャーナル領域にログを書いて、後で本物の位置に書き出すという方式。Linuxでもext4はデフォルトでメタをジャーナリングして、データは直接本物の位置に書き出すというやり方。data=journalにすると、データもジャーナリングする。ジャーナリングの欠点は書き込み量が倍になること。stable storageへの書き込み完了を返す時間を早めたいからジャーナル領域にログ書きするわけだけど、実際にファイルシステムの構造を効率よく保つためにはログ書きのままだと都合が悪い。なので、別の本物の領域を割り当てて書き出すという作業が必要になる。

そこのところ、btrfsやzfsは頑張っていて、二度書きしないようにうまくやっているらしい。この論文で言うlate bind journalはbtrfs, zfsみたいにjournalで二度書きしないように、btreeをうまくやるという話みたいだ。full journalよりはcrash consistencyが劣るのかな。

zoningはdirectory treeのtraverseやrenameを高速化する。高速化にはlocality必須なのだが、localityとrename高速化を両立させるのは当然難しい。なんでかというと、普通にやればrenameで実体を別のとこに移さないとlocalityが崩れるから。ホントか。

range deleteは全体的に良くなる。

WODはインタフェースはbtreeみたいだが、性能は違う。random key insertが速いし、deleteもマークするだけだから高速。deleteのマークのことをtombstone(墓石？)と表現していた。point queryの性能はbtree相当で、range queryもそこそこ速い。ここちょっと目を疑ったんだけど、tokudbをカーネルにポートして使ってるらしい。まじか。tokudbてあのfractal treeのやつでしょ？ 若干変態入ってるインデックスの。そしてuserlandのfuseではなくてカーネルで作ったのね、というところもちょっとした驚き。

このあとtokudbらしきもののことを盛んにbtreeと言ってるけどこれが、実際の処理はfractal treeなのかな…

late bind journalの説明。二度書きを防ぐには、ext4みたいにdata journalをやめるか、zfsやbtrfsみたくindirect writeにするかという選択になる。BetrFSでは当然indirect writeにする。indirectでログ(ジャーナル)てのはLSM treeと同じものなんだろうな。ログにはデータだけじゃなくてメタもあるはずだけど、アラインを両立させると穴空きが激しくなるだろうなー。マップをflushしてしまえばログのメタは邪魔になるだけだ。readにもペナルティがある。それをbtreeのノードででも埋める？ それともgcする？

searchとrenameはトレードオフ関係。zoneで解決するという話なんだけど、あんまり工夫してる気がしないな。普通じゃないのこれ？ そのtradeoffはパラメータで判定しているみたい。

…とまあここまで読んだところで、割と興味深い内容ではあるんだけど、自分との縁はなさそうに思った。評価のところは読んでない。おわり。