Posted on 2010-07-17 05:44
dennis 閱讀(4958)
評論(1) 編輯 收藏 所屬分類:
Clojure
Clojure
的并發（一） Ref和STM
Clojure
的并發（二）Write Skew分析
Clojure
的并發（三）Atom、緩存和性能
Clojure
的并發（四）Agent深入分析和Actor
Clojure
的并發（五）binding和let
Clojure的并發（六）Agent可以改進的地方
Clojure的并發（七）pmap、pvalues和pcalls
Clojure的并發（八）future、promise和線程
在
介紹Ref的上一篇blog提到，基于snapshot做隔離的MVCC實現來說，有個現象，叫
寫偏序——Write Skew。根本的原因是由于每個事務在更新過程中無法看到其他事務的更改的結果，導致各個事務提交之后的最終結果違反了一致性。為了理解這個現象，最好的辦法是在代碼中復現這個現象。考慮下列這個場景：
屁民Peter有兩個賬戶account1和account2，簡稱為A1和A2，這兩個賬戶各有100塊錢，一個顯然的約束就是這兩個賬戶的余額之和必須大于或者等于零，銀行肯定不能讓你賺了去，你也怕成為下個許霆。現在，假設有兩個事務T1和T2，T1從A1提取200塊錢，T2則從A2提取200塊錢。如果這兩個事務按照先后順序進行，后面執行的事務判斷A1+A2-200>=0約束的時候發現失敗，那么就不會執行，保證了一致性和隔離性。但是基于多版本并發控制的Clojure，這兩個事務完全可能并發地執行，因為他們都是基于一個當前賬戶的快照做更新的， 并且在更新過程中無法看到對方的修改結果，T1執行的時候判斷A1+A2-200>=0約束成立，從A1扣除了200塊；同樣，T2查看當前快照也滿足約束A1+A2-200>=0，從A2扣除了200塊，問題來了，最終的結果是A1和A2都成-100塊了，身為屁民的你竟然從銀行多拿了200塊，你等著無期吧。
現在，我們就來模擬這個現象，定義兩個賬戶：
;;兩個賬戶，約束是兩個賬戶的余額之和必須>=0
(def account1 (ref 100))
(def account2 (ref 100))
定義一個取錢方法：
;;定義扣除函數
(defn deduct [account n other]
(dosync
(if (>= (+ (- @account n) @other) 0)
(alter account - n))))
其中account是將要扣錢的帳號，other是peter的另一個帳號，在執行扣除前要滿足約束@account-n+@other>=0
接下來就是搞測試了，各啟動N個線程嘗試從A1和A2扣錢，為了盡快模擬出問題，使得并發程度高一些，我們將線程設置大一些，并且使用java.util.concurrent.CyclicBarrier做關卡，測試代碼如下：
;;設定關卡
(def barrier (java.util.concurrent.CyclicBarrier. 6001))
;;各啟動3000個線程嘗試去從賬戶1和賬戶2扣除200
(dotimes [_ 3000] (.start (Thread. #(do (.await barrier) (deduct account1 200 account2) (.await barrier)))))
(dotimes [_ 3000] (.start (Thread. #(do (.await barrier) (deduct account2 200 account1) (.await barrier)))))
(.await barrier)
(.await barrier)
;;打印最終結果
(println @account1)
(println @account2)
線程里干了三件事情：首先調用barrier.await嘗試突破關卡，所有線程啟動后沖破關卡，進入扣錢環節deduct，最后再調用barrier.await用于等待所有線程結束。在所有線程結束后，打印當前賬戶的余額。
這段代碼在我的機器上每執行10次左右都至少有一次打印：
-100
-100
這表示A1和A2的賬戶都欠下了100塊錢，完全違反了約束條件，法庭的傳票在召喚peter。
那么怎么防止write skew現象呢？如果我們能在事務過程中保護某些Ref不被其他事務修改，那么就可以保證當前的snapshot的一致性，最終保證結果的一致性。通過ensure函數即可保護Ref，稍微修改下deduct函數：
(defn deduct [account n other]
(dosync (ensure account) (ensure other)
(if (>= (+ (- @account n) @other) 0)
(alter account - n))))
在執行事務更新前，先通過ensure保護下account和other賬戶不被其他事務修改。你可以再多次運行看看，會不會再次打印非法結果。
上篇blog最后也提到了一個士兵巡邏的例子來介紹write skew，我也寫了段代碼來模擬那個例子，有興趣可以跑跑，非法結果是三個軍營的士兵之和小于100(兩個軍營最后只剩下25個人）。
;1號軍營
(def g1 (ref 45))
;2號軍營
(def g2 (ref 45))
;3號軍營
(def g3 (ref 45))
;從1號軍營抽調士兵
(defn dispatch-patrol-g1 [n]
(dosync
(if (> (+ (- @g1 n) @g2 @g3) 100)
(alter g1 - 20)
))
)
;從2號軍營抽調士兵
(defn dispatch-patrol-g2 [n]
(dosync
(if (> (+ @g1 (- @g2 n) @g3) 100)
(alter g2 - 20)
))
)
;;設定關卡
(def barrier (java.util.concurrent.CyclicBarrier. 4001))
;;各啟動2000個線程嘗試去從1號和2號軍營抽調20個士兵
(dotimes [_ 2000] (.start (Thread. #(do (.await barrier) (dispatch-patrol-g1 20) (.await barrier)))))
(dotimes [_ 2000] (.start (Thread. #(do (.await barrier) (dispatch-patrol-g2 20) (.await barrier)))))
;(dotimes [_ 10] (.start (Thread. #(do (.await barrier) (dispatch-patrol-g3 20) (.await barrier)))))
(.await barrier)
(.await barrier)
;;打印最終結果
(println @g1)
(println @g2)
(println @g3)