一致性Hash算法实现之PHP代码实现

算法 INFO院院长 121℃ 0评论

事情由来

公司要做一个基于discuz的论坛,需要支持同时在线千万级别,而discuz用于判断用户是否登录依据”session“常常是保存在数据库里面的,并且基于一张表保存,那么,当同时有大量用户挤入,会不会造成数据库无法承受而导致运行缓慢?答案是肯定的。那么,基于这种原因,我打算用分布式Redis来解决这个问题。按着不同的维度,这里可以是地区,活跃度等把用户登录信息分布存储在不同的redis中。

常用的负载均衡算法

在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括:轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least- Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其中哈希算法是最为常用的算法。那么,如果换做是你,当一个数据需要存入redis中,你会怎么选择存储的redis?这里我们假设有四台redis1,redis2,redis3,redis4。

1.hashResult = hash();//这里hash算法是你自定义算法,总之会得出一个unsigned int型的数据

2.hashResult  % 4 =  1;//假如余数为1,

好,当前这个要存储的数据存放在第一台redis中。以此类推,把所有的数据分别进行hash和取模,存放到余数的redis中。这样的方法会有一个致命的问题,当四台redis的其中一台redis1死机(down了),那么存放在这台redis1中的数据就丢失了,相当于有 (N-1)/ N,即  3/4 台的数据需要重新计算存放位置。这对系统是致命的打击。那么怎么能合理存放数据,并且能够任意的增加或删除redis机器呢?答案是  一致性hash.

一致性hash回顾

详细介绍可以参照

一致性hash算法实现详解

由于hash算法结果一般为unsigned int型,因此对于hash函数的结果应该均匀分布在[0,232-1]间,如果我们把一个圆环用232  个点来进行均匀切割

,首先按照hash(key)函数算出服务器(节点)的哈希值, 并将其分布到0~232的圆上。用同样的hash(key)函数求出需要存储数据的键的哈希值,并映

射到圆上。然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器(节点)上。如下

一致性Hash算法实现之PHP代码实现 图1

新增一个redis节点的时候,只有在圆环上新增节点逆时针方向的第一个redis节点的数据会受到影响。删除一个redis节点的时候,只有在圆环上原来删除

节点顺时针方向的第一个节点的数据会受到影响,因此通过Consistent Hashing很好地解决了负载均衡中由于新增节点、删除节点引起的hash值颠簸问题

。如下图:

一致性Hash算法实现之PHP代码实现 图2

PHP版本代码实现

<?php

/**
* 一致性hash的算法实现,用于解决redis的分布问题
* @package default
* @author qichangchun&lt;qichangchun@gomeplus.com&gt;
* @date: 2016/5/25
* @time: 10:43
*/

class FiexHash {
/**
* @var $_hasher 加密方式
* 加密方式的最后加密结果实质上是为了确定节点或者虚拟节点的存储位置position
*/

private $_hasher;

/**
* @var $_targetCount
* 节点数。例如已挂载四个redis节点,则$_targetCount=4
*/

private $_targetCount;

/**
* @var $_replicas
* 虚拟节点,每个redis节点生成$_replicas个虚拟节点
*/

private $_replicas;

/**
* @var $_target2Position
* 每个redis节点在圆环上对应的位置
* type Array
*/

private $_target2Position;

/**
* @var $_position2Target
* 每个圆环位置范围对应的实际节点
* type Array
*/

private $_position2Target;

/**
* @var $_hasSorted
* 是否已经把圆环上的节点进行排序,每次增加或删除节点都需要进行节点排序,以便可以顺时针查找数据存放最近节点
* type bool
*/

private $_hasSorted;

public function __construct($hasher, $replicas = 64) {
if (!in_array(get_class($hasher), array('HasherType_Crc32'))) {
throw new Exception("不可用的加密");
}
$this-&gt;_hasher = $hasher;
$this-&gt;_replicas = $replicas;
$this-&gt;_target2Position = $this-&gt;_position2Target = array();
$this-&gt;_targetCount = 0;
}

/**
* 新增节点到集群中
* @param $targetNew 新增的节点IP(一般为IP)
*/

public function addTarget($targetNew) {
//判断是否已经存在该节点
if (!isset($this-&gt;_target2Position[$targetNew])) {
//不存在,增加虚拟节点,并记录虚拟节点的位置以及每个位置对应的节点
$this-&gt;_target2Position[$targetNew] = array();
for ($i = 0; $i &lt; $this-&gt;_replicas; $i++) {
$position = $this-&gt;_hasher-&gt;hash($targetNew . $i);
$this-&gt;_position2Target[$position] = $targetNew;
$this-&gt;_target2Position[$targetNew][] = $position;
}
$this-&gt;_hasSorted = false;
$this-&gt;_targetCount++;
} else {
throw new Exception("该结点已经存在");
}
return $this;
}

/**
* 移除节点
* @param $targetRemove 要移除的节点IP
* @return mixed
*/

public function removeTarget($targetRemove) {
if (!empty($this-&gt;_target2Position[$targetRemove])) {
//移除位置信息和节点信息的对应关系
foreach ($this-&gt;_target2Position as $k =&gt; $p) {
unset($this-&gt;_target2Position[$k]);
unset($this-&gt;_position2Target[$p]);
}
$this-&gt;_hasSorted = false;
$this-&gt;_targetCount++;
}
return $this;
}

/**
* @param $resource 要读取或存的数据,例如“username”
* @param $resultCount 返回节点的个数
* @return 存放该数据的节点
*/

public function getTarget($resource,$resultCount = 1) {
$resourceHash = $this-&gt;_hasher-&gt;hash($resource);
if (!$this-&gt;_hasSorted) {
$this-&gt;_sortTargetAsc();
}
if($this-&gt;_targetCount == 1){
return array_unique(array_values($this-&gt;_position2Target));//返回当前唯一的节点
}
$result = array();//返回的节点,如 [192.168.1.1,192.168.1.2]
foreach($this-&gt;_position2Target as $position =&gt; $target){
//echo '&lt;/br&gt;'.$position.'--&gt;'.$target;
if($position &gt; $resourceHash){
if(count($result) &lt; $resultCount &amp;&amp; !in_array($target,$result)){
$result[] = $target;
}
}
}
return $result;
}

/**
* 将所有节点及虚拟节点进行排序
*/

private function _sortTargetAsc(){
ksort($this-&gt;_position2Target, SORT_REGULAR);
$this-&gt;_hasSorted = true;
}
}
/**
* Interface HasherType
* hash算法接口,实现hash加密方法
*/

interface HasherType {
public function hash($string);
}

/**
* Class HasherType_Crc32
* crc32hash算法实现
*/

class HasherType_Crc32 implements HasherType{
public function hash($string) {
return crc32($string);
}
}

/**
* 例子
*/

$redis = array('192.168.1.1','192.168.1.2','192.168.1.3','192.168.1.4');
$instance = new FiexHash(new HasherType_Crc32(),12);
$instance -&gt; addTarget("192.168.1.101");
$instance -&gt; addTarget("192.168.1.102");
$instance -&gt; addTarget("192.168.1.103");
$instance -&gt; addTarget("192.168.1.104");
$instance -&gt; addTarget("192.168.1.105");
$instance -&gt; addTarget("192.168.1.106");
$instance -&gt; addTarget("192.168.1.107");
$instance -&gt; addTarget("192.168.1.108");
$res = $instance -&gt;getTarget('test2',1);
var_dump($res);

转载请注明:INFO院 » 一致性Hash算法实现之PHP代码实现

喜欢 (0)or分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址