分布式寻址算法

• hash 算法（大量缓存重建）
• 一致性 hash 算法（自动缓存迁移）+ 虚拟节点（自动负载均衡） 
• redis cluster 的 hash slot 算法

hash 算法

来了一个 key，首先计算 hash 值，然后对节点数取模。然后打在不同的 master 节点上。一旦某一个 master 节点宕机，所有请求过来，都会基于最新的剩余 master 节点数去取模，尝试去取数据。这会导致大部分的请求过来，全部无法拿到有效的缓存，导致大量的流量涌入数据库。

一致性 hash 算法

一致性 hash 算法将整个 hash 值空间组织成一个虚拟的圆环，整个空间按顺时针方向组织，下一步将各个 master 节点（使用服务器的 ip 或主机名）进行 hash。这样就能确定每个节点在其哈希环上的位置。

来了一个 key，首先计算 hash 值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，遇到的第一个 master 节点就是 key 所在位置。

在一致性哈希算法中，如果一个节点挂了，受影响的数据仅仅是此节点到环空间前一个节点（沿着逆时针方向行走遇到的第一个节点）之间的数据，其它不受影响。增加一个节点也同理。

燃鹅，一致性哈希算法在节点太少时，容易因为节点分布不均匀而造成缓存热点的问题。为了解决这种热点问题，一致性 hash 算法引入了虚拟节点机制，即对每一个节点计算多个 hash，每个计算结果位置都放置一个虚拟节点。这样就实现了数据的均匀分布，负载均衡。

redis cluster 的 hash slot 算法

redis cluster 有固定的 16384 个 hash slot，对每个 key 计算 CRC16 值，然后对 16384 取模，可以获取 key 对应的 hash slot。

HASH_SLOT=CRC16(key) mod 16384

redis cluster 中每个 master 都会持有部分 slot，比如有 3 个 master，那么可能每个 master 持有 5000 多个 hash slot。hash slot 让 node 的增加和移除很简单，增加一个 master，就将其他 master 的 hash slot 移动部分过去，减少一个 master，就将它的 hash slot 移动到其他 master 上去。移动 hash slot 的成本是非常低的。客户端的 api，可以对指定的数据，让他们走同一个 hash slot，通过 hash tag 来实现。

任何一台机器宕机，另外两个节点，不影响的。因为 key 找的是 hash slot，不是机器。

备注：

 主从模式下的rediscluster 集群 Redis 并不能保证数据的强一致性.

 第一个原因是因为集群是用了异步复制。主节点对从节点命令的复制工作发生在返回客户端命令回复之后。

 第二个原因是 Redis 集群出现了网络分区， 并且一个客户端与至少包括一个主节点在内的少数实例被孤立。

————————————————————————————————————————————————————————————————————————

Redis 集群通过分区来提供一定程度的可用性,在实际环境中当某个节点宕机或者不可达的情况下继续处理命令. Redis 集群的优势:

• 自动分割数据到不同的节点上。
• 整个集群的部分节点失败或者不可达的情况下能够继续处理命令。

分片技术的矛盾之处：

即要求key尽可能地分散到不同机器，又要求某些相关联的key分配到相同机器。

所以引入 hash tag 机制

　　　　HashTag机制可以影响key被分配到的slot，从而可以使用那些被限制在slot中操作。

　　　　HashTag即是用{}包裹key的一个子串，如{user:}1, {user:}2。

　　　　在设置了HashTag的情况下，集群会根据HashTag决定key分配到的slot， 两个key拥有相同的HashTag:{user:}, 它们会被分配到同一个slot，允许我们使用MGET命令。

　　　　通常情况下，HashTag不支持嵌套，即将第一个{和第一个}中间的内容作为HashTag。若花括号中不包含任何内容则会对整个key进行散列，如{}user:。

　　　　HashTag可能会使过多的key分配到同一个slot中，造成数据倾斜影响系统的吞吐量，务必谨慎使用。