8. Redisson源码剖析-RedLock源码

一、RedLock算法原理

1. 这个场景是假设有一个redis cluster，有3个redis master实例，然后执行如下步骤获取一把分布式锁。
2. 获取当前时间戳，单位是毫秒，轮流尝试在每个master节点上创建锁，过期时间较短，一般就几十毫秒，在每个节点上创建锁的过程中，需要加一个超时时间，一般来说比如几十毫秒如果没有获取到锁就超时了，标识为获取锁失败
3. 尝试在大多数节点上建立一个锁，比如3个节点就要求是2个节点（n / 2 +1）
4. 客户端计算建立好锁的时间，如果建立锁的时间小于超时时间，就算建立成功了
5. 要是锁建立失败了，那么就依次删除已经创建的锁
6. 如果这把锁已经被别人获取了，你就得不断轮询去尝试获取锁

二、和普通的Redis锁的区别

普通的redis分布式锁，其实是在redis集群中根据hash算法选择一台redis实例创建一个锁就可以了，而RedLock需要尝试在每个master实例上获取锁，RedLock算法思想，不能只在一个redis实例上创建锁，应该是在多个redis实例上创建锁，n / 2 + 1，必须在大多数redis节点上都成功创建锁，才能算这个整体的RedLock加锁成功，避免说仅仅在一个redis实例上加锁

三、一些有趣的事情

1. 其实之前看redisson官方文档的时候，和现在的差别很大的，https://github.com/redisson/redisson/wiki/8.-distributed-locks-and-synchronizers#83-multilock，官方文档，面其实已经已经不推荐使用RedLock锁了，但是在前两年，关于RedLock的争议还是比较大的，主要是来自Martin的批评以及作者antirez的回应，在剖析源码之前，我们先来回顾一下两个神仙之间的大家，本文也将用大量的篇幅讲述两人之间的爱恨纠缠，并非我闲的蛋疼，而是从两个人的对攻与防守来看，真的有很多有趣的事情以及从中可以看到两个人对技术的执著以及技术功底的深厚，还有就是对待技术的态度。因为RedLock本身的源码是很简单的。
2. 首先来自Martin的质疑，http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html ，可以参考这篇。这里大概解释一下

四、Martin质疑

1. 首先Martin上来就提出，what are you using that lock for?我们要这个锁到底是用来干嘛的，两个原因

a） Efficiency: Taking a lock saves you from unnecessarily doing the same work twice (e.g. some expensive computation). If the lock fails and two nodes end up doing the same piece of work, the result is a minor increase in cost (you end up paying 5 cents more to AWS than you otherwise would have) or a minor inconvenience (e.g. a user ends up getting the same email notification twice).【提升效率，用锁来保证一个任务没有必要被执行两次。比如（很昂贵的计算）】
b ）Correctness: Taking a lock prevents concurrent processes from stepping on each others’ toes and messing up the state of your system. If the lock fails and two nodes concurrently work on the same piece of data, the result is a corrupted file, data loss, permanent inconsistency, the wrong dose of a drug administered to a patient, or some other serious problem.【保证正确，使用锁来保证任务按照正常的步骤执行，防止两个节点同时操作一份数据，造成文件冲突，数据丢失。】

2. 对于上面的2个问题，一个一个的来分析

a) 首先对于提升效率，如果多个客户端同时的去争取Redis的资源的话，会有什么影响？无非就是多付出一些计算成本，我们完全可以用单节点的Redis去完成，没必要用RedLock去维护那么多个Redis实例。原文中的部分【I will argue that if you are using locks merely for efficiency purposes, it is unnecessary to incur the cost and complexity of Redlock, running 5 Redis servers and checking for a majority to acquire your lock. You are better off just using a single Redis instance, perhaps with asynchronous replication to a secondary instance in case the primary crashes.】
b) 对于保证正确性这个问题，RedLock到底能不能保证？在源码中我们可以看到RedLock是继承了MultiLock,实际的应用场景，比如在下单的时候，需要锁住库存、积分等。对于这种情况，我们来看看，到底RedLock能不能100%的上锁成功。

