【第14回】元東大教員から学ぶLinuxカーネル「ファイルシステムとクラッシュ整合性」

こういった私から学べます．

前回を読んでいない方はこちらからどうぞ．

Linuxカーネルの記事一覧はこちらからどうぞ．

LinuxカーネルはC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

今回のテーマはファイルシステムとクラッシュ整合性です．

特に，Linuxカーネルでデフォルトで使われているext4ファイルシステムを理解しましょう！

Linuxカーネルのファイルシステム

上図にLinuxカーネルのファイルシステムを示します．

Linuxカーネルは多くのファイルシステムをサポートしていますが，本記事でext4ファイルシステムをメインで紹介する理由は以下になります．

• 主要なLinuxディストリビューションのデフォルトのファイルシステム
• Google データセンターで使用されているファイルシステム
• Androidカーネルのデフォルトのファイルシステム

また，ext4は伝統的なファイルシステムの設計に従っています．

デフォルトのUNIX系ファイルシステムの歴史は上図になりますので，それぞれ解説していきます．

UNIX系ファイルシステム

UNIX系ファイルシステムを紹介します．

• UNIX File System（UFS）
• MINIXファイルシステム
• extファイルシステム
• Fast File System（FFS）
• ext2ファイルシステム
• ext3ファイルシステム
• ext4ファイルシステム

参考までに，Linuxカーネルがサポートしているファイルシステムは/proc/filesystemsで確認できます．

UNIX File System（UFS）

UNIX File System（UFS）は，1969年にKen Thompsonにより開発された元祖UNIXファイルシステムです（上図）．

※1970年代以降にUFSのバージョン更新があります．

また，UNIXを開発するために1972年にC言語が開発されたことが有名です．

C言語を学びたいあなたはこちらからどうぞ．

UFS，MINIXファイルシステム，extファイルシステムは似たようなレイアウトになっています．

しかし，これらのファイルシステムの性能上の問題点は，inodeとdata blockの間のシーク時間が長いことです．

UFSの解説動画はこちらです．

MINIXファイルシステム

MINIXファイルシステムは，1987年にAndrew S. Tanenbaumによって開発されたMINIX用のファイルシステムです．

MINIXとそのファイルシステムは，ほとんどが教育的なコーディングの目的で使用されていました．

ファイルシステムの性能は，当時の標準には達していませんでした．

ファイル名の長さは14文字に制限され，パーティションは64MBに制限されていました．

当時，ハードディスクは140MBまでのパーティションをサポートしていました．

MINIXファイルシステムの解説動画はこちらです．

extファイルシステム

extファイルシステム（Extended File System）は，1992年4月にLinuxカーネルをサポートするために開発された最初のファイルシステムです．

extファイルシステムには仮想ファイルシステムが使用されました．

仮想ファイルシステムの主な目的は，Linuxカーネルがextファイルシステムにアクセスできるようにすることでした．

extファイルシステムは，ファイル名の長さを255文字に制限し，最大2GBまでのパーティションをサポートしました．

extファイルシステムは，MINIXファイルシステムが抱えていた問題を解決することができましたが，タイムスタンプという大きな欠点がありました．

各Linuxファイルが3つのタイムスタンプ（アクセスタイムスタンプ，修正タイムスタンプ，変更タイムスタンプ）を持つ今日とは異なり，extファイルシステムは1ファイルにつき1つのタイムスタンプしか保持しませんでした．

Fast File System（FFS）

Fast File System（FFS）は，1984年にMarshall Kirk McKusick等により開発されたBSD UNIXのファイルシステムです（上図）．

FFSの特徴は，シリンダグループと呼ばれる1つ以上の連続したシリンダを実装したことです．

シリンダグループは，以下のメリットがあります．

• シーク時間を短縮するためのディスクブロック割り当てのヒューリスティックスを実現
• inodeとアソシエイトデータを同じシリンダグループに配置

多くのインプレースアップデート（稼働中に更新可能な）ファイルシステムは，FFSの設計を踏襲しています．

FFSの解説動画はこちらです．

ext2ファイルシステム

