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

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

圖1  嵌入式應(yīng)用基本結(jié)構(gòu)

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

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

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

圖3  關(guān)系和網(wǎng)狀模型開銷比較

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

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

圖4  嵌入式RTDBS模塊結(jié)構(gòu)

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

圖5  嵌入式實時數(shù)據(jù)庫應(yīng)用圖示

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

參考文獻(xiàn)：
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.  盧炎生,潘怡等.一個內(nèi)存數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)組織.華中理工大學(xué)學(xué)報,1999，27(10):64-66
5.  楊進(jìn)才,劉云生等.嵌入式實時數(shù)據(jù)庫系統(tǒng)的存儲管理.小型微型計算機系統(tǒng),2002,24(1):42-45