Redis Cluster 是redis官方推出的集群方案，借助分布式提升了单个redis服务的内存（存更多数据）和吞吐量（容纳更高的qps）

• 高性能：没有使用代理、主从采用异步复制
• 可扩展性：集群节点数量小于1000时具备线性扩展性；如果节点数过多，节点通信成本将影响性能
• 最大限度的写入安全：小部分情况下，客户端已经确认的写入会丢失
• 高可用：在主节点发生故障时会自动进行主从备份&&网络分区的情况下仍然能够工作

Redis Cluster is a distributed implementation of Redis with the following goals in order of importance in the design:

• High performance and linear scalability up to 1000 nodes. There are no proxies, asynchronous replication is used, and no merge operations are performed on values.
• Acceptable degree of write safety: the system tries (in a best-effort way) to retain all the writes originating from clients connected with the majority of the master nodes. Usually there are small windows where acknowledged writes can be lost. Windows to lose acknowledged writes are larger when clients are in a minority partition.
• Availability: Redis Cluster is able to survive partitions where the majority of the master nodes are reachable and there is at least one reachable replica for every master node that is no longer reachable. Moreover using replicas migration, masters no longer replicated by any replica will receive one from a master which is covered by multiple replicas.

数据分布

分布式数据库把数据集划分到多个节点上，每个节点负责整体数据的一个子集。

首先要解决的是这两个问题：

• sharding：按照某个确定的规则将数据映射到节点
• resharding：当节点的数量发生改变时，需要重新映射，涉及到数据迁移问题

集群方案

redis-cluster 是redis3.0（2015年）才推出的，在此之前有一些其他分布式方案，它们也解决了sharding 和 resharding的问题：

• 客户端分区：通过Redis客户端预先定义好的路由规则，把对Key的访问转发到不同的Redis实例中，查询数据时把返回结果汇集。如jedis就是在客户端实现了一致性hash算法。

  • redis实例数变化时由于数据和节点的映射关系会变化，需要手动迁移数据，并重启客户端

• 代理分区：redis集群前面加上一层前置代理；如Twemproxy、predixy、codis

  • 本质就是把客户端分片的逻辑统一放到了Proxy层
  • 这些代理还会额外提供很多好用的功能，如codis提供了一个web界面，数据迁移过程也只需要在网页上就能完成；并且codis可以部署多个proxy来实现高可用（引入zookeeper保证一致性）
  • 增减redis实例时对client完全透明、不需要重启服务
  • 对外就像一个普通的redis单实例，客户端实现简单

• 服务端分区：redis-cluster 是基于smart client和无中心的设计，在服务端实现分区

  • proxy 多一次网络请求，有一定性能损耗

  • 自带数据迁移功能和丰富的集群管理功能

  • 高可用，且自带故障转移（使用proxy方案，为了保证redis实例的可用性还得部署哨兵模式）

  • client实现复杂，需要缓存slot mapping；proxy对外暴露的就像一个简单的redis单实例

  • 节点数量多时，节点检测（gossip）会占用带宽和资源

  Gossip 的消息通信量是节点数的平方，随着集群节点数的增加，Gossip 通信的消息量会急剧膨胀。比如，我们实测对于一个 900 节点的集群，Gossip 消息的 CPU 消耗会高达 12%，远高于小集群的 Gossip 资源消耗，这样会造成极大的资源浪费。

  除了资源的浪费以外，Gossip 消息过多也会抢占用户请求处理线程的资源，进而会导致用户请求经常被 Gossip 消息的处理所阻塞，再导致用户请求产生更多的超时，影响服务可用性。

哈希算法

简单的实现：

• 对节点数量进行取模运算，比如key为7，有3个节点，则数据存在节点1上面
• 存在的问题：如果节点数量发生了变化，也就是在对系统做扩容或者缩容时，必须迁移改变了映射关系的数据，否则会出现查询不到数据的问题。这个其实和内存里的map也是一样的，扩容需要重新算一遍哈希值。分布式系统中数据在节点间迁移的成本更高

一致性哈希：

普通的哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2的32次 进行取模运算。

• 每个节点对应一个哈希值
• 在存取数据时，计算出一个哈希值，往顺时针的方向的找到第一个节点，就是存储该数据的节点。

这种做法是为了减少节点数量变化时迁移的成本；当增加/减少节点时，只会影响相邻的一个节点

缺陷：节点数量较少时，很容易在哈希计算后分布不均衡，导致不同节点存储的数据数量不均衡；在一致性哈希算法中，每个节点的哈希值通常是通过对节点标识（例如节点的IP地址和端口号等）进行哈希计算得到的，具有随机性

