talk about consensus algorithm and distributed lock

關於一致性協議, 分散式鎖以及如何使用分散式鎖

最近看antirez 和 Martin 關於redlock 的分散式鎖是否安全的問題的爭吵, 非常有意思

http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

http://antirez.com/news/101

https://news.ycombinator.com/item?id=11065933

https://news.ycombinator.com/item?id=11059738

背景

關於分散式鎖其實這裡面是包含3個問題, 每一個都是獨立的不相關的問題

1. 一致性協議的問題
2. 如何通過一致性協議實現分散式鎖的問題
3. 如何結合業務場景使用分散式鎖

問題1和問題2 容易混淆, 其實實現一個分散式鎖只是需要一個key-value store 就可以了, 但是因為需要這個key-value store 高可用, 那麼就必然需要這個key-value store 多副本, 多副本又需要強一致, 那麼就必然引入一致性協議了

chubby 的論文裡面講的就是如何基於一致性協議paxos 實現一個分散式鎖服務, 跟一致性協議一點關係都沒有. 裡面很重要的一個觀點是為什麼要實現一個鎖服務, 用戶使用一個鎖服務相比於直接提供一個一致性協議的庫有哪些地方更方便

1. lock 提供的高可用性肯定比直接提供一致性協議的庫要來的低, 相當於通過lock 實現強一致和直接通過一致性協議提供強一致的業務邏輯
2. 有些場景很難改成通過一致性協議的場景
3. 分散式鎖的使用方式和之前單機是使用Lock 的方式一樣的直觀, 對使用人員的要求無成本
4. 有時候用戶只有少量的機器, 比如只有兩個機器, 就無法通過一致性協議提供強一致, 但是通過外部的鎖服務可以

在分散式鎖裡面有兩個要求

1. safety

任意時刻只能有一個 node 去獲得這個lock

1. liveness

這個lock 是在某一個時刻是會終止的

其實這兩點是互相矛盾的, 存在這個問題的本質原因是因為在分散式系統裡面我們無法判斷一個節點真的掛掉還是只是網路分區一會這個網路又會恢復

所有的distribute lock 的實現都存在的一個問題是, 在獲得這個鎖以後, 如果拿了這個鎖的節點死掉了, 或者網路永久斷開了, 那麼這個鎖也就死鎖了. 就違背了 liveness 的問題, 為了解決這個問題, 幾乎所有的distribute lock 都會加上一個時間的限制, 但是這個時間的限制又會有一個問題就是如果獲得這個鎖的節點, 在拿到鎖以後, 執行的操作的時候超過了這個時間的限制, 那麼我們改怎麼辦? 那麼這個時候就有可能被其他的節點也獲得這個鎖, 那麼就違背了 safety 的限制.

因此在我們操作系統的lock 裡面選擇的是死鎖, 所以操作系統有liveness 的問題, 而大部分的distribute lock 的實現選擇的是給這個lock 加上lease, 如果超過了這個lease, 依然返回, 我認為你這個lock 已經失效了, 可以把這個lock 給其他的節點. 因此在使用distribute lock 的時候需要注意的是儘可能在鎖區間的操作應該是可預期的, 儘可能時間短的.

觀點

主要噴antirez 有問題的地方在於兩個:

1. 這種auto release lock 會存在的問題是, 用戶獲得lock 操作以後, redlock 的做法有一個lease, 如果在這個lease 裡面不執行unlock 操作, 系統只能認為你已經掛掉. 那麼在過了lease 時間以後, 另外一個node 獲得了這個Lock, 那麼有可能第一個節點並沒有掛掉(這裡是java gc 黑的最慘的地方哈哈哈), 那麼這個時候系統就無法保證只有一個leader, 這個lock 也就沒用了
2. 第二個就比較直接了, 就是通過時間戳來保證底下的強一致. 這個是被噴的最慘的, 這個就沒什麼好解釋的了

