嵌入式內(nèi)存數(shù)據(jù)庫的研究與設(shè)計(jì)
摘要:近年來,各種嵌入式內(nèi)存數(shù)據(jù)庫不斷涌現(xiàn),但由于各種原因,很多產(chǎn)品不具有通用性、高效性、可靠性,以致于很難在市場上推廣開來。針對上述情況,提出一種新的嵌入式內(nèi)存數(shù)據(jù)庫的設(shè)計(jì)方法,該方法結(jié)合當(dāng)前流行的java語言和面向?qū)ο蟮乃枷?充分利用java語言本身的多線程機(jī)制,研究出基于多線程機(jī)制的嵌入式內(nèi)存數(shù)據(jù)庫的事務(wù)模型,檢查點(diǎn)方法和恢復(fù)策略,同時(shí)對數(shù)據(jù)庫的存儲管理和索引機(jī)制進(jìn)行了探討。實(shí)踐證明,相對于其它產(chǎn)品,本方法能大幅度的提高嵌入式內(nèi)存數(shù)據(jù)庫的性能。
本文引用地址:http://butianyuan.cn/article/149774.htm0引言
隨著硬件的發(fā)展,內(nèi)存的容量在不斷擴(kuò)大,人們長期思考的將全部或大部分?jǐn)?shù)據(jù)存放在 內(nèi)存中運(yùn)行成為可能。同時(shí),嵌入式設(shè)備在日常生活中得到廣泛應(yīng)用,如何對其內(nèi)部日益繁 多的數(shù)據(jù)進(jìn)行管理顯得很關(guān)鍵。當(dāng)前嵌入式內(nèi)存數(shù)據(jù)庫產(chǎn)品很多,大多數(shù)產(chǎn)品由于各方面的 限制,在性能和市場前景方面表現(xiàn)欠佳。在嵌入式內(nèi)存數(shù)據(jù)庫研究領(lǐng)域,新的存儲與索引方 法被不斷提出,同時(shí)面向?qū)ο蟮某绦?a class="contentlabel" href="http://butianyuan.cn/news/listbylabel/label/設(shè)計(jì)">設(shè)計(jì)語言java作為當(dāng)前主流開發(fā)語言,在多線程和死鎖 處理方面有其獨(dú)特之處,為提出新的嵌入式內(nèi)存數(shù)據(jù)庫的設(shè)計(jì)方法,及基于事務(wù)模型的恢復(fù) 方法提供了可能。
1嵌入式內(nèi)存數(shù)據(jù)庫概述
嵌入式內(nèi)存數(shù)據(jù)庫的設(shè)計(jì)一般采取兩種思路:一種是對傳統(tǒng)的大型數(shù)據(jù)庫進(jìn)行裁剪和改 進(jìn),很多處理問題的方法仍采用傳統(tǒng)數(shù)據(jù)庫的方法,某些方法在嵌入式內(nèi)存數(shù)據(jù)庫不適用則 做些稍微改進(jìn),這種思路沒有逃離傳統(tǒng)數(shù)據(jù)庫設(shè)計(jì)思想的束縛。另一種則是根據(jù)嵌入式內(nèi)存 數(shù)據(jù)庫自身的特點(diǎn),提出新的體系結(jié)構(gòu),存儲結(jié)構(gòu)和恢復(fù)機(jī)制,以滿足嵌入式內(nèi)存數(shù)據(jù)庫的 要求。目前,第二種方法被普遍采用和推崇,本文新的設(shè)計(jì)方法就采用后者。
1.2嵌入式內(nèi)存數(shù)據(jù)庫的體系結(jié)構(gòu)
在新的體系結(jié)構(gòu)中,我們采用關(guān)系數(shù)據(jù)模型,最上層提供外部查詢接口,支持多種常用 語言如C,java等語言連接數(shù)據(jù)庫。第二層是對SQL語句進(jìn)行解析的查詢命令分解與優(yōu)化層, 這一層下面是兩個重要的模塊:數(shù)據(jù)組織與管理和事務(wù)管理器。其中,數(shù)據(jù)組織與管理模塊 完成常用的索引和數(shù)據(jù)組織工作,事務(wù)管理器具有創(chuàng)建事務(wù),調(diào)度事務(wù),回收事務(wù)的功能。 內(nèi)存工作區(qū)是該體系結(jié)構(gòu)最重要的模塊,全部數(shù)據(jù)操作及日志處理在這里進(jìn)行,它在事務(wù)處 理時(shí)為每一個事務(wù)分配一個內(nèi)存工作區(qū),其中存放數(shù)據(jù)和日志。日志管理器管理內(nèi)存工作區(qū) 中的日志,而恢復(fù)管理器則在系統(tǒng)出現(xiàn)故障時(shí)起作用。該數(shù)據(jù)庫大部分操作在內(nèi)存工作區(qū)中 運(yùn)行,只有當(dāng)發(fā)生檢查點(diǎn)操作和數(shù)據(jù)庫備份,及系統(tǒng)恢復(fù)時(shí)才與外面的磁盤打交道,因此該 數(shù)據(jù)庫是典型的嵌入式內(nèi)存數(shù)據(jù)庫。上述體系結(jié)構(gòu)圖如圖1所示:
2.?dāng)?shù)據(jù)的存儲與索引
嵌入式內(nèi)存數(shù)據(jù)庫通常在內(nèi)存受限的環(huán)境中進(jìn)行,CPU能直接操縱內(nèi)存中的數(shù)據(jù),且數(shù) 據(jù)經(jīng)常由于各種故障而丟失。因此合理的有效利用內(nèi)存資源,減少內(nèi)存開銷和CPU指令數(shù), 使內(nèi)存空間得到高效利用很關(guān)鍵,為此我們引用了一種新的存儲與索引方法——T樹。
T樹是將AVL樹和B樹結(jié)合在一起而得出的一種新的數(shù)據(jù)結(jié)構(gòu),T樹也是一種二叉樹,只不 過每個結(jié)點(diǎn)(稱為T結(jié)點(diǎn))都包含多個元素。每個T結(jié)點(diǎn)都包含一系列從小到大排序后的元素和 三個指針,指針分別指向父結(jié)點(diǎn)和左右結(jié)點(diǎn)。某一T結(jié)點(diǎn)A的左結(jié)點(diǎn)中必會包含比A結(jié)點(diǎn)中最 小元素小的最大元素,而A結(jié)點(diǎn)的右結(jié)點(diǎn)中必會包含比A結(jié)點(diǎn)中最大元素大的最小元素。因?yàn)?是二叉樹,所以T樹具有AVL樹固有的二分查找特性,又因?yàn)槊總€結(jié)點(diǎn)包含多個元素,其又包 含了B樹良好的更新和存儲特性的優(yōu)點(diǎn)。對T樹來說,因插入和刪除數(shù)據(jù)所造成的數(shù)據(jù)移動通 ??梢跃窒拊谝粋€結(jié)點(diǎn)內(nèi)進(jìn)行,和AVL樹一樣,T樹也是通過旋轉(zhuǎn)來使樹達(dá)到平衡的, 但其所 需要的旋轉(zhuǎn)操作的次數(shù)遠(yuǎn)少于AVL樹[ 2 ]。T樹結(jié)點(diǎn)結(jié)構(gòu)如圖2所示:
3基于事務(wù)處理的恢復(fù)模塊設(shè)計(jì)
本嵌入式內(nèi)存數(shù)據(jù)庫,我們采用了基于多線程的事務(wù)模型,利用java語言作為開發(fā)語言, Eclipse3.2為開發(fā)工具,充分采用java語言的多線程機(jī)制和面向?qū)ο蟮乃枷雭黹_發(fā)數(shù)據(jù)庫。
在該事務(wù)模型中,我們將事務(wù)作為一個線程來看待,理由如下:(1)java語言有自己獨(dú)特 的多線程機(jī)制,具有開始狀態(tài),各種活動狀態(tài),結(jié)束狀態(tài),把線程作為一個事務(wù)整體運(yùn)行, 能夠滿足事務(wù)需求的各種操作,及自身的ACID屬性。(2)java語言有多線程處理時(shí)的同步操 作,事務(wù)處理時(shí)可以利用這種思想處理多事務(wù)之間的并發(fā)控制操作[ 3 ] 。我們利用事務(wù)管理 器創(chuàng)建事務(wù),并在影子內(nèi)存工作區(qū)為每一個事務(wù)分配相應(yīng)的影子內(nèi)存工作區(qū),其中包括該事 務(wù)應(yīng)處理的數(shù)據(jù)和日志,可以說該模型是影子內(nèi)存技術(shù)和日志處理技術(shù)的完美結(jié)合。其中, 新的事務(wù)模型和處理機(jī)制如下圖3所示。
3.1 日志操作
對每一個事務(wù)Ti分配一個內(nèi)存工作區(qū)WAi,兼做影子內(nèi)存和日志兩種功能。在事務(wù)進(jìn)入 提交狀態(tài)之前,將修改記錄放入影子內(nèi)存中,當(dāng)Ti進(jìn)入提交狀態(tài)時(shí),由提交處理根據(jù)WAi中 的記錄對MDB作相應(yīng)修改。我們稱這種修改為“日志驅(qū)動修改”。當(dāng)某一事務(wù)Tj由于某種原 因夭折時(shí),只需釋放其相應(yīng)的影子內(nèi)存工作區(qū)WAj即可, 而無需對數(shù)據(jù)庫進(jìn)行UNDO操作。因 此在本文中我們采用Redo日志。這樣,不僅可以大大節(jié)省內(nèi)存空間,同時(shí)也簡化了Abort(夭 折)處理。同時(shí),為了便于對影子內(nèi)存工作區(qū)的管理,給每一個影子內(nèi)存工作區(qū)WAi設(shè)置一時(shí) 間戳TWAi,用來表示對應(yīng)事務(wù)提交過程結(jié)束的時(shí)間。在處理日志提交時(shí),我們充分利用事務(wù) 預(yù)提交和組提交的優(yōu)點(diǎn)來設(shè)計(jì)。具體過程如下,每一個已提交事務(wù)的WAi進(jìn)行預(yù)提交,按時(shí) 間先后順序組成鏈表LiST(WAi),其結(jié)構(gòu)如下:
事務(wù)進(jìn)入提交階段,提交處理(COMMIteR)對MDB作“日志驅(qū)動修改”。當(dāng)上述事務(wù)都完成時(shí),進(jìn)行一次組提交,將上述事務(wù)的處理結(jié)果和日志寫入磁盤,這樣可以減少磁盤I/O操作的次數(shù)。
3.1.1事務(wù)提交算法
事務(wù)提交具體算法如下:設(shè)WAi為活動事務(wù)Ti的影子內(nèi)存工作區(qū),則事務(wù)Ti在時(shí)刻t的提 交處理算法為COMMITER(WAi,t)[ 4 ]。
輸入:WAi--事務(wù)Ti的影子工作區(qū);t--某一個時(shí)間點(diǎn)。
輸出:0--執(zhí)行成功;1--執(zhí)行失敗。
步驟: ①依據(jù)WAi中的記錄,對內(nèi)存中所有要被事務(wù)Ti修改的數(shù)據(jù)塊執(zhí)行上鎖操作;② 對已上鎖的數(shù)據(jù)塊, 根據(jù)WAi中的記錄執(zhí)行相應(yīng)的更新操作;③在WAi中寫入一個提交記錄; ④用當(dāng)前時(shí)間t為WAi設(shè)置時(shí)間戳TWAi;⑤將WAi加入到影子工作區(qū)隊(duì)列的尾部;⑥將事務(wù)表 中該事務(wù)的狀態(tài)標(biāo)志位從運(yùn)行狀態(tài)改為提交狀態(tài);⑦對在步驟①中上鎖了的數(shù)據(jù)塊解鎖。
3.1.2日志提交算法
在事務(wù)處理中,用于恢復(fù)的日志對WA的處理算法為LOGGER(WAq),日志提交算法如下:
輸入:WAq--影子工作區(qū)隊(duì)列。
輸出:0--執(zhí)行成功;1--執(zhí)行失敗。
步驟:①檢查WAq 是否為空,若不空,則從隊(duì)列頭取出第一個影子工作區(qū)WAx;若為空, 則掛起;②將WAx中的記錄寫入外存的日志文件LOG中;③釋放WAx;④將事務(wù)表中相應(yīng)于WAx 的事務(wù)的狀態(tài)標(biāo)志位從提交改為撤銷;⑤轉(zhuǎn)步驟①循環(huán)執(zhí)行。
3.2檢查點(diǎn)操作
檢查點(diǎn)操作包括靜止檢查點(diǎn)和非靜止檢查點(diǎn)。靜止檢查點(diǎn)要求操作過程中,數(shù)據(jù)庫處于 靜止?fàn)顟B(tài),檢查點(diǎn)結(jié)束后,開始新的事務(wù)。在嵌入式內(nèi)存數(shù)據(jù)庫對實(shí)時(shí)性要求很高靜止檢查 點(diǎn)很明顯不能滿足要求,因此我們采用非靜止檢查點(diǎn)。
在CHECKPOINT操作期間,由于采用的是Redo日志,提交事務(wù)所做的修改拷貝到磁盤的時(shí) 間可能比事務(wù)提交的時(shí)間晚得多,且采用預(yù)提交和組提交技術(shù),我們要考慮檢查點(diǎn)發(fā)生時(shí)的 活動事務(wù),及在檢查點(diǎn)進(jìn)行前將影子內(nèi)存工作區(qū)中,已提交的事務(wù)和日志刷新到磁盤中作為 備份。執(zhí)行檢查點(diǎn)的步驟如下[5 ]:
3.3重裝與恢復(fù)
恢復(fù)涉及到兩個步驟,首先是重裝,將數(shù)據(jù)庫備份裝入MMDB 中;然后是恢復(fù),根據(jù)日 志和檢驗(yàn)點(diǎn)執(zhí)行相應(yīng)操作使數(shù)據(jù)庫恢復(fù)到系統(tǒng)崩潰之前最近的一致性狀態(tài)。檢查點(diǎn)可以幫我 們縮小日志的范圍,減少日志占用的空間資源,根據(jù)最后一個檢查點(diǎn)記錄是START還是END, 有以下兩種情況。
4結(jié)束語
在嵌入式內(nèi)存數(shù)據(jù)庫領(lǐng)域,隨著程序語言的發(fā)展,數(shù)據(jù)庫理論的成熟,新的設(shè)計(jì)思想和 技術(shù)在不斷涌現(xiàn),各種產(chǎn)品應(yīng)運(yùn)而生。本文就是結(jié)合當(dāng)今流行的java 語言和面向?qū)ο蟮乃?想,結(jié)合嵌入式內(nèi)存數(shù)據(jù)庫本身的特征,充分利用java 的多線程機(jī)制與事務(wù)處理的結(jié)合來 提出新的事務(wù)模型,同時(shí)融合了影子技術(shù)和日志技術(shù),提出了新的恢復(fù)處理方法。但是本文 在很多方面還有不足之處,尤其是重裝與恢復(fù)算法方法,還有很多具體的工作要做。
linux操作系統(tǒng)文章專題:linux操作系統(tǒng)詳解(linux不再難懂)
評論