嵌入式實時數據庫技術研究

2005年2月A

本文于2004年10月10日收到。劉 震：博士，主要從事計算機測控、嵌入式系統(tǒng)及故障診斷等方面的研究；羅 欣，博士，主要從事圖象處理與模式識別、嵌入式系統(tǒng)等方面的研究。

摘要：對嵌入式實時數據庫系統(tǒng)的功能進行了分析，研究了嵌入式實時數據庫系統(tǒng)的結構及特性，探討了在嵌入式環(huán)境下進行實時數據庫設計的內容及需要解決的相關問題，最后給出了一個基于VxWorks的嵌入式實時數據庫開發(fā)的應用實例。
關鍵詞：嵌入式；實時數據庫；VxWorks

    隨著嵌入式系統(tǒng)的廣泛應用及嵌入式實時操作系統(tǒng)的不斷普及，嵌入式環(huán)境下的數據管理問題成為系統(tǒng)中的重要環(huán)節(jié)，構建嵌入式實時數據庫系統(tǒng)（RTDBS）成為嵌入式開發(fā)中必須解決的問題。這里所說的嵌入式RTDBS[1][2]是指可在嵌入式設備中獨立運行的一種數據庫系統(tǒng)，用以處理大量的、時效性強且有嚴格時序的數據，它以高可靠性、高實時性和高信息吞吐量為目標，其數據的正確性不僅依賴于邏輯結果，而且依賴于邏輯結果產生的時間。圖1是一個嵌入式應用的基本構架，整個嵌入式RTDBS構建于實時操作系統(tǒng)之上。由于嵌入式實時數據庫系統(tǒng)在運行環(huán)境和運行方式上與常見的企業(yè)級數據庫管理系統(tǒng)有很大差別，因此，傳統(tǒng)的企業(yè)數據庫如Oracle、Sybase等在實時嵌入式環(huán)境下很難發(fā)揮作用，尤其在一些實時性要求很高的控制系統(tǒng)中，傳統(tǒng)數據庫更顯得無能為力。因此，伴隨著各種商用嵌入式實時操作系統(tǒng)的出現，研究嵌入式環(huán)境下的實時數據庫系統(tǒng)成為嵌入式軟件中的一項重要內容。

圖1  嵌入式應用基本結構

嵌入式RTDBS內涵及其體系結構
    目前嵌入式系統(tǒng)開發(fā)中，在實時數據庫問題上的多數看法是，嵌入式RTDBS從本質上說是一個“內存數據庫”，是一個由應用程序管理的內存緩沖池，它在系統(tǒng)中的作用就是一個供多個實時任務共同使用的共享數據區(qū)。這種數據庫實際上是一個嵌入在用戶應用軟件中的與應用程序不可分割的部分，其功能主要是數據的存和取，不具有獨立性，不是一個真正意義上的數據庫系統(tǒng)。一個完整的嵌入式實時數據庫系統(tǒng)除了包括內存數據庫外，還應當含有歷史數據庫和數據庫管理系統(tǒng)DBMS及提供給用戶的接口函數，整個數據庫可由DBMS完成對數據庫的具體配置及各種操作，例如系統(tǒng)運行前根據實際需要對內存數據庫中的記錄節(jié)點進行增減等配置操作。目前的嵌入式實時數據庫系統(tǒng)可分為兩大類，一類是商用級的嵌入式實時數據庫系統(tǒng)，它獨立于具體的應用軟件，如美國McObject公司提供的eXtremeDB內存式實時數據庫，這是一種專門為嵌入式系統(tǒng)數據庫管理而編寫的實時數據庫，它將數據庫直接建立在內存之中，并根據應用特征產生數據庫API，用戶可方便的調用這些接口函數管理整個數據庫系統(tǒng)；另一類是用戶針對具體的應用對象而自行設計開發(fā)的嵌入式實時數據庫系統(tǒng)，這種數據庫一般是嵌入到應用軟件中作為應用程序的一部分，不具有獨立性，目前測控系統(tǒng)中用戶開發(fā)的實時數據庫大都屬于這種情況。

    圖2所示的是一個嵌入式實時數據庫系統(tǒng)的體系結構，同傳統(tǒng)的數據庫一樣，它仍然是一種三級模式的結構體系，即用戶模式、邏輯模式和存儲模式。在嵌入式環(huán)境下構建實時數據庫系統(tǒng)，應該完成以下功能：高效的數據存取機制、數據安全性控制、實時事務管理機制、數據庫的恢復機制等，設計中更關心的是系統(tǒng)的實時性、開銷大小、系統(tǒng)性能、可靠性、可預知性和底層控制能力，即如何針對選用的實時OS和嵌入式硬件平臺設計合理的數據模型和物理結構，重點放在如何高效的利用嵌入式系統(tǒng)的有限資源、如何提高數據的存取速度、如何進行數據保護、數據交換、查詢/ 事務處理算法的優(yōu)化、事務的優(yōu)先級分派、事務調度和并發(fā)控制等等。
