《雲數據管理：挑戰與機遇》2.3.2　並發控製

本節書摘來自華章出版社《雲數據管理》一書中的第2章，第3節，作者迪衛艾肯特·阿格拉沃爾，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看

並發控製

並發控製協議必須能夠保證衝突可串行性。並發控製協議一般可以分為悲觀協議（pessimistic protocol）和樂觀協議（optimistic protocol）兩種，悲觀協議使用鎖來避免錯誤的操作，而樂觀協議是在提交階段采用驗證器（certifier或validator）來保證正確性。一般情況下，從技術的角度來看，任何並發控製協議都可以很容易地擴展到分布式環境中。

封鎖協議

對於每一個操作，事務（或並發控製調度器）都會申請一個鎖，每個鎖都有兩種模式：讀和寫。兩個讀鎖是相容的，而兩個寫鎖或者一個讀鎖和一個寫鎖是不相容的。如果一個數據項沒有以不相容的模式封鎖，那麼該數據項就可以授予鎖。否則，存在一個鎖衝突，並且事務處於封鎖狀態（會經曆鎖等待）直到當前的鎖持有者釋放鎖。一個操作執行完成後，相應的鎖就會被釋放。鎖本身不足以保證正確性。兩段鎖協議增加了下列條件，以下條件足以保證衝突可串行性[Eswaran et al., 1976]：

一旦一個事務釋放了一個鎖，該事務不能隨即獲取任何數據項的任何其他鎖。

圖2-9顯示，在擴展階段，事務所需要的鎖的數量不斷增加，在收縮階段，鎖的數據逐漸減少。

 

圖2-9　兩段鎖

兩段鎖在很多商業化係統中廣受歡迎，尤其是嚴格版本，在事務結束之前（即提交或中斷），保留所有的鎖。然而，兩段鎖可能會出現死鎖。而且由於衝突操作的存在，數據項隊列可能導致數據衝突。這種衝突可能導致係統抖動（在常規多道程序設計係統中，資源衝突一般是由內存、處理器、I/O通道引起的，而不是數據引起的衝突）。

樂觀協議

如上所述，封鎖可能造成長時間的資源阻塞。樂觀並發控製協議可以允許事務執行所有操作，並使用驗證方法來判斷其他事務是否執行了衝突操作，通過這種方式可以有效避免這種阻塞。最簡單的情況是，事務t1執行其所有操作（寫操作會導致本地緩存更新）。當事務提交時，調度器會檢查是否有活動的事務執行了衝突操作，如果有，就中止t1。

Kung and Robinson [1981]對上述簡單思想進行了擴展，通過三個階段來執行每個事務t1：

讀階段。在該階段，事務可以無限製地讀取任何對象，而寫是本地的。

驗證階段。在該節點，調度器通過檢查所有的並發事務t2從而確保沒有衝突發生，即可以檢查事務t2在其寫階段進行寫操作的對象集合與事務t1在其讀階段進行讀操作的對象集合是否重疊，如果有重疊，則中止t1。

寫階段。驗證成功以後，值可以寫入數據庫中。

簡單的正確性證明顯示樂觀並發控製可以確保事務的可串行化執行。該協議出現了很多種變體，而且由於樂觀協議在數據資源上不會產生排它鎖，因此，樂觀協議在雲計算環境中的應用越來越廣泛