一種多粒度鎖的事務并發控制算法

張 云，李 嵐

（甘肅聯合大學 電子信息工程學院，甘肅 蘭州 730000）

實時事務處理的算法主要有兩個方面，一方面是實事事務調度算法，主要是事務優先級的確定；另一方面是實時事務的事務并發控制算法，包括悲觀事務并發控制算法和樂觀事務并發控制算法兩種[1]。近年來，在事務的并發控制方面已取得了大量理論研究成果。迄今為止，許多基于鎖、樂觀、時間戳的實時數據庫并發控制方法已提出，如優先級繼承 PI（Priority Inheriting）、高優先級夭折 HPA（High Priority Abort）、優先級頂 PC（Priority Ceiling）等，但很少見有關實時內存數據庫并發控制實現技術的相關論述[2]。實時事務的并發控制實現涉及到實時數據庫的底層技術，而一般的研究和討論只是基于一定的實驗模型進行理論研究和分析。而且，對于不同的實現環境和所選擇的實現策略，實時事務所采用的并發控制技術也不盡相同。本文在研究已有的事務并發控制算法的基礎上，對悲觀事務并發控制算法2PL進行了改進。

在對算法性能測試時，根據給出的實時內存數據庫的引擎結構，開發出一個實時內存數據庫，以測試類對內存數據庫三個方面的性能進行了測試。測試分為兩次，分別為事務并發控制算法優化前和事務并發控制算法優化后。

1 實時事務的并發控制算法

內存數據庫的一個重要設計問題是并發控制，它由于既要滿足事務的時間限制還要維護數據庫的一致性而變得復雜[3]。傳統數據庫系統的并發控制協議不適合內存數據庫系統，實時事務是緊急的并且事務調度必須滿足截止期[4]。

定義1：一個調度S定義在一個事務集合T={T1，T2，...，Tn}的基礎上，它是多個事務執行的操作系列。

定義2：一個調度S中，各個事務的操作執行時不疊加（即一個接著一個發生），則這個調度是串行的。

定義3：一個調度S是可串行的，當且僅當S沖突等價于一個串行調度。這種可串行化通常稱為沖突等價可串行化。

一個并發控制器（或稱調度器）的基本功能是產生一個要執行事務的可串行化調度。多數內存數據庫系統的并發控制協議均基于串行化理論[5]。并發控制協議用于控制數據的調度，主要目標是維持數據的一致性并提供最大化的并發度[1]。在有些情況下，一致性要求可適當放寬。內存數據庫是駐留在內存中的共享數據，在不同線程中同時運行的事務之間可能由于訪問內存數據庫中的同一個數據對象而發生沖突，并發控制協議就是用來解決事務之間沖突的策略[6]。常見的沖突模式有“讀-寫”沖突和“寫-寫”沖突[7]。

“讀-寫”沖突：對同一個數據對象，一個事務正在執行“讀”操作，同時另一個事務執行“寫”操作而發生沖突；

“寫-寫”沖突：對同一個數據對象，一個事務正在執行“寫”操作，同時另一個事務也執行“寫”操作而發生沖突。

內存數據庫中的并發控制協議解決沖突的辦法主要有兩種策略：

（1）等待：終止其中一個事務引起沖突的操作，使其停留在等待狀態，直到另一個事務的操作完成為止。在內存數據庫事務并發控制的研究中，等待策略有以下三種派生方法：①不等待 （no wait）：等待的事務立即夭折，而不是等到另一個事務操作完為止。②損傷等待（wound wait）：根據每個事務的達到時間，如果要求得到數據者到達得比較早，則夭折正在使用數據的事務；否則夭折要求得到數據的事務。③等待死亡（wait die）：根據每個事務的到達時間，如果要求得到數據者到達得比較早，則該事務可以繼續等待，否則夭折這個事務。

（2）回滾：撤消事務引起沖突的操作，事務重啟，回到開始時的狀態[1]。

根據解決“讀寫”操作沖突的不同策略，并發控制算法分為悲觀并發控制協議PCC（Pessimistic Concurrency Control）和 樂 觀 并 發 控 制 協 議 OCC（Optimistic Concurrency Control）兩大類[6]。分類如圖 1所示。

圖1 并發控制算法分類圖

悲觀并發控制算法中最廣泛使用的是基于鎖（Lock）協議的算法，它為數據訪問提供數據鎖，分為讀鎖和寫鎖，讀鎖又稱共享鎖（Shared Lock），被加讀鎖的數據對象只能讀不能寫；寫鎖又稱排它鎖（Exclusive lock），被加鎖的數據對象只能被加鎖事務讀寫，其他事務不能訪問[7]。事務要獲得對數據的訪問，首先要申請得到鎖，操作完成后釋放鎖。一般操作系列為：（1）申請鎖 （Lock request）；（2）授 予 鎖 （Lock granted）； （3）數 據庫 操 作 （Database operation）；（4）結 束 操 作 （End of database operation）；（5）釋放鎖（Release locks）。

