數據流系統降載研究綜述

收稿日期：2008-01-15；修回日期：2008-03-17

基金項目：國家“十一五”支撐計劃資助項目（2006BAH02A00）

作者簡介：陳軍(1973-)，男，山東棗莊人，博士研究生，主要研究方向為數據流、數據挖掘(cy7477@uestc.edu.cn)；周明天(1939-)，男，教授，博導，主要研究方向為網絡計算、信息安全；楊曉燕(1977-)，女，講師，博士研究生，主要研究方向為電子商務、供應鏈管理.

(1.電子科技大學 計算機科學與工程學院，成都 610054; 2. 西安工程大學 管理學院，西安 710048)

摘 要：在介紹數據流及數據流系統的模型后，對降載時的系統約束、輸出質量目標進行了正式闡述。提出數據流系統降載策略的分類方法，著重分析了目前一些較為重要的數據流系統降載策略，指出其特征和應用范圍，最后總結了好的數據流降載策略應具有的特點以及未來研究的發展趨勢。

關鍵詞：數據流系統; 降載；數據流管理系統; 窗口

中圖分類號：TP311.13

文獻標志碼：A

文章編號：1001-3695(2008)10-2898-05

Survey of load shedding in data stream system

CHEN Jun¹， ZHOU Ming-tian¹， YANG Xiao-yan²

(1.School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China; 2.School of Management， Xi’an Polytechnic University， Xi’an 710048， China)

Abstract:After describing the models of data streams and data stream systems， this paper presented the system constraints of load shedding and the output goals. It presented the classification standards for load shedding in data stream systems. Then analyzed the key mechanisms of existing representative strategies， their characteristic and application area. Finally，summarizedthe important features that good load shedding strategies， and introduced the future strategies and trends.

Key words：data stream system; load shedding; data stream managemant system; window

近年來，在入侵竊密檢測、電子商務應用、無線傳感器網絡、因特網流量檢測和醫療生命信號監測等許多應用領域，一種新型數據模型——數據流引起人們的廣泛關注。采用傳統DBMS處理數據流并不可行[1]，為此已開發許多數據流管理系統（data stream management system， DSMS）或原型系統，如STREAM[2]、TelegraphCQ[3]、Niagara[4]、Aurora[5]等。數據流源，如通信網絡流量、金融市場的事務等，經常呈現突發性和波動性。當數據流輸入率超過DSMS的處理能力時，DSMS不能處理所有的輸入數據流，也不能與數據流到達率保持一致。此時采用降載技術[6]，即丟棄輸入數據流的部分數據，可降低系統負荷，為應用提供及時的、最新的查詢響應。由于降載時丟棄部分數據，降載結果和未執行降載的原始結果必然不同。有效的降載算法應能克服過載，同時最小化原始結果與降載結果之間的差。本文分析并總結了當前比較重要的數據流降載算法，指出了面臨的挑戰和將來的研究展望，為數據流降載算法的進一步研究提供參考。

1 數據流系統降載概述

在數據流應用中，數據流連續、實時到達、高度動態波動、沒有邊界、不可預測，也不受DSMS的控制。數據流的在線處理要求和潛在較高的輸入率對DSMS施加了較大的資源需求，數據流突發時的數據模式和穩態時的數據模式也可能并不相同。即使采用并行技術，也不一定能保證在任意時刻可利用的資源均能滿足需求，因此為數據流系統提供充足能力以完全正常地處理峰值負荷并不現實。

DSMS優化調度策略雖可降低最高存儲需求、數據延遲或者最大化吞吐率，但不能提高系統的最大處理能力。因此，當DSMS過載時必須采用降載技術滿足系統的處理要求。

1）系統模型

DSMS不能控制數據流的輸入率，除被動跟上數據流外別無選擇，因此數據流系統必須強制采用基于推的處理方式。將一些輸入數據暫存到磁盤上待空閑時再處理的方法會帶來較大的處理延遲，不能滿足數據流聯機處理要求，故系統需要在內存中處理輸入數據，且通常只能掃描一遍輸入數據。