4.1 首先来看一张Martin给的图

afzssnw7ww.png

1. 首先，为了防止死锁，RedLock中有一个过期时间，这个过期时间原本是用来干嘛的，防止死锁，那么也就是这个超时时间，可能会出现问题。为什么呢？
2. 我们看上图，
   2.1 如果客户端1获取了锁，那么这个时候，恰好发生的FGC，导致系统停顿，Redis锁超时释放了
   2.2 这个时候客户端2正好来获取这把锁，然后提交了数据
   2.3 此时客户端1从FGC苏醒过来，然后提交了数据
3. 所以现在想想是不是还挺有意思的，你只能保证可用性而不能保证数据的正确性，那还玩个啥。OK，那么此时，就按照我们平时写业务代码的思维，在客户端1在提交数据的时候，检查一下自己是不是这把锁的持有者不就可以了么？显然不行，因为FGC可以发生在任何时候，万一FGC发生在你查询结果之后呢？

3.1 那换一种没有GC的语言？好像也不太行，为什么？导致系统停顿的原因不仅仅有FGC，还有可能是IO阻塞，网络抖动等。

4.2 对于上面的情况，Martin也给出了解决方案

2lp109vp42.png

为锁增加一个 token-fencing。

1. 获取锁的时候，还需要获取一个递增的token，比如上图中的客户端1获取的token是33.
2. 如果发生了类似FGC的情况，client 2获取了34的token
3. 在client 1提交数据的时候，判断如果token小于上一次提交时的token，就会报错(其实这个整体思想有点像是MySQL的MVCC多版本控制，个人感觉)

4.3 Using time to solve consensus，其实这里也是一个问题

1. 比如，客户端1从A、B、C、D、E五台 Redis master 中的A、B、C三台实例上获取了锁，这也是基于RedLock加锁的机制，只要保证大多数(n/2+1)加锁成功就代表加锁成功了
2. 如果这个时候，实例B的时间比其他机器走的快，B先过期了，他把锁释放了
3. 这个时候client 2从B、D、E获取锁，依然可以获取锁成功。这样是不是造成了两个客户端同时持有了锁

4.4 我想的Martin的意思

1. 分布式锁，你可以在有限的时间内，如果不能给出明确的结果没有关系，但是你特么别给错的啊。
2. 对于提升效率，RedLock太重
3. 对于正确性，你又不能完全保证，所以你说要你干嘛。

对于Martin的大概质疑，其实，个人感觉还是很刺激有趣的。对于他的质疑，有理有据。思路清晰

五、antires回应

首先antire总结了Martin的指控，反正写了很多。总结一下就是，RedLock无法解决的问题(计算获取锁的时间，检查获取锁的时间是否小于获取锁的时间。如果这个时候发生了阻塞的情况)，这个问题别的锁就能解决了？

六、源码

1. 在说源码之前，对于两个人的质疑与解答，个人感觉，系统设计不可能完全的去适应所有的场景，我们对于一个技术方案，知道他为我们解决了什么问题，带来了哪些方便以及局限性，能否接受他的缺陷给我们带来的后果。再去权衡是否将他引用到我们的业务系统之中

源码片段一、

public static void main(String[] args) throws Exception {
        Config config = new Config();
        config.useClusterServers()
                .addNodeAddress("redis://192.168.0.107:7001")
                .addNodeAddress("redis://192.168.0.107:7002")
                .addNodeAddress("redis://192.168.0.110:7003")
                .addNodeAddress("redis://192.168.0.110:7004")
                .addNodeAddress("redis://192.168.0.111:7005")
                .addNodeAddress("redis://192.168.0.111:7006");


        RedissonClient redisson = Redisson.create(config);

        RLock lock1 = redisson.getLock("lock1");
        RLock lock2 = redisson.getLock("lock2");
        RLock lock3 = redisson.getLock("lock3");

        RedissonRedLock lock = new RedissonRedLock(lock1,lock2,lock3);
        // 代码片段三、
        lock.lock();
        lock.unlock();
    }

