分布式系列之分布式锁几种实现机制

在分布式系统中，分布式锁用来解决分布式系统中多线程、多进程在不同机器上共享资源访问的问题。本文简要介绍分布式锁的四种实现机制，包括数据库、Redis缓存、Zookeeper和Etcd，以加深了解。

1、分布式锁介绍

在单体应用中，通过锁机制实现多线程对共享资源的访问的，在分布式系统中，由于多线程、多进程是分布在不同的机器上，单机部署的并发锁控制机制已经不能满足分布式要求。分布式锁就是解决分布式系统中共享资源访问的问题，与单体应用不同的是，资源控制的最小粒度也从线程升级到了进程。

1.1 分布式锁的设计原则

为了满足分布式系统中资源的并发访问控制，分布式锁在设计上应满足以下原则：

在分布式系统环境下，一个方法在同一个时间只能被一个机器的同一个线程执行
高可用架构保证获取锁与释放锁过程中可靠性
获取锁与释放锁的高性能保证
具备可重入特性，可以理解为由相同的任务并发使用，不必担心数据错误
具备锁失效机制，防止死锁。锁申请等待超时限制，通常我们无法判断为什么一个线程迟迟拿不到锁，可能是饥饿，可能是死锁，给定一个等待时间，让线程自动放弃
具备非阻塞锁特性，即没有获取到锁将直接返回获取锁失败
中断响应，等待锁的线程，程序可以根据需要取消对锁的请求，如果一个线程正在等待锁，那么它依然可以收到一个通知，被告知无需等待，可以停止等待，可以处理死锁
公平锁，会按照时间的先后顺序，保证先到者先得，后到者后得，不会产生饥饿现象，只要排队，最终都能得到资源。如果使用synchronized关键字进行锁控制，那么产生的锁就是非公平的

1.2 分布式锁实现方法

常见的分布式锁实现方法有几种：基于数据库通过唯一索引实现、基于缓存Redis实现、基于一致性算法Zookeeper或Etcd实现

基于数据库实现：主要是利用数据库的唯一索引来实现，同一时刻只能允许一个竞争者获取锁，加锁时候在数据库中插入一条锁记录，利用业务id进行防重。当第一个竞争者加锁成功后，后续竞争者再来加锁就会报唯一键值冲突
基于缓存实现：基于缓存的加锁基本是在内存进行操作，理论上效率最高。使用Redis实现都是基于SETNX key value这个命令，如果key不存在才会执行成功
基于一致性算法实现：常见的有基于zookeeper实现和基于Etcd实现，zookeeper是利用临时顺序节点不能重复创建来实现排它性；Etcd则是利用存储的key值带有Revision属性，每次进行全局事务操作，对应的Revision值都会加1，保证了全局唯一

下面将分别介绍以上几种实现方法。

2、基于数据库实现

基于数据库实现分布式锁的原理是使用表的唯一索引：在数据库中创建一个表，表中包含方法名等字段，并在方法名字段上创建唯一索引，想要执行某个方法，就是要这个方法名向表中插入数据，成功插入则获取锁，执行完成后删除对应的行数据释放锁。

