潘 靜 于宏偉

[摘 要] 流數(shù)據(jù)作為一種新的數(shù)據(jù)形態(tài)快速流行,但由于其連續(xù)快速不可預(yù)測(cè)的特點(diǎn),當(dāng)輸入速率超過(guò)系統(tǒng)處理能力時(shí),系統(tǒng)會(huì)產(chǎn)生過(guò)載。降載是解決該問(wèn)題的有效途徑。本文討論了流數(shù)據(jù)管理降載的關(guān)鍵技術(shù),分析了目前有代表性的流數(shù)據(jù)系統(tǒng)所采用的降載技術(shù),同時(shí)給出了降載技術(shù)的研究趨勢(shì)。

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

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2009 . 21 . 009

[中圖分類(lèi)號(hào)]TP393 [文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]1673 - 0194(2009)21 - 0033 - 04

1 引 言

流數(shù)據(jù)在電信數(shù)據(jù)管理、金融分析、網(wǎng)絡(luò)入侵檢測(cè)等多個(gè)領(lǐng)域中有著廣泛應(yīng)用,流數(shù)據(jù)管理也成為近年來(lái)數(shù)據(jù)管理的研究熱點(diǎn)之一。

流數(shù)據(jù)源大量快速實(shí)時(shí)的特性,使之經(jīng)常呈現(xiàn)突發(fā)性和波動(dòng)性。當(dāng)流數(shù)據(jù)輸入率超過(guò)流數(shù)據(jù)管理系統(tǒng)的處理能力時(shí), 流數(shù)據(jù)管理系統(tǒng)不能處理所有的輸入流數(shù)據(jù),也不能與流數(shù)據(jù)到達(dá)率保持一致,此時(shí)只能卸掉部分負(fù)載。降載就是處理掉系統(tǒng)容納不了的負(fù)載。本文分析介紹了主要降載技術(shù),總結(jié)了當(dāng)前主流流數(shù)據(jù)管理系統(tǒng)的降載方法,討論了流數(shù)據(jù)管理降載的進(jìn)一步研究趨勢(shì)。

2流數(shù)據(jù)管理降載主要技術(shù)

2.1 流數(shù)據(jù)管理降載方式

根據(jù)目前提出的各種降載技術(shù)研究, 主要可以將流數(shù)據(jù)管理中的降載方式分為兩種:隨機(jī)降載和語(yǔ)義降載,同時(shí)也有文獻(xiàn)認(rèn)為還有一類(lèi)是自適應(yīng)性降載的。

隨機(jī)降載通過(guò)在網(wǎng)絡(luò)的某點(diǎn)隨機(jī)地選擇丟棄元組的比例進(jìn)行丟棄,當(dāng)用這個(gè)方法來(lái)使整個(gè)系統(tǒng)的效用損失達(dá)到最小時(shí),卻不能控制由于刪除元組而產(chǎn)生的對(duì)應(yīng)用語(yǔ)義的影響。

語(yǔ)義降載運(yùn)用可控的方法來(lái)丟棄元組,它是使用過(guò)濾技術(shù)丟棄相對(duì)不重要的元組,而不是隨機(jī)地丟棄元組。最常用的有兩種策略是葡萄酒策略和牛奶策略。葡萄酒策略認(rèn)為舊數(shù)據(jù)比新數(shù)據(jù)更重要,丟棄數(shù)據(jù)時(shí)首先丟棄新數(shù)據(jù);與此相反,牛奶策略則認(rèn)為新數(shù)據(jù)比較重要,必要時(shí)首先丟棄舊的數(shù)據(jù)。

2.2 流數(shù)據(jù)管理降載的核心問(wèn)題

文獻(xiàn)[1]提出了降載需要解決的3個(gè)問(wèn)題:降載的時(shí)間、降載的位置以及降載的數(shù)據(jù)量。

2.2.1降載時(shí)間

流數(shù)據(jù)的速度經(jīng)常不斷變化,數(shù)據(jù)的處理速度必須要超過(guò)數(shù)據(jù)輸入的速度,一旦超載就應(yīng)盡快檢測(cè)到,丟棄部分?jǐn)?shù)據(jù),降低系統(tǒng)負(fù)載,保證系統(tǒng)正常運(yùn)行。各種系統(tǒng)檢測(cè)負(fù)載的方法不同,有利用公式的,有利用代價(jià)模型的,也有用統(tǒng)計(jì)器評(píng)估計(jì)算的,根據(jù)采用的不同方法會(huì)確定不同的檢測(cè)時(shí)間。

2.2.2降載的位置

