WLock为⽤户提供了秘钥作为集群分配、锁操作、隔离、权限控制的租户单位。为了保证数据的强一致性与服务吞吐能力，每个节点采用多Paxos分组并行向所有副本同步锁状态数据。业务接入前，首先会创建秘钥，并为秘钥分配可用的服务集群（通常包含5个节点）。在生产环境，如果为每个接入的业务独立部署集群，随着接入量的增多，存在管理不便以及资源浪费的问题。所以WLock采用的是多租户共用一个集群的部署方式，但这种方式必须要解决多个秘钥的租户因调用量参差不同而相互影响的问题。

WLock最初在设计时，考虑了以下两种秘钥隔离方案：

1. 为每个秘钥分配独立的Paxos分组
   该方式可以在一定程度上隔离不同秘钥的锁请求，但多个Paxos分组运行在相同的服务节点上，还是会抢占进程和系统内的共享资源。随着服务节点下秘钥分配数量的增多，单Paxos分组的最大处理能力也会随之下降，单秘钥下的锁请求最大并发受限于单Paxos分组的处理能力。

2. 秘钥请求散列在所有Paxos分组 + 分布式限速
   该方式不限制单个秘钥与某个Paxos分组绑定，秘钥下锁请求可散列在集群下所有的Paxos分组中，根据压测结果确定单集群最大并发处理能力，提前做好集群的容量规划，业务按照预测访问量来申请秘钥最大调用量，在WLock集群总访问量超过阈值时（默认最大吞吐量的50%），直接抛弃掉超速的秘钥锁请求来实现服务端的过载保护，同时避免了某秘钥未知调用量增长对其它秘钥调用产生影响。

最终，我们采用了第二种方案进行秘钥隔离。但是，当某个秘钥的调用量随着业务扩展正常增长，集群剩余可分配的调用量无法满足该秘钥调用增长量，如何在保证业务的锁请求不失败的前提下，继续提⾼单个秘钥的最大调用量？首先想到的解决方案是提升服务本身的处理能力，对集群进行动态扩容，下面分析下是否可行。

集群扩容，顾名思义，通过增加集群内的节点来提高集群的处理能力，但由于WLock每个锁状态更新请求都需要执行Paxos Propose同步过程来保证多副本数据一致性，Propose 能够执行成功的条件之一就是需要有过半的节点同意该请求，在这个条件下，直接扩充节点，如图1所示，从3个节点扩充到5个节点，原本一次 Propose 只需要2个节点(包括自己)应答就可以，现在变成了3个节点应答才能通过，因为受更多节点响应速度影响，Propose同步数据过程更容易出现抖动。所以扩充节点只能提升集群的容灾能力，并不能提升服务并发处理能力。

集群扩容的方案由于增加了单次Propose的应答节点数量，并不能解决秘钥并发过高的问题。那么如果能够在不增加单次Propose应答节点数量的前提下，进行集群扩容，是不是就可以提高秘钥的并发能力了？

目前秘钥和分组的关系如图2所示，从图中可以看出，每个物理节点包含了多个Paxos分组，每个秘钥会将请求分别发送到多个分组的Master节点，多个Paxos分组之间互相制约，限制了彼此能够处理的请求量。如何能够做到在不增加每个分组节点数量的同时增加总节点数量？如果分组总数量是固定的，那么将每个物理节点承载的分组数量减少一部分，将其分摊到其他节点，是不是就达到了扩充节点并且不增加Propose应答量的目的。

集群拆分方案虽然能够提升单分组的并发处理能力，但依然无法安全隔离单分组下流量突发增高的秘钥调用，而且集群拆分后客户端会同时调用两个集群不便于秘钥的管理。下面我们继续深入思考下有没有更好的方式可以解决该问题。

既然要进行隔离，那么首先需要把想要隔离的秘钥从原Paxos分组中迁移出来，可以在节点启动时，创建一些不处理正常请求的冗余Paxos分组来实现，冗余分组与原分组存在一一对应关系。当某个秘钥并发过高的时候，将其迁移到冗余分组上，因为冗余分组和原分组是在同一个进程内，所以迁移操作较为容易，但是只迁移过去是不能解决问题的，因为冗余分组和正常分组在同一进程内，他们仍然占用相同的进程资源，这里就可以使用前面的集群拆分方案，将冗余分组和普通分组拆分开来，先对冗余分组进行扩缩容，将冗余分组节点变更为新的节点，再将新节点拆分为一个新的集群，达到秘钥隔离的目的。迁移过程如图4所示，下面再详细介绍下迁移实现细节。

