面向實時應用的時態數據庫系統體系結構

收稿日期：2007-11-14；修回日期：2008-01-07

基金項目：國家“863”計劃資助項目(2006AA04Z182)

作者簡介：萬達(1984-)，男，安徽肥東人， 碩士研究生，主要研究方向為實時數據庫(wanda05@mails.gucas.ac.cn);王宏安(1963-)，男，研究員，博導，博士，主要研究方向為實時交互計算、實時數據庫、實時智能調度、人機交互等;王永炎(1978-)，男，工程師，博士，主要研究方向為實時數據庫;李坤(1982-)，男，博士研究生，主要研究方向為實時數據庫;李新(1978-)，男，博士，主要研究方向為數據流處理、實時調度、實時數據庫.*

(1.中國科學院 軟件研究所 人機交互技術與智能信息處理實驗室，北京 100080; 2.中國科學院 研究生院， 北京 100049)

摘 要：提出了面向實時應用的時態數據庫系統Agilor-TDB，詳細介紹了系統的體系結構。針對實時應用，實現了實時任務調度。在數據存儲方面介紹了基于時間區間的多級文件索引結構和高效的內存數據管理機制；在數據查詢方面提出了高速查詢緩存優化策略。此外，用PN模型對系統并發控制進行了詳細描述。

關鍵詞：時態數據庫；體系結構；存儲；查詢；并發控制

中圖分類號：TP392

文獻標志碼：A

文章編號：1001-3695(2008)10-2925-04

Architecture of temporal database system in real-time applications

WAN Da¹，2， WANG Hong-an¹， WANG Yong-yan¹， LI Kun¹，2， LI Xin¹，2

（1. Laboratory of Human-Computer Interaction Intelligence Information Processing， Institute of Software， Chinese Academy of Sciences， Beijing 100080， China; 2. Graduate School， Chinese Academy of Sciences， Beijing 100049， China）

Abstract:This paper proposed a temporal database system: Agilor-TDB and gave a detailed description of the overall architecture. And it realized real-time scheduled aiming at real-time application. In aspect of data storage， it discussed multi-level index scheme based on time-period and effective data management mechanism of memory. In aspect of data querying， it proposed optimized strategy of fast query cache. In addition， depicted carefully concurrency control scheme using PN model.

Key words：temporal database; architecture; storage; query; concurrency control

隨著工業控制、衛星通信、交通運輸等各個領域的發展，數據的采集和存儲變得越來越重要。傳統的關系數據庫缺乏對時序關系的支持，不能有效地存儲帶有時間屬性的數據。時態關系模型[1]的提出拓展了傳統的關系模型，對時間提供了很好的支持，時態數據庫也因此得到廣泛應用。

在實時應用領域，時態數據庫對實時數據的存儲和查詢提供了很好的支持。但是，面向實時應用的時態數據庫面臨著重要的問題：系統實時性的保證、海量數據存儲和實時查詢。

在實時應用中，每個任務的執行都有一個截止期。任務執行超過截止期，其結果將是無意義的或給系統帶來災難性結果。如果數據沒有在指定的截止期前存儲，將導致后續數據丟失；如果查詢沒有在指定截止期前返回結果，將導致查詢結果失效。

在存儲方面，由于實時數據更新頻繁，并且數據量很大，如果不進行優化存儲，將造成主存和輔存存儲空間的極大浪費。在查詢方面，由于查詢數據量巨大，如果沒有合理的索引結構或查詢機制，將導致磁盤的頻繁訪問、查詢速度緩慢、系統資源占用率高等情況，無法滿足實際應用。

針對以上的問題，本文提出了面向實時應用的時態數據庫系統體系結構Agilor-TDB。該體系結構主要包括數據存儲和數據查詢。在存儲方面，Agilor-TDB具有高效的存儲結構、壓縮算法，使磁盤空間得到了極大的節省。在查詢方面，本文設計的基于時間區間的索引結構和基于局部性原理的高速查詢緩存保證了查詢效率。此外，針對實時應用，本文設計實現了實時任務調度，使得任務可以合理地執行。

1 相關工作