如果判斷出系統(tǒng)處于過(guò)載狀態(tài),要及時(shí)插入降載操作進(jìn)行降載。降載位置的確定至關(guān)重要,如果插入到過(guò)早的位置,會(huì)影響到多個(gè)輸出(單一查詢(xún)除外),如果插入到過(guò)晚的位置,就會(huì)達(dá)不到降載的效果。所以合理確定降載操作應(yīng)該插入的位置,對(duì)系統(tǒng)的性能有直接的影響。

通常,如果在查詢(xún)中沒(méi)有共享操作,優(yōu)先的方案是在每個(gè)查詢(xún)的查詢(xún)路徑中第一個(gè)操作前面插入降載操作,且降載操作的抽樣比與該查詢(xún)的抽樣比相同。如果查詢(xún)中有共享操作,這時(shí)要插入降載操作較為復(fù)雜,應(yīng)通過(guò)預(yù)先設(shè)置的規(guī)則來(lái)確定降載的位置和數(shù)量。

2.2.3 降載數(shù)據(jù)量

因?yàn)槭菍⑸形刺幚淼脑M丟棄,會(huì)對(duì)查詢(xún)結(jié)果的正確性產(chǎn)生不利的影響,所以產(chǎn)生的是近似結(jié)果。文獻(xiàn)[2]中提出的目標(biāo)是將所有查詢(xún)的最大相對(duì)誤差最小化,同時(shí)證明了在最佳解決方案中,所有查詢(xún)的相對(duì)誤差是相等的。通過(guò)設(shè)計(jì)的自頂向下的算法和負(fù)載方程,可得到相對(duì)誤差的值,可確定降載的位置和數(shù)量。文獻(xiàn)[1]保證在插入降載操作符,丟棄掉一部分元組之后,系統(tǒng)的收益應(yīng)大于其損失,即單位時(shí)間內(nèi)獲得的周期數(shù)應(yīng)大于降載操作符本身的代價(jià)?？梢?jiàn),降載的數(shù)量與系統(tǒng)提出的降載目標(biāo)關(guān)系密切,降載目標(biāo)通常包括降載后輸出速度最大、對(duì)結(jié)果精確度影響最小等。

3流數(shù)據(jù)管理系統(tǒng)降載分析

由于流數(shù)據(jù)系統(tǒng)降載策略與實(shí)際應(yīng)用聯(lián)系密切,本部分主要分析當(dāng)前流行的流數(shù)據(jù)管理系統(tǒng)的降載策略。

3.1 STREAM系統(tǒng)

STREAM[3]是由斯坦福大學(xué)設(shè)計(jì)實(shí)現(xiàn)的,是以關(guān)系為基礎(chǔ)的流數(shù)據(jù)管理系統(tǒng),完成內(nèi)存管理和近似查詢(xún)。STREAM把降載作為一個(gè)優(yōu)化問(wèn)題來(lái)處理,目標(biāo)函數(shù)是查詢(xún)結(jié)果不準(zhǔn)性達(dá)到最小,其降載集中在聚集查詢(xún)上,并提出了相應(yīng)的降載算法。

STREAM的降載策略最主要研究流數(shù)據(jù)的滑動(dòng)窗口聚合操作,并假設(shè)所有的查詢(xún)一樣重要,在查詢(xún)計(jì)劃中引入隨機(jī)抽樣操作,每個(gè)降載器以一個(gè)采樣概率p將元組傳遞給下一個(gè)操作,為了補(bǔ)償由于元組刪除帶來(lái)的損失,系統(tǒng)計(jì)算出聚集值的適當(dāng)比例從而產(chǎn)生無(wú)偏近似結(jié)果。

STREAM的降載處理主要是由系統(tǒng)輸入、統(tǒng)計(jì)管理器和降載管理器3部分構(gòu)成,示例結(jié)構(gòu)如圖1所示。其中,系統(tǒng)輸入包括流數(shù)據(jù):S1,…,Sm;流數(shù)據(jù)上的查詢(xún)集合Q1,…,Qn;查詢(xún)操作集合O1,…,Ok。統(tǒng)計(jì)管理器對(duì)參數(shù)值進(jìn)行估值,對(duì)處理元組的個(gè)數(shù)、操作的輸出和總的操作處理時(shí)間進(jìn)行統(tǒng)計(jì)報(bào)告。降載管理器是在統(tǒng)計(jì)的基礎(chǔ)上,系統(tǒng)對(duì)操作的選擇率、操作的處理開(kāi)銷(xiāo)和流數(shù)據(jù)的速率進(jìn)行估值。當(dāng)流的到達(dá)速率和數(shù)據(jù)特征發(fā)生變化時(shí),相應(yīng)的負(fù)載要脫落,確定降載的位置。

STREAM降載算法分成兩步:

(1)在所有查詢(xún)之間平均分布誤差;

(2)獲得適當(dāng)?shù)妮敵鏊俾什M(mǎn)足負(fù)荷等式,考慮公共查詢(xún)子表達(dá)式共享的情況,確定在數(shù)據(jù)流圖的哪個(gè)位置進(jìn)行降載。

