一種并發(fā)控制的自優(yōu)化模型

摘 要：自主管理是目前數(shù)據(jù)庫系統(tǒng)亟待解決的重要問題之一，解決數(shù)據(jù)庫系統(tǒng)自主管理的核心是使得系統(tǒng)能夠自動調(diào)度資源，以達(dá)到系統(tǒng)運(yùn)行的目標(biāo)。提出一個數(shù)據(jù)庫系統(tǒng)并發(fā)控制的自主優(yōu)化模型NDACC，該模型能夠準(zhǔn)確預(yù)測運(yùn)行時系統(tǒng)的數(shù)據(jù)沖突率，并對數(shù)據(jù)訪問進(jìn)行控制，從而有效地提高資源利用率，增強(qiáng)系統(tǒng)的穩(wěn)定性。

關(guān)鍵詞：并發(fā)控制； 事務(wù)管理； 自主管理

中圖法分類號：TP311．11 文獻(xiàn)標(biāo)識碼：A 文章編號：1001-3695(2006)10-0033-03

Selfoptimization Model for Concurrency Control

SHI Lei， BAI Wenyang

(State Key Laboratory of Novel Software Technology， Dept. of Computer Science Technology， Nanjing University， Nanjing Jiangsu 210093， China)

Abstract:Self management is a currently critical problem of database management system. The key solution to self management is to make database system manage itself and use its resources effectively. This paper proposes a selfoptimization model of concurrency control which will make your database system more intelligent， powerful and costless by predicting and controlling the data conflict ratio.

Key words:Concurrency Control; Transaction Management; Self Management

1 引言

數(shù)據(jù)庫技術(shù)的發(fā)展推動了企業(yè)傳統(tǒng)經(jīng)營模式的轉(zhuǎn)變，提高了企業(yè)的運(yùn)作效率；同時，競爭的日益激烈又要求企業(yè)能夠反應(yīng)迅速、隨需而變、節(jié)約成本。數(shù)據(jù)庫系統(tǒng)作為企業(yè)應(yīng)用的核心，在這場變革中起著至關(guān)重要的作用。計(jì)算機(jī)技術(shù)的不斷進(jìn)步使得計(jì)算機(jī)硬件和軟件本身的價格逐漸降低，同時數(shù)據(jù)庫管理系統(tǒng)的規(guī)模越來越大，復(fù)雜度越來越高，能夠操作管理這些系統(tǒng)的專業(yè)人員越來越少，價格也越來越高，花在人力資源上的費(fèi)用逐漸成為部署電子商務(wù)應(yīng)用的主要支出。為了更好地增強(qiáng)數(shù)據(jù)庫系統(tǒng)的穩(wěn)定性，減少數(shù)據(jù)庫系統(tǒng)的維護(hù)費(fèi)用，實(shí)現(xiàn)數(shù)據(jù)庫系統(tǒng)的自我管理能力成為解決這個問題的關(guān)鍵。自我管理有幾個明顯的優(yōu)點(diǎn)：簡化管理任務(wù)、降低管理費(fèi)用、自動調(diào)度系統(tǒng)資源、優(yōu)化配置。

數(shù)據(jù)庫系統(tǒng)自主管理的核心是使得系統(tǒng)能夠自動調(diào)度資源，以達(dá)到系統(tǒng)運(yùn)行的目標(biāo)。并發(fā)控制的自主優(yōu)化是實(shí)現(xiàn)數(shù)據(jù)庫自主管理的重要內(nèi)容。并發(fā)控制是事務(wù)并發(fā)執(zhí)行的一種調(diào)度和控制手段，它可以保證并發(fā)執(zhí)行的事務(wù)間相互隔離、互不干擾，從而保證并發(fā)事務(wù)的正確執(zhí)行。目前，流行的數(shù)據(jù)庫管理系統(tǒng)的并發(fā)控制策略主要是依賴數(shù)據(jù)庫管理員的控制，其調(diào)度策略不夠靈活，不能隨需而變，在負(fù)載過高時可能導(dǎo)致系統(tǒng)響應(yīng)時間變慢，性能下降。

