本发明涉及云计算技术领域， 尤其涉及一种基于一致性 hash算法存储资 源的方法。 背景技术

在云存储中， 存储的资源与存储位置之间的关系往往记录在 一台元数据 服务器中， 在元数据服务器中往往使用 hash (哈希）算法进行处理。 传统的 哈希算法是指一个集合 M, 通过某种算法， 映射到另外一个较小的集合 N。 比如现在当前存储的资源有 1M的文件， 存储在 100台机器上， 1M的文件与 100台机器之间通过某种算法进行映射， 可以使用 10请求通过该算法查找文 件位置。

在现有算法中， 在集合 N的样本空间变化之后， 集合 M与集合 N的映 射关系将会发生变化， 这种变化在云存储中会带来很大的影响。 例如， 在上 述 100台机器增加到 101台时， 1M文件的位置需要重新计算和定位，这种运 算量是非常大的。 一旦元数据服务器死机， 会导致云存储服务中断， 而云存 储使用集中元数据设计的原因， 主要是没有合适的弹性哈希算法， 来计算存 储的资源所在的存储位置。 传统的哈希算法比较注重冲突处理， 而在云存储 中的哈希算法， 更注重 hash映射空间变化之后， 希望能够尽可能地保持资源 与 hash值关系的稳定。 一旦能保持稳定， 则可以抛弃元数据服务器， 釆用无 中心结构来存储资源传统的 hash值算法。

但是现有技术中的算法还无法实现当用于存储 资源的机器数量发生改变 时， 仍能保持资源与 hash值关系的稳定， 降低映射关系的变化。 发明内容

(一） 要解决的技术问题

针对上述缺陷， 本发明要解决的技术问题是如何解决映射空间 变化时降 低映射关系的变化， 对资源的定位产生尽量小的影响。

(二）技术方案 为解决上述问题， 本发明提供了一种基于一致性 hash算法存储资源的方 法， 其特征在于， 所述方法具体包括：

51、 从资源集合中选取元素， 并计算所述元素的哈希值， 计算公式为 h=m%n, 其中 h为所述哈希值， m为资源集合 M中元素的值， n为大于等于 样本空间 N的值的最小 2次幂；

52、 比较 h与 n的值的大小， 如果 h小于 n则所述资源集合 M中的资源 对应于所述样本空间 N的 h值的位置，否则对应于所述样本空间 N的 h/2值 的位置。

进一步地， 步骤 S2中对应于所述样本空间 N的 h/2值的位置还包括： 对于写请求， 当存储系统中所述样本空间 N的存储空间增大时， n的值 变大， 并在增加后的样本空间 N1的 h/2位置处进行写操作。

进一步地，所述步骤 S2中对应于所述样本空间 N的 h/2值的位置还包括： 对于写请求， 当存储系统中所述样本空间 N的存储空间减小时， n的值 变小， 并在减小后的样本空间 N2的 h/2位置处进行写操作。

进一步地，所述步骤 S2中对应于所述样本空间 N的 h/2值的位置还包括： 对于读请求， 在所述样本空间 N的 h/2位置处进行一级查找， 如果找到 则直接在所述读请求中相应的操作位置进行读 操作， 否则继续在所述样本空 间 N的 h/4位置处进行二级查找， 并循环上述操作在所述样本空间 M的 h/2 ^s 位置进行 s级查找， 知道找到为止， 其中 s为整数且8≥3。

进一步地， 所述读请求或写请求中包含读操作或写操作的 操作位置。 进一步地， 在所述读请求中相应的操作位置进行读操作之 后还包括根据 查找到的位置对所述资源集合中元素的存储位 置进行纠正。

(三）有益效果

本发明提供了一种基于一致性 hash算法存储资源的方法， 通过对计算的 hash值进行伙伴处理，避免在映射空间发生变� �后 hash关系发生激烈变化，解 决了云存储的节点发生动态变化时导致资源定 位变化的问题， 同时还能够提 高资源存储和读取的速度。 附图说明 图 1为本发明实施例中一种基于一致性 hash算法存储资源的方法的步骤 流程图。 具体实施方式

下面结合附图和实施例， 对本发明的具体实施方式作进一步详细描述。 以下实施例用于说明本发明， 但不用来限制本发明的范围。

本发明实施例中提供了本发明提供了一种基于 一致性 hash算法存储资源 的方法， 步骤流程如图 1所示， 具体包括以下步骤：

步骤 S1 : 从资源集合中选取元素， 并计算该元素的哈希值。

计算哈希值的公式为 h=m%n, 其中 h为计算得到的哈希值， m为资源集 合 M中元素的值， n为大于等于样本空间 N的值的最小 2次幂。

样本空间 N中是用于存储资源集合 M中资源的机器集合， 而且 m和 n 之间无明确的大小关系， m可大于等于 n, 也可小于 n, 但是 n值的取值是根 据样本空间 N的值计算的， 一定要大于等于样本空间 N的值的最小 2次幂， 例如： 样本空间 N中有 3个用于存储资源的机器， 则 n的值为 2 ² =4>3； 如果 样本空间 N中有 5个用于存储资源的机器， 则 n的值为 2 ³ =8>5。

本实施例中的 hash算法是参考现有的伙伴算法得到的。 对于固定分区和 动态分区方案都存在一定的缺陷， 固定分区方案限制活跃进程的数目， 而且， 可用分区的大小与进程大小非常不匹配， 空间的利用率非常低。 动态分区的 维护十分复杂， 而且需要紧凑的开销。 一个比较有吸引力的折衷方案是伙伴 算法。 在伙伴系统中， 内存块的大小为 2k, L<K<U, 其中 2L为分配的最小 块的尺寸， 2u为分配的最大块的尺寸。伙伴算法能够高效� ��分配和回收内存， 并可以避免内存碎片的产生， 从而提高了物理内存的利用率。 伙伴算法一次 分配和释放 2的幂次方个页面，而本实施例中的 hash算法中的样本空间 N中 资源的数目 n就是大于等于样本空间 N的最小 2次幂。

步骤 S2: 比较 h与 n的值的大小，如果 h小于 n则资源集合 M中的资源 对应于样本空间 N的 h值的位置， 否则对应于样本空间 N的 h/2值的位置。

具体的： 对于写请求， 当存储系统中样本空间 N 的存储空间增大时， n 的值变大， 并在增加后的样本空间 的 h/2位置处进行写操作； 对于写请求， 当存储系统中样本空间 N的存储空间减小时， n的值变小， 并在减小后的样本空间 N ₂ 的 h/2位置处进行写操作；

对于读请求， 在样本空间 N的 h/2位置处进行一级查找， 如果找到则直 接在读请求中相应的操作位置进行读操作， 否则继续在样本空间 N的 h/4位 置处进行二级查找，并循环上述操作在样本空 间 M的 11/ 2 ⁵ 位置进行 s级查找， 知道找到为止， 其中 s为整数且8≥3。

读请求或写请求中包含读操作或写操作的操作 位置。 对于读请求， 存储 空间改变与否， 改变的只是 n的值， 而算法不会改变。

在读请求中相应的操作位置进行读操作之后还 包括根据查找到的位置对 资源集合中元素的存储位置进行纠正。

通过使用本实施例中提供的方法， 通过对计算的 hash值进行伙伴处理， 避免在映射空间发生变化后 hash关系发生激烈变化， 解决了云存储的节点发 生动态变化时导致资源定位变化的问题， 将重新定位的变化降低到最小范围 内， 同时还能够提高资源存储和读取的速度。

以上实施方式仅用于说明本发明， 而并非对本发明的限制， 有关技术领 域的普通技术人员， 在不脱离本发明的精神和范围的情况下， 还可以做出各 种变化和变型， 因此所有等同的技术方案也属于本发明的范畴 ， 本发明的专 利保护范围应由权利要求限定。 工业实用性

本发明提供了一种基于一致性 hash算法存储资源的方法， 通过对计算的 hash值进行伙伴处理， 避免在映射空间发生变化后 hash关系发生激烈变化， 解决了云存储的节点发生动态变化时导致资源 定位变化的问题， 同时还能够 提高资源存储和读取的速度。