如何实现靠谱的分布式锁？

分布式锁，是用来控制分布式系统中互斥访问共享资源的一种手段，从而避免并行导致的结果不可控。基本的实现原理和单进程锁是一致的，通过一个共享标识来确定唯一性，对共享标识进行修改时能够保证原子性和和对锁服务调用方的可见性。由于分布式环境需要考虑各种异常因素，为实现一个靠谱的分布式锁服务引入了一定的复杂度。

分布式锁服务一般需要能够保证：

1. 同一时刻只能有一个线程持有锁
2. 锁能够可重入
3. 不会发生死锁
4. 具备阻塞锁特性，且能够及时从阻塞状态被唤醒
5. 锁服务保证高性能和高可用

当前使用较多的分布式锁方案主要基于redis、zookeeper提供的功能特性加以封装来实现的，下面我们会简要分析下这两种锁方案的处理流程以及它们各自的问题

1、基于redis实现的锁服务

加锁流程

SET resource_name my_random_value NX PX max-lock-time

注：资源不存在时才能够成功执行set操作，用于保证锁持有者的唯一性；同时设置过期时间用于防止死锁；记录锁的持有者，用于防止解锁时解掉了不符合预期的锁。

解锁流程

if redis.get("resource_name") ==  " my_random_value"
    return redis.del("resource_name")
else 
    return 0

注：使用lua脚本保证获取锁的所有者、对比解锁者是否所有者、解锁是一个原子操作。

该方案的问题在于

1) 通过过期时间来避免死锁，过期时间设置多长对业务来说往往比较头疼，时间短了可能会造成：持有锁的线程A任务还未处理完成，锁过期了，线程B获得了锁，导致同一个资源被A、B两个线程并发访问；时间长了会造成：持有锁的进程宕机，造成其他等待获取锁的进程长时间的无效等待

2) redis的主从异步复制机制可能丢失数据，会出现如下场景：A线程获得了锁，但锁数据还未同步到slave上，master挂了，slave顶成主，线程B尝试加锁，仍然能够成功，造成A、B两个线程并发访问同一个资源

2、基于zookeeper实现的锁服务

加锁流程

1) 在/resource_name节点下创建临时有序节点

2) 获取当前线程创建的节点及/resource_name目录下的所有子节点，确定当前节点序号是否最小，是则加锁成功。否则监听序号较小的前一个节点

注：zab一致性协议保证了锁数据的安全性，不会因为数据丢失造成多个锁持有者；心跳保活机制解决死锁问题，防止由于进程挂掉或者僵死导致的锁长时间被无效占用。具备阻塞锁特性，并通过watch机制能够及时从阻塞状态被唤醒

解锁流程

1) 删除当前线程创建的临时接点

该方案的问题在于

1) 通过心跳保活机制解决死锁会造成锁的不安全性，可能会出现如下场景：持有锁的线程A僵死或网络故障，导致服务端长时间收不到来自客户端的保活心跳，服务端认为客户端进程不存活主动释放锁，线程B抢到锁，线程A恢复，同时有两个线程访问共享资源

基于上诉对现有锁方案的讨论，我们能看到，一个理想的锁设计目标主要应该解决如下问题：

1. 锁数据本身的安全性
2. 不发生死锁
3. 不会有多个线程同时持有相同的锁

而为了实现不发生死锁的目标，又需要引入一种机制，当持有锁的进程因为宕机、GC活者网络故障等各种原因无法主动过释放锁时，能够有其他手段释放掉锁，主流的做法有两种：

1. 锁设置过期时间，过期之后Server端自动释放锁
2. 对锁的持有进程进行探活，发现持锁进程不存活时Server端自动释放

