memory-management - 我们如何设计磁盘数据结构以及如何保存它？

Question

我们如何设计磁盘数据结构？例如：查看 ext3 inode结构，我们有属性放置。在内存使用/对齐、填充等方面需要牢记什么？

此外，是否有任何特殊机制可以根据页面/块对齐将这些数据结构写入磁盘，或者您只是像文件写入一样简单地写入？

Answer 1

通常，这种结构的处理是在 C 中完成的，因为它具有相对低级的特性。例如，当您定义 an 时，struct您总是可以提前知道它将占用多少字节，甚至可以知道每个字段的对齐方式。C 永远不会在struct控件或其他类型的字段中引入供自己使用。这允许struct直接从磁盘读取和写入这些 s。

问题中包含的链接似乎对应于 Linux EXT2（扩展 2）文件系统，保存 2 件事：

• 它说对应于EXT3。但是，它没有显示任何添加到 EXT2 的特定于 EXT3 的结构。对 EXT2 的良好理解应该足以满足您当前的目的。我强烈建议您阅读 Wikipedia 关于 EXT2或类似内容的文章。
• 它将块（指针）数组的最后一个条目显示为单个间接间接条目，并且没有提及双重或三重间接条目。在 EXT2（和 EXT3）中，块（指针）数组包含 15 个条目。前 12 个是直接的，第 13 个是单间接，第 14 个是双间接，第 15 个是三倍。这种简化可以仅用于描述，也可以简化您将要做的整个工作。

这些结构是文件概念的起源。您不能将它们作为文件读取，因为还没有文件。您确实需要与代表硬盘驱动器的“块设备驱动程序”进行交互。与许多其他 Linux 对象一样，设备（以及它们的驱动程序）被表示为文件系统中的元素（不，不是在您尚不存在的root文件系统中，而是在任何 Linux 机器启动时具有的文件系统中）。您将需要打开相应的文件系统对象并使用该ioctl函数向其发送请求。

为了理解对齐，区分两件事很重要：

• 输入/输出单元（扇区），这是您从设备发送/接收的基本字节数。通常，它是 512 字节。
• 分配单元（块），它是您分配给文件系统中文件的基本字节数。通常是 1、2、4、8、16 个扇区或 2 的另一个幂（但磁盘中所有块的数量相同）。

因此，磁盘被划分为块，这些块被分配给文件以保存其内容。创建大小为 0 的文件时，它没有任何块。写入第一个字节时，分配第一个块。写入第二个字节时，不会分配新块，因为第一个块应该仍有大量可用空间（例如 4,095 个字节）。当字节数 4,096 被写入时，它仍然适合第一个块，但是当字节 4,097 被写入时，第二个块被分配给文件并且新字节被写入它的第一个位置。等等。平均而言，每个文件总是浪费一半的块，特别是在其最后一个块中。

磁盘上数据结构的基本部分应该是 512 字节大小，因此它们可以毫无浪费地读写。当然，这些基本部分的多个实例可以连续存储，但基本信息不应从一个扇区跨越到下一个扇区，而应完全包含在其中一个扇区中。超过 512 字节对齐，这是 512 字节大小要求。

然而，这些扇区最终将被读取到 RAM，并且出于效率原因，它们在使用前不应受到任何操作。另一方面，许多 CPU 体系结构在short大小为 2 字节的 s 上运行得更快，当它们的对齐为 2 时（即内存地址的倍数为 2），在ints 上运行得更快，当它们的对齐为 4 时，s 为 4 字节，以及依此类推，通常最大为 16。如果磁盘上的数据项遵循这些对齐方式，并且存储它们的扇区始终被读入具有最大可能所需对齐的内存块（16 以确保安全），那么数据项也将在内存中正确对齐。

在摘要模式下：

• 使磁盘数据结构的基本元素恰好大 1 个扇区（即使它们的重复将连续存储）。
• 根据它们的大小对齐这些扇区/基本元素中的数据项，以及
• 读取 16 字节对齐的内存块（或任何最大的基本数据项）中的磁盘数据结构（可能还有所有扇区）。

最后，回答不同评论中表达的一些问题：

• 既然您提到了 Java，我第一次明白为什么“磁盘上”和“内存中”数据结构之间的区别对您如此重要。见下文。
• 在 Java 中，您无法控制对象大小或数据项对齐方式。如果你想遵守上面建立的标准，每次你想把一个 Java DS 写到磁盘上，你都需要把它编码为byte[512]，然后写这个。每次从磁盘读取 DS 时，都需要读取 abyte[512]并将其解码为相应的 Java DS。这违反了内存和磁盘数据结构之间不进行数据转换的原则。
• 此外，在 Java 中，您通常无权访问设备。不过，您可以通过文件模拟块设备。
• 您可以将“磁盘数据结构”调用到byte[512]读/写到磁盘的数据元素，以及源/结果磁盘扇区（模拟或物理）本身。
  • 在这种情况下，您可以将 Java 对象调用为“内存数据结构”，以将其编码为byte[512]s，然后写入磁盘，或者从byte[512]已从磁盘读取的 s 中解码。
• 正确，很简单byte[512]，“磁盘上”数据结构本质上是“纯数据”。
• 是的，作为 Java 对象，“内存中”数据结构将属于类，而类又包含函数、常量、数据类型/辅助类等。
• 有关更多详细信息，请说明 EXT2 是完全按照公开指定的方式实现，还是仅作为您将定义细节的通用模型。
• inode仅出于美学原因，将其组织为表格（具有水平和垂直组件）。仅将其视为一维（水平或垂直）数据。

Answer 2

磁盘上的数据结构是特别适用于硬盘或其他类型的块访问存储设备（与 RAM 相对）的任何数据结构。

示例：（链接的）二叉树更适合 RAM，因为基本存储（和搜索）单元很小：具有一个且只有一个键的单个节点，例如 100 字节。b-tree 适用于硬盘，因为它的基本存储和搜索单元使用几个键（比如 20 个），总大小为 2000 字节。这更接近于硬盘的存储和访问单元，这意味着当一个节点存储在一个磁盘存储单元中时，很少或没有任何浪费，并且当执行磁盘访问操作时，确实需要所有传输的信息，并且用过的。事实上，b-trees 每个节点接受不同数量的键，可以调整以适应特定的硬盘驱动器。

停电时，RAM 数据结构会立即丢失。尝试任何恢复都没有任何意义。但是，硬盘驱动器不是。这种数据结构的恢复能力（部分或全部）通常是选择它们时的重要标准。

它还可以指管理块访问内存系统所需的数据结构，通常以文件和目录的形式（及其属性，包括安全属性）。