兩階段鎖 2PL（two phase lock）是悲觀并發控制協議算法的重要內容，為解決優先級倒置，派生出了高優先級法2PL-HP（也叫優先級夭折）、優先級繼承、有條件優先級繼承、數據優先級法PCP及其他衍生協議。

樂觀并發控制協議認為任何兩個并發事務請求同一個數據對象的概率很低，事務對數據庫的所有操作在請求時即可進行。樂觀并發控制協議的事務處理過程分為：讀、驗證、提交，驗證分為前向驗證和后向驗證，若在驗證階段發現沖突，則進行事務回滾。如果事務頻繁的重啟對于內存數據庫系統來說會是一個負擔并且不利于事務在截止期前完成，因此樂觀并發控制協議算法大多是圍繞如何減少事務重啟而進行改進，派生出了廣播算法 OCC-BC、WAIT-50、OCC-TI、OCC-DA、 多版本協議MCC等。

悲觀并發控制協議算法具有節約系統資源的特點，在處理時間限制比較嚴格的硬實時事務時表現優于樂觀并發控制協議，而樂觀并發控制協議有利于提高系統的并發度[8]。研究表明，2PL-HP更適合于分布式內存數據庫系統。根據流程工業大型內存數據庫系統的特點，借鑒分布式兩階段鎖協議2PL的思想，本文提出并設計了多粒度鎖的并發控制算法，其特點是減少沖突事務之間的等待時間。

2 兩階段鎖2PL

數據鎖分為讀鎖（也稱共享鎖）和寫鎖（也稱獨占鎖）：（1）共享鎖 Shared lock：只允許讀，簡稱“S 鎖”；（2）獨占鎖Exclusive lock：允許讀和修改鎖住的數據對象，簡稱“X鎖”。一般使用鎖的方式是用完即釋放，如以下代碼所示：

這種使用鎖的方式可能會導致不可串行化，而可串行化（serializability）是并發控制最普遍的正確性準則，各個事務對數據對象的操作不交叉存取（即每個事務對數據對象的操作是連續的）[9]。因為在這種方式中，當事務T1釋放鎖時，事務T2獲得了數據對象A的獨占鎖LOCK X（A）而執行 write（A）的操作，就會導致事務 T1的執行結果不正確。采用兩階段鎖來解決此問題，所謂兩階段指的是封鎖階段和解鎖階段。封鎖階段也稱為生長階段（Growing phase），事務獲得鎖并存取數據；解鎖階段也叫枯萎階段（Shrinking phase），事務的鎖不斷減少。

兩階段鎖算法的規則是：（1）如果事務T想讀 （修改）一個對象，它首先要獲得一個共享（獨占）鎖；（2）對事務已經持有的封鎖，不得重復申請；（3）一個事務必須注意到其他事務所做的封鎖；（4）每個事務分做兩段：生長期和枯萎期。生長期申請封鎖，枯萎期解除封鎖，在枯萎期不得申請新封鎖；（5）調度器在數據管理器完成對數據對象橢操作后才能釋放鎖；（6）事務結束時，解除所有封鎖。

兩階段鎖算法規則保證了事務執行的可串行化，鎖管理器LM （Lock Manager）在存取結束時即刻釋放鎖，提高了事務的并發度。但它存在的問題是可能導致級聯退出，所以需要使用嚴格 2PL（strict two-phase locking，簡稱S2PL），S2PL在數據存取完成的最后階段釋放所有鎖。

3 基于多粒度鎖的并發控制

內存數據庫中，兩階段鎖封鎖對象的大小稱為封鎖的粒度，一般情況下，加鎖的粒度越大，加鎖的次數就越少，系統資源的開銷小，事務之間沖突發生的概率就越高，系統的并發度越低；多粒度鎖封鎖就是在一個系統中同時支持多種封鎖粒度供不同的事務進行選擇。采取多粒度鎖封鎖策略，可以降低沖突發生的概率和事務的夭折數，減少事務重啟，有利于滿足事務截止期的要求，提高事務的并發度。

3.1 多粒度鎖并發控制鎖

參考關系數據庫的概念，內存數據庫中鎖的粒度可定義為：數據庫DataBase（如果多于一個庫，數據庫也可以作為粒度的元素）、表 Table、頁 Page、記錄 Record、元組Tuple。從前到后是一種順序包含的關系，展開以后其層次結構形成了一棵樹。多粒度鎖封鎖允許對樹上的每一個數據項進行封鎖。由于節點的這種包含關系，除S鎖和X鎖外，多粒度鎖鎖時需要引入以下的意向鎖：

（1）IS（Intent Share Lock）：意向共享鎖。 如果對一個數據對象加IS鎖，表示它的子結點擬加S鎖。

（2）IX（Intent Exclusive Lock）：意向排它鎖。 如果對一個數據對象加IX鎖，表示它的子結點擬加X鎖。

（3）SIX（Share Intent Exclusive Lock）：共 享 意 向 排它鎖。如果對一個數據對象加SIX鎖，表示對它加S鎖，再加IX鎖，即 SIX=S+IX。例如，對某個表加 SIX鎖，則表示該事務要讀整個表（對該表加S鎖），同時會更新個別元組（對該表加IX鎖）。

