ファイルシステム(ext2/ext3/ext4)の基礎まとめ

ext2

  • 正常にアンマウントが実行されなかった場合には、パーティション全体のメタデータと実データの整合性をfsckによって確認する必要がある

  • ブロック構造 - ブロックサイズは1KB,2KB,4KBのいずれか

http://3.bp.blogspot.com/-grP9mP9Kez8/UQaBRvz2E9I/AAAAAAAAASA/0kgIh9QvkLU/s1600/ext3.JPG

  • スーパーブロックには全体のi-node数など、グループデスクリプタにはそのブロックグループのi-node数など、i-nodeにはファイルのメタデータとデータブロックのアドレスなど、が記録されている

    • スーパーブロックはバックアップされており、mkfs.ext2 -nでバックアップされたブロックを確認することができ、mkfs.ext2 -bでそのブロックを指定することで復旧できる
  • 間接ブロック参照 - ext2のi-nodeにはデータが保存されているブロック番号を格納するサイズ15のテーブルがあり、そのうち#0〜#11は直接ブロック参照(ブロック番号を格納する)、#12は1段間接ブロック参照(ブロック番号を格納したテーブルを参照する)、#13は2段間接ブロック参照(ブロック番号を格納したテーブルを参照するテーブルを参照)、#14は3段間接ブロック参照、に使用される

http://wiki.bit-hive.com/linuxkernelmemo/upload/54/696e6f64655f626c6f636b.png

Ext2 FS - Linuxカーネルメモ

  • 間接ブロック参照によって1ファイル4TBまでブロックを参照できるが、i-nodeのメタデータにあるブロック数が2TB(ブロックサイズが4KBの場合)までしか管理できないので、そちらが1ファイルサイズの限界を決めている

  • 大きいサイズのファイルになると間接参照が多くなるため、書き込みや読み込みの性能が悪くなる

ext3

ジャーナリング

  • データの更新処理を、不可分(アトミック)な一つのトランザクションに集約して記録することで、ファイルシステムの整合性を維持するための仕組み
  • たとえファイルを削除するという単純なトランザクションの中でも、スーパーブロックやファイルのメタデータに対する様々なステップ処理が存在するため、その途中で不正なシャットダウン(アンマウント)が発生し、一部のステップ処理のみが実行される状態になるとメタデータの整合性が崩れる
  • ジャーナルログがあれば、不正なアンマウントが発生してそのパーティションcleanな状態でなくなっても、メタデータと実データとの不整合を復旧するだけでよい
    • fsckはステップ処理単位での復旧も可能だが、ジャーナルログがあれば(トランザクション単位での不可分な更新記録が存在するため)fsckの明示的な実行は不要で、ファイルシステムの機能としてジャーナルログから自動的に復旧する
    • ジャーナルログはあくまでもファイルシステムの整合性を維持するための仕組みであり、実データについては保証しない(書き込んだと思ったものが消失する)
  • ただしext3であっても、何らかの不正な書き込みが発生してメタデータの整合性が壊れると、fsckによるステップ処理単位での復旧が必要になるし、fsckを実施していない期間がある一定期間を超えるとパーティション全体の整合性を確認することになる

qiita.com

O+P Insights: Improving Ext3 performance with an external journal on an SSD Disk

Linuxカーネル2.6解読室

Linuxカーネル2.6解読室

fsck

  • メタデータの矛盾を取り除くコマンド。壊れたデータを復旧するわけではなく、メタデータの整合性が取れるように壊れた部分を排除する。
  • ファイルシステムには定期的にfsckを実行するオプションがある。ジャーナルログを採用しているファイルシステムであっても、マウントを実行した回数や前回fsck実行からの期間、によってサーバ起動時にfsckが発動してパーティション全体を走査することによる起動遅延が発生することがある。
$ sudo tune2fs -l /dev/sda1 | egrep -i "mount count|check"
Mount count:              16
Maximum mount count:      -1
Last checked:             Sun Jun 19 00:06:19 2016
Check interval:           0 (<none>)
  • fsckのチェックによってファイルシステムの整合性を保つためにディレクトリやi-nodeの内容が破棄されることで、参照不可能になったデータブロックの内容は/lost+foundディレクトリに#とi-node番号をファイル名として退避される。

kjournald

  • トランザクションを、定期的にディスク上のジャーナルログ領域に書き込む(コミットする)デーモン
  • kjournaldの書き込み間隔はデフォルトで5秒で、この間隔は信頼性と性能(データの永続化とDisk I/Oの回避)のトレードオフとなる

ジャーナルモード

www.atmarkit.co.jp

  • ジャーナルモードはマウントオプションとしてdata=journalなどとして指定する
journal
  • メタデータと実データのトランザクションをコミットしたのち、メタデータと実データをディスク上のデータ領域に書き込む
  • 完全にデータを冗長化することができるが、書き込み性能は悪い
  • ジャーナルログとデータ領域に不整合が発生することがない