傳統的商業數據庫系統，如Oracle、Sybase等為非時態數據系統，這些數據庫記錄的信息只對當前有效，而無法保存過去的信息。

從20世紀70年代開始，人們開始深入研究內嵌時間的數據庫，即時態數據庫。1977年，Kahn等人[2]發表了關于時態知識的文章。1979—1982年，Jacov Ben-Zvi提出了時態關系模型、非1NF的時態數據庫、雙時態等概念，對時態數據庫作了開創性研究。1982年，Clifford[3]引入了歷史關系模型和歷史關系代數，為時態數據庫的發展作了重要貢獻。

經過幾十年的發展，時態數據庫的理論研究目前已經比較完善，但是真正實現的時態數據庫系統并不多。目前，時態數據庫的實現大體可以分為兩類：a)在現有的關系數據庫基礎上實現一個前端應用層，以支持時態信息；b)實現自身支持時態信息的數據庫。

Andreas Steiner[4]在其博士論文中詳細描述了其開發的TimeDB，其實現屬于第一種，即建立在非時態數據庫系統上的前端應用層。TimeDB 1.0版本采用的底層數據庫是Oracle。TimeDB雖然是一個比較完備的時態數據庫管理系統，可是并沒有過多考慮實時性的要求。TO2[5]系統為面向對象的時態數據庫系統，其實現屬于第二種。目前TO2已在工業控制領域得到廣泛應用。文獻[5]給出了TO2系統的設計，TO2支持海量數據存儲，并且對系統效率進行了優化。TO2采用多級緩存機制，在提高系統效率的同時過多地占用了內存空間，并且使用率卻很低，造成了內存空間的浪費。

Agilor-TDB的設計屬于第二種，其數據緩存設計采用的共享內存機制極大地改善了TO2系統中內存空間的不足，并且也保證了運行效率。Agilor-TDB針對實時任務加入了實時調度，是一個面向實時應用的時態數據庫系統。

2 體系結構

圖1給出了Agilor-TDB系統體系結構。

a)應用程序接口層(API)分為三個部分。其中，數據采集和數據查詢分別向系統核心層提交存儲和查詢任務，并且由核心層調度完成。此外，用戶通過系統控制接口對系統進行配置管理。

b)數據文件層由文件訪問接口和數據文件組成。其文件訪問接口向核心層提供數據訪問服務。需要指出的是，文件訪問的并發控制是由核心層的并發控制部分來實現的，其本身對于文件并發訪問是透明的。

c)核心層由六個部分組成：系統配置管理、實時任務調度、數據存儲(數據緩存、存儲服務和監視狗)、數據查詢(查詢結果整合器、控制器和高速查詢緩存)、壓縮模塊(有損壓縮和無損壓縮)、系統并發控制。

數據存儲由數據緩存、存儲服務和監視狗組成。數據緩存接收數據采集端的數據，并由存儲服務存儲到數據庫。監視狗監視數據存儲部分的系統狀態，并在合適的時候采取措施。

查詢模塊由高速查詢緩存和查詢分析器組成。查詢分析器首先分析任務，然后根據分析結果查詢高速查詢緩存或數據存儲部分的數據緩存。高速查詢緩存按照一定的策略保存文件中需要被經常查詢的數據。當查詢任務被提交到高速查詢緩存后，該模塊判斷數據是否命中。如果命中，則直接返回緩存數據；否則，查詢數據文件。

數據壓縮分為有損壓縮和無損壓縮。由于有損壓縮是與數據格式相關的壓縮算法，并且系統只存儲有效數值，在有效數據進入數據緩存之前將其進行壓縮處理。Agilor-TDB采用時間復雜度為O(n)的有損壓縮算法。無損壓縮和有損壓縮的參數由系統配置管理控制。

3 實時任務調度

31 任務調度算法

在Agilor-TDB中，存在兩種不同類型的任務，即數據存儲任務和數據查詢任務，它們分別由數據采集端和數據查詢端提交到系統。在實時系統中，每個任務都必須在一定的時刻前完成，這個時刻稱為截止期(deadline)。不同任務的執行耗時和截止期是不同的。為了保證任務的有效執行，必須對其進行調度。Agilor-TDB采用最早截止期優先(earliest deadline first，EDF)[6]算法對任務進行調度。

