主要特性和设计原理 Redis 集群目标 Redis 集群是 Redis 集群中的一种分布式实现，它有以下目标（按照重要性进行排序）： 高性能 ，可以线性扩展至 1000 个节点；没有代理，使用异步复制，在 values 上面没有合并操作。 可接受范围内的写安全 ：系统尽最大努
主要特性和设计原理
Redis集群目标
Redis集群是Redis集群中的一种分布式实现，它有以下目标（按照重要性进行排序）：
- 高性能，可以线性扩展至1000个节点；没有代理，使用异步复制，在values上面没有合并操作。
- 可接受范围内的写安全：系统尽最大努力执行从客户端（和绝大多数master节点连接）发过来的所有写操作。在极端情况下，可能会有一小部分确认写会发生丢失。如果客户端只是连接了少数节点（ are in a minority partition），丢失的确认写数目会更多。
- 可用性：当每个挂掉的master都至少有一个可达的slave，并且绝大多数master节点都是正常的时候，Redis集群还可以正常运行。通过副本迁移（replicas migration,），没有slave的master会从另外一个master（它有多个slave）得到一个slave。
实现的功能子集
- Redis集群实现了所有非分布式Redis版本中对单个key操作的命令。哪些对多个key进行操作的命令（比如：set的union或intersection等），如果这些key都在一个节点上，那么Redis集群也是支持的。
- Redis集群实现一个hash tags的概念，它主要用于将某些key存放在同一个节点上面；但是在手动reshading的时候，多个key的操作命令，在一段时间内可能会无法使用，不过单个key的操作还是可以正常使用的。
- Redis集群不支持多个数据库的概念，也就是说只有数据库0（SELECT命令无效）。
在Cluster集群中，client和server的角色
- 在Redis当中，cluster节点负责持有数据（hoding the data），获取cluster的状态（包括：将key映射到对应节点上面）。cluster节点还能够自动发现其它节点，检测到失败节点，并能够在需要的时候将slave提升为master，以确保有错误发生的时候，集群还能够继续工作。
- 为了执行任务，cluster的节点之间使用tcp进行连接，并使用私有的二进制协议进行信息传输（也称为：Redis Cluster Bus）。在Cluster Bus上，节点之间可以使用gossip协议对当前集群的信息进行泛洪传播，这样有利于发现新节点；可以发送ping包以确认其它节点都是正常工作的，也可以发送cluster messages来通知一种特殊事件的发生。Cluster Bus也用来在cluster节点间广播Pub/Sub消息，当有用户发送了主备切换的指令后，配合完成人工切换。
- 由于Cluster节点不能够代理请求，所有client也许会被重定向到其它节点上面（使用错误信息：MOVED或ASK）。理论上，client可以向集群中任何节点发送请求，期间可能获取到重定向请求，因此client不需要了解集群的状态。然而客户端可以缓存key和node的对应关系来提升性能。
写安全
- Redis集群的节点之间是异步复制的，上一次故障转移成功（last failover wins）隐含着数据合并的功能。这就意味着上次被选举的master的数据集最终会被所有其它副本所替换。在数据分片之间总是存在一个丢失写的时间窗口。然而这个时间窗口对于连接到少数master的客户端和连接到多数master的客户端是很不一样的。Redis集群对连接到多数master的client发送的写，比连接到少数master的client发送的写，提供更好的成功保障。下面是一些在错误发生的时候，导致多数分片丢失确认写的场景例子：
1、一个写到达master；master在本地写入成功后，返回了client成功消息；但是孩没有来得及将本次写发送给slave进行复制就挂掉了；如果master过了一段时间都还没来得及恢复（其它slave提升为master了），那么，这个写就永远丢失了。这种情况应该比较少出现，master在同时回复客户端和slave的时候挂掉了。但这种情况的确是可能存在的。
2、另外一种理论上可能出现写丢失的情况是：
- master因为一个分片变得不可访问
- 它被一个slave替换了
- 过了一段时间，master变得可以访问了
- 持有老的路由表的client可能会将数据写入到原来的master上面，直到它的路由表进行了更新。
第2种情况，一般不太可能发生；因为一个master如何在发生切换的这段时间内都无法和其它大多数master进行通信的时候，它是不会接受任何写操作的。当这个master的分片状态恢复写的时候，它也会预留一段不接受写的时间，以便通知其它节点配置发生变化了。而且这个问题发生还需要client的路由表也没有发生更新。
对某个分片的少部分master进行写操作有更大的写丢失窗口。比如：RedisCluster会丢失一定数目的只有少部分节点才完成的写操作；客户端发送的写操作，只有少数master进行了更新，而其它大多数节点都没有更新，在这个过程中如果大多数节点中有的节点发生了切换，那么这些写就可能被丢失。
总结：一个master挂了，条件是至少在NODE_TIMEOUT时间内它和绝大部分master都无法通信，所以从这个时候开始到分片修复这段时间，写不会丢失；当分片失败持续时间超过NODE_TIMEOUT，那么截至到这个时间点，在少部分node上执行的写也许会丢失；但是那些少部分的节点，如果经过了NODE_TIMEOUT后还无法连接大多数的master，那么它们会启动禁止写操作；所以，对于少部分节点变得不可达有一个最大的时间窗口（就是NODE_TIMEOUT）。经过了这个时间窗口之后，没有写会接受或丢失。
高可用性
- Redis Cluster在分片的少数节点上不可用。假定每一个不可用的少数节点都有一个slave，该分片的大多数节点都是可用的，那么在NODE_TIME加上几秒钟的切换时间之后（一般1，2秒钟），Redis Clusteri又会变得可用。
- 这就是说Redis Cluster的设计适用于集群中有部分节点失败的时候，还可以自动进行恢复。但是，它不适用于哪些要求在大多数节点都失败的情况下还能恢复集群的应用。
- 假设有N个Master的Redis集群，每个Master都有一个slave；如果有一个节点挂掉了，那么集群还是可用的；如果有两个节点挂掉了，那么可用性为：1-(1/(N*2-1)),因为两个节点挂掉了的时候，第一个节点挂掉之后还剩余节点：N*2-1个，而这个节点的slave也挂掉的可能性为：1/(N*2-1).
- 如果有5个节点（每个节点有一个slave），那么有1/（5*2-1）=11.1%的可能性，有2个节点挂掉之后，集群不可用了。
- 由于Redis Cluster有副本迁移（replica migration）的功能，在现实场景下，Redis Cluster的可靠性更高，因为Redis Cluster会自动将副本迁移到没有任何副本（slave）的master上面（orphanded masters）。因此，每一次从失败中恢复之后，集群会自动调整slave的部署，以便下次更好地从失败中恢复过来。
性能
- Redis Cluster节点不会将命令发送到负责这个key的真正节点上面，而是引导client到负责给定key所在key空间的正确节点上面。最终client可以获取到最新的集群结构，那个node负责哪些key，后续，client可以直接将key转发到对应节点上面。
- 由于使用了异步复制，节点不会等待其它节点的确认（如果没有使用WAIT命令的话）
- 多个key的命令只适用于“接近”的keys上面，所以除了resharding，数据不会在在节点间迁移
- 一般的操作都和单机上执行一样，所以性能一般是N*单机性能。同时一个查询一般就是一个RT，因为客户端一般都会维持和节点的连接，所以延迟也和单机Redis差不多。
- 高性能和高可靠性；以及在可接受范围内的数据安全和可靠性的前提下，提供很好的容错性；这些就是Redis Cluster的主要目标。
为什么要避免合并操作
- Redis Cluster的设计避免了相同key-value对在不同节点间的版本冲突，因为Redis数据模型不能够完全满足这个要求。在Redis中存储的数据量常常是很大的，同时数据类型一般都是比较复杂的。传输和合并各类数据值可能成为系统瓶颈，可能需要业务逻辑的参与，需要存储元数据的额外内存等等。
- 这里不是技术的问题，CRDTs或其他同步复制的机器可以有和Redis类似的复杂数据模型，但是它们的实际运行运行的情况和Redis Cluster不一样；Redis Cluster设计的目标是让Redis Cluster的使用和单机版本一样。
Redis Cluster主要组件概述
Keys分布模型
- key空间被分到16384个槽中，也就决定了Redis Cluster最多有16384个master节点（建议节点数目不要超过1000）。
- cluster中的每一个master处理16384个hash slot的子集。当集群没有进行重配置的时候（重配置的时候，槽会从一个节点移动另外一个节点），我们称集群处于stable状态。当集群处于stable的时候，一个hash slot只会被一个node负责处理（但是读可以通过slave进行扩充）。
- 通过下面的算法将key映射到对应slot（槽）中
HASH_SLOT =CRC16(key) mod 16384
- CRC16的算法过程如下：
- 名称：XMODEM（也称之为ZMODEM或CRC-16/ACORN）
- 宽度：16位
- Poly：1021（也就是x^16 + x^12 + x^5+1）
- 初始化：0000
- Reflect Input Type：False
- Reflect Output Type：False
- Xor constant to output CRC：0000
- Output for "123456789":31C3
Keys Hash tags
- 在hash slot计算中，有一个例外，它用来实现hash tags。Hash Tags是确保多个keys被分配到同一个hash槽中的方式。这个是为了在Redis Cluster上实现多个key的操作。
- 为了实现hash tags，一个key的hash slot计算稍稍有点不一样；如果一个key包含"{…..}"的样式，只有{和}之间的部分会用于计算hash slot。然而由于key中可能有多个{和}，算法使用下面规则：
- 如果key包含一个{字符
- 并且如果有一个}字符和{对应
- 并且在第一个{和之后第一个}之间有一个或多个字符
这个时候将使用第一个{和之后第一个}之间的字符用来计算hash slot。
比如：
- {user1000}.following和{user1000}.followers会hash到同一个槽上面，因为只有user1000用来计算hash值
- foo{}{bar},将使用所有字符串进行hash值计算，因为第一个{和}之间没有字符
- foo{{bar}}zap,{bar用来计算hash
- foo{bar}{zap},只有bar用于计算hash
- 这个算法中有一个很有用的地方是，如果key以{}开头，那么整个key都会用来计算hash
Cluster节点属性
- Cluster中的每一个节点都有唯一的名字。节点名字是一个160位的16机制字符串，在节点第一次启动时候生成（一般使用/dev/urandom生成)。节点将会把这个名字保存在文件当中，以后都为使用这个名字保持不变（只要管理员没有删除这个文件或没有通过CLUSTER RESET命令发送的hand reset请求到来）。
- node ID是用来标识集群中每个节点的，给某个节点只改动ip，而不改动node id是可以得。