ext2ファイルシステムは，最初のLinuxファイルシステム（ext）の2番目の拡張版で，1993年1月に開発されました（上図）．

ext2ファイルシステムの設計は，BSD UNIXのFFSの影響を受けています．

ブロックグループ（シリンダーグループと同様）によりディスクシーク時間を短縮することができます．

ext2ファイルシステムは，ファイルシステムの機能を拡張しつつ，内部構造を保持することを可能にしました．

ファイルのデータは，同じ長さのデータブロックで保持され，順番に格納されます．

最初のブロックはブートセクターとして予約されています（ファイルシステムで管理されない）．

ext2パーティションの残りの部分は，ブロックグループに分割されます．

ext2ファイルシステムは，最大ファイルサイズ2TiBをサポートします．

ファイル名の長さは文字数ではなくバイト数で制限されており，255バイトです．

ext2ファイルシステムは，ジャーナリングをサポートされていないため，オーバーヘッドが低く，性能が向上しやすいです．

なので，現在ではUSBデバイスに時々使用されます．

ext2ファイルシステムを構成する要素は以下になります．

superblockはファイルシステムを記述する情報を格納します．

• ブロックサイズ
• inodeとブロックの数
• ファイルシステム内の空きブロック数

また，各ブロックグループは，リカバリ用にスーパーブロックのコピーを持ちます．

group descriptorは，各ブロックグループの情報を記述します．

• ブロックグループ内の空きブロック数
• 空きinode
• グループ内の使用ディレクトリ

inode bitmapは，inodeの使用状況を要約した情報を管理します．

• 0：空き
• 1：使用中

例えば，inodeビットマップの100ビット目は，inodeテーブルの100番目のinodeの使用状況を表します．

block bitmapは，data blockの使用状況を要約した情報を管理します．

• 0：空き
• 1：使用中

例えば，blockビットマップの100ビット目は，blockグループの100番目のdata blockの使用状況を表します．

inode tableは，固定サイズのinodeの配列で，inode番号＝ブロックグループの開始inode番号＋inodeテーブルのinode位置を表します．

data blockは，実際のデータ内容です．

inode indirect block mapは，ファイルオフセットからディスクブロックアドレスマッピングです．

directoryはリンクリストで管理するため，ファイル数が多い場合のディレクトリアクセスの性能が低いです．

ext2ファイルシステムで/home/chishiro/hello.cをopen関数でファイルをオープンする方法は，「/ -> home/ -> chishiro/ -> hello.c」の順番になります．

どこからオープンするかというと，linux/fs/ext2/ext2.hにある以下のspecial inode numbersを参考にします．

ext2ファイルシステムは広く使用されましたが，2つの大きな問題がありました．

• ファイルの破損：停電やシステムクラッシュの際にデータがディスクに書き込まれると，この現象が発生します．
• 性能の低下：ディスクの断片化は，1つのファイルが断片化され，ディスク上の複数の場所に分散されることで発生します．その結果，ファイルの読み書きに時間がかかり，性能の低下を招きます．

ext3ファイルシステム

ext3ファイルシステムは，ジャーナリングをext2ファイルシステムに統合し，突然のシステムクラッシュやパワーオフの後でもファイルシステムの一貫性を保証します（上図）．

また，ext3ファイルシステムは，Stephen Tweedieにより開発され，2001年11月にLinuxカーネル2.4.15にマージされ，現在でも利用されています．

ジャーナリングとは，データベースシステムにおけるログ先行書き込み（WAL：Write Ahead Log）のことです．

ディスクを更新するとき，その場の構造を上書きする前に，まずよく知られた場所に何をしようとしているのかを書き留めます．

ジャーナリングは論理的な固定サイズのリングバッファで構成されています（上図）．

ハードコードされたinode番号を持つ特別なファイルとして実装されます．

各ジャーナルトランザクションは，開始マーカー，ログ，および終了マーカーで構成されます．

ジャーナリングはCommitとCheckpointingから構成されます．

Commitは以下の手順で実行します．

1. トランザクション開始マーカーを書き込む
2. ログを書き込む
3. バリアを書き込む
4. トランザクション終了マーカーを書き込む

