【现货速发】重复数据删除技术——面向大数据管理的缩减技术

数据是数字经济时代的“石油”，已成为当今世界有价值的资源之一，甚至成为了中美贸易战的主战场。然而，纷繁复杂的海量数据存储管理，对当前数据中心的大数据存储提出了严峻的挑战。

人脑的智慧不仅体现在强化有深刻意义的人生大事，还在于能逐步淡忘无意义的生活琐事。类似人脑，大数据系统也需要依据数据的价值进行存储取舍，删除不必要的数据垃圾，这不仅提升降低整体系统建设和管理成本，更有利于提升大数据系统的性能和智能。

本书是国内本系统讲解重复数据删除技术的专业图书，内容丰富、彩色印刷。

本书以大数据存储为背景，介绍重复数据删除技术。世界著名数据科学家维克托·舍恩伯格教授所著畅销书《大数据时代》的姊妹篇《删除—大数据时代的取舍之道》，强调大数据时代需要在“记忆”和“遗忘”之间做平衡。大数据时代，个人数据隐私受到极大挑战，适当适时地删除数据，有利于保护大数据时代的隐私权。

创作背景

大数据时代的海量数据管理压力催生了很多方法来缓解大数据治理。面对企业数据量的急剧膨胀，需要不断购置大量的存储设备来应对不断增长的存储需求。然而，单纯地提高存储容量，并不能从根本上解决问题。伴随着数据量增长，存储设备采购开支、存储管理成本和数据中心能耗使企业越来越难以承担。特别是海量数据存储管理的复杂性，容易造成存储资源浪费和利用效率低下。因此，为解决信息的急剧增长问题，堵住数据“井喷”，基于数据缩减的高效存储理念油然而生，旨在缓解存储系统的空间增长问题，缩减数据占用空

间，简化存储管理，程度地利用已有资源，降低成本。近十年来，人们对数据缩减的需求越来越大，关键词“压缩软件”在百度指数中搜索热度逐年提升，重复数据删除（Deduplication）也受到持续关注，如图1所示。

图1 数据缩减技术关键词搜索热度

目前，数据压缩和重复数据删除是实现高效存储的两种典型的数据缩减技术。传统的数据压缩技术通过对数据重新编码来降低文件数据冗余度。然而，数据压缩仅能处理文件内部的数据冗余，并且由于需要进行细粒度的字节级比对，处理性能低，无法满足大数据时代的海量复杂数据管理需求。由此催生了重复数据删除技术，它能在文件级、块级和段级进行更广泛的比对，删除大规模共享数据集中重复的数据内容，从而实现快速缩减海量数据容量的目的。

如图2所示，重复数据删除在数据容量缩减上的优势，还能极大地节省企业数据中心的能耗、制冷、管理和场地等方面的成本。尤其是移动终端的普及使得“数据上云”需求提升明显，重复数据删除技术对数据上云至关重要，不仅能够节省用户的数据云存储成本，还能避免重复数据传输过程中的浪费，提升网络带宽利用率。

图2 数据缩减技术对比

重复数据删除相关技术研究早在20世纪90年代就被各国学者广泛研究，主要围绕数字文档中的副本和重复内容检测进行深入研究。2000年左右，出现了不少重复数据删除技术研究成果，比如通过检测重复和相似数据减少数据冗余以节省存储空间，还有利用重复数据删除思想提升因特网带宽限制下的数据传输性能。

2006年，图灵奖得主Jim Gray提出观点“磁带已死，磁盘是新磁带，闪存是新磁盘，随机存储器局部性是为王道。”当随机访问的硬盘代替了顺序访问的磁带，备份和归档存储系统可以获得相当惊人的速度提升，但成本却很难跟磁带库媲美。而基于重复数据删除的磁盘存储刚好可以弥补这一缺陷，通过节省容量使磁盘备份变得高速又经济。这已经作为企业数据保护中新一代存储形式，具有代表性的产品有Data Domain公司的DDFS和HP公司的D2D系列。

