(2021) 25 [持久化] 文件系統實現：FAT和UNIX文件系統

南京大學操作系統課蔣炎巖老師網絡課程筆記。

視頻：https://www.bilibili.com/video/BV1HN41197Ko?p=25
講義：http://jyywiki.cn/OS/2021/slides/15.slides#/

背景

回顧

應用眼中的文件系統：一組API

文件系統管理：mount
目錄管理：mkdir, rmkdir, link, symlink, unlink…
文件管理：open, mmap, read, write, lseek…

本次課的內容和目標

理解兩個文件系統的實現：

FAT
UNIX文件系統 / ext2

文件系統的實現：需求分析

例子：Linux文件系統的初始化

最小系統鏡像

最小的 Linux 系統鏡像

將上面的最小鏡像下載后解壓，構造 Linux 啟動時的 “根文件系統”，隨操作系統啟動加載，你可以像調試你的 oslab 一樣調試 Linux~！

initramfs
├── busybox
└── init

/busybox是個二進制文件
- ELF 64-bit LSB executable, statically linked
/init 只有 3 行，實際只做一件事: 執行 busybox：exec /busybox sh。

Linux 啟動第一個應用程序時的狀態

UNIX的SHELL實際上是將用戶的命令翻譯成了一系列系統調用

“幾乎什么也沒有”，但所有的一切都可以被系統調用 “創建” 出來，包括

mount - 文件系統管理
mkdir, rmkdir, link, symlink, unlink… - 目錄管理
open, mmap, read, write, lseek… - 文件管理

/busybox mkdir -p /bin && /busybox mv /busybox /bin/
c1="arch ash base64 cat chattr chgrp chmod chown conspy cp cpio cttyhack date dd df dmesg dnsdomainname dumpkmap echo ed egrep false fatattr fdflush fgrep fsync getopt grep gunzip gzip hostname hush ionice iostat ipcalc kbd_mode kill link linux32 linux64 ln login ls lsattr lzop makemime mkdir mknod mktemp more mount mountpoint mpstat mt mv netstat nice nuke pidof ping ping6 pipe_progress printenv ps pwd reformime resume rev rm rmdir rpm run-parts scriptreplay sed setarch setpriv setserial sh sleep stat stty su sync tar touch true umount uname usleep vi watch zcat"
c2="[ [[ awk basename bc beep blkdiscard bunzip2 bzcat bzip2 cal chpst chrt chvt cksum clear cmp comm crontab cryptpw cut dc deallocvt diff dirname dos2unix dpkg dpkg-deb du dumpleases eject env envdir envuidgid expand expr factor fallocate fgconsole find flock fold free ftpget ftpput fuser groups hd head hexdump hexedit hostid id install ipcrm ipcs killall last less logger logname lpq lpr lsof lspci lsscsi lsusb lzcat lzma man md5sum mesg microcom mkfifo mkpasswd nc nl nmeter nohup nproc nsenter nslookup od openvt passwd paste patch pgrep pkill pmap printf pscan"
c3="pstree pwdx readlink realpath renice reset resize rpm2cpio runsv runsvdir rx script seq setfattr setkeycodes setsid setuidgid sha1sum sha256sum sha3sum sha512sum showkey shred shuf smemcap softlimit sort split ssl_client strings sum sv svc svok tac tail taskset tcpsvd tee telnet test tftp time timeout top tr traceroute traceroute6 truncate ts tty ttysize udhcpc6 udpsvd unexpand uniq unix2dos unlink unlzma unshare unxz unzip uptime users uudecode uuencode vlock volname w wall wc wget which who whoami whois xargs xxd xz xzcat yes"
for cmd in $c1 $c2 $c3; do/bin/busybox ln -s /bin/busybox /bin/$cmd
done
mkdir -p /proc && mount -t proc  none /proc
mkdir -p /sys  && mount -t sysfs none /sys

文件系統的實現

在一個 I/O 設備 (驅動) 上實現 “目錄樹” 的數據結構。

VFS：管理所有文件系統共享的部分

對象 (inode) 分配/回收、路徑/符號鏈接解析、掛載
定義了每個具體文件系統需要實現的接口

具體的文件系統（如有設備的ext4，無設備的procfs）其實就是一組API，是將一個設備抽象成一棵樹的代碼。

利用塊設備驅動：read_block, write_block，得到目錄/文件 API：mkdir, rmdir, link, unlink, open, read, write, stat。

內存上的數據結構和磁盤上的數據結構

實際上，我們平時所談到的數據結構默認是內存上的數據結構，而文件系統相當于是在磁盤（更準確地說是 ”持久化的，不支持隨機讀寫的存儲設備“）上實現一種數據結構。

注意：我們的持久化存儲設備（磁盤、SSD等）不支持像內存RAM那樣的隨機訪問，即每次至少要訪問一個塊（如4KiB，512B）。

在內存上，我們擁有的API是訪問一個字（節）（如malloc / free），在磁盤上我們擁有的API是讀寫一個塊（read_block, write_block）, （可以稱為balloc, bfree）。在這些API的基礎上實現出我們想要的數據結構，實現出上面提到的文件、目錄、文件系統管理的API，那這就是文件系統。

FAT （File Allocation Table）

FAT是個簡單而古老的文件系統，基本所有平臺都支持這種文件系統。一路走來有FAT12，FAT16，FAT32，exFAT等。

