一種新的嵌入式內存數據庫的設計方法

0引言

隨著(zhù)硬件的發(fā)展，內存的容量在不斷擴大，人們長(cháng)期思考的將全部或大部分數據存放在 內存中運行成為可能。同時(shí)，嵌入式設備在日常生活中得到廣泛應用，如何對其內部日益繁 多的數據進(jìn)行管理顯得很關(guān)鍵。當前嵌入式內存數據庫產(chǎn)品很多，大多數產(chǎn)品由于各方面的 限制，在性能和市場(chǎng)前景方面表現欠佳。在嵌入式內存數據庫研究領(lǐng)域，新的存儲與索引方 法被不斷提出，同時(shí)面向對象的程序設計語(yǔ)言java作為當前主流開(kāi)發(fā)語(yǔ)言，在多線(xiàn)程和死鎖 處理方面有其獨特之處，為提出新的嵌入式內存數據庫的設計方法，及基于事務(wù)模型的恢復 方法提供了可能。

1嵌入式內存數據庫概述

嵌入式內存數據庫的設計一般采取兩種思路：一種是對傳統的大型數據庫進(jìn)行裁剪和改 進(jìn)，很多處理問(wèn)題的方法仍采用傳統數據庫的方法，某些方法在嵌入式內存數據庫不適用則 做些稍微改進(jìn)，這種思路沒(méi)有逃離傳統數據庫設計思想的束縛。另一種則是根據嵌入式內存 數據庫自身的特點(diǎn)，提出新的體系結構，存儲結構和恢復機制，以滿(mǎn)足嵌入式內存數據庫的 要求。目前，第二種方法被普遍采用和推崇，本文新的設計方法就采用后者。


1.2嵌入式內存數據庫的體系結構

在新的體系結構中，我們采用關(guān)系數據模型，最上層提供外部查詢(xún)接口，支持多種常用 語(yǔ)言如C,java等語(yǔ)言連接數據庫。第二層是對SQL語(yǔ)句進(jìn)行解析的查詢(xún)命令分解與優(yōu)化層， 這一層下面是兩個(gè)重要的模塊：數據組織與管理和事務(wù)管理器。其中，數據組織與管理模塊 完成常用的索引和數據組織工作，事務(wù)管理器具有創(chuàng )建事務(wù)，調度事務(wù)，回收事務(wù)的功能。 內存工作區是該體系結構最重要的模塊，全部數據操作及日志處理在這里進(jìn)行，它在事務(wù)處 理時(shí)為每一個(gè)事務(wù)分配一個(gè)內存工作區，其中存放數據和日志。日志管理器管理內存工作區 中的日志，而恢復管理器則在系統出現故障時(shí)起作用。該數據庫大部分操作在內存工作區中 運行，只有當發(fā)生檢查點(diǎn)操作和數據庫備份，及系統恢復時(shí)才與外面的磁盤(pán)打交道，因此該 數據庫是典型的嵌入式內存數據庫。上述體系結構圖如圖1所示：


2．數據的存儲與索引

嵌入式內存數據庫通常在內存受限的環(huán)境中進(jìn)行，CPU能直接操縱內存中的數據，且數 據經(jīng)常由于各種故障而丟失。因此合理的有效利用內存資源，減少內存開(kāi)銷(xiāo)和CPU指令數， 使內存空間得到高效利用很關(guān)鍵，為此我們引用了一種新的存儲與索引方法——T樹(shù)。