近十年来，重复数据删除技术已经成为存储与网络方向的学术研究热点，在产业界也获得了广泛应用，几乎所有存储企业都推出了重复数据删除技术相关的存储产品。结合Ganter的存储技术成熟度曲线，我们画出了如图3所示的重复数据删除技术成熟度曲线。2017年，重复数据删除技术从稳步爬升恢复期进入了生产成熟期，就在此时，我们决定写一本关于重复数据删除技术的专业书。

图3 重复数据删除技术成熟度曲线图

笔者研究重复数据删除技术的这些年，经常会被问到一个问题：“重复数据删除会不会影响数据存储的可靠性？”通常认为，在大数据存储系统中，为了维护大规模复杂系统的可靠稳定运行，需要配置大量的设备进行容错，并保留相应的数据副本或校验数据冗余。然而，重复数据删除技术貌似刚好做了一个逆向操作，违背了大数据存储系统可靠稳定运行的设计原则。实际上，重复数据删除所删除的数据是大数据存储系统上原有文件系统或设备驱动所无法发现和管理的重复数据，而大数据存储系统的可靠容错机制所需的副本和校验数据是原有系统可管理和控制的冗余，并不会被重复数据删除操作删除。例如：两个文件名不同但内容相同的文件，在原有大数据存储系统中各保留两份副本支持容错，重复数据删除只会发现并删除其中一个文件的两份副本。因此，这两者虽然目的相悖，但却因为存储管理层次和实现方式不同可以实现共存。

致谢那些帮助过我的人和组织

开始了解重复数据删除这个词汇是在2008年研究生导师肖老师安排的USENIX FAST论文研讨会。从阅读完普林斯顿大学的李凯教授团队发表的“Avoiding the Disk Bottleneck in the Data Domain Deduplication File System”论文后，被该文中巧妙的系统设计所吸引，并对重复数据删除产生了极大的研究兴趣，迅速放弃了已研究大半年的存储低功耗方向，转为专注研究重复数据删除。读博期间在国家留学基金委的资助下，赴美国内布拉斯加大学林肯分校留学访问两年，在国际著名存储专家江泓教授的指导下对应用感知重复数据删除技术进行了深入研究。从2010年投稿重复数据删除技术综述开始，先后在国内外期刊和会议上发表相关学术论文20余篇，并申请了不少国家发明专利。直到2017年，“企业存储技术”微信公众号作者、“存储争霸”行业群主黄亮专家邀请我给存储同行作一个介绍重复数据删除技术的在线报告，讲完后朋友们建议我把相关内容整理出来写一本相关的专业书。于是，开始了这项耗时近三年的“大工程”。

写这本书的过程也是断断续续，一有时间就写几页，后历时两年多终于完成初稿，并交给清华大学出版社。之所以选择清华大学出版社，是因为存储大牛“冬瓜哥（张冬）”的畅销书《大话存储》《大话计算机》等均出自该出版社，这两本书也是我的常用参考书，本书的出版也得到了冬瓜哥和他的编辑（栾大成主任）给予的写作指导和宝贵建议。在此衷心感谢。

后，这本书的出版，要感谢家人的理解与支持，还要感谢一路走来所有关心、鼓励、帮助我的各位老师和兄弟姐妹们！特别感恩博士后导师于全院士和研究生导师肖侬教授（合著者）给予我的悉心指导与大力支持！

联系作者/联系书友

由于作者所学和经历的局限性，书中难免出现谬误，欢迎读者朋友批评指正，联系邮箱：723908609@qq.com。

另外，本书读书QQ群：1148403700。有任何技术问题都可以在群里与大家探讨交流，读书群也会不定期发布勘误信息、技术资料等。

本书面向从事大数据存储系统设计及相关技术研究和开发工作的读者。既可以作为存储 系统架构师、软件开发工程师、产品或项目经理、数据中心运维人员等的实用工具书，还可 以作为普通高等院校计算机和大数据科学相关专业的教学或科研人员、研究生、高年级本科 生及相关培训机构学员的学习参考书。

