松花皮蛋的黑板报
  • 分享在京东工作的技术感悟,还有JAVA技术和业内最佳实践,大部分都是务实的、能看懂的、可复现的

扫一扫
关注公众号

ARTS-10-分布式系统之分布式锁

博客首页文章列表 松花皮蛋me 2019-05-19 17:52

ARTS的初衷

Algorithm: 主要是为了编程训练和学习。

Review:主要是为了学习英文

Tip:主要是为了总结和归纳在是常工作中所遇到的知识点。学习至少一个技术技巧。在工作中遇到的问题,踩过的坑,学习的点滴知识。

Share:主要是为了建立影响力,能够输出价值观。分享一篇有观点和思考的技术文章

https://www.zhihu.com/question/301150832

一、Algorithm

Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

class Solution {
    public boolean canPartition(int[] nums) {
        //正数集合划分子集,各子集求和值相等
        //先简单求和判断是否可以整除2
        int sum = 0;
        int maxNum = 0;
        for(int n:nums) {
            sum += n;
            maxNum = Math.max(maxNum,n);
        }
        if(sum%2!=0 || sum/2<maxNum) return false;
        //dfs
        //return  dfs(nums,sum/2,0);
        return dp(nums,sum/2);
    }

    //超时了,GG
    private boolean dfs(int[] nums,int target,int level) {
        if(nums.length==level) return false;
        if(nums[level]==target) return true;
        if(nums[level]>target) return false;
        return dfs(nums,target,level+1) || dfs(nums,target-nums[level],level+1);
    }

    private boolean dp(int[] nums,int target) {
        //dp[0] = true
        //dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)
       Boolean[] d = new Boolean[target+1];
       d[0] = true;
       for(int i=1;i<d.length;i++) {
            d[i] = false;
        }
       for(int i=0;i<nums.length;i++) {
           for(int j=target;j>=nums[i];j--) {
               d[j] = d[j] || d[j-nums[i]];
           }
       }
        return d[target];
    }

}

二、Review

How to do distributed locking如何设计分布式锁。

一般情况下我们会通过下面的方法进行资源的一致性保护。

// THIS CODE IS BROKEN
function writeData(filename, data) {
    var lock = lockService.acquireLock(filename);
    if (!lock) {
        throw 'Failed to acquire lock';
    }

    try {
        var file = storage.readFile(filename);
        var updated = updateContents(file, data);
        storage.writeFile(filename, updated);
    } finally {
        lock.release();
    }
}

但是很遗憾的是,上面这段代码是不安全的,比如客户端client-1获取锁后由于执行垃圾回收GC导致一段时间的停顿(stop-the-word GC pause)或者其他长时间阻塞操作,此时锁过期了,其他客户如client-2会获得锁,当client-1恢复后就会出现client-1\client-2同时处理获得锁的状态。

我们可能会想到通过令牌或者叫版本号的方式,然而在使用Redis作为锁服务时并不能解决上述的问题。不管我们怎么修改Redlock生成token的算法,使用unique random随机数是不安全的,使用引用计数也是不安全的,一个redis node服务可能会出宕机,多个redis node服务可能会出现同步异常(go out of sync)。Redlock锁会失效的根本原因是Redis使用getimeofday作为key缓存失效时间而不是监视器(monitonic lock),服务器的时钟出现异常回退无法百分百避免,ntp分布式时间服务也是个难点。

分布式锁实现需要考虑锁的排它性和不能释放它人的锁,作者不推荐使用Redlock算法,推荐使用zookeeper或者数据库事务(个人不推荐:for update性能太差了)。

补充:使用zookeeper实现分布式锁。

可以通过客户端尝试创建节点路径,成功就获得锁,但是性能较差。更好的方式是利用zookeeper有序临时节点,最小序列获得锁,其他节点lock时需要阻塞等待前一个节点(比自身序列小的最大那个)释放锁(countDownLatch.wait()),当触发watch事件时将计数器减一(countDownLatch.countDown()),然后此时最小序列节点将会获得锁。可以利用Curator简化操作,示例如下:

