近日和朋友聊到存储系统设计的相关技术，结合以前我在互联网公司做分布式系统的一些经验，本篇就粗略地讲一讲如何设计一个简单的磁盘文件系统。

磁盘的结构：

传统的磁盘结构是像下面这个样子的，它有一个或多个盘片，用于存储数据。盘片多采用铝合金材料；中间有一个主轴，所有的盘片都绕着这个主轴转动。一个组合臂上面有多个磁头臂，每个磁头臂上面都有一个磁头，负责读写数据。

image.png

磁盘一般有一个或多个盘片。每个盘片可以有两面，即第一个盘片的正面为0面，反面为 1 面；第二个盘片的正面为 2 面…依次类推。磁头的编号也和盘面的编号是一样的，因此有多少个盘面就有多少个磁头。盘面正视图如下图，磁头的传动臂只能在盘片的内外磁道之间移动。因此不管开机还是关机，磁头总是在盘片上面。关机时，磁头停在盘片上面，抖动容易划伤盘面造成数据损失，为了避免这样的情况，所以磁头都是停留在起停区的，起停区是没有数据的。

image.png

每个盘片的盘面被划分成多个狭窄的同心圆环，数据就存储在这样的同心圆环上面，我们将这样的圆环称为磁道 (Track)。每个盘面可以划分多个磁道，最外圈的磁道是0号磁道，向圆心增长依次为1磁道、2磁道…磁盘的数据存放就是从最外圈开始的。

image.png

根据硬盘的规格不同，磁道数可以从几百到成千上万不等。每个磁道可以存储数 Kb 的数据，但是计算机不必要每次都读写这么多数据。因此，再把每个磁道划分为若干个弧段，每个弧段就是一个扇区 (Sector)。扇区是硬盘上存储的物理单位，现在每个扇区可存储 512 字节数据已经成了业界的约定。也就是说，即使计算机只需要某一个字节的数据，但是也得把这个 512 个字节的数据全部读入内存，再选择所需要的那个字节。

image.png

柱面是我们抽象出来的一个逻辑概念，简单来说就是处于同一个垂直区域的磁道称为柱面 ，即各盘面上面相同位置磁道的集合。需要注意的是，磁盘读写数据是按柱面进行的，磁头读写数据时首先在同一柱面内从 0 磁头开始进行操作，依次向下在同一柱面的不同盘面(即磁头上)进行操作，只有在同一柱面所有的磁头全部读写完毕后磁头才转移到下一柱面。因为选取磁头只需通过电子切换即可，而选取柱面则必须通过机械切换。数据的读写是按柱面进行的，而不是按盘面进行，所以把数据存到同一个柱面是很有价值的。

磁盘被磁盘控制器所控制（可控制一个或多个），它是一个小处理器，可以完成一些特定的工作。比如将磁头定位到一个特定的半径位置；从磁头所在的柱面选择一个扇区；读取数据等。

image.png

现代硬盘寻道都是采用CHS(Cylinder Head Sector)的方式，硬盘读取数据时，读写磁头沿径向移动，移到要读取的扇区所在磁道的上方，这段时间称为寻道时间(seek time)。因读写磁头的起始位置与目标位置之间的距离不同，寻道时间也不同。磁头到达指定磁道后，然后通过盘片的旋转，使得要读取的扇区转到读写磁头的下方，这段时间称为旋转延迟时间(rotational latencytime)。然后再读写数据，读写数据也需要时间，这段时间称为传输时间（transfer time）。

根据上文的信息，我们可以得出磁盘容量的计算公式为：
磁盘容量 = 总盘面数 x 每盘面柱面数 x 每磁道扇区数 x 512

注：以上信息来源于网络。

文件系统的设计：

磁盘在物理上是一个很复杂的混和结构，对软件开发者来说，基本上不需要直接接触它们，我们所有的访问都在磁盘控制器的接口之一，使用与内存相似的统一寻址，只不过磁盘支持持久化，且性能相对于内存有数量级差。我们可以考虑使用静态链表来设计文件系统。

静态链表：

静态链表是一种利用顺序存储结构来进行链式存储的特殊结构，使用它可以在一段连接的存储空间模拟离散的链式结构。它通过将整块大内存划分为小的块，块与块之间通过指针连接，这个小的块，我称为之存储单元。

文件系统结构定义：

在存储单元之上，一个基本的文件系统需要有逻辑的目录、文件，通常一个块不可能存储完整个目录或文件，因此它们实际上可能需要跨多个块。下面是存储单元和目录结构的定义：

