數(shù)據(jù)流系統(tǒng)降載研究綜述

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

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

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

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

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

關(guān)鍵詞：數(shù)據(jù)流系統(tǒng); 降載；數(shù)據(jù)流管理系統(tǒng); 窗口

中圖分類號：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

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

1 數(shù)據(jù)流系統(tǒng)降載概述

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

DSMS優(yōu)化調(diào)度策略雖可降低最高存儲需求、數(shù)據(jù)延遲或者最大化吞吐率，但不能提高系統(tǒng)的最大處理能力。因此，當DSMS過載時必須采用降載技術(shù)滿足系統(tǒng)的處理要求。

1）系統(tǒng)模型

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

輸入數(shù)據(jù)流在遠端設(shè)備產(chǎn)生，經(jīng)由網(wǎng)絡(luò)發(fā)給DSMS。為平抑數(shù)據(jù)流的波動，到達的數(shù)據(jù)流項首先被放入一個輸入隊列。當查詢引擎空閑時，從隊列中取出數(shù)據(jù)項執(zhí)行查詢操作。

DSMS使用監(jiān)測器獲取輸入數(shù)據(jù)流和DSMS的狀態(tài)參數(shù)，如輸入流的分布特征，并根據(jù)這些參數(shù)作出降載決策。

2）輸入數(shù)據(jù)流模型

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

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

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

3）資源約束

處理數(shù)據(jù)流DSMS需要的系統(tǒng)資源主要有計算資源和存儲資源。計算資源是指系統(tǒng)CPU的處理能力，CPU處理查詢的速率要大于等于數(shù)據(jù)流的輸入率；存儲資源是指可使用的存儲必須足以保存執(zhí)行查詢產(chǎn)生的所有狀態(tài)。

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

4）降載的輸出質(zhì)量目標

降載時，由于丟棄部分元組，系統(tǒng)不能產(chǎn)生所有的輸出結(jié)果。不同的流應(yīng)用對輸出結(jié)果有不同的要求，要由不同的降載模式來產(chǎn)生。對這些不同的要求，根據(jù)輸出結(jié)果和原始結(jié)果的關(guān)系可以分為三類：

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

b)采樣結(jié)果，即原始結(jié)果的近似結(jié)果。降載時產(chǎn)生的輸出結(jié)果數(shù)量與穩(wěn)態(tài)時相同，但是降低了輸出結(jié)果的質(zhì)量，每個輸出結(jié)果可能是原始輸出結(jié)果的近似值。降載的目標是獲得原始結(jié)果的統(tǒng)一隨機樣本，若不能獲得，那么樣本應(yīng)盡可能逼近統(tǒng)一樣本。挑戰(zhàn)是保證誤差在設(shè)定范圍內(nèi)。

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

5）降載問題的正式描述

當輸入數(shù)據(jù)流到達率超過系統(tǒng)處理能力時，需執(zhí)行降載。

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

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

2 降載策略的分類

為滿足數(shù)據(jù)流應(yīng)用的不同目標要求，需采用不同的降載策略。降載策略的分類方法如下：

a）降載位置。可以在數(shù)據(jù)流產(chǎn)生的位置進行降載，也可以在DSMS處降載。在DSMS處降載又可分為在數(shù)據(jù)流項處理之前降載、查詢計劃中降載或者對數(shù)據(jù)流項不丟棄而等待其自然過期。

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

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

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

e）QoS的設(shè)定。系統(tǒng)指定QoS根據(jù)某個QoS設(shè)計降載機制；用戶指定QoS根據(jù)用戶設(shè)定的QoS動態(tài)設(shè)計降載機制。

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

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

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

i）窗口的分類。可使用的不同類型的窗口如時間窗口、元組窗口或者滑動窗口、滾動窗口或者界標窗口。

3 降載策略的挑戰(zhàn)

當輸入數(shù)據(jù)流的處理要求超過系統(tǒng)處理能力的時候降載，其面臨很多的技術(shù)挑戰(zhàn)：

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

