钛节点

我所认知的redis（三）--- 哈希一致性与集群

发表@2018-09-13 09:15:21

更新@2023-01-21 22:47:40

##### 单点redis的性能和容量总是有个极限的。
##### 假如你们有一台redis专门用来存储用户信息缓存，key都是user:uid这个规则，value是hash类型，那么当你们有5000万用户的时候，这台redis里就理论上就满员存储5000万个用户信息，从user:1... ...到user:500000。当业务发展，公司壮大，日活百万，即将上市的时候，你发现这台redis的QPS实在是不行了，达到极限了，业务会卡，而且机器内存已经很大很大了不太容易再继续升级了，拍了拍脑袋：这都快上市了，我自己都快身价过亿了，还买不起服务器？于是，你申请费用又加一台redis服务器，最终目的要实现：
- 两台redis分别承担50%的请求
- 两台redis分别存储50%的数据

##### 这个专业术语叫做数据分片。
##### 能够将这些key值均匀打散的办法，你自己还是有一些想法的，你灵机一动：从1到250000在第一台redis服务器，从250001到500000在第二台redis服务器。果断开始改代码，改到三分之一，突然大脑回路又清晰了：妈蛋！用户是不断增长的，刚才只想到了已有的前500000用户，尴尬，代码一顿回滚。
##### 吃顿饭功夫，你突然大脑灵光一闪，想起来小学数学老师教给自己的余数，没想到小学学到的知识现在终于用上了！
##### 将这个思路带入到redis中去，这样1号用户将会1 mod 2=1号redis服务器，2号用户将会2 mod 2=0号redis服务器上，3号用户将会3 mod 2=1号redis服务器上去...依次类推，即便是不断地在新增用户，这个算法依然可以妥妥地将用户以50%的比例平均分布到两台redis上去！
##### 代码一顿改，开发，测试，上线。
##### 过了半个月，突然有人说有一些用户动态内容也要缓存到redis中，但是这些动态的id都不是数字的，都是字母数字混合的uuid，没法办法用做余数计算，好尴尬！
##### 得想个办法把任何数据类型转换成数字或者一个可标记的存储位置，而且各种不同数据类型在转换完毕后还得均匀。如果转换算法不好导致十万个uuid在转换完毕后大量集中在某个区域，其他区域很少，这就不均衡了，这种不均衡会导致redis中存储的数据量也会不均衡，这不公平。
##### （tips：实际上取余就是最简单的哈希算法了，只不过你用了但你不知道。但是取余有个很大的问题，就是数据不均匀，及其容易产生冲突，两个不同的关键字很容易就被映射到同一个索引位置上）。
##### 网上资料一顿搜，你发现了解决这个问题的办法：哈希。简单地说，哈希算法就是通过把给定的关键字key通过某种映射算法映射到数组的一个位置上，从而可加快访问速度。一个好的哈希算法可以将每个关键字都均匀的分布到哈希表（你依然可以用数组来想象）的任意一个位置上，同时极大程度避免并与其他已被映射过的关键字的位置不发生冲突。
##### 世界是美好的，一些可爱的计算机界的大神们历经多年发明了一个叫做DJBX33A的hash算法，这个算法用如下寥寥几行php代码就可以实现：
```php
<?php
function djbx33a($str) {
  // hash(i) = hash(i-1) * 33 + str[i]
  $hash = 0;
  $s    = md5($str);
  $seed = 5;
  $len  = 32; 
  for ($i = 0; $i < $len; $i++) {
    // (hash << 5) + hash 相当于 hash * 33
    //$hash = sprintf("%u", $hash * 33) + ord($s{$i});
    //$hash = ($hash * 33 + ord($s{$i})) & 0x7FFFFFFF;
    $hash = ($hash << $seed) + $hash + ord($s{$i});
  }
  return $hash & 0x7FFFFFFF;
}
echo djbx33a( '任意string' ).PHP_EOL;
```
##### 利用哈希算法后改进后变成了这样：hash(动态uuid) mod 1，hash(动态uuid) mod 2，hash(动态uuid) mod 1.... ....完美解决了问题，以后任何类型的key都可以通过hash均匀的打散并均匀存储每台redis服务器上去。
##### 经过半年奋斗加班，公司终于上市了。
##### 公司上市后花钱推广了三天，用户量爆增，redis服务器又不够了，于是，你决定再加三台redis服务器（这样一共五台redis服务器），一开始没细想，按照上次的套路来就是了，开始改代码，改到三分之一，突然大脑回路又清晰了！妈蛋，还是有坑！
##### 假如六条用户动态，那么其uuid在经过hash之后分别是12、125245、54854、8845、254、5554548，在只有两台redis服务器的情况下分配如下：
- 12 mod 2 = 0
- 125245 mod 2 = 1
- 54854 mod 2 = 0
- 8845 mod 2 = 1
- 254 mod 2 = 0
- 5554548 mod 2 = 0
##### 然后同样还是这几个key在五台redis服务器的情况下，分配情况变成了如下：
- 12 mod 5 = 2
- 125245 mod 5 = 0
- 54854 mod 5 = 4
- 8845 mod 5 = 0
- 254 mod 5 = 4
- 5554548 mod 5 = 3

