集中式存储系统的数据去重解决方案研究与思考

Design of data deduplication for a centralized storage system

简介

大型存储系统是非常复杂，模块众多的软硬件系统，深入了解每个模块都会给我带来非常多的成长和感受，所以我想通过这篇文章，我将介绍自己熟知的一种存储系统的去重方案，并把自己的了解的存储去重架构相关知识以及一些自己的思考分享出来，仅简单的一篇文章很难把所有的细节讲清楚，因此我从我认为几个比较重要的模块出发，试图解释清楚其中的逻辑，以及我的一些思考。

        这个数据存储引擎主要面向的业务是存储、备份、恢复 服务，当然也有提供文件存储和对象存储的功能，但在业务层，有一些设计是单独针对数据备份、恢复进行优化的。

        在我们熟知的分布式存储系统里，数据的高可用（HA）一直都是不可或缺的标准，那我们就需要一些比如多副本、Erasure Coding（EC）之类的方法实现数据的高可用。特别对于多副本的系统，两个storage里都有数据A，那么再做dedup反而费力不讨好了，所以多副本的HA和dedup是不应该被放在同一层里的（针对分层架构的存储系统）。deduplication可以放在数据多副本HA前一层或后一层，我们就是把他放在前一层，先做deduplication，然后对所有deduplicated data做HA，那其实就可以做在File system或硬件系统（RAID）甚至公有云/私有云里。放在数据多副本HA后一层，也是完全没问题的，比如可以针对单个storage进行dedup，所以我们文章标题定为在一个集中式的存储系统里的数据去重，并不意味着它是不适用于分布式集群的，我只是想把它和整个集群的globle deduplication区分开。如果是用EC做HA的话，我觉得上述的问题应该是不存在的。

        这里所有的讨论都是针对单个节点或集中式的存储系统，至于可扩展的分布式存储系统的globle data deduplication(后面会单独具体讨论)。这种方案适合单个storage server(crunk server) 的数据去重，也适合集群中多个storage server/data server之间不需要deduplication的场景（不影响storage server之间可以做duplication/replication）。

引内部资料：

Storage Reduction method:

• Compression ​

Reduces size of files ​

Checks for repeating patterns within a file​

Data reduction does not increase over time​

• SIS – Single Instance Storage​

Checks for multiple instances of a file (file-level deduplication)​

Data reduction is not block- or segment-level changes require full copies of the file​

Used by Microsoft Exchange​

• Deduplication​

Checks for multiple instances of some sub-file data block (segment-level deduplication)​

Uses a database to record instances of segments and files​

Data reduction is significantly reduced by 50-500 times​

关于deduplication的基础知识我们这里不做太多介绍，主要针对segment-level deduplication的研究。

Fragmenting Data

Fragmenting data 和后面的segmenting data（chunking data）属于不同级别的切块，所以就保留了英文的术语，这里是系统的第一次切块，对于备份业务，它存储的往往是比较大的数据，因此这里的Fragment一般在50G的级别，这一层的存在是至关重要的，比如我们要存一个1T的目录或数据库，那么首先需要切分成20个fragments，因为有了这一层我们处理数据会更加高效、灵活。Fragment data和最终数据持久化的data container是没有直接关系的，有直接关系的是Segment data，因为我们需要知道一个fragment由哪些Segments 组成，而最终存储Segments的是data container，一个映射关系结构体也将因此而被创建出来。

       其实在这里deduplication应该放在存储系统的哪一层就需要简单介绍一下了，我目前了解有两种方案，一种是 Inline deduplication， 另一种属于Out of line deduplication(aka: post-processing deduplication)。

      我们当前这个系统使用的就是第一种Inline deduplication, 他需要嵌入到存储系统里。像CEPH，就使用了第二种post-processing deduplication。 他们有一个很重要的区别就是在切块和算指纹的先后，post-processing deduplication会先做chunking，将数据存起来，然后进行算指纹去重，而Inline deduplication一开始不做chunking存储据，是因为我们这个chunk里的数据要先做去重，被检测到去重的数据是不需要做持久化的。可以看到Inline deduplication的下一步直接就是segmenting data。