哈希槽（虚拟槽）：

1. 每个key属于一个槽，对key使用crc16算法，再对16384取模
2. 每个节点维护一部分槽，节点：虚拟槽 = 1：N；虚拟槽：key = 1：N

codis 和 redis-cluster 都使用了哈希槽算法，并且它们都有方便的数据迁移手段，当扩容时，可以指定将哪些槽分配给新节点

节点通信

redis 是去中心化的集群，节点之间通过P2P的Gossip协议不断地通信，用于故障转移、同步元数据

元数据主要为：

1. 节点和槽的映射关系
2. 节点的故障状态

通信过程：

1. 每个节点有一个专门负责通信的总线端口（一般默认是端口+10000）
2. 每个节点在固定周期内通过特定规则选择几个节点发送ping消息，每个节点本地会缓存它所知的所有节点情况，ping消息包含其中一部分节点的信息
3. 接收到ping消息的节点用pong消息作为响应

消息结构

常见的消息分为：

• meet：新节点通过三次握手加入集群（meet是集群中的节点向新节点发的）

• ping：集群内每个节点每秒向多个其他节点发送ping消息，用于检测节点是否在线和交换彼此状态信息（同步元数据）。ping消息封装了自身节点和部分已知其他节点的状态数据。

• pong：当接收到ping、meet消息时，作为响应消息回复给发送方确认消息正常通信。节点也可以向集群内广播自身的pong消息来通知整个集群对自身状态进行更新。

• fail消息：当节点判定集群内另一个节点下线时，会向集群内广播一个fail消息，其他节点接收到fail消息之后将其更新为下线状态

所有消息都用如下结构声明：

typedef struct { 
	char sig[4]; /* 信号标示 */ 
	uint32_t totlen; /* 消息总长度 */ 
	uint16_t ver; /* 协议版本*/ 
	uint16_t type; /* 消息类型,用于区分meet,ping,pong等消息 */ 
	uint16_t count; /* 消息体包含的节点数量，仅用于meet,ping,ping消息类型*/ 
	uint64_t currentEpoch; /* 当前发送节点的配置纪元 */ 
	uint64_t configEpoch; /* 主节点/从节点的主节点配置纪元 */ 
	uint64_t offset; /* 复制偏移量 */ 
	char sender[CLUSTER_NAMELEN]; /* 发送节点的nodeId */ 
	unsigned char myslots[CLUSTER_SLOTS/8]; /* 发送节点负责的槽信息，bitmap，2kb */ 
	char slaveof[CLUSTER_NAMELEN]; /* 如果发送节点是从节点，记录对应主节点的nodeId */ 
	uint16_t port; /* 端口号 */ 
	uint16_t flags; /* 发送节点标识,区分主从角色，是否下线等 */ 
	unsigned char state; /* 发送节点所处的集群状态 */ 
	unsigned char mflags[3]; /* 消息标识 */ 
	union clusterMsgData data /* 消息正文 */; 
} clusterMsg;


union clusterMsgData { 
	/* ping,meet,pong消息体*/ 
	struct { 
		/* gossip消息结构数组 */ 
		clusterMsgDataGossip gossip[1];
  } ping; 
  /* fail 消息体 */ 
  struct { 
  	clusterMsgDataFail about; 
  } fail; 
  // ... 
};

myslots[CLUSTER_SLOTS/8]是消息头中主要占用空间的字段，表明自身负责的槽信息，固定占用2KB

Gossip

思想：

每个节点可能知道全部节点，也可能仅知道部分节点，只要这些节点彼此可以正常通信，最终它们会达到一致的状态。当节点出故障、新节点加入、主从角色变化、槽信息变更等事件发生时，通过不断的ping/pong消息通信，经过一段时间后所有的节点都会知道整个集群全部节点的最新状态，从而达到集群状态同步的目的。

节点的选择：

虽然Gossip协议的信息交换机制具有天然的分布式特性，但它是有成本的。由于内部需要频繁地进行节点信息交换，而ping/pong消息会携带当前节点和部分其他节点的状态数据，势必会加重带宽和计算的负担。Redis集群内节点通信采用固定频率（定时任务每秒执行10次）。因此节点每次选择需要通信的节点列表变得非常重要。通信节点选择过多虽然可以做到信息及时交换但成本过高。节点选择过少会降低集群内所有节点彼此信息交换频率，从而影响故障判定、新节点发现等需求的速度。

客户端

Redis集群对客户端通信协议做了比较大的修改，为了追求性能最大化，并没有采用代理的方式而是采用客户端直连节点的方式。

