內(nèi)存數(shù)據(jù)庫技術(shù)在嵌入式控制系統(tǒng)中的應用研究

馮文飛 毛洪川 韓潔 徐聰

摘要：論文通過分析嵌入式控制系統(tǒng)的數(shù)據(jù)管理需求，利用內(nèi)存數(shù)據(jù)庫實時性強、磁盤數(shù)據(jù)庫安全性高的特點，在對內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)、并發(fā)控制算法和查詢處理算法進行優(yōu)化設(shè)計和仿真驗證的基礎(chǔ)上，提出了內(nèi)存數(shù)據(jù)庫管理實時數(shù)據(jù)、磁盤數(shù)據(jù)庫管理記錄數(shù)據(jù)的整體數(shù)據(jù)管理解決方案。本文所建立的數(shù)據(jù)管理模型和內(nèi)存數(shù)據(jù)庫模型也可推廣至類似系統(tǒng)應用中。

關(guān)鍵詞：內(nèi)存數(shù)據(jù)庫（MMDB）；關(guān)系型磁盤數(shù)據(jù)庫（DRDB）；并發(fā)控制算法；查詢優(yōu)化算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2018）05-0127-03

1 引言

磁盤數(shù)據(jù)庫（DRDB，Disk-Resident Database）系統(tǒng)，數(shù)據(jù)存放在外部存儲器（如磁盤、FLASH盤等裝置）上進行管理，使用時數(shù)據(jù)的存取操作需通過緩沖區(qū)調(diào)度和I/O操作實現(xiàn)，可能會造成頻繁地訪問外部存儲器操作，會由于應用場景不同引起同樣的事務處理時間的不確定，較難滿足系統(tǒng)實時性要求較高的應用需求。但數(shù)據(jù)存儲于外部存儲器上，安全性較高，數(shù)據(jù)恢復機制成熟、可靠。

內(nèi)存數(shù)據(jù)庫，也稱為主存數(shù)據(jù)庫（MMDB，Main Memory Database）是數(shù)據(jù)庫技術(shù)的發(fā)展的新成果，其解決方案是“近乎于”將整個數(shù)據(jù)庫放在內(nèi)存里，重新設(shè)計其數(shù)據(jù)結(jié)構(gòu)、查詢處理算法、并發(fā)控制算法和數(shù)據(jù)恢復算法，以期更有效地利用CPU 和內(nèi)存[1]。與傳統(tǒng)DRDB相比， MMDB的數(shù)據(jù)存取和事務處理均為內(nèi)存讀寫，無需 I/O操作，其速度遠遠快于磁盤讀寫速度，且同一事務處理的時間確定性很高，可滿足對實時性要求較高的系統(tǒng)應用需求。但其工作版本直接存放于內(nèi)存中，極容易遭受操作系統(tǒng)和應用軟件的破壞，需設(shè)計完善的保護機制或數(shù)據(jù)恢復機制。

嵌入式控制系統(tǒng)中，主要的數(shù)據(jù)管理需求一般有兩類：一類是傳感器上報數(shù)據(jù)的管理，另一類是系統(tǒng)工作數(shù)據(jù)的記錄與重演。對于傳感器數(shù)據(jù)，一般需要實時完成排序、篩選、更新、刪除等處理，來實現(xiàn)解算處理、數(shù)據(jù)融合、指令生成、顯示輸出等功能，對實時性要求較高，且一般需多個進程（或任務）并行處理，因此采用MMDB，設(shè)計其數(shù)據(jù)結(jié)構(gòu)、并行控制算法和查詢處理算法。針對數(shù)據(jù)記錄和數(shù)據(jù)重演需求，記錄是僅需及時、完備地將系統(tǒng)工作數(shù)據(jù)記錄到外部存儲器上；重演時能夠按照同步時鐘控制要求從外部存儲器讀取記錄的數(shù)據(jù)即可，因此選用關(guān)系型DRDB，通過提高緩沖區(qū)空間，進行最小化磁盤 I/O 算法設(shè)計[1]，可達到接近MMDB的性能，滿足性能要求，并確保數(shù)據(jù)的安全性。

