內存數據庫技術在嵌入式控制系統中的應用研究

馮文飛 毛洪川 韓潔 徐聰

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

關鍵詞：內存數據庫（MMDB）；關系型磁盤數據庫（DRDB）；并發控制算法；查詢優化算法

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

1 引言

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

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

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

2 關系型DRDB和MMDB特點分析

2.1 關系型DRDB的特點

層次型數據庫適合表示數據記錄之間一對多的聯系，不便于表示多對多和多對一的聯系。網狀型數據庫的數據結構較為復雜，設計困難。 與層次型和網狀型相比，關系型MMDB具有以下特點：

（1）描述的一致性，且利用公共屬性連接；（2）采用的表結構簡單、直觀；（3）有嚴格的理論基礎（關系代數），且語言表達簡練。

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

2.2 MMDB的特點

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

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

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

2.3 MMDB和DRDB的對比

MMDB的工作版本存放在內存中，直接存取數據，不需要對緩沖區進行管理，因此其體系結構與DRDB有明顯的差異。一般的DRDB和MMDB的結構對比圖見圖1。

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

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

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

3 嵌入式控制系統中MMDB的設計與應用

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

分析了MMDB在嵌入式控制系統中的應用需求后，其結構就可描述為如圖2所示的圖形。

該類數據管理的特點決定MMDB需頻繁地執行數據添加、數據刪除、數據更新、排序及查詢操作，且這些操作往往由不同的進程（或任務）來實現，因此MMDB的數據結構、查詢優化和并發控制成為了設計的關鍵，并需結合數據結構和并發控制算法的設計，來著重進行數據庫的保護機制設計。

3.1 數據結構

為適應不同數據格式的數據管理（添加、更新、刪除、排序、查詢等）操作，設計時采用雙向鏈表的數據結構，構成環形的數據緩沖區，如圖3所示。

MMDB數據結構中每一個數據節點均采用如下的結構體形式：

typedef struct _DATA_NODE

{

unsigned char 數據標識；

unsigned char 數據長度；

unsigned char 數據報文[M]；

struct _DATA_NODE * Up；

struct _DATA_NODE * Down；

}DATA_NODE；

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

3.2 優化查詢算法

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

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

優化查詢算法設計后的MMDB數據結構中每一個數據節點均采用如下的結構體形式：

typedef struct _DATA_NODE

{

unsigned char 數據標識；

unsigned char 數據長度；

unsigned char 數據報文[M]；

數據類型1 查詢字段1；

數據類型2 查詢字段2；

… …

數據類型n 查詢字段n；

struct _DATA_NODE * Up；

struct _DATA_NODE * Down；

}DATA_NODE；

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

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

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

3.3 并發控制算法

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

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

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

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

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

關于多個任務等待獲取信號量時，任務間是依據任務優先級搶占還是時間片輪訓方式獲取信號量，屬操作系統的信號量機制和應用系統設計范疇，不加詳述。

4 結語

本文描述的內存數據庫技術已在多個嵌入式系統中得以應用，可滿足大多數實時嵌入式系統的數據管理需求。基于具體使用環境，可在數據結構和查詢算法方面進行適當調整設計，可有更廣泛的應用。目前，部分商用和開源的嵌入式數據庫采用B樹算法完成查詢算法設計[4]，經測算，在10K條級別以下的數據管理應用中，與本文設計的查詢算法效率相當。

參考文獻

[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]劉云生.現代數據庫技術[M].北京：國防工業出版社，2001.

[4]Robert Sedgewick.算法Ⅰ-Ⅳ（C++實現）：基礎、數據結構、排序和搜索[M].北京：中國電力出版社，2004.