Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1944095
  • 博文数量: 1000
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7921
  • 用 户 组: 普通用户
  • 注册时间: 2013-08-20 09:23
个人简介

storage R&D guy.

文章分类

全部博文(1000)

文章存档

2019年(5)

2017年(47)

2016年(38)

2015年(539)

2014年(193)

2013年(178)

分类: 服务器与存储

2015-01-29 10:03:26

Rsync中使用了一种滚动检验(Rolling Checksum)算法,用于快速计算数据块的检验值。它是一种弱校验算法,采用的是Mark Adler的adler-32校验,它的定义如下:

       a(k, l) = (∑Xi)  mod M

       b(k, l) = (∑(l - i +1)Xi) mod M

       s(k, l) = a(k, l) + 216 b(k, l)

上面公式中,s(k, l)表示数据块Xk, ..., Xl的滚动校验值,为了简化以及计算速度考虑,M取值为216。这种校验计算公式具有一个非常关键的特性,那就是后续校验值可以通过递推关系高效地计算获得。

      a(k+1, l+1) = (a(k, l) - Xk + Xl+1)) mod M

      b(k+1, l+1) = (b(k, l) - (l - k +1)Xk + a(k+1, l+1)) mod M

      s(k+1, l+1) = a(k+1, l+1) + 216 b(k+1, l+1)

因此,给定X1, ..., Xn的校验值,X1以及Xn+1,我们就可以快速地计算出X2, ..., Xn+1校验值。这样,利用这种性质我们就可以高效地计算数据块连续校验值,大幅减少checksum计算量。dedup util中,我在CDC和Sliding-block文件分块处理中使用了该校验值算法,性能得到大幅提升。

 

附Adler32_checksum算法实现:


  1. /* 
  2.  *   a simple 32 bit checksum that can be upadted from either end 
  3.  *   (inspired by Mark Adler's Adler-32 checksum) 
  4.  */  
  5. unsigned int adler32_checksum(char *buf, int len)  
  6. {  
  7.     int i;  
  8.     unsigned int s1, s2;  
  9.     s1 = s2 = 0;  
  10.     for (i = 0; i < (len - 4); i += 4) {  
  11.         s2 += 4 * (s1 + buf[i]) + 3 * buf[i+1] + 2 * buf[i+2] + buf[i+3] +  
  12.           10 * CHAR_OFFSET;  
  13.         s1 += (buf[i+0] + buf[i+1] + buf[i+2] + buf[i+3] + 4 * CHAR_OFFSET);  
  14.     }  
  15.     for (; i < len; i++) {  
  16.         s1 += (buf[i]+CHAR_OFFSET);  
  17.         s2 += s1;  
  18.     }  
  19.     return (s1 & 0xffff) + (s2 << 16);  
  20. }  
  21. /* 
  22.  * adler32_checksum(X0, ..., Xn), X0, Xn+1 ----> adler32_checksum(X1, ..., Xn+1) 
  23.  * where csum is adler32_checksum(X0, ..., Xn), c1 is X0, c2 is Xn+1 
  24.  */  
  25. unsigned int adler32_rolling_checksum(unsigned int csum, int len, char c1, char c2)  
  26. {  
  27.         unsigned int s1, s2, s11, s22;  
  28.         s1 = csum & 0xffff;  
  29.         s2 = csum >> 16;  
  30.         s1 -= (c1 - c2);  
  31.         s2 -= (len * c1 - s1);  
  32.         return (s1 & 0xffff) + (s2 << 16);  
  33. }  
 


阅读(1069) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~