为什么早期的 Windows 需要整理碎片
为什么这么设计（Why’s THE Design）是一系列关于计算机领域中程序设计决策的文章，我们在这个系列的每一篇文章中都会提出一个具体的问题并从不同的角度讨论这种设计的优缺点、对具体实现造成的影响。如果你有想要了解的问题，可以在文章下面留言。
记得十几年前还在用早期 Windows 系统的时候，每用一段时间系统都会变得很卡顿，这时候需要打开系统提供的下面的磁盘碎片整理程序，当碎片整理完成后会感觉到系统变得稍微流畅了一些。
图 1 - Windows 磁盘碎片整理程序
在文件系统中，碎片整理（Defragmentation）是减少文件系统中碎片的过程[^2]，该过程会将磁盘上相同文件的的内容按照顺序重新排列并利用压缩算法去除文件之间的空隙，有点类似垃圾回收中的标记压缩算法[^3]。
作者已经很多年都不使用 Windows 操作系统了，上大学之后就一直在用 macOS 到今年也有七八年的时间了，最近在研究文件系统时突然想到小时候经常见到的磁盘碎片整理程序仿佛已经消失了。不知道今天的 Windows 是否还需要磁盘整理，但是无论是 Linux 还是 macOS 上都没有类似的工具[^1]，这不禁让作者想要研究一下背后的原因。总得来说，操作系统需要碎片整理主要有以下两个原因：
-
文件系统的设计使得资源被释放后出现很多碎片；
-
机械硬盘的随机读写性能比顺序读写差几个数量级；
文件系统
上古时代的 Windows 使用了非常简单的文件系统 - 文件分配表（File Allocation Table、FAT）[^4]，该文件系统的设计是造成磁盘出现碎片的根本原因，不过在分析该系统之前，我们在这里先介绍一下文件系统的历史。
FAT 是 1977 年最开始为软盘设计的文件系统，软盘是一种非常古老的存储介质，今天的电脑基本上也都移除了软盘的驱动，当时的软盘都只能整盘的写入，所以更新软盘上的数据其实会覆盖原来的全部内容，这也就不存在所谓的磁盘碎片了。
在该文件系统被使用后不久，随着机械硬盘（Hard Disk Driver、HDD）的价格开始变得逐渐低廉并被广泛使用，微软选择在 DOS 和 Windows 9x 系列扩展 FAT 文件系统以支持更大的空间，而数据库等磁盘敏感型的应用也迅速变得非常热门。
每次写入数据都需要重新写入整张软盘是比较低效的做法，不过因为软盘的存储空间比较小，所以这在当时也是可以接受的，但是随着存储介质的空间变得越来越大，我们需要引入随机写入提高效率，支持随机写入的 FAT 也是很简单的文件系统[^5]。
图 2 - FAT 的写入
如上图所示，如果我们要向一块新的硬盘写入多个文件 A、B 和 C，这些文件会在 FAT 文件系统中按照顺序存储，文件之间不存在任何碎片。然而如果在这时我们决定删除其中 B 文件并向文件系统中写入更大的文件 D，会出现比较有趣的情况。
图 3 - FAT 的碎片
FAT 文件系统在磁盘上会先找到删除 B 后留下的两块空闲位置并在其中写入 D 文件的一部分，随后又会在 C 文件后找到另一块空闲位置并将 D 文件的剩余内容全部写到该位置。这样造成的结果是 D 文件会分散在硬盘上，当用户读取 D 文件时需要触发多次随机读取。
FAT 是一种非常简单、原始的文件系统，它的设计和实现从今天的角度来看都很糟糕，每次写入文件时不仅不会检查空闲空间的大小、造成文件碎片，还不包含碎片管理功能，使用时间过长还需要用户手动触发磁盘的碎片整理，这其实是很糟糕的设计和用户体验。
机械硬盘
机械硬盘（Hard Disk Drive、HDD）是一种基于电子的、非易失的机械数据存储设备，它使用磁性存储器存储并查找磁盘上的数据，在读取和写入数据的过程中，硬盘机械臂连接的磁头会读写磁盘表面的位[^6]。
正是因为磁盘具有比较复杂的机械结构，所以磁盘的读取和写入都要花费很多时间，数据库的读写性能也基本都依赖于磁盘的性能，如果我们在使用机械硬盘的数据库中随机查询一条数据，这可能会触发磁盘的随机 I/O，然而将数据从磁盘读取到内存中所需要的成本是非常大的，普通磁盘（非 SSD）加载数据需要经过队列、寻道、旋转以及传输的这些过程，大概要花费 10ms 左右的时间[^7]。
图 4 - 磁盘的随机 I/O
当我们在磁盘中读取文件时，如果文件的内容散落到了磁盘上的不同位置，它可能需要执行多次随机 I/O 才能够获取该文件的全部内容，这对于机械结构的磁盘来说是很大的额外开销。如果文件的内容会存储在相同的位置，那么读取文件时仅需要执行一次随机 I/O，后续的读取都可以使用速度约为 40 MB/s 的顺序 I/O，这可以显著减少文件的读取时间。
碎片化的文件在机械硬盘上会导致比较严重的性能问题，在理想情况下，我们希望磁盘能够达到它的读写带宽上限；但是在实际使用过程中，频繁的随机 I/O 让磁盘将大多数的时间都花在寻道和旋转上，导致其无法全力工作。与机械硬盘相比，具有电子结构的固态硬盘能够更好地耐受碎片化的文件系统，而整理碎片反而会影响它的使用寿命。
总结
相信很多工程师在进入这一行业之前都会使用 Windows 系统，早期的 Windows 是桌面系统近乎唯一的选择，作者对今天的这个题目有比较特殊的感情，在研究操作系统的文件系统之前一直都没有想过这个问题，直到碎片化的文件系统一词让自己想到了十多年前的疑问，这种豁然开朗的感觉在今天还是很少能够体会到的。我们简单总结一下早期的 Windows 需要碎片整理的两个原因：
-
早期的 Windows 系统使用简单的 FAT 文件系统，该文件系统经过频繁的写入删除操作会导致大文件散落在磁盘的各处；
-
机械硬盘在十多年前还是当时的主流设备，不过因为硬盘的机械结构，所以随机读写磁盘上的位置需要物理上的寻道和旋转，导致该过程极其缓慢；
到最后，我们还是来看一些比较开放的相关问题，有兴趣的读者可以仔细思考一下下面的问题，与前面的问题不同，作者会在后面的文章中解答这两个问题：
-
为什么 macOS 的文件系统不需要整理碎片？
-
为什么 Linux 的文件系统不需要整理碎片？
如果对文章中的内容有疑问或者想要了解更多软件工程上一些设计决策背后的原因，可以在博客下面留言，作者会及时回复本文相关的疑问并选择其中合适的主题作为后续的内容。
推荐阅读
参考资料
[^1]: Do Macs need to be defragmented? https://apple.stackexchange.com/questions/829/do-macs-need-to-be-defragmented
[^2]: Wikipedia: File system fragmentation https://en.wikipedia.org/wiki/File\_system\_fragmentation
[^3]: 内存管理设计精要 https://draveness.me/system-design-memory-management/
[^4]: Wikipedia: Design of the FAT file system https://en.wikipedia.org/wiki/Design\_of\_the\_FAT\_file\_system
[^5]: Why is it less necessary (comparing to FAT) to do disk defragmentation for NTFS hard drive? https://www.quora.com/Why-is-it-less-necessary-comparing-to-FAT-to-do-disk-defragmentation-for-NTFS-hard-drive?top\_ans=69674612
[^6]: Wikipedia: Hard disk drive https://en.wikipedia.org/wiki/Hard\_disk\_drive
[^7]: 为什么 CPU 访问硬盘很慢 https://draveness.me/whys-the-design-cpu-and-disk/