这两种方案各有优缺点，在Calculating Fingerprint章节里还会详细讨论一下，这里就先简单引入一下概念。

       对于文件元数据的管理我们这里不做过多介绍，有机会会介绍基于这个存储引擎我们如何开发的文件存储和对象存储功能。

       需要详细说明的是我们这个存储引擎在设计时对于已经持久化成功的数据是没有overwrite的操作的，但可以通过Append+Garbage Collection的功能去实现overwrite，这样也保证了我们所有要落盘的数据永远都是顺序写的（当然肯定也会有读写放大等问题需要思考）。

       至于怎么实现的文件存储里的write操作，就不在这里过多介绍了。

Segmenting Data（Chunking Data）

根据微软和EMC的重复数据删除研究（Todo: add reference），他们的生产存储系统中分别约有50%和85%的数据是冗余的，而且是能够通过deduplication技术进行删除的。真正对冗余数据进行去重能达到多少dedup rate，这和选择什么样的切块算法是密切相关的。

       首先我们在客户端提供一个写接口，接收流式数据，收到的数据我们对其进行切块处理，这里选择切块的方法就很重要了，不同的算法显然会对最终的dedup rate有很大的影响。

       我们这里拿最经典的定长切块算法:fixed-size segmenting(aka FSC: fixed-size chunking)来举例, 固定segment data长度使得我们在切块过程中节省了cpu的资源，降低了切块逻辑的复杂性，在备份存储业务中，它适用于大部分的数据修改方式：append、overwrite，这些操作不会影响数据的位置，原始数据并不会有位移行为（boundary-shifting problem）。

       切块长度的设定也是非常讲究的，理想情况下我们切的segment Object(SO)越小我们可能得到的数据dedup rate约高，但是dedup metadata的数量限制又要求我们不能把数据切的过小，要知道一旦确定了切块大小，那么dedup metadata和data就有一个固定计算比例，比如我们使用128K作为SO的最大值（遇到不足128K的就按照实际大小切块）Fingerprint使用SHA256，然而我们可能还需要一些数据记录这个SO持久化后的磁盘位置、数据结构的开销，那SO data和其Fingerprint structure的比例就是2731：1，假如我们需要存最多1PB的数据，那么Fingerprint consumption 是 384GiB，如果全部加载到内存里这显然是一个很大的开销，后面我们会详细讨论这个事情，以及在这个上面做过的很多优化，比如如何减小这个内存开销，具体可以参考【Sparse Indexing: Large Scale, Inline Deduplication Using Sampling and Locality】。

       所以总的来说选择一个合适的定长切块大小是非常重要的，需要我们反复权衡，因为一旦我们固定了这个fixed length值，那么随着系统长时间运行，想要再次修改这个值，需要付出的代价就会比较大了，最直观的影响就是dedup rate迅速下降(就像你半年前特别喜欢一双鞋，但当时没钱，好不容易把钱攒够了，没试穿直接买下了，回家发现由于你的脚已经变大了，鞋码已经不合适了，但是这鞋还不能退，那你只能要么忍受着继续穿，要么攒钱再买一双，不过我相信再买第二双的时候你肯定会先试一试，just kidding…)，所以遇到这种问题的选择也不多，我们要么接着用原来的值，要么就得做好storage急速增长的准备。如果我们可以在前期做大量调研测试工作，这应该会帮我们在后期少走很多弯路（in-progress）

        在切块算法中还有一大类属于变长切块算法：Varible-size segmenting,比如 Content-Defined Chunking(CDC), 它可以在规定的范围内对数据进行扫描计算哈希值，寻找符合条件的特征值。它在一些场景中起到了非常重要的寻找冗余数据的作用，比如在CEPH里就提供了FastCDC【a Fast and Efficient Content-Defined Chunking Approach for Data Deduplication】 和FixedCDC(实际上就是上文提到的FSC)的两种切块算法。还有一些比较常用的变长切块算法，比如Rabin-based CDC, Gear-based CDC, AE-based CDC. 我使用比较多的是Rabin-based CDC, 它在一些场景中表现的比较好，比如boundary-shifting problem、数据库dump的库文件（with compression or encryption feature enabled）、冗余数据分布在不同位置等等场景。

        这是一块非常有意思的领域，有很多论文可以帮我们了解更多有意思的事情，比如如何更快的进行计算/性能优化，如何把数据合理的限制在固定区域范围，实际我在工作中发现我使用的Rabin-based CDC在我给定的范围内有很多是遇到边界不得已进行切块，显然这里还有需要优化的地方。定义边界的行为是希望切的数据块不要过大或过小，所以在边界处切块算是无奈之举，如果算法比较差的极端情况下，它就相当于退化为FSC,还浪费了CPU资源。

       我之前看到过一篇文章【Alternatives for detecting redundancy in storage systems data】就详细对比了不同的workload和不同的切块算法得到的dedup rate。

       当然，变长切块算法的区域范围选择和FSC里的固定长度设置有着一样的修改问题。

       通常我们会把Segmenting Data这个模块部署在Client 或Load Balancing server上，因为他要和Fingerprint calculation 放在一起。