ordered
  • 実データが書き込まれたのち、メタデータトランザクションをコミットする
    • つまり、実データの書き込み順序と、トランザクションへのコミット順序が、常に一貫性を保つ(シーケンシャルに実行される)ことを保証する
  • 実データがディスク上のデータ領域に書き込まれる前に不正なアンマウントが発生すると…
    • ジャーナルログから、ディスク上のデータ領域のメタデータを復旧する
    • 新しい実データが(バッファには書き込まれているものの)ディスク上のデータ領域に書き込まれていない場合は、実データは復旧できない
  • 新しい実データの復旧はできないが、ジャーナルログによるメタデータの復旧は可能になる
writeback
  • 実データの書き込み順序と、トランザクションへのコミット順序が、一貫性を保てない
  • 実データがデータ領域に書き込まれる前に不正なアンマウントが発生すると…
    • ジャーナルログはシーケンシャルに書き込まれたものであることが保証されていないため、メタデータの復旧が正しく行われないことがある
  • 書き込み性能は最も良いが、メタデータの復旧がうまくいかない場合があることを許容する動作になる

MySQLInnoDB)との関連について一言

WAL / Double Write
  • WAL (Write Ahead Log) は、トランザクションがコミットされたときに、トランザクションの内容をディスク上のログ領域に書き込む(更新データはバッファ上に残っている)
  • Double Writeは、バッファからディスクへフラッシュされたときに、ディスク上のデータ領域に書き込む前に、ダブルライトバッファ領域に書き込む(更新データのコピーを保持することができる)
  • これらの領域はシーケンシャルに書き込まれていくので、ディスク上のシーク時間が短く、I/Oに必要な時間が短い(Double Writeといっても書き込み時間が二倍になるわけではない)

ext4

  • 遅延確保 - ext3まではバッファ書き込み時にディスク上のブロック割り当てを行うが、これをバッファ書き込み時からディスク書き込み時にまで遅延することで、複数の書き込みをまとめてブロック割り当てを行うことができるため、連続したブロックを割り当てやすくなりフラグメンテーションを起こりにくくする

  • エクステントの導入 - 大きなファイルに対して、複数のブロックの格納場所を全て保持する(かつ、多段参照のオーバーヘッドがある)と非効率なため、隣接するブロックに対してその格納場所を配列として保持することにより効率化する(先頭ブロックの格納場所と連続ブロック数(オフセット)、を組み合わせて複数保持する)

    • 一つのi-nodeに格納できるエクステントは限りがあるので、Extent-IndexをB-treeとして保持することで検索効率を上げる

https://www.usenix.org/legacy/event/lsf07/tech/cao_m.pdf

# ext4
$ mount | grep " / "
/dev/mapper/fedora-root on / type ext4 (rw,relatime,seclabel,data=ordered)
$ stat /etc/fstab 
  File: ‘/etc/fstab’
  Size: 465         Blocks: 8          IO Block: 4096   regular file
Device: fd01h/64769d    Inode: 130747      Links: 1
Access: (0664/-rw-rw-r--)  Uid: (    0/    root)   Gid: (    0/    root)
Context: system_u:object_r:etc_t:s0
Access: 2017-02-14 09:24:21.453460379 +0900
Modify: 2014-03-01 18:43:24.267325166 +0900
Change: 2014-03-01 18:43:24.267325166 +0900
 Birth: -
# ext3
$ dd if=/dev/zero of=ext3img bs=1M count=100
100+0 records in
100+0 records out
104857600 bytes (105 MB) copied, 0.386865 s, 271 MB/s
$ mkfs.ext3 -F ext3img 
mke2fs 1.42.12 (29-Aug-2014)
Discarding device blocks: done                            
Creating filesystem with 102400 1k blocks and 25688 inodes
Filesystem UUID: 235bf453-34b4-430e-b508-4279dbc61c6c
Superblock backups stored on blocks: 
    8193, 24577, 40961, 57345, 73729

Allocating group tables: done                            
Writing inode tables: done                            
Creating journal (4096 blocks): done
Writing superblocks and filesystem accounting information: done 

$ sudo mkdir /mount
$ sudo mount -t ext3 -o loop ext3img /mount/
$ mount | grep ext3
/home/nishidy/ext3img on /mount type ext3 (rw,relatime,seclabel,data=ordered)
$ sudo touch /mount/file
$ sudo vim /mount/file 
$ stat /mount/file 
  File: ‘/mount/file’
  Size: 12          Blocks: 4          IO Block: 1024   regular file
Device: 700h/1792d  Inode: 14          Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Context: unconfined_u:object_r:file_t:s0
Access: 2017-02-14 09:31:39.000000000 +0900
Modify: 2017-02-14 09:31:25.000000000 +0900
Change: 2017-02-14 09:31:25.000000000 +0900
 Birth: -
  • チェックサムの導入 - ジャーナルログにチェックサムが追加されて、ジャーナルログに対するチェックサムチェックが可能になり、信頼性が向上する

  • H-Tree - ext2/ext3ではディレクリ構造が連結リストにより管理されていたが、連結リストでは探索にO(n)の時間がかかるため、B-Treeの改良版であるH-Treeが採用されており、これにより探索時間が短縮される*1

