0引言

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

1嵌入式內存數(shù)據庫概述

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


1.2嵌入式內存數(shù)據庫的體系結構

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


2．數(shù)據的存儲與索引

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

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


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

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

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


3.1 日志操作

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

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

3.1.1事務提交算法

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

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檢查點操作

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

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


3.3重裝與恢復

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


4結束語

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