一種存儲和索引歷史數據流數據的方法

摘 要：通過對流數據的抽樣存儲，并在內存中建立B+樹結構，對抽樣數據和常用聚集操作進行索引，實現了對無限數據流歷史數據的抽樣存儲管理，有效地支持了數據流歷史數據查詢。

關鍵詞：數據流;歷史查詢;抽樣;存儲;索引;B+ 樹

中圖分類號：TP311.13文獻標志碼：A

文章編號：1001-3695(2007)06-0104-03

0 引言

數據流(Data Stream)應用的出現引起了國內外專家和學者的關注。數據流管理技術作為一種新興技術已經得到廣泛研究。目前通用的DSMS(Data Stream Management System)包括TelegraphCQ［1］、Aurora［2］和STREAM［3］。

TelegraphCQ致力于多數據流上的并發連續查詢的自適應和共享處理；Aurora是一個面向監測應用的DSMS，用于處理在線時序安排和負載平衡；STREAM集中于資源管理和近似連續查詢。美國加州大學伯克萊分校正在構建一個TelegraphCQ系統，該系統用于連續的數據流處理。TelegraphCQ 的目的在于處理大量高速變化的數據流而進行的大量連續查詢流。布朗大學的Aurora工程建造了一個專門用于流監控的數據處理系統。斯坦福大學已經開始了一種全面DSMS的設計和原型實現。該系統為STREAM (Stanford Stream Data Manager)。STREAM 是一個以關系為基礎的數據流管理系統，它重點在于內存管理和近似查詢。它可以用于處理快速的、易變的、大量涌入的數據流信息，其連續查詢能力非常好。STREAM 的主要處理技術包括連續的自我監控和再優化、適應于不同需要的近似查詢、合理的資源分配和使用。

目前，對數據流的研究大多集中在對當前流數據的分析和處理上。相對于數據流的連續性和無限性，存儲器的存儲能力是有限的。隨著數據的流入，舊的數據將被拋棄；當查詢涉及到歷史數據時，因為沒有可用的數據而不能得到查詢的結果。

例如，在監控某一地點實時溫度的傳感器網絡中，查詢過去一段時間的最高溫度。因為沒有歷史數據的存儲，無法得到答案。那為什么不用傳統的數據庫管理系統呢？眾所周知，傳統的數據庫管理系統（DBMS）是靜態的、有限的，查詢可以處理所有存儲的數據，但是用傳統數據庫存儲流數據是不可能的。DBMS與DSMS的比較如表1所示［4］。

表1 DBMS與DSMS比較

比較項傳統的數據庫管理系統(DBMS)數據流管理系統(DSMS)

設計原則旨在處理永久性數據。其設計與開發主要強調維護數據的完整性、一致性，不考慮與數據及其處理相關聯的時限針對具有簡單結構與聯系，穩定和可預報數據(或資源)要求的任務，支持數據及其處理的實時限制

對象靜態存儲的信息，可在任何需要的時候進行存取、檢索

以連續的、有序的“流”形式輸入。經過在線檢索后，輸入的數據被淘汰或歸檔。其中被淘汰的數據無法進行二次檢索

典型操作在持久的關系上進行一次查詢，可對欲檢索的記錄集隨機存取對暫態的流數據進行持續檢索，對輸入的流數據進行順序掃描

數據存儲利用外存儲器保持歷史數據，容量近乎無限，數據的存儲由應用程序通過數據管理語言顯式執行(被動方式)存儲和處理均在有限的主存中進行，容量有限，數據的摘要信息由系統提取并更新(主動方式)，過期的歷史數據不予保存

數據有效性查詢所得結果表示當前狀態，即有效數據

無當前狀態，數據序列中數據分量的到達時間及其到達順序決定檢索結果

針對數據流中一些歷史查詢，不僅為了節省存儲空間，還滿足數據流中的近似查詢，本文介紹了一種抽樣方法。尤其是基于時間的滑動窗口的元組數不確定的情況，采用經典的B+樹來索引所存儲的抽樣。

目前對于數據流的研究主要集中于怎樣處理當前到達的數據，而忽略了歷史流數據的分析和管理。本文采用一種抽樣的方法存儲流數據，支持歷史查詢的近似查詢，同時存儲一些常用聚集操作的結果以支持這些常用聚集操作的歷史查詢。

1 基于滑動窗口的數據流抽樣

數據流的查詢過程是持續查詢(Continuous Query)［5］。持續查詢所關心的并不是全部的數據，而是近期到達的部分數據，所以數據流中的持續查詢采用滑動窗口(Moving Window)機制［5］、基于滑動窗口的查詢。

滑動窗口可以看做是數據流有限部分的歷史性快照。基于這種定義可以將滑動窗口劃分為三種類型，即基于時間的滑動窗口、基于元組的滑動窗口和分區滑動窗口。本文的抽樣方法便是基于滑動窗口的抽樣。不同機制的滑動窗口，其特性不同，抽樣方法也不同。

