 学习笔记：文件系统实现——从 FAT、ext2 到现代 B-Tree 黑科技)
写在前面这是本系列的第二十三篇。文件系统为我们实现了树和图状的目录结构并提供了丰富的 API 让我们实现增删改查。实际上文件系统就是在底层存储系统Block I/O块设备之上实现的一个支持修改、查询操作的数据结构。本讲内容我们将化身文件系统的架构师探索如何在极度受限的磁盘块上设计数据结构从 1980 年代的 FAT 文件系统一路演进到现代文件系统的终极形态。什么是文件系统Block devices (块设备)… 以块为单位进行read和write的设备。块设备上的数据结构 Abstract DataType (ADT)文件系统的本质就像我们在内存里设计数据结构一样。只不过底层的介质不是 Random Access Memory (RAM)而是 Block I/O (块设备)。内存里的new/delete非常快但在 M5 (mymalloc) 实验中大家可能没考虑过物理“块”的问题而在磁盘上读写放大是致命的。// 在 C 的视角下文件系统就是这样一棵多态的对象树structFSObject{virtual~FSObject()default;};structFile:FSObject{vectorcharcontent;// 字节序列};structDirectory:FSObject{mapstring,unique_ptrFSObjectchildren;// 目录包含子对象};用块设备虚拟块设备 (LVM)Logical Volume Manager (LVM逻辑卷管理器)LVM 支持一些极其极客的骚操作… 比如瞬间打快照、无缝热扩容。今天的文件系统可以扩容了AI 时代的正确解决方法我们需要知道的仅仅是“什么可以做”。有一天你在公司的服务器上看到了 LVM。你多嘴问一句LVM 可以做什么世界上的技术知识已经多到“不可能全部搞清楚”了但这不妨碍我们很好地使用它们。遇到问题“我有一个 LVM vg1如何将分区扩容到 100%”AI 会精准提供有效的命令线索vgdisplay,lvextend,resize2fs。Anyway, LVM 在操作系统的眼里它依旧只是一个被虚拟出来的块设备。File Allocation Table (FAT)我们要如何在块设备上实现这个巨大的“数据结构”实现文件系统敌人和朋友敌人读/写放大存储设备的物理特性被迫只能读写连续的一块数据通常是 512B 或 4KB。不能像 Memory Hierarchy 那样随心所欲地操作单字节。朋友局部性适当地排布数据使得临近的数据有“一同访问”的倾向。允许数据暂时停留在内存Buffer Cache延迟写回磁盘。需求分析时间回到 1980 年5.25 软盘单面 160 KiB一共只有 320 个 512B 扇区 (sectors)。在这样简陋的设备上实现文件系统应该选用怎样的数据结构系统特征相当小的文件系统。目录中一般只有几个、十几个文件。以小文件为主 (都在几个 block 以内)。文件的实现方式本质上就是struct block *的链表。任何复杂的高级数据结构比如 B 树在这里都显得极其浪费。目录的实现方式目录就是一个普通的文件被称为“目录文件”操作系统会把它的内容解读成struct dentry[]数组。用链表存储数据两种设计抉择1. 在每个数据块的末尾放置 Next 指针优点实现简单、无须单独开辟全局存储空间。缺点数据的大小不再是 $ 2^k $如果 block size 为 512可用数据区就只剩 508 字节。这会导致跨块拷贝极其痛苦。lseek读放大极其严重想读文件的最后一个字节必须把前面的所有块全读一遍才能顺藤摸瓜找到最后2. 将所有指针集中存放在文件系统的某个独立区域优点局部性极好lseek可以在内存里瞬间算完速度飞快。缺点集中存放的数据一旦损坏整个磁盘的数据链将彻底丢失微软的选择FAT (集中保存所有指针)先算一笔账160 KB 的软盘320 个扇区。用 12-bit entryFAT12来存指针总共只要 480B。惊人事实只需要 1 个扇区就能存下整个磁盘的next[]数组哪怕容量翻倍也就 2 个扇区。File Allocation Table (文件分配表)既然这么小那就在内存里直接缓存一份 FAT 数组的副本反正读一次磁盘也是最少读 512B。有了内存缓存结合延迟写回读/写放大的问题就完全解决了FAT 链接存储文件的原理int next[];next[i] 0: Free (本块未分配)。next[i] -1: EOF (本块是文件的最后一个块)。可靠性问题的补救集中存储容易坏那就连续存 $ n $ 份副本通常是 FAT1 和 FAT2 两份目录树实现目录文件目录就是个普通文件。只是在 metadata 里打了个标记 (mode directory)。DOS 时代的经典“8 3” 文件名规范如AUTOEXEC.BAT。文件名最多 8 个字符扩展名 3 个字符默认中间有一个点。历史的包袱总有一天8 3 文件名会不够用的比如你想存一个长长的 MP3 名字。微软想出的补丁极其猥琐用连续的几个“短目录项”强行拼凑成一个长文件名VFAT。极客实践直接观察与恢复 FAT所谓“快速格式化”mkfs.fat其实就是把 FAT 表清空而已。所有的文件内容包括目录文件里的数据都还在磁盘的 Data 区里只是在数据结构眼里它们变成了无人认领的 “free block”。数据恢复软件的原理猜出文件系统的参数SecPerClus,BytsPerSec然后全局扫描特征码强行把断掉的next关系拼接回来FAT 性能与可靠性总结性能优势对小文件简直太合适了极其轻量。劣势大文件的随机访问是灾难。4 GB 的文件假设 4 KB 一个 cluster想跳到末尾必须在内存里的 FAT 数组执行 $ 2^{20} $ 次next追溯操作。在 FAT 时代磁盘使用久了会产生严重的碎片 (fragmentation)需要用“磁盘碎片整理程序”跑上一整夜。UNIX 文件系统 (ext2 家族)我们想要一个更好的文件系统基于真实世界的统计观察大多数文件都很小约 2K 是最常见的。大多数的磁盘空间却被少数极其巨大的文件占据数据库、视频等。目录通常都很小大部分目录包含的文件不到 20 个。启示如果目录项 20顺序遍历数组的性能远好于维护复杂的 B 树。UNIX 文件系统的改进iNode改进 1支持硬链接文件系统的拓扑从 树 $ \rightarrow $ 图。允许一个底层物理文件存在多份引用。因此struct node(数据本身) 和struct edge(目录里记录的文件名) 必须分家改进 2支持大文件$ O(1) $随机读写UNIX 引入了“iNode” (index node索引节点)的概念。它保存了所有的元数据Mode,Links,User/Group,Size,Time。核心它内部包含了一个多级索引的数据结构类似于mapint,int映射file offset$ \rightarrow $block id。ext2联合数据结构 (Fast/Slow Path)“Superblock (超级块)”记录文件系统全局的元数据inode 总数量、block 大小等。ext2 iNode 极具智慧的索引设计直接块 (Direct blocks):指针直接指向数据块用于满足绝大多数的小文件极速读取。间接块 (Indirect / Double / Triple blocks):当文件很大时指针指向的是一个“存满指针的块”。通过二级、三级树状索引轻松支撑起 TB 级别的巨型文件并实现 $ O(1) $ 复杂度的随机寻址。ext2 目录文件在目录文件上实现的数据结构本质上就是一个mapstring,int(将文件名映射到 inode 号)。ext2 性能与局限局部性与缓存bitmap 和 inode 都有集中存储的局部性可通过内存缓存大幅减少读写放大。大文件友好极速的 $ O(1) $ 随机读写inode 在磁盘上连续存储便于预取。致命弱点可靠性依然是短板。存储 inode 的核心数据块一旦损坏整个文件就灰飞烟灭了。系统断电极易造成文件系统不一致后来 ext3/ext4 引入了日志 Journaling 来拯救它。现代文件系统 (Spicy ️)既然文件系统就是存储器上的数据结构那黑客们玩的花活可就太多了比如引入 Persistent data structure, learned index…1. 数据结构不一定要写在内核里 (FUSE)FUSE: Filesystem in Userspace (用户态文件系统)违背祖宗的决定文件系统不在内核态跑而在用户态跑内核里只放一个很小的FUSE Kernel Module负责转发协议 (/dev/fuse)。开发者直接用普通的 C/Python/Go 代码调用libfuse就能手搓一个文件系统。极其适合开发网盘挂载工具如 macFUSE。// 在用户态只需要实现这几个业务函数你就能造一个文件系统structfuse_operationsnull_oper{.getattrnull_getattr,.truncatenull_truncate,.opennull_open,.readnull_read,.writenull_write,};2. Everything is a B-Tree (btrfs)B-Tree Filesystem (btrfs)反正只要“实现文件系统 API”就行那干脆把整个底层换成极其强悍的 B 树彻底解决碎片问题并顺带白嫖了无敌的高级特性热扩缩容 (resize)、透明数据压缩、以及做快照不花钱得益于 B 树的 Copy-on-Write 机制。Btrfs 的特点快照可以瞬间创建文件系统的快照不消耗额外空间方便备份和恢复。原生 RAID 支持内置软件 RAID 控制提高数据可靠性。在线修复可以在线检查和修复底层错误无需卸载重启。3. 针对特定硬件极限优化的现代 FSFlash-Friendly Filesystem (f2fs):华为/三星等手机里常用的底层文件系统专为 NAND Flash 的擦写特性磨损均衡、避免随机小写操作量身定制极大地延长了闪存寿命并减少卡顿。Enhanced Read-only Filesystem (erofs):华为开源的只读文件系统。利用透明压缩技术极限压缩系统分区的大小专门为安卓系统的只读系统镜像优化读取速度快得惊人。总结Take-away messages:把文件系统理解成一个持久化设备上的“数据结构”我们就不难理解从古典时代到现代文件系统各种眼花缭乱的设计理念了。本质上所有的文件系统都是在为了适配特定的硬件物理特性软盘、机械磁盘、SSD 闪存、特定的读写 Workload小文件碎片化、大文件吞吐用当时最聪明的方式去组织数据维护那棵迷人的树状目录结构并支撑起极其高效的文件随机访问。 南京大学 操作系统 (JYY) 学习笔记：文件系统实现——从 FAT、ext2 到现代 B-Tree 黑科技
写在前面这是本系列的第二十三篇。文件系统为我们实现了树和图状的目录结构并提供了丰富的 API 让我们实现增删改查。实际上文件系统就是在底层存储系统Block I/O块设备之上实现的一个支持修改、查询操作的数据结构。本讲内容我们将化身文件系统的架构师探索如何在极度受限的磁盘块上设计数据结构从 1980 年代的 FAT 文件系统一路演进到现代文件系统的终极形态。什么是文件系统Block devices (块设备)… 以块为单位进行read和write的设备。块设备上的数据结构 Abstract DataType (ADT)文件系统的本质就像我们在内存里设计数据结构一样。只不过底层的介质不是 Random Access Memory (RAM)而是 Block I/O (块设备)。内存里的new/delete非常快但在 M5 (mymalloc) 实验中大家可能没考虑过物理“块”的问题而在磁盘上读写放大是致命的。// 在 C 的视角下文件系统就是这样一棵多态的对象树structFSObject{virtual~FSObject()default;};structFile:FSObject{vectorcharcontent;// 字节序列};structDirectory:FSObject{mapstring,unique_ptrFSObjectchildren;// 目录包含子对象};用块设备虚拟块设备 (LVM)Logical Volume Manager (LVM逻辑卷管理器)LVM 支持一些极其极客的骚操作… 比如瞬间打快照、无缝热扩容。今天的文件系统可以扩容了AI 时代的正确解决方法我们需要知道的仅仅是“什么可以做”。有一天你在公司的服务器上看到了 LVM。你多嘴问一句LVM 可以做什么世界上的技术知识已经多到“不可能全部搞清楚”了但这不妨碍我们很好地使用它们。遇到问题“我有一个 LVM vg1如何将分区扩容到 100%”AI 会精准提供有效的命令线索vgdisplay,lvextend,resize2fs。Anyway, LVM 在操作系统的眼里它依旧只是一个被虚拟出来的块设备。File Allocation Table (FAT)我们要如何在块设备上实现这个巨大的“数据结构”实现文件系统敌人和朋友敌人读/写放大存储设备的物理特性被迫只能读写连续的一块数据通常是 512B 或 4KB。不能像 Memory Hierarchy 那样随心所欲地操作单字节。朋友局部性适当地排布数据使得临近的数据有“一同访问”的倾向。允许数据暂时停留在内存Buffer Cache延迟写回磁盘。需求分析时间回到 1980 年5.25 软盘单面 160 KiB一共只有 320 个 512B 扇区 (sectors)。在这样简陋的设备上实现文件系统应该选用怎样的数据结构系统特征相当小的文件系统。目录中一般只有几个、十几个文件。以小文件为主 (都在几个 block 以内)。文件的实现方式本质上就是struct block *的链表。任何复杂的高级数据结构比如 B 树在这里都显得极其浪费。目录的实现方式目录就是一个普通的文件被称为“目录文件”操作系统会把它的内容解读成struct dentry[]数组。用链表存储数据两种设计抉择1. 在每个数据块的末尾放置 Next 指针优点实现简单、无须单独开辟全局存储空间。缺点数据的大小不再是 $ 2^k $如果 block size 为 512可用数据区就只剩 508 字节。这会导致跨块拷贝极其痛苦。lseek读放大极其严重想读文件的最后一个字节必须把前面的所有块全读一遍才能顺藤摸瓜找到最后2. 将所有指针集中存放在文件系统的某个独立区域优点局部性极好lseek可以在内存里瞬间算完速度飞快。缺点集中存放的数据一旦损坏整个磁盘的数据链将彻底丢失微软的选择FAT (集中保存所有指针)先算一笔账160 KB 的软盘320 个扇区。用 12-bit entryFAT12来存指针总共只要 480B。惊人事实只需要 1 个扇区就能存下整个磁盘的next[]数组哪怕容量翻倍也就 2 个扇区。File Allocation Table (文件分配表)既然这么小那就在内存里直接缓存一份 FAT 数组的副本反正读一次磁盘也是最少读 512B。有了内存缓存结合延迟写回读/写放大的问题就完全解决了FAT 链接存储文件的原理int next[];next[i] 0: Free (本块未分配)。next[i] -1: EOF (本块是文件的最后一个块)。可靠性问题的补救集中存储容易坏那就连续存 $ n $ 份副本通常是 FAT1 和 FAT2 两份目录树实现目录文件目录就是个普通文件。只是在 metadata 里打了个标记 (mode directory)。DOS 时代的经典“8 3” 文件名规范如AUTOEXEC.BAT。文件名最多 8 个字符扩展名 3 个字符默认中间有一个点。历史的包袱总有一天8 3 文件名会不够用的比如你想存一个长长的 MP3 名字。微软想出的补丁极其猥琐用连续的几个“短目录项”强行拼凑成一个长文件名VFAT。极客实践直接观察与恢复 FAT所谓“快速格式化”mkfs.fat其实就是把 FAT 表清空而已。所有的文件内容包括目录文件里的数据都还在磁盘的 Data 区里只是在数据结构眼里它们变成了无人认领的 “free block”。数据恢复软件的原理猜出文件系统的参数SecPerClus,BytsPerSec然后全局扫描特征码强行把断掉的next关系拼接回来FAT 性能与可靠性总结性能优势对小文件简直太合适了极其轻量。劣势大文件的随机访问是灾难。4 GB 的文件假设 4 KB 一个 cluster想跳到末尾必须在内存里的 FAT 数组执行 $ 2^{20} $ 次next追溯操作。在 FAT 时代磁盘使用久了会产生严重的碎片 (fragmentation)需要用“磁盘碎片整理程序”跑上一整夜。UNIX 文件系统 (ext2 家族)我们想要一个更好的文件系统基于真实世界的统计观察大多数文件都很小约 2K 是最常见的。大多数的磁盘空间却被少数极其巨大的文件占据数据库、视频等。目录通常都很小大部分目录包含的文件不到 20 个。启示如果目录项 20顺序遍历数组的性能远好于维护复杂的 B 树。UNIX 文件系统的改进iNode改进 1支持硬链接文件系统的拓扑从 树 $ \rightarrow $ 图。允许一个底层物理文件存在多份引用。因此struct node(数据本身) 和struct edge(目录里记录的文件名) 必须分家改进 2支持大文件$ O(1) $随机读写UNIX 引入了“iNode” (index node索引节点)的概念。它保存了所有的元数据Mode,Links,User/Group,Size,Time。核心它内部包含了一个多级索引的数据结构类似于mapint,int映射file offset$ \rightarrow $block id。ext2联合数据结构 (Fast/Slow Path)“Superblock (超级块)”记录文件系统全局的元数据inode 总数量、block 大小等。ext2 iNode 极具智慧的索引设计直接块 (Direct blocks):指针直接指向数据块用于满足绝大多数的小文件极速读取。间接块 (Indirect / Double / Triple blocks):当文件很大时指针指向的是一个“存满指针的块”。通过二级、三级树状索引轻松支撑起 TB 级别的巨型文件并实现 $ O(1) $ 复杂度的随机寻址。ext2 目录文件在目录文件上实现的数据结构本质上就是一个mapstring,int(将文件名映射到 inode 号)。ext2 性能与局限局部性与缓存bitmap 和 inode 都有集中存储的局部性可通过内存缓存大幅减少读写放大。大文件友好极速的 $ O(1) $ 随机读写inode 在磁盘上连续存储便于预取。致命弱点可靠性依然是短板。存储 inode 的核心数据块一旦损坏整个文件就灰飞烟灭了。系统断电极易造成文件系统不一致后来 ext3/ext4 引入了日志 Journaling 来拯救它。现代文件系统 (Spicy ️)既然文件系统就是存储器上的数据结构那黑客们玩的花活可就太多了比如引入 Persistent data structure, learned index…1. 数据结构不一定要写在内核里 (FUSE)FUSE: Filesystem in Userspace (用户态文件系统)违背祖宗的决定文件系统不在内核态跑而在用户态跑内核里只放一个很小的FUSE Kernel Module负责转发协议 (/dev/fuse)。开发者直接用普通的 C/Python/Go 代码调用libfuse就能手搓一个文件系统。极其适合开发网盘挂载工具如 macFUSE。// 在用户态只需要实现这几个业务函数你就能造一个文件系统structfuse_operationsnull_oper{.getattrnull_getattr,.truncatenull_truncate,.opennull_open,.readnull_read,.writenull_write,};2. Everything is a B-Tree (btrfs)B-Tree Filesystem (btrfs)反正只要“实现文件系统 API”就行那干脆把整个底层换成极其强悍的 B 树彻底解决碎片问题并顺带白嫖了无敌的高级特性热扩缩容 (resize)、透明数据压缩、以及做快照不花钱得益于 B 树的 Copy-on-Write 机制。Btrfs 的特点快照可以瞬间创建文件系统的快照不消耗额外空间方便备份和恢复。原生 RAID 支持内置软件 RAID 控制提高数据可靠性。在线修复可以在线检查和修复底层错误无需卸载重启。3. 针对特定硬件极限优化的现代 FSFlash-Friendly Filesystem (f2fs):华为/三星等手机里常用的底层文件系统专为 NAND Flash 的擦写特性磨损均衡、避免随机小写操作量身定制极大地延长了闪存寿命并减少卡顿。Enhanced Read-only Filesystem (erofs):华为开源的只读文件系统。利用透明压缩技术极限压缩系统分区的大小专门为安卓系统的只读系统镜像优化读取速度快得惊人。总结Take-away messages:把文件系统理解成一个持久化设备上的“数据结构”我们就不难理解从古典时代到现代文件系统各种眼花缭乱的设计理念了。本质上所有的文件系统都是在为了适配特定的硬件物理特性软盘、机械磁盘、SSD 闪存、特定的读写 Workload小文件碎片化、大文件吞吐用当时最聪明的方式去组织数据维护那棵迷人的树状目录结构并支撑起极其高效的文件随机访问。