由于STREAM系統(tǒng)作降載決策所用的參數(shù)隨流數(shù)據(jù)的波動(dòng)而變化,需周期性地重新估計(jì)這些參數(shù),并改變降載策略,這將會(huì)導(dǎo)致系統(tǒng)的開(kāi)銷(xiāo)增大。另外,系統(tǒng)采用了隨機(jī)丟棄策略,沒(méi)有考慮流數(shù)據(jù)項(xiàng)的語(yǔ)義。

3.2 Telegraph CQ系統(tǒng)

Telegraph CQ[4]是美國(guó)加州大學(xué)伯克利分校構(gòu)建的流數(shù)據(jù)管理系統(tǒng)。Telegraph CQ系統(tǒng)中使用的是數(shù)據(jù)篩余的降載框架,思想是在數(shù)據(jù)源和查詢(xún)處理器的中間放置篩余隊(duì)列。

降載要求用低的等待時(shí)間來(lái)產(chǎn)生準(zhǔn)確的查詢(xún)結(jié)果。由于突發(fā)期間包含較多的潛在有用信息,所以降載不能簡(jiǎn)單地丟棄過(guò)載的數(shù)據(jù),有必要捕捉丟失數(shù)據(jù)的特性。圖2中的篩余隊(duì)列,把流數(shù)據(jù)轉(zhuǎn)換成系統(tǒng)的內(nèi)在格式。如果查詢(xún)引擎不能處理以一定速率進(jìn)入篩余隊(duì)列的元組,系統(tǒng)會(huì)建立過(guò)量元組的摘要。

正常的操作過(guò)程是數(shù)據(jù)源向各自的隊(duì)列輸入元組,查詢(xún)處理器按需要從隊(duì)列的后面獲取元組。如果流數(shù)據(jù)的輸入速率超出了查詢(xún)處理器處理數(shù)據(jù)的能力,篩余隊(duì)列填滿(mǎn)。當(dāng)篩余隊(duì)列超出空間,系統(tǒng)使用一個(gè)丟棄策略從隊(duì)列中去掉不是很重要的數(shù)據(jù),而且使用摘要捕捉已刪除元組集的相似特性。在連續(xù)查詢(xún)的每個(gè)時(shí)間窗口,篩余子系統(tǒng)把這些摘要傳到查詢(xún)引擎,并計(jì)算查詢(xún)結(jié)果的一個(gè)近似答案。最后,準(zhǔn)確和近似的結(jié)果合起來(lái)組成一個(gè)窗口的查詢(xún)結(jié)果。

3.3 AURORA系統(tǒng)

AURORA[5]系統(tǒng)是由布朗大學(xué)、布蘭代斯大學(xué)和麻省理工大學(xué)聯(lián)合開(kāi)發(fā)的,核心是一個(gè)巨大的觸發(fā)器網(wǎng)絡(luò),目標(biāo)是專(zhuān)門(mén)處理流式監(jiān)控,是一個(gè)面向工作流的系統(tǒng),連續(xù)查詢(xún)根據(jù)由盒子、箭頭構(gòu)成的數(shù)據(jù)流圖來(lái)定義,構(gòu)成查詢(xún)網(wǎng)絡(luò)。AURORA中的降載組件在數(shù)據(jù)輸入上接受速率信息,從目錄中讀取整個(gè)查詢(xún)網(wǎng)絡(luò)的描述,檢測(cè)系統(tǒng)的負(fù)荷,通過(guò)在運(yùn)行的查詢(xún)網(wǎng)絡(luò)中插入負(fù)荷減少的降載操作來(lái)降低負(fù)載。降載器能決定降載操作在什么時(shí)間執(zhí)行,降載框架如圖3所示。

AURORA系統(tǒng)實(shí)施降載是在查詢(xún)網(wǎng)絡(luò)中插入降載操作符,是基于窗口降載的,降載組件連續(xù)監(jiān)測(cè)查詢(xún)網(wǎng)絡(luò)的CPU負(fù)荷。若過(guò)載,將窗口刪除器插入到查詢(xún)網(wǎng)絡(luò)中。該刪除器使用查詢(xún)計(jì)劃的下游聚合的窗口屬性,如窗口尺寸和滑動(dòng)幅度,邏輯上將流以窗口為單位進(jìn)行劃分,并根據(jù)一定概率刪除整個(gè)窗口。

3.4 分布式流數(shù)據(jù)管理降載技術(shù)

Borealis[6]系統(tǒng)是布朗大學(xué)、布蘭代斯大學(xué)和麻省理工大學(xué)研制的分布式流處理引擎,可以跨越不同的處理單元,大至服務(wù)器,小到傳感器。Borealis的主要目標(biāo)在于使系統(tǒng)對(duì)分布式流數(shù)據(jù)的處理提高可測(cè)量性和實(shí)用性,已逐漸代替AURORA系統(tǒng)。