圖2  嵌入式RTDBS系統(tǒng)結構

嵌入式RTDBS的數據模型
    嵌入式實時數據庫系統(tǒng)的關鍵是數據模型的確立，它決定了數據被訪問和操作的方式，應用程序的性能和可靠性也大部分取決于此。目前嵌入式環(huán)境下的數據庫系統(tǒng)多數采用了關系模型結構，這也是商用數據庫系統(tǒng)的數據模型，該模型結構是利用二維關系表來實現數據存儲，利用索引訪問和查詢數據，這種模型結構是建立在嚴格的數學基礎上的，結構簡單靈活，獨立性好，但在嵌入式環(huán)境下的內存開銷和數據冗余較大，用戶必須對其進行優(yōu)化，增加了開發(fā)數據庫系統(tǒng)的難度；有些嵌入式數據庫則采用了網狀模型結構，該模型通過指針來確定數據間的顯式連接關系，它比關系模型中利用冗余數據和索引文件要節(jié)約大量的存儲空間，具有一定的數據獨立性和共享特性，運行效率較高，而且由于它避免了索引操作，比關系型數據庫模式要節(jié)省存儲空間，數據操作速度也更快。但是這種模型結構比較復雜，尤其當嵌入式系統(tǒng)規(guī)模增大時，其數據庫的結構變得非常龐大，可能會影響到系統(tǒng)的實時性能。圖3所示的是在相同數目的記錄下，關系模型和網狀模型的系統(tǒng)開銷比較，從圖中可以看出，網狀模型因為避免了索引操作使得其開銷要小于關系模型。但是在實際應用中，應當根據實時系統(tǒng)的綜合性能選取數據庫模型，通?？刹捎镁W狀加關系或層次加關系的混合模型結構以彌補兩種結構之間的缺陷，如CENTURA公司的嵌入式實時數據庫RDM（Raima Database Management），它將網狀和關系模型的優(yōu)點結合起來，避免了不必要的索引開銷，顯著地減少系統(tǒng)存儲空間、I/O操作和CPU周期，由于其快速而且可靠性高的特點，廣泛應用于許多嵌入式產品中。

圖3  關系和網狀模型開銷比較

嵌入式RTDBS的物理結構
    在嵌入式實時系統(tǒng)中，確定性是一個重要的性能指標，用戶必須能夠確定數據操作的時間和數據庫存儲空間的占用情況等。傳統(tǒng)的數據庫的存儲管理主要是基于磁盤存儲結構，數據在存取過程中需要進行頻繁的I/O操作，由于I/O操作時間的不確定性，使得傳統(tǒng)數據庫存儲技術無法應用在嵌入式系統(tǒng)中?？紤]到存取時間、存儲空間利用率和維護代價等因素，通常嵌入式實時系統(tǒng)的存儲結構分為兩個層次，第一層為內存，即RTDBS中的內存數據庫，整個實時數據庫系統(tǒng)的高性能要求就是以內存數據庫做為底層支持的，它是實時數據庫系統(tǒng)的關鍵，用于程序運行和實時數據的處理，它存取速度快，無需進行磁盤的I/O操作，因此最適合用于實時數據的管理和操作；第二層為外存，通常采用一些永久存儲設備，需要進行讀寫I/O操作，用于存儲系統(tǒng)中的歷史數據。這樣，對于那些固定不變的數據（如模擬量的工程單位）或存取頻率相對較低的數據（如只有在故障恢復時才使用的數據備份或日志備份）放在外存空間內，而把所有的實時數據或當前工作部分的數據駐留在內存中，避免了數據庫文件的操作，大大提升了實時數據庫系統(tǒng)的性能。對于這種兩層存儲結構中的內存部分，可由嵌入式OS自動分配，用戶也可指定系統(tǒng)的分配空間，一般由三部分共享內存構成，分別是索引區(qū)、數據區(qū)和系統(tǒng)信息區(qū)，每條記錄由表名、段號、段內偏移地址來確定。
    嵌入式RTDBS中數據的查找及更新相當頻繁，必須建立良好的索引結構以加速各種操作的執(zhí)行速度和確保數據結構的緊湊性。嵌入式RTDBS由于實時數據全部駐留內存，系統(tǒng)很少進行磁盤I/O操作，因此其索引結構重點解決時間和空間上的開銷，其建立原則是快速定位，節(jié)省空間。通常采用的數據庫索引結構為順序結構、B樹、AVL樹的方法。順序結構可采用數組方式存儲，其優(yōu)點是存取方便，但不便于動態(tài)維護，進行插入刪除等操作時需要移動大量的數據； B樹的使用最為廣泛，它操作性能好，動態(tài)維護方便，但是它的每個節(jié)點的數據覆蓋率僅為55％[3]，存儲效率太低；AVL樹具有較高的存取性能，但是每個節(jié)點需要兩個指針域和一些附加的控制信息，存儲效率也不高。它們均不是嵌入式實時環(huán)境下的最佳選擇，因此在以上結構的基礎上，出現了多種改進的適用于嵌入式數據庫系統(tǒng)的索引結構，如針對提高內存數據庫性能的T*樹索引結構[4]，這是一種改進的T樹結構，它比AVL樹和B樹具有更高的空間利用率，雖然查找時間復雜度稍高于AVL樹，但內存中的操作使得其查找時間足以滿足實時性要求，這種結構大大減少了節(jié)點間元素的移動和平衡處理的次數，較好的考慮了時間和空間的關系，是一種適用于嵌入式系統(tǒng)的索引結構；此外，針對嵌入式系統(tǒng)I/O操作性能的不平衡B樹索引結構[5]，主要為了減少存儲塊的寫次數，這種索引結構的節(jié)點由若干個關鍵字和指針域構成，每個指針指向具有相應關鍵字的文件記錄，由于不平衡B樹避免了B樹為了調節(jié)平衡產生的進一步分裂而進行的次數，因此提高了系統(tǒng)的寫性能。