基于通用的事務(wù)管理模型，本文提出一種并發(fā)控制的自主優(yōu)化模型NDACC，該模型在原有模型基礎(chǔ)上增加了一個自優(yōu)化模塊DCC對并發(fā)事務(wù)進(jìn)行管理。

2 并發(fā)控制的自優(yōu)化模型NDACC

并發(fā)控制是事務(wù)并發(fā)執(zhí)行的一種調(diào)度和控制手段，它可以保證并發(fā)執(zhí)行的事務(wù)間相互隔離、互不干擾，從而保證并發(fā)事務(wù)的正確執(zhí)行。在并發(fā)控制技術(shù)中，通常采用三種可串行化方法，即封鎖、時間戳、有效性確認(rèn)，而封鎖是在保證數(shù)據(jù)庫可串行化機(jī)制中最常用的方法。目前普遍使用的是兩階段封鎖(2PL)協(xié)議，它要求在每個事務(wù)中，所有封鎖請求必須先于所有解鎖請求。兩階段就是指封鎖請求的第一階段和解鎖請求的第二階段。

實(shí)現(xiàn)并發(fā)控制的自主優(yōu)化就是在原有并發(fā)控制模型的基礎(chǔ)上增加一個反饋環(huán)路，在該環(huán)路中置入一個沖突控制器，負(fù)責(zé)收集系統(tǒng)的運(yùn)行參數(shù)，并根據(jù)這些參數(shù)決定是否對系統(tǒng)的并發(fā)策略作出調(diào)整。沖突控制器是該環(huán)路的核心組件，怎樣選擇有效的參數(shù)并進(jìn)行有效的計(jì)算又是實(shí)現(xiàn)該沖突控制器的關(guān)鍵。

有效的控制事務(wù)沖突是事務(wù)管理的關(guān)鍵問題。目前大多數(shù)數(shù)據(jù)庫系統(tǒng)都是采取由數(shù)據(jù)庫管理員手動設(shè)定多事務(wù)級別（Degree of MultiProgramming，DMP）的方法。DMP是指系統(tǒng)允許并發(fā)執(zhí)行事務(wù)的最大數(shù)目。手動設(shè)定DMP的方法有兩個主要缺點(diǎn)：①如果DMP值過高，超出了系統(tǒng)的正常處理能力，則系統(tǒng)可能出現(xiàn)過多的事務(wù)沖突，從而導(dǎo)致事務(wù)因競爭資源而不斷地放棄、回滾和重啟，這樣系統(tǒng)資源被浪費(fèi)在處理事務(wù)的放棄、回滾和重啟上，而不能進(jìn)行有效的事務(wù)處理；相反，如果DMP值過低，又會使得很多事務(wù)沒有必要地置于等待隊(duì)列中，導(dǎo)致平均響應(yīng)時間變長，系統(tǒng)資源不能得到充分利用。②管理員設(shè)定DMP值后，DMP值在一段時間內(nèi)是穩(wěn)定不變的，對于不斷變化的數(shù)據(jù)庫訪問負(fù)載，系統(tǒng)不能根據(jù)實(shí)際情況調(diào)整并發(fā)策略。要解決上述問題，就必須找到一個合理的事務(wù)準(zhǔn)入策略，既不能準(zhǔn)入過多的事務(wù)而導(dǎo)致上面的問題，也不能阻止過多的事務(wù)而使得資源閑置。數(shù)據(jù)沖突率（Data Conflict Ratio，DCR）[1，6]已被證明是有效判斷事務(wù)沖突是否適量的一個重要指標(biāo)。定義DCR的計(jì)算方法如下：

DCR=#locks held by all transactions#locks held by active(unblocked)transactions（1）

通常在不考慮事務(wù)的長度和持有鎖的數(shù)目時選擇DCR的閾值為1．3[1]。文獻(xiàn)[2~4]通過大量的實(shí)驗(yàn)證明了在通常情況下，當(dāng)DCR＜1．3時系統(tǒng)能夠正常運(yùn)行；當(dāng)DCR≥1．3時系統(tǒng)就很容易出現(xiàn)因事務(wù)沖突引起的性能下降。