T樹(shù)是將AVL樹(shù)和B樹(shù)結合在一起而得出的一種新的數據結構，T樹(shù)也是一種二叉樹(shù)，只不 過(guò)每個(gè)結點(diǎn)(稱(chēng)為T(mén)結點(diǎn))都包含多個(gè)元素。每個(gè)T結點(diǎn)都包含一系列從小到大排序后的元素和 三個(gè)指針，指針?lè )謩e指向父結點(diǎn)和左右結點(diǎn)。某一T結點(diǎn)A的左結點(diǎn)中必會(huì )包含比A結點(diǎn)中最 小元素小的最大元素，而A結點(diǎn)的右結點(diǎn)中必會(huì )包含比A結點(diǎn)中最大元素大的最小元素。因為 是二叉樹(shù)，所以T樹(shù)具有AVL樹(shù)固有的二分查找特性，又因為每個(gè)結點(diǎn)包含多個(gè)元素,其又包 含了B樹(shù)良好的更新和存儲特性的優(yōu)點(diǎn)。對T樹(shù)來(lái)說(shuō)，因插入和刪除數據所造成的數據移動(dòng)通 ?？梢跃窒拊谝粋€(gè)結點(diǎn)內進(jìn)行，和AVL樹(shù)一樣，T樹(shù)也是通過(guò)旋轉來(lái)使樹(shù)達到平衡的, 但其所 需要的旋轉操作的次數遠少于A(yíng)VL樹(shù)[ 2 ]。T樹(shù)結點(diǎn)結構如圖2所示:


3基于事務(wù)處理的恢復模塊設計

本嵌入式內存數據庫，我們采用了基于多線(xiàn)程的事務(wù)模型，利用java語(yǔ)言作為開(kāi)發(fā)語(yǔ)言， Eclipse3.2為開(kāi)發(fā)工具，充分采用java語(yǔ)言的多線(xiàn)程機制和面向對象的思想來(lái)開(kāi)發(fā)數據庫。

在該事務(wù)模型中，我們將事務(wù)作為一個(gè)線(xiàn)程來(lái)看待，理由如下:(1)java語(yǔ)言有自己獨特 的多線(xiàn)程機制，具有開(kāi)始狀態(tài)，各種活動(dòng)狀態(tài)，結束狀態(tài)，把線(xiàn)程作為一個(gè)事務(wù)整體運行， 能夠滿(mǎn)足事務(wù)需求的各種操作，及自身的ACID屬性。(2)java語(yǔ)言有多線(xiàn)程處理時(shí)的同步操 作，事務(wù)處理時(shí)可以利用這種思想處理多事務(wù)之間的并發(fā)控制操作[ 3 ] 。我們利用事務(wù)管理 器創(chuàng )建事務(wù)，并在影子內存工作區為每一個(gè)事務(wù)分配相應的影子內存工作區，其中包括該事 務(wù)應處理的數據和日志，可以說(shuō)該模型是影子內存技術(shù)和日志處理技術(shù)的完美結合。其中， 新的事務(wù)模型和處理機制如下圖3所示。


3.1 日志操作

對每一個(gè)事務(wù)Ti分配一個(gè)內存工作區WAi，兼做影子內存和日志兩種功能。在事務(wù)進(jìn)入 提交狀態(tài)之前，將修改記錄放入影子內存中，當Ti進(jìn)入提交狀態(tài)時(shí)，由提交處理根據WAi中 的記錄對MDB作相應修改。我們稱(chēng)這種修改為“日志驅動(dòng)修改”。當某一事務(wù)Tj由于某種原 因夭折時(shí)，只需釋放其相應的影子內存工作區WAj即可, 而無(wú)需對數據庫進(jìn)行UNDO操作。因 此在本文中我們采用Redo日志。這樣，不僅可以大大節省內存空間，同時(shí)也簡(jiǎn)化了Abort(夭 折)處理。同時(shí)，為了便于對影子內存工作區的管理,給每一個(gè)影子內存工作區WAi設置一時(shí) 間戳TWAi,用來(lái)表示對應事務(wù)提交過(guò)程結束的時(shí)間。在處理日志提交時(shí)，我們充分利用事務(wù) 預提交和組提交的優(yōu)點(diǎn)來(lái)設計。具體過(guò)程如下，每一個(gè)已提交事務(wù)的WAi進(jìn)行預提交，按時(shí) 間先后順序組成鏈表LiST(WAi)，其結構如下:

事務(wù)進(jìn)入提交階段，提交處理(COMMIteR)對MDB作“日志驅動(dòng)修改”。當上述事務(wù)都完成時(shí)，進(jìn)行一次組提交，將上述事務(wù)的處理結果和日志寫(xiě)入磁盤(pán)，這樣可以減少磁盤(pán)I/O操作的次數。

