Redis Cluster data sharding

Redis Cluster 不使用一个固定的hash 算法，它通过把每个键分配给一个 **hash slot**，来做 sharding。

在 Redis Cluster 中共有 16384 个 hash slots，并使用如下算法确定 key 属于哪个 hash slots。

Redis Cluster 中的每一个节点负责存储 hash slots 的一个子集。例如，如果你的集群中有3个节点：

• 节点 A 包含 0-5500 号 hash slots
• 节点 B 包含 5501-11000 号 hash slots
• 节点 C 包含 11001-16383 号 hash slots

通过这种方式，也可以很方便的添加或者删除节点。比如，如果想添加一个节点 D，则只需要从节点 A、B、C 中分别移除一定数量的 hash slots 到 D 中即可。

优势：

1. 不需要重新 hash 所有的 key；
2. 添加或删除节点不会影响正常的功能；

3. 可以通过 _hash tags_的方式，这是一种将多个 key 分配给一个 hash slots的功能；

   1. 比如，事务或者Lua 脚本涉及多个key时，要求这些 key 在一个 hash slot 中
   2. set 类型的交集、并集等操作也涉及多个 key
   3. hash tags 此处不进行介绍，请查阅 https://redis.io/topics/cluster-spec
   4. 实现方式：仅对 **{}**内部的 **string** 进行 **crc16** 操作。即，如果有两个**key**，**{user1000}:xxx**、**{user1000}:qqq**，则定位 **hash slot** 时，只使用 **user1000** 这个**string**。

      客户端如何知道 hash slot 分布

4. 第一次启动时，Redis Client 从集群中拉取当前 hash slot 与节点的映射关系；

5. 当集群中的 hash slot 发生变化时（添加或删除新节点）；
   1. Redis client 发送一个查询请求给集群中hash slot对应的节点；
   2. 节点判断这个请求是否应该自己处理（查找hash slot是否属于自己）；
   3. 如果不该自己处理，则告诉客户端该 hash slot 应该请求哪个节点；
   4. 节点记录（更新）hash slot 和 node 的对应关系，并去对应节点执行对应请求。

当发生查询 miss 时，也可以再次从集群拉取最新信息。

实际上会复杂很多，在集群添加节点时，**hash slot** 调整过程中需要请求之前的节点。只有等到整个 **hash slot**全部迁移完成后，才可以访问新的节点。

Performance

在 Redis Cluster 中，如果一个 key 的请求发送到了一个节点，但是这个节点不负责处理该 key（hash slot 不属于这个node），则该节点不代理该请求的处理，而是返回客户端应该请求的节点。然后客户端就可以缓存这个结果，后续请求都直接到目标节点进行。

因为使用了异步 replication，即 master 不会等待其他节点写入完成。对于 multi-key 的指令的操作也限制在需要在同一个 hash slot 内。

所以，在 **Redis Cluster** 中的操作和 **single Redis instance** 的性能是差不多的。也就是说不管集群中有多少个节点，Redis 的性能不会有任何下降（a single round trip），而且，集群中存储的数据量是线性增长的（Scalibility）。

Very high performance and scalability while preserving weak but reasonable forms of data safety and availability is the main goal of Redis Cluster.

Redis Cluster master-slave model

其中，

• A、B、C 为 master，A1、B1、C1 为 slave。
• 每一个箭头表示一个 TCP 连接，一般使用 16379 端口。（省略了很多箭头，每个节点都会和其他节点建立一个 TCP 连接）。
  • nodes use a gossip protocol and a configuration update mechanism in order to avoid exchanging too many messages between nodes during normal conditions, so the number of messages exchanged is not exponential.

    Redis Cluster consistency guarantees

    不担保强一致性。也就是说，在异常情况下，即使 redis 集群返回了 OK，此数据也可能会丢失：

同步数据过程如下：

1. Your client writes to the master B.
2. The master B replies OK to your client.
3. The master B propagates the write to its slaves B1, B2 and B3.

因为 B 传播给 slave 是异步的，所以在 B 返回 client OK 后，如果马上宕机，则可能会造成丢失。

Redis 是一个高性能的 kv 数据库，如果等待数据复制成功后在返回，则可能会有很高的延迟。

上述的过程和 sync 数据到 disk 的过程也是类似的。你必须在性能和一致性中做一个权衡。

网络分区

如上图，其中 A、B、C 为 master，A1、B1、C1 为 slave，还有一个 client Z1。此时发生了网络分区。

图中省略了较多网络连接的箭头。

此时，C 对于 Z1 的操作任然可以继续正常响应。如果网络分区在短时间内恢复了，则不会造成影响。然而如果长时间不恢复，则 C1 会自动升级成 master，这就意味着 Z1 写到 C 中的数据丢失了。

在 Redis Cluster 中有一个 node timeout 的配置，在节点超时后，主节点就会被其任意一个 slave 代替。类似地，如果在超时后，主节点无法感知到大多数其他主节点，则它就进入错误状态并停止接受写操作。

更多内容

计算 hash slot 代码

def HASH_SLOT(key)
    s = key.index "{"
    if s
        e = key.index "}",s+1
        if e && e != s+1
            key = key[s+1..e-1]
        end
    end
    crc16(key) % 16384
end

参考

https://redis.io/topics/cluster-spec
https://redis.io/topics/cluster-tutorial