代码片段二、

RedissonRedLock

/**
 * Copyright 2018 Nikita Koksharov
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.redisson;


import java.util.List;


import org.redisson.api.RLock;


/**
 * RedLock locking algorithm implementation for multiple locks. 
 * It manages all locks as one.
 * 
 * @see <a href="http://redis.io/topics/distlock">http://redis.io/topics/distlock</a>
 *
 * @author Nikita Koksharov
 *
 */
public class RedissonRedLock extends RedissonMultiLock {


    /**
     * Creates instance with multiple {@link RLock} objects.
     * Each RLock object could be created by own Redisson instance.
     *
     * @param locks - array of locks
     */
    public RedissonRedLock(RLock... locks) {
        super(locks);
    }

    /**
     * 加锁失败的一个数量。锁的个数-成功获取锁的客户端的最小数量
     */
    @Override
    protected int failedLocksLimit() {
        return locks.size() - minLocksAmount(locks);
    }
    
    /**
     * 代表成功获取锁的个数，即：如果3个客户端，3/2 +1 = 2，2个客户端加锁成功，代表获取锁成功
     */
    protected int minLocksAmount(final List<RLock> locks) {
        return locks.size()/2 + 1;
    }

    /**
     * 计算多个客户端一起加锁的超时时间，每个客户端的等待时间
     */
    @Override
    protected long calcLockWaitTime(long remainTime) {
        return Math.max(remainTime / locks.size(), 1);
    }
    
    @Override
    public void unlock() {
        unlockInner(locks);
    }


}

代码片段三、

