一致性哈希算法以及其PHP实现详细解析

在做服务器负载均衡时候可供选择的负载均衡的算法有很多，包括：  轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希算法是最为常用的算法.

典型的应用场景是： 有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。

常用的算法是对hash结果取余数 (hash() mod N)：对机器编号从0到N-1，按照自定义的hash()算法，对每个请求的hash()值按N取模，得到余数i，然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。那么，如何设计一个负载均衡策略，使得受到影响的请求尽可能的少呢？

在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以说Consistent Hashing 是分布式系统负载均衡的首选算法。

1、Consistent Hashing算法描述

下面以Memcached中的Consisten Hashing算法为例说明。
由于hash算法结果一般为unsigned int型，因此对于hash函数的结果应该均匀分布在[0,232-1]间，如果我们把一个圆环用232 个点来进行均匀切割，首先按照hash(key)函数算出服务器（节点）的哈希值， 并将其分布到0～232的圆上。

用同样的hash(key)函数求出需要存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器（节点）上。

 Consistent Hashing原理示意图

新增一个节点的时候，只有在圆环上新增节点逆时针方向的第一个节点的数据会受到影响。删除一个节点的时候，只有在圆环上原来删除节点顺时针方向的第一个节点的数据会受到影响，因此通过Consistent Hashing很好地解决了负载均衡中由于新增节点、删除节点引起的hash值颠簸问题。

 Consistent Hashing添加服务器示意图

虚拟节点（virtual nodes）：之所以要引进虚拟节点是因为在服务器（节点）数较少的情况下（例如只有3台服务器），通过hash(key)算出节点的哈希值在圆环上并不是均匀分布的（稀疏的），仍然会出现各节点负载不均衡的问题。虚拟节点可以认为是实际节点的复制品（replicas），本质上与实际节点实际上是一样的（key并不相同）。引入虚拟节点后，通过将每个实际的服务器（节点）数按照一定的比例(例如200倍)扩大后并计算其hash(key)值以均匀分布到圆环上。在进行负载均衡时候，落到虚拟节点的哈希值实际就落到了实际的节点上。由于所有的实际节点是按照相同的比例复制成虚拟节点的，因此解决了节点数较少的情况下哈希值在圆环上均匀分布的问题。

虚拟节点对Consistent Hashing结果的影响

从上图可以看出，在节点数为10个的情况下，每个实际节点的虚拟节点数为实际节点的100-200倍的时候，结果还是很均衡的。

第3段中有这些文字：“但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；”

为何是 (N-1)/N 呢？解释如下：

比如有 3 台机器，hash值 1-6 在这3台上的分布就是：
host 1: 1 4
host 2: 2 5
host 3: 3 6
如果挂掉一台，只剩两台，模数取 2 ，那么分布情况就变成：
host 1: 1 3 5
host 2: 2 4 6

可以看到，还在数据位置不变的只有2个： 1，2，位置发生改变的有4个，占共6个数据的比率是 4/6 = 2/3这样的话，受影响的数据太多了，势必太多的数据需要重新从 DB 加载到 cache 中，严重影响性能

【consistent hashing 的办法】
上面提到的 hash 取模，模数取的比较小，一般是负载的数量，而 consistent hashing 的本质是将模数取的比较大，为 2的32次方减1，即一个最大的 32 位整数。然后，就可以从容的安排数据导向了，那个图还是挺直观的。
以下部分为一致性哈希算法的一种PHP实现。点击下载

赞 (0)