2 關(guān)系型DRDB和MMDB特點分析

2.1 關(guān)系型DRDB的特點

層次型數(shù)據(jù)庫適合表示數(shù)據(jù)記錄之間一對多的聯(lián)系，不便于表示多對多和多對一的聯(lián)系。網(wǎng)狀型數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)較為復雜，設(shè)計困難。 與層次型和網(wǎng)狀型相比，關(guān)系型MMDB具有以下特點：

（1）描述的一致性，且利用公共屬性連接；（2）采用的表結(jié)構(gòu)簡單、直觀；（3）有嚴格的理論基礎(chǔ)（關(guān)系代數(shù)），且語言表達簡練。

其缺點是：進行查詢操作時，需要執(zhí)行查表、拆表、并表等處理，時間不確定。

2.2 MMDB的特點

與DRDB相比，MMDB具有以下特點：

（1）數(shù)據(jù)的存取和事務處理直接對內(nèi)存操作，無需 I/O操作，大幅提高速度；（2）在事務執(zhí)行前將所需數(shù)據(jù)集調(diào)入內(nèi)存，提交時把所有對數(shù)據(jù)庫修改寫回磁盤，不再需要對緩沖區(qū)進行管理，消除了磁盤和內(nèi)存之間數(shù)據(jù)拷貝開銷；（3）對內(nèi)存可根據(jù)需要采用順序存取或隨機存取方式，性能基本一致；

其缺點是：對內(nèi)存的直接存取，容易因操作系統(tǒng)和應用軟件的錯誤遭受破壞。

2.3 MMDB和DRDB的對比

MMDB的工作版本存放在內(nèi)存中，直接存取數(shù)據(jù)，不需要對緩沖區(qū)進行管理，因此其體系結(jié)構(gòu)與DRDB有明顯的差異。一般的DRDB和MMDB的結(jié)構(gòu)對比圖見圖1。

如圖1所示， DRDB采用內(nèi)存緩沖區(qū)管理機制，需要把應用所需的數(shù)據(jù)復制到內(nèi)存緩沖區(qū)，應用在緩沖區(qū)里取所需數(shù)據(jù)。數(shù)據(jù)存取過程為先計算出待取記錄的磁盤地址，然后調(diào)用緩沖區(qū)管理器，查詢該記錄對應的塊是否在緩沖區(qū)中，若在則直接調(diào)用；若不在緩沖區(qū)且緩沖區(qū)已滿，需采取相應算法進行數(shù)據(jù)置換。增大緩沖區(qū)可以明顯提高磁盤數(shù)據(jù)庫的性能，如把緩沖區(qū)增大到可以存儲所有數(shù)據(jù)，并進行最小化磁盤I/O的算法設(shè)計，可達到接近內(nèi)存數(shù)據(jù)庫MMDB的性能[2]。

MMDB直接訪問內(nèi)存，不需數(shù)據(jù)緩沖區(qū)和進行緩沖區(qū)管理。Tobin J.Lehman等人曾對此進行了專門的性能測試，測試案例為：子系統(tǒng)A采用MMDB，子系統(tǒng)B采用DRDB，且將子系統(tǒng)B所需的數(shù)據(jù)完全存放在內(nèi)存緩沖區(qū)，保證兩者在事務處理期間沒有磁盤 I/O。測試結(jié)果表明，MMDB比DRDB快2.3倍～7.1倍[3]。

