44<海性能计算发展与应用204年第三期总第四十人期 块以为粒度进行。路由粒度大,能使单个节点保持较 有状态路由在路由决策的时候,会查询每个节 大的数据流重复局部性,这对利用数据流重复局部点的 B loom filter,以获取与每个节点重复数据块的数 性进行吞吐率加速的系统来说非常重要。而过大的目,选择重复数据块最多的节点进行路由。通常, 路由粒度,可能会导致存在于其他节点的很多重复个节点上的数据越多,它与新到来的超级块中重 数据块检测不出来。当以单个数据块进行路由时, 复块数目最多的可能性也就越大,如果仅仅依靠重 理论上通过定义规则,可以准确的判断单个数据块复块的数目作为路由的依据,则可能导致单个节点 应该发往哪个节点从而实现全局去重。如定义规则上的数据越积越多。解决方法之一是在判断路由目 hash%k==n发往第n个节点,那么所有满足这一规则的节点的时候,将各节点当前的空间利用率也考虑 的索引项都会存在于节点n。但是以单个数据块为在内。文献B6采用的机制是用超级块与单个物理节 粒度进行路由会完全破坏节点上的数据流重复局部点重复的块数除以存储空间利用率作为路由决策的 性,使原有的加速机制(如DDFS中的SISL、LPC) 权重。实验验证,有状态路由能够适应更多的节点 无效。 数,达到更高的去重率,并且因其在路由的过程中 Extrem e B inn ing以文件为粒度进行路由,它通就考虑到了负载的平衡,不需要做数据迁移。但其 内存中的一级索引表确定相似文件的bi所在的引入的额外计算、内存开销不容小觑。 节点位置,然后把文件发送到该节点。 Extreme 随着数据存储要求的不断提高以及集群存储在 B inn ing在分布式情况下能够达到与单节点时相同企业范围内的广泛应用,对重复数据删除技术的研 的数据缩减率,且各个节点之间不存在依赖性。但究重点也从单节点转移到了集群环境下。重复数据 Extrem e b inning针对的是数据流以单个文件随机到删除技术适用的集群架构、在集群中面临的去重率 来的场景。大多数备份应用先将大量备份文件进行和效率的平衡、集群的动态扩展性问题都需要进行 打包,在这种情况下利用文件相似性进行路由的进一步的研究 Extrem e b inn ing方法有效性会降低 HYDRAstori是一个以单个数据块为粒度进行路3.7其他研究问题 由的集群重复数据删除存储系统,它采用分布式哈 在对重复数据删除系统性能研究方面,除了经 希表分布索引表项。将备份数据流切成6KB的较大典的对磁盘索引瓶颈的研究,还有对分块和哈希计 的块,然后路由到存储节点。 HYDRA Stor采用的是简算过程的优化。文献B3用协处理器 PadLock来加速哈 单的路由策略,在存储节点上对指纹空间进行均匀希计算过程。文献B2提出了采用流水线方式和计算 划分,各节点之间不存在依赖。在4-12个存储节点操作并行化来加速去重过程,相对于传统的串行执 上获得了几百兆的吞吐率 行方式获得了3-4倍的加速。文献5提出了考虑数 文献B6]提出了以超级块为粒度进行路由的方据类型和硬件平台的自适应流水线,比固定流水线 法。超级块由多个连续数据块组成,既保留了大部有50%的性能提升 分的数据流重复局部性,又不至于因为粒度太大造 因为记录哈希序列的文件元数据(被称为file 成大量重复数据块检测不出来。实验表明超级块平 recipe)与数据的逻辑大小成正比。数据缩减率越 均大小在IMB的时候能够获得数据缩减率和吞吐率的高, file recipe占用的比例就越高。因此有研究者致力 折中 于研究减少 file recipe占用空间的方法。文献B1提出 ⅱ负载均衡 了一种有效的压缩方法,减少了93%的文件元数据占 文献B6]提出了两种路由策略,分别称为无状空间。 态的路由策略和有状态的路由策略。无状态的路由 重复数据删除技术已经在二级存储得到了非常 策略仅仅参考超级块的内容进行决策,它首先为超广泛的应用,EMC、HP、BM、NEC、 Neta pp等大型 级块计算一个特征(如选择其最小数据块的哈希存储供应商都推出了用于二级存储的重复数据删除 值),然后根据特征进行路由。而有状态的路由策设备。但考虑到去重对系统延迟的影响,主存储系 略则要考虑到各节点目前的状态,以达到更高的去统很少采用重复数据删除技术。 DEDE3I是一个主存 重率,但需要更多的计算资源和内存空间。 储去重系统,构建在VMFS之上,在SAN环境中采用 无状态路由有可能造成一个节点上的数据越积后处理的方式对分布式文件系统中的文件进行块级 越多,需要平衡各节点的负载。策略是在某节点的别去重。对主存储采用在线去重技术是一个挑战 负载超过平均负载的某个阈值时,进行数据迁移。 id edup s和DBLK分别提出了减轻主存储去重系统 数据的迁移以bi为单位进行,一个bin中存放着多个访问延迟的方法。如何将重复数据删除技术在主存 具有相同映射值的超级块 储中进行高数据缩减率、低延迟的应用是今后的一44 《高性能计算发展与应用》 2014年第三期 总第四十八期 块[7]为粒度进行。路由粒度大，能使单个节点保持较 大的数据流重复局部性，这对利用数据流重复局部 性进行吞吐率加速的系统来说非常重要。而过大的 路由粒度，可能会导致存在于其他节点的很多重复 数据块检测不出来。当以单个数据块进行路由时， 理论上通过定义规则，可以准确的判断单个数据块 应该发往哪个节点从而实现全局去重。如定义规则 hash%k==n发往第n个节点，那么所有满足这一规则 的索引项都会存在于节点n。但是以单个数据块为 粒度进行路由会完全破坏节点上的数据流重复局部 性，使原有的加速机制（如DDFS中的SISL、LPC） 无效。 Extreme Binning以文件为粒度进行路由，它通 过内存中的一级索引表确定相似文件的bin所在的 节点位置，然后把文件发送到该节点[19]。Extreme Binning在分布式情况下能够达到与单节点时相同 的数据缩减率，且各个节点之间不存在依赖性。但 Extreme Binning针对的是数据流以单个文件随机到 来的场景。大多数备份应用先将大量备份文件进行 打包，在这种情况下利用文件相似性进行路由的 Extreme Binning方法有效性会降低。 HYDRAstor[7]是一个以单个数据块为粒度进行路 由的集群重复数据删除存储系统，它采用分布式哈 希表分布索引表项。将备份数据流切成64KB的较大 的块，然后路由到存储节点。HYDRAstor采用的是简 单的路由策略，在存储节点上对指纹空间进行均匀 划分，各节点之间不存在依赖。在4-12个存储节点 上获得了几百兆的吞吐率。 文献[36]提出了以超级块为粒度进行路由的方 法。超级块由多个连续数据块组成，既保留了大部 分的数据流重复局部性，又不至于因为粒度太大造 成大量重复数据块检测不出来。实验表明超级块平 均大小在1MB的时候能够获得数据缩减率和吞吐率的 折中。 ii. 负载均衡 文献[36]提出了两种路由策略，分别称为无状 态的路由策略和有状态的路由策略。无状态的路由 策略仅仅参考超级块的内容进行决策，它首先为超 级块计算一个特征（如选择其最小数据块的哈希 值），然后根据特征进行路由。而有状态的路由策 略则要考虑到各节点目前的状态，以达到更高的去 重率，但需要更多的计算资源和内存空间。 无状态路由有可能造成一个节点上的数据越积 越多，需要平衡各节点的负载。策略是在某节点的 负载超过平均负载的某个阈值时，进行数据迁移。 数据的迁移以bin为单位进行，一个bin中存放着多个 具有相同映射值的超级块。 有状态路由在路由决策的时候，会查询每个节 点的Bloom filter，以获取与每个节点重复数据块的数 目，选择重复数据块最多的节点进行路由。通常， 一个节点上的数据越多，它与新到来的超级块中重 复块数目最多的可能性也就越大，如果仅仅依靠重 复块的数目作为路由的依据，则可能导致单个节点 上的数据越积越多。解决方法之一是在判断路由目 的节点的时候，将各节点当前的空间利用率也考虑 在内。文献[36]采用的机制是用超级块与单个物理节 点重复的块数除以存储空间利用率作为路由决策的 权重。实验验证，有状态路由能够适应更多的节点 数，达到更高的去重率，并且因其在路由的过程中 就考虑到了负载的平衡，不需要做数据迁移。但其 引入的额外计算、内存开销不容小觑。 随着数据存储要求的不断提高以及集群存储在 企业范围内的广泛应用，对重复数据删除技术的研 究重点也从单节点转移到了集群环境下。重复数据 删除技术适用的集群架构、在集群中面临的去重率 和效率的平衡、集群的动态扩展性问题都需要进行 进一步的研究。 3.7 其他研究问题 在对重复数据删除系统性能研究方面，除了经 典的对磁盘索引瓶颈的研究，还有对分块和哈希计 算过程的优化。文献[33]用协处理器PadLock来加速哈 希计算过程。文献[32]提出了采用流水线方式和计算 操作并行化来加速去重过程，相对于传统的串行执 行方式获得了3-4倍的加速。文献[45]提出了考虑数 据类型和硬件平台的自适应流水线，比固定流水线 有50%的性能提升。 因为记录哈希序列的文件元数据（被称为file recipe）与数据的逻辑大小成正比。数据缩减率越 高，file recipe占用的比例就越高。因此有研究者致力 于研究减少file recipe占用空间的方法。文献[31]提出 了一种有效的压缩方法，减少了93%的文件元数据占 用空间。 重复数据删除技术已经在二级存储得到了非常 广泛的应用，EMC、HP、IBM、NEC、NetApp等大型 存储供应商都推出了用于二级存储的重复数据删除 设备。但考虑到去重对系统延迟的影响，主存储系 统很少采用重复数据删除技术。DEDE[3]是一个主存 储去重系统，构建在VMFS之上，在SAN环境中采用 后处理的方式对分布式文件系统中的文件进行块级 别去重。对主存储采用在线去重技术是一个挑战， iDedup[15]和DBLK[16]分别提出了减轻主存储去重系统 访问延迟的方法。如何将重复数据删除技术在主存 储中进行高数据缩减率、低延迟的应用是今后的一