本文是閱讀論文Efficient Optimistic Concurrency Control Using Loosely Synchronized Clocks的讀書筆記.
概述
論文是在1995年發表的，當時分佈式數據系統中怎麼實現分佈式事務這個方向就是一個熱門的領域，這麼多年過去了，一直到現在，當時提出的OCC（Optimistic Concurrency Control）仍然是當今的一個熱門個研究方向。
人們一直都希望能夠實現一個高效、可擴展、穩定的持久化存儲系統，而本文提出的OCC正是用來解決這個問題的，其特點是：
- 數據在client端本地緩存，在server端持久化
- 對提交的事務提供了serializability and external consistency的保證
- 通過鬆散同步的時鐘獲取global serialization
OCC支持併發事務，但是沒有像傳統方法那樣對每個數據都保存著併發控制的信息，而是隻保存了一個版本號，保證了內存消耗盡量的少，並且低存儲消耗的情況下，也保證了性能。
介紹
本文介紹的OCC適用的場景是什麼？
分佈式面向對象數據庫系統，數據持久化由server負責，client為了提高性能會對數據進行cache。
為什麼叫樂觀併發控制？
樂觀是相對比悲觀算法來說的，為了保證事務的external consistency，一個簡單的方法就是通過鎖，將所有事務串行化，但是這樣子肯定會使得性能很差，那解決方法就是去掉鎖，只有當衝突發生的時候才採取措施，因此樂觀是相對於悲觀的加鎖算法來說的。
什麼是external consistency？
external consistency(有些文章叫Linearizability或者strict serializability) 是指：後開始的事務一定可以看到先提交的事務的修改
樂觀的代價
由於我們不採用鎖，因此OCC有其使用的限制：適合衝突少的場景，如果大量事務都發生衝突，那OCC會有非常糟糕的性能，因為：
悲觀算法只會延遲事務的執行，樂觀算法一旦衝突，會直接終止事務執行。
樂觀的實現
樂觀算法本質上只是將衝突的檢測延後了，當發生衝突後進行恢復，因此核心解決的問題有兩個：
- 衝突檢測
- 衝突恢復
環境
本文提出的OCC已經在面向對象數據庫Thor中實現，下面給出Thor的模型圖
Thor模型圖
此處每個應用直接運行在client上，數據持久化在server上，為了提高性能，每個client本地對數據都進行了cache，應用可以直接在client上執行，然後操作本地cache中的數據，最後提交時才與後端servers進行通信。
在數據提交的時候，會帶上兩部分信息：
- validation information：表示本次事務T中涉及到的數據的讀寫類型
- installation information：修改後的數據
client發送commit請求給後端server，如果這些數據是server自己擁有的，則進行提交操作，否則，server轉換為Coordinate角色，和擁有數據的participants一起完整事務的提交操作。
此時coordinate和participants之間會涉及到2-phase protocol，下面簡要的描述下。
第一階段如下：
1.1 coordinate發送prepare msg給各個參與者，消息包含了validation information和installation information
1.2 參與者驗證通過後，將 installation information記錄到磁盤，回覆ok
1.3 coordinate收到所有參與者回覆ok後，記錄一條commit消息到本地磁盤，然後回覆給客戶端說ok
第二階段是異步執行的
2.1 coordinate發送commit消息給各個參與者
2.2 參與者將installation消息中的新值覆蓋掉老值，並在本地記錄一條commit日誌，回覆給coordinate說ok
當server提交了事務後，需要發送invalidation messages給除了客戶端之外的其他持有緩存數據的客戶端，那怎麼找到這些客戶端呢？
server這邊對每個客戶端都存著一個cached set，這些invalidation messages不要求正確，但是需要滿足下面兩點：
- 如果client收到invalidation messages，當前執行中的transaction還沒讀到舊數據了，那將本地cache中的數據失效
- 如果當前transaction已經讀到舊數據了，則立即終止當前transaction
當客戶端處理完invalidation messages消息後，回覆給server，server將其從失效集合（invalid set）中移除。
高效的驗證規則
閱讀更多 Java高併發框架 的文章