Checkpointingは，ジャーナルトランザクションがディスクに書き込まれたことを確認したら（つまりCommit），元のデータを更新する準備が整ったということです．

ジャーナリングのリカバリは以下の2ケースになります．

• ケース1：ジャーナルコミットとチェックポイントの間に障害が発生した場合
  • ジャーナルの末尾にトランザクション終了マーカーがある場合，開始マーカーと終了マーカー間のログは整合性があるという意味になる．
  • 最後のジャーナルトランザクションのログを再生する．
• ケース2：ジャーナルコミット前の失敗
  • ジャーナルの末尾にトランザクション終了マーカーがない場合，開始マーカーと終了マーカー間のログが整合している保証はないという意味になる．
  • 最後のジャーナルトランザクションを無視する．

ジャーナリングのモードは以下の3つになります．

• Journal：メタデータとコンテンツをジャーナルに保存する．
• Ordered（デフォルト）：メタデータのみをジャーナルに保存する．メタデータは，コンテンツをディスクに書き込んだ後にジャーナリングされる．
• Writeback：メタデータのみをジャーナルに保存する．メタデータは，コンテンツをディスクに書き込む前または後のいずれかにジャーナリングされる場合がある．

ext3ファイルシステムの解説動画はこちらです．

ext4ファイルシステム（Linuxカーネルでデフォルト）

ext4ファイルシステムは，現在のLinuxカーネルのデフォルトのファイルシステムです．

2008年10月にLinuxカーネル2.6.28で導入されました．

ext4ファイルシステムは，最大ファイルサイズ16TiBをサポートし，最大ファイル長を255バイトに制限しています．

64ビットでより大きなファイルシステム容量に対応しています．

巨大なファイルサイズ（16GB～16TB）とファイルシステム（\(2^{32}\)～\(2^{64}\)ブロック）をサポートします．

ディレクトリに最大64,000のサブディレクトリを格納可能（ext3では32,000）です．

ext4ファイルシステムの主要な機能は以下になります．

• エクステント（extent）
• HTree

extent

ext4ファイルシステムでは，indirect block mapからextentに変更されました．

indirect block mapは，非常に非効率で，1024ブロックごとに1ブロック余分に読み込みとシークするため，大きなムービーファイルを削除する際に顕著になります．

これに対して，extentは，大きなファイルを効率的に表現する方法で，連続するブロックの範囲に対する単一の記述子なため効率的に処理できます．

例えば，「{file block offset, length, disk block address} = {100, 1000, 200}」の場合です．

indirect block mapとextent mapの違いは下図になります．

extentに関連して以下の機能が追加されています．

• Multiple block allocation：連続したブロックをまとめて割り当てる．フラグメンテーションやextentメタデータを削減する．
• Delayed allocation：ブロックの割り当てをwrite back時間まで遅延する．連続ブロックの割り当て確率を向上させ，フラグメンテーションを削減する．

HTree

ext4ファイルシステムでは，リストからHTreeに変更されました．

HTreeは，ハッシュ化されたB木で，ディレクトリ内のファイル名のハッシュ値をキーとしています．

HTreeは，ext3ファイルシステムではdir_index機能が有効な場合に利用可能ですが（オプション），ext4ではデフォルトで利用しています．

Htreeを利用することで，性能低下を回避することができます．

B木の解説動画は以下がわかりやすいです．

ext4ファイルシステムの制限事項と解決できるファイルシステム

ext4ファイルシステムは，Linuxディストリビューションに最適なファイルシステムとして考えられていますが，システムのさらなる開発において考慮すべきいくつかの制限があります．

• 破損したデータのリカバリ：ext4ファイルシステムは，ディスク上に既に書き込まれた破損したデータを検出したり回復したりすることはできません．
• 最大ボリュームサイズ：最大ボリュームサイズは1 EiBに設定されています．しかし，ファイルシステムは，性能の大幅な低下とディスクの断片化の増加なしに，100TiBを超えるデータを扱うことはできません．

ext4ファイルシステムには，いくつかの代替手段があります．

Linuxカーネルは，以下に挙げるすべての代替システムをサポートしています．