算指纹（Fingerprint Calculation）

这也是一个非常有意思，值得仔细研究的一个领域，其实我们知道Fingerprint就是个哈希值，代表了一个数据块的特征值，所以Fingerprint这个术语简直再形象不过了，就像指纹某种程度上也代表了我们这个人。

       这里需要介绍一下之前提到的关于Deduplication procedure位置的两种方案，一个是我们目前在这讨论的这种 Inline deduplication：

优点:

1. 通过实时的Fingerprint计算，可以快速的删掉冗余数据(包括对比自身的冗余数据和与data storage里的数据)，甚至可以减少传输的throughput，毕竟我们检测到冗余就不会将数据再进行持久化了。这样在某种程度上提高了写的throughput。
2. 不需要额外的空间存储（vs post-processing deduplication）

        另一种Out of line deduplication(aka: post-processing deduplication)，在【Design of Global Data Deduplication for A Scale-out Distributed Storage System】里针对他的design有详细的实现过程，和一些简单的对比讨论（实际我对里面有些观点是有些异议的），针对于论文里的方案我们有机会再详细讨论学习。这里暂时引用一下【Sparse Indexing: Large Scale, Inline Deduplication Using Sampling and Locality】里关于Inline versus out-of-line deduplication的一段话：

However, out-of-line deduplication has several disadvantages compared to inline deduplication:

 (a) the need for an on-disk holding area large enough to hold an entire backup window’s worth of raw data can substantially diminish storage capacity,

(b) all the functionality that a D2D device provides (data restoration, data replication, compression, etc.) must be implemented and/or tested separately for the raw holding area as well as the deduplicated store, and

(c) it is not possible to conserve network or disk bandwidth because every chunk must be written to the holding area on disk.

        这里我们主要讨论的是Inline deduplication，所以以上观点都是突出这种方案的优点（后面有机会会详细讨论两种方案各自的优缺点，及解决方案）。

       接下来有一个比较有意思的事情，我们的的duplication技术是建立在Fingerprint可以作为数据块的唯一特征值的理论基础上的，而对于一个特别大的数据集，较短hash算法会增加碰撞的风险， 一旦出现hash collision那么就涉及到了最高级别的数据安全问题：data loss。所以针对于hash collision的问题，我们一般可能有两种解决方案：

        1.将指纹升级为更加复杂的hash算法（我经历过系统的指纹hash算法升级，这会给系统软件升级和兼容性带来了不小的挑战）。

        2.直接对比原始数据，这无疑会给存储系统的写延迟和吞吐带来降级影响，具体的性能可能还要取决于磁盘的吞吐能力。随着NVME和RDMA等技术的应用，可能会把性能影响降的很低，但对于存储一些冷数据，比如备份业务，大部分的存储介质的读写能力还是比较差的，这种方案会对这种业务造成很大影响。