public static void main(String[] args) throws Exception {
            //重试策略
            RetryPolicy retryPolicy = new ExponentialBackoffRetry(1000, 3);

            //创建工厂连接
            final CuratorFramework curatorFramework = CuratorFrameworkFactory.builder().connectString(connetString)
                    .sessionTimeoutMs(sessionTimeOut).retryPolicy(retryPolicy).build();

            curatorFramework.start();

            //创建分布式可重入排他锁,监听客户端为curatorFramework,锁的根节点为/locks
            final InterProcessMutex mutex = new InterProcessMutex(curatorFramework, "/lock");
            final CountDownLatch countDownLatch = new CountDownLatch(1);

            for (int i = 0; i < 100; i++) {
                new Thread(new Runnable() {
                    @Override
                    public void run() {
                        try {
                            countDownLatch.await();
                            //加锁
                            mutex.acquire();
                            process();
                        } catch (Exception e) {
                            e.printStackTrace();
                        }finally {
                            try {
                                //释放锁
                                mutex.release();
                                System.out.println(Thread.currentThread().getName() + ": release lock");
                            } catch (Exception e) {
                                e.printStackTrace();
                            }
                        }
                    }
                },"Thread" + i).start();
            }

            Thread.sleep(100);
            countDownLatch.countDown();

        }
    }

补充:redis实现分布式锁。

public enum  FreeLockUtil {
    instance;

    public static FreeLockUtil getInstance()
    {
        return instance;
    }

    @Autowired
    @Qualifier("jimClient")
    private Cluster jimClient;

    @Autowired
    private TdeUtil tdeUtil;

    private String scriptHash;

    @PostConstruct
    public void init() {
        String script = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";
        scriptHash = jimClient.scriptLoad(script);
    }

    /** 
    * @Description: 没有获得锁时会返回空 
    * @Param: [key] 
    * @return: java.lang.String 
    * @Author: Pidan
    */
    public String lock(String lockKey)
    {
        String token = tdeUtil.random();
        //不要将set和expire分开
        Boolean lockRes = jimClient.set(lockKey, token, 1L,TimeUnit.MINUTES, false);
        return lockRes?token:null;
    }
    /** 
    * @Description: 类似CAS版本号
    * @Param: [key, value] 
    * @return: void 
    * @Author: Pidan
    */
    public void unlock(String lockKey,String token)
    {
        //不要在客户端使用get-if-equals-del
      jimClient.evalsha(scriptHash, Collections.singletonList(lockKey),Collections.singletonList(token),true);
    }
}

各种选型优缺点比较

1、Redis实现

1)优点

性能较好,实现简单。

2)缺点

Redis缓存的内存大小如果不足的话极有可能会导致信息丢失。

一般情况下redis可以满足业务场景,但是在执行耗时较长的任务时,需要为锁添加很长的超时时间,一方面时间比较难估算,另一方面,若中途宕机或服务重启,都需要在管理页面手动释放锁,这需要对业务相对熟悉才能知道有多少受影响的锁,操作具有一定难度。所以对于类似业务场景,在添加锁时初始设置一个较短的时间,再额外开启一个守护线程,在当前锁快过期时再为其设置一个过期时间,直至任务执行完成。

业务场景中对于阻塞锁的实现,一般使用while循环定时尝试获取锁。若已获取锁的服务在执行任务过程中宕机,则其他阻塞必须等待锁超时才有可能获取锁。

2、Zookeeper实现

1)优点

客户端宕机等异常情况下,当前客户端持有的锁可实时释放。
依据Zookeeper官方API自定义实现,有问题方便排查。

2)缺点

需要动态创建删除临时节点,频繁操作磁盘读写,性能会受到影响。
Zookeeper API抛出的各种异常需手动处理。
ZK连接管理,session失效管理需手动处理。
Watch只生效一次,需反复重连。
不适用场景:一个线程中先添加A锁再添加B锁,同时另一个线程先添加B锁再添加A锁,该种死锁问题无法解决。

3、Apache Curator实现

1)优点

Curator封装较为彻底,API简单明了,掌握及接入成本很低。
客户端宕机等异常情况下,当前客户端持有的锁可实时释放。
解决了各种异常处理、Watch反复注册的问题。
提供了各种分布式场景下的工具包,例如分布式锁的实现,分布式CyclicBarrier实现、Leader选举等。

2)缺点

不适用场景:一个线程中先添加A锁再添加B锁,同时另一个线程先添加B锁再添加A锁,该种死锁问题无法解决。

三、Tip

谈谈SpringBoot中Condition条件注解容易踩的坑。

1、在自定义Condition实现类中不能注入Bean。
2、application.properties在spring boot中属于环境变量级别的配置加载,所以优先级较高,
假如通过其他配置文件进行加载时借助PropertySource或者ConfigurationProperties之类的是不能如愿的,需要我们手动加载。

 Properties properties = new Properties();
        try {
            properties.load(context.getResourceLoader().getResource("important.properties").getInputStream());
        } catch (IOException e) {
            e.printStackTrace();
        }

3、自定义Condition实现类不是单实例的,不能使用成员变量缓存上面手动加载的Properties或者验证结果。

四、Share

微服务架构之服务框架Dubbo-服务暴露
微服务架构之我们应该从Dubbo中学到什么