BlobFS中的随机访问压缩

Fuchsia 中的 BlobFS 文件系统为了节省磁盘空间而显式的压缩文件，BlobFS 提供多种不同的压缩策略，默认使用zstd

文件压缩的一个缺点是阻止对文件的 随机访问。对于大多数压缩算法来说，必须从磁盘读取全部内容并解压缩才能访问单个字节。

对于 BlobFS来说，当文件按需分页时，这是一个特别的挑战。按需分页允许一个文件部分装载到内存，以便节省系统内存。 完整文件压缩防止了部分加载文件方式。

Fuchsia 中的分块压缩方式和库将压缩文件分解成可以独立解压缩的帧。 这让 BlobFS 实现了压缩文件的按需分页，因为文件能够部分加载和解压。

这篇文档描述了分块压缩格式的设计以及介绍了它是如何在 Fuchsia 中使用的。

设计目标和非目标

以下是分块压缩格式和库的设计目标：

  • 随机存取解压 能够独立的解压部分数据段而不需要解压整个文件。

  • 灵活的解压 API 该库被设计为可以让客户端控制搜索表，因此客户端可以细粒度地控制它们解压缩的帧。在支持请求分页等用例中，客户端( BlobFS )有更多有关访问模式的信息，并且可以通过解压缩特定帧来精确控制预读和预取。

    这与更受管理的API形成对比，后者隐藏哪些帧包含哪些解压缩字节的详细信息。

  • 可配置的帧大小 为了适配不同的案例以及不同的需求，数据压缩帧的大小可适配是必须的。
  • 灵活的压缩方式 支持多种多样的帧方式，例如非统一的帧大小或者帧开始的对齐来适应需要更为灵活的场景需求。通过将一起读取的数据分组成更小或更大的帧，可以使用非均匀帧大小来改善数据局部性。
  • 与 zstd 的压缩率差不多 由于在撰写本文档时，zstd 是 BlobFS 的当前默认压缩算法，zstd 的压缩率是以分块压缩库进行基准测试为标准。因此成帧和附加元数据引起的开销一定是最小的。
  • 压缩比例的选配。在较慢的压缩速度之间进行折衷，以获得更好的压缩比。
  • 库可跨平台。用于在压缩和解压缩文档压缩块的库，必须要能够在 Fuchsia 和其他编译主机上（如： Linux ），都能在工具链上使用这个库。 这对于在构建时压缩文件是必要的，例如在生成基本 BlobFS 映像时。

以下是非设计目标：

  • 与 zstd 格式的兼容性。文档压缩块不期望能和 zstd 的格式相兼容，因此，常用的 zstd 工具将无法应用在文档压缩块上。

块压缩

归档格式

一个文档块的头的组成应该是0个或者多个 zstd 帧。

头

头描述了存档的格式，并包含一个将压缩帧映射到解压缩空间的搜索表。

  1.       0     1     2     3     4     5     6     7
  2.    +-----+-----+-----+-----+-----+-----+-----+-----+
  3.  0 |                 Magic Number                  |
  4.    +-----+-----+-----+-----+-----+-----+-----+-----+
  5.  8 |  Version  |  Reserved |       Num Frames      |  // Reserved must be zero.
  6.    +-----+-----+-----+-----+-----+-----+-----+-----+
  7. 16 |    Header CRC32       |        Reserved       |  // Reserved must be zero.
  8.    +-----+-----+-----+-----+-----+-----+-----+-----+
  9. 24 |                    Reserved                   |  // Reserved must be zero.
  10.    +-----+-----+-----+-----+-----+-----+-----+-----+
  11. 32 |                                               |
  12. 40 |                   Seek Table                  |
  13. 48 |                     Entry                     |
  14. 56 |                                               |
  15.    +-----+-----+-----+-----+-----+-----+-----+-----+
  16. .. |                                               |
  17. .. |                   Seek Table                  |
  18. .. |                     Entry                     |
  19. .. |                                               |
  20.    +-----+-----+-----+-----+-----+-----+-----+-----+

基于包括搜索表在内的整个报头来计算“ Header CRC32 ”。

查找表