实际上不管采用哪种方式，都可能造成锁的安全性被破坏，导致多个线程同时持有同一把锁的情况出现。因此我们认为锁设计方案应在预防死锁和锁的安全性上取得平衡，没有一种方案能够绝对意义上保证不发生死锁并且是安全的。而锁一般的用途又可以分为两种，实际应用场景下，需要根据具体需求出发，权衡各种因素，选择合适的锁服务实现模型。无论选择哪一种模型，需要我们清楚地知道它在安全性上有哪些不足，以及它会带来什么后果。

1. 为了效率，主要是避免一件事被重复的做多次，用于节省IT成本，即使锁偶然失效，也不会造成数据错误，该种情况首要考虑的是如何防止死锁。
2. 为了正确性，在任何情况下都要保证共享资源的互斥访问，一旦发生就意味着数据可能不一致，造成严重的后果，该种情况首要考虑的是如何保证锁的安全。

下面主要介绍一下sharkLock的一些设计选择

锁信息设计如下

lockBy：client唯一标识
condition：client在加锁时传给server，用于定义client期望server的行为方式
lockTime：加锁时间
txID：全局自增ID
lease：租约

如何保证锁数据的可靠性

sharkLock底层存储使用的是sharkStore，sharkStore是一个分布式的持久化 Key-Value 存储系统。采用多副本来保证数据安全，同时使用 raft 来保证各个副本之间的数据一致性。

如何预防死锁

1. Client定时向Server发送心跳包，Server收到心跳包之后，维护Server端Session并立即回复，Client收到心跳包响应后，维护Client端Session。心跳包同时承担了延长Session租约的功能。
2. 当锁持有方发生故障时，Server会在Session租约到期后，自动删除该Client持有的锁，以避免锁长时间无法释放而导致死锁。Client会在Session租约到期后，进行回调，可选择性的决策是否要结束对当前持有资源的访问。
3. 对于未设置过期的锁，也就意味着无法通过租约自动释放故障Client持有的锁。因此额外提供了一种协商机制，在加锁的时候传递一些condition到服务端，用于约定Client端期望Server端对异常情况的处理，包括什么情况下能够释放锁。譬如可以通过这种机制实现server端在未收到十个心跳请求后自动释放锁，Client端在未收到五个心跳响应后主动结束对共享资源的访问。
4. 尽最大程度保证锁被加锁进程主动释放
   • 进程正常关闭时调用钩子来尝试释放锁
   • 未释放的锁信息写文件，进程重启后读取锁信息，并尝试释放锁

如何确保锁的安全性

1） 尽量不打破谁加锁谁解锁的约束，尽最大程度保证锁被加锁进程主动释放

• a) 进程正常关闭时调用钩子来尝试释放锁
• b) 未释放的锁信息写文件，进程重启后读取锁信息，并尝试释放锁

2） 依靠自动续约来维持锁的持有状态，在正常情况下，客户端可以持有锁任意长的时间，这可以确保它做完所有需要的资源访问操作之后再释放锁。一定程度上防止如下情况发生

• a) 线程A获取锁，进行资源访问
• b) 锁已经过期，但A线程未执行完成
• c) 线程B获得了锁，导致同时有两个线程在访问共享资源

3） 提供一种安全检测机制，用于对安全性要求极高的业务场景

• a) 对于同一把锁，每一次获取锁操作，都会得到一个全局增长的版本号
• b) 对外暴露检测API checkVersion（lock_name,version），用于检测持锁进程的锁是不是已经被其他进程抢占（锁已经有了更新的版本号）
• c) 加锁成功的客户端与后端资源服务器通信的时候可带上版本号，后端资源服务器处理请求前，调用checkVersion去检查锁是否依然有效。有效则认为此客户端依旧是锁的持有者，可以为其提供服务。
• d) 该机制能在一定程度上解决持锁A线程发生故障，Server主动释放锁，线程B获取锁成功，A恢复了认为自己仍旧持有锁而发起修改资源的请求，会因为锁的版本号已经过期而失败，从而保障了锁的安全性

下面对sharkLock依赖的sharkStore做一个简单的介绍

基本模块

