本文是SPDK文档SPDK “Reduce” Block Compression Algorithm的翻译，在读SPDK的文档过程中，刚好看到了SPDK里bdev reduce模块实现背后的算法描述，于是就想着翻译一下，正好也借翻译的同时仔细理解一下背后算法的原理，当然本人的水平有限，如果译文有任何歧义，还请参考原文并以实际原文为准。

概述

SPDK的“reduce”块压缩方案使用SSD存储压缩后的块数据，同时将元数据存放到持久内存中。此元数据包含用户数据的逻辑块到压缩后的物理块的对应关系。本文档中描述的方案是通用的，不依赖于包括SPDK在内任何特定的块设备框架。该算法会在一个叫做libreduce的库中实现。更高层次的软件可以基于该模块创建和呈现特定的块设备。对于SPDK来说，bdev_reduce模块封装了libreduce库，从而在SPDK中提供一个bdev以实现压缩功能。

本方案仅仅解释压缩后的数据块和用于跟踪这些数据块的元数据的管理。它依赖于高层软件模块来执行压缩操作。对于SPDK，bdev_reduce模块利用DPDK compressdev框架执行压缩和解压缩。

（需要注意的是，在某些情况下，数据块可能是不可压缩的，或者无法压缩到足以实现空间节省的程度。在这些情况下，数据可能不经过压缩，直接存储在磁盘上。“压缩的存储块”包括这些不经压缩的块。）

一个压缩块存储设备是一个建立在拥有相似大小的后备存储设备之上的一个逻辑实体。其中的后备存储设备必须是精简置备（thin-provisioned）的从而才能真正意义上从后文描述的实现中获得空间节省。同样该算法除了一直使用后备存储设备上可用的编号最低的块之外，对后备存储设备的实现没有直接的了解。这保证了在精简配置的后备存储设备上使用此算法时，在实际需要空间之前不会分配对应空间。

后备存储的大小，必须考虑最坏情况，也就是所有数据都不可压缩的情况。在这种情况下，后备存储的大小和压缩块设备的大小是一致的。另外，本算法基于永远不会原地写这个前台来保证原子性，所以在更新元数据之前，可能还需要额外的一些后备存储空间来作为临时写缓存。

为了最佳性能考虑，所有后备存储设备都将以4KB为最小单位进行分配、读取和写入。这些4KB的单元被称作“后备IO单元”（backing IO units）。他们被一个称作“后备IO单元索引”（backing IO unit indices）的索引列表中以0到N-1编号进行索引。在一开始，这个完整的索引代表了“空闲后备IO单元列表”（free backing IO unit list）。

一个压缩块存储设备基于chunk进行压缩和解压操作，chunk大小至少是两个4K的后备IO单元，每个chunk所需要的后备IO单元数量，也同样表明了chunk的大小，这个数量或者大小需要在压缩块存储设备创建时指定。一个chunk，需要消耗至少1个，至多chunk大小个后备IO单元数量。举个例子，一个16KB的chunk，有可能消耗1，2，3，4个后备IO单元，最终消耗的数量取决于这个chunk的压缩率。磁盘blocks和chunk的对应关系，存储在持久内存中的一个chunk map里。每个chunk map包含了N个64-bit的值，其中N是每个chunk所包含的后备IO单元的数量。每个64-bit值表示一个后备IO单元的索引。一个特殊的值（举个例子，2^64-1）用来表示因为压缩节省而不需要使用实际的后备存储。chunk map的数量，等于压缩块设备的容量除以它的chunk大小，再加上少量用于保证原子写操作额外的一些chunk map。一开始所有的chunk map都表示“空闲chunk map列表”。

最后，压缩块设备的逻辑映射表通过“logical map”进行表示。这里的“logical map”指的是压缩块存储设备对于对于chunk map的偏移的对于关系。logical map里每个条目是一个64-bit的值，表示所关联的chunk map。一个特殊值（UINT64_MAX）表示没有对应关联的chunk map。映射是通过将字节偏移量除以块大小得到一个索引来确定的，该索引用作块映射条目数组的数组索引。 开始时，逻辑映射表中的所有条目都没有关联的块映射。 请注意，虽然对后备存储设备的访问以 4KB 为单位，但逻辑映射表可能允许以4KB或512B为单位进行访问。

一些例子

为了说明这个算法，我们将使用一个真实的非常小规模的例子。

压缩块设备的大小为64KB，chunk大小为16KB。 这会实现以下几点：

• “后备存储” 需要是一个80KB大小的精简置备（thin-provisioned）逻辑设备。这包括了64KB的压缩设备原始大小，以及为了在最坏情况下保证写原子性而额外分配的16KB大小。
• “空闲后备IO单元列表”（free backing IO unit list）由一个0-19的索引组成，这些索引表示在后备存储里的20个4KB最小IO单元。
• 一个”chunk map”的大小是32字节， 对应每个chunk需要4个后备存储单元（16KB/4KB），以及每个存储单元需要8个字节（64bit）进行表示。
• 需要从持久内存中分配5个chunk map，共160B的空间。这包含了压缩块设备的4个chunk（64KB / 16KB）所对应的4个chunk map以及为了改写已有chunk时需要的额外1个chunk map
• “空闲后备IO单元列表”（Free chunk map list） 将由0 - 4（包含4）进行索引。 这些索引表示这5个被分配的chunk map
• “逻辑映射表”（logical map）需要在持久内存中分配32B空间，这包含了压缩块设备4个chunk的索引，每个索引需要8B（64bit）。

在下面的例子中，”X”符号代表上面所说的那个特殊值特殊值（2^64-1）。

创建初始化（Initial Creation）

                +--------------------+Backing Device  |                    |                +--------------------+Free Backing IO Unit List  0, 1, 2, 3, 4, 5, 6, 7, 8,...