32 分解整合器

在Agilor-TDB中，數據存儲任務和查詢任務都有一定的預期耗時和截止期，即數據存儲和查詢必須在一定的時刻前完成；否則，要么將會影響后續的數據存儲，要么查詢結果超時。但是事實上，一批數據由數據采集端到達系統時，其數值個數不確定，可能很大，也可能很小；數據查詢也是如此，其結果集也是不確定的。這就導致一個嚴重的后果，數據存儲任務或數據查詢任務的預期執行時間隨著任務的不同而變化很大。如果其中某一個任務的執行時間過長，將會嚴重影響其他任務的執行，最終使得任務調度截止期錯失率很高。

事實上，雖然單個整體任務(單個存儲或查詢任務)的執行耗時是不確定的，但是整體任務卻可以被分解為多個固定長度子任務，而每個子任務的執行耗時是可以預測的。分解器的作用就是將一個完整的存儲或查詢任務分解為多個執行耗時可預測的子任務，并將其插入到任務隊列中等待調度。整合器的作用與分解器相反，它將各個子任務執行的結果按照分解的順序進行整合，并將結果返回給用戶。

4 數據存儲

41 文件及索引結構

合理的索引結構是進行高效查詢的必要條件。數據庫中文件索引常見的有多級索引和B+樹[7]等。Agilor-TDB以有效時間[1]為索引，其中數據絕大部分是以有效時間順序到達系統的，大部分是追加操作，即需要進行插入和刪除操作的機會很少。如果以B+樹為索引結構，在調節樹的平衡方面會花費較多的系統時間，不適合在實時系統中使用。此外，Agilor-TDB中數據在文件中的存儲是以數據塊的形式存在的，每個數據塊都有一個時間區間包含該數據塊內所有的數據。由于系統的原因，每個數據塊的時間區間是有可能相交的。這一點不同于普通樹中葉子節點只含有一個關鍵字的樹，也使得必須建立合適的索引結構，以滿足高效的存儲和查詢。

圖2給出了Agilor-TDB的索引結構圖：基于時間區間的多級索引結構。其中，標號為1的節點表明該節點為一級索引；標號為2的節點表明該節點為二級索引。上下表格分別指出了一級索引和二級索引的結構圖。

一級索引表包含一個表頭和m個表項。表頭中，Ts=min(Ts1， Ts2， …， Tsm)，Te=max(Te1， Te2，…， Tem)，next域為指向下一個一級索引表的指針。第i個表項的結構為Tsi，Tei，L2addr。其中：L2addr為該表項所指向的二級索引表地址；Tsi、Tei分別指向二級索引表所有數據的起始時間和結束時間。

二級索引表包含n個表項。第i個表項的結構為Tsi，Tei，DataAddr。其中：Tsi、Tei為該表項指向的數據塊的起始時間和結束時間；DataAddr為數據塊地址。

42 數據緩存

在Agilor-TDB中，數據更新頻率極高，如果每次都將這些數據直接寫入文件，一方面將導致系統對磁盤的頻繁訪問，降低了系統效率；另一方面，使得系統不得不等待磁盤I/O，不可能滿足實時性的要求。由于系統對內存的訪問速度遠遠快于對文件的訪問速度，在系統中開辟內存數據緩存成為必然。為了使得數據緩存得到充分利用，Agilor-TDB采用了數據點共享緩沖區設計。

圖3給出了數據緩存的結構圖。其中，虛線框內的為一連續的內存區域。該內存區域由物理地址相鄰的固定大小的數據塊(cell)組成。每個數據塊又由數據區和指針區兩個部分組成。數據塊經過合理的設計，能夠滿足不同數據類型的存儲要求，并盡量避免空間浪費。

空白塊(blank cell)：未被系統使用的數據塊。

空白鏈表(blank list)：所有的空白塊首尾相接形成的單項鏈表。

數據點鏈表(tag list)：單個數據點的數據塊首尾相接形成的單項鏈表。

