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

2024-07-28 14:51:11

本文实例讲述了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);
}

这个接口分别定义了4个方法，cHash（将字符串处理为hash值）、addServer（增加一台服务器）、removeServer（移除一台服务器）、lookup（找到一台服务器来存储数据）

下面给出一个该接口的具体实现

/**
 * 具体一致性哈希实现
 * author chenqionghe
 * Class MyConsistentHash
 */
class MyConsistentHash implements ConsistentHash
{
 public $serverList = array(); //服务器列列表
 public $virtualPos = array(); //虚拟节点的位置
 public $virtualPosNum = 5;  //每个节点对应5个虚节点
 /**
  * 将字符串转换成32位无符号整数hash值
  * @param $str
  * @return int
  */
 public function cHash($str)
 {
  $str = md5($str);
  return sprintf('%u', crc32($str));
 }
 /**
  * 在当前的服务器列表中找到合适的服务器存放数据
  * @param $key 键名
  * @return mixed 返回服务器IP地址
  */
 public function lookup($key)
 {
  $point = $this->cHash($key);//落点的hash值
  $finalServer = current($this->virtualPos);//先取圆环上最小的一个节点当成结果
  foreach($this->virtualPos as $pos=>$server)
  {
   if($point <= $pos)
   {
    $finalServer = $server;
    break;
   }
  }
  reset($this->virtualPos);//重置圆环的指针为第一个
  return $finalServer;
 }
 /**
  * 添加一台服务器到服务器列表中
  * @param $server 服务器IP地址
  * @return bool
  */
 public function addServer($server)
 {
  if(!isset($this->serverList[$server]))
  {
   for($i=0; $i<$this->virtualPosNum; $i++)
   {
    $pos = $this->cHash($server . '-' . $i);
    $this->virtualPos[$pos] = $server;
    $this->serverList[$server][] = $pos;
   }
   ksort($this->virtualPos,SORT_NUMERIC);
  }
  return TRUE;
 }
 /**
  * 移除一台服务器（循环所有的虚节点，删除值为该服务器地址的虚节点）
  * @param $key
  * @return bool
  */
 public function removeServer($key)
 {
  if(isset($this->serverList[$key]))
  {
   //删除对应虚节点
   foreach($this->serverList[$key] as $pos)
   {
    unset($this->virtualPos[$pos]);
   }
   //删除对应服务器
   unset($this->serverList[$key]);
  }
  return TRUE;
 }
}

然后，我们来测试一下该算法

$hashServer = new MyConsistentHash();
$hashServer->addServer('192.168.1.1');
$hashServer->addServer('192.168.1.2');
$hashServer->addServer('192.168.1.3');
$hashServer->addServer('192.168.1.4');
$hashServer->addServer('192.168.1.5');
$hashServer->addServer('192.168.1.6');
$hashServer->addServer('192.168.1.7');
$hashServer->addServer('192.168.1.8');
$hashServer->addServer('192.168.1.9');
$hashServer->addServer('192.168.1.10');
echo "增加十台服务器192.168.1.1~192.168.1.10<br />";
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.2<br />";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.6<br />";
$hashServer->removeServer('192.168.1.6');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.8<br />";
$hashServer->removeServer('192.168.1.8');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.2<br />";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "增加一台服务器192.168.1.11<br />";
$hashServer->addServer('192.168.1.11');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';

运行结果如下

增加十台服务器192.168.1.1~192.168.1.10
保存 key1 到 server :192.168.1.2
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.6
保存 key4 到 server :192.168.1.8
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一台服务器192.168.1.2
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.6
保存 key4 到 server :192.168.1.8
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一台服务器192.168.1.6
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.3
保存 key4 到 server :192.168.1.8
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一台服务器192.168.1.8
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.3
保存 key4 到 server :192.168.1.10
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一台服务器192.168.1.2
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.3
保存 key4 到 server :192.168.1.10
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
增加一台服务器192.168.1.11
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.11
保存 key4 到 server :192.168.1.10
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4

可以，看到，使用一致性哈希后，无认是增加服务器还是减少服务器都最大程度的保证了数据的完整性、均匀性.

PS：这里再为大家提供2款hash相关在线工具供大家参考使用：

在线散列/哈希算法加密工具：
http://tools.jb51.net/password/hash_encrypt

在线MD5/hash/SHA-1/SHA-2/SHA-256/SHA-512/SHA-3/RIPEMD-160加密工具：
http://tools.jb51.net/password/hash_md5_sha

更多关于PHP相关内容感兴趣的读者可查看本站专题：《php加密方法总结》、《PHP编码与转码操作技巧汇总》、《PHP数学运算技巧总结》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》及《php正则表达式用法总结》

希望本文所述对大家PHP程序设计有所帮助。

Nginx 安装笔记(含PHP支持、虚拟主机、反向代理负载均衡)

