分布式锁的几种实现

分布式锁的几种实现

Tans 1,133 2022-03-29

分布式锁

1.何为分布式锁

原来的单机部署的系统演化为分布式集群系统后,由于分布式系统多线程、多进程分布在不同的机器上,那么在单机部署情况下的原有的并发控制锁策略失效,为了解决分布在不同主机上共享资源的访问,就需要今天要谈的分布式锁。

现在,市面上基于锁主流的实现方案主要有以下几种:

  1. 基于数据库实现分布式锁
  2. 基于缓存(Redis等)
  3. 基于Zookeeper等

2.条件

  • 互斥性:在任意时刻,只有一个客户端才能持有锁
  • 无死锁,即使一个客户端在持有锁的期间崩溃而没有主动解锁,那也能保证后续其他客户能加锁
  • 加锁和解锁的必须是一个客户端,A客户端不能解除B客户端上的锁
  • 加锁和解锁必须有原子性

3.基于数据库实现

利用了主键唯一的特性,当多个请求同时提交到数据库时,数据库保证只有一个操作可以成功,那么我们就可以认为那个线程获得了该方法的锁,当方法执行完毕后,想要释放锁的话,那么删除这条数据库记录即可。

也可以配合类似MVCC的版本号进行实现。

缺点:

  1. 是非阻塞的,数据库插入失败会直接返回错误,需要一直插入
  2. 多个请求同时到来可能会造成表锁,效率较低
  3. 数据库压力比较大
  4. 没有失效时间,可能需要设置一个定时任务来自动删除。
  5. 这把锁是非重入的,需要设置锁的主机信息和线程信息,下次请求的话,比对两者数据就可以获得锁
  6. 非公平的,需要添加额外的一张表来存储等待锁的全部线程。按照时间排序
  7. 连接的开销比较大

4.基于Redis实现(单点实现)

基本流程

  1. 使用set key value nx ex time来设置锁,并设置过期时间。但是可能造成如下问题:

    image-20220328191239418
  2. 为了解决自动过期导致不同客户端错误删锁,使用UUID(也可以引用fetching机制)来解决如上问题。

    image-20220328191625433
  3. 由于之前是非原子性操作,因此会导致错误:

    image-20220328192210598
  4. 为了解决以上问题,可以使用Lua脚本来让判断并删除锁的连续行为变成原子操作

image-20220328192513548

伪代码

void getLock(){
	String uuid = new UUID();
	if(set nx key uuid ex 100){
		//lock sucess
		//相应逻辑
	}else{
		//以下两行再lua脚本实现
		if((get key) != uuid) continue;
		else del(key);
	}
}

5.基于RedLock实现(分布式实现)

是Redis作者提出的一种解决方案,主要是针对分布式模式下,如果从mater节点拿到了锁,由于采用异步通信的方式进行数据同步,当master还未进行同步时就已宕机,那么此时slave节点被选举出来成为新的master,这个时候由于slave没有这把锁就会导致一把锁被拿到两次的情景。

1.基本流程

  1. 获取当前Unix时间startTime,以毫秒为单位。
  2. 以此尝试N个节点,使用相同的key和随机值获取,在此步骤中,应该在客户端设置一个网络连接和响应超时时间,这个超时时间应该小于锁的失效时间,如果锁的失效时间是10s,那么超时时间应该是5ms左右,这是为了防止当在一个实例获取不到锁的时候,长时间等待导致后续获得锁操作时间严重推迟。
  3. 客户使用当前时间减去开始时间startTime得到获取锁消耗的时间usedTime,当且仅当获取了大部分锁(N / 2 + 1),并且使用时间小于失效时间,那么才算获得成功
  4. 如果获取到了锁,key的真正有效时间等于有效时间减去获得锁所使用的时间expireTime-usedTime
  5. 如果获取锁失败或者逻辑完成需要释放锁,客户端应该在所有的客户端实例上进行解锁操作。(为了防止加锁时候,加锁成功但是由于网络原因未收到相应的节点响应)

代码实现(基于redission)

public class RedissonMultiLock implements Lock {

    final List<RLock> locks = new ArrayList<RLock>();

    public RedissonMultiLock(RLock... locks) {
        if (locks.length == 0) {
            throw new IllegalArgumentException("Lock objects are not defined");
        }
        this.locks.addAll(Arrays.asList(locks));
    }

