差异编码信息的数据文件布局同样由文件头(delta_file_header)和数据块描述实体(delta_block_entry)集组成,如下所定义。其中,文件头定义了文件A的数据块总数、最后一个数据的长度和偏移。文件头后紧随一组数据块描述实体,每个实体代表一个数据块,定义了数据块长度、偏移以及数据块位置指示。如果embeded为1,则表示数据块位于差异编码文件中offset处,数据紧随该实体后;如果embeded为0,则表示数
据块位于文件B中offset处。最后数据块存储于差异编码文件尾部,长度和偏移由头部指示。
view plaincopy to clipboardprint? /* define delta file header and block entry */ typedef struct _delta_file_header { uint32_t block_nr; uint32_t last_block_sz; uint64_t last_block_offset; /* offset in delta file */ } delta_file_header; #define DELTA_FILE_HEADER_SZ (sizeof(delta_file_header)) typedef struct _delta_block_entry { uint64_t offset; uint32_t len; uint8_t embeded; /* 1, block in delta file; 0, block in source file. */ } delta_block_entry; #define DELTA_BLOCK_ENTRY_SZ (sizeof(delta_block_entry)) /* define delta file header and block entry */ typedef struct _delta_file_header { uint32_t block_nr; uint32_t last_block_sz; uint64_t last_block_offset; /* offset in delta file */ } delta_file_header; #define DELTA_FILE_HEADER_SZ (sizeof(delta_file_header)) typedef struct _delta_block_entry { uint64_t offset; uint32_t len; uint8_t embeded; /* 1, block in delta file; 0, block in source file. */ } delta_block_entry; #define DELTA_BLOCK_ENTRY_SZ (sizeof(delta_block_entry))
从实时性能方面考虑,数据块信息和差异编码信息并不一定要写入文件,可以存在于Cache中,但数据布局与上面描述相同。
5、文件切分
Dedupe技术中,数据分块算法主要有三种,即定长切分(fixed-size partition)、CDC切分(content-defined chunking)和滑动块(sliding block)切分。定长分块算法采用预先定义好的块大小对文件进行切分,并进行弱校验值和md5强校验值。弱校验值主要是为了提升差异编码的性能,先计算弱校验值并进行hash查找,如果发现则计算md5强校验值并作进一步hash查找。由于弱校验值计算量要比md5小很多,因此可以有效提高编码性能。定长分块算法的优点是简单、性能高,但它对数据插入和删除非常敏感,处理十分低效,不能根据内容变化作调整和优化。
CDC算法是一种变长分块算法,它应用数据指纹(如Rabin指纹)将文件分割成长度大小不等的分块策略。与定长分块算法不同,它是基于文件内容进行数据块切分的,因此数据块大小是可变化的。算法执行过程中,CDC使用一个固定大小(如48字节)的滑动窗口对文件数据计算数据指纹。如果指纹满足某个条件,如当它的值模特定的整数等于预先设定的数时,则把窗口位置作为块的边界。CDC算法可能会出现病态现象,即指纹条件不能满足,块边界不能确定,导致数据块过大。实现中可以对数据块的大小进行限定,设定上下限,解决这种问题。CDC算法对文件内容变化不敏感,插入或删除数据只会影响到检少的数据块,其余数据块不受影响。CDC算法也是有缺陷的,数据块大小的确定比较困难,粒度太细则开销太大,粒度过粗则dedup效果不佳。如何两者之间权衡折衷,这是一个难点。
出处:CSDN
责任编辑:bluehearts
上一页 数据同步算法研究 [2] 下一页 数据同步算法研究 [4]
◎进入论坛网络编程版块参加讨论
|