數據緩存的工作流程分為以下三個部分：

a)初始化。內存中所有的塊均為空白塊，因此被初始化為空白鏈表。每個數據點的頭指針被初始化為空。

b)存入數據。首先，向空白鏈表請求一定數目的空白塊；然后，將有效數據填入相應的空白塊；最后，找到相應的數據點鏈表，并將裝有有效數據的數據塊鏈接到數據點鏈表尾部。

c)取出數據。首先，找到相應的數據點鏈表，并將相應的數據取出，轉存；然后，將廢棄的數據塊鏈接到空白鏈表尾部進行回收。

43 存儲服務

歸檔：將數據緩存中的數據寫入數據文件的過程。

歸檔觸發條件(archive trigger condition)：觸發數據歸檔過程的條件。Agilor-TDB以數據值的個數為歸檔觸發條件，即數據值個數達到一定規模后就需要進行歸檔。

存儲服務的任務：將數據緩存中滿足歸檔條件的數據取出并歸檔。在此過程中還將產生數據拷貝，并提交拷貝到高速查詢緩存。

由于數據緩存中滿足歸檔條件的數據點是不確定的，有的數據點可能更新頻率很高，滿足歸檔條件的時間間隔往往很短；有的數據點則可能很長時間才更新一次。如果存儲服務采取輪詢的方式依次檢查存儲緩存中是否存在滿足條件的數據點，則效率會很低。

為了解決上述問題，Agilor-TDB引入了消息機制。圖4給出了Agilor-TDB數據存儲工作流程圖。從圖中可以看出，每當有新的數據存入數據緩存時，數據緩存檢查該數據點是否滿足歸檔條件。如果滿足，向消息隊列放置請求存儲消息。存儲服務在正常情況下處于休眠狀態，一旦發現消息隊列中有消息，便取出消息，分析其內容，然后進行相應的操作；如果消息隊列中沒有消息，則存儲服務再次進入休眠狀態，負責繼續處理直到消息隊列為空。

在分析消息內容后，存儲服務需要完成四個步驟的操作：a)從數據緩存取出數據；b)按數據類型整理數據；c)寫數據到數據文件，并提交拷貝到高速查詢緩存；d)生成索引信息，并寫入到索引文件。需要指出的是，步驟b)由于Agilor-TDB支持多種數據類型和時間精度，為了優化存儲減少數據冗余，將數據從數據緩存中取出時需要按不同類型整理數據；此外，數據的統計信息也可以在此步驟生成，并寫入數據文件。步驟c)由于該數據可能需要被頻繁查詢，需要將其提交到高速查詢緩存，并由高速查詢緩存決定是否需要將其全部或部分保存在高速查詢緩存中。

44 監視狗

由上文可知，Agilor-TDB中歸檔觸發條件是一個數據點數據值的個數。因此，當一個數據點更新頻率很低時，歸檔觸發條件往往很長時間無法為真。這將導致數據無法及時歸檔，而只能駐留在數據緩存。此時，如果數據庫意外中斷，則這些數據將會丟失。此外，如果數據緩存耗盡，而仍然沒有任何數據點使得歸檔觸發條件為真，則可能造成系統死鎖。因此，Agilor-TDB使用監視狗定期對數據緩存進行掃描。圖4給出了監視狗工作機制，如果發現數據緩存中有數據駐留的時間過長或者數據緩存的使用率已經過高，其將向消息隊列發送強制歸檔的消息，并通知存儲服務進行強制存儲。

5 數據查詢

查詢子任務經過實時調度后，被提交到查詢分析器。查詢分析器根據查詢條件分別查詢數據文件或數據緩存，最后查詢結果綜合，并將結果返回。當查詢數據文件時，查詢分析器首先查詢高速查詢緩存。如果命中，則可以直接返回數據;否則，高速查詢緩存將查詢數據文件，并返回數據。

51 高速查詢緩存

大量的數據統計顯示，用戶查詢的數據不是隨機的，而是有規律的。如果能使頻繁查詢數據盡可能地駐留內存，將會極大地提高查詢效率。