     // waitTime: 获取锁最长等待时间 leaseTime:租期 unit:时间单位
    public boolean tryLock(long waitTime, long leaseTime, TimeUnit unit) throws InterruptedException {
        long newLeaseTime = -1;
        if (leaseTime != -1) {
            if (waitTime == -1) {
                 //如果没有设置等待时间,那么租期新租期为现有租期时间
                newLeaseTime = unit.toMillis(leaseTime);
            } else {
                 //否则新租期为等待时间*2
                newLeaseTime = unit.toMillis(waitTime)*2;
            }
        }
        
        // 1. time为当前时间戳,用来标记每次获得锁的起始时间
        long time = System.currentTimeMillis();
        long remainTime = -1; //获取锁剩余等待时间 
        if (waitTime != -1) {
            remainTime = unit.toMillis(waitTime);
        }
        // 计算锁的等待时间,RedLock中:如果remainTime=-1,那么lockWaitTime为1
        long lockWaitTime = calcLockWaitTime(remainTime);
        
        // RedLock中failedLocksLimit即为n/2 + 1
        int failedLocksLimit = failedLocksLimit();
        List<RLock> acquiredLocks = new ArrayList<RLock>(locks.size());
        // 循环每个redis客户端,去获取锁
        for (ListIterator<RLock> iterator = locks.listIterator(); iterator.hasNext();) {
            RLock lock = iterator.next();
            boolean lockAcquired; // 标记该是否获取成功
            try {
                // 调用tryLock方法去获取锁,如果获取锁成功,则lockAcquired=true
                if (waitTime == -1 && leaseTime == -1) {
                    lockAcquired = lock.tryLock();
                } else {
                    long awaitTime = Math.min(lockWaitTime, remainTime);
                    lockAcquired = lock.tryLock(awaitTime, newLeaseTime, TimeUnit.MILLISECONDS);
                }
            } catch (Exception e) {
                lockAcquired = false;
            }
            
            // 如果获取锁成功,将锁加入到list集合中
            if (lockAcquired) {
                acquiredLocks.add(lock);
            } else {
                // 如果获取锁失败,判断失败次数是否等于失败的限制次数
                // 比如,3个redis客户端,最多只能失败1次
                // 这里locks.size = 3, 3-x=1,说明只要成功了2次就可以直接break掉循环
                if (locks.size() - acquiredLocks.size() == failedLocksLimit()) {
                    break;
                }

                // 如果最大失败次数等于0, 那么直接释放锁
                if (failedLocksLimit == 0) {
                    // 释放所有的锁,RedLock加锁失败
                    unlockInner(acquiredLocks);
                    if (waitTime == -1 && leaseTime == -1) {
                        return false;
                    }
                    failedLocksLimit = failedLocksLimit();
                    acquiredLocks.clear();
                    // 由于设置了等待时间,重置迭代器 重试再次获取锁
                    while (iterator.hasPrevious()) {
                        iterator.previous();
                    }
                } else {
                    // 失败的限制次数减一
                    // 比如3个redis实例,最大的限制次数是1,如果遍历第一个redis实例,失败了,那么failedLocksLimit会减成0
                    // 如果failedLocksLimit就会走上面的if逻辑,释放所有的锁,然后返回false
                    failedLocksLimit--;
                }
            }
            
            if (remainTime != -1) {
                 //剩余等待时间减去本次获得锁所需要的时间
                remainTime -= (System.currentTimeMillis() - time);
                time = System.currentTimeMillis();
                 //如果剩余等待时间小于0,那么直接释放所有锁
                if (remainTime <= 0) {
                    unlockInner(acquiredLocks);
                    return false;
                }
            }
        }

         //将每个租期设置成为
        if (leaseTime != -1) {
            acquiredLocks.stream()
                    .map(l -> (RedissonBaseLock) l)
                    .map(l -> l.expireAsync(unit.toMillis(leaseTime), TimeUnit.MILLISECONDS))
                    .forEach(f -> f.toCompletableFuture().join());
        }
        return true;
    }
}

但是RedLock遭到了分布式专家Martin Kleppmann的质疑,他认为该方案存在两个问题:

  1. 虚拟机中GC等运行的时候会出现STW也就是说暂停所有进程,这会导致如下情况:

    图片

    这里他也给出了一种基于 fencing token的机制:也就是每次修改请求都会发送一个令牌,会对令牌进行校验,如果已经出处理过高请求的令牌,那么会执行拒绝该请求。

    640

  2. RedLock是依赖时钟的,如果存在时钟跳跃或者是时钟错误那么会导致不稳定。

  3. 过期时间无法确定,如果网络请求延迟那么会导致正在请求的锁还未获得,原本获取的锁已经到期了。

6.总结

关于分布式锁,其实还有很多实现,无论是从数据库、Redis等缓存数据库或者Zookeeper入手,都能找到比较好的解决方案,但是各有利弊,同时比如RedLock等安全性可靠性还亟待验证,没有完美的架构,没有普适的架构,只有在不同架构之间寻求平衡,才是好的架构。

参考文档

  1. 关于RedLock的安全性辩论
  2. Redission基于RedLock的实现
  3. 分布式锁-看这一篇就够了
  4. 关于时钟跳跃的论证

喜欢的小伙伴还请点个赞哦!如有纰漏可联系博主。