思考：其实我们是可以给数据做分级的，安全级别高的数据是完全是可以采用第二种方案，而对于一些安全级别不高的，第一种方案是完全可以胜任的，毕竟我们在讨论的是一个极小概率事件，这里也不做过多描述了。

        这里有一些性能必须要优化地方，比如：哈希运算是一个比较耗费CPU资源的过程，我们可以通过多线程和cpu指令集(AVX、SSE…)优化和加速运算。不过多线程可能会在某种程度上影响Varible-size segmenting的dedup rate(有机会可以做深入讨论).

数据去重（Data deduplication）

在一批数据指纹计算结束后，我们需要对这批缓存的数据进行dedup，这里的dedup分为两种： self-dedup 和global-dedup，这是判断数据（SO）是否最终落盘之前的最后一道关卡。

self-dedup/global-dedup：顾名思义我们既需要对数据自身进行dedup，同时也需要进行全局的dedup，那么我们就来详细介绍这两个步骤。

self-dedup：

        首先我们需要做的就是缓存当前Fragment数据的指纹集合，他肯定是in-memory的，毕竟它存储的是一直再增加的数据，一旦这里检测有重复的数据那么我们只需要原地记录对应的指纹和对应SO的存储位置就可以了，所以这里我们还需要一个数据结构记录数据内容的映射关系（FCR: Fragment Content Relation），它顺序记录着所有的SO的指纹、存储位置（DCID）、size等信息。在后面读取Fragment的数据时，就需要查找FCR里的记录，所以它最大容纳的数量限制对查找性能是有很大影响的，这也是为什么要有Fragment这一层的原因之一。

global-dedup：

既然是全局的dedup，那我们就需要在有一个地方存放指纹及其相关信息的结构（FP-Cache: In-memory Fingerprint index Cache），它应该具有：

        1.支持最多容纳十亿级别的数据容量。

        2.查询快，插入快，删除快，需要O(1)的时间复杂度

        3.支持高并发。

        4.支持扩容缩容，且业务不应该收到可感知的影响。

        就像我们在Segmenting Data里描述的，它的内存占有量可能会达到数百GiB。这是个很有意思的造轮子的工作，我想把他放到单独的一个地方详细讨论我们的做法，因为确实花费了不少的精力。

        在FP-Cache里查询完成如果仍然没有命中的话，那就完成了data deduplication操作，下一步就是存储数据。

        这里显然有很多需要性能优化的细节，比如面对高并发的写请求，我们怎么通过设计去帮助系统处理这种高并发。

思考：

        针对FP-Cache我们是否能通过更加好的方法，让系统更加聪明的动态加载相应的指纹集，而不是上面那种简单的空间换时间的设计，这个详情可以参考【Sparse Indexing: Large Scale, Inline Deduplication Using Sampling and Locality】，里面介绍一种取样筛选champions的做法。实际上我们后面也改为了相似的方式降低了FP-Cache的内存占用。

        当然，我们也是可以使用数据库将所有的指纹缓存，然后FP-cache利用例如LRU规则去加载指纹信息，我的看法是这要配合业务来考虑，首先这个数据库更新时与FP-cache会有一致性的问题需要维护，同时如果使用第三方服务型数据库无疑给系统带来的更多的复杂性，嵌入式的存储面对如此大量的数据可能会有性能问题，实际上我们也测试过使用redis对比，得到的结果是需要的内存更多，查询时间也会更多，还需要更多的精力去了解数据库产品及优化。

    

经过这一层的过滤，我们的数据可以开始进行数据持久化了。

存储数据（Storing Data）

写数据无非就是把没有被去重掉的数据写到磁盘里，这里对Data Container做了分层：

Data Container Location：

Mount Point:

        利用简单的除余算法把相应的数据写入对应的mount point。这里需要考虑mount point的capacity, 应该根据各自的容量进行相应的sharding。

Data Group:

        将大量的data containers分到不同的data group里，保证目录内不会有过多的文件。另外，这一层可以使分配Data Container ID不用一个一个的申请，而是一次申请整个group资源做相应分配。

