松花皮蛋的黑板報
  • 分享在京東工作的技術感悟,還有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中學到什么

黑龙江6+1开奖结果查询