系统环境:RHEL5 [ 2.6.18-8.el5xen ] 软件环境: nginx-0.7.17 lighttpd-1.4.20.tar.gz pcre-6.6-1.1 pcre-devel-6.6-1.1 php-5.1.6-5.el5 参考下载地址: http://sysoev.ru/nginx/nginx-0.7.17.tar.gz (最新稳定版为0.6.32) http://www.lighttpd.net/download/lighttpd-1.4.20.tar.gz #######
PHP经典算法集锦【经典收藏】

本文实例总结了PHP经典算法.分享给大家供大家参考,具体如下: 1.首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半. 思路:多少行for一次,然后在里面空格和星号for一次. <?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo '<br/>'; } 2.冒泡排序,C里基础算法,从小到大对一组数
PHP中对各种加密算法、Hash算法的速度测试对比代码

PHP 的Hash算法是比较常用的,现在的MD5有时候不太安全,就得用到Hash_algos()中的其它算法,下面进行了一个性能的比较. php代码: define('testtime', 50000); $algos = hash_algos(); foreach($algos as $algo) { $st = microtime(); for($i = 0; $i < testtime; $i++) { hash($algo, microtime().$i); } $et = microt
php 分库分表hash算法

复制代码代码如下: //分库分表算法 function calc_hash_db($u, $s = 4) { $h = sprintf("%u", crc32($u)); $h1 = intval(fmod($h, $s)); return $h1; } for($i=1;$i<100;$i++) { echo calc_hash_db($i); echo "<br>"; } function calc_hash_tbl($u, $n = 256
Thinkphp结合AJAX长轮询实现PC与APP推送详解

前言本文主要给大家介绍的关于Thinkphp结合AJAX长轮询实现PC与APP推送的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍. 实现逻辑某个操作(比如新建一条公告)后,触发同时推送消息给APP或是移动WEB的所有用户或指定用户. 不论性能,总还是有人会用到吧,实现如下(基于Thinkphp5消息推送): PHP长轮询 /* * long轮询 API查询接口 */ public function id_log() { if (request()->isPost()) {
PHP实现负载均衡下的session共用功能

本文实例讲述了PHP实现负载均衡下的session共用功能.分享给大家供大家参考,具体如下: 最近忙于开发台湾运动彩券第四版的程序,所以已经很久没有上来写东西了,今天随便写点东西和大家分享. 首先说一下负载均衡,相信大家都知道负载均衡可以很好地解决网站大流量的问题,负载均衡就是把用户的请求分发到多态pc上进行处理,既然分发了请求那么session就要考虑好处理方法.传统情况下php会把session存入本机的暂存档内,可是这种情况下分发了之后session就丢失了,其实最简单的解决方法就是用me
PHP实现负载均衡的加权轮询方法分析

本文实例讲述了PHP实现负载均衡的加权轮询方法.分享给大家供大家参考,具体如下: 1. 负载均衡算法有哪些? 轮询法:将请求按顺序轮流地分配到后端服务器上,它均衡地对待后端的每一台服务器,而不关心服务器实际的连接数和当前的系统负载. 随机法:通过系统的随机算法,根据后端服务器的列表大小值来随机选取其中的一台服务器进行访问. 源地址哈希法:根据获取客户端的IP地址,通过哈希函数计算得到一个数值,用该数值对服务器列表的大小进行取模运算,得到的结果便是客服端要访问服务器的序号.采用源地址哈希法进行负载
PHP开发负载均衡指南

今天,'大型服务器'模式已经过去,取而代之的是大量的小服务器,使用各种各样的负载均衡技术.这是一种更可行的方法,将使硬件成本降至最低. '更多小服务器'的优势超过过去的'大型服务器'模式体现在两个方面: 1. 如果服务器宕机,那么负载均衡系统将停止请求到宕机的服务器,转而分发负载到其他正常运行的服务器上. 2. 扩展你的服务器更加容易.你要做的仅仅是加入新的服务器到负载均衡系统.不需要中断你的应用运行. 所以,把握住这个机会:). 当然,代价就是这要求你的应用开发时增加一点复杂度.这就是本文要覆
php的hash算法介绍

Hash Table是PHP的核心,这话一点都不过分. PHP的数组,关联数组,对象属性,函数表,符号表,等等都是用HashTable来做为容器的. PHP的HashTable采用的拉链法来解决冲突, 这个自不用多说, 我今天主要关注的就是PHP的Hash算法, 和这个算法本身透露出来的一些思想. PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition), 这个算法被广泛运用与多个软件项目,Apache, P
PHP实现负载均衡session共享redis缓存操作示例

本文实例讲述了PHP实现负载均衡session共享redis缓存操作.分享给大家供大家参考,具体如下: 1.首先先创建html表单页面 <meta chatset='utf-8'> <center> <form action="se.php" method="post"> <table> <tr> <td>帐号:</td> <td><input type="

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

相关推荐

随机推荐