MMDB工作時，數(shù)據(jù)庫的主拷貝常駐于內(nèi)存，任何一個事務在執(zhí)行過程中沒有內(nèi)外存儲器之間的數(shù)據(jù) I/O，使得數(shù)據(jù)庫系統(tǒng)性能得到極大提高。同時，由于所有操作直接作用于內(nèi)存中的數(shù)據(jù)庫主拷貝，操作系統(tǒng)和應用軟件的錯誤極易使數(shù)據(jù)庫受到破壞，因此MMDB的恢復與DRDB相比較更為關(guān)鍵和復雜。MMDB的恢復機制一般仍采用日志、備份等方式，仍通過I/O操作實現(xiàn)，因此MMDB的恢復機制對數(shù)據(jù)庫性能有著非常重要的影響。

3 嵌入式控制系統(tǒng)中MMDB的設(shè)計與應用

嵌入式控制系統(tǒng)中主要應用MMDB管理傳感器數(shù)據(jù)或指令數(shù)據(jù)，這類數(shù)據(jù)的特點是數(shù)據(jù)根據(jù)外部環(huán)境“實時”產(chǎn)生，數(shù)據(jù)具有“定時處理”和“短暫有效”的特性，要求在一定時刻或一定的時間期限內(nèi)自外部環(huán)境采集數(shù)據(jù)，進行數(shù)據(jù)存取、處理，并做出響應[3]。故障時恢復的數(shù)據(jù)無“實效性”，不能繼續(xù)使用，MMDB不需要考慮設(shè)計數(shù)據(jù)恢復機制，避免了數(shù)據(jù)庫進行備份和日志時的I/O操作，確保了MMDB數(shù)據(jù)存取和事務處理的實時性。

分析了MMDB在嵌入式控制系統(tǒng)中的應用需求后，其結(jié)構(gòu)就可描述為如圖2所示的圖形。

該類數(shù)據(jù)管理的特點決定MMDB需頻繁地執(zhí)行數(shù)據(jù)添加、數(shù)據(jù)刪除、數(shù)據(jù)更新、排序及查詢操作，且這些操作往往由不同的進程（或任務）來實現(xiàn)，因此MMDB的數(shù)據(jù)結(jié)構(gòu)、查詢優(yōu)化和并發(fā)控制成為了設(shè)計的關(guān)鍵，并需結(jié)合數(shù)據(jù)結(jié)構(gòu)和并發(fā)控制算法的設(shè)計，來著重進行數(shù)據(jù)庫的保護機制設(shè)計。

3.1 數(shù)據(jù)結(jié)構(gòu)

為適應不同數(shù)據(jù)格式的數(shù)據(jù)管理（添加、更新、刪除、排序、查詢等）操作，設(shè)計時采用雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，構(gòu)成環(huán)形的數(shù)據(jù)緩沖區(qū)，如圖3所示。

MMDB數(shù)據(jù)結(jié)構(gòu)中每一個數(shù)據(jù)節(jié)點均采用如下的結(jié)構(gòu)體形式：

typedef struct _DATA_NODE

{

unsigned char 數(shù)據(jù)標識；

unsigned char 數(shù)據(jù)長度；

unsigned char 數(shù)據(jù)報文[M]；

struct _DATA_NODE * Up；

struct _DATA_NODE * Down；

}DATA_NODE；

上述的數(shù)據(jù)結(jié)構(gòu)形式，即可存儲同一類型（數(shù)據(jù)報文格式和長度相同）的數(shù)據(jù)，也可用于存儲不同類型（數(shù)據(jù)報文格式和長度不同）的數(shù)據(jù)。當某MMDB中存儲的數(shù)據(jù)需進行排序和查詢操作時，建議僅存儲同一類型的數(shù)據(jù)；若僅用于數(shù)據(jù)存儲和多進程間的數(shù)據(jù)交互應用，可用于存儲不同類型的數(shù)據(jù)。

3.2 優(yōu)化查詢算法

