SSD去重：建模和量化分析
原文：J. Kim. Deduplication in SSDs: Model and Quantitative Analysis.
数据去重技术可以有效减少写负载，节约存储空间，进而减少垃圾回收的次数，增加垃圾回收和损耗均衡算法的效率，对SSD的寿命有很好的改进。这篇来自MSST’2012的文章站在了CAFTL和CA-SSD的肩膀上，进一步探讨了数据去重对SSD性能的影响，也就是探讨数据去重是否可以改进SSD的写延迟。
数据去重为SSD带来了很多的好处，但是存在两大挑战：1.数据去重的开销问题，通常SSD的资源有限，只有ARM7或ARM9等低端CPU和少量内存，这和备份归档环境有很大不同；2.SSD的典型负载是否有足够的重复数据？
为了回答这些问题，作者为SSD设计了一个数据去重框架，由指纹生成器、指纹管理、映射管理组成。和CAFTL、CA-SSD一样，分别针对映射表（CAFTL和CA-SSD）、指纹索引（LRU）、哈希计算瓶颈（硬件逻辑和取样法）进行讨论，并提出了解决方案。
针对9个负载的实验表明，平均可以达到17%的重删率，SHA-1硬件逻辑的延迟是80us，平均可以改善延迟15%；当SSD装配了较高端CPU，比如ARM9时，软件实现的取样哈希法也可以获得很好的效果；数据去重平均可以提高2.4倍寿命。
图1展示了SSD的基本结构，以及本文设计的数据去重框架。数据去重的功能组件（指纹生成器、指纹管理和映射管理）都位于FTL。指纹生成器的设计对性能的影响很大，本文分别提出了硬件和软件的实现方案；指纹管理的问题在于应该维护多大的索引，传统的备份和归档应用会维护完整的索引，但SSD的内存有限，因此本文采用一种类似CA-SSD的LRU索引；FTL的映射表很容易将多个逻辑地址映射到同一个物理地址来实现数据去重，但存在的问题是当垃圾回收时，如何快速地更新映射表，本文采用了CA-SSD的反向映射法。
本文对数据去重开销进行建模，寻找去重开销、去重率和写延迟的关系。给定去重开销，要想改进写延迟，必须满足多少去重率。
无去重SSD的写延迟如下，FMprogram是写入数据的延迟，MAPmanage是更新映射表的延迟。
而装备去重的SSD，其写延迟如下。
FPgenerator是计算指纹的时间，FPmanage是查询指纹的时间，DUPrate是去重率。比较两个公式，去重SSD要想改善写延迟，必须满足：
这个等式表示，当去重率高于这个水平时，就可以改善SSD的写延迟。实际上，SSD的写延迟还必须考虑垃圾回收的时间，而数据去重可以减少垃圾回收的次数和时间，因此去重率实际上可以更低。当写数据的时间越长，所需要的去重率就越低。例如，当写数据的时间为1300us，去重的开销是256us，去重率最低需要16%才能获得性能提升。现在最主要的问题是如何减少去重的开销。
作者测试了三种CPU计算SHA-1的延迟，以及SHA-1硬件逻辑的延迟，如图4。可见SHA-1的开销还是很大的，结合公式3，可知使用MicroBlaze和ARM7的SSD无论如何不可能因为去重而获得性能提升。
作者在Xilinx Virtex6 XC6VLX240T FPGA之上实现了SHA-1硬件逻辑，其计算延迟只有80us。它由五部分组成：主控制单元，负责管理总体逻辑；IO控制单元，负责与CPU交互；双端口BRAM，存储4KB临时数据；SHA-1核心，实现标准SHA-1算法；哈希比较器，检查两指纹是否相同。使用Verilog HDL 2001进行RTL编码（对FPGA、Verilog HDL、RTL编码完全不懂啊，所以全部抄下来了）。采用硬件逻辑，只需要5%的去重率就可以提升性能。
使用硬件逻辑增加了产品的价格，对于装备了ARM9或者更高端CPU的SSD，采用软件方法也是有机会获得性能提升的。通过实验，发现重复数据具有类似TVL（CA-SSD）的时间局部性，即大多数重复数据的到达时间非常接近，基于此提出了抽样哈希法（和CAFTL的抽样有些不一样）。图7是取样法的图示，它利用了SSD的写缓冲区，大概32MB，最多可以缓冲8000个page。当SSD接收到一个写请求，首先从page内偏移q的位置取样p（>=20）字节，使用这p字节作为哈希索引插入page到某个bucket中，因此相同p字节被插入同一个bucket。当缓冲区满时，只需要对长度大于1的bucket进行哈希计算，预期可以减少大量不必要的计算开销。缓冲区的大小会对去重率产生影响。
使用的是和CA-SSD几乎一样的LRU索引，按照指纹的产生时间组织队列。图8是实验结果，当LRU索引的规模超过2048时，能够很好挖掘所有负载的重复数据。
去重将逻辑地址到物理地址的映射关系变为n-to-1，这里最大的挑战是如何优化垃圾回收：移动一个合法page，需要更新n个逻辑地址的映射关系。而优化垃圾回收问题又可以分为两个问题，定位逻辑地址和更新映射关系。
本文并没有提出新的映射表设计，而是比较了CAFTL和CA-SSD，二者做出了不同的权衡。CAFTL和CA-SSD的比较一文已经将二者进行了对比。CAFTL的读操作需要额外访问二级映射表；同时，CAFTL移动一个合法page只需要更新一个位置，而CA-SSD需要更新所有对应的逻辑page的映射关系。CA-SSD垃圾回收的效率取决于iLPT表中链表的平均长度，通过实验发现，大多数page的重复次数不超过3，因此作者选择了CA-SSD。
实验所用9个负载的重复数据特性如图10所示，去重率从4%到51%，平均17%。
实验的重点是检查去重对写延迟的影响，图12比较了装备SHA-1硬件逻辑的数据去重和无去重SSD，以及引起垃圾回收时的结果。可以看出对于9个负载，数据去重SSD的写延迟都降低了；有垃圾回收时，数据去重对写延迟的改进更加明显，可见数据去重可以加速垃圾回收。
图14是软件实现取样哈希的效果。14(a)显示了取样法损失的去重率，大概能获得完全哈希64%的重删率。14(b)比较了无去重、取样哈希、完全哈希的写延迟，这里使用的CPU是ARM9，取样哈希比完全哈希的写延迟更小，和无去重差不多。
数据去重技术可以有效减少写负载，节约存储空间，进而减少垃圾回收的次数，增加垃圾回收和损耗均衡算法的效率，对SSD的寿命有很好的改进。这篇来自MSST’2012的文章站在了CAFTL和CA-SSD的肩膀上，进一步探讨了数据去重对SSD性能的影响，也就是探讨数据去重是否可以改进SSD的写延迟。
数据去重为SSD带来了很多的好处，但是存在两大挑战：1.数据去重的开销问题，通常SSD的资源有限，只有ARM7或ARM9等低端CPU和少量内存，这和备份归档环境有很大不同；2.SSD的典型负载是否有足够的重复数据？
为了回答这些问题，作者为SSD设计了一个数据去重框架，由指纹生成器、指纹管理、映射管理组成。和CAFTL、CA-SSD一样，分别针对映射表（CAFTL和CA-SSD）、指纹索引（LRU）、哈希计算瓶颈（硬件逻辑和取样法）进行讨论，并提出了解决方案。
针对9个负载的实验表明，平均可以达到17%的重删率，SHA-1硬件逻辑的延迟是80us，平均可以改善延迟15%；当SSD装配了较高端CPU，比如ARM9时，软件实现的取样哈希法也可以获得很好的效果；数据去重平均可以提高2.4倍寿命。
1.概述
图1展示了SSD的基本结构，以及本文设计的数据去重框架。数据去重的功能组件（指纹生成器、指纹管理和映射管理）都位于FTL。指纹生成器的设计对性能的影响很大，本文分别提出了硬件和软件的实现方案；指纹管理的问题在于应该维护多大的索引，传统的备份和归档应用会维护完整的索引，但SSD的内存有限，因此本文采用一种类似CA-SSD的LRU索引；FTL的映射表很容易将多个逻辑地址映射到同一个物理地址来实现数据去重，但存在的问题是当垃圾回收时，如何快速地更新映射表，本文采用了CA-SSD的反向映射法。
2.建模
本文对数据去重开销进行建模，寻找去重开销、去重率和写延迟的关系。给定去重开销，要想改进写延迟，必须满足多少去重率。
无去重SSD的写延迟如下，FMprogram是写入数据的延迟，MAPmanage是更新映射表的延迟。
而装备去重的SSD，其写延迟如下。
FPgenerator是计算指纹的时间，FPmanage是查询指纹的时间，DUPrate是去重率。比较两个公式，去重SSD要想改善写延迟，必须满足：
这个等式表示，当去重率高于这个水平时，就可以改善SSD的写延迟。实际上，SSD的写延迟还必须考虑垃圾回收的时间，而数据去重可以减少垃圾回收的次数和时间，因此去重率实际上可以更低。当写数据的时间越长，所需要的去重率就越低。例如，当写数据的时间为1300us，去重的开销是256us，去重率最低需要16%才能获得性能提升。现在最主要的问题是如何减少去重的开销。
3.指纹计算
作者测试了三种CPU计算SHA-1的延迟，以及SHA-1硬件逻辑的延迟，如图4。可见SHA-1的开销还是很大的，结合公式3，可知使用MicroBlaze和ARM7的SSD无论如何不可能因为去重而获得性能提升。
作者在Xilinx Virtex6 XC6VLX240T FPGA之上实现了SHA-1硬件逻辑，其计算延迟只有80us。它由五部分组成：主控制单元，负责管理总体逻辑；IO控制单元，负责与CPU交互；双端口BRAM，存储4KB临时数据；SHA-1核心，实现标准SHA-1算法；哈希比较器，检查两指纹是否相同。使用Verilog HDL 2001进行RTL编码（对FPGA、Verilog HDL、RTL编码完全不懂啊，所以全部抄下来了）。采用硬件逻辑，只需要5%的去重率就可以提升性能。
使用硬件逻辑增加了产品的价格，对于装备了ARM9或者更高端CPU的SSD，采用软件方法也是有机会获得性能提升的。通过实验，发现重复数据具有类似TVL（CA-SSD）的时间局部性，即大多数重复数据的到达时间非常接近，基于此提出了抽样哈希法（和CAFTL的抽样有些不一样）。图7是取样法的图示，它利用了SSD的写缓冲区，大概32MB，最多可以缓冲8000个page。当SSD接收到一个写请求，首先从page内偏移q的位置取样p（>=20）字节，使用这p字节作为哈希索引插入page到某个bucket中，因此相同p字节被插入同一个bucket。当缓冲区满时，只需要对长度大于1的bucket进行哈希计算，预期可以减少大量不必要的计算开销。缓冲区的大小会对去重率产生影响。
4.指纹索引
使用的是和CA-SSD几乎一样的LRU索引，按照指纹的产生时间组织队列。图8是实验结果，当LRU索引的规模超过2048时，能够很好挖掘所有负载的重复数据。
5.映射表
去重将逻辑地址到物理地址的映射关系变为n-to-1，这里最大的挑战是如何优化垃圾回收：移动一个合法page，需要更新n个逻辑地址的映射关系。而优化垃圾回收问题又可以分为两个问题，定位逻辑地址和更新映射关系。
本文并没有提出新的映射表设计，而是比较了CAFTL和CA-SSD，二者做出了不同的权衡。CAFTL和CA-SSD的比较一文已经将二者进行了对比。CAFTL的读操作需要额外访问二级映射表；同时，CAFTL移动一个合法page只需要更新一个位置，而CA-SSD需要更新所有对应的逻辑page的映射关系。CA-SSD垃圾回收的效率取决于iLPT表中链表的平均长度，通过实验发现，大多数page的重复次数不超过3，因此作者选择了CA-SSD。
6.实验
实验所用9个负载的重复数据特性如图10所示，去重率从4%到51%，平均17%。
实验的重点是检查去重对写延迟的影响，图12比较了装备SHA-1硬件逻辑的数据去重和无去重SSD，以及引起垃圾回收时的结果。可以看出对于9个负载，数据去重SSD的写延迟都降低了；有垃圾回收时，数据去重对写延迟的改进更加明显，可见数据去重可以加速垃圾回收。
图14是软件实现取样哈希的效果。14(a)显示了取样法损失的去重率，大概能获得完全哈希64%的重删率。14(b)比较了无去重、取样哈希、完全哈希的写延迟，这里使用的CPU是ARM9，取样哈希比完全哈希的写延迟更小，和无去重差不多。