3.1.1事務(wù)提交算法

事務(wù)提交具體算法如下：設WAi為活動(dòng)事務(wù)Ti的影子內存工作區，則事務(wù)Ti在時(shí)刻t的提 交處理算法為COMMITER(WAi，t)[ 4 ]。
輸入：WAi--事務(wù)Ti的影子工作區；t--某一個(gè)時(shí)間點(diǎn)。
輸出：0--執行成功；1--執行失敗。
步驟: ①依據WAi中的記錄，對內存中所有要被事務(wù)Ti修改的數據塊執行上鎖操作；② 對已上鎖的數據塊, 根據WAi中的記錄執行相應的更新操作；③在WAi中寫(xiě)入一個(gè)提交記錄； ④用當前時(shí)間t為WAi設置時(shí)間戳TWAi；⑤將WAi加入到影子工作區隊列的尾部；⑥將事務(wù)表 中該事務(wù)的狀態(tài)標志位從運行狀態(tài)改為提交狀態(tài)；⑦對在步驟①中上鎖了的數據塊解鎖。

3.1.2日志提交算法

在事務(wù)處理中，用于恢復的日志對WA的處理算法為L(cháng)OGGER(WAq)，日志提交算法如下：
輸入：WAq--影子工作區隊列。
輸出：0--執行成功；1--執行失敗。
步驟：①檢查WAq 是否為空,若不空,則從隊列頭取出第一個(gè)影子工作區WAx；若為空， 則掛起；②將WAx中的記錄寫(xiě)入外存的日志文件LOG中；③釋放WAx；④將事務(wù)表中相應于WAx 的事務(wù)的狀態(tài)標志位從提交改為撤銷(xiāo)；⑤轉步驟①循環(huán)執行。

3.2檢查點(diǎn)操作

檢查點(diǎn)操作包括靜止檢查點(diǎn)和非靜止檢查點(diǎn)。靜止檢查點(diǎn)要求操作過(guò)程中，數據庫處于 靜止狀態(tài)，檢查點(diǎn)結束后，開(kāi)始新的事務(wù)。在嵌入式內存數據庫對實(shí)時(shí)性要求很高靜止檢查 點(diǎn)很明顯不能滿(mǎn)足要求，因此我們采用非靜止檢查點(diǎn)。

在CHECKPOINT操作期間，由于采用的是Redo日志，提交事務(wù)所做的修改拷貝到磁盤(pán)的時(shí) 間可能比事務(wù)提交的時(shí)間晚得多，且采用預提交和組提交技術(shù)，我們要考慮檢查點(diǎn)發(fā)生時(shí)的 活動(dòng)事務(wù)，及在檢查點(diǎn)進(jìn)行前將影子內存工作區中，已提交的事務(wù)和日志刷新到磁盤(pán)中作為 備份。執行檢查點(diǎn)的步驟如下[5 ]：


3.3重裝與恢復

恢復涉及到兩個(gè)步驟，首先是重裝，將數據庫備份裝入MMDB 中；然后是恢復，根據日 志和檢驗點(diǎn)執行相應操作使數據庫恢復到系統崩潰之前最近的一致性狀態(tài)。檢查點(diǎn)可以幫我 們縮小日志的范圍，減少日志占用的空間資源，根據最后一個(gè)檢查點(diǎn)記錄是START還是END， 有以下兩種情況。


4結束語(yǔ)

在嵌入式內存數據庫領(lǐng)域，隨著(zhù)程序語(yǔ)言的發(fā)展，數據庫理論的成熟，新的設計思想和 技術(shù)在不斷涌現，各種產(chǎn)品應運而生。本文就是結合當今流行的java 語(yǔ)言和面向對象的思 想，結合嵌入式內存數據庫本身的特征，充分利用java 的多線(xiàn)程機制與事務(wù)處理的結合來(lái) 提出新的事務(wù)模型，同時(shí)融合了影子技術(shù)和日志技術(shù)，提出了新的恢復處理方法。但是本文 在很多方面還有不足之處，尤其是重裝與恢復算法方法，還有很多具體的工作要做。