多粒度鎖鎖協議準則：

（1）從層次結構的根節點開始封鎖；

（2）子節點要獲得S或IS鎖，它的父節點必須持有IS或IX鎖；

（3）子節點要獲得X或IX或 SIX鎖，它的父節點必須持有IX或SIX鎖；

（4）必須從由底向上的順序釋放鎖。

3.2 粒度并發控制算法步驟

本文提出的多粒度鎖的并發控制協議中，采用S2PL-HP算法解決沖突。如果低優先級事務試圖申請高優先級事務持有的鎖，則阻塞優先級低的事務；如果優先級高的事務到達時申請低優先級事務持有的鎖，則將低優先級事務回滾。

兩階段鎖算法需要構造鎖管理器LM，鎖管理器管理的鎖存放在散列表（Hash Table）一類的數據結構中，數據結構中的元素可定義如下：

定 義 4：RTDB={DT1，DT2，… ，DTn}，其 中 ， DTi為 數據庫中第 i個的數據表，DTi={DR1，DR2，…，DRn}：DRj為數據表中第 j條記錄，DRj={DF1，DF2， …，DFn}；DFk為記錄中的第k個元組。

定義 5： 數 據的 全 局 標 識 為 GID=f（DB，DTi，DRj，DFk）；conflict（Ti，Tj）為 事 務 Ti和 Tj的 沖 突 ；lock （Ti，Di）表示事務Ti對數據對象Di加鎖。

LM：Lock Manager， 即 鎖 表 管 理 器 ；DM：Data Manager，即數據管理器。當事務Ti到達時，多粒度鎖并發控制算法步驟為：

（1）進行事務預分析，根據一定的算法規則計算Ti所操作的數據對象的數據標識；并填寫lock_item中的其他項；將鎖粒度lg初始化設置為table。

（2）查看鎖表管理器，找到事務Tj的數據對象ID：

①Ti和Tj不沖突，則鎖表管理器將Ti的信息加入鎖表中，lock（Ti，Di），轉到第（3）步；

②如果 Ti和 Tj發生沖突，若它們的鎖類型相容，則鎖表管理器將Ti的trans_id加入向量中，轉到第（3）步；

③如果鎖粒度是元組，即最小加鎖粒度，則跳到第（5）步，否則調整 Ti和 Tj的加鎖粒度，并返回第（2）步；

（3）處理事務，調用數據管理器進行數據讀寫操作；

（4）數據管理器處理完畢，鎖表管理器更新對應鎖表中的信息，跳到第（6）步；

（5）如果有沖突發生，調用S2PL—HP算法規則解決沖突；

（6）結束。

4 算法測試

4.1 內存數據庫引擎結構設計

內存數據庫 Engine是內存數據庫的核心，它對實時/歷史數據進行管理，它的本質是一個實時事務處理器。

關系型數據庫采用二維關系表來進行數據的存儲，基于磁盤的存儲結構，數據存取過程中要進行頻繁的磁盤I/O操作。由于磁盤I/O操作時間不確定性，要引入內存數據庫中是不現實的。內存數據庫將實時數據常駐內存，訪問實時數據時無需進行I/O操作，保證了運行速度，有利于滿足實時事務截止期的要求。

4.2 事務并發控制優化算法測試結果

測試系統環境為：Win7+JDK+NetBeans6.7。

事務并發控制算法優化前測試結果如圖2所示。

事務并發控制算法優化后測試結果如圖3所示。

與傳統數據庫不同，內存數據庫系統事務的并發擦控制除需保證共享數據的一致性外，還要考慮事務的定時限制。因此，其并發控制機制比傳統數據庫要復雜。本文給出了一個基于多粒度鎖的并發控制機制，通過驗證，該方法成功且有效地解決了內存數據庫的事務并發問題。從內存數據庫的測試結果可知，算法優化后系統的各項性能都有所提升，證明了算法優化的可行性和必要性。

[1]納永良.大型實時數據庫關鍵技術及應用研究 [D].北京：北京化工大學，2010.

[2]祁鑫，王文海.內存數據庫系統并發控制機制綜述[J].計算機技術，2006.33（1）：47-50.

[3]陳小艷.嵌入式主動內存數據庫 ARTs.EDB的并發控制[D].武漢：華中科技人學，2009.

[4]桑楠.嵌入式應用原理及應用開發技術[M].北京：北京航空航天大學出版社，2003.

[5]夏家莉.嵌入式數據庫系統中無沖突并發控制協議CCCP[J].計算機研究與發展，2004，41（11）：1936-1941.

[6]廖國瓊，劉云生，等.嵌入式內存數據庫事務的并發控制[J].計算機工程，2005（9）.

[7]趙文潔.基于OPC技術的實時數據庫的研究與設計[D].太原：太原理工大學，2007.

[8]廖國瓊，劉云生，等.嵌入式實時數據庫事務的并發控制[J].計算機工程，2005，32（5）：12－18.

[9]LAM K W，LAM K Y，HUNG S L.Optimistic concurrency controlprotocol for real-time databases [J]. SYSTEMS SOFTWARE， 2007，11：34-39.