Fuchsia 中的 BlobFS 文件系统以透明方式压缩文件以节省磁盘空间。BlobFS 支持许多不同的压缩策略,其中 zstd 为默认值。
文件压缩的一个缺点是,可能会阻止对文件的随机访问。对于大多数压缩算法,必须从磁盘读取所有内容并将其解压缩以访问单个字节。
对于 BlobFS,当文件需要分页时,这是一个特殊挑战。需求分页可将文件的一部分加载到内存中,从而节省系统内存。全文件压缩可防止部分文件加载。
Fuchsia 中的分块压缩格式和库将压缩文件拆分为多个可以单独解压缩的帧。这允许 BlobFS 对压缩文件实现需求分页,因为文件可以部分加载和解压缩。
本文档介绍了分块压缩格式的设计,并介绍了其在 Fuchsia 中的用途。
设计目标和非目标
下面这些目标激励着我们设计分块压缩格式和库:
随机访问解压缩。必须能够独立解压缩数据帧,而无需解压缩整个文件。
Flexible Decompression API。该库旨在让客户端能够控制跳转表,因此客户端可以精细控制要解压缩的帧。这支持需求分页等用例,在此类用例中,客户端 (BlobFS) 包含有关访问模式的更多信息,并且可以通过解压缩特定帧来精确控制预读和预提取。
这与管理更密切的 API 相反,后者隐藏哪些帧包含哪些解压缩的字节的详细信息。
可配置的帧大小。必须能够调整已解压缩的数据帧的大小,以适应不同的用例和不同要求。
灵活的压缩布局。该格式支持更加独特的帧布局,例如具有不统一的帧大小或使帧起始对齐,以适应未来需要更高灵活性的用例。例如,通过将一起读取为更小或更大的帧的数据分组在一起,可以使用非统一帧大小来改进数据局部性。
与 zstd 相当的压缩比。 在撰写本文档时,zstd 是 BlobFS 当前的默认压缩算法,因此 zstd 的压缩比率是对分块压缩库进行基准化比较的基准。由框架和其他元数据造成的开销必须最小。
可配置的压缩积极性。您必须尽可能通过牺牲更慢的压缩速度,获得更好的压缩比。
跨平台库。用于压缩和解压缩分块压缩归档的库必须在 Fuchsia 和编译主机(例如 Linux)上均可使用,以便在构建工具链中使用。如需在构建时(例如生成基础 BlobFS 映像时)压缩文件,必须执行此操作。
以下是非目标:
- 与 zstd 在格式级兼容。分块压缩归档文件并不与 zstd 的格式兼容,而且常规 zstd 工具不适用于分块压缩归档文件。
分块压缩
归档格式
分块归档由一个标头组成,后跟零个或零个以上的 zstd 帧。
标题
标头说明了归档的格式,并包含将压缩帧映射到解压缩空间的查找表。
0 1 2 3 4 5 6 7
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | Magic Number |
+-----+-----+-----+-----+-----+-----+-----+-----+
8 | Version | Reserved | Num Frames | // Reserved must be zero.
+-----+-----+-----+-----+-----+-----+-----+-----+
16 | Header CRC32 | Reserved | // Reserved must be zero.
+-----+-----+-----+-----+-----+-----+-----+-----+
24 | Reserved | // Reserved must be zero.
+-----+-----+-----+-----+-----+-----+-----+-----+
32 | |
40 | Seek Table |
48 | Entry |
56 | |
+-----+-----+-----+-----+-----+-----+-----+-----+
.. | |
.. | Seek Table |
.. | Entry |
.. | |
+-----+-----+-----+-----+-----+-----+-----+-----+
“标头 CRC32”是根据整个标头(包括查找表)计算的。
跳转表
每个还原表条目都描述了压缩空间中连续的数据范围,以及数据在解压缩后扩展到的位置。
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | Decompressed Offset |
+-----+-----+-----+-----+-----+-----+-----+-----+
8 | Decompressed Size |
+-----+-----+-----+-----+-----+-----+-----+-----+
16 | Compressed Offset |
+-----+-----+-----+-----+-----+-----+-----+-----+
24 | Compressed Size |
+-----+-----+-----+-----+-----+-----+-----+-----+
还原表条目在解压缩空间中是连续的,但在压缩空间中可能是不连续的。这是为了支持为输出文件添加对齐和内边距,从而提高存储空间访问效率。
一个查找表最多可以保存 1023 个条目(生成 32KiB 标头),并且必须包含至少 1 个条目(生成 64 字节的标头)。通常,压缩帧紧跟在跳转表后面(但该格式支持从超出跳转表末尾的任何偏移量开始的压缩帧)。
跳转表不变
I0:第一个跳转表条目的解压缩偏移量为 0。
I1:第一个跳转表条目的压缩偏移量必须大于或等于标头大小。
I2:每个条目的解压缩偏移量必须等于上一帧的结尾(即前一帧的解压缩偏移量+长度)。
I3:每个条目的压缩偏移量必须大于或等于上一帧的末尾(即前一帧的压缩偏移量+长度)。
I4:每个条目必须具有非零的解压缩和压缩长度。
I5:压缩帧不得超出文件末尾。
经过压缩的帧
文件中的每个压缩帧都是常规 zstd 压缩帧。给定帧将映射到解压缩文件中的某个连续字节块。
文件中未包含的字节范围将被忽略。
并不要求每个数据帧的解压缩后大小都相同,但是当前的压缩实现会将输入数据拆分为大小相等的帧。在压缩期间,可以配置帧的大小。
随机访问解压缩
跳转表用于查找包含给定解压缩范围的帧。当请求解压缩文件中的给定范围时,必须加载并解压缩一个或多个压缩帧。
例如,假设下面的文件包含三个框架:
Decompressed Space Compressed Space
+-----------------+ +--------------+
| | <-------- | |
| | | +--------|
| | +-----+ |
+-----------------+ +------ | |
| | <-+ +--------------+
| | +-- | |
| | | +--------------=
+-----------------+ |
| | <-----+
| +---------|
+-------+
若要访问单个帧中的字节范围,只需将其对应的压缩帧解压缩:
Decompressed Space Compressed Space
+-----------------+ +--------------+
| | <-------- |xxxxxxxxxxxxxx|
| xxxxxxxx | |xxxxx+--------|
| | +-----+ |
+-----------------+ +------ | |
| | <-+ +--------------+
| | +-- | |
| | | +--------------=
+-----------------+ |
| | <-----+
| +---------|
+-------+
涵盖多个解压缩帧的范围将需要解压缩多个压缩帧:
Decompressed Space Compressed Space
+-----------------+ +--------------+
| | <-------- |xxxxxxxxxxxxxx|
| | |xxxxx+--------|
| xxx| +-----+xxxxxxxx|
+-----------------+ +------ |xxxxxxxxxxxxxx|
|xxxx | <-+ +--------------+
| | +-- | |
| | | +--------------=
+-----------------+ |
| | <-----+
| +---------|
+-------+
在 BlobFS 中使用
在 BlobFS 中,使用分块压缩库压缩文件,以便于随机访问和需求分页。
目前,只有启用需求分页时,才会使用随机访问。停用需求分页后,BlobFS 会在首次访问时加载并解压缩整个文件,并在有文件句柄时在内存中缓冲文件。
启用需求分页后,BlobFS 会在有人访问文件时延迟加载部分文件。BlobFS 使用 zx_pager_create 系统调用将自身注册为 VMO 的 pager。当您在 VMO 中访问不存在的页面时,会发生页面错误,BlobFS 会处理此错误。
BlobFS 会查找包含目标页面的已解压缩帧,并解压缩每个帧。解压缩每一帧后,系统会验证数据,并通过 zx_pager_supply_pages 系统调用将数据提交到由分页器支持的 VMO。