分 类 号学号M201072431学校代码10487密级硕士学位论文云网关上重复数据删除的设计与实 现学位申请人 ：周旋学 科 专 业 ：计算机系统结构指 导 教 师 ：曾令仿答 辩 日 期 ：2013.1.22A Thesis Submitted to Academic Evaluation Committee of HuazhongUniversity of Science and Technology for the Degree of Master of EngineeringDesign and Implementation of Data Deduplication on the Cloud GatewayCandidate : Zhou XuanMajor: Computer ArchitectureSupervisor : Ass. Prof. Zeng LingfangHuazhong University of Science uint32_t c_num;uint32_t b_num;uint64_t t_num;uint64_t b_off;uint64_t h_off;uint64_t v_off; HDR;19华中科技大学硕士学位论文其中，m_flag 用于判断所读取的是否为 header 结构，c_num, b_num, t_num 分别用于缓存条目数，桶条目数，总的条目数，云网关上设置的默认值为 106,106,107，而 b_off, h_off, v_off 则分别表示 bloom filter, 桶, 条目分别在文件中的偏移量，header在散列表初始化的时候被读取用于初始化其它各部分。3.3.2 hash entriestypedef struct hash_entry uint8_t is_cached;char *key;void *value;uint32_t k_size;uint32_t v_size;uint32_t t_size;uint32_t hash;uint64_t off;uint64_t left;uint64_t right; HASH_ENTRY;其中，is_cached 用于标志这条目录是否被缓存，*key,*value 用于存储键值对，k_size, v_size 用于键值对中元素的长度，t_size 用于表示该条目的大小，一般为固定大小，hash 表示二次哈希值的大小，off 表示条目在文件中的偏移地址，left, right 分别表示左右孩子节点，用于二次查找时的二叉查找树。所有的条目都以追加的形式添加到散列表文件中。3.3.3 bucketstypedef struct hash_bucket uint64_t off; HASH_BUCKET; 其中，off 用于存储桶中根条目的文件偏移地址。主要用于在出现哈希冲突时进行的二次查找，一般可以使用链表的形式存储，但是当数据量很大时，链表的查找性能不高，所以使用二次哈希结合二叉查找树来实现桶的结构，桶中存储了一次哈20华中科技大学硕士学位论文希相同的条目的二叉查找树的根条目的文件偏移地址，然后根据二次哈希值进行查找和相应的插入工作。因此桶的数目远小于条目的数目，云网关的设计中将桶长设计为大于 10，所以 t_num = 10 * b_num。这部分桶以固定大小存储在文件中。3.3.4 bloom filter云网关上的散列表使用 bloom filter 检测 md5 值是否已存在。在数据集合中查找某个数据是否存在有很多方法，通常会将这个数据与数据集合中的元素进行比较来检测，二叉树，数组，链表及散列表都能实现这种查找，但是当数据集合中元素非常多时，这些方法都产生很大的时间及空间复杂度，所以并不适合大数据集的检测。bloom filter 是一种二进制的数据结构，其主要特点是消耗较小的时间及空间复杂度，但是不能准确判断该数据是否一定在这个数据集合中，需要进行进一步的准确判断，所以非常适合用于数据的初步查找，将部分一定不在集合中的数据筛掉，减小云网关中重复数据删除所需 md5 值查找所需的时间。算法实现keysax_hash%tnumsdbm_hash%tnumbloom filter 图3.4 云网关上使用的 bloom filterbloom filter 使用哈希函数的方法，将数据映射到一个长度为 n 的 bit 数组上的某个点，如果这个 bit 为 1，则判断数据在该数据集合中，否则就不在该数据集合中。如果使用单一的哈希函数进行检测，存储的元素很多时，发生冲突的可能性较大，如果使用 k 个哈希函数，这个数据就对应 k 个判断点，只有当所有判断点都为 1 时，数据才被判断为在该数据集合内，只要有任何 1bit 为 0，那么这个数据就不在该数据集合内。使用 bloom filter 进行判断的查询及插入时间都具有 O(1)的复杂度，但是随着数据数量的增加，会增加对数据“在该数据集合内”的判断错误概率，同时由于可21nl i m (1 x华中科技大学硕士学位论文能多个集合内的数据使用结构中的同一 bit，因此不能对 bloom filter 进行删除操作。在云网关上实现的 bloom filter，使用 2 个哈希函数进行判断（ sax_hash,sdbm_hash），1 个哈希函数容易产生较高的冲突率，太多的哈希函数会增加判断时间，可能消耗大量时间，而且即使使用大量的哈希函数，bloom filter 仍然可能会出现错误判断，还需要进一步的查找，所以 2 个哈希函数比较适合做为 md5 值的初步查找。其中使用的 2 个哈希函数：sax_hash 实现：uint32_t result = 0; while(*key) result = (result2) +(unsigned char) *key+; return result;sdbm_hash 实现：uint32_t result = 0; while(*key) result = (unsigned char)*key+ +(result=0）大小，然后在得到的数据后添加 64bit 用于表示填充之前的数据长度。，目前的数据就为 512 的整数倍。sha1sha1 19：将一个数据块计算处理后得到一个 160bit 的 key 值。sha1 被广泛用于网络传输中的数据是否被篡改的检查。分别在源端和目标端计算 sha1 值，如果相同则认为数据是安全的，如果不同则认为数据在传输过程中被修改。首先，将数据转换为 bit 串，将 bit 串补一个 1，再补 0 至使消息长度为448+N*512bit（N=0）。用 64bit 的数据表示数据的原始长度。把 bit 串以 512bit 一组分组，依次处理分组，得到 160bit 的 key 值。RabinHashRabinHash20:将数据块当成由 01 组成的一个数字或着是多项式，将不可约的多项式取模得结果。能够在线性时间内得到 key 值，可通过移位异或等方法实现，能在较短的时间内得到结果。而且当哈希函数得到的 key 非变长时，能够在时间复杂度 O(n)内得到下一个 key 值，如果使用字或字节单位，处理的响应时间更短。云网关上重复数据删除使用了 md5 算法计算校验值，虽然 md5 可能产生碰撞问题，但是概率很小，相对比较安全，对于碰撞问题，会将 md5 值相同的数据块进行逐个 bit 的进行比对，以确保数据的安全性以及正确性。3.7 本章小结本章对云网关上重复数据删除的总体设计进行了总体的介绍。在 Swift 云平台上，主要是将文件信息和数据块进行分离独立保存以实现块级别的重复数据删除。云网关上存储结构针对云网关中于云端进行通信的 cloudfuse，在网关上使用桶，bloom filter，二叉查找树，缓存等数据结构保存查找信息，以便于上传文件时的重复数据查找过程。云网关上重复数据的查找流程设计主要通过散列表来实现 md5 值的查找。首先通过 bloom filter 进行初步查找，然后使用桶结合结合二次哈希及二叉查找树进行进一步的查找及插入任务。为了提高查找性能，使用了缓存条目结构，缓存了桶中最近访问过的条目，在插入时对缓存进行相应的换出换入操作，当程序关闭时将缓存31华中科技大学硕士学位论文中所有的条目写回文件中。由于云平台上的数据与文件信息独立存储，所以下载文件时，需要先获取文件信息，然后根据文件信息来获取相应的数据块信息。对于重复数据删除算法的选择上，根据 cloudfuse 及 Swift 云平台的具体情况，使用了在云网关上进行的源端块级别的重复数据删除，由于 cloudfuse 的 write 函数已经将文件进行定长上传，所以使用了定长算法，同时使用了 md5 来用于 key 值的计算处理。32华中科技大学硕士学位论文4云网关上重复数据删除的实现4.1 上传4.1.1 cloudfuse 正常文件上传流程用户使用 cloudfuse 上传文件至 Swift 云平台的大体流程，如图 4.1 所示：begincfs_getattrcfs_createcfs_writecfs_fgetattrcfs_flushcfs_releaseend图 4.1 cloudfuse 上传流程当上传文件至 Swift 云平台时，cloudfuse 的文件操作流程为：1 首先获取目的文件夹中文件的属性信息。2 若目的文件不存在则创建相应文件。3 将源文件数据写入目的文件。其中文件数据会以定长数据块大小从 buffer 中写入目的文件。4 获取目的文件的属性信息。33华中科技大学硕士学位论文5 对文件操作进行更新。6 关闭源文件及目标文件。4.1.2 修改后的 cloudfuse 上传流程重复数据删除所需进行修改重复数据删除操作主要在调用 cfs_create, cfs_write, cfs_fgetattr 时进行，由于在cfs_write 中数据以定长的数据块进行写操作，所以进行块级别的重复数据删除，每个块大小为 32KB。同时在创建文件时需设置 block 用来记录子文件信息。在 cfs_create 中主要进行重复数据删除的一些准备工作，对一些变量进行设置，同时在 hashtable 中查找该文件名，如果文件名已存在，则出错返回。由于需要进行块级别的重复数据删除，所以将数据以块为单位存放至云平台，需要在云网关上将数据与文件信息进行分离传送至云平台。所以在 cfs_write 中所需要进行的主要处理流程如图 4.2：34华中科技大学硕士学位论文beginmd5Set_subpath(md5)Write subpath into info_blockdedup_regfile_block_processIf(lengthBLOCK_MAX_SIZE)YWrite info_fileNReturn length图 4.2 重复数据删除的 cfs_write 处理流程图1 将需要写入的数据块计算 md5 值（第三章中介绍）。2 将 md5 值转换为相应的子文件名。3 将子文件名写入用来记录子文件信息的 block 中。4 对块数据进行重复数据删除，如果无重复块，则创建相应子文件并写入数据并对其进行更新操作，如果块重复，则记录块索引值，并返回。5 如果这是文件的最后一块（块大小小于 32KB），则将子文件信息快写入以目的文件命名的文件信息文件中。6 在 cfs_fgetattr 中主要需要更新文件的元数据属性信息。dedup_regfile_block_process 处理流程将数据计算的 md5 值传入 dedup_regfile_block_process，操作流程如图 4.3 所示：35华中科技大学硕士学位论文beginBindex=hash_valueY Bindex!=NULLNBlock_cmpN bindex = NULL | (