本书面向从事大数据存储系统设计及相关技术研究和开发工作的读者。既可以作为存储 系统架构师、软件开发工程师、产品或项目经理、数据中心运维人员等的实用工具书，还可 以作为普通高等院校计算机和大数据科学相关专业的教学或科研人员、研究生、高年级本科 生及相关培训机构学员的学习参考书。

付印金 博士
军事科学院系统工程研究院博士后、陆军工程大学讲师，现为中国计算机学会高级会员、信息存储技术/系统软件专业委员会委员。长期从事网络存储、大数据管理与云计算方向的课题研究。已主持完成国家自然科学基金、江苏省自然科学基金等课题多项，发表学术论文50多篇，申请和授权国家发明专利10余项。主讲过“计算机组成原理”、“计算机网络”与“云计算”等本科与研究生专业课程。

肖侬 教授
中山大学国家超算计算广州中心教授、博士生导师，国防科技大学教授。获得*长江学者特聘教授、国家杰出青年科学基金资助。现任CCF Fellow、中国计算机学会大数据专家委员会副主任、信息存储技术专业委员会副主任。研究方向为网络计算与云计算、新型存储和系统结构，是我国高性能网络计算技术研究的先行开拓者之一。负责过863重大项目和国家自然科学基金重点项目等课题，发表学术论文200多篇。

第1章概述1

1.1　大数据简介2

1.1.1　大数据定义和维度2

1.1.2　大数据管理挑战6

1.2　高效能存储管理9

1.2.1　存储虚拟化10

1.2.2自动分层存储13

1.2.3　自动精简配置17

1.2.4　数据缩减技术19

1.3　本章小结21

第2章存储技术基础23

2.1　存储介质24

2.1.1　磁存储介质24

2.1.2　光存储介质26

2.1.3　电子存储介质28

2.2　存储接口32

2.2.1　IDE接口33

2.2.2　SATA接口33

2.2.3　SCSI接口34

2.2.4　SAS接口35

2.2.5　PCIE接口36

2.2.6　FC接口37

2.3　存储系统架构38

2.3.1　存储器分层结构38

 
2.3.2　RAID技术40

2.4　网络存储系统44

2.4.1　直接连接存储44

2.4.2　网络附加存储46

2.4.3　存储区域网络47

2.4.4　基于对象存储48

2.4.5　几种存储结构的比较49

2.5　本章小结51

第3章大数据管理技术52

3.1　分布式计算框架53

3.2　分布式文件系统56

3.2.1　HDFS58

3.2.2　Ceph59

3.2.3　Lustre　61

3.3　NoSQL数据库63

3.3.1　HBase64

3.3.2　MongoDB66

3.4　大数据仓库67

3.4.1　Hive68

3.4.2　Pig69

3.4.3　Phoenix70

3.5　本章小结73

第4章重复数据删除存储系统74

4.1　重复数据删除的概念及分类75

4.1.1　基本概念76

4.1.2　技术分类78

4.2　重复数据删除存储原理81

4.2.1　系统架构81

4.2.2　主要步骤82

4.2.3　衡量指标83

4.3　重复数据删除技术应用场景84

4.3.1　数据备份84

 
XI

4.3.2　归档存储85

4.3.3　远程容灾85

4.3.4　虚拟化环境86

4.3.5　主存储系统86

4.3.6　新型存储介质87

4.4　相关产品及开源项目87

4.4.1　企业产品88

4.4.2　开源项目91

4.5　本章小结94

第5章重复数据删除关键技术95

5.1　数据划分方法96

5.1.1　全文件分块97

5.1.2　静态分块97

5.1.3　基于内容分块98

5.1.4　基于应用分块100

5.1.5　Delta编码100

5.2　块索引查询优化技术102

5.2.1　基于块局部性的优化策略102

5.2.2　基于分层消重的优化策略104

5.2.3　基于固态存储的优化策略105

5.3　可扩展数据路由技术107

5.3.1　基于分布式哈希表的块级数据路由技术107

5.3.2　基于状态信息的超块级数据路由技术108