相关推荐

  • php加密算法之实现可逆加密算法和解密分享

    加密算法如下: 复制代码 代码如下: function encrypt($data, $key){ $key = md5($key);    $x  = 0;    $len = strlen($data);    $l  = strlen($key);    for ($i = 0; $i < $len; $i++)    {        if ($x == $l)         {         $x = 0;        }        $char .= $key{$x};   

  • 又一个PHP实现的冒泡排序算法分享

    经典的冒泡排序法一直是许多程序沿用的其中一种排序法,话说冒泡排序法在效率上比PHP系统函数sort更高效.本章不讨论性能,所以就不拿它来跟系统性能做对比了. 冒泡排序大概的意思是依次比较相邻的两个数,然后根据大小做出排序,直至最后两位数.由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序.但其实在实际过程中也可以根据自己需要反过来用,大树往前放,小数往后放. <?php /** * PHP中的冒泡排序法使用 */ // 预先声明一个数组 $arr = array (1

  • 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树的深度编历生成迷宫及A*自动寻路算法实例分析

    本文实例讲述了PHP树的深度编历生成迷宫及A*自动寻路算法.分享给大家供大家参考.具体分析如下: 有一同事推荐了三思的迷宫算法,看了感觉还不错,就转成php 三思的迷宫算法是采用树的深度遍历原理,这样生成的迷宫相当的细,而且死胡同数量相对较少! 任意两点之间都存在唯一的一条通路. 至于A*寻路算法是最大众化的一全自动寻路算法 废话不多说,贴上带代码 迷宫生成类: 复制代码 代码如下: class Maze{     // Maze Create     private $_w;     priv

  • php实现的生成迷宫与迷宫寻址算法完整实例

    php实现的生成迷宫与迷宫寻址算法完整实例

    本文实例讲述了php实现的生成迷宫与迷宫寻址算法.分享给大家供大家参考,具体如下: 较之前的终于有所改善.生成迷宫的算法和寻址算法其实是一样.只是一个用了遍历一个用了递归.参考了网上的Mike Gold的算法. <?php header('Content-Type: text/html; charset=utf-8'); error_reporting(E_ALL); //n宫格迷宫 define('M', 39);//宫数 define("S", 20);//迷宫格大小 $_p

  • PHP实现基于回溯法求解迷宫问题的方法详解

    本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言 最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述 这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.

  • 适用于抽奖程序、随机广告的PHP概率算法实例

    那么我们在程序里必然会设计到算法,即按照一定的概率让用户获得奖品.先来看两个概率算法函数. 算法一 复制代码 代码如下: /** * 全概率计算 * * @param array $p array('a'=>0.5,'b'=>0.2,'c'=>0.4) * @return string 返回上面数组的key */function random($ps){    static $arr = array();    $key = md5(serialize($ps)); if (!isset

  • php实现的微信红包算法分析（非官方）

    php实现的微信红包算法分析（非官方）

    本文实例讲述了php实现的微信红包算法.分享给大家供大家参考.具体如下: 最近一直在微信群里体验红包功能,红包类型有两种: 1. 普通红包 2. 拼手气红包 普通红包就不用多解析了,大锅饭原理,平分. 拼手气红包讲的是手气(运气),有人可以抢到很多,有人抢的少得可怜,当然也不是先抢就一定多,说到底了就是随机. 想了想,自己写写看,能不能实现类似的功能(不敢说是算法). // $bonus_total 红包总金额 // $bonus_count 红包个数 // $bonus_type 红包类型 1

  • php实现猴子选大王问题算法实例

    本文实例讲述了php实现猴子选大王问题算法.分享给大家供大家参考.具体分析如下: 一.问题: n只猴子围坐成一个圈,按顺时针方向从1到n编号. 然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数, 如此重复,直至剩下一个猴子,它就是大王. 设计并编写程序,实现如下功能: (1)   要求由用户输入开始时的猴子数$n.报数的最后一个数$m. (2)   给出当选猴王的初始编号. 二.解决方法: /** * @param int $n 开始时的猴子数

  • PHP 快速排序算法详解

    PHP 快速排序算法详解

    概念 这里借用百度百科的一张图来,非常形象: 快速排序算法是对冒泡算法的一个优化.他的思想是先对数组进行分割, 把大的元素数值放到一个临时数组里,把小的元素数值放到另一个临时数组里(这个分割的点可以是数组中的任意一个元素值,一般用第一个元素,即$array[0]),然后继续把这两个临时数组重复上面拆分,最后把小的数组元素和大的数组元素合并起来.这里用到了递归的思想. PHP实现 复制代码 代码如下: /*     快速排序 */ function quickSort($array) {    

  • php实现rc4加密算法代码

    代码 复制代码 代码如下: /* * rc4加密算法 * $pwd 密钥 * $data 要加密的数据 */ function rc4 ($pwd, $data)//$pwd密钥 $data需加密字符串 { $key[] =""; $box[] =""; $pwd_length = strlen($pwd); $data_length = strlen($data); for ($i = 0; $i < 256; $i++) { $key[$i] = ord(

  • PHP面试常用算法(推荐)

    一.冒泡排序 基本思想: 对需要排序的数组从后往前(逆序)进行多遍的扫描,当发现相邻的两个数值的次序与排序要求的规则不一致时,就将这两个数值进行交换.这样比较小(大)的数值就将逐渐从后面向前面移动. //冒泡排序 <?php function mysort($arr) { for($i = 0; $i < count($arr); $i++) { $isSort = false; for ($j=0; $j< count($arr) - $i - 1; $j++) { if($arr[$

随机推荐