记得十几年前使用早期 windows 系统时，经过一段时间后，系统会变得非常卡顿，这时需要启动系统自带的下面的磁盘碎片整理程序。完成碎片整理后，系统的运行速度会稍微有所改善。
图 1 - Windows 磁盘碎片整理程序
在文件系统中，碎片整理（Defragmentation）是减少文件系统中碎片的过程[^2]，该过程会将磁盘上相同文件的内容按照顺序重新排列，并利用压缩算法去除文件之间的空隙，这有点类似于垃圾回收中的标记压缩算法[^3]。
作者已经多年未使用 Windows 操作系统了，从上大学开始就一直使用 macOS，至今已有七八年了。最近在研究文件系统时，突然想起小时候经常见到的磁盘碎片整理程序仿佛已经消失了。不知道现在的 Windows 是否还需要磁盘整理，但无论是 Linux 还是 macOS 上都没有类似的工具[^1]，这让作者想要探究背后的原因。总的来说，操作系统需要碎片整理的主要原因有两个：
文件系统的设计导致资源释放后产生大量碎片；机械硬盘的随机读写性能比顺序读写差几个数量级；文件系统的上古时代，Windows 使用了非常简单的文件系统 - 文件分配表（File Allocation Table、FAT）[^4]，该文件系统的设计是导致磁盘出现碎片的根本原因。不过在分析该系统之前，我们先简要介绍一下文件系统的历史。
FAT 是 1977 年为软盘设计的文件系统，软盘是一种非常古老的存储介质，现代电脑基本上已不再使用。当时的软盘只能整盘写入，因此更新数据时会覆盖所有内容，也就不存在所谓的磁盘碎片。
在 FAT 被广泛使用后不久，随着机械硬盘（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 的文件系统不需要整理碎片？