輸入數據流在遠端設備產生，經由網絡發給DSMS。為平抑數據流的波動，到達的數據流項首先被放入一個輸入隊列。當查詢引擎空閑時，從隊列中取出數據項執行查詢操作。

DSMS使用監測器獲取輸入數據流和DSMS的狀態參數，如輸入流的分布特征，并根據這些參數作出降載決策。

2）輸入數據流模型

a)頻率模型[7]。它指數據流項的屬性值在流中具有粗略的固定頻率分布。頻率分布已知或可根據從監測器獲取的信息推導出來。降載時，根據屬性值的頻率分布和查詢計劃丟棄產生的降載結果的QoS較低的數據流項。

b)年齡模型。有許多流應用并不適合頻率模型，如外鍵連接等。年齡模型[8]根據數據流項在隊列中保留時間的長短來判斷其產生結果的QoS。根據輸出結果和保留時間長短繪制的曲線稱為年齡曲線，不同的應用具有不同的年齡曲線。

c)隨機模型。頻率模型和 年齡模型都使用監測器來監測輸入數據流的特征，必然產生額外的開銷。而隨機模型[9]認為從一個流到達的數據流項獨立于從另一個流到達的數據流項，這樣無須使用監測器也可降低降載算法的開銷。

3）資源約束

處理數據流DSMS需要的系統資源主要有計算資源和存儲資源。計算資源是指系統CPU的處理能力，CPU處理查詢的速率要大于等于數據流的輸入率；存儲資源是指可使用的存儲必須足以保存執行查詢產生的所有狀態。

相應地，系統的資源瓶頸有兩類：CPU受限和存儲受限。CPU受限時，有足夠的存儲可保存查詢產生的所有狀態，但沒有足夠的存儲容量應對由于CPU來不及處理而導致的緩沖隊列的無限增長。CPU受限是產生存儲受限的一個原因，反之并不成立。為降低CPU的利用率而降載可減少需要保持的狀態，故降低CPU的利用率是解決存儲受限的一個方案。

4）降載的輸出質量目標

降載時，由于丟棄部分元組，系統不能產生所有的輸出結果。不同的流應用對輸出結果有不同的要求，要由不同的降載模式來產生。對這些不同的要求，根據輸出結果和原始結果的關系可以分為三類：

a)最大子集，即原始結果的最大子集或最大回歸。降載產生的所有輸出結果保證是原始結果的一個子集。當應用依賴于輸出結果的正確性時，該特征非常重要。該要求本質上認為每個元組的重要性相同，挑戰是提供最大的可能子集結果。

b)采樣結果，即原始結果的近似結果。降載時產生的輸出結果數量與穩態時相同，但是降低了輸出結果的質量，每個輸出結果可能是原始輸出結果的近似值。降載的目標是獲得原始結果的統一隨機樣本，若不能獲得，那么樣本應盡可能逼近統一樣本。挑戰是保證誤差在設定范圍內。

c)輸出延遲，數據流項的處理延遲是指數據流項從進入DSMS到離開DSMS所需要的時間。該輸出目標的挑戰是如何降載以保證滿足處理延遲要求的同時盡可能少地丟棄數據。

5）降載問題的正式描述

當輸入數據流到達率超過系統處理能力時，需執行降載。

a)輸入：一組注冊的查詢以及查詢計劃中算子的選擇性參數和每元組處理時間參數等；一組輸入數據流，其參數有數據流的到達率等；一組相關的信息，如輸入數據流的統計信息，數據流元組平均值和標準偏差的估計值等。

b)輸出：使得系統的處理能力應大于等于輸入流需要的處理能力，并盡可能滿足降載的輸出質量目標。

2 降載策略的分類

為滿足數據流應用的不同目標要求，需采用不同的降載策略。降載策略的分類方法如下：

a）降載位置?？梢栽跀祿鳟a生的位置進行降載，也可以在DSMS處降載。在DSMS處降載又可分為在數據流項處理之前降載、查詢計劃中降載或者對數據流項不丟棄而等待其自然過期。