采用DCR作為控制參數(shù)的一個并發(fā)控制的自主優(yōu)化模型如圖1所示。該模型在原有調(diào)度器之上增加了一個數(shù)據(jù)沖突管理器（Data Contention Control，DCC），沖突管理器是該模型的核心組件。事務(wù)請求經(jīng)系統(tǒng)入口進(jìn)入事務(wù)管理器，首先被傳遞給沖突管理器，然后才交給調(diào)度器。例如，一個新的事務(wù)請求到達(dá)事務(wù)管理器，事務(wù)管理器將該請求交給沖突管理器，沖突管理器檢查當(dāng)前系統(tǒng)的DCR值：如果DCR＜1．3，則直接將該請求遞交給調(diào)度器；如果DCR≥1．3，則將事務(wù)請求置于等待隊(duì)列等待處理。當(dāng)循環(huán)檢測到DCR值再次小于1.3時，事務(wù)管理器可以接收新的事務(wù)請求，并優(yōu)先處理等待隊(duì)列中的事務(wù)請求。

3 DCC的實(shí)現(xiàn)模型

沖突管理器是并發(fā)控制的自優(yōu)化模型中最關(guān)鍵的組件。DCC的實(shí)現(xiàn)模型如圖2所示。

DCC包含兩個輸入?yún)?shù)，即DCR閾值1．3和系統(tǒng)的DCR值。定義ε=1．3-DCR，ε作為計(jì)算結(jié)果傳遞給DCC。當(dāng)ε＞0時，直接將事務(wù)請求遞交給調(diào)度器；當(dāng)ε≤0時，則將事務(wù)請求置于事務(wù)請求隊(duì)列中。

沖突管理器的實(shí)現(xiàn)有一個很重要的問題就是怎樣選擇合適的計(jì)算DCR的時間間隔。如果時間間隔太長，系統(tǒng)就不能夠?qū)ω?fù)載的迅速變化及時作出調(diào)整；間隔太短，則DCR的計(jì)算過于頻繁，有可能受噪音干擾，甚至引起不必要的系統(tǒng)資源浪費(fèi)。目前有兩種比較可行的方法[5]：①當(dāng)一個事務(wù)處理完畢時計(jì)算DCR值；②由數(shù)據(jù)庫管理員設(shè)定一個固定的時間間隔進(jìn)行DCR值的計(jì)算。在下面的實(shí)現(xiàn)步驟中我們選擇第②種方法，每1s計(jì)算一次DCR。

沖突管理器的實(shí)現(xiàn)步驟如下：

(1)檢測DCC內(nèi)部的事務(wù)請求隊(duì)列是否有事務(wù)請求等待，無則轉(zhuǎn)(2)，有則轉(zhuǎn)(3)；

(2)檢測系統(tǒng)入口是否有事務(wù)請求等待，無則轉(zhuǎn)(1)，有則轉(zhuǎn)(3)；

(3)DCC檢查器檢查ε值是否大于0，如果大于0，則轉(zhuǎn)(4)，否則轉(zhuǎn)(6);

(4)DCC檢查器將事務(wù)請求遞交給調(diào)度器，由調(diào)度器分配資源并執(zhí)行事務(wù)；

(5)事務(wù)執(zhí)行完畢后，將結(jié)果反饋給DCC并觸發(fā)計(jì)時器，如果已過1s則重新計(jì)算DCR值和ε值，否則不作任何處理，轉(zhuǎn)(1)；

(6)DCC檢查器將事務(wù)請求置入請求隊(duì)列中等待處理，轉(zhuǎn)(1)。

4 改進(jìn)的DCC實(shí)現(xiàn)模型

前面所實(shí)現(xiàn)的DCC模型是假設(shè)所有的事務(wù)長度均是一致的，但實(shí)際的數(shù)據(jù)庫應(yīng)用中事務(wù)的特征是各不相同的。如果某個時刻DCR已經(jīng)十分接近于1．3，此時有一個將申請很多排他鎖的Update事務(wù)請求等待處理。按照上述DCC的實(shí)現(xiàn)方法，當(dāng)DCR＜1．3時準(zhǔn)入該事務(wù)，但由于該事務(wù)需要請求很多的排他鎖，沖突率將增高，從而又會導(dǎo)致事務(wù)的取消和重啟。在這種情況下，就要求DCC控制器能夠預(yù)測并推遲該事務(wù)的準(zhǔn)入時間。下面將討論一種改進(jìn)的DCC實(shí)現(xiàn)模型，該模型能較好地預(yù)測并處理復(fù)雜事務(wù)。