key 的路由是客户端和redis-cluster共同完成的

• 请求重定向：Redis实例接收任何键相关命令时首先计算键对应的槽，再根据槽找出所对应的节点，如果节点是自身，则处理键命令；否则回复MOVED重定向错误，通知客户端请求正确的节点。

  

• ask重定向：Redis集群支持在线数据迁移，当slot对应的数据从源节点到目标节点迁移过程中，客户端需要做到智能识别，保证键命令可正常执行。例如当一个slot数据从源节点迁移到目标节点时，期间可能出现一部分数据在源节点，而另一部分在目标节点

  1. 还没迁移的key命令都会在源节点执行

  2. 已经迁移的key、新的key命令都在目标节点执行；源节点会回复ASK重定向异常，并包含目标节点的信息

  3. 客户端从ASK重定向异常提取出目标节点信息，发送asking命令到目标节点打开客户端连接标识，再执行键命令。

     数据迁移没完成，新节点是不会对外提供服务的，而ASKING命令唯一做的事就是打开发送该命令的客户端的redis_asking标识，然后再携带着这个标识访问目标节点中关于槽i的命令，如果该节点正在导入槽i，那么该节点将会破例执行这个命令一次，之后则会拒绝执行这个命令。

  4. 为了保证一致性，数据从源节点迁移到新节点这个动作是原子性的，且会阻塞住这两个节点

  Atomically transfer a key from a source Redis instance to a destination Redis instance. On success the key is deleted from the original instance and is guaranteed to exist in the target instance.

  The command is atomic and blocks the two instances for the time required to transfer the key, at any given time the key will appear to exist in a given instance or in the other instance, unless a timeout error occurs.

Golang客户端：

翻了下Golang客户端的实现，就是遵照着上面的协议来的

type ClusterClient struct {
	opt           *ClusterOptions   // 一些选项，初始化的参数
	nodes         *clusterNodes     // 客户端设置的一些节点，loadState时访问这些nodes
	state         *clusterStateHolder  // 维护集群状态信息的holder
	cmdsInfoCache *cmdsInfoCache
	cmdable 
	hooksMixin
}

Incr命令，实际就是New了一个cmd，client.Incr 实际会调用ClusterClient里的cmdable方法

func (c cmdable) Incr(ctx context.Context, key string) *IntCmd {
	cmd := NewIntCmd(ctx, "incr", key)
	_ = c(ctx, cmd)
	return cmd
}

实际执行命令的函数：github.com/redis/go-redis/v9@v9.0.5/cluster.go:903

func (c *ClusterClient) process(ctx context.Context, cmd Cmder) error {
	cmdInfo := c.cmdInfo(ctx, cmd.Name())
  // 计算key对应的slot  crc16sum(key)%16384
	slot := c.cmdSlot(ctx, cmd)
	var node *clusterNode
	var ask bool
	var lastErr error
	for attempt := 0; attempt <= c.opt.MaxRedirects; attempt++ {
		// ...
		if node == nil {
			var err error
      // 获取槽位对应的节点
			node, err = c.cmdNode(ctx, cmdInfo, slot)
			if err != nil {
				return err
			}
		}

		if ask {
			ask = false
			pipe := node.Client.Pipeline()
			_ = pipe.Process(ctx, NewCmd(ctx, "asking"))
			_ = pipe.Process(ctx, cmd)
			_, lastErr = pipe.Exec(ctx)
		} else {
      // 实际执行
			lastErr = node.Client.Process(ctx, cmd)
		}
		if lastErr == nil {
			return nil
		}

    // ...
		var moved bool
		var addr string
		moved, ask, addr = isMovedError(lastErr)
		if moved || ask {
      // 重新获取集群信息（cluster nodes命令）
			c.state.LazyReload()

			var err error
			node, err = c.nodes.GetOrCreate(addr)
			if err != nil {
				return err
			}
			continue
		}

    // ...
		return lastErr
	}
	return lastErr
}

故障转移

Redis集群自身实现了高可用，当集群内少量节点出现故障时通过自动故障转移保证集群可以正常对外提供服务

官方推荐至少三主三从来搭建redis集群

故障发现：

通过消息传播机制发现

• 主观下线：指某个节点认为另一个节点不可用，即下线状态，这个状态并不是最终的故障判定，只能代表一个节点的意见。
• 客观下线：指标记一个节点真正的下线，集群内多个节点都认为该节点不可用，从而达成共识的结果。