• Master Server 集群分片路由等元数据管理、扩容和Failover调度等
• Data Server 数据存储节点，提供RPC服务访问其上的KV数据
• Gateway Server 网关节点，负责用户接入

Sharding

sharkStore采用多副本的形式来保证数据的可靠性和高可用。同一份数据会存储多份，少于一半的副本宕机仍然可以正常服务。 sharkStore的数据分布如下图所示

扩容方案

当某个分片的大小到达一定阈值，就会触发分裂操作，由一个分片变成两个，以达到扩容的目的。

• Dataserver上range的leader自己触发。 leader维持写入操作字节计数，每到达check size大小，就异步遍历其负责范围内的数据，计算大小并同时找出分裂时的中间key 如果大小到达split size，向master发起AskSplit请求，同意后提交一个分裂命令。分裂命令也会通过raft复制到其他副本。
• 本地分裂。分裂是一个本地操作，在本地新建一个range，把原始range的部分数据划拨给新range，原始range仍然保留，只是负责的范围减半。分裂是一个轻量级的操作。

Failover方案

failover以range的级别进行。range的leader定时向其他副本发送心跳，一段时间内收不到副本的心跳回应，就判断副本宕机，通过range心跳上报给master。由master发起failover调度。 Master会先删除宕机的副本然后选择一个合适的新节点，添加到range组内之后通过raft复制协议来完成新节点的数据同步。
Balance方案

dataserver上的range leader会通过range 心跳上报一些信息，每个dataserver还会有一个节点级别的Node心跳。 Master收集这些信息来执行balance操作。Balance通过在流量低的节点上增加副本，流量高的节点上减少副本促使整个集群比较均衡，维护集群的稳定和性能。

Raft实践-MultiRaft

1. 心跳合并

以目标dataserver为维度，合并dataserver上所有Raft心跳 心跳只携带 range ids，心跳只用来维护leader的权威和副本健康检测range ids的压缩，比如差量+整型变长 Leader类似跟踪复制进度，跟踪follower commit位置。

2. 快照管理控制

建立ack机制，在对端处理能力之内发送快照; 控制发送和应用快照的并发度，以及限速; 减少对正常业务的冲击。

Raft实践-PreVote

Raft算法中，leader收到来自其他成员term比较高的投票请求会退位变成follower

因此，在节点分区后重加入、网络闪断等异常情况下，日志进度落后的副本发起选举，但其本身并无法被选举为leader，导致集群在若干个心跳内丢失leader，造成性能波动;

针对这种情况，在raft作者的博士论文中，提出了prevote算法: 在发起选举前，先进行一次预选举Pre-Candidate， 如果预选举时能得到大多数的投票，再增加term，进行正常的选举。 prevote会导致选举时间变长(多了一轮RPC)，然而这个影响在实践中是非常小的， 可以有利于集群的稳定，是非常值得的实践。

Raft实践-NonVoter

一个新的raft成员加入后，其日志进度为空; 新成员的加入可能会导致quorum增加，并且同时引入了一个进度异常的副本; 新成员在跟上leader日志进度之前，新写入的日志都无法复制给它; 如果此时再有原集群内一个成员宕机， 很有可能导致集群内可写副本数到不到quorum，使得集群变得不可写。很多raft的实现中，都会引入了一种特殊身份的raft成员(non-voting 或者 learner) Learner在计算quorum时不计入其内，只被动接收日志复制，选举超时不发起选举; 在计算写入操作是否复制给大多数(commit位置)时，也忽略learner。 sharkstore raft 会在leader端监测learner的日志进度， 当learner的进度跟leader的差距小于一定百分比(适用于日志总量比较大) 或者小于一定条数时(适用于日志总量比较小)， 由leader自动发起一次raft成员变更，提升leaner成员为正常成员。

sharkStore目前已经开源，有兴趣的同学可详细了解，期待能跟大家能够一块儿沟通交流https://github.com/tiglabs/sharkstore