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

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

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

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

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