重复数据删除.docx

1、重复数据删除(De-duplication) 1、Dedupe 概述De-duplication，即重复数据删除，它是一种目前主流且非常热门的存储技术，可对存储容量进行有效优化。它通过删除数据集中重复的数据，只保留其中一份，从而消除冗余数据。如下图所示。这种技术可以很大程度上减少对物理存储空间的需求，从而满足日益增长的数据存储需求。Dedupe 技术可以带许多实际的利益，主要包括以下诸多方面：(1) 满足 ROI(投资回报率， Return On Investment)/TCO(总持有成本，Total Cost of Ownership)需求；(2) 可以有效控制数据的急剧增长；(3) 增加有

2、效存储空间，提高存储效率；(4) 节省存储总成本和管理成本；(5) 节省数据传输的网络带宽；(6) 节省空间、电力供应、冷却等运维成本。Dedupe 技术目前大量应用于数据备份与归档系统，因为对数据进行多次备份后，存在大量重复数据，非常适合这种技术。事实上，dedupe 技术可以用于很多场合，包括在线数据、近线数据、离线数据存储系统，可以在文件系统、卷管理器、NAS、SAN 中实施。Dedupe 也可以用于数据容灾、数据传输与同步，作为一种数据压缩技术可用于数据打包。Dedupe 技术可以帮助众多应用降低数据存储量，节省网络带宽，提高存储效率、减小备份窗口，节省成本。Dedupe 的衡量维度主

3、要有两个，即重复数据删除率(deduplocation ratios)和性能。Dedupe 性能取决于具体实现技术，而重复数据删除率则由数据自身的特征和应用模式所决定，影响因素如下表2 所示。目前各存储厂商公布的重复数据删除率从 20:1 到 500:1不等。高重复数据删除率 低重复数据删除率数据由用户创建 数据从自然世界获取数据低变化率 数据高变化率引用数据、非活动数据 活动数据低数据变化率应用 高数据变化率应用完全数据备份 增量数据备份数据长期保存 数据短期保存大范围数据应用 小范围数据应用持续数据业务处理 普通数据业务处理小数据分块 大数据分块变长数据分块 定长数据分块数据内容可感知 数

4、据内容不可知时间数据消重 空间数据消重2、Dedupe 实现要点研发或应用 Dedupe 技术时应该考虑各种因素，因为这些因素会直接影响其性能和效果。(1) What：对何种数据进行消重？对时间数据还是空间数据进行消重，对全局数据还是局部数据进行消重？这是首先需要考虑的因素，这直接决定着 Dedupe 实现技术和数据消重率。随时间变化的数据，如周期性的备份、归档数据，比空间数据具有更高的消重率，Dedupe 技术在备份归档领域中被广泛应用。不难想象，全局范围内的数据重复率比局部范围数据要高，会获得更高的数据消重率。(2) When：何时进行消重？数据消重时机分为两种情形：在线消重和离线消重。采

5、用在线消重模式，数据写入存储系统同时执行消重，因此实际传输或写入的数据量较少，适合通过 LAN 或 WAN 进行数据处理的存储系统，如网络备份归档和异地容灾系统。由于它需要实时进行文件切分、数据指纹计算、Hash 查找，对系统资料消耗大。离线消重模式，先将数据写入存储系统，然后利用适当的时间再进行消重处理。这种模式与前面一种刚好相反，它对系统资料消耗少，但写入了包含重复的数据，需要更多的额外存储空间来预先存储消重前数据。这种模式适合直连存储 DAS 和存储区域网络 SAN 存储架构，数据传输不占用网络带宽。另外，离线消重模式需要保证有足够的时间窗口来进行数据去重操作。总之，在何时进行消重，要根