b）數據流項丟棄的方式。CF（coin flipping）法在接收數據流項時根據概率判斷是丟棄還是插入到隊列中，插入隊列的數據流項要參與后面的所有查詢運算；INC（insert-no-compute）法接收所有的數據流項，根據CF法判斷是否參與查詢運算；CNI（compute-no-insert）法接收的每個數據流項都要執行查詢運算，是否插入隊列根據CF法判斷。

c)數據流項丟棄策略。（a）隨機丟棄指數據流項到達DSMS時，不考慮數據流項值，也不考慮該數據流項產生的輸出，而是根據概率丟棄。這種策略開銷小，但會產生次優輸出集。（b）QoS丟棄指定義一個數據流項的質量，如數據流項最終期限丟失率，將低優先級的數據流項丟棄。（c）語義丟棄則是根據數據流項的分布特征選擇要丟棄的數據流項。（d）重要性丟棄根據內嵌于數據流項內的重要性值進行丟棄。

d）降載機制。靜態機制在離線狀態時計算降載模式；動態機制根據動態變化的輸入流計算降載模式；而自適應機制在每個時間步重新計算和更新降載模式。

e）QoS的設定。系統指定QoS根據某個QoS設計降載機制；用戶指定QoS根據用戶設定的QoS動態設計降載機制。

f）降載粒度。屬性粒度以數據流項的屬性為單位進行丟棄；元組粒度以數據流項為單位進行丟棄；窗口粒度則以窗口為單位進行丟棄。

g）先驗信息。有的降載機制需要根據數據流的先驗知識降載，有的降載機制則不需要先驗信息。

h）數據流的時間域。某些降載機制考慮的是離散的時間域，某些考慮的是連續時間域。

i）窗口的分類?？墒褂玫牟煌愋偷拇翱谌鐣r間窗口、元組窗口或者滑動窗口、滾動窗口或者界標窗口。

3 降載策略的挑戰

當輸入數據流的處理要求超過系統處理能力的時候降載，其面臨很多的技術挑戰：

a）降載的開銷。當激活降載機制時，系統已處于過載狀態，激活降載必然引入額外的開銷，這是一個矛盾。

b）為獲得最優的輸出質量，需要根據系統信息和輸入流的信息確定降載決策，而這需要監測系統的運行狀態和輸入流的特征，又將引入額外的開銷。

c）在選擇降載策略時，需要選擇開銷小且可獲得最優輸出的策略，而這需要計算降載策略的開銷。為估計開銷需設計一個成本模型。由于系統時刻在動態變化，如何設計合理的成本模型是一個挑戰。

d）降載策略需要保證系統的魯棒性和穩定性；執行和不執行降載策略時不能出現系統顛簸現象。

4 降載策略

降載策略由于應用查詢和輸出目標不一樣而有各自不同的降載策略。本文選擇其中的典型降載策略進行分析。

4. 1 基于經典反饋控制理論的降載策略[10，11]

圖1為根據經典反饋控制理論設計的降載架構，降載架構的不同組件構成了三個反饋循環：一個外環和兩個內環。圖中陰影部分為被控系統的新添組件。

系統輸出y為被控變量，定義為某個時刻描述系統性能的一個參數；ye為性能參照變量，代表系統的期望性能參照值;性能參照ye和被控變量y的差為控制誤差e;u代表操縱變量，是指為影響被控變量，系統能夠動態改變的系統屬性，如數據流到達率;x為控制器變量。Plant為被控系統，可為不同的DSMS；monitor監測系統的被控變量。外環的目標是在輸入負荷和系統配置動態變動的情況下，準確跟蹤被控變量。核心是controller，負責將控制誤差映射為操縱變量;controller輸出操縱變量，load shedder根據操縱變量對系統進行降載，即確定如何丟棄數據以使進入plant的數據經處理后滿足期望性能的要求。