嵌入式RTDBS管理系統(tǒng)
    嵌入式RTDBS系統(tǒng)是介于用戶和實時操作系統(tǒng)之間的一層軟件，由眾多程序模塊組成，它的作用是對數據庫中的共享數據進行有效的組織、管理和存取，其結構如圖4所示。其中，存儲空間管理模塊、安全性和完整性控制模塊、事務并發(fā)控制模塊、實時數據轉儲模塊、運行日志管理模塊是在嵌入式環(huán)境下開發(fā)實時數據庫系統(tǒng)需要特別解決的幾個問題：（1）存儲空間管理模塊。嵌入式實時數據庫系統(tǒng)由于采用了內存數據庫技術，必然要涉及到嵌入式操作系統(tǒng)的內存管理，因此，用戶必須了解系統(tǒng)對內存的分配機制，并設計自己的內存管理程序。系統(tǒng)運行時，由該模塊通過實時OS向系統(tǒng)申請內存緩沖區(qū)，作為共享的內存數據區(qū)使用。之后，將歷史數據庫中的初始化數據調入內存區(qū)對這些空白內存進行初始化。對內存空間的申請，用戶可采用靜態(tài)分配方式，這種方式實現簡單，無需復雜的索引結構，缺點是失去了靈活性，必須在設計階段就預先知道所需內存并對之作出分配；或者采用動態(tài)分配方式，這種方式使用靈活，可以根據需要擴充數據節(jié)點，但是必須建立合適的索引結構，以加快數據的檢索時間。該模塊要根據具體的實時OS進行設計；（2）數據安全性、完整性控制模塊。實時數據庫設計中必須考慮數據的安全性，一方面指用戶訪問數據的合法性，另一方面是指系統(tǒng)的安全性。完整性是指用戶對實時數據或歷史數據的各種操作必須符合一定的語義，可通過完整性約束條件來實現；（3）事務并發(fā)控制模塊。實時數據庫是一個共享資源，允許多個任務共同使用，如果不對并發(fā)事務進行控制，可能會造成任務錯誤的讀取或存儲數據，破壞數據的一致性，因此實時數據庫系統(tǒng)中，必須實現良好的并發(fā)控制機制。傳統(tǒng)的數據庫一般采用加鎖的方式，類似于實時操作系統(tǒng)中的信號量，對于封鎖粒度的大小要根據具體的應用系統(tǒng)確定，傳統(tǒng)數據庫獲得鎖的開銷較小，因此通常選用小粒度封鎖單位，以增加系統(tǒng)的并行性。但在實時數據庫系統(tǒng)中，事務獲得鎖的開銷與處理數據的開銷相當，過小的封鎖粒度反而會降低系統(tǒng)的性能，因此在實時數據庫中的封鎖粒度通常選擇一張關系表為一個單位（如模擬量關系表為一個封鎖單位），這樣做減少了并發(fā)控制機制的復雜度，減小了系統(tǒng)的開銷，提高了事務處理的整體性能；（4）實時數據轉儲模塊。該模塊實現的功能是將實時數據存儲為歷史數據，通常由該模塊先將歷史數據保存在內存緩沖區(qū)中，緩沖區(qū)滿時才一次性的寫入磁盤；讀歷史數據時，先從緩沖區(qū)內取數據，取不到數據時再進行文件的讀寫，這種方式可以降低磁盤I/O操作次數。并且只對變化數據進行存儲，即節(jié)省了外存空間，又不會影響系統(tǒng)性能；（5）運行日志管理模塊。日志文件在數據庫恢復中起著非常重要的作用，可以用來進行事務故障恢復和系統(tǒng)故障恢復。日志緩沖區(qū)專門存放數據庫操作的記錄，傳統(tǒng)的數據庫日志記錄包括記錄名、更新前記錄的舊值、更新后記錄的新值、事務標識、操作類型等。在嵌入式實時數據庫系統(tǒng)中，為了減少系統(tǒng)的開銷，在日志記錄中不包括新舊記錄值，對日志記錄的寫操作只對緩沖區(qū)進行，當緩沖區(qū)滿時，才由磁盤寫操作寫入日志文件當中。