##### 是不是发现一个严重的问题：这么多缓存全都失效了，这不是坑爹么？这重建缓存得多长时间啊，重建期间这么多miss的请求直接会达到数据库上，那么，数据库是否能够经得起考验？会不会crash？瑟瑟发抖中... ...即便这次能混过去，那我以后如果再加redis服务器，岂不是还要经历一次？而且，万一假如其中一台redis服务器由于QPS过高crash了，打到这台redis的请求将会无效。
##### 在历经了上述这么多磨难后，你终于找到了一个截止到目前业界内较为彻底的解决方案：一致性哈希算法。
##### 下面我六个步骤再配合上亲手绘制的图来替你向大家解释一致性哈希算法的大概流程：
1.闭上眼睛，将0~2^32-1想象成一个圆圈，0就是圆圈的起点，2^32-1就是圆圈的尾巴，两个数字首尾相连。大概如下图所示：
![](https://ti-node.com/static/upload/6382235268694409217)
2.然后将任何四个key通过DJBX33A算法哈希成为整数，伪代码如下：
- $key1 = djbx33a( 'key1' );
- $key2 = djbx33a( 'key2' )；
- $key3 = djbx33a( 'key3' );
- $key4 = djbx33a( 'key4' );
这个时候，$key1、$key2、$key3、$key4都已经是整数了，然后继续闭上眼睛脑补这四个整数落在上一个步骤中那个圆环的相应的位置上，我们假设如下图所示：
![](https://ti-node.com/static/upload/6382235271693336577)

3.假设我们有三台redis服务器：node1和node2和node3，通过相同的哈希算法（这个很重要），也将其变为整数：
- $node1 = djbx33a( 'node1' );
- $node2 = djbx33a( 'node2' );
- $node3 = djbx33a( 'node3' );
这个时候，$node1、$node2、$node3都已经是整数了，然后继续闭上眼睛脑补这两个数字落在上上步骤那个圆环的相应位置上，我们假设如下图所示：
![](https://ti-node.com/static/upload/6382235274549657600)

4.现在我们从key1开始顺时针沿着圆环开始走，当遇到第一个服务器节点的时候（也就是node1），我们算key1算node1服务器。依次往下，大家可以看到key2和key3都属于node2服务器，key4属于node3服务器。如下图所示：
![](https://ti-node.com/static/upload/6382235276860719104)

5.新增服务器的时候，假如新增的节点叫做new-node，经过djbx33a哈希过后的整数落在了如图位置，那么依然按照4中规则，我们发现只有key2落在了new-node上，这也就是说，新增机器后，只有key2所属的服务器发生了变化，其他key依然还在原来的服务器上。整体如下图：
![](https://ti-node.com/static/upload/6382235279213723648)

6.删除服务的时候，假如是node3节点删除了，那么只有key4会发生变化，会规划到node1服务器下，其余key依然没有变化。整体如下图：
![](https://ti-node.com/static/upload/6382235281902272512)

##### 这就是传说中哈希一致性分布算法，大家可以尝试用php代码实现一下以上原理，有耐心就可以写出来的。
##### 下面提出一个新的概念：redis集群和中间件。其实上面叨叨了那么多，肯定有人问这么多台redis服务器，我代码里怎么链接？删除或者添加一台机器我都要修改业务代码，感觉并不符合社会主义主流价值观。所以，这个锅果断甩给运维。
##### 运维收到锅后，跟你说搭建个redis集群前面当一层代理就行了，你业务代码只需要连接那个代理就OK，至于代理后面的redis集群中增加机器还是删除机器，对你们开发来说都是透明的。
##### 实际上，上述来甩锅的过程中就蕴涵着redis数据分片的三种不同方案：
- 业务代码中实现数据分片。哈希一致性算法什么的，统统由客户端代码来实现，对于开发来说比较累。可以用用。
- redis中间价（代理）实现分片。对于开发来说，业务代码只需要连接redis中间件的IP地址即可。数据的分片由中间件程序自动实现，最大程度保证开发不受影响，而且易于运维操作。强烈推荐！
- redis服务器实现分片。目前好像只有redis cluster是这种做法，应用并不广泛，因为redis cluster本身也缺少一个大的应用案例。不推荐！

##### 目前市面上常用的redis集群解决方案大概有三种：
- twemproxy。这个是twitter的人搞出来的这么一坨东西，非常成熟，很多大公司生产环境都在使用这个东西。但这个东西有两个缺点：一是没有良好运维控制面板，二是不支持平滑添加新机器，也就是说每当新添加了机器，那些key不会自动从老节点中转移到新节点。
- codis。豌豆荚的人搞的东西，是魔改了后的redis，非常牛逼。twemproxy的两个很大的缺点，codis都没有。codis提供了一套良好完整的网页控制和监控面板，同时对于新增机器数据平滑迁移有着良好的支持。codis采用了组的概念，一组中有一个redis master和至少一个slave，当某组的master挂了后，可以将其中一台slave提升为master。codis用了一种预分片（pre-sharding）的技术，上来就先将所有数据分为了1024个slot（槽），可以简单理解codis集群中可以最多添加1024组机器！如果每台32G内存，1024*32G=32768G，大约就是32TB！
- redis cluster。恕我直言，没用过也没调研过，但原来大概了，这是一种去中心化方案，累觉不爱，而且目前应用案例比较少，不推荐。

##### tips：我公司目前部署就是codis，非常稳定！twemproxy前期是做过调研的，后面我会出两篇文章用来实践部署这两种集群。
---