存储单元结构定义：

    头区(保留32字节)：
        本单元数据区大小(4字节)
        数据类型(4字节)：目录 / 文件
        数据区偏移(4字节)：32
        父级存储单元地址(4字节)
        数据区的下一单元地址(4字节)
        本单元的下一空闲单元地址(4字节)
    数据区（大小由头区指定）：
        目录数据 / 文件数据

目录结构定义：

    项目数(4字节)
    项目1(保留16字节)：
        项目类型(4字节)：目录 / 文件
        项目名称(4字节)：目录名 / 文件名
        项目所在存储单元地址(4字节)
    项目2(保留16字节)：
        项目类型(4字节)：目录 / 文件
        项目名称(4字节)：目录名 / 文件名
        项目所在存储单元地址(4字节)

文件结构定义：
纯文件内容

此外，还需要有空闲单元结构等信息，这里增加一个全局磁盘信息定义：

    存储单元大小
    存储单元入口地址
    空闲单元入口地址

文件系统内容布局：

下面以一个64K的磁盘，假设起始地址从0开始，最大地址64K-1，对于如下的逻辑存储：

/ 
  |------目录1 
  |           |------目录2 
  |           |           |------文件3 (大小3.1K)
  |           |           
  |           |------文件2 (大小100)
  |          
  |------文件1 (大小100)

假设定义每单元大小为4K，在4K字节中，需要存储单元头32字节，其余4K-32可存储目录或文件内容，假设在下面的设计中，每个单元若存储文件内容最多不超过3K。且假设定义全局磁盘信息在0单元，其实际物理布局如下：

全局信息地址：0
    存储单元大小：4K
    存储单元入口地址：4K
    空闲单元入口地址：32K

单元地址：4K (/目录)
    头区：
        本单元数据区大小：36(4 + 2x16)
        数据类型：目录
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        目录数据，内容如下：
            项目数：2
            项目1：
                项目类型：目录
                项目名称：目录1
                项目所在存储单元地址：8K
            项目2：
                项目类型：文件
                项目名称：文件1
                项目所在存储单元地址：12K

单元地址：8K (目录1)
    头区：
        本单元数据区大小：36(4 + 2x16)
        数据类型：目录
        数据区偏移：32
        父级存储单元地址：4K
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        目录数据，内容如下：
            项目数：2
            项目1：
                项目类型：目录
                项目名称：目录2
                项目所在存储单元地址：16K
            项目2：
                项目类型：文件
                项目名称：文件2
                项目所在存储单元地址：20K

