基于滑動窗口的分布式數(shù)據(jù)流ToP-K監(jiān)控.pdf

1、近年來，伴隨著社交網(wǎng)絡(luò)、移動互聯(lián)網(wǎng)和物聯(lián)網(wǎng)等技術(shù)領(lǐng)域的迅猛發(fā)展，數(shù)據(jù)量呈現(xiàn)爆炸式的增長。在這些領(lǐng)域中，通常需要實(shí)時(shí)地、高效地處理快速變化的海量數(shù)據(jù)。目前，針對數(shù)據(jù)流的實(shí)時(shí)分析和流式處理逐漸成為大數(shù)據(jù)研究的熱門領(lǐng)域。分布式數(shù)據(jù)流監(jiān)控問題在許多應(yīng)用領(lǐng)域被廣泛研究，比如:網(wǎng)絡(luò)流量監(jiān)控、傳感器網(wǎng)絡(luò)監(jiān)控、Web日志使用分析和股票市場監(jiān)管等領(lǐng)域。這些應(yīng)用場景通常需要監(jiān)控分布式數(shù)據(jù)流中存在的異常情況，并進(jìn)行及時(shí)匯報(bào)處理。由于數(shù)據(jù)產(chǎn)生速度快、數(shù)據(jù)量大，

2、傳統(tǒng)的集中式的處理方式變得不再可行，出現(xiàn)了由于中心處理節(jié)點(diǎn)計(jì)算資源有限、存儲能力不足導(dǎo)致的計(jì)算延遲，以及耗費(fèi)大量的網(wǎng)絡(luò)通信用來傳輸數(shù)據(jù)等問題。
　　本文主要研究基于滑動窗口的分布式數(shù)據(jù)流Top-K監(jiān)控問題，即在給定的監(jiān)控窗口大小內(nèi)，在分布式數(shù)據(jù)流上連續(xù)地查詢前K個(gè)數(shù)值最大的對象。我們采用連續(xù)的分布式監(jiān)控處理模型來進(jìn)行分布式數(shù)據(jù)流的監(jiān)控，包含一個(gè)中心協(xié)調(diào)處理節(jié)點(diǎn)和多個(gè)分布式監(jiān)控節(jié)點(diǎn)。每個(gè)監(jiān)控節(jié)點(diǎn)負(fù)責(zé)實(shí)時(shí)接收處理對應(yīng)的數(shù)據(jù)流。中心協(xié)調(diào)

3、處理節(jié)點(diǎn)則負(fù)責(zé)計(jì)算全局的Top-K結(jié)果。為了高效地維護(hù)和處理數(shù)據(jù)流，本文采用基于時(shí)間的滑動窗口處理模型。該模型將給定的監(jiān)控時(shí)間窗口劃分為多個(gè)大小相同的窗口單元進(jìn)行數(shù)據(jù)流的處理。每當(dāng)一個(gè)新的窗口單元創(chuàng)建完成后，最早的窗口單元將由于過期被移除監(jiān)控窗口。伴隨著監(jiān)控窗口的滑動，分布式監(jiān)控節(jié)點(diǎn)上對象的數(shù)值也隨著不斷變化。連續(xù)地查詢前K個(gè)數(shù)值最大的對象，需要頻繁地從分布式監(jiān)控節(jié)點(diǎn)獲取對象變化的數(shù)值，并計(jì)算新的Top-K結(jié)果。這將導(dǎo)致整個(gè)分布式監(jiān)控系

4、統(tǒng)的通信負(fù)載和計(jì)算消耗加重。
　　為了能夠盡可能降低分布式監(jiān)控系統(tǒng)中出現(xiàn)的通信開銷，本文提出了一種基于調(diào)整因子的對象數(shù)值重分配算法。該算法通過指派調(diào)整因子來協(xié)調(diào)分布式監(jiān)控節(jié)點(diǎn)上對象的數(shù)值，使得分布式監(jiān)控節(jié)點(diǎn)上的本地Top-K結(jié)果與全局的Top-K結(jié)果保持一致。當(dāng)本地的Top-K結(jié)果出現(xiàn)不一致時(shí)，才重新進(jìn)行協(xié)調(diào)，并計(jì)算出新的全局Top-K結(jié)果和新的調(diào)整因子。該算法只在分布式監(jiān)控節(jié)點(diǎn)出現(xiàn)違反約束時(shí)，才需要額外的通信來協(xié)調(diào)全局的信息，所