系統模型動態變化時，內環1可對系統進行更好的控制。Self-tuning module的輸入為被控變量和操作變量，根據被控系統的實時參數估計對controller進行在線修改。更多系統特征的突然變化（如調度策略）由內環2處理。運行時，concept selector以關鍵系統特征作輸入，判斷系統運行時狀態的變化，并據此選擇相適應的controller參數。

反饋控制循環的設計包括系統建模和設計controller。采用系統識別技術對系統建模。根據控制理論提供的一系列工具去設計和調節控制器，并在受到干擾的情況下保證性能;使用控制度量可以正式描述降載算法的性能。重要的控制度量參數包括穩定性、穩態誤差、收斂速率和系統阻尼等?？刂破鞯脑O計是離線的過程，僅僅需要進行一次。

基于經典反饋控制理論的策略可以解決DSMS降載時容易出現的過反應或者欠反應問題；對突發大流量的輸入數據流反應速度比較快，具有較高的動態響應特性；采用被控變量進行降載，可以實現系統的高度魯棒性和穩定性；在降載同樣數量的輸入數據時，可獲得更高的輸出精度；控制理論提供許多工具可用于設計控制器；load shedder組件可單獨、也可與不同的DSMS聯合執行降載任務。但是DSMS一般為復雜的時變和非線性系統，其模型會隨時間而變化，采用分析和實驗方法建立其近似模型，并以此為基礎降載會導致系統輸出的準確度受到一定的影響。當系統特征波動較大時，建立的模型有可能偏離系統特征。被控變量的近似處理引入了估計誤差，該誤差會隨著時間而變化，當波動較大時，必須要考慮該誤差是否可能會影響系統的魯棒性。為適應系統特征的變化，需要周期地采樣系統特征參數。采樣周期是系統的一個重要參數，錯誤地選擇采樣周期將會惡化閉環的性能。系統波動大時，self-tu-ning module和concept selector需要頻繁地調節controller，其開銷以及降載的開銷可能會較大而不能將其忽略。

42 STREAM的降載策略[12，13]

STREAM的降載策略主要研究數據流的滑動窗口聚合操作，并假設所有的查詢同等重要。在STREAM中，查詢計劃的所有算子構成一個有向非循環數據流圖，在一個查詢計劃的不同點引入降載算子來實現降載。每個降載算子有一個采樣率參數p，以概率p將元組傳遞給下一個操作符，以概率1-p將其丟棄。一些動態變化的參數，如算子的選擇性、數據流項消耗量和平均處理時間等，會導致產生的誤差偏離期望的誤差，故需要周期地重新計算采樣率。STREAM將降載時應滿足的系統負荷定義為一個負荷等式。降載算法分成兩步：a)在所有查詢之間平均分布誤差；b)獲得適當的輸出速率并滿足負荷等式，考慮公共查詢子表達式共享的情況，確定在數據流圖的哪個位置進行降載。

STREAM的策略可以擴展到具有不同優先級的查詢運算；當輸入數據流波動時，不用修改每個降載算子的采樣率，僅需改變初始段降載算子的采樣率；可以為查詢設定不同的QoS；處理除可應用于聚合查詢外，也可應用于集合值查詢或者監測查詢。該策略針對的是單個流的運算，因此無法實現連接等類型的操作；由于系統作降載決策所用的參數隨數據流的波動而變化，需周期地重新估計這些參數，并改變降載策略，這將會導致系統的開銷增大；采用相對誤差作為目標函數，適合聚合運算，但不適合別的查詢運算；采用隨機丟棄策略，沒有考慮數據流項的語義。

43 基于屬性的降載策略[14]

基于屬性的降載策略假設數據流中的每個數據流項同等重要，刪除任一項都會對結果產生較大影響，因此降載時不能直接丟棄數據流項。數據流降載時，首先對所有數據流項作預處理，減小不規則性；然后計算降載模式，包括指定要丟棄的屬性和需要的降載量；當窗口滑動時，實時計算和更新數據流的降載模式。若有多個數據流，由一個中心降載器負責判斷是否需要降載，若需要降載，還需確定降載量；再根據算法將每個數據流需要降載的量傳遞給對應數據流，由每個數據流獨立作出降載決策。