• eXtents File System（XFS）
• OpenZFS
• B-tree file system（BtrFS）
• Journaling Flash File System2（JFFS2）

eXtents File System（XFS）

eXtents File System（XFS）は，1994年に発表され，2001年からLinuxカーネルにマージされた64ビットファイルシステムです．

また，XFSは，RedHat Linuxのデフォルトのファイルシステムです．

XFSは最大ファイルサイズ8 EiBをサポートし，ファイル名の長さを255バイトに制限しています．

ジャーナリングをサポートし，ext4ファイルシステムのようにメインファイルシステムに変更がコミットされる前にジャーナルに変更を保存するため，ファイルが破損する可能性が低くなります．

データはB+木で構造化され，効率的なスペース割り当てが行われるため，性能が向上します．

XFSの主な欠点は，既存のXFSのサイズ変更処理が困難であることに反映されています．

XFSの解説動画はこちらです．

OpenZFS

OpenZFSは，2013年に初めて導入されたファイルシステムとボリュームマネージャを組み合わせたプラットフォームです．

OpenZFSは，最大ファイルサイズを16 EiBにサポートし，ファイル名の長さを255文字に制限しています．

OpenZFSの特徴は，データの破損に対する保護，暗号化，大容量ストレージのサポート，コピーオンライト，RAID-Zなどがあります．

OpenZFSの主な欠点は，CDDL（OpenZFS）ライセンスとGPL（Linuxカーネル）ライセンスの間に法的な非互換性があることです．

これは，ZFSのコードをLinuxカーネルにコンパイルしてロードすることで解決されます．

OpenZFSの解説動画はこちらです．

B-tree file system（BtrFS）

B-tree file system（BtrFS）は，Oracle社が開発し，2009年にLinuxカーネル2.6.29にマージされたファイルシステムです．

BtrFSは最大ファイルサイズ16 EiBをサポートし，ファイル名の長さを255文字に制限しています．

BtrFSの特徴は，コピーオンライト，オンラインデフラグ，オンラインブロックデバイスの追加と削除，RAIDのサポート，ファイルまたはボリュームごとに設定可能な圧縮，ファイルのクローン，チェックサム，スワップファイル，スワップパーティションを扱う機能などが挙げられます．

BtrFSの解説動画はこちらです．

Journaling Flash File System2（JFFS2）

Journaling Flash File System2（JFFS2）は，JFFSの後継として開発されたLinux向けNAND型フラッシュメモリ用ログ構造ファイルシステムです．

JFFS2は，2001年9月にLinuxカーネルのバージョン2.4.10にメインラインにマージされました．

JFFS2は，Das U-Boot，Open Firmware，eCos，RTEMS，RedBootなどのいくつかのブートローダーで利用できます．

ファイルシステムのクラッシュ整合性（Crash Consistency）

ファイルシステムのクラッシュ整合性（Crash Consistency）を紹介します．

具体的には，以下の内容を解説します．

• クラッシュ整合性
• ジャーナリングファイルシステム
• ログ構造ファイルシステム
• コピーオンライトファイルシステム

クラッシュ整合性

クラッシュの整合性の問題は以下になります．

• 1つのファイルシステム操作で複数のディスクブロックを更新：古典的なストレージデバイスのインタフェースはブロックベースで，多くの書き込みを行うことができるが，一度に処理されるのは1ブロックのみです．
• 操作の途中でシステムがクラッシュする可能性がある：あるブロックは更新され，あるブロックは更新されないため，一貫性のないファイルシステムになってしまう．
• クラッシュ後，ファイルシステムを修復する必要がある：ブロック間の整合性をリカバリする必要がある．

ファイルの操作

例えば，ファイルの追加方法を考えてみましょう．

上図を以下の手順で実行します．

1. 新しいデータブロック（ブロックビットマップ）を確保
2. データブロックにユーザデータを格納（データブロック）
3. データブロックの位置の記録（inode）
4. 最終更新時刻の更新（inode）

次に，ファイルの名前を変更する場合を考えてみましょう．

上図を以下の手順で実行します．