Directory indexing

  • 動的なi-node確保 - …

B-Tree

https://upload.wikimedia.org/wikipedia/commons/6/68/B-tree_example.svg

  • Balanced Tree(平衡木の一つ)
  • 検索における計算量
    • 木に含まれる全てのキーの数をn、ノードが持つ子の最大数をm(ノードが持つキーの最大数をm-1)とする
    • ノードが持つ子の平均数は m/2 になり、よって木の深さは となる
    • ノードのキー探索回数は、mが大きいときにはBinary Searchによってlog mとなる(キーはソート済み)
    • よって計算時間は log m * となり、計算量は O( log m * ( log n / log m) ) となって、結果的にO(log n)となる

e.g.

30 50 70 | 
10 20 | 40 | 60 | 80 90 | 

B+-Tree

  • B-Treeを拡張した、Key-Valueを格納する木構造
  • リーフノードのみがValueを持つ(全てのKey-Valueがリーフノードに存在する)ため、必ずリーフノードまで辿り着く必要がある

e.g.

30 50 70 | 
10 20 | 30 40 | 50 60 | 70 80 90 |

http://www.drk7.jp/MT/drk/images/091108/ora003.png

Oracle の B*Tree インデックスの内部構造についてお勉強中(その1) - drk7jp

Interactive B+ Tree

B*-Tree

  • B+-Treeを拡張して、ノードの持つキー数をなるべく多く保つ(as dense as possible)ことで、メモリ利用効率や検索速度が向上
    • 最大数のキーを保持しているノードに挿入する場合、(B+-Treeのように)即座にノードを分割するのではなく、隣のノードに空きがある場合は、親ノードを介した回転を伴って、隣のノードにキーを移動させる
    • 隣のノードも最大数のキーを保持している場合、二つのノードを三つのノードに分割する

The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版 (Ascii Addison Wesley programming series)

The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版 (Ascii Addison Wesley programming series)

XFS

  • アロケーショングループ
    • パーティションを同一サイズの複数のエリアに分け、各アロケーショングループを独立に管理することにより、書き込み処理を並列に行うことができるようにする
    • ext4ではスーパーブロックにパーティション全体を管理する情報が書き込まれているため、書き込み処理はシーケンシャルな実装にする必要がある
    • XFSでは各アロケーショングループにおいてスーパーブロックが独立しているため、スレッドでCPU的には並列な書き込み処理が実装できる*2

Btrfs

  • コピーオンライト(CoW)
    • データ更新時にスナップショットを作成することで、障害時の実データのロールバックが可能に
    • データコピー時には実体への参照のみを作成することで、高速な処理が可能に(データ更新時に実体を作成)
  • 透過圧縮
    • ディスクに書き込む・読み込む際にファイルシステムのサポートによってデータを圧縮・解凍する(LZO、ZLIB)
    • 圧縮・解凍のためにCPU使用率が上がるが、書き込む量を減らすことで、ディスクスペースの利用効率だけでなく、ディスクI/Oの効率を上げる効果がある
  • LVMのようなボリューム管理機能
    • 複数デバイスを一つのボリュームとして扱うことができ、balance機能によって自動的に書き込み領域を各デバイスに分散することで性能向上が可能に
    • オンラインでのデバイスの追加・削除が可能に

www.slideshare.net

ハードリンクとシンボリックリンクの違い

  • ハードリンクは、オリジナルファイルと同じi-node番号を持つファイル。i-node番号が同じファイルのため、オリジナルファイルをどのパスに移動しても、ハードリンクはパスに関係無くオリジナルファイルへ追従することができる。ただし、ハードリンクはオリジナルファイルと別のファイルシステム上には作成できない。i-node番号体系が異なるためである。
  • i-nodeには参照カウントがあり、ハードリンクが作成されるとオリジナルファイルの参照カウントがインクリメントされる。ハードリンクが削除されると参照カウントはデクリメントされる。参照カウントが0になった時点で実体のブロックは解放可能となる。
  • シンボリックリンクの実体はオリジナルファイルへのパスである。従って、シンボリックリンクはハードリンクと別のファイルシステム上にも作成できる。ただし、オリジナルファイルを削除したことに気が付かない。

  • ディレクトリエントリは、ファイル名とi-node番号を対としたリストを持つ。従って、i-nodeにファイル名の情報は無い。".“は自分自身のi-node番号を指すため、ディレクトリ作成時に参照カウントは2となる。”..“は親ディレクトリへのi-node番号を指すため階層構造をルート方向へ追跡することができる。

chroot配下でchroot外へディレクトリへリンクする場合

ディレクトリ自体のハードリンクに関しての覚え書き - Qiita

*1:H-TreeのHはHashで、Hash値をキーに用いることで、B-Treeよりも高速な検索になるらしい。HashなのでO(1)だが、Treeなので階層別にHashが必要になるのと、リーフは衝突に備えてリストにする必要がある

*2:物理的には並列ではなく並行なはずだが、RAID0を使っていたり、LVMで複数のPhysical Volumeの上にLogical Volumeを作成していたりした場合は、より効果があるのかもしれない