圖5給出了Agilor-TDB高速查詢緩存結構圖。

1）查詢任務統計信息區 記錄查詢任務的統計信息，如查詢頻率、頻繁查詢時間區間等。

2）存儲判斷器 判斷由存儲服務發送的數據拷貝是否需要放入高速查詢緩存中。其需要查詢任務統計信息區提供統計信息。

3）存儲控制器 對物理內存進行訪問，當空間不夠時進行調頁處理。

4）查詢控制器 根據查詢任務更新查詢任務統計信息；判斷數據是否命中；進行文件查詢。

5）物理內存區 用于緩存數據的內存空間。

數據緩存的工作流程分為兩個部分：

a)圖5左部是存儲服務數據拷貝的提交和處理過程。當存儲服務的數據拷貝提交到高速查詢緩存時，它需要經過存儲判斷器，首先從查詢任務統計信息塊中獲取信息，然后判斷數據是否需要放入高速查詢緩存中。如果需要，將數據提交到存儲控制器，并由存儲控制器寫入物理內存；如果不需要，則直接丟棄。

b)圖5右部是查詢控制器接收到來自上層的查詢任務的查詢過程。當其接收到查詢任務后，首先根據任務中的查詢信息更新查詢任務統計信息；然后判斷所需要查詢的數據是否存在于快速查詢緩存。如果存在，則請求存儲控制器讀取數據；如果緩存中只存在部分數據或不存在，則查詢文件數據。查詢文件時可能會將必要的數據預讀到高速查詢緩存中。

52 文件查詢

為了減少磁盤訪問的次數，快速定位數據在文件中的位置，Agilor-TDB設計了基于時間區間的多級索引機制。對于每一個以時間為索引的數據，Agilor-TDB用至多三次的磁盤訪問就可以實現。

其在單文件中的查詢流程可以描述為三部分：

a)對該數據文件定位包含所需數據的一級索引表集。

b)對每個一級索引表結果集定位包含所需數據的二級索引表集。

c)對每個二級索引表結果集定位包含所需數據的數據塊，并讀取數據。

6 并發控制機制

在數據庫系統中，并發的優勢[8]是明顯的：提高系統吞吐量和資源利用率；減少等待時間。在Agilor-TDB中，特點也是類似的，很多模塊是可以并發或并行的。例如數據查詢過程和數據存儲過程可以并行工作；數據存入數據緩存過程和存儲服務也可以在一定程度上并行工作。但并發控制帶來的問題就是操作對資源的訪問需要互斥或同步。與很多系統一樣，在Agilor-TDB中，讀—讀操作是可以并行執行的，讀—寫和寫—寫操作必須互斥。為此，Agilor-TDB引入了讀寫鎖，以滿足上述要求。

61 文件訪問并發控制

由于文件系統對單個文件的大小是有限制的，而Agilor-TDB的數據量又是巨大的，需要將數據存儲在多個文件中。

數據文件隊列：將數據文件按照生成時間的先后順序安排并形成的邏輯上相連的隊列。其中，最舊文件位于隊列頭部，最新的數據文件位于隊列尾部。

活動文件：當前存儲服務進行數據存儲操作的文件，即文件隊列的最新文件。

起始文件：當前數據文件隊列中的最舊文件。

中間文件：數據文件隊列中，除起始文件和活動文件以外的文件。

圖6給出了Agilor-TDB數據文件隊列模型。其中，數據查詢需要對所有的數據文件進行讀操作；數據存儲只對活動文件進行寫操作。當文件隊列長度超過默認長度時，隊列管理需要刪除當前起始文件，可視為寫操作。因此，對起始文件和活動文件的訪問需要進行讀—寫互斥。

62 系統并發PN模型

在共享資源模型中，Petri網(PN)[9]可以很好地描述對資源的共享訪問。圖7通過Petri網給出了Agilor-TDB主要模塊的并發模型。該PN模型包括三個部分：

a)數據緩存過程。從圖7中可以看出，當有數據需要寫入緩存時，其狀態進入等待緩存狀態；接著，如果數據緩存可用，將執行寫入緩存操作；最后釋放緩存，并向消息隊列準備計數加1，回到初始狀態。