基于屬性的降載策略應用范圍廣；在每個滑動窗口計算和更新降載模式，具有高度的動態性；由于只是丟棄信息熵較小的屬性，可最小化信息的損失。該策略要求數據流具有高度規則性和重復性；在每個滑動窗口更新降載模式時，若窗口小，則計算開銷會比較大；中心降載器需要周期性確定是否降載以及降載量，如何確定采樣周期也沒有行之有效的算法。

44 基于窗口的降載策略[15，16]

基于窗口的降載策略應用于Aurora/Borealis數據流處理系統[17]的連續聚合查詢。連續查詢根據由盒子、箭頭構成的數據流圖來定義，構成查詢網絡。降載組件連續監測查詢網絡的CPU負荷，若過載，將一種新型刪除算子——窗口刪除算子插入到查詢網絡中。該算子使用查詢計劃的下游聚合算子的窗口屬性，如窗口尺寸和窗口滑動幅度，邏輯上將流以窗口為單位進行劃分，并根據一定概率刪除整個窗口。

窗口降載策略產生的輸出結果為原始結果的一個最大子集，對需要準確結果的應用具有重要意義。其適用范圍廣，可處理任意的聚合函數，如用戶自定義聚合函數、多重聚合函數和共享查詢計劃等；無論聚合運算在查詢計劃中哪一點，窗口刪除算子都可越過并定位于查詢計劃的更早點，可最大化節省處理工作量。該算法以窗口為單位，刪除粒度較大，有可能導致刪除過量數據，不適合對多個數據流的連接等運算；在刪除窗口時根據概率隨機刪除，而沒有考慮數據的優先級；產生的輸出結果會有間隔，且間隔不確定。

45 基于雙窗口的降載策略[18]

雙窗口降載策略模型中，每個流包括兩個窗口：a)連接窗口，保存用于執行連接運算的數據流項；b)輔助窗口，與連接窗口大小相同，有一個窗口計數器，算法根據其統計信息刪除產生較少結果的數據流項。

該策略包括兩種降載策略，即前端降載和后端降載。系統過載不太嚴重時采用后端降載，即獲取輔助窗口的統計信息，根據語義選擇丟棄的數據流項；當過載很嚴重，后端降載可能仍不能滿足系統負荷要求，則采用前端降載，即在輸入隊列前插入刪除算子，根據概率將到達的數據流項丟棄或者入隊。當數據流速率比變化時，需動態改變窗口大小并保持窗口計數器有效，以實現降載不受調整過程影響。為提高運算的效率，該策略采用了二叉索引樹存儲結構。

算法的前端降載可在數據流率過高時有效降低輸入負荷；后端降載輸出最大子集，對降載的數據流項不是丟棄而是不參與連接運算，增加了輸出結果的數量。對不同的流速率的情況也可有效適應。但是算法僅適應兩個流的等值連接，當多個流要執行運算，窗口尺寸會比較大，存儲開銷也要增大；當兩個流的速率比波動大，需要頻繁調整窗口的大小，這需要耗費很多的CPU周期。用來計算連接成本的參數隨系統動態變化，因此計算出的系統模型可能會偏離實際狀態。

46 基于查詢優先級的降載策略[19]

基末查詢優先級的降載策略根據查詢的優先級、QoD對算術比較或帶有聚合操作的且不考慮多個流的連接運算，將重要性最低的數據流項丟棄。該策略系統結構如圖2所示。降載器放在數據流進入系統的開始處，即查詢處理器處理數據流項之前的位置，這對于沒有共享的運算是最好的地方。降載器負載確定降載算法。統計管理器為降載器提供必要的信息，如查詢信息和數據區信息。根據查詢謂詞將數據流的數據域劃分為多個不重疊的區域。降載器根據統計管理器提供的每個數據區的參數確定其QoD。當系統過載時，將對應QoD最小的首先刪除，即過濾掉該部分數據流項。