1.1 基于元組的滑動窗口抽樣

數據流S基于元組的滑動窗口實質是大小固定的滑動窗口，窗口模型以正整數N作為參數。直觀地看，帶有時間的基于元組的滑動窗口的輸出關系是有序數據流到目前為止最近到達的N個元組。形式上來說，是由數據流S到目前為止最大時間戳的N個元組組成。

基于元組的滑動窗口的元組數N是已知的，在N已知的情況下從中抽樣n個（已經有很多算法支持類似的抽樣）。例如文獻[6]介紹了一種Chainsample抽樣算法。

1.2 基于時間的滑動窗口抽樣

①當T=0， R(τ) 由數據流 S中帶有時間戳的元素組成；

②當T=∞，R(τ)由數據流S中所有時間戳的元素組成。

在基于時間的滑動窗口中，窗口中的元組數N是不確定的，可能在某個時間T內，數據流速快、元組數量大；也可能在某個時間T內，接收到的數據流數據少，則N的值就小。所以本文抽樣的樣品容量n也應該是動態變化的。

1.2.1 抽樣比例

定義1 抽樣比例（Sampling Ratio）f= n/N。

其中，n為樣本容量；N為T周期內滑動窗口元組數。

為了查詢方便，為抽樣所得的樣品建立B+樹索引。n的值取決于數據流中元組的大小和存儲樣品的數據頁（Data Page）的容量以及數據頁中存儲的其他信息，如聚集結果等。抽樣比例f與抽樣數據一起存儲，可以近似逆推窗口的數據，以滿足一些近似查詢。

1.2.2 抽樣算法

基于時間的滑動窗口中N是變化的，不能提前預知，所以從中抽取n個元組的方法勢必與基于元組的滑動窗口的方案有所不同。

2 數據流歷史信息的存儲與索引

2.1 存儲

本文采用B+樹結構來索引存儲的數據。抽樣結果存儲在數據頁中；每個滑動窗口都有一個抽樣，每個抽樣對應一個數據頁。抽樣比例 f也存儲在對應的數據頁中，根據抽樣數據和抽樣比例f，可以近似逆推滑動窗口的原始數據，以滿足一些近似查詢。

在對滑動窗口抽樣時，整個窗口必須被掃描一遍。可以在抽樣的同時做一些該窗口的常用聚集操作，如SUM、MAX、MIN等；把這些常用聚集操作的結果也存儲在對應的數據頁中。當歷史查詢是所存儲的常用聚集操作時，可以得到精確的而不是近似的結果。

2.2 索引

如此海量的歷史流數據，為支持數據流查詢的快速響應，本文為眾多的數據頁建立索引，采用經典的B+樹結構。之所以采用B+樹結構，主要是基于B+樹的如下特點:所有的葉子節點中包含了全部關鍵字的信息，及指向含這些關鍵字記錄的指針；且葉子節點本身依關鍵字的大小自小而大地順序鏈接。

(2)頁節點包含所有的關鍵字

每個關鍵字有一個指針指向該關鍵字對應時間的數據頁。

每個頁節點有一個指針指向右邊的葉子節點。

(3)葉子節點

所有的葉子節點通過向右的指針鏈接在一起，所以在處理一些歷史查詢時方便快捷。例如，查詢 t0 到 t11數據流中的MAX。此查詢僅涉及到t0到 t11的滑動窗口，即僅涉及page1到 page11。通過內存中建立的B+樹索引，很快找到page1中的MAX值，然后可以直接通過葉節點的右指針依次找到剩余頁的MAX值，從而很容易得到此查詢結果。

3 結束語

采用抽樣方法存儲海量的流數據，減輕了存儲器的負載。抽樣比例和常用聚集操作結果也被一同存儲在數據頁中，用B+樹結構索引存儲的數據頁。這個方法能夠有效地存儲和分析歷史流數據。當查詢涉及歷史流數據時，如果查詢是存儲在數據頁中的常用聚集操作，則得到準確的結果；如果查詢不是存儲的聚集操作，則利用存儲的抽樣數據和抽樣比例得到近似查詢結果。因為在很多情況下，數據流查詢并不要求絕對精確，近似的結果更能滿足數據流的快速、實時響應。

筆者將數據流以離散的時間段劃分，在處理那些起止時間都是劃分時間點的查詢有較好的響應；而查詢所涉及的起止時間不是劃分點時，即使查詢是存儲的常用聚集操作也不能得到準確的答案，仍是近似的。下一步會考慮盡量將劃分的粒度縮小，即ΔT小一點。但是粒度太小了會使窗口數增加，進而使數據頁增加，花費更大的代價以維護B+樹。

本文討論的前提是在內存中建立B+樹。隨著時間的推移、數據的流入，B+樹會很大，以至于無法存儲在內存中，可以再為B+樹做二級索引。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。