Fixed-Output Compression 的神话

Fixed-output compression——变长输入、定长输出的压缩布局——曾被赋予消除读放大、对齐 I/O、提高压缩率、节省内存等优势。逐项归因之后:这些优势或来自粒度选择,或来自索引与解压器的实现,或只在限定口径里成立,或查无实据;而代价是格式级的、永久的。结论是客气但彻底的:作为一项格式设计决策,fixed-output 不值得采用。

在可随机读取的压缩存储设计中,数据布局先要回答一个问题:压缩的边界画在哪里。fixed-input 按定长输入切分、逐单元压缩、变长输出紧密排列;fixed-output 反其道而行——变长输入"塞满"定长的输出块,使压缩单元与存储块天然对齐。

fixed-output 由 [1] 提出,并携一串动人的故事而来:消除读放大、对齐 I/O、提高压缩率、节省内存。本文逐一核对它们的下落:这些故事要么记错了主人,要么只在限定的口径里上演,要么查无实据;而代价永久有效——作为一项格式设计决策,fixed-output 并无存在的必要。 本文否定的是这项技术作为通用设计选择的价值,不涉及任何采用它的具体系统。系统的成败由实现质量、运营与生态共同决定,一个不成立的机制不一定妨碍一个成功的系统。

一、读放大与对齐:两则童话

读放大的机制很简单:解压必须从一条压缩流的头部开始(LZ4 等算法无法从流中间寻址),单元越大,为一个小请求付出的 I/O 与解压就越多。它只取决于单元大小,与输入定长还是输出定长无关。

先看 [1] 自己的评测数据(读取 16MB,实际发出的 I/O 量;跨步读即每 128KB 只读开头 4KB):

布局单元大小随机读跨步读
fixed-input128KB165.27 MB203.91 MB
fixed-input4KB26.19 MB26.23 MB
fixed-output4KB(输出)26.12 MB25.93 MB

4KB 粒度下两种布局的 I/O 量几乎相同;六到八倍的放大差异全部来自单元尺寸。第一则童话到此显形:读放大的消除是粒度的功劳,与布局无关——而给出这个对照的,正是提出它的论文自己。

同一组数据里还藏着第二则童话。fixed-output 的输出块与存储块天然对齐;而 fixed-input 的变长块紧密排列、必然跨越块边界,读取时要整读首尾两个只用得到一部分的物理块,理论上有"碎块"损耗。理论成立,红利却从未兑现:上表中两种布局的总 I/O 量相同——碎块字节属于相邻单元,对后续读取同样有效,缓存将这项理论损耗抹平。

机制层面的关键在于缓存顺带取回但暂未用到的数据,而两种布局缓存的形态不同。fixed-input 只需要缓存压缩态数据,而 fixed-output 则需要缓存解压态数据,否则就会浪费解压开销。缓存这一层非但不偏向 fixed-output,反而站在 fixed-input 一边。

二、压缩率:限定口径里的大捷

fixed-output 对同单元尺寸的 fixed-input(4KB 对 4KB)确有约 10% 的体积优势 [1]——一场大捷,机制也清楚:“塞满"使每条压缩流覆盖更长的输入,而流越长压缩率越好。

但这场大捷避开了现实的对手。4KB 输出的 fixed-output 比大窗口 fixed-input(128KB 单元)的镜像大 11% 到 29% [1](实测两组语料: 0.52GB 对 0.47GB;100.9MB 对 78.0MB)。要追回这个差距,fixed-output 只能放大输出块——也就是把粒度拧回去,同时把读放大请回来。这项技术把压缩率和随机读性能焊死在同一个旋钮上,拧向哪一头都是让步。

存储侧还有一笔小账:fixed-input 紧密排列、一字节不浪费; fixed-output 的每个输出块尾部填不满,自带内部碎片。

三、同口径对比:孪生兄弟的故事

其实前两节藏着一个口径陷阱:fixed-input 的标签指输入, fixed-output 的标签指输出——同挂一个"4KB”,流长并不相同。真正的同口径,是让每条压缩流覆盖相同的逻辑数据。以 2:1 压缩率为例:fixed-input 的 256KB 单元与 fixed-output 的 128KB 输出块,是同一条流的两种切法。逐项重算(服务一次 4KB 随机读):