該策略根據查詢優先級進行降載，適合于查詢重要性不同的應用；以謂詞為基準劃分數據區降載，開銷比較小。但是當查詢較多時，劃分的數據區會很多，導致QoD表很大，當數據流波動較大時，維護QoD表的開銷也較大。該算法沒有考慮數據流項的語義。

47 基于緩沖前置的降載策略[20]

許多降載策略基于數據流項的處理成本，但是該成本值波動較大。基于緩沖前置的降載策略可使DSMS具有高度的自適應性，其系統框架如圖3所示。

系統架構包括上行數據流和下行數據流兩部分。PI controller接收monitor發送的輸出結果的QoS，并確定下一個監測周期中流入查詢處理器的數據流項?；诮浀淇刂评碚摰慕递d策略當CPU在最大能力附近波動時會導致丟棄過多數據項，在最前面放置一個緩沖管理器調節緩沖區可消除該問題。緩沖管理器內嵌三個模塊：a)調度器，分配存儲資源并將數據項調度進/出其對應的隊列；b)適配器，當隊列溢出時丟棄負荷；c)清除器，負責將不符合QoS的數據項丟棄。

當輸入負荷在CPU峰值處理能力附近波動時，該策略丟棄更少的數據項；數據項的處理成本隨系統動態變化，更符合實際系統的情況；較早地丟棄不能滿足QoS的數據項可節省后續的處理成本。但當輸入數據流的數量很大時，監測系統的CPU和存儲開銷會很大；若DSMS的特征波動較大，需要頻繁計算處理成本，降載開銷將會增大；沒有考慮數據項語義，重要的數據項在隊列中等待時就可能超過QoS，導致被從隊列中刪除。

48 基于范圍的降載策略[21]

基于范圍的降載策略考慮的數據項的類型不是整型而是更符合實際情況的實數類型。由于數據流的分布未知，使用固定數量的存儲資源、采用群集技術為每個滑動窗口構造一個CR-histogram以建立統計信息。算法不是對所有輸入的數據項執行降載，而是根據CR-histogram和ADC-table選擇降載的數據項。

在CR-histogram中有兩個域：range域表示連接屬性的范圍；counter表示對應range范圍內且在窗口中的數據項的數量。采用群集計算獲取range準確范圍；為獲取屬性域的分布，采用聚類技術更新range域。ADC-table包括三個域：a)ARange使用對應窗口的CR-histogram的range域構建；b)ACounter表示本窗口在對應窗口的range范圍內的數據項格式；c)ADCounter表示范圍的平均值。當本窗口變動時，對應的窗口也要更新。當一個數據項到達系統時，在對應窗口搜索包括該數據項的range，然后計算ADC，掃描ADT-table，判斷是否小于降載率，若小于則插入窗口而不執行計算。

基于聯合的降載策略不需要預知數據流的分布特征，而是采用聚類技術來在線獲取；系統的存儲開銷較??；算法需周期更新range范圍，聚簇周期沒有理論的方法可以使用，也不適合處理非等值連接或者多流連接查詢。

49 基于聯合的降載策略[22]

基于聯合的降載策略將約束分為兩類：每個流需要降載的量已知的本地約束和需要降載的總量已知的全局約束。對于本地約束，IS（independent shedding）策略中每個流獨立地執行降載決策，而不考慮不同流之間的關系，因此產生的輸出結果不一定是最大子集。

考慮不同流之間的聯合關系，BLAS（basic local associated shedding）算法將所有的流按照一定的關系排列順序，稱為降載順序。為獲得最大子集，BLAS算法需要探測降載順序空間并選擇能產生輸出最大子集的降載順序。當輸入流很多時，時間復雜度和空間復雜度都是不可接受的。MxLF（max loss first associated）算法采用流損失率，即丟棄該流部分數據項導致丟棄的輸出結果數進行計算。首先計算每個流的損失率，將產生的輸出結果的損失率最大的數據流項降載，然后再重新計算，若降載量不足以滿足約束，則重復此步驟。另一個可選的方法是只計算一次，而不是每次都計算損失率。MxLF是一個近似的算法，可快速選擇一個降載順序，但不一定能保證是最佳順序。MLAS（multi round associated shedding）算法采用多輪策略，即在每一輪，局部降載值為原始值的一個比例。顯然，輪數對結果有影響，大多數情況下，輪數越多，產生的結果集越大。GAS（global associated shedding）算法考慮全局約束，降載前每個流計算其數據項輸出率，根據輸出率建立一個等級表，降載時將等級表最后的數據項丟棄。GAS算法也可采用多輪策略。

