摘要：近年來,各種嵌入式內存數據庫不斷涌現,但由于各種原因,很多產品不具有通用性、高效性、可靠性,以致于很難在市場上推廣開來。針對上述情況,提出一種新的嵌入式內存數據庫的設計方法,該方法結合當前流行的java語言和面向對象的思想,充分利用java語言本身的多線程機制,研究出基于多線程機制的嵌入式內存數據庫的事務模型,檢查點方法和恢復策略,同時對數據庫的存儲管理和索引機制進行了探討。實踐證明,相對于其它產品,本方法能大幅度的提高嵌入式內存數據庫的性能。

0引言

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

1嵌入式內存數據庫概述

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

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

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

2．數據的存儲與索引

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

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

3基于事務處理的恢復模塊設計

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

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

3.1 日志操作

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

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

3.1.1事務提交算法

事務提交具體算法如下：設WAi為活動事務Ti的影子內存工作區(qū)，則事務Ti在時刻t的提 交處理算法為COMMITER(WAi，t)[ 4 ]。

輸入：WAi--事務Ti的影子工作區(qū)；t--某一個時間點。

輸出：0--執(zhí)行成功；1--執(zhí)行失敗。

步驟: ①依據WAi中的記錄，對內存中所有要被事務Ti修改的數據塊執(zhí)行上鎖操作；② 對已上鎖的數據塊, 根據WAi中的記錄執(zhí)行相應的更新操作；③在WAi中寫入一個提交記錄； ④用當前時間t為WAi設置時間戳TWAi；⑤將WAi加入到影子工作區(qū)隊列的尾部；⑥將事務表 中該事務的狀態(tài)標志位從運行狀態(tài)改為提交狀態(tài)；⑦對在步驟①中上鎖了的數據塊解鎖。

3.1.2日志提交算法

在事務處理中，用于恢復的日志對WA的處理算法為LOGGER(WAq)，日志提交算法如下：

輸入：WAq--影子工作區(qū)隊列。

輸出：0--執(zhí)行成功；1--執(zhí)行失敗。

步驟：①檢查WAq 是否為空,若不空,則從隊列頭取出第一個影子工作區(qū)WAx；若為空， 則掛起；②將WAx中的記錄寫入外存的日志文件LOG中；③釋放WAx；④將事務表中相應于WAx 的事務的狀態(tài)標志位從提交改為撤銷；⑤轉步驟①循環(huán)執(zhí)行。

3.2檢查點操作

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

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

3.3重裝與恢復

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

4結束語

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