fixed-input,256KB 单元fixed-output,128KB 输出
单条流256KB 输入 → ~128KB 压缩~256KB 输入 → 128KB 压缩
读取 I/O整条流 ~128KB整条流 128KB
解压量从头解到目标产出,平均半条流从头解到目标产出,平均半条流
读放大~32×~32×
压缩率相同相同

全部归零:孪生兄弟之间,本无所谓高下。由此还多出一个推论——第二节那 10% 的"优势"其实也是口径幻觉:“4KB 对 4KB"的标签之下, fixed-output 的流实际长了一倍:优势的源头是流长差,而非布局;流长拉平,率差归零。fixed-output 的 128KB 输出块 ≡ fixed-input 的 256KB 单元加上对齐;而对齐的收益从未兑现(见第一节)。

同口径下,剩余的差异全部是结构性的:fixed-input 索引稀疏、逻辑定位算术免费、存储零浪费;fixed-output 块对齐、I/O 大小先验可知(见第六节)。公平对比之下,性能与压缩率的账上,再没有属于布局的盈余。

四、读取位置的算术:镜花水月

定位一次读取需要两步映射:逻辑偏移→压缩单元,压缩单元→物理地址。两种布局各自只能免费完成一步,且方向相反:

fixed-input:  offset ──[÷C,算术]──→ 单元 ──[查表]──→ 物理位置
fixed-output: offset ──[÷4K]──→ 逻辑块 ──[?]──→ 单元 ──[×4K]──→ 物理位置

关键在于:fixed-output 免费的乘法步位于链路末端,而查询永远从逻辑偏移发起——这步算术便利如镜花水月,在读路径上永远用不上。它缺失的"逻辑→单元"映射是数据相关的,无法算术求得,只剩两个选择:稠密索引(每个逻辑块一项、每项 8 字节 [1],比大窗口 fixed-input 按单元计的索引稠密一个数量级以上),或者稀疏索引加二分查找(O(log n))。

fixed-input 则没有这个问题:偏移表中相邻两项相减即得压缩单元长度,位置与长度一次查表齐活。在定位这根轴上,fixed-output 的账上只有支出。

五、可寻址性:一则传说

超出 [1] 之外,分发格式的设计讨论中还流传着一条对定长对齐的期待:按需分发、懒加载、块级去重,似乎都以定长块为前提——传说正是从这里开始失真。fixed-input 加一张偏移表,变长块同样是可寻址对象——地址就是索引项里的(偏移,长度),配合 HTTP range 请求即构成完整的按需分发。生产级的 fixed-input 分发方案早已存在(OverlayBD 的 ZFile [2];stargz 的 TOC [3]),且规模庞大。

传说的下落就此查明:可寻址性的源头是索引,而非输出的定长。

六、省内存:一枚颁错的勋章

[1] 还有一条内存效率的宣称:fixed-output 使原位解压成为可能,且每次解压至多读取两个压缩块、大小先验可知,内存开销因此有界。这条宣称同样经不起归因检验——省内存的关键技术,件件记在解压器名下。

其一,部分解压:从流头解到目标产出即停,之后的字节不解。这是压缩流顺序解码的直接推论,对两种布局同样成立。其二,滚动解压:利用压缩算法的滑动窗口(如 LZ4 的 64KB 窗口),只保留窗口大小的历史页面即可持续解码——窗口是算法的属性,不是布局的。其三,直接灌入目标页:解压输出直接写入目标页缓存,省去临时输出缓冲, fixed-input 的读路径同样可以这样做。至于"大小先验可知”,第四节已经给出——压缩单元长度就是偏移表相邻两项之差,并非定长输出的专利。

反向的账更值得记:fixed-output 为这条路径付出的复杂度反而更高。它要求压缩算法提供定输出接口(destSize),这是格式级约束;定位需要按逻辑块计的稠密索引;[1] 的原位解压自身也不免费,需要在构建镜像时模拟解压、逐块判定可行性。这枚勋章该颁给解压器,而不是布局;fixed-output 为它背的复杂度,一分不少。

七、代价:格式的刺青

前六节核的都是收益一侧的故事,代价的账集中记在这一节。