b)數據存儲過程。圖7左下所示的是存儲數據需要滿足存儲服務空閑、數據緩存可用、消息隊列有消息、當前活動文件可用四個條件。需要指出的是，當消息隊列準備中的令牌(token)個數達到M個時，它才會轉向消息隊列有消息狀態。

c)查詢工作流程。圖7右邊所示的是查詢工作流程。該部分圖示為一個標準的查詢流程，在實際情況中，查詢起始文件、查詢中間文件、查詢活動文件和查詢數據緩存并不都是同時需要執行的。

在標準的流程中，當查詢任務被提交到系統后，首先查詢起始文件。此時，需要保證起始文件可用，因為由6.1節可知，隊列管理程序可能正在刪除起始文件。然后查詢過程查詢中間文件，由于中間文件不可能被執行刪除或寫入操作，可以直接執行。最后進入查詢活動文件和查詢數據緩存部分。查詢完畢后恢復初始狀態。

需要注意的是，在查詢活動文件和查詢數據緩存時，必須有活動文件可用和數據緩存可用兩個條件同時滿足。其原因是明顯的。考慮這樣的情況：查詢模塊開始查詢活動文件，將活動文件鎖住。這時存儲服務不能將數據寫入文件，但是其可以將數據緩存中的數據拷貝到自身緩沖區，并完成數據整理，然后等待寫入文件。查詢活動文件結束后，活動文件被釋放，這時存儲服務可以將數據寫入文件，而系統也可以接著去查詢數據緩存中的數據。問題產生了，如果剛剛被存儲服務寫入文件中的數據恰好是需要查詢的數據，查詢就會將這一部分數據忽略，這顯然是錯誤的。

7 結束語

面向實時應用的Agilor-TDB時態數據庫系統對時態數據的存儲和查詢提供了很好的支持。對實時任務的分解和整合使得任務調度成為可能。在數據存儲方面，海量數據的優化存儲大大減少了主存和輔存空間的浪費；在數據查詢方面，高效的索引結構和緩存機制保證了數據查詢效率。此外，合理的并發控制機制。在滿足多任務并行執行的同時，維持了對數據訪問的一致性。

由于Agilor-TDB以時間為索引，對以時間為關鍵字的查詢具有很高的效率，這也在一定程度上限制了其以非時間關鍵字查詢的效率。另外，為了使得Agilor-TDB系統更加完備，對時態結構化查詢語言(T-SQL)[10]的支持是進一步的工作。

參考文獻：

[1]JENSEN C S， DYRESON C E. The consensus glossary of temporal database concepts-february 1998 version[C]//ETZION O， JAJODIA S， SRIPADA S. Temporal database-research and practice. Berlin Springer-Verlag，1998:367-405.

[2]KAHN K M， GORRY G. Mechanizing temporal knowledge[J]. Artificial Intelligence， 1977， 9(2):87-108.

[3]CLIFFORD J. A logical framework for the temporal semantics and natural language querying of historical database[D]. Stony Brook:State University of New York， 1982.

[4]STEINER A. TimeDB: a temporal relational DBMS[EB/OL]. http://www.timeconsult.com/Software/Software.html.

[5]章峰.面向對象的時態數據庫系統研究和開發[D]. 北京：中國科學院軟件研究所，2001.

[6]LIU C L， LAYLAND J W. Scheduling algorithms for multiprogramming in hard real-time environment[J]. Journal of the ACM， 1973， 20(1):46-61.

[7]GARCIA-MOLINA H， ULLMAN J D， WIDOM J. Database systems: the complete book[M]. Upper Saddle River， NJ: Prentice Hall PTR， 2001.

[8]SILBERSCHATZ A， KORTH H E， SUDARSHAN S. Database system concepts[M]. [S.l.]: McGraw-Hill， 2003.

[9]林闖. 計算機網絡與計算機系統性能評價[M]. 北京：清華大學出版社， 2001.

[10]湯庸. 時態數據庫導論[M]. 北京：北京大學出版社， 2004.