圖4  嵌入式RTDBS模塊結構

嵌入式RTDBS設計實例
    我們開發(fā)了針對測控系統(tǒng)的基于嵌入式操作系統(tǒng)VxWorks的實時數據庫系統(tǒng)，該系統(tǒng)的硬件平臺采用了Intel486系列的PC104 CPU板，用戶可通過PC104硬件平臺上的顯示界面添加或刪除相應的數據節(jié)點，整個應用系統(tǒng)結構如圖5所示。該系統(tǒng)分為內存數據庫和歷史數據庫兩部分，內存數據庫是一個數據實時更新的數據庫系統(tǒng)，由應用程序初始化時靜態(tài)創(chuàng)建一個大型緩沖池，用于存放各種類型的數據節(jié)點，利用空閑鏈表管理緩沖池中的空閑單元。程序在添加新節(jié)點時，首先從空閑鏈表中找到空閑單元分配給用戶，然后鏈表中的該節(jié)點被刪除。當緩沖區(qū)內存不夠時，通過VxWorks中提供的增強型內存分區(qū)管理庫MemLib，從系統(tǒng)內存中動態(tài)申請一塊緩沖池作為新的緩沖池，這種靜態(tài)結合動態(tài)的內存分配方式可以克服內存碎片的問題，同時也避免了靜態(tài)分配中內存數據庫容量設計過大或過小的問題；對于數據索引結構，考慮到實時系統(tǒng)中數據的檢索和更新相當頻繁，結合系統(tǒng)性能要求，在嵌入式RTDBS中我們采用了L樹的索引結構，該樹結合了B+樹、T樹和AVL樹的特征，它的每一結點可含有多個關鍵字，具有較高的空間利用率，是一種比較好的支持內存數據庫的索引結構；在基于優(yōu)先級驅動的實時事務的控制上，將事務的截止時間映射為事務優(yōu)先級，最簡單的先來先服務FCFS的分配策略由于沒有考慮到定時限制，不適合用于實時系統(tǒng)，因此我們采用了最短期限的分配策略；此外，對于數據庫的管理，我們提供了傳統(tǒng)數據庫的管理功能，如添加、刪除、修改及顯示等，用戶必須以相應的權限進入系統(tǒng)才能進行操作，顯示系統(tǒng)利用VxWorks中的圖形軟件包Zinc進行開發(fā)，整個系統(tǒng)運行穩(wěn)定，能夠滿足實時系統(tǒng)的數據管理要求。

圖5  嵌入式實時數據庫應用圖示

結語
    目前，嵌入式環(huán)境下的實時數據庫開發(fā)還存在許多問題需要解決，在實際應用中的性能也有待進一步提高，其關鍵在于實時系統(tǒng)的存儲結構、數據的存取速度、實時事務的優(yōu)先級調度、故障恢復問題，這是提高實時數據庫性能的關鍵之處，也是實時數據庫系統(tǒng)理論的研究重點。

參考文獻：
1.  Olson,M.A. Selecting and Implementing an Embedded Database System. IEEE Computer.
    2000,33(9):27-34
2.  J Stankovic,et al. Misconceptions about Real-Time Databases. IEEE Computer,1999,
32(6):29-36
3.  Lehman T J, Carey M. A Study of Index Structure MMDBMS. Proc of the 12th International
Conference on Very Large Database,1986,294-303
4.  盧炎生,潘怡等.一個內存數據庫管理系統(tǒng)的數據組織.華中理工大學學報,1999，27(10):64-66
5.  楊進才,劉云生等.嵌入式實時數據庫系統(tǒng)的存儲管理.小型微型計算機系統(tǒng),2002,24(1):42-45