@Override
public void lock() {
    try {
        // 代码片段四、
        lockInterruptibly();
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}

代码片段四、

@Override
public void lockInterruptibly() throws InterruptedException {
    //这里的参数其实直接会影响后面的逻辑。代码片段五、
    lockInterruptibly(-1, null);
}

代码片段五、

public void lockInterruptibly(long leaseTime, TimeUnit unit) throws InterruptedException {
    // baseWaitTime = 3 * 1500 = 4500毫秒
    long baseWaitTime = locks.size() * 1500;
    long waitTime = -1;
    if (leaseTime == -1) {
        // waitTime = 4500毫秒
        waitTime = baseWaitTime;
        unit = TimeUnit.MILLISECONDS;
    } else {
        waitTime = unit.toMillis(leaseTime);
        if (waitTime <= 2000) {
            waitTime = 2000;
        } else if (waitTime <= baseWaitTime) {
            waitTime = ThreadLocalRandom.current().nextLong(waitTime/2, waitTime);
        } else {
            waitTime = ThreadLocalRandom.current().nextLong(baseWaitTime, waitTime);
        }
        waitTime = unit.convert(waitTime, TimeUnit.MILLISECONDS);
    }
    
    while (true) {
        // 代码片段六、waitTime = 4500毫秒, leaseTime= -1
        if (tryLock(waitTime, leaseTime, unit)) {
            return;
        }
    }
}

代码片段六、

其实这里又走到了RedissonMultiLock中

// 这里的参数如果设置了，waitTime = 4500毫秒，laseTime = -1
 public boolean tryLock(long waitTime, long leaseTime, TimeUnit unit) throws InterruptedException {
//        try {
//            return tryLockAsync(waitTime, leaseTime, unit).get();
//        } catch (ExecutionException e) {
//            throw new IllegalStateException(e);
//        }
        long newLeaseTime = -1;
        if (leaseTime != -1) {
            // 1. 如果设置了leaseTime newLeaseTime= waitTime * 2,这里并没有设置
            newLeaseTime = unit.toMillis(waitTime) * 2;
        }
        // 当前时间    
        long time = System.currentTimeMillis();
        long remainTime = -1;
        if (waitTime != -1) {
            // remainTime = 4500毫秒
            remainTime = unit.toMillis(waitTime);
        }

        // 计算所的等待时间lockWaitTime=1500毫秒，这里可以参考代码片段七、
        long lockWaitTime = calcLockWaitTime(remainTime);
        // 代码片段八、n - (n / 2 + 1)，3个lock，最多可以容忍1个lock加锁失败
        int failedLocksLimit = failedLocksLimit();
        List<RLock> acquiredLocks = new ArrayList<RLock>(locks.size());

        // 拿到每个获取锁的客户端的迭代器
        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);
                    // 其实这里就是说，能够容忍最大的超时时间就是1500毫秒，1500毫秒之内必须加成功这个小锁，不然就加锁失败
                    lockAcquired = lock.tryLock(awaitTime, newLeaseTime, TimeUnit.MILLISECONDS);
                }
            } catch (Exception e) {
                lockAcquired = false;
            }
            
            // 如果获取锁成功了，acquiredLocks.add，将添成功加到锁的客户端添加到集合中
            if (lockAcquired) {
                acquiredLocks.add(lock);
            } else {
                // 其实就是判断失败的次数是否大于允许失败的次数
                // 如果加锁失败了，3 - 成功加锁的客户端个数 == 允许加锁失败个数
                // 比如，此时第一个客户端A加锁失败，那么就是3-0 = 3，逻辑往下走，当然，我们先假设加锁成功
                // 客户端A加锁成功 3-1 = 2，条件是不成立的，逻辑往下走，客户端B再来加锁,如果加锁成功,那么3-2=1，
                // 条件成立的，那么就已经满足了大多数实例加锁成功的条件，直接返回加锁成功
                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();
                    // reset iterator
                    while (iterator.hasPrevious()) {
                        iterator.previous();
                    }
                } else {
                    // failedLocksLimit—-，如果加锁失败，那么能容忍失败的限制就是会从1变成0，你不能再失败了，兄弟，再失败就真的失败了
                    // 如果有3个redis实例，最大的限制次数是1，如果遍历第一个redis实例，失败了，那么failedLocksLimit会减成0
                    // 如果failedLocksLimit就会走上面的if逻辑，释放所有的锁，然后返回false
                    failedLocksLimit--;
                }
            }
            
            if (remainTime != -1) {
                remainTime -= (System.currentTimeMillis() - time);
                time = System.currentTimeMillis();
                if (remainTime <= 0) {
                    unlockInner(acquiredLocks);
                    return false;
                }
            }
        }


        if (leaseTime != -1) {
            List<RFuture<Boolean>> futures = new ArrayList<RFuture<Boolean>>(acquiredLocks.size());
            for (RLock rLock : acquiredLocks) {
                RFuture<Boolean> future = rLock.expireAsync(unit.toMillis(leaseTime), TimeUnit.MILLISECONDS);
                futures.add(future);
            }
            
            for (RFuture<Boolean> rFuture : futures) {
                rFuture.syncUninterruptibly();
            }
        }
        
        return true;
    }

代码片段七、

@Override
protected long calcLockWaitTime(long remainTime) {
    // 4500 / 3 = 1500毫秒
    return Math.max(remainTime / locks.size(), 1);
}

源码片段八、

@Override
protected int failedLocksLimit() {
    // 3 - 2 = 1
    return locks.size() - minLocksAmount(locks);
}

七、总结

1. RedLock，是一个锁，只不过是在各个不同的master实例上进行加锁，但是现在说RedLock合并了多个小lock。也就是说，如果你有3个redis master实例，你就用lock1、lock2、lock3三个锁key，人家本来就是分布在3个不同的redis master实例上的
2. 加这个RedLock，相当于是3个redis master实例上的key，有2个加成功了，就算这个RedLock加锁成功了
3. 此时别人如果要来加锁，用一样的key，人家是无法成功加锁的，锁被你占用了，人家就会卡在那儿，死循环，不断的尝试加锁，直到你释放锁