b）為獲得最優(yōu)的輸出質(zhì)量，需要根據(jù)系統(tǒng)信息和輸入流的信息確定降載決策，而這需要監(jiān)測系統(tǒng)的運行狀態(tài)和輸入流的特征，又將引入額外的開銷。

c）在選擇降載策略時，需要選擇開銷小且可獲得最優(yōu)輸出的策略，而這需要計算降載策略的開銷。為估計開銷需設(shè)計一個成本模型。由于系統(tǒng)時刻在動態(tài)變化，如何設(shè)計合理的成本模型是一個挑戰(zhàn)。

d）降載策略需要保證系統(tǒng)的魯棒性和穩(wěn)定性；執(zhí)行和不執(zhí)行降載策略時不能出現(xiàn)系統(tǒng)顛簸現(xiàn)象。

4 降載策略

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

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

圖1為根據(jù)經(jīng)典反饋控制理論設(shè)計的降載架構(gòu)，降載架構(gòu)的不同組件構(gòu)成了三個反饋循環(huán)：一個外環(huán)和兩個內(nèi)環(huán)。圖中陰影部分為被控系統(tǒng)的新添組件。

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

系統(tǒng)模型動態(tài)變化時，內(nèi)環(huán)1可對系統(tǒng)進行更好的控制。Self-tuning module的輸入為被控變量和操作變量，根據(jù)被控系統(tǒng)的實時參數(shù)估計對controller進行在線修改。更多系統(tǒng)特征的突然變化（如調(diào)度策略）由內(nèi)環(huán)2處理。運行時，concept selector以關(guān)鍵系統(tǒng)特征作輸入，判斷系統(tǒng)運行時狀態(tài)的變化，并據(jù)此選擇相適應(yīng)的controller參數(shù)。

反饋控制循環(huán)的設(shè)計包括系統(tǒng)建模和設(shè)計controller。采用系統(tǒng)識別技術(shù)對系統(tǒng)建模。根據(jù)控制理論提供的一系列工具去設(shè)計和調(diào)節(jié)控制器，并在受到干擾的情況下保證性能;使用控制度量可以正式描述降載算法的性能。重要的控制度量參數(shù)包括穩(wěn)定性、穩(wěn)態(tài)誤差、收斂速率和系統(tǒng)阻尼等。控制器的設(shè)計是離線的過程，僅僅需要進行一次。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

46 基于查詢優(yōu)先級的降載策略[19]

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

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

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

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

系統(tǒng)架構(gòu)包括上行數(shù)據(jù)流和下行數(shù)據(jù)流兩部分。PI controller接收monitor發(fā)送的輸出結(jié)果的QoS，并確定下一個監(jiān)測周期中流入查詢處理器的數(shù)據(jù)流項。基于經(jīng)典控制理論的降載策略當CPU在最大能力附近波動時會導(dǎo)致丟棄過多數(shù)據(jù)項，在最前面放置一個緩沖管理器調(diào)節(jié)緩沖區(qū)可消除該問題。緩沖管理器內(nèi)嵌三個模塊：a)調(diào)度器，分配存儲資源并將數(shù)據(jù)項調(diào)度進/出其對應(yīng)的隊列；b)適配器，當隊列溢出時丟棄負荷；c)清除器，負責將不符合QoS的數(shù)據(jù)項丟棄。

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

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

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

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

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

49 基于聯(lián)合的降載策略[22]

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

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

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

5 降載策略的比較

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

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

策略最大

子集 采樣

結(jié)果輸出

延遲典型

應(yīng)用降載

策略最大

子集 采樣

結(jié)果輸出

延遲典型

應(yīng)用經(jīng)典反饋√廣泛查詢

優(yōu)先級√聚合STREAM√聚合緩沖前置√廣泛基于屬性√廣泛基于范圍√等值連接基于窗口√聚合基于聯(lián)合√等值連接雙窗口√等值連接6 結(jié)束語

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

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

參考文獻：

[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.