4．1 DCR的預(yù)測方法

首先我們定義以下幾個參數(shù)，并假定它們是可知的。

D：數(shù)據(jù)庫所擁有的鎖數(shù)目。

L：當(dāng)前所有事務(wù)持有鎖數(shù)目，包括活動的和非活動的。

A：當(dāng)前所有活動事務(wù)持有鎖數(shù)目。

n：當(dāng)前系統(tǒng)中正在執(zhí)行的事務(wù)數(shù)目。

li：事務(wù)i的長度，即事務(wù)i成功執(zhí)行需要占用的鎖數(shù)目，第4．2節(jié)將討論li的預(yù)測方法。

基于以上這些可知的參數(shù)，我們引入一種啟發(fā)式方法對事務(wù)進(jìn)行預(yù)測，式（2）定義了如果DCC準(zhǔn)入新的事務(wù)Tn+1，則該事務(wù)被調(diào)度器阻止的可能性Pn+1：

Pn+1=1-∏ln+1-1k=0D-L-kD-k（2）

基于式（2）的結(jié)論，我們可以重新計(jì)算DCR的值DCR′：

DCR′=L+ln+1A+(1-Pn+1)·ln+1（3）

新的啟發(fā)式方法可以有效地預(yù)測將來的DCR值，從而避免在系統(tǒng)資源有限時準(zhǔn)入復(fù)雜事務(wù)而導(dǎo)致沖突增長。

4．2 事務(wù)長度預(yù)測

在以上的DCR預(yù)測方法中，D，L，A，n均是系統(tǒng)可知的，但新進(jìn)事務(wù)的長度ln+1是現(xiàn)有系統(tǒng)不可知的，所以必須找到一種方法能夠有效地預(yù)測新進(jìn)事務(wù)的長度。為了預(yù)測新進(jìn)事務(wù)的長度，我們在圖2的基礎(chǔ)上引入一個統(tǒng)計(jì)模塊，如圖3所示。

該統(tǒng)計(jì)模塊統(tǒng)計(jì)事務(wù)執(zhí)行的歷史信息，進(jìn)而預(yù)測新進(jìn)事務(wù)的可能長度。統(tǒng)計(jì)預(yù)測方法是基于這樣一個事實(shí)：數(shù)據(jù)庫系統(tǒng)在一定的應(yīng)用場景下，事務(wù)的種類和數(shù)目均是有限的，它們所訪問的資源在短時間內(nèi)變化也是很小的。統(tǒng)計(jì)歷史信息的一種方法是記錄每次事務(wù)執(zhí)行的數(shù)據(jù)，用作預(yù)測分析，但該方法是不現(xiàn)實(shí)的，因?yàn)榇鎯v史數(shù)據(jù)需要寫磁盤，讀取歷史數(shù)據(jù)又需要讀磁盤，這種磁盤的I/O開銷將對性能產(chǎn)生很大的影響。本文提出一種基于Hash表的統(tǒng)計(jì)方法：

Lkey=Hash(key)·p+l·(1-p)（4）

其中，key是Hash關(guān)鍵字，Lkey是調(diào)整后的事務(wù)長度，Hash(key)是關(guān)鍵字為key的Hash值，代表該事務(wù)的歷史長度；l是最后提交事務(wù)的長度，代表該事務(wù)的最新長度；p用于調(diào)控歷史長度與最新長度所占的比重。式（4）在歷史事務(wù)長度和最新事務(wù)長度間按一定比例計(jì)算Lkey值，既考慮了歷史信息的平均表現(xiàn)，又兼顧了表數(shù)據(jù)不斷變化引起的事務(wù)長度改變。在初步的實(shí)驗(yàn)中，我們選擇p=0．5，這只是一個直觀的估計(jì)，其最佳值如何還需要進(jìn)行大量的實(shí)驗(yàn)來確定。