4.1 正向迁移

4.1.1 正向迁移流程

秘钥从原分组迁移到冗余分组需要经过6个步骤，如图5所示：

初始化：秘钥开始迁移之前需要进行准备工作，初始化秘钥为迁移状态。

迁移准备：原分组的 Master节点记录需要迁移的秘钥、分组信息，并通过Propose同步该信息给分组内的其他节点。

迁移开始：原分组的 Master节点对于迁移秘钥进行锁操作转发，将锁操作由原分组转发给冗余分组，记录此时原分组的最大InstanceId，增加迁移次数，冗余分组会在处理第一个转发请求前将该数据同步给冗余分组的所有节点。

迁移安全状态：迁移开始5分钟之后可进入迁移安全状态（安全状态定义为：冗余分组Paxoslog中已经存储了迁移秘钥的所有锁全量变更记录，通过Paxoslog可以恢复锁最新状态。因为WLock限制了每次设置锁过期时间最长为5分钟，超过5分钟要么锁自动过期删除，要么进行续约，必然有一次锁更新操作记录）。进入迁移安全状态后会开启冗余分组的Master选举机制，并保证原分组的Master节点会优先成为冗余分组的Master节点。

客户端配置变更：客户端进行连接的重连，触发锁事件补偿，锁操作请求直接发送给冗余分组。

迁移结束：清除分组迁移数据，恢复迁移状态。

4.1.2 迁移的关键点

在进行秘钥迁移的过程中，由于迁移秘钥一直有锁请求，所以必须要保证整个迁移过程不影响业务的正常调用，下面我们来介绍几个关键实现。

Master节点一致

之所以需要保证Master节点一致，是因为WLock是由Master节点发起Propose进行请求处理的，如果原分组和冗余分组的Master节点不一致，就会导致原分组和冗余分组的处理节点不同，秘钥迁移时已经发送到原分组Master节点上的锁请求，还需要转发到冗余分组Master节点来处理，分组变更实现起来较为复杂。

因为冗余分组除了迁移流程外是不对外提供服务的，所以对于冗余分组不需要开启Master选举，可以在秘钥迁移过程进行到分组变更完成的时候再开启Master选举。另外，当冗余分组第一次开启Master选举时，为了保证原分组的Master节点和冗余分组的Master节点一致，会先调整原分组Master节点在冗余分组中抢占Master的时机与间隔，确保该节点优先成为冗余分组的Master。

锁操作一致性

在不影响业务正常调用的情况下，如何保证锁操作一致性是整个秘钥平滑迁移过程中最核心的实现，下面分别从存储一致性、如何保证锁版本递增、锁操作连续性三个方面介绍下实现细节。

1. 存储的一致性

因为WLock通过冗余分组来进行迁移秘钥和非迁移秘钥的隔离，对于迁移秘钥来说，它存在两种状态，分别是由原分组处理和由冗余分组处理，对于每一个锁变更请求来说，秘钥无论是由原分组处理，还是由冗余分组处理，锁操作都是必须连续的。也就是说，锁的数据存储必须保持一致。

WLock 的数据存储使用的是 RocksDB，每个Paxos分组对应独立的RocksDB存储实例，在此基础上，为了保证原分组和冗余分组的锁操作一致并连续，WLock 共用了原分组和冗余分组的存储实例，这样在秘钥的Paxos分组变更过程中，不需要提前进行数据迁移。对于新的锁请求，直接切换为冗余分组的Master发起Propose同步数据。流程如图6所示：

2. 锁版本递增

在介绍锁版本递增前，先来了解下，锁版本到底是什么？它解决了什么问题？这里考虑一个场景 : 当客户端获取到锁后发生GC pause或者服务端出现时钟回退，有可能锁持有者释放锁之前，锁就发生过期，此时如果另外一个客户端获取到锁，锁的互斥性会被破坏。WLock解决这个问题的方案是引入了一个 fencing token，当业务在访问共享资源时，需要携带并比较当前资源更新操作的锁最大fencing token（类似于乐观锁机制），再结合事务机制保证数据操作的一致性，而这个fencing token 就是锁的版本。

