重复数据删除(De-duplication)技术研究

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不等。高重复数据删除率低重复数据删除率数据由用户创建数据从自然世界获取数据低变化率数据高变化率引用数据、非活动数据活动数据低数据变化率应用高数据变化率应用完全数据备份增量数据备份数据长期保存数据短期保存大范围数据应用小范围数据应用持续数据业务处理普通数据业务处理小数据分块大数据分块变长数据分块定长数据分块数据内容可感知数据内容不可知时间数据消重空间数据消重2、D

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

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

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

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

8、edupe的关键技术主要包括文件数据块切分、数据块指纹计算和数据块检索。(1 文件数据块切分Dedupe按照消重的粒度可以分为文件级和数据块级。文件级的dedupe技术也称为单一实例存储(SIS, Single Instance Store，数据块级的重复数据删除其消重粒度更小，可以达到4-24KB之间。显然，数据块级的可以提供更高的数据消重率，因此目前主流的 dedupe产品都是数据块级的。数据分块算法主要有三种，即定长切分(fixed-size partition、CDC切分(content-defined chunking和滑动块(sliding block切分。定长分块算法采用预先义好

9、的块大小对文件进行切分，并进行弱校验值和md5强校验值。弱校验值主要是为了提升差异编码的性能，先计算弱 校验值并进行hash查找，如果发现则计算md5强校验值并作进一步hash查找。由于弱校验值计算量要比md5小很多，因此可以有效提高编码性能。定长 分块算法的优点是简单、性能高，但它对数据插入和删除非常敏感，处理十分低效，不能根据内容变化作调整和优化。Deduputil中FSP分块算法代码如 下。  1. /* 2.  * fixed-sized file chunking  3.  */

10、60; 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 *l

11、ast_block_buf, unsigned int *last_block_len  6.   7.     int ret = 0;  8.     unsigned int rwsize;  9.     unsigned char md5_checksum16 + 1&

12、#160;= 0;  10.     char *buf = NULL;  11.   12.     buf = (char *malloc(g_block_size;  13.     if (buf = NULL  14.     &

13、#160; 15.         perror("malloc in file_chunk_fsp"  16.         return errno;  17.       18.   19.     while&

14、#160;(rwsize = read(fd, buf, g_block_size  20.           21.                 /* if the last block */  22.

15、                 if (rwsize != g_block_size  23.                         br

16、eak;  24.   25.                 /* calculate md5 */  26.                 md5(buf, rwsize,&

17、#160;md5_checksum;  27.         if (0 != (ret = dedup_regfile_block_process(buf, rwsize, md5_checksum, fd_ldata,   28.             fd_b

18、data, pos, block_num, metadata, htable  29.           30.             perror("dedup_regfile_block_process in file_chunk_fsp"  31.

19、            goto _FILE_CHUNK_FSP_EXIT;  32.           33.       34.     *last_block_len = (rwsize > 0&

20、#160;? 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.  &

21、#160;  return ret;  40.   CDC(content-defined chunking算法是一种变长分块算法，它应用数据指纹(如Rabin指纹将文件分割成长度大小不等的分块策略。与定长分块算法不同，它是基于文件 内容进行数据块切分的，因此数据块大小是可变化的。算法执行过程中，CDC使用一个固定大小(如48字节的滑动窗口对文件数据计算数据指纹。如果指纹满 足某个条件，如当它的值模特定的整数等于预先设定的数时，则把窗口位置作为块的边界。CDC算法可能会出现病态现象，即指纹条件不能满足，块边界不能确 定，导致

22、数据块过大。实现中可以对数据块的大小进行限定，设定上下限，解决这种问题。CDC算法对文件内容变化不敏感，插入或删除数据只会影响到检少的数 据块，其余数据块不受影响。CDC算法也是有缺陷的，数据块大小的确定比较困难，粒度太细则开销太大，粒度过粗则dedup效果不佳。如何两者之间权衡折 衷，这是一个难点。Deduputil中CDC分块算法代码如下。 1. /* 2.  * content-defined chunking: 3.  * 1. BLOCK_MIN_SIZE <= blo

23、ck_size <= BLOCK_MAX_SIZE 4.  * 2. hash(block % d = r 5.  */  6. static int file_chunk_cdc(int fd, int fd_ldata, int fd_bdata, unsigned int *pos, unsigned int *bl

24、ock_num,  7.     block_id_t *metadata, hashtable *htable, char *last_block_buf, unsigned int *last_block_len  8.   9.     char bufBUF_MAX_SIZE = 0;  10.   

25、  char block_bufBLOCK_MAX_SIZE = 0;  11.     char win_bufBLOCK_WIN_SIZE + 1 = 0;  12.     char adler_pre_char;  13.     unsigned char md5_checksu

26、m16 + 1 = 0;  14.     unsigned int bpos = 0;  15.     unsigned int rwsize = 0;  16.     unsigned int exp_rwsize = BUF_MAX_SIZE;

27、60; 17.     unsigned int head, tail;  18.     unsigned int block_sz = 0, old_block_sz = 0;  19.     unsigned int hkey = 0;  20.  &

28、#160;  int ret = 0;  21.   22.     while(rwsize = read(fd, buf + bpos, exp_rwsize  23.       24.         /* last ch

29、unk */  25.         if (rwsize + bpos + block_sz < BLOCK_MIN_SIZE  26.             break;  27.   28.   

30、0;     head = 0;  29.         tail = bpos + rwsize;  30.         /* avoid unnecessary computation and comparsion */

31、  31.         if (block_sz < (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE  32.           33.             old_block

32、_sz = block_sz;  34.             block_sz = (block_sz + tail - head > (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE ?   35.       

33、              BLOCK_MIN_SIZE - BLOCK_WIN_SIZE : block_sz + tail -head;    36.             memcpy(block_buf +&#

34、160;old_block_sz, buf + head, block_sz - old_block_sz;  37.             head += (block_sz - old_block_sz;  38.           

35、;39.   40.         while (head + BLOCK_WIN_SIZE <= tail  41.           42.             memcpy(win_buf,

36、 buf + head, BLOCK_WIN_SIZE;  43.             /* 44.              * Firstly, i think rabinhash is the bes

37、t. However, it's performance is very bad. 45.              * After some testing, i found ELF_hash is better both on performance and 

38、;dedup rate. 46.              * So, EFL_hash is default. Now, adler_hash as default. 47.              */  

39、;48.             if (g_rolling_hash  49.               50.                 

40、hkey = (block_sz = (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE ? adler32_checksum(win_buf, BLOCK_WIN_SIZE :  51.                     adler32_rolling_ch

41、ecksum(hkey, BLOCK_WIN_SIZE, adler_pre_char, bufhead+BLOCK_WIN_SIZE-1;  52.                53.             else   54.  &

42、#160;              hkey = g_cdc_chunk_hashfunc(win_buf;  55.   56.             /* get a normal chunk */  

43、p 57.             if (hkey % g_block_size = CHUNK_CDC_R   58.               p 59.          

44、;       memcpy(block_buf + block_sz, buf + head, BLOCK_WIN_SIZE;   60.                 head += BLOCK_WIN_SIZE;  p 61.  &

45、#160;              block_sz += BLOCK_WIN_SIZE;   62.                 if (block_sz >= BLOCK_MIN_SIZE  6

46、3.                   64.                     md5(block_buf, block_sz, md5_checksum;  65. &

47、#160;                   if (0 != (ret = dedup_regfile_block_process(block_buf, block_sz,   66.            

48、;             md5_checksum, fd_ldata, fd_bdata, pos, block_num, metadata, htable  67.                   &

49、#160;   68.                         perror("dedup_reggile_block_process in file_chunk_cdc"  69.       

50、60;                 goto _FILE_CHUNK_CDC_EXIT;  70.                       71.   

51、                  block_sz = 0;  72.                   73.        

52、;       74.             else   75.               76.            &

53、#160;    block_bufblock_sz+ = bufhead+;  77.                 /* get an abnormal chunk */  78.         

54、60;       if (block_sz >= BLOCK_MAX_SIZE  79.                   80.              &

55、#160;      md5(block_buf, block_sz, md5_checksum;  81.                     if (0 != (ret = dedup_regfile_block_process(block_

56、buf, block_sz,   82.                         md5_checksum, fd_ldata, fd_bdata, pos, block_num, metadata, htable  83.

57、60;                     84.                         perror("dedup_regg

58、ile_block_process in file_chunk_cdc"  85.                         goto _FILE_CHUNK_CDC_EXIT;  86.        

59、               87.                     block_sz = 0;  88.         

60、;          89.               90.   91.             /* avoid unnecessary computation and

61、60;comparsion */  92.             if (block_sz = 0  93.               94.          &#

62、160;      block_sz = (tail - head > (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE ?   95.                     BLOCK_MIN_

63、SIZE - BLOCK_WIN_SIZE : tail - head;  96.                 memcpy(block_buf, buf + head, block_sz;  97.         

64、;        head = (tail - head > (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE ?   98.                     head&

65、#160;+ (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE : tail;  99.               100.   101.             adler_pre_char = bufhead

66、 -1;  102.           103.   104.         /* read expected data from file to full up buf */  105.     

67、0;   bpos = tail - head;  106.         exp_rwsize = BUF_MAX_SIZE - bpos;  107.         adler_pre_char = bufhead -1;  108

68、.         memmove(buf, buf + head, bpos;  109.       110.     /* last chunk */  111.     *last_block_len = (rwsize +

69、0;bpos + block_sz >= 0 ? rwsize + bpos + block_sz : 0;  112.     if (*last_block_len > 0  113.       114.        &

70、#160;memcpy(last_block_buf, block_buf, block_sz;  115.         memcpy(last_block_buf + block_sz, buf, rwsize + bpos;  116.       117.   118. _FILE_CHUNK_CDC_EXI

71、T:  119.     return ret;  120.    滑动块(sliding block算法结合了定长切分和CDC切分的优点，块大小固定。它对定长数据块先计算弱校验值，如果匹配则再计算md5强校验值，两者都匹配则认为是一 个数据块边界。该数据块前面的数据碎片也是一个数据块，它是不定长的。如果滑动窗口移过一个块大小的距离仍无法匹配，则也认定为一个数据块边界。滑动块算 法对插入和删除问题处理非常高效，并且能够检测到比CDC更多的冗余数据，它的不足是容易产生数据碎片。

72、Deduputil中SB分块算法代码如下。 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, int fd_ldat

73、a, 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

74、  6.   7.     char bufBUF_MAX_SIZE = 0;  8.     char win_bufBLOCK_MAX_SIZE + 1 = 0;  9.     char block_bufBLOCK_MAX_SIZE = 0;  10. 

75、0;   char adler_pre_char;  11.     unsigned char md5_checksum16 + 1 = 0;  12.     unsigned char md5_checksum116 + 1 = 0;  13.     

76、unsigned char crc_checksum16 = 0;  14.     unsigned int bpos = 0;  15.     unsigned int slide_sz = 0;  16.     unsigned int rwsize =

77、60;0;  17.     unsigned int exp_rwsize = BUF_MAX_SIZE;  18.     unsigned int head, tail;  19.     unsigned int hkey = 0;  20.    &

78、#160;unsigned int bflag = 0;  21.     int ret = 0;  22.   23.     while(rwsize = read(fd, buf + bpos, exp_rwsize  24.       2

79、5.         /* last chunk */  26.         if (rwsize + bpos + slide_sz < g_block_size  27.          

80、60;  break;  28.   29.         head = 0;  30.         tail = bpos + rwsize;  31.         while 

81、(head + g_block_size <= tail  32.           33.             memcpy(win_buf, buf + head, g_block_size;  34.    &#

82、160;        hkey = (slide_sz = 0 ? adler32_checksum(win_buf, g_block_size :   35.                 adler32_rolling_checksum(hk

83、ey, g_block_size, adler_pre_char, bufhead+g_block_size-1;  36.             uint_2_str(hkey, crc_checksum;  37.             bflag = 

84、;0;  38.   39.             /* this block maybe is duplicate */  40.             if (hash_exist(g_sb_htable_crc,

85、0;crc_checksum  41.                  42.                 bflag = 2;  43.      &#

86、160;          md5(win_buf, g_block_size, md5_checksum;  44.                 if (hash_exist(htable, md5_checksum  45.   &

87、#160;               46.                     /* insert fragment */  47.      

88、;               if (slide_sz != 0  48.                       49.     &

89、#160;                   md5(block_buf, slide_sz, md5_checksum1;  50.                    &#

90、160;    if (0 != (ret = dedup_regfile_block_process(block_buf, slide_sz, md5_checksum1,   51.                       

91、0;     fd_ldata, fd_bdata, pos, block_num, metadata, htable  52.                           53.   

92、60;                         perror("dedup_regfile_block_process in file_chunk_sb"  54.          

93、0;                  goto _FILE_CHUNK_SB_EXIT;  55.                         

94、  56.                       57.                     /* insert fixed-si

95、ze block */  58.                     if (0 != (ret = dedup_regfile_block_process(win_buf, g_block_size, md5_checksum,   59.  

96、                       fd_ldata, fd_bdata, pos, block_num, metadata, htable  60.            

97、60;          61.                         perror("dedup_regfile_block_process in file_chunk_sb"  62.

98、                        goto _FILE_CHUNK_SB_EXIT;  63.                   &#

99、160;   64.   65.                     head += g_block_size;  66.                &

100、#160;    slide_sz = 0;  67.                     bflag = 1;  68.             

101、0;     69.               70.   71.             /* this block is not duplicate */  72.  

102、60;          if (bflag != 1  73.               74.                 block_bu

103、fslide_sz = bufhead;  75.                 head+;  76.                 slide_sz+;  77.   &#

104、160;             if (slide_sz = g_block_size  78.                   79.         

105、            if (bflag != 2 md5(block_buf, g_block_size, md5_checksum;  80.                     if

106、60;(0 != (ret = dedup_regfile_block_process(block_buf, g_block_size, md5_checksum,   81.                         fd_ldata, fd_bdat

107、a, pos, block_num, metadata, htable  82.                       83.                

108、60;        perror("dedup_regfile_block_process in file_chunk_sb"  84.                         goto _FILE_

109、CHUNK_SB_EXIT;  85.                       86.                     hash_checkin(g

110、_sb_htable_crc, crc_checksum;  87.                     slide_sz = 0;  88.                   89.               90.