1. /data/(ディレクトリ)のlog.txtを削除
2. data/（inode）の最終更新時刻を更新
3. log0.txtを/tmp/（ディレクトリ）に追加
4. tmp/（inode）の最終更新時刻を更新

クラッシュ整合性の問題の根本原因は，従来のストレージデバイスでは，複数ブロックの更新はアトミックではないことです．

つまり，1回のファイルシステム操作で複数のディスクブロックが更新され，操作の途中でシステムがクラッシュする可能性があります．

クラッシュ整合性の解決方法

クラッシュ整合性の解決方法を2つ紹介します．

解決策1は，怠惰で楽観的なアプローチで，再起動時に不整合を修正し，データを直接更新することです．

• メリット：シンプルで高性能
• デメリット：リカバリにコストがかかる

例えば，fsckを使ったext2です．

解決策2は，熱心で悲観的なアプローチで，データのコピーを維持することです．

• メリット：迅速な復旧
• デメリット：永続的な性能低下

例えば，以下の方法になります．

• ロギング：ext3/ext4，XFS
• コピーオンライト：btrfs，ZFS，Write Anywhere File Layout（WAFL）
• ログ構造書き込み：Flash-Friendly File System（F2FS）

ジャーナリングファイルシステム

ジャーナリングファイルシステムを理解するために必要なロギング方法のUNDO（元に戻す）とREDO（UNDOで一旦取り消した操作をやり直す）を解説します．

UNDOとREDOの比較は下表になります．

項目	UNDO	REDO
別名	ロールバックジャーナリング	Write Ahead Log（WAL）ジャーナリング
ロギング	変更（古いコピー）を取り消す方法	変更点の再現方法（新規コピー）
リード	元の場所からリード	新しいコピーがあれば，ログからリード

ジャーナリングファイルシステムとは，クラッシュしてもアトミックアップデートを実現するためにREDOロギングを使用するファイルシステムのことです．

REDOロギング = WAL = ジャーナリングを意味します．

更新待ちの情報を記録（ロギングまたはジャーナリング）し，更新中にクラッシュが発生しても，ログにあるものを再生するだけで修復可能（リカバリー）にする．

つまり，複数の書き込みをアトミックな動作に変えます．

基本プロトコルは以下になります．

• Logging：ジャーナルに書き込む（書きかけのものを記録する）
• Checkpoint：主要構造体へ書き込む（最終的な位置への情報記録）

クラッシュした場合，ログから復旧します．

つまり，ログを再生し更新を終了します．

次に，（バグありの）基本ジャーナリングプロトコルを紹介します．

書き込みプロトコルは以下の手順になります．

1. トランザクション開始+内容
2. トランザクションのcommit
3. checkpointの内容

読み出しプロトコルは以下の設計があります．

1. ログにブロックがある場合は，ログを読み込む．それ以外の場合は，元の場所からコンテンツを読み込む．
2. ジャーナリングされたページはチェックポイントまで退避させない．ページキャッシュまたは元の場所から内容を読み出す．

なぜ上記のプロトコルがバグなのかというとディスクキャッシュがあるからです．

最近のHDD/SSD等のディスクキャッシュは，性能にとって重要です．

読み出し時のキャッシュトラック，物理記憶媒体にコミットする前に書き込みをバッファします．

バッファリングが重要な理由は，（一部のワークロードの場合）性能が2倍以上になるからです．

上図に示すように，正しいジャーナリングの書き込みプロトコルは以下の手順になります．

正しいジャーナリングの書き込みプロトコルでは，「トランザクションの開始と終了前にフラッシュする」ことが必須となります．

1. （オプション）ディスクキャッシュのフラッシュ（ライトバリア）
2. トランザクション開始+内容
3. ディスクキャッシュフラッシュ（ライトバリア）
4. トランザクションのcommit
5. checkpointの内容

Linuxのジャーナリングファイルシステムは，ほぼ全ての主要なファイルシステム（ext3/ext4，XFS等）で利用されています．

※OpenZFSとBtrFSはコピーオンライトファイルシステムです．

ログ構造ファイルシステム

