Ext4

Ext4はファイルシステム内部がBlock Group(BG)という領域に分割されています。各BGは空きブロックの数・空きinodeの数・どのinodeが空いているのかを示すbitmapを持ちます。inodeのallocateはどこかのBGから行われます。

たとえば今回の結果だと、"0/*"がBG#256から、"1/*"がBG#864からallocされていることがわかります。"Group 256"の"Free inodes"が"2097158-"と"0/3"の次のinode番号になり、同様に"Group 864"でも"Free inodes"が"1/3"の次である"7077894-"となっています。

# dumpe2fs ext4.img
…
Group 256: (Blocks 8388608-8421375) [ITABLE_ZEROED]
  Checksum 0xb0b5, unused inodes 8187
  Block bitmap at 8388608 (+0), Inode bitmap at 8388624 (+16)
  Inode table at 8388640-8389151 (+32)
  24539 free blocks, 8187 free inodes, 5 directories, 8187 unused inodes
  Free blocks: 8396837-8421375
  Free inodes: 2097158-2105344
…
Group 864: (Blocks 28311552-28344319) [ITABLE_ZEROED]
  Checksum 0xf815, unused inodes 8187
  Block bitmap at 28311552 (+0), Inode bitmap at 28311568 (+16)
  Inode table at 28311584-28312095 (+32)
  24539 free blocks, 8187 free inodes, 5 directories, 8187 unused inodes
  Free blocks: 28319781-28344319
  Free inodes: 7077894-7086080

Ext4は新しいinodeを(ルート直下の場合を除いて)親ディレクトリと同じBG内にallocしようとします。、一般にディレクトリのinodeへのアクセスの後にはその中のファイルにアクセスすることが予想されます。ext4では同一BG内のinodeは固まって配置されているため、同一BGにallocすることでディレクトリinodeの読みこみがついでにその中のファイルのinodeの読みこみもやってくれる可能性が高まります。おそらくこの効果による速度向上を狙ったinode allocation policyなのでしょう。まとめるとext4は"locality"を重視したallocationを行っているわけです。

XFS

XFSでもExt4のBGと同様にファイルシステムの内部をAllocation Groupという領域に分割しています。ただし、Ext4では上記のように800以上にも分割されていましたが、XFSでは多くの場合(FSが128MBから4TBの間なら)、4つのAGに分割されるだけです。

そう思ってよくよくXFSのinode番号の結果を見てみると、4つごとにinode番号のだいたいの大きさがそろっていますね。それぞれAG#0-AG#3にallocationされているというわけです。

せっかくなので、こっちもallocationされている様子を見ておきましょう。まず、AG#0の情報をdumpします。

# xfs_db xfs.img
xfs_db> agi 0
xfs_db> p
magicnum = 0x58414749
versionnum = 1
seqno = 0
length = 33554432
count = 64
root = 3
level = 1
freecount = 58
newino = 96
dirino = null
unlinked[0-63] =
uuid = 3dd1af10-10f6-45dc-b466-c10a727d9842
lsn = 0x100000002
crc = 0x7df3830f (correct)
free_root = 4
free_level = 1

ここの"root"がこのAGでinodeを管理しているB+treeのrootがあるブロックです。該当部分をinodeのB+treeとしてdumpします。

xfs_db> fsblock 3
xfs_db> type inobt
xfs_db> p
magic = 0x49414233
level = 0
numrecs = 1
leftsib = null
rightsib = null
bno = 24
lsn = 0x100000002
uuid = 3dd1af10-10f6-45dc-b466-c10a727d9842
owner = 0
crc = 0x1b9f870b (correct)
recs[1] = [startino,freecount,free] 1:[96,58,0xffffffffffffffc0]

"[startino,freecount,free] 1:[96,58,0xffffffffffffffc0]" がinode管理情報です。XFSではinodeは64個の塊で動的にallocされていきます。このエントリはinode番号96から64個分のinodeについて管理しています。"freecount"が58なので64-58=6個のinodeが使用されており、どこが空いているのかは"free" bitmapを見ることでわかります。実際96-101に相当する下位6bitが0で残りが1になっていることが見てとれます。

同様にAG#1のinode B+treeも見てみると…。(agi 1+addrでAG#1のoffsetを確認し、そこに3足したところがAG#1のinode B+tree root)

xfs_db> agi 1
xfs_db> addr
current
        byte offset 137438954496, length 512
        buffer block 268435458 (fsbno 33554432), 1 bb
        inode -1, dir inode -1, type agi