分布式流數(shù)據(jù)處理系統(tǒng)的負(fù)載問(wèn)題主要是負(fù)載的均衡和共享問(wèn)題,在流數(shù)據(jù)以一定速率到達(dá)而產(chǎn)生負(fù)載波動(dòng)的情形下,即使某一節(jié)點(diǎn)的平均負(fù)載不是很高,但在峰值期間,一個(gè)節(jié)點(diǎn)將會(huì)遇到暫時(shí)的負(fù)載峰值,其數(shù)據(jù)處理的等待時(shí)間將受到影響。

Borealis系統(tǒng)把操作負(fù)載描述為固定長(zhǎng)度的時(shí)間序列。兩個(gè)時(shí)間序列的關(guān)聯(lián)是通過(guò)關(guān)聯(lián)系數(shù)來(lái)度量的,關(guān)聯(lián)系數(shù)是[-1,l]之間的實(shí)數(shù)。當(dāng)兩個(gè)時(shí)間序列有正的相關(guān)系數(shù)時(shí),如果某個(gè)下標(biāo)的一個(gè)時(shí)間序列的值相對(duì)它的平均值是相對(duì)大的,那么另一個(gè)有同樣下標(biāo)的時(shí)間序列的值也往往是相對(duì)大的。相反,當(dāng)相關(guān)系數(shù)是負(fù)數(shù)時(shí),如果一個(gè)時(shí)間序列的值是相對(duì)大的,那么另一個(gè)的值往往是相對(duì)小的。系統(tǒng)算法通過(guò)觀察兩個(gè)操作的負(fù)載時(shí)間序列的相關(guān)系數(shù)是否為小的值來(lái)激勵(lì)。當(dāng)對(duì)操作的分配進(jìn)行決策時(shí),盡量對(duì)不同節(jié)點(diǎn)間的靜態(tài)負(fù)載相關(guān)系數(shù)最大化,只要兩個(gè)節(jié)點(diǎn)的負(fù)載時(shí)間序列有大的相關(guān)系數(shù)。

4結(jié)束語(yǔ)

針對(duì)流數(shù)據(jù)管理系統(tǒng)和實(shí)際應(yīng)用系統(tǒng)的特點(diǎn),可以看出降載技術(shù)進(jìn)一步的研究趨勢(shì)有:

(1)研究擴(kuò)展的語(yǔ)義降載;

(2)研究如何盡可能降低實(shí)施降載的額外開(kāi)銷(xiāo);

(3)構(gòu)建良好降載策略,以適應(yīng)多重目標(biāo);

(4)研究如何進(jìn)一步提高降載的自適應(yīng)性,能處理高度波動(dòng)流數(shù)據(jù),能自適應(yīng)調(diào)整降載策略;

(5)用戶(hù)可以根據(jù)實(shí)際應(yīng)用自定義多重降載目標(biāo);

(6)降載策略的適應(yīng)范圍要更加廣泛,要能適應(yīng)多種查詢(xún)運(yùn)算。

主要參考文獻(xiàn)

[1]Tatbul N,Cetintemel U,Zdonik S, et al. Load Shedding in a Data Stream Manager[C]//Proceedings of the 29th International Conference on Very Large Databases (VLDB'03), 2003.

[2]Babcock B,Datar M,Motwani R.Load Shedding for Aggregation Queries over Data Streams[C]//Proceedings of the 20th International Conference on Data Engineering,2004.

[3]A Arasu,B Babcock,et al.STREAM:The Stanford Stream Data Manager[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data,2003.

[4]Chandrasekaran S ,Deshpande A, et al. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World[C]//Proceedings of the CIDR Conference,2003.

[5]Carney D,Cetintemel U,Cherniack M,et al. Monitoring Streams A New Class of Data Management Applications[C]//Proceedings of the 28th International Conferenceon Very Large Database(VLDB),2002.

[6]Abadi D, Ahmad Y, Balazinska M, et al. The Design of the Borealis Stream Processing Engine[C]//Proceedings of the CIDR Conference,2005.

Load Shedding Techniques in Data Stream Management

PAN Jing1, YU Hong-wei2

(1.School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China;

2.Jilin Teachers' Institute of Engineering & Technology,Changchun 130052,China )

Abstract:Data stram is rapid popular as a new data form that is continous,fast and unpredictable.When input rates exceed the system processing capacity,the system will become overloaded.Load shedding is a way to solve this problem.This paper discussed the key load shedding technniques,analyzed the load shedding strategies of exsiting representative system,and introduced the study trends.

Key words:Data stream;Load shedding;Data Stream Management System