摘  要： 研究了一種基于多粒度鎖的并發(fā)控制算法，包括其多粒度鎖鎖,、鎖表數(shù)據結構及鎖操作的算法步驟,。算法可以降低沖突發(fā)生的概率和事務的夭折數(shù)，減少事務重啟,，有利于滿足事務截止期的要求,，提高事務的并發(fā)度。在驗證算法有效性時,，通過測試類對內存數(shù)據庫記錄的插入速度,、索引查找的速度、記錄的刪除速度三方面的性能進行了測試,，結果表明,，事務并發(fā)控制優(yōu)化算法對內存數(shù)據庫性能的提升是有效可行的。
關鍵詞： 內存數(shù)據庫,；實時事務,；算法；并發(fā)控制,；粒度

　實時事務處理的算法主要有兩個方面,，一方面是實事事務調度算法，主要是事務優(yōu)先級的確定,；另一方面是實時事務的事務并發(fā)控制算法,，包括悲觀事務并發(fā)控制算法和樂觀事務并發(fā)控制算法兩種[1]。近年來,，在事務的并發(fā)控制方面已取得了大量理論研究成果,。迄今為止，許多基于鎖、樂觀,、時間戳的實時數(shù)據庫并發(fā)控制方法已提出，如優(yōu)先級繼承PI（Priority Inheriting）,、高優(yōu)先級夭折HPA（High Priority Abort）,、優(yōu)先級頂PC（Priority Ceiling）等，但很少見有關實時內存數(shù)據庫并發(fā)控制實現(xiàn)技術的相關論述[2],。實時事務的并發(fā)控制實現(xiàn)涉及到實時數(shù)據庫的底層技術,，而一般的研究和討論只是基于一定的實驗模型進行理論研究和分析。而且,，對于不同的實現(xiàn)環(huán)境和所選擇的實現(xiàn)策略,，實時事務所采用的并發(fā)控制技術也不盡相同。本文在研究已有的事務并發(fā)控制算法的基礎上,，對悲觀事務并發(fā)控制算法2PL進行了改進,。
　在對算法性能測試時，根據給出的實時內存數(shù)據庫的引擎結構,，開發(fā)出一個實時內存數(shù)據庫,，以測試類對內存數(shù)據庫三個方面的性能進行了測試。測試分為兩次,，分別為事務并發(fā)控制算法優(yōu)化前和事務并發(fā)控制算法優(yōu)化后,。
1 實時事務的并發(fā)控制算法
　內存數(shù)據庫的一個重要設計問題是并發(fā)控制，它由于既要滿足事務的時間限制還要維護數(shù)據庫的一致性而變得復雜[3],。傳統(tǒng)數(shù)據庫系統(tǒng)的并發(fā)控制協(xié)議不適合內存數(shù)據庫系統(tǒng),，實時事務是緊急的并且事務調度必須滿足截止期[4]。
　定義1：一個調度S定義在一個事務集合T={T1,，T2,，．．．，Tn}的基礎上,，它是多個事務執(zhí)行的操作系列,。
　定義2：一個調度S中，各個事務的操作執(zhí)行時不疊加（即一個接著一個發(fā)生）,，則這個調度是串行的,。
　定義3：一個調度S是可串行的，當且僅當S沖突等價于一個串行調度,。這種可串行化通常稱為沖突等價可串行化,。
　一個并發(fā)控制器（或稱調度器）的基本功能是產生一個要執(zhí)行事務的可串行化調度。多數(shù)內存數(shù)據庫系統(tǒng)的并發(fā)控制協(xié)議均基于串行化理論[5],。并發(fā)控制協(xié)議用于控制數(shù)據的調度,，主要目標是維持數(shù)據的一致性并提供最大化的并發(fā)度[1]。在有些情況下，一致性要求可適當放寬,。內存數(shù)據庫是駐留在內存中的共享數(shù)據,，在不同線程中同時運行的事務之間可能由于訪問內存數(shù)據庫中的同一個數(shù)據對象而發(fā)生沖突，并發(fā)控制協(xié)議就是用來解決事務之間沖突的策略[6],。常見的沖突模式有“讀-寫”沖突和“寫-寫”沖突[7],。
　“讀-寫”沖突：對同一個數(shù)據對象，一個事務正在執(zhí)行“讀”操作,，同時另一個事務執(zhí)行“寫”操作而發(fā)生沖突,；
　“寫-寫”沖突：對同一個數(shù)據對象，一個事務正在執(zhí)行“寫”操作,，同時另一個事務也執(zhí)行“寫”操作而發(fā)生沖突,。
　內存數(shù)據庫中的并發(fā)控制協(xié)議解決沖突的辦法主要有兩種策略：
　（1）等待：終止其中一個事務引起沖突的操作,，使其停留在等待狀態(tài),，直到另一個事務的操作完成為止。在內存數(shù)據庫事務并發(fā)控制的研究中,，等待策略有以下三種派生方法：①不等待（no wait）：等待的事務立即夭折,，而不是等到另一個事務操作完為止。②損傷等待（wound wait）：根據每個事務的達到時間,，如果要求得到數(shù)據者到達得比較早,，則夭折正在使用數(shù)據的事務；否則夭折要求得到數(shù)據的事務,。③等待死亡（wait die）：根據每個事務的到達時間,，如果要求得到數(shù)據者到達得比較早，則該事務可以繼續(xù)等待,，否則夭折這個事務,。
　（2）回滾：撤消事務引起沖突的操作,，事務重啟,，回到開始時的狀態(tài)[1]。
　根據解決“讀寫”操作沖突的不同策略,，并發(fā)控制算法分為悲觀并發(fā)控制協(xié)議PCC（Pessimistic Concurrency Control）和樂觀并發(fā)控制協(xié)議OCC（Optimistic Concurrency Control）兩大類[6],。分類如圖１所示。