xfs_db> fsblock 33554435
xfs_db> type inobt
xfs_db> p
magic = 0x49414233
level = 0
numrecs = 1
leftsib = null
rightsib = null
bno = 268435480
lsn = 0x100000002
uuid = 3dd1af10-10f6-45dc-b466-c10a727d9842
owner = 1
crc = 0x687eec0e (correct)
recs[1] = [startino,freecount,free] 1:[96,61,0xfffffffffffffff8]

こちらもinode番号96から、となっていますね。ここに記録される96というのはAG内localのinode番号でFSでのinode番号にするには上位bit領域にAGの番号を入れる必要があります。そう思って"0/0"のinode番号を見ると"268435552"というのは"0x10000060"というわけで"0x60=96"と"0x1"=AGの番号が見てとれます。

さてXFSのinode allocation policyの話に行きましょう。XFSではディレクトリの場合、FS全体でラウンドロビンにAGを(優先して)選択していきます。そのため最初の実験結果のようにディレクトリごとにAGが変わっていっているわけですね。一方でファイルであればディレクトリと同じAGを優先するので、さきほどのスクリプトをディレクトリ0,1以下はファイルを作るようにするとこうなります。

xfs
       96 drwxr-xr-x 4 root root 24 Jun 17 01:18 /mnt/test
       99 drwxr-xr-x 2 root root 42 Jun 17 01:18 /mnt/test/0/
      100 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/0/0
      101 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/0/1
      102 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/0/2
      103 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/0/3
268435552 drwxr-xr-x 2 root root 42 Jun 17 01:18 /mnt/test/1/
268435553 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/1/0
268435554 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/1/1
268435555 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/1/2
268435556 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/1/3

ディレクトリをFS全体でラウンドロビンに配置していくことで、個々のディレクトリ内の操作はAGが異なれば独立して進めることができ、scalabiltyが向上しています。このようにXFSでは"scalability"を意識したallocation policyが使われています。

Btrfs

Btrfsでは、ディレクトリとファイルとの親子関係・inodeデータ・ファイルのデータ位置情報が全て「ファイルシステムツリー」(FS tree)と呼ばれるB-treeで管理されます。また、Btrfsにおいては「どこのinodeが空いているか」を管理するまとまった情報(ext4やXFSのbitmapみたいな)は(デフォルトでは)存在しません。treeの中でファイル削除などで空いてしまったinode番号を発見する最速の方法はFS treeを全部scanすることです。前述の通り、FS treeには様々な情報が載っているのでこれをなめていくのはかなりの時間がかかります。ということで、Btrfsではこれまでにallocした最大のinode番号を覚えておいて、これまでに割り当てたことのないinode番号を割り当てるというallocation policyをとっています。そのため、最初の結果のようにシーケンシャルになっています。なんですかね、"simple"なallocation policyとでも言っておくといいんでしょうか。

(Btrfsはext4, XFSみたいにFS領域分割しないのかというのがありますが、一応chunkという単位に分かれています。ただ、localityやscalabilityのためでは(多分)なく管理しやすさぐらい…。localityなんてやろうとしてもどうせCoW FSだからそのうち崩壊するだろうし、デフォルトでinode番号管理構造ないからallocするinode番号を開けていくようにするのはうまくいかないし…。inode_cacheを仮定してallocするinode番号を変えるなどするのはおもしろいのかもしれないが…もう2時なのでもうこんな感じで)

まとめ

それぞれのFSがBtrfsはsimple, Ext4はlocality, XFSはscalabilityと違ったinode allocation policyを取っています。そのおかげであなたも明日からファイルシステムソムリエです。おめでとうございます。

補則

今回は作りたてのFSだったけれど、じゃあ、ある程度使われたFSだとどうなるってことなんですが、inode_cacheなしのbtrfsだとやはりシーケンシャルに当たるのでわかりやすい。ext4とXFSではinodeの空き方によって複雑になる気がします。まあXFSの方が性質上inode番号が大きくなりがちなんでそこ見ていけばいいかなとか、inode領域が動的確保なことを利用してあるAG内のファイルにデータを書きまくる->その後にそのAG内でallocされたinode番号を見るといったことをすればいいんじゃないでしょうか。

あとbtrfs、inode割り当て一周したらどーすんのってのはちゃんとinode_cacheというmount optionでどこが空いているかのデータベース作ってそこ見てくれるようになるんで安心してください。でも64bit環境ならそうそうなくならんし普通はなくてもいいんじゃないかな。