Dedupe技术目前主要应用于数据备份，因此对数据进行多次备份后，存在大量重复数据，非常适合这种技术。事实上，dedupe技术可以用于很多场合，包括在线数据、近线数据、离线数据存储系统，甚至可以在文件系统、卷管理器、NAS、SAN中实施。也可以用于网络数据传输，当然也可以应用于数据打包技术。Dedupe技术可以帮助众多应用降低数据存储量，节省网络带宽，提高存储效率、减小备份窗口，绿色节能。

4、数据同步算法

如Rsync假设现在有两台计算机Alpha和Beta ,计算机Alpha能够访问A文件,计算机Beta能够访问B文件，文件A和B非常相似，计算机Alpha和Beta通过低速网络互联。基于dedupe技术的数据同步算法大致流程与Rsync相似，简单描述如下：

1、Beta采用数据切分算法，如FSP(fixed-size partition)、CDC(content-defined chuking)，将文件B分割成大小相等或不等的数据块；

2、Beta对于每一个数据块,计算一个类似rsync弱校验值和md5强校验值，并记录数据块长度len和在文件B中的偏移量offset；

3、Beta将这将数据块信息发送给Alpha；

4、Alpha采用同样的数据块切分技术将文件A切成大小相等或不等的数据块，并与Beta发过来的数据信息进行搜索匹配，生成差异编码信息；

5、Alpha将差异编码信息发送给Beta，并同时发送重构文件A的指令；

6、Beta根据差异编码信息和文件B重构文件A。

上面算法描述中，有几个关键问题需要解决，即文件切分、切分数据块信息描述、差异编码、差异编码信息描述、文件同步。文件切分、差异编码、文件同步将在后续部分介绍，这里对切分数据块信息描述和差异编码信息描述作说明。

切分数据块信息的数据文件布局由文件头(chunk_file_header)和数据块描述(chunk_block_entry)实体集组成，具体定义如下。其中，文件头定义了文件B的数据块大小、数据块总数。文件头后紧随一组数据块描述实体，每个实体代表一个数据块，定义了块长度、块在文件B中的偏移、弱校验值和强md5校验值。　

view plaincopy to clipboardprint?
/* define chunk file header and block entry */ 
typedef struct _chunk_file_header {  
        uint32_t block_sz;  
        uint32_t block_nr;  
} chunk_file_header;  
#define CHUNK_FILE_HEADER_SZ    (sizeof(chunk_file_header))  
typedef struct _chunk_block_entry {  
        uint64_t offset;  
        uint32_t len;  
        uint8_t  md5[16 + 1];  
        uint8_t  csum[10 + 1];  
} chunk_block_entry;  
#define CHUNK_BLOCK_ENTRY_SZ    (sizeof(chunk_block_entry)) 
/* define chunk file header and block entry */
typedef struct _chunk_file_header {
        uint32_t block_sz;
        uint32_t block_nr;
} chunk_file_header;
#define CHUNK_FILE_HEADER_SZ    (sizeof(chunk_file_header))
typedef struct _chunk_block_entry {
        uint64_t offset;
        uint32_t len;
        uint8_t  md5[16 + 1];
        uint8_t  csum[10 + 1];
} chunk_block_entry;
#define CHUNK_BLOCK_ENTRY_SZ    (sizeof(chunk_block_entry))

出处：CSDN
责任编辑：bluehearts

上一页 数据同步算法研究 [1] 下一页 数据同步算法研究 [3]

◎进入论坛网络编程版块参加讨论