6、据实际存储应用场景来确定。(3) Where：在何处进行消重？数据消重可以在源端(Source)或者目标端(Target) 进行。源端消重在数据源进行，传输的是已经消重后的数据，能够节省网络带宽，但会占用大量源端系统资源。目标端消重发生在目标端，数据在传输到目标端再进行消重，它不会占用源端系统资源，但占用大量网络带宽。目标端消重的优势在于它对应用程序透明，并具有良好的互操作性，不需要使用专门的 API，现有应用软件不用作任何修改即可直接应用。(4) How：如何进行消重？重复数据删除技术包含许多技术实现细节，包括文件如何进行切分？数据块指纹如何计算？如何进行数据块检索？采用相同数据检测还是采用

7、相似数据检测和差异编码技术？数据内容是否可以感知，是否需要对内容进行解析？这些都是 Dedupe 具体实现息息相关。本文主要研究相同数据检测技术，基于二进制文件进行消重处理，具有更广泛的适用性。3、Dedupe 关键技术存储系统的重复数据删除过程一般是这样的：首先将数据文件分割成一组数据块，为每个数据块计算指纹，然后以指纹为关键字进行 Hash 查找，匹配则表示该数据块为重复数据块，仅存储数据块索引号，否则则表示该数据块是一个新的唯一块，对数据块进行存储并创建相关元信息。这样，一个物理文件在存储系统就对应一个逻辑表示，由一组 FP 组成的元数据。当进行读取文件时，先读取逻辑文件，然后根据 FP

8、 序列，从存储系统中取出相应数据块，还原物理文件副本。从如上过程中可以看出，Dedupe 的关键技术主要包括文件数据块切分、数据块指纹计算和数据块检索。(1) 文件数据块切分Dedupe 按照消重的粒度可以分为文件级和数据块级。文件级的 dedupe 技术也称为单一实例存储(SIS, Single Instance Store)，数据块级的重复数据删除其消重粒度更小，可以达到 4-24KB 之间。显然，数据块级的可以提供更高的数据消重率，因此目前主流的dedupe 产品都是数据块级的。数据分块算法主要有三种，即定长切分(fixed-size partition)、CDC 切分(content-

9、defined chunking)和滑动块(sliding block)切分。定长分块算法采用预先义好的块大小对文件进行切分，并进行弱校验值和 md5 强校验值。弱校验值主要是为了提升差异编码的性能，先计算弱校验值并进行 hash 查找，如果发现则计算 md5 强校验值并作进一步 hash 查找。由于弱校验值计算量要比 md5 小很多，因此可以有效提高编码性能。定长分块算法的优点是简单、性能高，但它对数据插入和删除非常敏感，处理十分低效，不能根据内容变化作调整和优化。Deduputil 中 FSP 分块算法代码如下。cpp:collapse + expand sourceview plainc

10、opyprint?1. /* 2. * fixed-sized file chunking 3. */ 4. static int file_chunk_fsp(int fd, int fd_ldata, int fd_bdata, unsigned int *pos, unsigned int *block_num, 5. block_id_t *metadata, hashtable *htable, char *last_block_buf, unsigned int *last_block_len) 6. 7. int ret = 0; 8. unsigned int rwsize;