采用本文3.1章節(jié)描述的數(shù)據(jù)結(jié)構(gòu)，可實現(xiàn)MMDB的數(shù)據(jù)添加、更新、刪除、排序、查詢等操作，但每次在進行數(shù)據(jù)查詢時，需根據(jù)查詢內(nèi)容，對已存儲的數(shù)據(jù)節(jié)點中，選取某數(shù)據(jù)節(jié)點，根據(jù)報文協(xié)議約定解析出數(shù)據(jù)報文字符串中要查詢的字段后，與待查詢內(nèi)容比較來確定該數(shù)據(jù)節(jié)點是否為查詢結(jié)果，若是則可進行數(shù)據(jù)讀取、數(shù)據(jù)更新或數(shù)據(jù)刪除操作，若不是，則對下一個數(shù)據(jù)節(jié)點進行查詢處理。因每次查詢操作，均需對數(shù)據(jù)報文字符串進行解析，因此效率較低。

為提高查詢效率，對原始的查詢算法進行優(yōu)化，采用“犧牲空間換取效率”的策略，即在設(shè)計數(shù)據(jù)結(jié)構(gòu)時，事先將使用該MMDB所需的查詢字段獨立定義，進行數(shù)據(jù)添加和更新操作時一次完成數(shù)據(jù)解析，之后的數(shù)據(jù)查詢操作可直接比對查詢字段，不需進行多次數(shù)據(jù)解析處理，大幅提升查詢效率。

優(yōu)化查詢算法設(shè)計后的MMDB數(shù)據(jù)結(jié)構(gòu)中每一個數(shù)據(jù)節(jié)點均采用如下的結(jié)構(gòu)體形式：

typedef struct _DATA_NODE

{

unsigned char 數(shù)據(jù)標識；

unsigned char 數(shù)據(jù)長度；

unsigned char 數(shù)據(jù)報文[M]；

數(shù)據(jù)類型1 查詢字段1；

數(shù)據(jù)類型2 查詢字段2；

… …

數(shù)據(jù)類型n 查詢字段n；

struct _DATA_NODE * Up；

struct _DATA_NODE * Down；

}DATA_NODE；

以一次數(shù)據(jù)更新操作為例，兩種查詢處理算法的工作流程對比如圖4所示。

圖4中，原始查詢算法中，每一次查詢中的每一個數(shù)據(jù)節(jié)點的比較均需讀取數(shù)據(jù)報文進行解析，并記錄待查詢字段，與目標值比較來確定是否為查詢結(jié)果。在優(yōu)化后的查詢算法中，每一個數(shù)據(jù)節(jié)點僅需讀取待查詢字段，得到查詢結(jié)果后。在數(shù)據(jù)更新時僅需多進行一次查詢字段的更新操作即可。經(jīng)測算，在10K條級別的數(shù)據(jù)管理應用中，優(yōu)化后的查詢算法效率提高95%以上，存儲空間僅增加10%左右。

根據(jù)數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù)內(nèi)容和使用方式，在查詢優(yōu)化設(shè)計時，也可考慮借鑒成熟的關(guān)系數(shù)據(jù)庫排序和查詢算法和技術(shù)，如索引順序存取、B樹等技術(shù)[4]。但在數(shù)據(jù)量級別較?。?0K條數(shù)據(jù)以下）的情況下，效率提高不明顯，因此不建議采用更為復雜的數(shù)據(jù)結(jié)構(gòu)。

3.3 并發(fā)控制算法

在實時多任務嵌入式控制系統(tǒng)中，一般由多個任務/進程通過上下文切換和任務調(diào)度控制機制來實現(xiàn)多任務調(diào)度，應用系統(tǒng)無法事先獲取某個任務的運行狀態(tài)。對于某個數(shù)據(jù)庫而言，往往是多個任務都需要對其進行處理和操作，比如，有數(shù)據(jù)接收任務，需要實時地對數(shù)據(jù)庫進行數(shù)據(jù)查詢和數(shù)據(jù)更新或數(shù)據(jù)添加操作；有顯示任務和數(shù)據(jù)處理任務需要實時地從數(shù)據(jù)庫中查詢和讀取數(shù)據(jù)；有接收人工輸入的任務需要從數(shù)據(jù)庫中查詢和刪除數(shù)據(jù)。多任務對某一數(shù)據(jù)庫中的處理就需要設(shè)計數(shù)據(jù)庫系統(tǒng)的并發(fā)控制算法來實現(xiàn)。