　 悲觀并發(fā)控制算法中最廣泛使用的是基于鎖（Lock）協(xié)議的算法,，它為數(shù)據訪問提供數(shù)據鎖,，分為讀鎖和寫鎖，讀鎖又稱共享鎖（Shared Lock）,，被加讀鎖的數(shù)據對象只能讀不能寫,；寫鎖又稱排它鎖（Exclusive lock）,，被加鎖的數(shù)據對象只能被加鎖事務讀寫，其他事務不能訪問[7],。事務要獲得對數(shù)據的訪問,，首先要申請得到鎖，操作完成后釋放鎖,。一般操作系列為：（1）申請鎖（Lock request）,；（2）授予鎖（Lock granted）；（3）數(shù)據庫操作（Database operation）,；（4）結束操作（End of database operation）；（5）釋放鎖（Release locks）,。
　兩階段鎖2PL（two phase lock）是悲觀并發(fā)控制協(xié)議算法的重要內容,，為解決優(yōu)先級倒置，派生出了高優(yōu)先級法2PL-HP（也叫優(yōu)先級夭折）,、優(yōu)先級繼承,、有條件優(yōu)先級繼承、數(shù)據優(yōu)先級法PCP及其他衍生協(xié)議,。
　樂觀并發(fā)控制協(xié)議認為任何兩個并發(fā)事務請求同一個數(shù)據對象的概率很低,，事務對數(shù)據庫的所有操作在請求時即可進行。樂觀并發(fā)控制協(xié)議的事務處理過程分為：讀,、驗證,、提交，驗證分為前向驗證和后向驗證,，若在驗證階段發(fā)現(xiàn)沖突,，則進行事務回滾。如果事務頻繁的重啟對于內存數(shù)據庫系統(tǒng)來說會是一個負擔并且不利于事務在截止期前完成,，因此樂觀并發(fā)控制協(xié)議算法大多是圍繞如何減少事務重啟而進行改進,，派生出了廣播算法OCC-BC、WAIT-50,、OCC-TI,、OCC-DA、多版本協(xié)議MCC等,。
　悲觀并發(fā)控制協(xié)議算法具有節(jié)約系統(tǒng)資源的特點,，在處理時間限制比較嚴格的硬實時事務時表現(xiàn)優(yōu)于樂觀并發(fā)控制協(xié)議，而樂觀并發(fā)控制協(xié)議有利于提高系統(tǒng)的并發(fā)度[8],。研究表明,，2PL-HP更適合于分布式內存數(shù)據庫系統(tǒng)。根據流程工業(yè)大型內存數(shù)據庫系統(tǒng)的特點,，借鑒分布式兩階段鎖協(xié)議2PL的思想,，本文提出并設計了多粒度鎖的并發(fā)控制算法，其特點是減少沖突事務之間的等待時間。
2 兩階段鎖2PL
　數(shù)據鎖分為讀鎖（也稱共享鎖）和寫鎖（也稱獨占鎖）：（1）共享鎖Shared lock：只允許讀,，簡稱“S鎖”,；（2）獨占鎖Exclusive lock：允許讀和修改鎖住的數(shù)據對象，簡稱“X鎖”,。一般使用鎖的方式是用完即釋放,，如以下代碼所示：
　LOCK  S（A）； //對數(shù)據對象A加共享鎖
　read（A）,； //讀數(shù)據對象A
　UNLOCK（A）,；//釋放鎖
　LOCK  S（B）； //對數(shù)據對象B加共享鎖
　read（B）,； //讀數(shù)據對象B
　UNLOCK（B）,； //釋放鎖
　display（A+B）； //顯示結果
　這種使用鎖的方式可能會導致不可串行化,，而可串行化（serializability）是并發(fā)控制最普遍的正確性準則,，各個事務對數(shù)據對象的操作不交叉存取（即每個事務對數(shù)據對象的操作是連續(xù)的）[9],。因為在這種方式中,，當事務T1釋放鎖時，事務T2獲得了數(shù)據對象A的獨占鎖LOCK  X（A）而執(zhí)行write（A）的操作,，就會導致事務T1的執(zhí)行結果不正確,。采用兩階段鎖來解決此問題，所謂兩階段指的是封鎖階段和解鎖階段,。封鎖階段也稱為生長階段（Growing phase）,，事務獲得鎖并存取數(shù)據；解鎖階段也叫枯萎階段（Shrinking phase）,，事務的鎖不斷減少,。
　兩階段鎖算法的規(guī)則是：（1）如果事務T想讀（修改）一個對象，它首先要獲得一個共享（獨占）鎖,；（2）對事務已經持有的封鎖,，不得重復申請；（3）一個事務必須注意到其他事務所做的封鎖,；（4）每個事務分做兩段：生長期和枯萎期,。生長期申請封鎖，枯萎期解除封鎖,，在枯萎期不得申請新封鎖,；（5）調度器在數(shù)據管理器完成對數(shù)據對象橢操作后才能釋放鎖；（6）事務結束時,，解除所有封鎖,。
　兩階段鎖算法規(guī)則保證了事務執(zhí)行的可串行化,，鎖管理器LM （Lock Manager）在存取結束時即刻釋放鎖，提高了事務的并發(fā)度,。但它存在的問題是可能導致級聯(lián)退出,，所以需要使用嚴格2PL（strict two-phase locking，簡稱S2PL）,， S2PL在數(shù)據存取完成的最后階段釋放所有鎖,。
3 基于多粒度鎖的并發(fā)控制
　內存數(shù)據庫中，兩階段鎖封鎖對象的大小稱為封鎖的粒度,，一般情況下,，加鎖的粒度越大，加鎖的次數(shù)就越少,，系統(tǒng)資源的開銷小,，事務之間沖突發(fā)生的概率就越高，系統(tǒng)的并發(fā)度越低,；多粒度鎖封鎖就是在一個系統(tǒng)中同時支持多種封鎖粒度供不同的事務進行選擇。采取多粒度鎖封鎖策略,，可以降低沖突發(fā)生的概率和事務的夭折數(shù),，減少事務重啟，有利于滿足事務截止期的要求,，提高事務的并發(fā)度,。
3.1 多粒度鎖并發(fā)控制鎖
　參考關系數(shù)據庫的概念，內存數(shù)據庫中鎖的粒度可定義為：數(shù)據庫DataBase （如果多于一個庫,，數(shù)據庫也可以作為粒度的元素）,、表Table、頁Page,、記錄Record,、元組Tuple。從前到后是一種順序包含的關系,，展開以后其層次結構形成了一棵樹,。多粒度鎖封鎖允許對樹上的每一個數(shù)據項進行封鎖。由于節(jié)點的這種包含關系,，除S鎖和X鎖外,，多粒度鎖鎖時需要引入以下的意向鎖：
　（1）IS（Intent Share Lock）：意向共享鎖,。如果對一個數(shù)據對象加IS鎖,，表示它的子結點擬加S鎖。
?。?）IX（Intent Exclusive Lock）：意向排它鎖,。如果對一個數(shù)據對象加IX鎖,，表示它的子結點擬加X鎖。
?。?）SIX（Share Intent Exclusive Lock）：共享意向排它鎖,。如果對一個數(shù)據對象加SIX鎖，表示對它加S鎖,，再加IX鎖,，即SIX=S+IX。例如,，對某個表加SIX鎖,，則表示該事務要讀整個表（對該表加S鎖），同時會更新個別元組（對該表加IX鎖）,。
多粒度鎖鎖協(xié)議準則：
?。?）從層次結構的根節(jié)點開始封鎖；
?。?）子節(jié)點要獲得S或IS鎖,，它的父節(jié)點必須持有IS或IX鎖；
?。?）子節(jié)點要獲得X或IX或SIX鎖,，它的父節(jié)點必須持有IX或SIX鎖；
?。?）必須從由底向上的順序釋放鎖,。
3.2 粒度并發(fā)控制算法步驟
　本文提出的多粒度鎖的并發(fā)控制協(xié)議中，采用S2PL-HP算法解決沖突,。如果低優(yōu)先級事務試圖申請高優(yōu)先級事務持有的鎖,，則阻塞優(yōu)先級低的事務；如果優(yōu)先級高的事務到達時申請低優(yōu)先級事務持有的鎖,，則將低優(yōu)先級事務回滾,。
　兩階段鎖算法需要構造鎖管理器LM，鎖管理器管理的鎖存放在散列表（Hash Table）一類的數(shù)據結構中,，數(shù)據結構中的元素可定義如下：
typedef lock_type{
DATAID data_id： //被鎖定的數(shù)據對象ID
vector trans_id,； //持有鎖的事務ID向量
int lt：//鎖類型：S、X,、1S,、IX，SIX
int lg,；//鎖粒度：db,，table，page,，record,，Tuple
}lock_item
　定義4：RTDB={DT1,，DT2，…,，DTn},，其中， DTi為數(shù)據庫中第i個的數(shù)據表,，DTi={DR1,，DR2，…,，DRn}：DRj為數(shù)據表中第j條記錄,，DRj={DF1，DF2,，…,，DFn}；DFk為記錄中的第k個元組,。
　定義5：數(shù)據的全局標識為GID=f（DB,，DTi，DRj,，DFk）,；conflict（Ti，Tj）為事務Ti和Tj的沖突,；lock（Ti，Di）表示事務Ti對數(shù)據對象Di加鎖,。
LM：Lock Manager,，即鎖表管理器；DM：Data Manager,，即數(shù)據管理器,。當事務Ti到達時，多粒度鎖并發(fā)控制算法步驟為：
?。?）進行事務預分析,，根據一定的算法規(guī)則計算Ti所操作的數(shù)據對象的數(shù)據標識；并填寫lock_item中的其他項,；將鎖粒度lg初始化設置為table,。
　（2）查看鎖表管理器,，找到事務Tj的數(shù)據對象ID：
?、賂i和Tj不沖突，則鎖表管理器將Ti的信息加入鎖表中,，lock（Ti,，Di）,，轉到第（3）步；
?、谌绻鸗i和Tj發(fā)生沖突,，若它們的鎖類型相容，則鎖表管理器將Ti的trans_id加入向量中,，轉到第（3）步,；
　③如果鎖粒度是元組,，即最小加鎖粒度,，則跳到第（5）步，否則調整Ti和Tj的加鎖粒度,，并返回第（2）步,；
　（3）處理事務,，調用數(shù)據管理器進行數(shù)據讀寫操作,；
（4）數(shù)據管理器處理完畢，鎖表管理器更新對應鎖表中的信息,，跳到第（6）步,；
（5）如果有沖突發(fā)生，調用S2PL—HP算法規(guī)則解決沖突,；
（6）結束,。
4 算法測試
4.1 內存數(shù)據庫引擎結構設計
　內存數(shù)據庫 Engine是內存數(shù)據庫的核心，它對實時/歷史數(shù)據進行管理,，它的本質是一個實時事務處理器,。
　關系型數(shù)據庫采用二維關系表來進行數(shù)據的存儲，基于磁盤的存儲結構,，數(shù)據存取過程中要進行頻繁的磁盤I/O操作,。由于磁盤I/O操作時間不確定性，要引入內存數(shù)據庫中是不現(xiàn)實的,。內存數(shù)據庫將實時數(shù)據常駐內存,，訪問實時數(shù)據時無需進行I/O操作，保證了運行速度,，有利于滿足實時事務截止期的要求,。
4.2 事務并發(fā)控制優(yōu)化算法測試結果
　測試系統(tǒng)環(huán)境為：Win7+JDK+NetBeans6.7。
　事務并發(fā)控制算法優(yōu)化前測試結果如圖2所示,。