WLock 使用 InstanceId 作为锁的版本，InstanceId可以认为是 Paxos请求的唯一 Id，每一次请求都会有一个 InstanceId，并且对于一个分组来说，InstanceId 是单调递增的。在不涉及迁移的时候，该策略是没有问题的，但是由于迁移会将秘钥从一个分组迁移到另一个分组，而不同分组之间的 InstanceId 没有办法保证绝对递增，如果继续使用 InstanceId 作为锁版本就会出现切换分组后 InstanceId 反而降低的情况，破坏了锁的互斥性。

为了解决该问题，对于锁版本进行了优化。因为InstanceId为一个long类型，一共有64位，可以将其拆分为两部分，前16位和后48位，并赋予不同的含义，前16位在每次进行秘钥迁移的分组变更时，只要有原分组向冗余分组的变更操作，就会对其进行+1，作为分组变换次数的记录、后48位取 InstanceId 的后 48 位，如图7所示，通过这样的方式，保证了每次分组变更的时候，锁版本都是单调递增的。

3. 锁操作连续

由于原分组与冗余分组是两个并行独立运行的Paxos分组，Paxoslog以及状态机状态不同步，在分组切换的过程中，有可能会出现两个分组同时在更新相同锁数据的现象，如图8所示。

客户端发送请求12（12这⾥指代的是请求序列号，假设此操作为释放锁）到节点 2，节点2的原分组⼴播请求，此时节点1回复了请求12，由于应答数已经过半，此时获取锁操作成功。但是节点3由于还没有处理完前⼀个请求，此时他的序列号为11，接下来进⾏秘钥迁移，请求交给冗余分组处理，客户端发送请求13（假设此操作为获取锁），请求由冗余分组⼴播，节点3收到请求13的时候会进⾏数据同步更新操作，在请求13数据更新完成后，可能请求12才会被原分组处理，此时就出现了请求顺序错乱的问题，先执⾏了请求13获取锁，之后执⾏请求12释放锁，导致此时对于节点3来说锁状态为已释放，其他节点为锁持有中，出现数据不⼀致。

为了保证锁操作的连续性，解决上面的问题，在进行锁请求转发的时候，原分组的Master节点会记录此时原分组的最大InstanceId，该InstanceId之后的所有请求都和迁移的秘钥没有关系，当冗余分组要发起第一次 Propose 的时候会将原分组记录的InstanceId广播告诉所有节点，如图9，在冗余分组的所有成员节点第一次执行状态机对锁状态更新之前，先检查当前节点原分组对应的InstanceId是否大于记录的最大InstanceId，如果比记录的InstanceId小，说明该节点有数据落后，此时会等待原分组的数据同步完成之后再执行冗余分组的锁状态更新，避免了数据错乱问题。

通过上面的方式，保证了数据的一致性和锁操作的连续性。

4.1.3 迁移异常

在生产环境秘钥迁移过程中，可能会出现一些节点宕机、重启、网络抖动等异常情况，应对这些突发情况，需要能够将秘钥状态恢复到初始状态，如图10所示为正向（逆向）迁移流程。在迁移正常进行的基础上，迁移的准备阶段、开始阶段、迁移安全状态阶段都是可以进行回滚操作的，而等到客户端配置变更之后，向客户端下发的秘钥分组配置已经切换为冗余分组，不能再回滚。

如果触发迁移回滚，会将所有迁移的数据状态都恢复到迁移前状态。在迁移回滚的过程中，同样需要保证锁操作一致。

首先是存储一致性，在客户端变更前，服务端只进行了请求的转发，存储也是公用的，所以对于服务端来说，只要将请求转发恢复就可以了；其次，对于锁版本递增，每次在进行回滚操作的时候，如果是秘钥变更安全状态的回滚，会将分组变更次数加一，保证锁版本递增；最后是锁操作连续，前面已经介绍了为保证锁操作连续，在进行冗余分组第一次Propose时会检查当前节点原分组对应的InstanceId是否大于记录的最大InstanceId，在进行回滚操作的时候，同样也会检查冗余分组对应的InstanceId是否大于记录的最大InstanceId来保证锁操作的连续。

除了支持回滚外，考虑到每一个操作都有可能出现执行失败的情况，针对每一个操作都支持了重试。并且当 web 推送重试信息的时候，服务端会检测当前节点是否执行完该操作，如果执行完成了不进行处理，做到了重试的幂等。

4.2 分组节点变更和集群拆分

