News新闻

业界新闻动态、技术前沿
Who are we?

您的位置:首页      网络营销      PHP实现的一致性Hash算法详解【分布式算法】

PHP实现的一致性Hash算法详解【分布式算法】

本文实例讲述了PHP实现的一致性Hash算法。分享给大家供大家参考,具体如下:一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法?比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对

本文实例讲述了PHP实现的一致性Hash算法。分享给大家供大家参考,具体如下:

一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法?

比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的方法(如key%服务器总数量),如果期间有服务器宕机了或者需要增加服务器,问题就出来了。 同一个key经过hash之后,再与服务器总数量取模的结果跟之前的结果会不一样,这就导致了之前保存数据的丢失。因此,引入了一致性Hash(Consistent Hashing)分布算法

把数据用hash函数(如md5,sha1),映射到一个圆环上,如上图所示,数据在存储时,先根据hash算法算出key的hash值,对应到这个环中的位置,如k1对应图中所示的位置同,然后沿着顺时针方向找到服务器节点B,然后把k1在存到B这个节点中。

如果B节点宕机了,则B上的数据就会落到C节点上,如下图所示

这样,只会影响C节点,对于其他节点A、D的数据不会造成影响。但是问题来了,这样会造成C节点负载过重的情况,因为C节点承担了B节点的数据,所以C节点容易宕机,这样造成了分布不均匀。

为了解决这个问题,引入了“虚拟节点“的概念:即想象空上环上有很多”虚拟节点“,一个真实的服务器节点对应多个虚拟节点,数据存储的时候沿着环的顺时针方向找到虚拟节点,就找到了对应的真实服务器节点。如下图

图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点,机器A负载存储A1、A2的数据,机器B负载存储B1、B2的数据,机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多,均匀分布,因此不会造成“雪崩”现象。

一致性哈希算法的PHP实现

下面给出一个接口

/**
 * 一致性哈希实现接口
 * Interface ConsistentHash
 */
interface ConsistentHash
{
 //将字符串转为hash值
 public function cHash($str);
 //添加一台服务器到服务器列表中
 public function addServer($server);
 //从服务器删除一台服务器
 public function removeServer($server);
 //在当前的服务器列表中找到合适的服务器存放数据
 public function lookup($key);
}

    我要评论
    共有 人参与,评论 条,顶帖 [点击查看]
  • 验证码:
  • 所有评论仅代表网友意见,与本站立场无关!