那麼Martin 提供的帶遞增Token 的方法是不是解決了這個問題呢?

其實我覺得Martin 說的帶fencing Token 的方法是通過拿到鎖的系統必須能夠保證提供一個支持cas 操作檢查的系統才行, 能夠檢查寫入的Token 是否比之前的token 都大, zk 使用的也是類似的方法. 但是不解決剛才我們說的safety 的問題, 因為在使用帶Token 的方法裡面也是無法保證某一個時刻只能有一個節點獲得這個lock, 只是通過額外的一個系統裡面寫入的時候檢查這個Token 來避免這個問題. 所以從整體上來看是解決了這個問題, 但是其實是需要使用lock 的服務提供 cas 操作才行.

所以我認為從整體上看, 除非你底下獲得Lock 操作以後, 需要做的事情非常簡單, 那麼可以通過fencing token 來做保證, 但是更多的工程裡面獲得lock 以後的操作比較複雜, 所以很難想Martin 說的那樣能夠實現這個cas 操作. 所以floyd 提供的lock 基本就是基於一致性協議raft + lease 實現的auto release lock

結論

回頭開頭的3個問題, 如果實現一致性協議就不說了.

如何實現分散式鎖呢?

那麼大體的實現就是給在節點lock 的時候, 對於這個lock 操作有一個lease的時候, 如果在這個租約的時間內, 這個節點沒有來續租, 那麼就認為這個操作是超時的, 一般情況為了實現的可靠性保證, 會在這個租約失效前就提前續租, 比如租約的時間是 10s, 我在0s 的時候就獲得這個lock, 那麼我在6s 的時候就必須去做這個續租操作, 如果沒有執行成功的話, 那麼我就認為你這個lease 失效了, 其他的節點可以在6s 時刻就獲得這個lock, 但是只能在10s以後提供服務, 新的節點的租約時間是10s~20s. 那麼從6s~10s 這段時間即使新節點獲得了lock, 但是也無法提供服務的, 這個是典型的CAP 場景裡面系統availability 換取consistenty 的例子.

那麼如何使用分散式鎖呢?

在pika_hub 的場景裡面, 有一個專門的線程每3s去獲得這個lock, 在獲得這個lock 以後, 就認為自己是 pika_hub 的leader, 然後建立與所有的pika 節點的連接. 如果在某一個時刻其他的pika_hub 節點搶到了這個lock, 那麼就說明之前的pika_hub 節點已經掛掉, 或者超時. 那麼如何Pika_hub 節點在6s的時刻發現自己獲得這個lock 失敗, 那麼該如何操作呢? 這個時刻 pika_hub 將與 pika 建立連接的線程都殺死, 這個時候其實有6s~10s 這一段4s 的時間, 我們認為在工程實現裡面4s 可以完成這個操作. 那麼其他節點就算在6s的時候執行Lock() 操作依然是獲得不了這個lock(), 因為這個lock() 雖然沒有被更新lease, 但是lease 依然在有效期內的. 那麼等到10s 以後才有一個新的節點搶到這個lock(). 這個時候新的節點成為leader 與其他的Pika 節點建立連接, 所以系統中可能存在最多13s的沒有leader 的時間

在zeppelin 裡面, 也一樣有專門的線程去獲得這個lock, 在獲得這個lock 以後, 將自己是leader 的信息寫入到floyd 裡面, 然後做leader 該做的事情. 和pika_hub 的處理方式一樣, 如果發現無法和floyd 交互了, 那麼就把自己改成follower 的信息. 不一樣的地方在於因為這裡使用floyd 作為storage, 那麼其實可以通過類似Martin 提供的方式進行類似cas 的操作來更新. 這裡也可以看出就像 antirez 噴 Martin 一樣, 並不是所有的獲得鎖以後的操作都可以改成cas 的操作, 比如pika_hub 就不可以

最後, 看到最後的肯定是真愛, 歡迎關注我們的項目 floyd https://github.com/Qihoo360/floyd