ログ構造ファイルシステムは，データやメタデータをログと呼ばれるリングバッファにシーケンシャルに書き込むファイルシステムです．

ログ構造ファイルシステムの特徴は，ディスクスペース全体をログとして扱うことです．

1988年にはじめてJohn K. OusterhoutとFred Douglisが設計を提案し，1992年にOusterhoutとMendel RosenblumがSpriteというUNIX系分散OS用に実装しました．

Spriteでログ構造ファイルシステムを実装した論文は，「The design and implementation of a log-structured file system」です．

Spriteを含む代表的な分散OSを知りたいあなたはこちらからどうぞ．

ほとんどのシステムは，最近アクセスされたブロックを保持するためにディスクブロックをキャッシュするのに十分な大きさのメモリを持っています．

したがって，ほとんどの読み出しはページキャッシュから行われます．

ディスクの観点から，ほとんどのトラフィックは書き込みトラフィックですので，ディスクI/Oを高速化するためには，書き込みを高速化する必要があります．

しかし，ディスクの性能は，最終的にはディスクヘッドの移動（シーク時間）によって制限されます．

現在のファイルシステムでは，ブロックを追加する際に（ファイルとメタデータに）何度か書き込みを行い，何度かディスクをシークする必要があります．

代替案として，ディスクをログとして使用する方法もあります．

ログはヘッドにのみ書き込まれるデータ構造です．

ディスクをログとして管理すれば，書き込みのためのヘッドシークは事実上不要になります．

ファイルは常にシーケンシャルに追加されます．

新しいデータとメタデータ（inodeやdirectory）はバッファキャッシュに蓄積され，大きなブロック（例えば0.5Mや1Mのセグメント）で一度に書き込まれます．

これにより，ディスクのスループットが大幅に向上します．

• inode：UNIXのように，inodeはファイルオフセットとディスクブロックのマッピングを維持．
• inode map：各inodeがディスク上のどこにあるかを示すテーブル．inode mapのブロックは，セグメントの一部として書き込まれる．
• segment：ブロックの固定サイズの大きな塊（例：0.5M，1M）
• segment summary：セグメント内の各ブロックに関する情報．
• segment usage table：ブロック内のライブデータ量に関する情報．
• checkpoint region：チェックポイント（通常30秒に一度程度）で，inode mapの最後の既知のブロック位置と現在のセグメント番号をディスク上の固定位置（チェックポイント領域）に書き込み．
• superblock：ログ構造ファイルシステムの静的構成．

ログ構造ファイルシステムの読み出しはUFSと変わらず，一度ファイルのinodeを見つけると以下の手順でデータを読み込みます．

1. 固定位置のcheckpoint region
2. inode map
3. inode
4. inode offset
5. disk block mapping

ログ構造ファイルシステムの書き込みでは，メモリ上の現在のセグメントバッファに新しいブロックが追加されます．

そのセグメントが一杯になると，ディスクに書き込まれます．

上書きにより，上書きされた前のブロックは廃止されます．

• live block：新たに書き込まれたブロック
• dead block：時代遅れ，上書きされたブロック

時間が経つと，古いブロックのファイルを新しいブロックに置き換えるので，ログのセグメントは断片化します．

定常状態では，書き込むための連続した空き領域が必要です．

ログ構造ファイルシステムの主要な問題は，セグメントクリーニング（またはガベージコレクション），つまりディスク上に連続した空き領域を作ることです．

クリーナープロセスは古いセグメントをクリーニングします．

つまり，完全でないセグメントをいくつか取り，それらをコンパクトにして，1つの完全なセグメントと空き領域を作成します．

クリーニングするセグメントを選択する方法として，クリーナーは以下の基準でディスク上のセグメントを選択します．

• セグメントの利用率（segment utilization）：利用率が高い（live blockが多い），つまりコピーのオーバーヘッドが大きい．
• 年齢（age）：最近書き込まれたセグメントは，すぐに変更される可能性が高い．

ログ構造ファイルシステムにおけるクラッシュ整合性として，クリーナー処理でディスクブロックがクリーニングされるまでは，ディスクブロックの更新履歴が残ります．

