微信号:openstacks

介绍:云计算技术的深入分析和解析;计算,存储,网路,SDN,KVM一网打尽......

3分钟学会一致性hash算法

2017-01-03 14:38 王宇行

本文介绍一致性hash算法的基本原理。他是swift中ring的理论基础。


普通Hash算法

假设有四台存储节点(Drive 0, 1, 2 and 3),有4个object需要存储在上面。用普通的Hash算法实现方法如下:

  • Step 1: 对象名称account/container/object作为键,使用MD5散列算法得到一个散列值key

  • Step 2: 用第一步计算得到的key mod N 得到存储节点的号(0,1,2 and 3) 
    N:为存储节点的数量,本例中N=4.

普通hash算法的缺点是: 如果N增加1,映射关系变成了key mod (N+1),会导致整个哈希环的重新分配,几乎全部的数据都要重新移动一遍,这样会造成极大的性能开销。


一致性哈希算法


一致性哈希算法实现

  • Step 1: 每个节点的机器名或者是IP地址最键,使用MD5散列算法得到一个散列值key,并将其分配到一个圆环区间上(这里取0-2^32)。

  • Step 2: 每个对象名称account/container/object作为键,使用MD5散列算法得到一个散列值key,也将其分配到这个圆环上。

  • Step 3: 从对象映射到的位置开始顺时针查找,将对象保存到找到的第一个节点上。



虚拟节点

平衡性是hash算法的一个重要指标,平衡性是指对于存储的所有对象,尽可能均匀的分到所有的设备上去。  注: 虚拟节点在swift里叫partion。

用上面提到的一致性哈希算法存储对象,当节点数量比较少时,平衡性会很差,所以引入了虚拟节点的概念来解决这个问题。

对每一个存储节点计算多个哈希,每个计算结果,都在ring中放置一个存储节点,称为虚拟节点。那么多个hash值该如何计算呢?解决方案是在服务器ip或主机名的后面增加编号,然后在计算Hash。比如一个存储节点对应三个虚拟节点,总共三个存储节点,计算方法如下:

  • Step 1: 分别以“A#1”、“A#2”、“A#3”做键,用MD5散列算法计算其散列值key,并将其分配到一个圆环区间上。

  • Step 2: 分别以“B#1”、“B#2”、“B#3”做键,用MD5散列算法计算其散列值key,并将其分配到一个圆环区间上。

  • Step 3: 分别以“C#1”、“C#2”、“C#3”做键,用MD5散列算法计算其散列值key,并将其分配到一个圆环区间上。

  • Step 4: 每个对象名称account/container/object作为键,使用MD5散列算法得到一个散列值key,也将其分配到这个圆环上。

  • Step 5: 从对象映射到的位置开始顺时针查找,将对象保存到找到的第一个节点上。



对象和存储节点的映射

加入虚拟节点后,一个实际的存储节点对应若干个虚拟的节点,对象和实际的存储节点的映射关系如下:对象——虚拟节点——设备,如下图所示:  





 
Devops 更多文章 Network Namespace在Openstack中的应用 基于Mesos和Docker的分布式计算平台 分布式系统的特点及设计理念 存储的崩溃 更快学会任何东西的终极指南
猜您喜欢 【第665期】京东单品页前端开发那些不得不说的事儿 奥斯卡才是真正的设计盛宴 怎么才能参与到Tomcat社区当中呢? 星聚tech talk:如何在百播大战中技压群雄 自学编程的六个技巧总结