SPDK的“Reduce”块压缩算法
本文是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, 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 |
+---+---+---+---+在32KB偏移量处写入16KB（Write 16KB at Offset 32KB）
- 找到逻辑映射表（logical map）对应的index。32KB偏移量除以16KB的chunk size，得到index为2。
- Logical map里的第2个单元是一个“X”，也就是说当前这16KB还没有被写入过。
- 在内存中分配16KB的buffer。
- 将写入的这16KB数据压缩后，存入到刚刚分配的buffer中。
- 假设数据被压缩到只剩6KB，那么就需要2个4KB的后备IO单元。
- 从空闲后备IO单元列表中分配2个block（编号0和1）。需要注意的是，永远都从空闲后备IO单元列表中最小的单元还是分配，这样可以保证在thin-provision情况下，不会用到多余的后端存储，从而节省容量。
- 将压缩后的6KB数据存储到后备存储的第0和第一个单元。
- 从空闲chunk map列表中分配一个chunk map 0。
- 将（0，1，X，X）存储到chunk map 0中。这表示只有2个后备IO单元被用来存储这16KB数据。
- 把chunk map的编号0，写到逻辑映射表（logical map）的第二个单元中。
+--------------------+
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 |
+---+---+---+---+在8KB偏移量处写入4KB（Write 4KB at Offset 8KB）
- 在逻辑映射表中找到对应的index。 8KB偏移量，除以16KB的chunk size，得到index为0。
- 逻辑映射表中的0号条目是“X”，这表示这16KB还没有被写入过数据。
- 写入请求不是一个完整的16KB chunk大小，所以我们必须要先分配一个16KB的buffer用于暂存源数据。
- 把需要写入的4KB数据写入到这16KB buffer的8KB偏移处，并把buffer其他的地方填0。
- 再分配16KB的目标buffer。
- 把16KB的源数据，压缩后存入到目标buffer中。
- 假设数据被压缩到3KB，这将需要1个4KB的后备IO单元。
- 从空闲后备单元列表中分配一个block（编号2）。
- 把3KB数据写入到编号2的block中。
- 从空闲chunk map列表中分配一个空闲chunk map(编号1)。
- 把（2，X，X，X）写入到chunk map中。
- 将chunk map的索引（编号1）写入到逻辑映射表的第0个条目里。
+--------------------+
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 |
+---+---+---+---+在16K偏移量处读取16KB数据（Read 16KB at Offset 16KB）
- 16KB偏移量，在逻辑映射表中对应第1个条目。
- 逻辑映射表第1个条目是“X”，这说明这个16KB空间还没有被写入过任何数据。
- 由于这16KB的chunk还没有被写入过任何数据，所以直接这个读请求直接返回全0。
在4KB偏移量处写入4KB（Write 4KB at Offset 4KB）
- 4KB偏移量，在逻辑映射表中对应第0个条目。
- 逻辑映射表的第0个条目是“1”，由于我们并不是覆盖写整个chunk，所以我们必须要进行一个读-改-写（read-modify-write）操作。
- chunk map 1仅仅指定了一个后备IO单元（编号2），分配一个16KB的buffer，并讲编号2的后备IO单元读入到这个buffer，这个buffer后面会被叫做压缩数据buffer。
需要注意的是，因为我们一下子分配了16KB的buffer而不是只分配4KB，我们可以继续使用这个buffer作为后面新压缩数据的存放地点。 - 再分配一个16KB的buffer用于存放解压后的数据。解压压缩数据buffer里的数据，并将数据存入刚分配的buffer里。
- 把需要写入的4KB数据写入到解压数据buffer的4KB偏移处。
- 把解压数据buffer里的数据压缩，并放到压缩数据buffer中。
- 假设新的数据压缩后大小5KB，这将需要2个4KB的后备IO单元。
- 从空闲后备IO单元列表里，分配编号为3和4的两个block。
- 将这个5KB数据写入到3和4这两个block中。
- 从空闲chunk map列表中分配编号2的chunk map。
- 将（3，4，X，X）写入到编号2的chunk map中。需要注意的是，到当前节点，这个chunk map还没有被逻辑映射表引用，如果此时出现了掉电，当前chunk的数据依然是保持完整的。
- 将chunk map的编号2写入到逻辑映射表中。
- 释放编号为1的chunk map，并放入到空闲chunk map列表中。
- 释放编号为2的后备IO单元，并将编号放入到空闲后备IO单元列表中。
+--------------------+
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的请求（Operations that span across multiple chunks）
针对跨越多个chunks的请求，逻辑上这个请求会被分割成多个请求，每个请求关联一个chunk。
举例：在4KB偏移处写入20KB数据
在这个场景下，这个写请求会被分割成：一个在4KB偏移处写入12KB数据的请求（只影响逻辑映射表的第0个条目），以及一个在偏移量16KB处写入8KB的请求（只影响逻辑映射表的第1个条目）。
每个子请求都独立的基于上述的算法进行处理，直到这两个子请求全部完成时，原始的20KB写入操作才会返回。
Unmap操作（Unmap Operations）
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操作（Write Zeroes Operations）
写0操作的流程和Unmap操作类似，如果一个写0操作覆盖了整个chunk，我们也可以在逻辑映射表中完全移除整个chunk的对应条目，然后后续的读操作也会返回全0。
Restart
一个使用libreduce模块的应用程序，有可能需要定期退出并重新启动。当应用程序重新启动的时候，会重新加载压缩卷，从而恢复到应用程序退出之前的状态。
当压缩卷被加载的时候，空闲chunk map列表和空闲后备IO单元列表会通过扫描逻辑映射表的形式进行重建。逻辑映射表只会保存有效的chunk map索引，同样的，chunk map只会保存有效后备单元索引。
任何没有被引用的chunk map以及后备IO单元，都会被认为是空的，并加入到对应的空闲列表中。
这就保证了如果系统在一个写操作的中间状态下崩溃后（比如在chunk map被更新，但还没写入逻辑映射表的过程中崩溃）重启的过程中，所有未完成的写入操作都会被忽略。
对同一个chunk的并发操作（Overlapping operations on same chunk）
具体实现时，必须要考虑针对同一个chunk并发操作的情况。比如第一个IO需要对chunk A写入某些数据，同时又有第二个IO也需要对chunk A进行写入。在这种情况下，第二个IO必须等第一个IO完成之后才能开始。
针对类似情况的进一步优化，超出了本文档的描述范围。
精简置备的后备存储（Thin provisioned backing storage）
后备存储设备必须是精简置备的，从而才能在压缩场景下实现空间节约。本文的算法永远都会使用（重用）后备存储上最靠近偏移量0的后备IO单元。
这确保了即使后备存储的空间和压缩块设备的大小接近，但是直到确实需要后备IO单元的时候，才会真正从后备存储设备上分配存储空间。