つまり，特別な一貫性保証機構は必要ありません．

Linuxのログ構造ファイルシステムとして以下が挙げられます．

• Flash-Friendly File System（F2FS）：NANDフラッシュSSDに最適化されたログ構造ファイルシステムでモバイル機器に利用．
• New Implementation of a Log-structured File System（NILFS）：連続スナップショットファイルシステム．

また，ログ構造ファイルシステムの設計はファイルシステム以外にも広く採用されています．

例えば，NANDフラッシュSSDのファームウェアであるFlash Translation Layer（FTL）は，NANDフラッシュ媒体の複雑さを隠蔽し，一つのファイルを管理するログ構造ファイルシステムの一種です．

コピーオンライトファイルシステム

コピーオンライトファイルシステムは，1994年のUSENIX WinterでDave Hitz，James Lau，Michael Malcolmによる論文「File System Design for an NFS File Server Appliance」で発表されました．

コピーオンライトファイルシステムの特徴は，NetAppストレージアプライアンスの中核設計であるWrite Anywhere File Layout（WAFL）です．

コピーオンライトファイルシステムは，ログ構造ファイルシステムからインスパイアされた設計です．

• ログ構造ファイルシステムのようにブロックの上書きをしない
• ログ構造ファイルシステムのようにセグメントクリーニングを行わない

コピーオンライトファイルシステムのキーアイデアは，ファイルシステムを1つの木として表現し，ブロックを上書きしない（Copy-on-Write）ことです．

WAFLレイアウトはブロックのツリーです（上図）．

• root inode：すべてのルートを表す．
• inode file：すべてのinodeを含む．
• block map file：空きブロックを示す．
• inode map file：空いているinodeを示す．

メタデータをファイルに保存する理由は以下になります．

• メタデータブロックをディスク上の任意の場所に書き込めるようにする：これが「Write Anywhere File Layout」の原点である．
• ファイルシステムのサイズを動的に増加させることが容易にする：ディスクを追加すると，inodeの追加につながる．
• コピーオンライトを有効にしてスナップショットを作成できる：新しいデータとメタデータを新しいディスクの場所にコピーオンライトする．メタデータの位置が固定されるのは面倒である．

WAFLの読み出しは，Unixのファイルシステムと同じで，ファイルのinodeを見つけると以下の手順で実行します．

1. root inode
2. inode file
3. inode
4. inode file offset
5. disk block mapping

WAFLの書き込みにおいて，WAFLファイルシステムはブロックの木と表現します（上図）．

ブロックの上書きをしないため，コピーオンライトになります．

コピーオンライトファイルシステムにおけるクラッシュ整合性において，各root nodeは，ファイルシステムの一貫したスナップショットを表します．

Linuxにおけるコピーオンライトファイルシステムは以下になります．

• BtrFS：ファイルシステムは4つのコピーオンライトで最適化されたB木である
• ZFS：Solarisのデフォルトファイルシステム

※OpenZFSはZFSのオープンソース版です．

まとめ

今回はファイルシステムとクラッシュ整合性を紹介しました．

ext4ファイルシステムを含む多くのファイルシステムの特徴と，クラッシュ整合性をどのように解決しているのかがわかりました．

ファイルシステムやクラッシュ整合性を深掘りしたいあなたは，以下を読みましょう！

• Introduction to the Linux File System
• Ext4: The Next Generation of Ext2/3
• Outline of Ext4 File System & Ext4 Online Defragmentation Foresight
• Ext4 Disk Layout
• An introduction to Linux's EXT4 filesystem
• ext4 General Information
• ext4 Data Structures and Algorithms
• JFTL: A flash translation layer based on a journal remapping for flash memory
• extents and 48bit ext3
• Optimistic crash consistency
• Consistency Without Ordering
• Lightweight Application-Level Crash Consistency on Transactional Flash Storage
• SFS: Random Write Considered Harmful in Solid State Drives
• The design and implementation of a log-structured file system
• File System Design for an NFS File Server Appliance
• How Do SSDs Work?
• Disk buffer

以下の動画もおすすめです！

LinuxカーネルはC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

次回はこちらからどうぞ．