CREATE TABLE `distributed_lock` (`id` bigint(20) NOT NULL AUTO_INCREMENT,`unique_method` varchar(255) NOT NULL COMMENT '锁定的方法名',`holder_id` varchar(255) NOT NULL COMMENT '锁持有者id',`create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP,PRIMARY KEY (`id`),UNIQUE KEY `unique_method_index` (`unique_method`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

其中id字段为自增id，unique_method字段就是防重的唯一方法名，也就是加锁的对象。在表中创建了唯一索引，保证unique_method的唯一性。

1）加锁即插入一条记录

insert into distributed_lock(unique_method, holder_id) values (‘unique_method’, ‘holder_id’);

如果当前sql执行成功代表加锁成功，如果抛出唯一索引异常(DuplicatedKeyException)则代表加锁失败，当前锁已经被其他竞争者获取。

2）解锁很简单，直接删除此条记录即可

delete from methodLock where unique_method=‘unique_method’ and holder_id=‘holder_id’;

3）数据库实现简单，操作简单，用操作数据库的方式即可实现锁，但是存在以下问题：

因为是基于数据库实现的，数据库的可用性和性能将直接影响分布式锁的可用性及性能，所以数据库需要实现高可用架构部署以及支持高TPS的并发访问效率；
不具备可重入特性，因为同一个线程在释放锁之前，行数据一直存在，无法再次成功插入数据。解决方法是在表中新增一列，用于记录当前获取到锁的机器和线程信息。在再次获取锁的时候，先查询表中的机器和线程信息是否和当前机器和线程信息相同，若相同则直接获取锁；
没有锁失效机制，因为有可能出现成功插入数据后，服务器宕机了，对应的数据没有被删除，此时distributed_lock表中的这条记录就会一直存在，其他竞争者无法加锁。为了解决这个问题，需要在锁中新增一列，用于记录失效的时间，并且需要有定时任务清除这些失效的数据；
不具备阻塞锁的特性，获取不到锁直接返回失败，所以需要优化获取逻辑，循环多次去获取，增加失败重试的机制

3、基于Redis实现

3.1 Redis基本实现

Redis加锁的基本实现：使用setnx、expire、delete以及LUA脚本实现

1）使用setnx设置超时时间，锁定资源，客户端在此超时时间内完成对共享资源的访问

set(lockKey, requestId, SET_IF_NOT_EXIST, SET_WITH_EXPIRE_TIME, expireTime);

第一个为key，我们使用key来当锁，因为key是唯一的
第二个为value，这里是锁竞争者的id，在解锁时需要判断当前解锁的竞争者id是否为锁持有者
第三个SET_IF_NOT_EXIST即当key不存在时，我们进行set操作；若key已经存在，则不做任何操作
第四个SET_WITH_EXPIRE_TIME给这个key加一个过期时间的设置，具体时间由第五个参数决定
第五个参数为time，与第四个参数相呼应，代表key的过期时间

2）使用随机字符串做value值，预防以下情况：客户端1获取锁成功，在某个操作阻塞很久后超时，自动释放锁，客户端2拿到此资源的锁，客户端1从阻塞中恢复过来，释放客户端2的锁，所以这个值需要是随机的

3）释放锁的操作需要使用LUA脚本，包括get、判读和del，保证操作的原子性

String script = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";

判断当前解锁的竞争者id是否为锁的持有者，如果不是直接返回失败，如果是则进入第2步；
删除key，如果删除成功，返回解锁成功，否则解锁失败。

注意到这里解锁其实是分为2个步骤，涉及到解锁操作的一个原子性操作问题。这也是为什么解锁的时候用Lua脚本来实现，因为Lua脚本可以保证操作的原子性。

4）节点宕机，在failover过程中丧失了锁的安全性。在主从架构下，客户端A从master获取到锁，在master将锁同步到slave之前主节点宕机了，slave节点升级为主节点，客户端B获取了客户端A相同的资源，但是已经A已经获取了另外一个锁，锁安全失效。

3.2 Redlock算法

Redlock算法是在单节点Redis的基础上引入的高可用模式，基于Redlock分布式锁的实现原理如下，假设有N个Redis master节点（N为奇数），同时需要在N台服务器上面运行这些Redis实例，这样保证不会同时宕掉。为了获取到锁，客户端应该执行以下操作：

获取当前时间（毫秒数），并设置超时时间TTL
按顺序依次向N个Redis节点执行获取锁的操作，这里获取锁和之前单节点的操作过程相同，包括全局唯一的随机字符串、过期时间。
1. 为了保证某个Redis节点不可用的时候算法能够继续运行，客户端需要设置一个响应超时时间，这个超时时间要远小于锁的有效时间。
2. 客户端在向某个Redis节点获取锁失败后，立即尝试下一个节点，避免客户端等待时间过长。
3. 获取锁失败包括任何类型的失败，比如Redis节点不可用、Redis节点上的客户端已经被其它客户端持有等
计算整个获取锁过程总共耗时时间
1. 计算方法是当前时间减去第一步记录的时间
2. 如果客户端大多数Redis节点（>=N/2+1）成功获取了锁，并且获取锁总共消耗的时间没有超过锁的有效时间TTL，则客户端认为最终获取锁成功；否则认为获取锁失败
如果最终获取锁成功，则这个锁的有效时间为锁最初的有效时间TTL-第3步计算出来的锁获取消耗时间。比如TTL定义为5s，获取锁耗时1s，那么锁实际有效时间为4s
如果最红锁获取失败（没有获取到半数以上的Redis锁或者获取所有节点的锁耗时超过有效时间TTL），客户端应想所有Redis节点发起释放锁的操作
释放锁的过程比较简单，客户端向所有Redis节点发起释放锁的操作，不管这些节点当时是否获取锁成功与否

在这里插入图片描述

4、基于Zookeeper实现

4.1 Zookeeper的节点类型

Zookeeper节点可以看成是树形结构，每个目录都被定义为一个目录节点znode，znode一共有四种类型：

持久节点(PERSISTENT)：默认的节点类型。创建节点的客户端与zookeeper断开连接后，该节点依旧存在。
持久节点顺序节点(PERSISTENT_SEQUENTIAL)：所谓顺序节点，就是在创建节点时，Zookeeper根据创建的时间顺序给该节点名称进行编号。
临时节点(EPHEMERAL) ：和持久节点相反，当创建节点的客户端与zookeeper断开连接后，临时节点会被删除。
临时顺序节点（EPHEMERAL_SEQUENTIAL）：临时顺序节点结合临时节点和顺序节点的特点，在创建节点时，Zookeeper根据创建的时间顺序给该节点名称进行编号；当创建节点的客户端与Zookeeper断开连接后，临时节点会被删除。

Zookeeper分布式锁是基于临时顺序节点实现的。

4.2 排他锁实现

排他锁实现机制是线程在zookeeper上创建临时有序节点，使用watch监控资源节点等待获得锁。具体流程如下：

线程x申请锁资源时候，先去判断是否有其它事务持有锁，如果有需等待锁释放
多个线程1、2、3并发请求在zk上创建一个名为 /lock 的节点，同时只能有一个线程创建成功，假设线程1创建成功，那么线程2、3在创建，只会提示该节点已经存在，这样模拟线程1加锁成功，让他执行业务
此时让线程2、3加锁失败，就监听/lock这个节点，模拟排队等待锁被释放
当线程1执行完业务逻辑后，删除/lock节点，模拟释放锁
当/lock被删除后，就会被线程2、3监听到，他们就可以重新尝试创建该节点

在这里插入图片描述

在上述流程中，客户端通过调用create方法创建表示锁的临时节点/lock，创建成功的客户端获得了锁，同时让没有获得锁的节点在该节点上注册Watcher监听，以便实时监听到lock节点的变更情况。当当前获得锁的客户端正常执行完业务逻辑，客户端会主动删除创建的临时节点。同时，如果获得锁的客户端发生宕机或异常，那么zookeeper上这个节点就会被删除也会释放锁资源。

4.3 共享锁实现

排他锁有一个缺点就是，如果并发量大，那么同一时刻会有很多连接对同一节点进行监听，但检测到删除事件后，zk需要通知所有的连接，所有连接收到监听后，会同一时间在发生高并发竞争，给性能带来严重损耗。多数场景下考虑使用共享锁实现：

读锁：共享锁，如果前面没有写节点，则直接上锁；如果前面有写节点，则等待距离自己最近的写节点释放锁
写锁：如果前面没有节点，则直接上锁，如果前面有节点，则等待释放

同时为了避免锁竞争，会使用公平锁机制，将没有获得锁的线程放入队列进行排队，等锁资源释放以后，按照先进先出的算法取出一个线程尝试获取锁。

在这里插入图片描述

通过Zookeeper上节点表示一个锁，类似于“/lockpath/[hostname]-请求类型-序号”的临时顺序节点
客户端通过调用create方法创建表示锁的临时顺序节点，如果是读请求为“/lockpath/[hostname]-R-序号”，写请求为“/lockpath/[hostname]-W-序号”
将临时节点加入到锁请求队列中
根据先进先出算法，锁队列中的第一个获取锁资源，判断读写请求分为以下步骤：
1. 对于读请求，如果没有比自己序号更小的子节点或者比自己序号小的子节点都是读请求，那么表明已经成功获得共享锁，开始执行读取逻辑；如果有比自己序号小的子节点有写请求，则等待锁资源
2. 对于写请求，如果不是序号最小的节点，则等待锁资源，否则获得锁开始处理业务
当事务处理完成或异常中断，锁资源释放以后会唤醒所有在队列中的线程，从第四步开始尝试重新申请锁资源
线程会注册Watcher监听lockpath子节点中前一个节点的状态，形成一个等待队列

4.4 实现分析

Zookeeper实现分布式锁有以下特征：

解决不可重入：客户端加锁时将主机和线程信息写入锁中，下一次再来加锁时直接和序列最小的节点对比，如果相同，则加锁成功，锁重入。
锁释放时机：由于创建的节点是顺序临时节点，当客户端获取锁成功之后session会话突然断开，ZK也会自动删除这个临时节点。
单点问题：ZK是集群部署的，主要一半以上的机器存活，就可以保证服务可用性。

5、基于Etcd实现

5.1 Etcd分布式锁实现机制

Lease机制：即租约机制（TTL，Time to Live），Etcd可以为存储的key-value对设置租约，当租约到期，key-value将失效删除；同时也支持refresh续约，通过客户端可以在租约到期前进行续约，以避免过期失效。Lease机制可以保证分布式锁的安全性，为锁对应的key配置租约，即使锁的持有者因故障而不能主动释放锁，也会因为租约到期而自动释放。
Revision 机制：存储的每个key值都带有一个Revision属性值，Etcd每进行一次事务操作，对应的全局Revision值都会加一，因此每个key对应的Revision属性值都是全局唯一的。这种机制有个作用就是通过比较Revision的大小就能知道写操作的顺序。
公平锁机制：在实现分布式锁时，多个客户端同时抢锁，根据Revision号的大小依次获得锁，可以避免“羊群效应”，实现公平锁。
Prefix机制：即前缀机制也称目录机制，可以根据前缀获取该目录下所有的key及对应的属性（包括key,、value以及revision等）。
- 比如，一个名为/mylock的锁，两个客户端同时进行写操作，实际写入的值分别为：key1=”/mylock/uuid1”和key2=”/mylock/uuid2”，其中uuid表示全局唯一。很显然写操作都会成功，但是返回的revision值不一样，那么判断谁获得了锁呢？
- 通过前缀/mylock查询，返回包含两个key-value对应的列表，同时也包含他们的revision值，通过Revision大小，客户端可以判断自己是否获得了锁。如果锁资源争抢失败，则等待锁释放再判断是否可以获得锁
Watch机制：即监听机制，Watch 机制支持Watch某个固定的key，也支持Watch一个目录（前缀机制），当被 Watch 的key或目录发生变化，客户端将收到通知。
- 在实现分布式锁时，可以通过对Revision值比自己小且相差最小的key（称为pre-key）值进行监控，因为只有它释放锁，自己才能获得锁。如果监测到pre-key的DELETE事件，则说明pre-key已释放，自己将获得锁资源。

5.2 Etcd分布式锁实现流程

Etcd分布式锁实现流程如下所示，分为6个阶段：

在这里插入图片描述

1）准备阶段

客户端连接Etcd，以/lock/mylock为前缀创建全局唯一的key，假设第一个客户端对应的key为“/lock/mylock/UUIDA”，第二个客户端对应的key为“/lock/mylock/UUIDB”，第三个客户端对应的key为“/lock/mylock/UUIDC”。客户端分别为自己的key创建租约lease，租约的长度根据业务耗时确定。

2）创建定时任务作为租约的“心跳”

当客户端持有锁期间，其它客户端只能等到，为了避免等待期间租约失效，客户端需要创建一个定时任务作为心跳以保证租约的有效性。此外，如果持有锁期间客户端奔溃，心跳停止，key值也会因为租约到期而被删除，从而释放锁资源，避免死锁。

7）客户端将自己全局唯一的key写入Etcd

客户端进行Put操作，将步骤1中创建的key值绑定租约写入Etcd，根据ETCD的revision机制，ETCD中会根据事务的操作顺序记录revision值。同时，客户端需要记录Etcd返回的revision值，用于接下来判断是否获得锁。在图中，Etcd中插入三条key-value记录，Revision分别为1/2/3，其中客户端A返回的Revision值为1。

4）客户端判断是否获得锁

客户端以前缀/lock/mylock读取key-value列表，判断自己的Revision是否为当前key-value列表中最小的，如果是则认为获得锁；否则的话，会监听key-value中前一个Revision比自己小的key的DELETE事件，一旦监听到删除事件或者因为租约到期的删除事件，则客户端获得锁资源。在图中，客户端A执行完事务，释放锁资源执行DELETE操作，客户端B即获得锁资源。

5）执行业务

客户端在获得锁资源后，执行业务逻辑。

6）获得锁

完成业务流程后对应的key释放锁。