　事務并發(fā)控制算法優(yōu)化后測試結果如圖3所示,。

　與傳統(tǒng)數(shù)據庫不同，內存數(shù)據庫系統(tǒng)事務的并發(fā)擦控制除需保證共享數(shù)據的一致性外,，還要考慮事務的定時限制,。因此,，其并發(fā)控制機制比傳統(tǒng)數(shù)據庫要復雜。本文給出了一個基于多粒度鎖的并發(fā)控制機制,，通過驗證,，該方法成功且有效地解決了內存數(shù)據庫的事務并發(fā)問題。從內存數(shù)據庫的測試結果可知,，算法優(yōu)化后系統(tǒng)的各項性能都有所提升,，證明了算法優(yōu)化的可行性和必要性。
參考文獻
[1] 納永良．大型實時數(shù)據庫關鍵技術及應用研究[D]．北京：北京化工大學,，2010．
[2] 祁鑫,，王文海．內存數(shù)據庫系統(tǒng)并發(fā)控制機制綜述[J]．計算機技術，2006．33（1）：47-50.
[3] 陳小艷．嵌入式主動內存數(shù)據庫ARTs．EDB的并發(fā)控制[D]．武漢：華中科技人學,，2009.
[4] 桑楠．嵌入式應用原理及應用開發(fā)技術[M]．北京：北京航空航天大學出版社,，2003.
[5] 夏家莉．嵌入式數(shù)據庫系統(tǒng)中無沖突并發(fā)控制協(xié)議CCCP[J]．計算機研究與發(fā)展，2004,，41（11）：1936-1941.
[6] 廖國瓊,，劉云生，等．嵌入式內存數(shù)據庫事務的并發(fā)控制[J]．計算機工程,，2005（9）.
[7] 趙文潔．基于OPC技術的實時數(shù)據庫的研究與設計[D]．太原：太原理工大學,，2007．
[8] 廖國瓊，劉云生,，等．嵌入式實時數(shù)據庫事務的并發(fā)控制[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.