日拱一卒无有尽,功不唐捐终入海

深入浅出一致性hash及PHP代码实现

系统架构 Sam 708℃ 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的介绍,网上有很多,大家自行google即可。这里我简单的盗图说明一下,哈哈哈。省事!

由于hash算法结果一般为unsigned int型,因此对于hash函数的结果应该均匀分布在[0,232-1]间,如果我们把一个圆环用232  个点来进行均匀切割,首先按照hash(key)函数算出服务器(节点)的哈希值, 并将其分布到0~232的圆上。用同样的hash(key)函数求出需要存储数据的键的哈希值,并映射到圆上。然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器(节点)上。如下

网站架构byPHP笔记phpnote.cc

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

网站架构byPHP笔记phpnote.cc

学习困惑

1.为什么hash算法结果会分布在1-2^32 -1的范围呢?

2.那一般企业redis大多不超过十台,因此每台redis之间的环的角度可能出现不平衡性(例如redis1占用了一半圆,其余的redis来分剩余一半圆环),所以当数据量较大的时候,运用一致性hash还是会出现数据分布不均匀的情况,从而破坏了hasn算法的ping。怎么办?

这里引入虚拟节点的概念:虚拟节点可以认为是实际节点的复制品(replicas),其实就是redis1又生了很多个孩子redis1-1,redis1-2,这样redis1家族通过hash算出来的位置会均匀的分布在圆环中各个位置。在进行负载均衡时候,落到虚拟节点的哈希值实际就落到了实际的节点上。由于所有的实际节点是按照相同的比例复制成虚拟节点的,因此解决了节点数较少的情况下哈希值在圆环上均匀分布的问题。

3.我们运用一致性hash的算法的最终目的是干什么?

简单的说,是用来取出一个节点。这个节点用来存放或者读取你想要存放或者读取的数据。

PHP代码实现

其实,很多人都了解过一致性hash算法,只是对它如何实际运用到场景中不太明白,那么我们就用php代码实际来实现一下该算法,并模拟一个实际场景。

转载自:http://blog.csdn.net/ccyours/article/details/51495878

转载请注明:PHP笔记 » 深入浅出一致性hash及PHP代码实现

喜欢 (0)
发表我的评论
取消评论

表情

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

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