Redis系列目录



redis系列之——分布式锁



redis系列之——缓存穿透、缓存击穿、缓存雪崩



redis系列之——Redis为什么这么快？



redis系列之——数据持久化（RDB和AOF）



redis系列之——一致性hash算法



redis系列之——高可用（主从、哨兵、集群）



redis系列之——事物及乐观锁



redis系列之——数据类型geospatial：你隔壁有没有老王？



redis系列之——数据类型bitmaps：今天你签到了吗？



布隆过滤器是个啥！



一致性hash算法你了解吗？什么时候使用？解决什么问题？redis集群模式使用了一致性hash算法了吗？





数据分片（sharding）



分布式数据存储时，经常要考虑数据分片，避免将大量的数据放在单表或单库中，造成查询等操作的耗时过长。比如，存储订单数据时使用三个mysql库（编号0,1,2），当一条订单数据过来时，对订单id求hash后与机器数量取模，hash(orderId) % 3，假如得到的结果是2，则这条数据会存储到编号为2的mysql中。分表分库存储时，根据数据库的主键或唯一键做hash，然后跟数据库机器的数量取模，从而决定该条数据放在哪个库中。



根据机器数量取模就会存在一个问题，当机器不够用需要扩容或机器宕机，机器的数量就会发生变化，造成数据的命中率下降，所以之前的数据就需要重新hash做一次sharding。这种操作会导致服务在一定的时间不可用，而且每次扩缩容都会存在这个问题。



一致性hash



一致性hash算法主要应用于分布式存储系统中，可以有效地解决分布式存储结构下普通余数Hash算法带来的伸缩性差的问题，可以保证在动态增加和删除节点的情况下尽量有多的请求命中原来的机器节点。



Hash环



一致性Hash算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性Hash算法是对2^ 32-1取模，什么意思呢简单来说，一致性Hash算法将整个Hash值控件组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1取模（即哈希值是一个32位无符号整型），整个哈希环如下：





整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^ 32-1，也就是说0点左侧的第一个点代表2^ 32-1， 0和2^ 32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环。



下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的主机名（考虑到ip变动，不要使用ip）作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中三个master节点的IP地址哈希后在环空间的位置如下：





下面将三条key-value数据也放到环上：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置。将数据从所在位置顺时针找第一台遇到的服务器节点，这个节点就是该key存储的服务器！



例如我们有a、b、c三个key，经过哈希计算后，在环空间上的位置如下：key-a存储在node1，key-b存储在node2，key-c存储在node3。





容错性和可扩展性



现假设Node 2不幸宕机，可以看到此时对象key-a和key-c不会受到影响，只有key-b被重定位到Node 3。一般的，在一致性Hash算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器，如下图中Node 2与Node 1之间的数据，图中受影响的是key-2）之间数据，其它不会受到影响。



同样的，如果集群中新增一个node 4，受影响的数据是node 1和node 4之间的数据，其他的数据是不受影响的。





综上所述，一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。



数据倾斜



一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题，例如系统中只有两台服务器，此时必然造成大量数据集中到Node 2上，而只有极少量会定位到Node 1上。其环分布如下：





为了解决数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node 1#1”、“Node 1#2”、“Node 1#3”、“Node 2#1”、“Node 2#2”、“Node 2#3”的哈希值，于是形成六个虚拟节点：





上图中虚拟节点node 1#1，node 1#2，node 1#3都属于真实节点node 1；虚拟节点node 2#1，node 2#2，node 2#3都属于真实节点node 2。



实际项目中使用



上来先说一个误区，Redis 集群没有使用一致性hash, 而是引入了哈希槽slots的概念。可以参考我的另一篇文章《redis系列之——高可用（主从、哨兵、集群）》。



我们说的一致性hash都不是缓存机器自身的功能，而是集群前置的代理或客户端实现的。而redis官方的集群是集群本身通过slots实现了数据分片。



redis集群时3.0版本才出现的，出现的比较晚，在集群模式出现之前，很多公司都做了自己的redis集群了。这些自研的redis集群的实现方式有多种，比如在redis的jedis客户端jar包就是实现了一致性hash算法（客户端模式），或者在redis集群前面加上一层前置代理如Twemproxy也实现了hash一致性算法（代理模式）。Twemproxy，是 Twitter 开源出来的 Redis 和 Memcached 代理，使用这种代理模式搭建的集群，我们的客户端连接只需要连接代理服务器即可，不用连接代理后面具体的redis机器。Twemproxy具体使用哪一种hash算法也是可以通过配置文件指定的。



完成，收工！





【传播知识，共享价值】，感谢小伙伴们的关注和支持，我是【诸葛小猿】，一个彷徨中奋斗的互联网民工！！！