流數(shù)據(jù)管理系統(tǒng)降載技術(shù)綜述

1、流數(shù)據(jù)管理系統(tǒng)降載技術(shù)研究綜述潘靜 ， 高學(xué)東北京科技大學(xué)經(jīng)濟管理學(xué)院，中國北京100083摘要關(guān)鍵字Abstract1 引言2 流數(shù)據(jù)管理系統(tǒng)降載技術(shù)概述2.1 流數(shù)據(jù)管理系統(tǒng)降載處理降載處理主要由以下三個方面構(gòu)成。（ 1）降載時間：數(shù)據(jù)流的速度是經(jīng)常不斷變化的。數(shù)據(jù)的處理速度必須要超過數(shù)據(jù)輸入的速度 87 ，一旦超載就應(yīng)該能盡快檢測到，丟棄部分?jǐn)?shù)據(jù)，降低系統(tǒng)負載，保證系統(tǒng)正常運行。文章 88 提出了一種檢測數(shù)據(jù)流速率跳變的算法。（ 2）降載的位置：如果在查詢中沒有共享操作，優(yōu)先的方案是在每個查詢的查詢路徑中第一個操作前面插入降載操作，且降載操作的抽樣比與該查詢的抽樣比相同。如果查詢中有共享

2、操作，這時要插入降載操作就較為復(fù)雜。此時要對兩查詢都有影響應(yīng)當(dāng)是在查詢路徑的共享部分插入降載操作。通過預(yù)先設(shè)置的規(guī)則確定降載的位置和數(shù)量。（ 3）降載數(shù)據(jù)量：根據(jù)每個流數(shù)據(jù)的輸入速度、操作的選擇率和降載操作的抽樣比等參數(shù)可計算出降載后輸出的速度。決定降載的量實際上是在確保系統(tǒng)不超載情況下，選擇合適的降載抽樣比，使輸出速度最大。由于降載是刪除未處理的元組，故降載會對查詢結(jié)果東的準(zhǔn)確性產(chǎn)生影響，也就體現(xiàn)所謂的近似查詢。2.2 降載方式降載方式主要有：隨機降載、語義降載。隨機降載通過在網(wǎng)絡(luò)的某點隨機地選擇丟棄元組的比例進行丟棄，當(dāng)用這個方法來使整個系統(tǒng)的效用損失達到最小時，卻不能控制由于刪除元組而產(chǎn)

3、生的對應(yīng)用語義的影響，其中文。語義降載是一種運用可控的方法來丟棄元組，它是使用過濾技術(shù)丟棄相對不重要的元組，而不是隨機地丟棄元組。最常用的有兩種策略：葡萄酒策略、牛奶策略。葡萄酒策略認(rèn)為舊數(shù)據(jù)比新數(shù)據(jù)更重要，丟棄數(shù)據(jù)時首先丟棄新數(shù)據(jù)；與此相反，牛奶策略則認(rèn)為新數(shù)據(jù)策略比較重要，必要時首先丟棄舊的數(shù)據(jù)。3 原型系統(tǒng)及其降載技術(shù)分析3.1 STREAM系統(tǒng)降載STREAM(StanfordStreamDataManage)是斯坦福大學(xué)設(shè)計的DSMS 原型實現(xiàn)，該系統(tǒng)為是以關(guān)系為基礎(chǔ)的流數(shù)據(jù)管理系統(tǒng)，完成內(nèi)存管理和近似查詢?？梢杂糜谔幚砜焖俚?、易變的、大量涌入的流數(shù)據(jù)信息，其連續(xù)查詢能力非常好。ST