经过秘钥正向迁移，此时秘钥的所有请求都已经交给冗余分组来处理了，接下来就是分组节点变更和集群拆分。整体流程如图11所示。下面来介绍下变更的过程：

4.2.1 分组节点变更和集群拆分流程

添加节点 ：将需要迁移的新节点列表依次在web添加进来。

节点扩缩容 ：对于冗余分组将添加进来的节点按照扩节点，启动进程，缩节点的流程依次进行变更，直到冗余分组的成员都调整为新添加的节点。

集群拆分 ：通过web平台将所有新节点设置为一个新的集群，注册中心下发配置，服务端收到配置之后变更自身节点的归属集群。

4.2.2 关键点

1. 分组节点变更控制

因为WLock最初的成员变更维度都是集群维度，在进行添加减少节点的时候都是对集群下的所有分组进行操作，要支持分组维度的成员变更，就需要注册中心按照分组维度下发配置，如图12所示。这样，当每个节点拉取到自身的配置后，再按照分组进行比对找到需要进行成员变更的分组以及变更节点，通过Paxos进行成员的变更。

在进行扩缩容的时候，我们采用扩一个节点缩一个节点方式的原因是，如果我们直接将所有新节点扩进来或者直接将所有老节点下线，对于一个Paxos集群来说，由于存在过半节点响应的限制，每次Propose请求需要等待的响应节点数量会翻倍，降低了系统的处理能力，可能出现锁超时的情况。

2. Master漂移优化

分组节点扩缩容的目的是为了将冗余分组的成员从老节点调整为新节点，在变更的过程中，因为所有的老节点都会被新节点替换，所以必然存在Master节点的漂移，如图13所示，由于Master节点是处理锁请求的节点，为了保证处理锁请求的稳定性，需要在节点变更的过程中尽可能的减少Master漂移。但是在老节点被缩容之后，其余节点都可能成为新的Master。为此，可以通过调整新节点抢占Master的时机与间隔，来确保分组变更的新节点优先成为冗余分组的Master。

4.3 逆向迁移

在线上运行期间，每个分组对外提供服务的还是正常分组，冗余分组只是作为迁移过程中的一个中转分组，不会长期对外提供锁操作，当迁移经过集群拆分的时候，所有迁移秘钥的锁操作都是由冗余分组来处理的，为了保证对外提供服务的分组一致以及下次秘钥迁移的正常进行，需要再进行一次秘钥的逆向迁移，将秘钥归属分组从冗余分组迁移到原分组上。该步骤的流程和正向迁移类似，这里不在详细描述。

4.4 清除迁移数据

在经过了前面这些步骤之后，秘钥已经迁移到了一个新的集群，接下来就要进行迁移数据的清除。包括对于新老集群的冗余分组关闭Master选举、关闭Master负载均衡、清除迁移状态这些操作。删除之后冗余分组已经恢复到了迁移前的状态，随时可以进行下一次的迁移操作。

4.5 整体流程

最后再来回顾一下整体的迁移流程，如图14所示，首先是分组变更，将秘钥从原分组迁移到冗余分组，在此过程中，客户端会进行连接的断开、重连，触发过期事件补偿，之后进行分组的扩缩容和集群拆分，最后进行秘钥逆向迁移，最终达到秘钥隔离的目的。

在本文中，介绍了 WLock 为了应对突发情况而设计的秘钥迁移方案，通过几次演进与思考对方案进行了优化和调整，最终实现了分布式锁的平滑迁移。在迁移过程中只影响需要迁移的秘钥，对于其他秘钥没有影响，做到了秘钥隔离，并提供了容灾机制，在迁移过程中出现异常情况时，执行Master漂移、迁移回滚、重试操作仍能保证锁状态一致性。

参考资料

• [1] 开源｜WPaxos：一致性算法Paxos的生产级高性能Java实现

• [2] 开源 | WLock：高可用分布式锁设计实践

• [3] WLock 源码地址 : https://github.com/wuba/WLock.git

作者简介

闫城哲，58同城后端开发工程师

刘丹，58同城后端架构师，58分布式消息队列、分布式锁、分布式链路追踪等系统负责人

如何贡献&问题反馈

诚挚邀请对分布式锁感兴趣的同学一起参与WLock项目的开发建设，提出宝贵意见和建议，可在https://github.com/wuba/WLock.git开源社区提交issue与Pull Request反馈给我们。也可以扫描微信号，备注WLock，加入微信交流群。