deduputil中使用md5算法计算数据块hashkey。md5是128位的hash值,理论上产生碰撞的概率非常小,据说比磁盘发生物理损坏的概率还要小几个数据级。然而,虽然说概率非常微小,但产生碰撞的可能性真实存在,王小云教授的团队已经找到快速发现碰撞的算法。在重复数据删除技术中,鉴于性能考虑,主流做法是使用碰撞概率更小的hash算法,如sha256, sha512,或者同时使用两种以上hash算法,或者使用非平凡的hash算法,从而减小碰撞概率,从而可以假设不会发生碰撞。数据碰撞的存在,使数据存在潜在的安全问题,这让很多用户不敢放心使用重复数据删除技术及相关产品。deduputil是一款轻量级数据打包归档工具,我认为它的数据安全性要高于性能,因此以牺牲部分性能为代价,对md5碰撞问题进行彻底解决,确保数据的安全性。

假设md5不会产生碰撞,那么hash_md5(block)产生的值是唯一的,也就是说一个数据块对应一个唯一的hash值,可以用1:1映射来表示。现在,这个假设被否定,可能存在两个数据块的md5哈稀值相同,即hash_md5(block1) =hash_md5(block2),多个数据块对应一个hash值,这时就需要使用1:n映射来表示。新的hashtable表项使用三元组表示:

                                              

其中,md5_hashkey表示数据块md5值,block_nr表示md5哈稀值相同的数据块数量,block_IDs表示这些数据块逻辑块号。在程序设计中,将block_nr与block_IDs合并在一块,结构如下所示:

+----------------------------------------------------+
|  block_nr | block_ID1 | block_ID2 | ... | block_IDn  |
+----------------------------------------------------+ 

这实际上是使用链接法来解决hash碰撞问题,每个桶的长度不定。对于每个数据块,都要与桶中的数据块进行逐位的比较,以保证数据块的唯一性。算法描述如下:

1、计算数据块md5值,hkey = hash_md5(block);

2、查找hashtable,bindex = hash_value(hkey, htable);

3、如果未发现哈稀表项,即bindex == NULL,则直接将hkey插入hashtable, 并且block_nr =1,block_ID1 = g_unique_block_nr;

4、如果发现哈稀表项,则作如下处理

 4.1 遍历哈稀桶,将逻辑号对应的物理数据块与当前数据块进行比较;

 4.2 如果找到相同数据块,则该数据块已经存在,无需处理;

  4.3 如果未找到相同数据块,则将数据块插入桶尾,并将数据块写入文件,并且block_nr++, block_IDn =g_unique_block_nr;

不作碰撞处理的算法,未发现md5值哈稀表项则直接返回逻辑块号,没有如上算法的第4步。这里需要进行数据块的比较,性能损失主要发生在这里。算法细节请直接参考源码src/dedup.c中的dedup_regfile,部分代码摘录如下:


  1. pos = 0;  

  2. while (rwsize = read(fd, buf, g_block_size))   

  3. {  

  4.     /* if the last block */  

  5.     if (rwsize != g_block_size)  

  6.         break;  

  7.     /* calculate md5 */  

  8.     md5(buf, rwsize, md5_checksum);  

  9.     /* check hashtable with hashkey  

  10.        NOTE: no md5 collsion problem, but lose some performace  

  11.        hashtable entry format: (md5_key, block_id list) 

  12.        +--------------------------------+ 

  13.        | id num | id1 | id2 | ... | idn | 

  14.        +--------------------------------+ 

  15.     */  

  16.     unsigned int cbindex;  

  17.     int bflag = 0;  

  18.     unsigned int *bindex = (block_id_t *)hash_value((void *)md5_checksum, htable);  

  19.     /* the block exists */  

  20.     if (bindex != NULL)  

  21.     {  

  22.         int i;  

  23.         for (i = 0; i < *bindex; i++)  

  24.         {  

  25.             if (0 == block_cmp(buf, fd_bdata, *(bindex + i + 1), g_block_size))  

  26.             {  

  27.                 cbindex = *(bindex + i + 1);  

  28.                 bflag = 1;  

  29.                 break;  

  30.             }  

  31.         }  

  32.     }  

  33.     /* insert hash entry and write unique block into bdata*/  

  34.     if (bindex == NULL || (bindex != NULL && bflag == 0))  

  35.     {  

  36.         if (bindex == NULL)  

  37.             bflag = 1;  

  38.         bindex = (bflag) ? (block_id_t *)malloc(BLOCK_ID_SIZE * 2) :  

  39.             (block_id_t *)realloc(bindex, BLOCK_ID_SIZE * ((*bindex) + 1));  

  40.         if (NULL == bindex)  

  41.         {  

  42.             perror("malloc/realloc in dedup_regfile");  

  43.             break;  

  44.         }  

  45.         *bindex = (bflag) ? 1 : (*bindex) + 1;  

  46.         *(bindex + *bindex) = g_unique_block_nr;  

  47.         cbindex = g_unique_block_nr;  

  48.         hash_insert((void *)strdup(md5_checksum), (void *)bindex, htable);  

  49.         write(fd_bdata, buf, rwsize);  

  50.         g_unique_block_nr++;  

  51.     }  

  52.     metadata[pos] = cbindex;  

  53.     memset(buf, 0, g_block_size);  

  54.     memset(md5_checksum, 0, 16 + 1);  

  55.     pos++;  

  56. }  

 


11-30 04:50