4、REAM的主要處理技術(shù)包括 :連續(xù)的自我監(jiān)控和再優(yōu)化。適應(yīng)于各種需求的近似查詢。合理的資源分配和使用?？梢灾С侄喾N查詢語言。STREAM通過降載來達到適當(dāng)?shù)男阅芙档?。把降載作為一個優(yōu)化問題來處理，目標(biāo)函數(shù)是查詢結(jié)果不準(zhǔn)性達到最小，其降載集中在聚集查詢上，并提出了相應(yīng)的降載算法。STREAM降載技術(shù)是在查詢計劃中引入隨機抽樣操作，每個降載器對抽樣比p 進行參數(shù)化。概率p 是通過本操作流到下一個操作的元組比。為了補償由于元組刪除帶來的損失，系統(tǒng)計算出聚集值的適當(dāng)比例從而產(chǎn)生無偏近似結(jié)果。STREAM的降載處理主要是由系統(tǒng)輸入，統(tǒng)計管理器和降載管理器三部分構(gòu)成。其中，系統(tǒng)輸入：流數(shù)據(jù)：S 1， ，

5、S。流數(shù)據(jù)上的查詢集合q1 ， q 。查詢操作集合O1 ， ， Ok統(tǒng)計管理器 :對參數(shù)值進行估值，對處理元組的個數(shù)、操作的輸出和總的操作處理時間進行統(tǒng)計報告。降載管理器：在統(tǒng)計的基礎(chǔ)上，系統(tǒng)對操作的選擇率、操作的處理開銷和流數(shù)據(jù)的速率進行估值。當(dāng)流的到達速率和數(shù)據(jù)特征發(fā)生變化時，相應(yīng)的負載要脫落，確定降載的位置。STREAM系統(tǒng)是通過統(tǒng)計管理器周期性地更新降載輸入?yún)?shù)的估計值，降載計劃也是周期性地改變。如圖圖 STREAM系統(tǒng)降載示意圖3.2 TelegraphCQ系統(tǒng)降載3.3 AROURA系統(tǒng)降載AROURA系統(tǒng)是由布朗大學(xué)、布蘭代斯大學(xué)和麻省理工大學(xué)聯(lián)合開發(fā)的流數(shù)據(jù)處理系統(tǒng)，核心是一個

6、巨大的觸發(fā)器網(wǎng)絡(luò)，目標(biāo)是專門處理流式監(jiān)控，是一個面向工作流的系統(tǒng)。 Aurora系統(tǒng)的每個觸發(fā)器是一個數(shù)據(jù)流向圖，每個節(jié)點則是七種Built-in操作中的一個。對每一個使用Aurora的應(yīng)用，應(yīng)用管理器創(chuàng)建一個或多個觸發(fā)器加入到Aurora的觸發(fā)器網(wǎng)絡(luò)中。Aurora 系統(tǒng)實現(xiàn)了觸發(fā)器網(wǎng)絡(luò)的編譯優(yōu)化和運行優(yōu)化。它允許用戶通過安排boxes( 操作符 )和 arrows( 數(shù)據(jù)的流向 ) 來建立查詢計劃。數(shù)據(jù)流是一個潛在的無窮元組隊列，這些元組由一個數(shù)據(jù)源產(chǎn)生。可能的數(shù)據(jù)源如硬件傳感器，它連續(xù)地將數(shù)據(jù)推向A 盯 ora 。Aurora 可以處理大量查詢，這些查詢由7 個簡單的操作符組成的重復(fù)集合構(gòu)成。一個查詢可以處理任意數(shù)量的數(shù)據(jù)流，并經(jīng)常以一個輸出流結(jié)束。一個操作符可以被連接到多個下游的操作符。所有這樣的分裂點能夠向其下游的多個操作符傳送同樣的元組，并且能夠在不同的查詢之間共享計算。因為一個操作符能夠接受多流輸人，所以多流也能被合并。一個 Aurora 查詢網(wǎng)絡(luò)就是這樣的查詢構(gòu)成的集合。實施卸載是由在查詢網(wǎng)絡(luò)中插人卸載操作符來實現(xiàn)的。3.4 Borealis系統(tǒng)降載5 流數(shù)據(jù)降載策略比較6 結(jié)束語參考文獻91over infinite stream