對于有嵌入式操作系統(tǒng)支持的嵌入式系統(tǒng)應用中，操作系統(tǒng)通常會提供信號量機制（同步信號量、互斥信號量、計數(shù)信號量等）來完成多任務間的同步或互斥操作。此時，MMDB系統(tǒng)可以利用信號量實現(xiàn)并發(fā)控制，如圖5所示。

某些嵌入式系統(tǒng)應用中，若無操作系統(tǒng)支持或操作系統(tǒng)供任務間的信號量同步/互斥機制時，需應用軟件設(shè)計專用保護信號來模擬實現(xiàn)信號量同步/互斥機制，完成對數(shù)據(jù)庫使用時的并發(fā)控制和數(shù)據(jù)安全保護。

圖5中，T1時刻，任務1啟動對某數(shù)據(jù)庫的數(shù)據(jù)處理操作，需先獲取到該數(shù)據(jù)庫的保護信號量（若不能獲取，需等待）；到T3時刻，任務1完成數(shù)據(jù)處理后，釋放該數(shù)據(jù)庫的保護信號量，供完成其它數(shù)據(jù)處理的任務（包括任務1本身的下一次數(shù)據(jù)處理操作）捕獲。

T2時刻，任務2啟動對該數(shù)據(jù)庫的數(shù)據(jù)處理操作，但此刻信號量被任務1占用，任務2不能獲取需，就需等待，直至T3時刻，任務2獲取到該數(shù)據(jù)庫的保護信號量后方可對該數(shù)據(jù)庫進行處理，到T4時刻，任務2完成數(shù)據(jù)處理后，釋放該數(shù)據(jù)庫的保護信號量，供完成其它數(shù)據(jù)處理的任務（包括任務2本身的下一次數(shù)據(jù)處理操作）捕獲。

關(guān)于多個任務等待獲取信號量時，任務間是依據(jù)任務優(yōu)先級搶占還是時間片輪訓方式獲取信號量，屬操作系統(tǒng)的信號量機制和應用系統(tǒng)設(shè)計范疇，不加詳述。

4 結(jié)語

本文描述的內(nèi)存數(shù)據(jù)庫技術(shù)已在多個嵌入式系統(tǒng)中得以應用，可滿足大多數(shù)實時嵌入式系統(tǒng)的數(shù)據(jù)管理需求?；诰唧w使用環(huán)境，可在數(shù)據(jù)結(jié)構(gòu)和查詢算法方面進行適當調(diào)整設(shè)計，可有更廣泛的應用。目前，部分商用和開源的嵌入式數(shù)據(jù)庫采用B樹算法完成查詢算法設(shè)計[4]，經(jīng)測算，在10K條級別以下的數(shù)據(jù)管理應用中，與本文設(shè)計的查詢算法效率相當。

參考文獻

[1]Tobin J.Lehman， Michael J.Carey， A Study of Index Structures for Main Memory Database Management Systems， Proceedings of the Twelfth International Conference on Very LargeDataBases， Kyoto，August，1986.

[2] David J DeWitt， Randy H Katz， Frank Olken，et al.， Implementation techniques for main memory database systems，Proc，ACM SIGMOD Conf，1984.

[3]劉云生.現(xiàn)代數(shù)據(jù)庫技術(shù)[M].北京：國防工業(yè)出版社，2001.

[4]Robert Sedgewick.算法Ⅰ-Ⅳ（C++實現(xiàn)）：基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、排序和搜索[M].北京：中國電力出版社，2004.