分布式锁

1.何为分布式锁

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

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

基于数据库实现分布式锁
基于缓存（Redis等)
基于Zookeeper等

2.条件

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

3.基于数据库实现

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

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

缺点：

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

4.基于Redis实现（单点实现）

基本流程

使用set key value nx ex time来设置锁，并设置过期时间。但是可能造成如下问题：
为了解决自动过期导致不同客户端错误删锁，使用UUID（也可以引用fetching机制）来解决如上问题。
由于之前是非原子性操作，因此会导致错误：
为了解决以上问题，可以使用Lua脚本来让判断并删除锁的连续行为变成原子操作

伪代码

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.基本流程

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

代码实现(基于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的质疑，他认为该方案存在两个问题：

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

这里他也给出了一种基于 fencing token的机制：也就是每次修改请求都会发送一个令牌，会对令牌进行校验，如果已经出处理过高请求的令牌，那么会执行拒绝该请求。
RedLock是依赖时钟的，如果存在时钟跳跃或者是时钟错误那么会导致不稳定。
过期时间无法确定，如果网络请求延迟那么会导致正在请求的锁还未获得，原本获取的锁已经到期了。