每个查找表项描述压缩空间中的连续数据范围，以及它在解压缩数据中扩展到的位置。

  1.    +-----+-----+-----+-----+-----+-----+-----+-----+
  2.  0 |               Decompressed Offset             |
  3.    +-----+-----+-----+-----+-----+-----+-----+-----+
  4.  8 |                Decompressed Size              |
  5.    +-----+-----+-----+-----+-----+-----+-----+-----+
  6. 16 |                Compressed Offset              |
  7.    +-----+-----+-----+-----+-----+-----+-----+-----+
  8. 24 |                 Compressed Size               |
  9.    +-----+-----+-----+-----+-----+-----+-----+-----+

查找表项在解压缩空间中是 连续的，但是在压缩空间时可能是 非连续的。这是为了支持向输出文件添加对齐和填充，以提高存储访问效率。

单个查找表最高支持1023个表项（表头占32KB）和至少1个表项（表头占64字节）。因此，压缩帧能立刻通过查找表被找到（但该格式支持从超过搜索表末尾的任何偏移量开始的压缩帧）。

查找表常量

  • I0: 第一个查找表项必须具有解压缩的偏移量0。

  • I1: 第一个搜索表条目必须具有大于或等于标题大小的压缩偏移量。

  • I2: 每个条目的解压缩偏移量必须等于前一帧的末尾(即前一帧的解压缩偏移量+长度)。

  • I3: 每个条目的压缩偏移量必须大于或等于前一帧的末尾(即前一帧的压缩偏移量+长度)。

  • I4: 每个条目必须具有非零解压缩和压缩长度。

  • I5: 任何压缩帧都不能超过文件末尾。

压缩帧

文件中的每个压缩帧都是规则的 zstd 压缩帧。给定帧将映射到解压缩文件中的某个连续字节块。 文件中未被搜索表覆盖的任何字节范围都将被忽略。 不要求每个数据帧的解压缩大小相同，但当前的压缩实现将输入数据分割成大小相等的帧。帧的大小在压缩期间是可配置的。

随机存取解压

搜索表用于查找包含给定解压缩范围的帧。当请求解压缩文件中的给定范围时，必须加载并解压缩一个或多个压缩帧。

例如，考虑以下具有三个帧的文件：

  1. Decompressed Space            Compressed Space
  2. +-----------------+           +--------------+
  3. |                 | <-------- |              |
  4. |                 |           |     +--------|
  5. |                 |           +-----+        |
  6. +-----------------+   +------ |              |
  7. |                 | <-+       +--------------+
  8. |                 |       +-- |              |
  9. |                 |       |   +--------------=
  10. +-----------------+       |
  11. |                 | <-----+
  12. |       +---------|
  13. +-------+

访问单个帧内的字节范围只需要解压缩其对应的压缩帧：

  1. Decompressed Space            Compressed Space
  2. +-----------------+           +--------------+
  3. |                 | <-------- |xxxxxxxxxxxxxx|
  4. |  xxxxxxxx       |           |xxxxx+--------|
  5. |                 |           +-----+        |
  6. +-----------------+   +------ |              |
  7. |                 | <-+       +--------------+
  8. |                 |       +-- |              |
  9. |                 |       |   +--------------=
  10. +-----------------+       |
  11. |                 | <-----+
  12. |       +---------|
  13. +-------+

跨越多个解压缩帧的范围需要解压缩多个压缩帧：

  1. Decompressed Space            Compressed Space
  2. +-----------------+           +--------------+
  3. |                 | <-------- |xxxxxxxxxxxxxx|
  4. |                 |           |xxxxx+--------|
  5. |              xxx|           +-----+xxxxxxxx|
  6. +-----------------+   +------ |xxxxxxxxxxxxxx|
  7. |xxxx             | <-+       +--------------+
  8. |                 |       +-- |              |
  9. |                 |       |   +--------------=
  10. +-----------------+       |
  11. |                 | <-----+
  12. |       +---------|
  13. +-------+

BlobFS 应用

在 BlobFS 中，文件使用分块压缩库进行压缩，以便于随机访问和请求分页。

目前，随机访问仅当按需分页开启时才被使用。当按需分页被关闭时，BlobFS 将在首次加载和解压整个文件，并当操作文件时将文件缓存到内存中。

当按需分页被开启时，BlobFS 在访问文件时只懒加载文件的部分。BlobFS使用 ZX_PAGER_CREATE 将自身注册为VMO的 pager 在 VMO 中访问非当前页时，会发生页错误，由 BlobFS 处理。

BlobFS 查找包含目标页面的解压缩帧，然后解压缩每个帧。 解压缩每一帧后，将验证数据，并通过 ZX_PAGER_SUPPLE_PAGES 系统调用将数据提交给页表备份的 VMO