基于聯合的策略考慮多個流之間數據項的復雜關系，因此可輸出更多的結果；即使采用多輪技術，該算法需要的計算開銷仍較大，輪數的設定也沒有明確的算法可供參考。

5 降載策略的比較

不同的降載策略與流應用高度相關，因此降載策略具有多樣性的特點，難以直接進行比較。為說明不同策略的特點，采用列表方式進行總結。表1采用本文的分類方法對重點討論的降載策略進行分類比較；表2對降載策略的輸出目標和應用范圍進行分類比較。

表1 降載策略分類比較降載策略丟棄位置丟棄方式丟棄策略窗口類型時間域經典反饋處理之前CF隨機無連續、離散STREAM查詢計劃中CF隨機時間離散基于屬性處理之前不丟棄語義無離散基于窗口查詢計劃中/隨機時間連續、離散雙窗口處理前、中INC語義時間離散查詢優先級處理之前CF語義無離散緩沖前置處理之前CF語義無連續、離散基于范圍處理之前CF語義元組連續基于聯合處理之前CF語義時間離散降載策略降載機制QoS設定降載粒度先驗信息經典反饋自適應系統指定數據流項不需要STREAM動態系統指定數據流項需要基于屬性自適應系統指定屬性需要基于窗口動態無窗口無雙窗口動態系統指定數據流項需要查詢優先級動態用戶指定數據流項需要緩沖前置自適應用戶指定數據流項不需要基于范圍自適應系統指定數據流項需要基于聯合動態系統指定數據流項不需要表2 降載目標和應用范圍降載

策略最大

子集 采樣

結果輸出

延遲典型

應用降載

策略最大

子集 采樣

結果輸出

延遲典型

應用經典反饋√廣泛查詢

優先級√聚合STREAM√聚合緩沖前置√廣泛基于屬性√廣泛基于范圍√等值連接基于窗口√聚合基于聯合√等值連接雙窗口√等值連接6 結束語

由于數據流系統降載策略與實際應用聯系密切，研究人員已開發許多的降載策略。一個好的降載策略應該具有以下特點：a）實施降載策略所引入的額外開銷??；b）能夠適應數據流波動的情況；c）能夠自適應DSMS特征變動的情況；d）降載時系統的穩定性和魯棒性高；e）能適應數據流數量較多的情況；f）適應的查詢運算種類多。

針對數據流系統和實際應用系統的特點可以看出，將來的降載策略的某些研究策略與發展趨勢：a）應降低實施降載策略的開銷以在系統過載時可有效地降低系統負荷；b）提高降載策略的自適應性，在系統特征和輸入流特征高度波動時，仍能有效實現降載；c）降載策略應能適應更多的輸出目標，如同時支持多個輸出目標；d）應能允許用戶根據自己的實際應用自定義QoS；e）降載策略的適應范圍更廣泛，目前的降載策略主要是針對某一類的查詢運算，應開發適應查詢運算種類更多的降載策略；f）降載策略應能自適應地根據過載的輕重采用不同的降載策略以實現更高的輸出質量的目標。

參考文獻：

[1]BRAIN B B， SHIVNATH B， MAYUR D， et al. Models and issues in data stream systems[C]//Proc of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM Press， 2002:1-16.

[2]The STREAM Group. STREAM: the Stanford stream data manager [J]. IEEE Data Engineering Bulletin， 2003， 26(1):19-26.