集群中每个节点都会定期向其他节点发送ping消息，接收节点回复pong消息作为响应。如果在cluster-node-timeout时间内通信一直失败，则发送节点会认为接收节点存在故障，把接收节点标记为主观下线（pfail）状态。

当某个节点判断另一个节点主观下线后，相应的节点状态会跟随消息在集群内传播。当某个节点从接收到的消息里解析出已经有半数节点认为某个节点是不可用的，就会尝试触发客观下线逻辑（广播fail消息）

故障恢复：

如果下线节点是主节点，需要从它的从节点中找出一个替换它

选举逻辑：

1. 每个从节点都要检查最后与主节点断线时间，判断是否有资格替换故障的主节点。如果从节点与主节点断线时间超过cluster-node-time*cluster-slave-validity-factor，则当前从节点不具备故障转移资格。参数cluster-slave-validity-factor用于从节点的有效因子，默认为10。
2. 从节点根据自身复制偏移量设置延迟选举时间，如复制偏移量最大的节点slave b-1延迟1秒执行，保证复制延迟低的从节点优先发起选举。
3. 投票权是主节点的（因为从节点的数量不一定很多），当从节点收集到N/2+1个持有槽的主节点投票时，从节点可以执行替换主节点操作，例如集群内有5个持有槽的主节点，主节点b故障后还有4个，当其中一个从节点收集到3张投票时代表获得了足够的选票可以进行替换主节点操作
4. 替换主节点：
   • 取消主从复制
   • 接管主节点的槽位
   • 向集群广播自己成为了主节点

redis的故障恢复时间取决于cluster-node-timeout的值

一些注意点

主从可以读写分离吗？

取决于客户端，go-redis是支持读从节点的；

func (c *ClusterClient) cmdNode(
	ctx context.Context,
	cmdInfo *CommandInfo,
	slot int,
) (*clusterNode, error) {
	state, err := c.state.Get(ctx)
	if err != nil {
		return nil, err
	}

	if c.opt.ReadOnly && cmdInfo != nil && cmdInfo.ReadOnly {
		return c.slotReadOnlyNode(state, slot)
	}
	return state.slotMasterNode(slot)
}

type ClusterOptions struct {
	// Enables read-only commands on slave nodes.
	ReadOnly bool
	// Allows routing read-only commands to the closest master or slave node.
	// It automatically enables ReadOnly.
	RouteByLatency bool
	// Allows routing read-only commands to the random master or slave node.
	// It automatically enables ReadOnly.
	RouteRandomly bool
}

RouteByLatency：会选择latency最小的一个节点

RouteRandomly：会随机选一个

默认：优先slave，再master

Pipeline相关：

在 Redis Cluster 中，PIPELINE 操作无法保证顺序性，因为它涉及的多个键可能分布在不同的节点上。

pipeline在实现就是客户端对请求做了个拆分，相关逻辑位置：/Users/mima123456/go/pkg/mod/github.com/redis/go-redis/v9@v9.0.5/cluster.go:1206

	if err := c.mapCmdsByNode(ctx, cmdsMap, cmds); err != nil {
		setCmdsErr(cmds, err)
		return err
	}
	
	for attempt := 0; attempt <= c.opt.MaxRedirects; attempt++ {
    // ...
		for node, cmds := range cmdsMap.m {
			wg.Add(1)
			go func(node *clusterNode, cmds []Cmder) {
				defer wg.Done()
				c.processPipelineNode(ctx, node, cmds, failedCmds)
			}(node, cmds)
		}
    // ...
  }

同一个节点上的操作还是顺序执行的

mset/mget相关：

只支持在同个哈希槽进行批量操作，否则会报错：(error) CROSSSLOT Keys in request don't hash to the same slot

解决方案：自己用hashtag的方式来保证key在创建的时候位于同一个slot

如mset {test}a 1 {test}b 2，只有{}内的内容会被用来hash

codis是支持mget/mset的，实现类似于pipeline，是客户端对请求进行拆分发到不同的redis实例上

丢失写入的场景：

1. 异步复制的过程中，master宕机；slave可能不具备master的所有数据导致数据丢失

2. 网络分区：客户端和一个master在小分区，此时仍然能写入（只有cluster-node-timeout窗口内，因为随后master发现自己在小分区会禁止写入）；大分区的slave会成为master，写入就丢失了

官方建议节点数量保证奇数个（奇数个主节点，每个主节点两个从节点），这样的话在网络分区的情况下就最多只存在一个大分区，其它都是小分区；（如果是偶数个就会出现两个大分区）

如果有两个大分区，那它们在网络分区恢复前都可以写入数据，如果有相同的key那其中一个就会丢失