其一是工程复杂度,最终形态是代码量。fixed-input 的两端各是一个简短的循环:构建端切分、压缩、追加、记下偏移;读取端一次查表、一次解压。fixed-output 没有这样的直线:前面各节的每一项结构差异,最终都要落成代码——构建端是一台状态机,读取端是一路分支,代码量成倍提高。这份开销不按次计费,按实现数计费:内核驱动、用户态工具、各语言绑定,每个采用者都要重写一遍。

其二是构建速度。主流压缩库的主干接口是 fixed-input 的:定长输入、变长输出、一次调用,库的优化投入全部集中于此。fixed-output 需要的定输出(destSize)接口只是部分算法的支流变体;绕开它,就得用通用接口反复试压——填入一段输入、观察输出是否越界、越界则回退重压。两条路都慢;且算法库每次升级,红利先落在主干——fixed-output 只能隔岸观望。

其三是演进负担。fixed-input 把自由度留在格式之外:单元大小是每个镜像自选的参数,索引与解压策略都是实现细节,随时可调。 fixed-output 则把关键决策写进了格式:输出定长、块对齐、逐块的原位标志,都是契约条款——日后每一次扩展格式、更换算法、优化读路径,都得背着这张契约走,无从修订。

故事的缺陷在讲述——换一个口径、做一次实测就会现形;代价的缺陷在定义——只要格式还是 fixed-output,每一个镜像、每一个实现就都要照付。实现可以迭代,格式一旦发布只能兼容:内部碎片不会因更聪明的构建工具而消失,定位的查表不会因更勤勉的缓存而省掉,构建期的接口错配也不会因算法库的升级而弥合。它们随格式的每一次使用而复利——这正是"格式级的、永久的"的含义。

于是整笔账就此合上:被宣称的收益,对手用实现手段就能免费获得——粒度、索引、解压器,哪一样都不需要定长输出;而代价全部刻在格式自己身上。故事会褪色,刺青不会。

结论

把归因做完,神话逐一收场:读放大归于粒度,内存效率归于解压器,对齐的红利查无实据,压缩率的大捷只在避开现实对手的口径里上演; [1] 之外的可寻址性期待,同样归于索引——每一项被宣称的优势,要么消失,要么易主。代价则全部留在它自己账上:定位失去算术性、输出块内部碎片、对压缩算法 destSize 接口的约束、构建与运行两侧的工程复杂度、更慢的构建与无从修订的演进契约——格式级的、永久的。

因此我们的结论客气但彻底:这项技术不值得采用。 事实上自 2019 年提出至今,没有任何第二个系统采纳这项技术——它唯一的载体,仍是提出它的那个文件系统自己。设计只读压缩布局时,正确的做法是把自由度留在粒度轴上(按负载选择单元大小)、把索引建好,然后使用 fixed-input。

最后留两条方法论,它们比本文的具体结论更耐久:

  • 归因检验。 见到一项优势,先问"一个实现同样良好的对手方案能否得到它"。能回答这个问题,多数技术营销会当场现形。
  • 时间检验。 多数论文与技术的论点会随时间湮灭,这是常态。制品的幸存不等于论点的幸存——一个系统活得好好的,它的核心主张可能早已被它自己的演进悄悄替换。

参考文献

[1] Xiang Gao, Mingkai Dong, Xie Miao, Wei Du, Chao Yu, Haibo Chen. “EROFS: A Compression-friendly Read-only File System for Resource-scarce Devices.” USENIX Annual Technical Conference (ATC ‘19), 2019. https://www.usenix.org/conference/atc19/presentation/gao

[2] Huiba Li, Yifan Yuan, Rui Du, Kai Ma, Lanzheng Liu, Windsor Hsu. “DADI: Block-Level Image Service for Agile and Elastic Application Deployment.” USENIX Annual Technical Conference (ATC ‘20), 2020. https://www.usenix.org/conference/atc20/presentation/li-huiba

[3] stargz Snapshotter: eStargz (seekable tar.gz) lazy-pulling image support. https://github.com/containerd/stargz-snapshotter

前往 GitHub 评论本文 →

使用 Hugo 构建
主题 StackJimmy 设计