本文是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。 这会实现以下几点：
在下面的例子中，”X”符号代表上面所说的那个特殊值特殊值（2^64-1）。
+--------------------+
Backing Device | |
+--------------------+
Free Backing IO Unit List 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
+------------+------------+------------+------------+------------+
Chunk Maps | | | | | |
+------------+------------+------------+------------+------------+
Free Chunk Map List 0, 1, 2, 3, 4
+---+---+---+---+
Logical Map | X | X | X | X |
+---+---+---+---+ +--------------------+
Backing Device |01 |
+--------------------+
Free Backing IO Unit List 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
+------------+------------+------------+------------+------------+
Chunk Maps | 0 1 X X | | | | |
+------------+------------+------------+------------+------------+
Free Chunk Map List 1, 2, 3, 4
+---+---+---+---+
Logical Map | X | X | 0 | X |
+---+---+---+---+ +--------------------+
Backing Device |012 |
+--------------------+
Free Backing IO Unit List 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
+------------+------------+------------+------------+------------+
Chunk Maps | 0 1 X X | 2 X X X | | | |
+------------+------------+------------+------------+------------+
Free Chunk Map List 2, 3, 4
+---+---+---+---+
Logical Map | 1 | X | 0 | X |
+---+---+---+---+ +--------------------+
Backing Device |01 34 |
+--------------------+
Free Backing IO Unit List 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
+------------+------------+------------+------------+------------+
Chunk Maps | 0 1 X X | | 3 4 X X | | |
+------------+------------+------------+------------+------------+
Free Chunk Map List 1, 3, 4
+---+---+---+---+
Logical Map | 2 | X | 0 | X |
+---+---+---+---+针对跨越多个chunks的请求，逻辑上这个请求会被分割成多个请求，每个请求关联一个chunk。
举例：在4KB偏移处写入20KB数据
在这个场景下，这个写请求会被分割成：一个在4KB偏移处写入12KB数据的请求（只影响逻辑映射表的第0个条目），以及一个在偏移量16KB处写入8KB的请求（只影响逻辑映射表的第1个条目）。
每个子请求都独立的基于上述的算法进行处理，直到这两个子请求全部完成时，原始的20KB写入操作才会返回。
Unmap操作通过从逻辑映射表中删除对应的（如果有）chunk map条目来实现，对应的chunk map会被放回到空闲chunk map列表中，并且任何相关的后备IO单元也会被释放并放回到空闲后备IO单元列表中。
而对于针对chunk的某一部分进行Unmap的操作，相当于对chunk的这一部分写0，如果整个chunk在多次的操作中被整体Unmap掉了，那么未压缩的数据就变成全0了，这样就可以被检测出来，在这种情况下，整个chunk的映射条目也会从逻辑映射表里被移除。
当整个chunk都被Umap掉之后，后续针对该chunk的读操作都会返回全0，这个表现就和上述在16K偏移量处读取16KB数据（Read 16KB at Offset 16KB）的例子一致。
写0操作的流程和Unmap操作类似，如果一个写0操作覆盖了整个chunk，我们也可以在逻辑映射表中完全移除整个chunk的对应条目，然后后续的读操作也会返回全0。
一个使用libreduce模块的应用程序，有可能需要定期退出并重新启动。当应用程序重新启动的时候，会重新加载压缩卷，从而恢复到应用程序退出之前的状态。
当压缩卷被加载的时候，空闲chunk map列表和空闲后备IO单元列表会通过扫描逻辑映射表的形式进行重建。逻辑映射表只会保存有效的chunk map索引，同样的，chunk map只会保存有效后备单元索引。
任何没有被引用的chunk map以及后备IO单元，都会被认为是空的，并加入到对应的空闲列表中。
这就保证了如果系统在一个写操作的中间状态下崩溃后（比如在chunk map被更新，但还没写入逻辑映射表的过程中崩溃）重启的过程中，所有未完成的写入操作都会被忽略。
具体实现时，必须要考虑针对同一个chunk并发操作的情况。比如第一个IO需要对chunk A写入某些数据，同时又有第二个IO也需要对chunk A进行写入。在这种情况下，第二个IO必须等第一个IO完成之后才能开始。
针对类似情况的进一步优化，超出了本文档的描述范围。
后备存储设备必须是精简置备的，从而才能在压缩场景下实现空间节约。本文的算法永远都会使用（重用）后备存储上最靠近偏移量0的后备IO单元。
这确保了即使后备存储的空间和压缩块设备的大小接近，但是直到确实需要后备IO单元的时候，才会真正从后备存储设备上分配存储空间。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。