一種基于多級的實時數據庫緩沖管理算法

隨著實時數據庫應用程序的普及，不同的技術問題（如事務規劃和同時控制）被研究越來越多。然而，實時數據庫緩沖區管理技術（或內存管理技術）是研究人員不可忽視的問題，而面向實時數據庫的緩沖區管理算法很少。許多研究人員認為實時數據庫應當或者必須是內存數據庫,因此實時數據庫緩沖區管理算法的研究沒有意義。對于這種認識,文獻進行了否定,闡述了實時數據庫和內存數據庫在概念、功能以及使用的調度算法上的區別;而在諸如過程生產監控、股票交易等實際應用中,實時數據庫需要處理海量數據,這些系統每天產生的數據以GB計,將數據全部存儲在內存中是不可能的,對于此類應用,將緩沖區管理算法引入實時數據庫系統是非常必要的。實時數據庫應用于對數據刷新和處理要求時限性很強的系統,其事務和數據與一般數據庫的事務和數據相比,一個最大的不同是具有時態約束。事務的時態約束主要指截止期約束,數據的時態約束是數據的有效時間約束。由于這些特點,用于關系數據庫的調度方法,例如事務調度、I/O調度以及緩沖區調度都不能直接用于實時數據庫系統中,因為傳統的調度方法很少考慮截止期。盡管在實時數據庫中,事務調度和并發控制策略對于系統性能影響更大一些,但是不論系統的瓶頸是CPU還是磁盤I/O,對重要資源的調度必須由基于優先級的緩沖區調度算法配合完成,許多實驗結果也證明了這一結論,因此緩沖區管理是影響實時數據庫系統性能的因素之一,應針對實時數據庫的特點進行設計。實時數據庫越來越多地用于開放式的環境下,其負載變化比較大,這要求實時數據庫的調度方法必須能夠適應變化的負載,保持穩定的性能。用于關系數據庫的緩沖區管理方法一般都使用固定長度的緩沖區,對負載變化的適應性比較差。我們通過對實時數據庫事務和數據特征的分析,總結了以往的研究成果,在本文中提出了實時數據庫緩沖區管理算法的設計原則,并依據該原則設計了一種使用反饋控制思想的基于優先級的實時數據庫緩沖區管理方法FCLRU2-dl(FeedbackControlbasedLRU2-dl)。該方法根據系統負載的變化,動態調整緩沖區的規模,在不同負載下,將系統的事務按時完成比率(SuccessRatio)維持在一定的水平,在一定程度上保證系統性能的穩定。1緩沖管理方法由于內存訪問時間遠遠低于磁盤訪問時間,因此直接從內存獲取所需要的數據將大大縮短事務的執行時間。但是數據庫的數據量一般很大,無法把全部數據放在內存中,而只能將一部分數據放入內存,這就給事務的執行帶來了不確定性。緩沖區管理的作用是把事務將要訪問的數據盡量多地換入內存中,當事務訪問這些數據時,使執行速度得以提高。緩沖區管理算法是用來決定將哪些數據放在內存以及存放多長時間的一組策略。緩沖區管理算法包括緩沖區分配和緩沖區置換兩個過程,其中緩沖區置換策略是傳統緩沖區管理技術的核心。傳統的置換方法以提高事務對內存數據訪問的命中率(HitRatio)為目的,一般基于局部性(Locality)原理和事務的傾斜訪問(SkewedAccess)原理,通過分析事務對數據的訪問模式,針對一個固定長度的緩沖區設計一個置換算法,按照某種策略將內存數據與磁盤數據進行交換,以期在內存中保存事務將要訪問的數據,降低事務執行時的缺頁率(PageFaultRa￣tio),減少事務對磁盤的訪問。但是多數文獻提出的緩沖區管理方法都沒有使用優先級策略,同時也沒有考慮實時環境。還有的文獻提出了一些使用優先級策略的方法如PLRU(Prio￣rity-LRU),PH(PriorityHints)等,使用的都是靜態的優先級,而實時環境下的事務的優先級是隨著截止期的變化而變化的。文獻研究了實時環境下的緩沖區調度問題,并且都使用了基于優先級的調度策略。文獻提出的緩沖區管理算法是LRU-dl(具有截止期的LRU算法),并且將該算法用于多種CPU調度算法、并發控制算法協同運行,形成了一些實驗結果。該文同時探討了實時數據庫中所有的調度策略對于系統性能的影響,但是沒有使用先進的緩沖區管理方法。文獻針對實時數據庫事務特點提出了一種使用預取(Prefe￣tching)策略的緩沖區管理算法PAPER,取得了較好的實驗效果。但是該算法仍然沒有脫離傳統方法的思維模式,使用固定長度的緩沖區應對變化的負載,影響了算法的穩定性,其預取策略基于對事務、數據、約束三者關系的分析比較復雜,實現困難,也帶來較大的系統開銷。在實時事務調度和并發控制策略的研究方面,目前已經有許多研究成果。文獻提出了2PL-HP的沖突解決方法,是一種目前被廣泛使用的并發控制策略,該方法偏向高優先級事務。其基本思想是:如果一個事務請求鎖住某個數據對象,而這個數據對象已經被一個或多個低優先級事務鎖住,則持有鎖的事務被夭折;如果鎖請求者的優先級低于鎖持有者的優先級,則鎖請求者等待。該算法的優點是避免了優先級反轉和死鎖問題,缺點是可能導致無效的重啟。文獻最先綜合研究了FCFS(FirstComeFirstServe),EDF(EarliestDeadlineFirst),LSF(LeastSlackFirst)三種優先級調度算法,認為就調度算法而言,EDF表現了最好的性能。通過對于實時數據庫特征及其他相關研究成果的總結,我們認為實時數據庫緩沖區算法設計應當遵循以下原則:(1)應以事務的按時完成比率作為衡量緩沖區管理算法優劣的標準,好的算法應能提高按時完成比率。(2)實時數據庫的緩沖區管理算法必須考慮事務的信息,包括截止期和事務價值等因素,或者說是能夠識別事務截止期和價值的調度算法。(3)實時數據庫的緩沖區管理算法要考慮系統在變化負載下的穩定性和效率問題。(4)實時數據庫的緩沖區管理算法需要為用戶提供控制接口,除了允許用戶改變緩沖區的長度、結構等信息外,還應當允許用戶指定重要的、使用頻繁的表和數據常駐緩沖區,使其在生存期間不被換出。2緩沖優化設計針對上述的實時數據庫的緩沖區管理的要求,我們提出了一個新方法,使用反饋控制策略對緩沖區長度進行調整,維持系統在不同負載下性能的穩定性。圖1中,虛線右側為FCLRU2-dl算法的組成模塊,虛線左側為實時數據庫系統的功能模塊。算法使用的所有緩沖區頁面都位于全局緩沖區GlobalBuffer中;置換控制器(ReplacementController)在系統穩態運行期間工作,(這里的穩態是指系統在某個固定負載條件下運行了足夠的時間后達到的狀態),置換控制器將使用LRU2-dl方法決定哪一頁換出,并將這個信息發送給執行器(Executor)執行;反饋控制器(FeedbackController)在系統負載發生較大變化時工作,用來判斷緩沖區長度是否符合負載的要求,當緩沖區長度不適合當前的負載時,反饋控制器根據一定的方法計算一個新的緩沖區尺寸,將這個決定也交給執行器執行;事務管理器(TransactionMana￣ger)計算當前的負載并將負載情況通知反饋控制器。執行器負責執行分配/釋放/交換緩沖區等所有實際的操作行為。執行器需要通過I/O管理器的協助完成最終的讀寫磁盤的操作。2.1實時數據庫的緩沖區設計大量的實驗結果證明,事務對數據的訪問滿足局部性(Locality)原理,即一個數據被訪問,其相鄰的數據也將很快被訪問。在實時數據庫系統中,該規則依然成立。實時數據庫中事務訪問數據的另一個特點是時態傾斜,即多數事務只訪問最近某個時間段內的數據,一個數據的時間標簽距離當前時間越遠,其被訪問的概率也越小。基于這些特點,我們為實時數據庫的緩沖區設計了如表1所示的結構。Valueij是字段i在j時刻的值,可能是一個結構型數據,包括了字段的值和其他需要的信息。一個緩沖區中的包含的字段可以是全部或部分數據庫字段,時刻1～n時刻是一組連續的時間標簽。參數m和n的選擇與緩沖區長度、數據庫的規模以及具體的應用有關。該結構可以很好地利用局部性原理和時態傾斜訪問原理,提高數據訪問的命中率。緩沖區頁面的控制信息包括如該頁面是否被引用以及引用時間,該頁面是否是“臟”頁,引用該頁面事務的部分信息如截止期、價值等也包含在緩沖區的頁面中。頁面的優先級與引用頁面的事務的截止期成反比。2.2基于lru2算法的頁面信息挖掘當系統的事務到達速率在一定時間內基本維持恒定時,可以認為系統負載處于穩態狀態,此時使用緩沖區置換策略處理事務訪問時的缺頁。我們使用LRU2-dl的置換策略。許多實驗證明文獻提出的LRUK算法優于LRU算法(命中率最大可以提高40%)。LRUK算法記錄每個頁面最近第K次被引用的時間,取該值最小(離當前時間最久)的一頁換出。文獻同時證明了LRUK算法取K>2時的效果僅僅略優于K=2的效果,所以我們此處取K=2,即使用LRU2算法。我們對LRU2增加了識別截止期的機制,建立了LRU2-dl算法。算法中使用的頁面信息包括:Pi.dl,頁面的截止期,是引用該頁的事務的(如果多個事務取最短)截止期;Pi.usr,引用該頁面的事務數;Pi.ts,該頁的次最近(從當前時間向前推的第二次引用)訪問時間。算法描述如下:2.3緩沖過量控制ratio當負載發生較大變化時,系統將根據一定的規則增加(減少)緩沖區的長度,維持SuccessRatio穩定于某個目標值。系統根據負載變化的情況確定反饋策略,增加或減少緩沖區的長度,當緩沖區的長度等于數據庫的長度時,實時數據庫完全位于內存中,成為一種內存數據庫。此時系統表現了較好的性能,我們把系統在這種情況下的SuccessRatio值作為反饋控制算法的目標值,對系統的緩沖區規模進行反饋控制。一個典型的反饋系統如圖2所示。Plant是被控制對象,有若干個變量反映它的狀態,在該算法中被控制對象是Plant的一個屬性——SuccessRatio,控制的手段是調控Plant的緩沖區長度Bl,從Plant中采集的狀態是Sr和MAR(MeanArrivalRate,事務平均到達速率);Sensor采集Plant的狀態,計算SuccessRatio狀態的變化率和MAR的變化率△MAR,傳送給Controller,Controller使用一個控制算法計算出系統需要改變的緩沖區數量的比率△Bl,將這個決策交給Activator執行,使Plant的Sr向目標的方向變化。反饋控制的算法如下:t是穩定時間,△S是允許的調整誤差。Bll是低負載時的緩沖區長度的理想值,Blm是中負載時的理想值,Blh是高負載時的理想值,是由實驗得到的。Srl,Srm,Srh分別是系統在低、中、高負載下的SuccessRatio的目標值,上述已經提到,該值是實時數據庫全部位于內存時的SuccessRatio測量值。3其他功能模塊我們的測試平臺是集中式的實時數據庫系統,包括了實時數據庫系統中所有重要的功能模塊,例如事務調度、并發控制、I/O管理等功能。我們在實驗中使用的事務調度算法是EDF,使用的并發控制協議是2PL-HP,I/O調度是基于優先級的非搶占式調度,這里優先級和頁面的截止期成反比。其他重要的實驗參數在表2中詳細的列出。3.1實驗參數的確定我們進行算法測試的實驗環境如表2所示。實驗的參數主要參照文獻中的實驗參數。其中緩沖區的長度是緩沖區管理而言的一個重要參數。我們研究了不同緩沖區規模下系統的性能。3.2反饋控制的lru2-dl性能指標我們測量了在不同的緩沖區長度和不同負載的條件下,基于反饋控制的LRU2-dl的性能指標,包括HitRatio和SuccessRatio,形成了本節的各實驗曲線。圖3、圖4是三種負載情況下的命中率曲線。3.2.1緩沖區較大時的ratio如圖3、圖4所示,當緩沖區長度小于200時,HitRatio(H曲線)和SuccessRatio(S曲線)隨著緩沖區長度的增加有比較快的增長,這是由于緩沖區長度較小時HitRatio小于緩沖區長度較大時的HitRatio,因此小緩沖區會引起比較多的I/O操作,事務也因此花費更多的時間獲取數據,增加了事務錯失截止期的概率。當逐漸增加緩沖區規模時,I/O操作將減少,使事務可以在更短的時間內獲取數據,因此系統的SuccessRatio將隨著緩沖區的增加而增加。當緩沖區長度大于200時,H曲線和S曲線隨著緩沖區的增加只有邊際的提高。這是因為數據的訪問模式是傾斜訪問,遵循80-20規則,即80%的事務只集中訪問數據庫中特定區域(一般只占數據庫規模的20%)的數據。當緩沖區大于700時,由于HitRatio已經足夠大,幾乎消除了I/O操作對于事務的影響,因此H曲線和S曲線都不再隨緩沖區的增加而上升。3.2.2負載過高的問題當緩沖區長度小于600時,H曲線的趨勢和低負載情況下的一樣,其原因也相同。當緩沖區大于600時,雖然H曲線隨著緩沖區的增加而增加,但是S曲線卻開始下降。這個反常的現象可以用并發事務對于數據的爭奪來解釋。在中負載條件下,當緩沖區長度大于700時,幾乎沒有事務是因為I/O操作而超時或夭折的,由于負載比較高,因此并發事務之間的數據爭奪就比較嚴重,由于一些被低優先級事務持有的鎖又被高優先級事務請求,引起了持有鎖的低優先級事務的夭折。但是在緩沖區較小時,例如200～600,這些事務可能是被I/O操作阻塞的,它們就不會被高優先級的事務鎖夭折,因此有機會執行完畢,這種情況下系統的SuccessRatio也比較高;同時,由于這些事務的阻塞,系統中的數據爭奪現象得以緩解,其他的事務有機會得到它們的數據并且在截止期內完成。因此在中負載情況下,緩沖區較小時的SuccessRatio可能高于緩沖區較大時的SuccessRatio。3.2.3fclru2-dl算法性能分析高負載時的H曲線趨勢和中、低負載條件下的曲線是一樣的,其原因也相同。而高負載下的S曲線的趨勢與中負載條件下的曲線相似,只是在不同緩沖區規模下,SuccessRatio的變化更加明顯一些。圖3顯示出:不論系統的負載情況如何,H曲線基本是一樣的,這也源于我們使用80-20的規則模擬數據訪問。而圖4顯示了不同負載條件下,低負載時系統具有最高的SuccessRatio,而高負載時的SuccessRatio最低。同時在中、高負載條件下,系統的SuccessRatio以緩沖區規模在200～600時為最高。根據上述的實驗結果,我們設定了FCLRU2-dl算法的各項參數,包括Bll,Blm,Blh和Srl,Srm,Srh,并且對該算法進行了測試。此處Bll為700,Blm為600,B