多版本并發控制(MVCC)在分布式系統中的應用
問題
最近項目中遇到了一個分布式系統的并發控制問題。該問題可以抽象為：某分布式系統由一個數據中心D和若干業務處理中心 L1，L2 … Ln 組成；D本質上是一個 key-value 存儲，它對外提供基于 HTTP 協議的 CRUD 操作接口。L的業務邏輯可以抽象為下面 3 個步驟：
- read: 根據 keySet {k1, … kn}從D獲取 keyValueSet {k1:v1, … kn:vn}
- do: 根據 keyValueSet 進行業務處理，得到需要更新的數據集 keyValueSet’ {k1′:v1′， … km’:vm’} (注：讀取的 keySet 和更新的 keySet’可能不同)
- update: 把 keyValueSet’更新到D （注：D保證在一次調用更新多個 key 的原子性）
在沒有事務支持的情況下，多個L進行并發處理可能會導致數據一致性問題。比如，考慮 L1 和 L2 的如下執行順序：
- L1從D讀取 key:123對應的值 100
- L2從D讀取 key:123對應的 100
- L1將 key:123更新為 100 + 1
- L2將 key:123更新為 100 + 2
如果 L1 和 L2 串行執行，key 123 對應的值將為 103，但上面并發執行中 L1 的執行效果完全被 L2 所覆蓋，實際 key 123 所對應的值變成了 102。
解決方案1：基于鎖的事務
為了讓L的處理具有可串行化特性(Serializability)，一種最直接的解決方案就是考慮為D加上基于鎖的簡單事務。讓L在進行業務 處理前先鎖定D，完成以后釋放鎖。另外，為了防止持有鎖的L由于某種原因長時間未提交事務，D還需要具有超時機制，當L嘗試提交一個已超時的事務時會得到 一個錯誤響應。
本方案的優點是實現簡單，缺點是鎖定了整個數據集，粒度太大；時間上包含了L的整個處理時間，跨度太長。為此，可以考慮把鎖定粒度降低到數據項 級別，按 key 進行鎖定，但這又會帶來其他的問題。由于更新的 keySet’可能是事先不確定的，所以可能無法在開始事務時鎖定所有的 key；如果分階段來鎖定需要的 key，又可能出現死鎖(Deadlock)問題。另外，按 key 鎖定在有鎖爭用的情況下并不能解決鎖定時間太長的問題。所以，按 key 鎖定仍然存在重要的不足之處。
解決方案2：多版本并發控制
為了實現可串行化，同時避免鎖機制存在的各種問題，我們可以采用基于多版本并發控制（Multiversion concurrency control，MVCC）思想的無鎖事務機制。人們一般把基于鎖的并發控制機稱成為悲觀機制，而把 MVCC 等機制稱為樂觀機制。這是因為鎖機制是一種預防性的，讀會阻塞寫，寫也會阻塞讀，當鎖定粒度較大，時間較長是并發性能就不會太好；而 MVCC 是一種后驗性的，讀不阻塞寫，寫也不阻塞讀，等到提交的時候才檢驗是否有沖突，由于沒有鎖，所以讀寫不會相互阻塞，從而大大提升了并發性能。目 前，Oracle、PostgreSQL 和 MySQL 都已支持基于 MVCC 的并發機制，但具體實現各有不同。
MVCC 的一種簡單實現是基于 CAS（Compare-and-swap）思想的有條件更新（Conditional Update）。普通的 update 參數只包含了一個 keyValueSet’，Conditional Update 在此基礎上加上了一組更新條件 conditionSet { … data[keyx]=valuex， … }，即只有在D滿足更新條件的情況下才將數據更新為 keyValueSet’；否則，返回錯誤信息。這樣，L就形成了如下圖所示的 Try/Conditional Update/(Try again)的處理模式：
雖然對單個L來講不能保證每次都成功更新，但從整個系統來看，總是有任務能夠順利進行。這種方案利用 Conditional Update 避免了大粒度和長時間的鎖定，當各個業務之間資源爭用不大的情況下，并發性能很好。不過，由于 Conditional Update 需要更多的參數，如果 condition 中 value 的長度很長，那么每次網絡傳送的數據量就會比較大，從而導致性能下降。特別是當需要更新的 keyValueSet’很小，而 condition 很大時，就顯得非常不經濟。
為了避免 condition 太大所帶來的性能問題，可以為每條數據項增加一個 int 型的版本號字段，由D維護該版本號，每次數據有更新就增加版本號；L在進行 Conditional Update 時，通過版本號取代具體的值。
另一個問題是上面的解決方案假設了D是可以支持 Conditional Update 的；那么，如果D是一個不支持 Conditional Update 的第三方的 key-value 存儲怎么辦呢？這時，我們可以在L和D之間增加一個P作為代理，所有的 CRUD 操作都必須經過P，讓P來進行條件檢查，而實際的數據操作放在D。這種方式實現了條件檢查和數據操作的分離，但同時降低了性能，需要在P中增加 cache，提升性能。由于P是D的唯一客戶端；所以，P的 cache 管理是非常簡單的，不必像多客戶端情形擔心緩存的失效。不過，實際上，據我所知 redis 和 Amazon SimpleDB 都已經有了 Conditional Update 的支持。
總結
本文介紹了一種基于多版本并發控制（MVCC）思想的 Conditional Update 解決分布式系統并發控制問題的方法。和基于鎖的方法相比，該方法避免了大粒度和長時間的鎖定，當各個業務之間資源爭用不大的情況下，并發性能很好。
參考
Wikipedia – Multiversion concurrency control
Lock-free algorithms: The try/commit/(try again) pattern
Amazon SimpleDB FAQs – Does Amazon SimpleDB support transactions?
A Quick Survey of MultiVersion Concurrency Algorithms
友情推薦
本文的圖是陳皓開發的 TextDiagram 工具畫的，歡迎試用！如果您喜歡，請推薦給朋友，謝謝