Redis是一种开源的、基于内存的、支持多种数据结构的键值数据库，它具有高速、灵活、可扩展和持久化等特点，被广泛应用于缓存、消息队列、排行榜等场景。但是，当数据量增大或者访问压力增高时，单个Redis实例可能无法满足需求，这时就需要使用Redis集群来提升系统的可用性和性能。
Redis集群是一种分布式的数据存储方案，它由多个Redis节点组成，每个节点可以存储一部分数据，并且可以与其他节点通信。Redis集群的核心特性之一就是分片（sharding），即将数据按照一定的规则分散到不同的节点上，从而实现水平扩展和负载均衡。
分片算法
Redis集群使用了一种叫做CRC16的哈希函数来计算每个键的哈希值，然后对16384取模，得到一个0到16383之间的整数，这个整数就是键所属的分片ID。Redis集群将16384个分片ID平均分配给所有的节点，每个节点负责一部分分片ID，也就是一部分数据。当客户端要访问某个键时，它会先计算出该键的分片ID，然后找到对应的节点，再发送命令给该节点执行。
例如，假设有一个键叫做user:1，它的哈希值是12539，对16384取模后得到12539，这就是它的分片ID。假设有6个节点，每个节点负责2730个分片ID（16384/6=2730），那么user:1就属于第5个节点（12539/2730=4.59），客户端就会将命令发送给第5个节点。
数据迁移
Redis集群支持动态地添加或删除节点，以适应数据量和访问压力的变化。当添加或删除节点时，Redis集群会自动地重新分配分片ID，使得每个节点负责大致相同数量的分片ID。这个过程叫做数据迁移（data migration），它涉及到两种角色：源节点（source node）和目标节点（target node）。源节点是要放弃一部分分片ID的节点，目标节点是要接收这些分片ID的节点。
数据迁移的流程如下：
1. 源节点将要迁移的分片ID标记为迁移状态（migrating state），并将目标节点的信息记录在一个哈希表中。
2. 源节点向目标节点发送一个请求，告诉它要迁移哪些分片ID，并将这些分片ID标记为导入状态（importing state）。
3. 目标节点接受请求后，开始向源节点发送请求，获取每个分片ID下的所有键值对，并将它们保存在本地。
4. 源节点在接收到请求后，会检查该键是否属于迁移状态的分片ID，如果是，则返回该键值对，并将该键从本地删除，如果不是，则返回一个错误。
5. 目标节点在接收到所有的键值对后，会将导入状态的分片ID改为正常状态（normal state），并向集群广播自己已经接收了这些分片ID。