Hash表關(guān)鍵字key的選擇是式（4）中最重要的部分，它代表著一個事務(wù)的長度，所以它必須唯一確定一個事務(wù)。首先分析事務(wù)的特征：事務(wù)一般由存儲過程、觸發(fā)器、SQL語句的一個或多個部分構(gòu)成，我們對一個經(jīng)典的商務(wù)應(yīng)用分析發(fā)現(xiàn)，同一個模式下，存儲過程名和觸發(fā)器名稱肯定是唯一的，復(fù)雜事務(wù)的第一條SQL語句一般也是不一樣的，而這些數(shù)據(jù)是我們在DCC入口處可以獲得的。由此我們定義：key=模式名.存儲過程名，或者key=模式名.觸發(fā)器名稱，或者key=模式名.SQL動詞名.表名，其中，表名可能是一個表名，也可能是多個表名的合并字符串。

根據(jù)Hash表預(yù)測事務(wù)長度的方法，其效率是很高的。①式（4）的計(jì)算復(fù)雜度是o(1)；②DCR′計(jì)算模塊每次從Hash表中讀取ln+1，因?yàn)樵揌ash表常駐內(nèi)存，所以讀取ln+1的計(jì)算復(fù)雜度也是o(1)，無I/O操作。因此該Hash表可以高效地預(yù)測事務(wù)長度。

改進(jìn)的DCR預(yù)測方法有一種特殊情況：當(dāng)一個事務(wù)第一次請求執(zhí)行時，Hash(key)=0，這種情況下按照式（1）計(jì)算DCR的值；當(dāng)該事務(wù)執(zhí)行完畢，統(tǒng)計(jì)模塊計(jì)算該事務(wù)Hash值時，現(xiàn)有Hash表中Hash(key)=0，此時我們不利用式（4），而直接將當(dāng)前事務(wù)長度賦予Lkey，并更新Hash表。

5 結(jié)論

數(shù)據(jù)庫系統(tǒng)的自主管理是一項(xiàng)很復(fù)雜的工作，本文提出了一個數(shù)據(jù)庫系統(tǒng)并發(fā)控制的自主優(yōu)化模型。該模型的一個特點(diǎn)是自主管理模塊比較獨(dú)立，提供統(tǒng)一的接口，不需要對原有系統(tǒng)進(jìn)行很大改動；該模型實(shí)現(xiàn)了并發(fā)控制的自主管理，降低了對管理員的依賴，從而可以提高性能并降低管理成本。該模型中對事務(wù)長度的預(yù)測只是一個初步的嘗試，式（4）中如何選擇合適的權(quán)重p仍然需要進(jìn)行很多的實(shí)驗(yàn)分析。

參考文獻(xiàn)：

[1]Moenkeberg A， Weikmn G. Conflictdriven Load Control for the Avoidance of Datacontention Thrashing[C]. IEEE Data Eng. Conf.， 1991.632-639.

[2]Thomasian A， Ryu I K. Performance Analysis of Twophase Locking[J]. IEEE Trans. on Softw. Eng.， 1991，17(5):386-402.

[3]Thomasian A. Performance Limits of Twophase Locking[C]. IEEE Data Eng. Conf.， 1991.426-435.

[4]Thomasian A. Thrashing in Twophase Locking Revisited[C]. IEEE Data Eng. Conf.， 1992.518-526.

[5]Moenkeherg A， Weikum G， Zurich E. Performance Evaluation of an Adaptive and Robust Load Control Method for the Avoidance of Datacontention Thrashing[C]. VLDB Conference， 1992.432-443.

[6]Weikum G， Moenkeberg A， Hasse C， et al. Selftuning Database Technology and Information Services: From Wishful Thinking to Viable Engineering[C]. VLDB， 2002.20-31.

[7]Hector G M， Jeffrey D U， et al. IBM Research Autonomic Computing[EB/OL]. http://www.research.ibm.com/autonmic/.

[8]數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)[M].楊冬青，唐世渭，徐其鈞.北京:機(jī)械工業(yè)出版社，2001.

作者簡介：

施磊（1981-），男，碩士，主要研究方向?yàn)閿?shù)據(jù)庫安全、數(shù)據(jù)倉庫；柏文陽（1967-），男，副教授，主要研究方向?yàn)閿?shù)據(jù)庫安全、數(shù)據(jù)挖掘、數(shù)據(jù)倉庫。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文