11、9. unsigned char md5_checksum16 + 1 = 0; 10. char *buf = NULL; 11.12. buf = (char *)malloc(g_block_size); 13. if (buf = NULL) 14. 15. perror(“malloc in file_chunk_fsp“); 16. return errno; 17. 18.19. while (rwsize = read(fd, buf, g_block_size) 20. 21. /* if the last block */ 22. if (rwsize != g_block

12、_size) 23. break; 24.25. /* calculate md5 */ 26. md5(buf, rwsize, md5_checksum); 27. if (0 != (ret = dedup_regfile_block_process(buf, rwsize, md5_checksum, fd_ldata, 28. fd_bdata, pos, block_num, metadata, htable) 29. 30. perror(“dedup_regfile_block_process in file_chunk_fsp“); 31. goto _FILE_CHUNK_

13、FSP_EXIT; 32. 33. 34. *last_block_len = (rwsize 0) ? rwsize : 0; 35. if (*last_block_len) memcpy(last_block_buf, buf, *last_block_len); 36.37. _FILE_CHUNK_FSP_EXIT: 38. if (buf) free(buf); 39. return ret; 40. /* * fixed-sized file chunking */static int file_chunk_fsp(int fd, int fd_ldata, intblock_i

14、d_t *metadata, hashtable *htable, cint ret = 0;unsigned int rwsize;unsigned char md5_checksum16 + 1 = 0;char *buf = NULL;buf = (char *)malloc(g_block_size);if (buf = NULL) perror(“malloc in file_chunk_fsp“);return errno;CDC(content-defined chunking)算法是一种变长分块算法，它应用数据指纹(如 Rabin 指纹)将文件分割成长度大小不等的分块策略。与定

15、长分块算法不同，它是基于文件内容进行数据块切分的，因此数据块大小是可变化的。算法执行过程中，CDC 使用一个固定大小(如 48 字节 )的滑动窗口对文件数据计算数据指纹。如果指纹满足某个条件，如当它的值模特定的整数等于预先设定的数时，则把窗口位置作为块的边界。CDC 算法可能会出现病态现象，即指纹条件不能满足，块边界不能确定，导致数据块过大。实现中可以对数据块的大小进行限定，设定上下限，解决这种问题。CDC 算法对文件内容变化不敏感，插入或删除数据只会影响到检少的数据块，其余数据块不受影响。CDC 算法也是有缺陷的，数据块大小的确定比较困难，粒度太细则开销太大，粒度过粗则 dedup 效果不佳

16、。如何两者之间权衡折衷，这是一个难点。Deduputil 中 CDC 分块算法代码如下。cpp:collapse + expand sourceview plaincopyprint?1. /* 2. * content-defined chunking: 3. * 1. BLOCK_MIN_SIZE (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE) ? 35. BLOCK_MIN_SIZE - BLOCK_WIN_SIZE : block_sz + tail -head; 36. memcpy(block_buf + old_block_sz, buf + head, bl

17、ock_sz - old_block_sz); 37. head += (block_sz - old_block_sz); 38. 39.40. while (head + BLOCK_WIN_SIZE) = BLOCK_MIN_SIZE) 63. 64. md5(block_buf, block_sz, md5_checksum); 65. if (0 != (ret = dedup_regfile_block_process(block_buf, block_sz, 66. md5_checksum, fd_ldata, fd_bdata, pos, block_num, metadat

18、a, htable) 67. 68. perror(“dedup_reggile_block_process in file_chunk_cdc“); 69. goto _FILE_CHUNK_CDC_EXIT; 70. 71. block_sz = 0; 72. 73. 74. else 75. 76. block_bufblock_sz+ = bufhead+; 77. /* get an abnormal chunk */ 78. if (block_sz = BLOCK_MAX_SIZE) 79. 80. md5(block_buf, block_sz, md5_checksum);

19、81. if (0 != (ret = dedup_regfile_block_process(block_buf, block_sz, 82. md5_checksum, fd_ldata, fd_bdata, pos, block_num, metadata, htable) 83. 84. perror(“dedup_reggile_block_process in file_chunk_cdc“); 85. goto _FILE_CHUNK_CDC_EXIT; 86. 87. block_sz = 0; 88. 89. 90.91. /* avoid unnecessary compu

20、tation and comparsion */ 92. if (block_sz = 0) 93. 94. block_sz = (tail - head) (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE) ? 95. BLOCK_MIN_SIZE - BLOCK_WIN_SIZE : tail - head; 96. memcpy(block_buf, buf + head, block_sz); 97. head = (tail - head) (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE) ? 98. head + (BLOCK_MIN_SIZE

21、- BLOCK_WIN_SIZE) : tail; 99. 100.101. adler_pre_char = bufhead -1; 102. 103.104. /* read expected data from file to full up buf */ 105. bpos = tail - head; 106. exp_rwsize = BUF_MAX_SIZE - bpos; 107. adler_pre_char = bufhead -1; 108. memmove(buf, buf + head, bpos); 109. 110. /* last chunk */ 111. *

22、last_block_len = (rwsize + bpos + block_sz) = 0) ? rwsize + bpos + block_sz : 0; 112. if (*last_block_len 0) 113. 114. memcpy(last_block_buf, block_buf, block_sz); 115. memcpy(last_block_buf + block_sz, buf, rwsize + bpos); 116. 117.118. _FILE_CHUNK_CDC_EXIT: 119. return ret; 120. /* * content-defin

23、ed chunking:* 1. BLOCK_MIN_SIZE = block_size = BLOCK_MAX_SIZ * 2. hash(block) % d = r*/static int file_chunk_cdc(int fd, int fd_ldata, intblock_id_t *metadata, hashtable *htable, cchar bufBUF_MAX_SIZE = 0;char block_bufBLOCK_MAX_SIZE = 0;char win_bufBLOCK_WIN_SIZE + 1 = 0;char adler_pre_char;unsigne

24、d char md5_checksum16 + 1 = 0;unsigned int bpos = 0;unsigned int rwsize = 0;unsigned int exp_rwsize = BUF_MAX_SIZE;unsigned int head, tail;unsigned int block_sz = 0, old_block_sz = 0滑动块(sliding block)算法结合了定长切分和 CDC 切分的优点，块大小固定。它对定长数据块先计算弱校验值，如果匹配则再计算 md5 强校验值，两者都匹配则认为是一个数据块边界。该数据块前面的数据碎片也是一个数据块，它是不定

25、长的。如果滑动窗口移过一个块大小的距离仍无法匹配，则也认定为一个数据块边界。滑动块算法对插入和删除问题处理非常高效，并且能够检测到比 CDC 更多的冗余数据，它的不足是容易产生数据碎片。Deduputil 中 SB 分块算法代码如下。cpp:collapse + expand sourceview plaincopyprint?1. /* 2. * slideing block chunking, performance is a big issue due to too many hash lookup. 3. */ 4. static int file_chunk_sb(int fd, i

26、nt fd_ldata, int fd_bdata, unsigned int *pos, unsigned int *block_num, 5. block_id_t *metadata, hashtable *htable, char *last_block_buf, unsigned int *last_block_len) 6. 7. char bufBUF_MAX_SIZE = 0; 8. char win_bufBLOCK_MAX_SIZE + 1 = 0; 9. char block_bufBLOCK_MAX_SIZE = 0; 10. char adler_pre_char;

27、11. unsigned char md5_checksum16 + 1 = 0; 12. unsigned char md5_checksum116 + 1 = 0; 13. unsigned char crc_checksum16 = 0; 14. unsigned int bpos = 0; 15. unsigned int slide_sz = 0; 16. unsigned int rwsize = 0; 17. unsigned int exp_rwsize = BUF_MAX_SIZE; 18. unsigned int head, tail; 19. unsigned int

28、hkey = 0; 20. unsigned int bflag = 0; 21. int ret = 0; 22.23. while(rwsize = read(fd, buf + bpos, exp_rwsize) 24. 25. /* last chunk */ 26. if (rwsize + bpos + slide_sz) g_block_size) 27. break; 28.29. head = 0; 30. tail = bpos + rwsize; 31. while (head + g_block_size) = tail) 32. 33. memcpy(win_buf,

29、 buf + head, g_block_size); 34. hkey = (slide_sz = 0) ? adler32_checksum(win_buf, g_block_size) : 35. adler32_rolling_checksum(hkey, g_block_size, adler_pre_char, bufhead+g_block_size-1); 36. uint_2_str(hkey, crc_checksum); 37. bflag = 0; 38.39. /* this block maybe is duplicate */ 40. if (hash_exist(g_sb_htable_crc, crc_checksum) 41.