[3]CHANDRASEKARAN S， DESHPANDE A， FRANKLIN M， et al. TelegraphCQ: continuous dataflow processing for an uncertain world[C]//Proc of the 1st Conference on Innovative Data Systems Research. 2003.

[4]Niagara project[EB/OL]. http://www.cs.wisc.edu/niagara/.

[5]ABADI D J， CARNEY U， CETINTMELM U， et al. Aurora: a new model and architecture for data stream management[J]. VLDB Journal， 2003， 12(2):120-139.

[6]TATBUL N， CETINTEMEL U， ZDONIK S， et al. Load shedding in a data stream manager[C]//Proc of the 29th International Conference on Very Large Databases. New York: VLDB Endowment Inc， 2003:309-320.

[7]VIGLAS S D， NAUGHTON J F. Rate-based query optimization for streaming information sources[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 2002:37-48.

[8]SRIVASTAVA U， WIDOM J. Memory-limited execution of windowed stream joins[C]//Proc of the 30th International Conference on Very Large Databases. New York: VLDB Endowment Inc， 2004: 324-335.

[9]XIE Jun-yi， Yang Jun， CHEN Yu-guo. On joining and caching stochastic streams[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 2005:359-370.

[10]TU Yi-cheng， LIU Song， PRABHAKAR S， et al. Using control theory for load shedding in data stream management[C]//Proc of the 23rd IEEE International Conference on Data Engineering. Washington DC: IEEE Computer Sciety， 2007:1491-1492.

[11]TU Yi-cheng， LIU SONG， PRABHAKAR S， et al. Load shedding in stream databases: a control-based approach[C]//Proc of the 32nd International Conference on Very Large Databases. New York: VLDB Endowment Inc， 2006:787-798.

[12]HU Zi-jing， LI Hong-yan， QIU Bao-jun， et al. Using control theory to guide load shedding in medical data stream management system[M]//Advances in Computer Science ASIAN 2005. Berlin: Sprin-ger， 2005: 236-248.

[13]BABCOCK B， DATAR M， MOTWANI R. Data streams models and algorithms， load shedding in data stream systems[M]. Berlin: Springer 2007.

[14]BABCOCK B， DATAR M， MOTWANI R. Load shedding techniques for data stream systems[C]//Proc of the Workshop on Management and processing of Data Streams. 2003.

[15]AHUJA A， YIU K N. A dynamic attribute based load shedding scheme for data stream management systems[C]//Proc of the 2nd International Conference on Digital Telecommunications. Washington DC: IEEE Computer Society， 2007:30.

[16]TATBIUL N， SZDONIK S. Window aware load shedding for aggregation queries over data streams[C]//Proc of the 32nd International Conference on Very Large Databases. New York: VIDB Endowment Inc， 2006:799-810.

[17]ABADI D， AHMAD Y， BALAZINSKA M， et al. The design of the Borealis stream processing engine[C]//Proc of the 2nd Conference on Innovative Data Systems. 2005.

[18]HAN Dong-hong， WANG Guo-ren， XIAO Chuan， et al. Load shedding for window joins over streams[J]. Journal of Computer Science and Technology， 2007， 22(2):182-189.

[19]JAESEOK P， HAENGRAE C. Semantic load shedding for prioritized continuous queries over data streams[C]//Proc of International Symposium on Computer and Information Sciences. Berlin: Springer，2005:813-812.

[20]ZHOU Rui， WANG Guo-ren， HAN Dong-hong. Buffer-preposed QoS adaptation framework and load shedding techniques over streams[C]//Proc of International Comference on Web Information System Engineering. Berlin: Springer，2006:234-246.

[21]REN Jia-dong， JIANG Wun-chang， HUO Cong. Efficient load shedding for strea-ming sliding window joins[C]//Proc of the 6th International Conference on Machine Learning and Cybernetics.2007:1536-1541.

[22]YANG Xiao-chun， LI Lin， NG Y K， et al. Associated load shedding strategies for computing multi-joins in sensor networks[C]//Proc of the 11th International Conference on Database Systems for Advanced Applications.Berlin: Springer，2006:50-64.