需求

在很久很久以前，存儲設備的空間遠沒有今天這么大。如5.25" 軟盤：單面 180 KiB，360 個 512B 扇區 (sectors)，在這樣的設備上持久化數據，應該選用怎樣的數據結構？

拋開workload談優化，就是耍流氓。

需求：

樹狀的目錄結構
系統中以小文件為主 (幾個 block 以內)
無需支持鏈接

實現方式：鏈表。任何復雜的高級數據結構都顯得浪費。

用鏈表存儲數據：兩種設計

兩種選擇

在每個數據塊后放置指針
- 優點：實現簡單、無須單獨開辟存儲空間
- 缺點：數據的大小不是 $2^k$ ；單純的 lseek 需要讀整塊數據
將指針集中存放在文件系統的某個區域
- 優點：局部性好；lseek 更快
- 缺點：集中存放的數據損壞將導致數據丟失 (怎么辦？)

哪種方式的缺陷是致命、難以解決的？

集中保存所有指針

FAT文件系統選擇將指針集中存放在文件系統的某個區域，這個區域稱為File Allocation Table，這也正是FAT名稱的由來。

集中存儲的指針容易損壞？存 n 份就行！FAT-12/16/32 (FAT entry，即 “next 指針” 的大小)。

在這里插入圖片描述

“File Allocation Table” 文件系統

RTFM 得到必要的細節

邏輯上，文件/目錄都是字節序列 (虛擬化的磁盤)，以 cluster (簇) 為單位鏈接 (FAT 集中存儲鏈表的 next)。
目錄也是文件，一個 (filename, size, firstblock) 的列表，順序存儲。

struct fat_volume {struct fat_header header;struct fat[FAT_NUM];char clusters[CLUSTER_SZ][];
};

FAT: 鏈接存儲的文件

“FAT” 的 “next” 數組

0: free; 2...MAX: allocated;
ffffff7: bad cluster; ffffff8-ffffffe, -1: end-of-file

更細節的信息如圖。
在這里插入圖片描述

以普通文件的方式存儲 “目錄” 這個數據結構

FAT: 目錄 = 32-byte 定長目錄項的集合
操作系統在解析時把標記為目錄的目錄項 “當做” 目錄即可。另外，可以用連續的若干個目錄項存儲 “長文件名”。

FAT: 性能與可靠性

性能

優點：小文件簡直太合適了。
缺點：但大文件的隨機訪問就不行了，4 GB 的文件跳到末尾 (4 KB cluster) 就要有 220 次鏈表 next 操作，緩存能部分解決這個問題。
在 FAT 時代，磁盤連續訪問性能更佳（現在也是連續訪問更佳，但沒差那么多），使用時間久的磁盤會產生碎片 (fragmentation)，malloc 也會產生碎片，不過對性能影響不太大。

可靠性

維護若干個 FAT 的副本防止元數據損壞，有額外的同步開銷。
損壞的 cluster 在 FAT 中標記。

ext2 / UNIX 文件系統

思考：更好的文件系統，需要做到什么

怎樣才能支持更好的隨機訪問呢？

不能 “盡善盡美”，但可以在 “實際 workload” 下盡可能好。

Summary	Findings
Most files are small	Roughly 2K is the most common size
Average file size is growing	Almost 200K is the average
Most bytes are stored in large files	A few big files use most of the space
File systems contains lots of files	Almost 100K on average
File systems are roughly half full	Even as disks grow, file systems remain ~50% full
Directories are typically small	Many have few entries; most have 20 or fewer

ext2 / UNIX文件系統

ext2

按對象方式集中存儲文件/目錄元數據

增強局部性 (更易于緩存)
支持鏈接（名字不同，但是同一個文件）

為了支持鏈接，文件對象inode（包括文件元數據等）需要單獨存儲。
為大小文件區分 fast/slow path
- 小的時候應該用數組，連鏈表遍歷都省了
- 大的時候應該用樹 (B-Tree; Radix-Tree; …)，快速的隨機訪問

ext2磁盤鏡像格式

對磁盤進行分組：
在這里插入圖片描述

“superblock”：文件系統元數據

文件 (inode) 數量
block group 信息
- ext2.h 里有你需要知道的一切

ext2 innode

在這里插入圖片描述

ext2目錄文件

與 FAT 本質相同：在文件上建立目錄的數據結構。

注意到 inode 統一存儲，目錄文件中存儲文件名到 inode 編號的 key-value mapping。

在這里插入圖片描述

ext2性能與可靠性

大文件的隨機讀寫性能提升明顯 ( $O (1)$ )

支持鏈接 (一定程度減少空間浪費)
inode 在磁盤上連續存儲，便于緩存/預取
依然有碎片的問題

但可靠性依然是個很大的問題

存儲 inode 的數據塊損壞是很嚴重的，但現代的磁盤相對于FAT時代的軟盤，設備可靠性要好一些。

尋找更高效的數據結構 — BTRFS

btrfs: Everything is a B-tree

The BTRFS B-tree… knows only about “keys, items, and block headers.”
數據結構由多個 copy-on-write 的 tree 組成
- subvolume, extent allocation tree, checksum tree, chunk and device tree, reloc tree, …
- O. Rodeth, et al. BTRFS: The Linux B-tree filesystem. ACM Transactions on Storage (ToS), 9(3), 2013.

在這里插入圖片描述