5.3.3　基于相似性的文件级数据路由技术109

5.4　块指纹计算加速方法110

5.4.1　多核CPU加速方法110

5.4.2　GPGPU加速方法111

5.5　数据还原方法113

5.5.1　主存储还原方法113

5.5.2　备份存储还原方法113

5.5.3　云存储还原方法115

5.6　垃圾回收技术116

 
5.6.1　引用计数法116

5.6.2　标记清理法117

5.7　高可靠数据配置策略118

5.7.1　纠错编码技术118

5.7.2　副本策略119

5.8　数据安全技术120

5.8.1　加密冲突121

5.8.2　旁路攻击121

5.8.3　所有权证明122

5.9　本章小结123

第6章应用感知源端重复数据删除机制124

6.1　研究背景125

6.2　相关研究工作127

6.2.1　应用感知存储研究127

6.2.2　基于源端重复数据删除的云备份研究127

6.3　基本形式化模型128

6.3.1　符号与基本定义128

6.3.2　模型抽象与问题定义129

6.4　研究动机132

6.5　高效应用感知源端重复数据删除的设计与实现139

6.5.1　ALG-Dedupe体系结构简介139

6.5.2　文件大小过滤器140

6.5.3　智能数据分块策略141

6.5.4　应用感知的消重器141

6.5.5　应用感知索引结构142

6.5.6　段和容器管理143

6.6　实验评估144

6.6.1　实验平台和数据集144

6.6.2　重复数据删除效果145

6.6.3　重复数据删除效率146

6.6.4　云备份窗口147

6.6.5　能耗利用率148

 
6.6.6　云存储代价149

6.6.7　系统开销150

6.7　本章小结151

第7章高可扩展集群重复数据删除技术152

7.1　研究背景154

7.2　相关研究工作155

7.3　基本模型与算法157

7.3.1　超块相似性分析158

7.3.2　基于手纹的数据路由算法160

7.4　系统设计与实现162

7.4.1　Σ-Dedupe系统架构162

7.4.2　数据路由消息通信164

7.4.3　相似索引查询优化165

7.5　性能评估166

7.5.1　实验平台和工作负载167

7.5.2　验证度量167

7.5.3　单节点并行重复数据删除效率168

7.5.4　集群重复数据删除效率172

7.6　本章小结176

第8章重复数据删除存储案例分析177

8.1　重复数据删除缩减率评估178

8.2　主流厂商相关产品应用案例181

8.2.1　DellEMC公司产品案例181

8.2.2　IBM公司产品案例195

8.2.3　飞康软件公司产品案例199

8.2.4　富士通公司产品案例204

8.2.5　NetApp公司产品案例211

8.2.6　Quantum公司产品案例218

8.3　本章小结224

本书面向从事大数据存储系统设计及相关技术研究和开发工作的读者。既可以作为存储 系统架构师、软件开发工程师、产品或项目经理、数据中心运维人员等的实用工具书，还可 以作为普通高等院校计算机和大数据科学相关专业的教学或科研人员、研究生、高年级本科 生及相关培训机构学员的学习参考书。

付印金 博士
军事科学院系统工程研究院博士后、陆军工程大学讲师，现为中国计算机学会高级会员、信息存储技术/系统软件专业委员会委员。长期从事网络存储、大数据管理与云计算方向的课题研究。已主持完成国家自然科学基金、江苏省自然科学基金等课题多项，发表学术论文50多篇，申请和授权国家发明专利10余项。主讲过“计算机组成原理”、“计算机网络”与“云计算”等本科与研究生专业课程。

肖侬 教授
中山大学国家超算计算广州中心教授、博士生导师，国防科技大学教授。获得*长江学者特聘教授、国家杰出青年科学基金资助。现任CCF Fellow、中国计算机学会大数据专家委员会副主任、信息存储技术专业委员会副主任。研究方向为网络计算与云计算、新型存储和系统结构，是我国高性能网络计算技术研究的先行开拓者之一。负责过863重大项目和国家自然科学基金重点项目等课题，发表学术论文200多篇。