Data Container:

        他算是磁盘的最小存储单元了，缺省最大值和GFS的chunk size一样，都是64MB，他需要一个全局唯一的ID(DCID)，在我们上面的提到的Fragment Content Relation里就有这个ID帮助确定SO的DC位置，当然一个DC里会有很多的SO, 关于如何管理DC，这里有很多做法，比如：我们可以通过给DC文件增加头文件来帮助锁定指纹是FP1的SO的位置（这样的话，一个DC就有两个文件组成，一个data、一个header，但header的存在也会给系统造成大量的小文件，这里有优点也有缺点）。

DC里面的存放的SO数据是可以做加密、压缩等处理，这样可以增加数据的安全性，和减少磁盘空间。

每个SO的CRC校验信息也必不可少。

Garbage Collection

垃圾回收是通过查看DC的引用去确定是否可以删除这个DC,那么就需要一个含有DC及其引用的DB（Reference DB），它记录着这个DC被那些Fragment引用（实际上在Fragment之上还有一层，先随意起个名字：OFO: Over Fragment Object, OFO结构里记录着关于这个Fragment的一些重要的信息，比如：找到Fragment的映射关系FCR在磁盘的位置，上面介绍中这里我把这一层直接去掉了，主要是想尽量简化文章内容，这里的DC记录的引用实际上就是OFO的，通过OFO可以找到对应的Fragment），如果没有任何引用，那这个DC就可以被删掉了。注：这里删除过程中必须要加锁保护，否则很有可能会出现data loss。

Data Location

数据最终落盘的位置分布是很重要的，分布不好会影响到读的性能，也会影响到Garbage Collection，在这上面有很多的优化工作。

还有一些必要的功能就不详细介绍了：

CRC check

Compaction

Duplication/Replication

如果后端不是local disk，而是接对象存储（AWS、Azure…）的话，还有一些功能、优化。

提交元数据（Metadata Commit）

这里的元数据是dedup的元数据，一旦以上操作成功完成，那么我们需要对一些元数据进行持久化，比如：

• OFO（Over Fragment Object）
  • 记录data sharding的信息
    • Reference DB的更新
      • FP-Cache的加载

这里的元数据是至关重要的，是会有一些WAL、checkpoint等的逻辑来防止数据丢失的。

元数据的管理其实算是整个系统中最复杂，最核心的地方了。

错误处理（Error handling）

理论上，在以上任意一个步骤出错我们都应该有相应的错误处理。

实际也确实是这样的，比如：

        如果100G的数据写了60G之后返回写失败了（有很多情况，比如storage server连不上了、磁盘出现问题，进程crash了等等）这时我们需要清理那些写到后端的数据（Garbage Collection），但是如果立刻清理的话，还得考虑断点续传的问题，所以就需要延时删除。

这些错误处理遍布着整个系统的每个步骤，这里就不错一一描述了。

性能优化（performance optimization）

性能优化是个非常广的话题了。感觉越写越多了，就先到这儿吧

Client

Load Balancing server

Metadata server(MDS)

Storage server(chunk server)

总结（conclusion）

这种方案对于扩展到分布式存储globle deduplication里，有些地方的架构设计还是需要仔细斟酌的, 比如：FP-Cache的查询、分布，去重元数据的高可用等。

如果有任何疑惑或者有问题的地方，请帮忙指出，非常感谢！

引用（reference）

1. Design of Global Data Deduplication for A Scale-out Distributed Storage System
2. TiDedup: A New Distributed Deduplication Architecture for Ceph
3. FastCDC: a Fast and Efficient Content-Defined Chunking Approach for Data Deduplication
4.  POLICRONIADES, C., AND PRATT, I. Alternatives for detecting redundancy in storage systems data. In Proc. of the General Track, 2004 USENIX Annual Technical Conference (Boston, MA, USA, June 2004), USENIX Association, pp. 73–86.
5. S. Ghemawat, H. Gobioff, and S.-T. Leung. The Google file system. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP ’03), Bolton Landing, NY, Oct. 2003. ACM.
6. Sparse Indexing: Large Scale, Inline Deduplication Using Sampling and Locality
7. veritas internal materials