单元地址：12K (文件1)
    头区：
        本单元数据区大小：100
        数据类型：文件
        数据区偏移：32
        父级存储单元地址：4K
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        文件数据，内容如下：
            abcdefg....(100字节）

单元地址：16K (目录2)
    头区：
        本单元数据区大小：20(4 + 1x16)
        数据类型：目录
        数据区偏移：32
        父级存储单元地址：8K
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        目录数据，内容如下：
            项目数：1
            项目1：
                项目类型：文件
                项目名称：文件3
                项目所在存储单元地址：24K

单元地址：20K (文件2)
    头区：
        本单元数据区大小：100
        数据类型：文件
        数据区偏移：32
        父级存储单元地址：8K
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        文件数据，内容如下：
            abcdefg....(100字节）

单元地址：24K (文件3)
    头区：
        本单元数据区大小：3K
        数据类型：文件
        数据区偏移：32
        父级存储单元地址：16K
        数据区的下一单元地址：28K
        本单元的下一空闲单元地址：0
    数据区：
        文件数据，内容如下：
            abcdefg....(3K字节）

单元地址：28K (文件3)
    头区：
        本单元数据区大小：100
        数据类型：文件
        数据区偏移：32
        父级存储单元地址：16K
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        文件数据，内容如下：
            abcdefg....(100字节）

单元地址：32K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：36K
    数据区：
        无

单元地址：36K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：40K
    数据区：
        无

单元地址：40K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：44K
    数据区：
        无

单元地址：44K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：48K
    数据区：
        无

单元地址：48K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：52K
    数据区：
        无

单元地址：52K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：56K
    数据区：
        无

单元地址：56K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：60K
    数据区：
        无

单元地址：60K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        无

操作设计：

一个合格的文件系统至少应支持以下操作：

格式化：

包括低级格式化和高级格式化，低级格式化由厂商提供，由控制器提供支持，主要用于消除数据，重建扇区存储结构。高级格式化由操作系统提供，主要目的是向固定扇区写入特定结构，这些结构包括磁盘或分区元信息表，管理整个磁盘或分区的全局和入口信息。
对我们的简单系统来说，需要初使化全局信息地址和根目录，以及各存储单元，初使化为：

全局信息地址：0
    存储单元大小：4K
    存储单元入口地址：4K
    空闲单元入口地址：8K

单元地址：4K (/目录)
    头区：
        本单元数据区大小：0
        数据类型：目录
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        目录数据，暂无

单元地址：8K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：12K
    数据区：
        无

......

单元地址：60K
    头区：
        本单元数据区大小：0
        数据类型：0
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        无

新增目录：

首先需要找到父目录所在的单元位置，由于整个文件系统是一个树型结构，需要从根目录位置开始寻找。若在根目录添加，或者说找到了父目录的单元地址，操作如下：

1. 在全局信息地址中找一个空闲单元，如8K，修改空闲单元入口地址为12K。

全局信息地址：0
    存储单元大小：4K
    存储单元入口地址：4K
    空闲单元入口地址：12K

2. 修改4K所在的根目录存储单元内容，如下：

单元地址：4K (/目录)
    头区：
        本单元数据区大小：20(4 + 2x16)
        数据类型：目录
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        目录数据，内容如下：
            项目数：1
            项目1：
                项目类型：目录
                项目名称：目录名称
                项目所在存储单元地址：8K

3. 修改8K的存储单元内容，如下：

单元地址：8K (目录名称)
    头区：
        本单元数据区大小：4
        数据类型：目录
        数据区偏移：32
        父级存储单元地址：4K
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        目录数据，内容如下：
            项目数：0

删除目录：

删除目录是上面新增目录的逆操作，操作步骤：

1. 首先必须提供待删除目录的确定地址，如删除上面新增的目录8K，不需要特意的做数据区的擦除工作。
2. 从8K的数据单元头区找到父级存储单元地址，如4K，然后读取4K数据区的内容，删除对应的子目录，然后重新写回数据区。
3. 将8K的数据单元重新加入到空闲单元中，需要先取出修改全局信息地址中的空闲单元入口地址，将8K存储单元链向它，并将8K地址更新到空闲单元入口地址。

遍历目录：

遍历通常实现为一个递归的过程，对每个递归单元来说，逻辑如下：

1. 判断提供的存储单元的头区数据类型，如果非目录，返回不再执行后续步骤。
2. 根据数据区偏移找到目录的数据结构，这里一个列表，读取其内容。
3. 顺序遍历这个列表，判断项目类型，如果是文件，打印文件名，如果是目录，则递归。
4. 判断数据区的下一单元地址是否为0，非0表示目录列表未展示完全，还需要读取其他的单元，继续回到步骤1执行。

新增文件：

首先需要提供父目录位置，即目录存储单元地址，以在根目录添加文件为例，操作如下：

1. 在全局信息地址中找一个空闲单元，如8K，修改空闲单元入口地址为12K。

全局信息地址：0
    存储单元大小：4K
    存储单元入口地址：4K
    空闲单元入口地址：12K

2. 修改4K所在的根目录存储单元内容，如下：

单元地址：4K (/目录)
    头区：
        本单元数据区大小：20(4 + 2x16)
        数据类型：目录
        数据区偏移：32
        父级存储单元地址：0
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        目录数据，内容如下：
            项目数：1
            项目1：
                项目类型：文件
                项目名称：文件名称
                项目所在存储单元地址：8K

3. 修改8K的存储单元内容，如下：

单元地址：8K (文件名称)
    头区：
        本单元数据区大小：0
        数据类型：文件
        数据区偏移：32
        父级存储单元地址：4K
        数据区的下一单元地址：0
        本单元的下一空闲单元地址：0
    数据区：
        无

写入文件：

需要提供文件的存储单元地址，以向上面的8K地址写入abcdefg内容为例，操作如下：

1. 更新8K的头区单元数据区大小为7。
2. 更新8K的数据区的内容为abcdefg。

读取文件：

需要提供文件的存储单元地址，以向上面的8K地址读取为例，操作如下：

1. 取得8K的头区单元数据区大小，如7。
2. 读取8K的数据区内容，读取长度7。
3. 检查数据区的下一单元地址，确保是否是最后数据区，若不为0，切换存储单元地址，继续执行步骤1。

删除文件：

是新增文件的反操作，操作如下：

1. 首先必须提供待删除文件的确定地址，如删除上面新增的文件8K，不需要特意的做数据区的擦除工作。
2. 从8K的数据单元头区找到父级存储单元地址，如4K，然后读取4K数据区的内容，删除对应的子项，然后重新写回数据区。
3. 将8K的数据单元重新加入到空闲单元中，需要先取出修改全局信息地址中的空闲单元入口地址，将8K存储单元链向它，并将8K地址更新到空闲单元入口地址。