摘要：分析了基於結構化覆蓋網的分散式查詢處理模型，支援大量資料流的分散式儲存，連續查詢間、查詢內的並行處理操作，能夠在很大程度上消除資源約束問題（主要是記憶體），提高了查詢效能、服務質量，並且該查詢模型具有很好的擴充套件性。
關鍵詞：分散式資料流,分散式資料流系統
近年來，資料流查詢處理是資料庫研究領域的1個熱點方向。資料流的特徵可概括為無限性、瞬時性、流速不定性、語義不定性（資料模式隨時可能改變）等。針對資料流的以上特徵，不考慮將資料流儲存在傳統的關係資料庫中，資料流上的查詢是近似查詢、連續查詢(continuous query)。 目前，資料流管理系統中所採用的近似查詢的方法主要有以下幾種：隨機抽樣(random sampling)、資料寫生（sketching）、直方圖(histograms)、小波變換(wavelets)、視窗（windows）等。如何保證查詢的服務質量成為上述各種近似查詢方法必須考慮的問題。資料流上的查詢處理給人們提出了1個很大的難題——對處理器、記憶體等系統資源非常苛刻的需求。到目前已經出現了許多資料流的原型系統：單節點（單CPU）上的資料流管理系統，如Stanford 大學的Stream[1] 系統、布朗大學的Aurora[2,3] 系統等；有分散式資料流處理系統，如MIT的Medusa[4,5] 專案，Brandeis、Brown、MIT 的合作專案Borealis[6,7]等。這些專案在資料流處理的查詢語言、近似查詢演算法、保證服務質量的策略，以及系統的負載均衡等方面做了大量的工作，但同時也揭示出在分散式資料流處理系統中更多值得研究的問題。本文將對基於structured overlay network的分散式資料流系統的近似、自適應查詢處理進行研究，給出查詢處理模型。
1集中式資料流查詢處理及分散式散列表、Chord路由協議的相關說明
1．1資料流查詢處理相關的概念定義以及假設說明
集中式資料流查詢處理的體系結構由兩部分構成，即查詢計劃生成子系統（FRONT－end）以及查詢執行子系統(BACK)。其中兩部分與關係資料庫系統相比均有較大的區別。查詢執行子系統如圖1所示。
通過這種雜湊，將系統當前的所有查詢對映到節點空間，然後由該節點上的查詢處理器完成到達的查詢。
b)查詢內並行處理方式。在系統的範圍內，由操作符、輸入均輸出記錄佇列、維持操作符狀態的大綱資訊構成網狀結構。
c)命名發現機制。參與查詢處理的節點有全域性惟1命名participant（如IP地址等）。當在1個節點上面定義1個新的流模式、資料流、操作符，這些實體均隸屬於其名稱空間。該實體可以採用下面的命名方式：（participant，entity－name） 。為了瞭解系統中資料流模式的定義、系統中的資料流、資料流的到達（存放）位置、系統中哪1部分查詢執行，就要考慮在?catalog中存放必要的資料。其中catalog資訊是通過在DHT下分散式儲存的，前面已經分析了catalog資訊的儲存問題。
系統中對每1個數據流、每1個查詢、查詢中的運算元、運算元大綱、節點間輸出佇列均有惟1的命名。查詢處理器位於DHT之上。同查詢相關的資料粒度限定為資料流、輸入資料來源（記錄集）、節點間傳輸資料佇列、運算元大綱，而不是針對單個記錄而言。對於這些粒度的'資料可以通過在DHT中通過put（namespace，object）、get（namespace）、multicast（namespace）訊息得到。
對於操作符（運算元）在節點間遷移的情況，可以提供遠端運算元定義介面。當節點?A?上查詢執行的下1步join操作要求節點?B的查詢執行器完成時，節點B?接收到遠端呼叫請求，初始化join運算元，將節點?A?上發出呼叫請求運算元的狀態資訊（大綱，synopsis）作為引數傳遞給?B,然後就可以在節點B?上進行join運算元運算。查詢內並行就是有若干這樣的節點間的運算元遷移，使1個查詢計劃得以在多節點的運算元之間並行執行。
對於基於滑動視窗的資料流處理的join操作，如果有兩個資料流，查詢處理基於時間的視窗，進行join操作的兩個資料流時間範圍較長，那麼要求在1個節點上維護操作符的狀態資訊將會變得非常困難，join運算元狀態資訊儲存要求的記憶體空間可能非常大，則會進行操作符分割操作。在該節點的近鄰節點上同時進行join操作，最終將各個節點上的狀態資訊進行合併操作即可。
運算元遷移、運算元合併、運算元分割等操作在基於DHT的系統上實現具有良好的擴充套件性。DHT層為資料流處理系統在荷載大的情況下進行負載脫落、查詢計劃間並行、查詢計劃內並行提供了可以隨意擴充套件的基礎平臺。
3結束語
本文給出了基於structured overlay network 的分散式資料流查詢處理模型，考慮了對於到達系統的大量資料流的分片存放策略；同時在查詢處理中對查詢內的並行、查詢間的並行、運算元在分散式節點的遷移等提供了很好的支援。對系統catalog目錄資訊的分散式存放維護，從而消除了單節點查詢處理引擎在資源（CPU、記憶體）上的約束。本文沒有考慮分散式查詢模型在網路頻寬資源方面的問題，這將是以後要完善的地方。基於結構化覆蓋網的分散式資料流查詢模型提高了系統性能、查詢服務質量，並且基於Chord實現，具有很好的擴充套件性。
參考文獻：
［1］BRIAN B, SHIVNATH B, JENNIFER W. Models and issues in data stream systems[C]//Proc of the 21st ACM Symposium on Principles of Database Systems,2002.
?［2］BALAKRISHNAN H, BALAZINSKA M, CARNEY D, ?et al?. ?Retrospective on Aurora[J]. VLDB Journal, 2004,13(4):370-383.
［3］ABADI D, CARNEY D, STONEBRAKER M, ?et al?. Aurora: a new model and architecture for data stream management[J]. VLDB Journal,2003,12（2）:120-139.
［4］ZDONIK S, STONEBRAKER M, CHERNIACK M,?et al?. The Aurora and Medusa Projects[J] Data Engineering Bulletin, 2003,26(1):3-10.
［5］CHERNIACK M, BALAKRISHNAN H, BALAZINSKA M, ?et al?. Scalable distributed stream processing[C]//Proc of the 1st Biennial Conference on Innovative Data Systems Research. Asilomar, California:[s.n.],2003.
［6］ABADI D J, AHMAD Y, BALAZINSKA M, ?et al?. The design of the Borealis stream processing engine[C]//Proc of the 2nd Biennial Conference on Innovative Data Systems Research (CIDR’05). Asilomar:[s.n.],2005.
［7］TATBUL N, ZDONIK ing with overload in distributed stream processing systems[C]//Proc of IEEE International Workshop on Networking Meets Databases (NetDB’06). Atlanta:[s.n.],2006.
［8］Distributed hash tables links[EB/OL].
［9］DABEK F, STOICA I, BALAKRISHNAN H, ?et al?. Building peer－to－peer systems with Chord, a distributed lookup service[C]//Proc of the 8th Workshop on Hot Topics in Operating Systems(HotOS－VIII).2001.
［10］STOICAL I, MORRIS R, BALAKRISHNAN H, ?et al?. Chord:a sca－lable peer－to－peer lookup service for internet applications[C]//Proc ofACM SIGCOMM. New York: ACM Press, 2001:149-160.