基于結(jié)構(gòu)化Ｐ２Ｐ的分布式數(shù)據(jù)流系統(tǒng)的查詢處理模型

摘要：分析了基于結(jié)構(gòu)化覆蓋網(wǎng)的分布式查詢處理模型，支持大量數(shù)據(jù)流的分布式存儲(chǔ)，連續(xù)查詢間、查詢內(nèi)的并行處理操作，能夠在很大程度上消除資源約束問題（主要是內(nèi)存），提高了查詢性能、服務(wù)質(zhì)量，并且該查詢模型具有很好的擴(kuò)展性。

關(guān)鍵詞：分布式數(shù)據(jù)流管理系統(tǒng)； 結(jié)構(gòu)化覆蓋網(wǎng)； 分布式散列表； 滑動(dòng)窗口

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)12-0074-03

近年來，數(shù)據(jù)流查詢處理是數(shù)據(jù)庫研究領(lǐng)域的一個(gè)熱點(diǎn)方向。數(shù)據(jù)流的特征可概括為無限性、瞬時(shí)性、流速不定性、語義不定性（數(shù)據(jù)模式隨時(shí)可能改變）等。針對(duì)數(shù)據(jù)流的以上特征，不考慮將數(shù)據(jù)流存儲(chǔ)在傳統(tǒng)的關(guān)系數(shù)據(jù)庫中，數(shù)據(jù)流上的查詢是近似查詢、連續(xù)查詢(continuous query)。 目前，數(shù)據(jù)流管理系統(tǒng)中所采用的近似查詢的方法主要有以下幾種：隨機(jī)抽樣(random sampling)、數(shù)據(jù)寫生（sketching）、直方圖(histograms)、小波變換(wavelets)、窗口（windows）等。如何保證查詢的服務(wù)質(zhì)量成為上述各種近似查詢方法必須考慮的問題。數(shù)據(jù)流上的查詢處理給人們提出了一個(gè)很大的難題——對(duì)處理器、內(nèi)存等系統(tǒng)資源非?？量痰男枨蟆５侥壳耙呀?jīng)出現(xiàn)了許多數(shù)據(jù)流的原型系統(tǒng)：?jiǎn)喂?jié)點(diǎn)（單CPU）上的數(shù)據(jù)流管理系統(tǒng)，如Stanford 大學(xué)的Stream^[1] 系統(tǒng)、布朗大學(xué)的Aurora^[2，3] 系統(tǒng)等；有分布式數(shù)據(jù)流處理系統(tǒng)，如MIT的Medusa^[4，5] 項(xiàng)目，Brandeis、Brown、MIT 的合作項(xiàng)目Borealis^[6，7]等。這些項(xiàng)目在數(shù)據(jù)流處理的查詢語言、近似查詢算法、保證服務(wù)質(zhì)量的策略，以及系統(tǒng)的負(fù)載均衡等方面做了大量的工作，但同時(shí)也揭示出在分布式數(shù)據(jù)流處理系統(tǒng)中更多值得研究的問題。本文將對(duì)基于structured overlay network的分布式數(shù)據(jù)流系統(tǒng)的近似、自適應(yīng)查詢處理進(jìn)行研究，給出查詢處理模型。

1集中式數(shù)據(jù)流查詢處理及分布式散列表、Chord路由協(xié)議的相關(guān)說明

1．1數(shù)據(jù)流查詢處理相關(guān)的概念定義以及假設(shè)說明

集中式數(shù)據(jù)流查詢處理的體系結(jié)構(gòu)由兩部分構(gòu)成，即查詢計(jì)劃生成子系統(tǒng)（FRONT－end）以及查詢執(zhí)行子系統(tǒng)(BACK)。其中兩部分與關(guān)系數(shù)據(jù)庫系統(tǒng)相比均有較大的區(qū)別。查詢執(zhí)行子系統(tǒng)如圖1所示。

通過這種散列，將系統(tǒng)當(dāng)前的所有查詢映射到節(jié)點(diǎn)空間，然后由該節(jié)點(diǎn)上的查詢處理器完成到達(dá)的查詢。

b)查詢內(nèi)并行處理方式。在系統(tǒng)的范圍內(nèi)，由操作符、輸入均輸出記錄隊(duì)列、維持操作符狀態(tài)的大綱信息構(gòu)成網(wǎng)狀結(jié)構(gòu)。

c)命名發(fā)現(xiàn)機(jī)制。參與查詢處理的節(jié)點(diǎn)有全局惟一命名participant（如IP地址等）。當(dāng)在一個(gè)節(jié)點(diǎn)上面定義一個(gè)新的流模式、數(shù)據(jù)流、操作符，這些實(shí)體均隸屬于其命名空間。該實(shí)體可以采用下面的命名方式：（participant，entity－name） 。為了了解系統(tǒng)中數(shù)據(jù)流模式的定義、系統(tǒng)中的數(shù)據(jù)流、數(shù)據(jù)流的到達(dá)（存放）位置、系統(tǒng)中哪一部分查詢執(zhí)行，就要考慮在catalog中存放必要的數(shù)據(jù)。其中catalog信息是通過在DHT下分布式存儲(chǔ)的，前面已經(jīng)分析了catalog信息的存儲(chǔ)問題。

系統(tǒng)中對(duì)每一個(gè)數(shù)據(jù)流、每一個(gè)查詢、查詢中的算子、算子大綱、節(jié)點(diǎn)間輸出隊(duì)列均有惟一的命名。查詢處理器位于DHT之上。同查詢相關(guān)的數(shù)據(jù)粒度限定為數(shù)據(jù)流、輸入數(shù)據(jù)源（記錄集）、節(jié)點(diǎn)間傳輸數(shù)據(jù)隊(duì)列、算子大綱，而不是針對(duì)單個(gè)記錄而言。對(duì)于這些粒度的數(shù)據(jù)可以通過在DHT中通過put（namespace，object）、get（namespace）、multicast（namespace）消息得到。

對(duì)于操作符（算子）在節(jié)點(diǎn)間遷移的情況，可以提供遠(yuǎn)程算子定義接口。當(dāng)節(jié)點(diǎn)A上查詢執(zhí)行的下一步j(luò)oin操作要求節(jié)點(diǎn)B的查詢執(zhí)行器完成時(shí)，節(jié)點(diǎn)B接收到遠(yuǎn)程調(diào)用請(qǐng)求，初始化join算子，將節(jié)點(diǎn)A上發(fā)出調(diào)用請(qǐng)求算子的狀態(tài)信息（大綱，synopsis）作為參數(shù)傳遞給B，然后就可以在節(jié)點(diǎn)B上進(jìn)行join算子運(yùn)算。查詢內(nèi)并行就是有若干這樣的節(jié)點(diǎn)間的算子遷移，使一個(gè)查詢計(jì)劃得以在多節(jié)點(diǎn)的算子之間并行執(zhí)行。

對(duì)于基于滑動(dòng)窗口的數(shù)據(jù)流處理的join操作，如果有兩個(gè)數(shù)據(jù)流，查詢處理基于時(shí)間的窗口，進(jìn)行join操作的兩個(gè)數(shù)據(jù)流時(shí)間范圍較長(zhǎng)，那么要求在一個(gè)節(jié)點(diǎn)上維護(hù)操作符的狀態(tài)信息將會(huì)變得非常困難，join算子狀態(tài)信息存儲(chǔ)要求的內(nèi)存空間可能非常大，則會(huì)進(jìn)行操作符分割操作。在該節(jié)點(diǎn)的近鄰節(jié)點(diǎn)上同時(shí)進(jìn)行join操作，最終將各個(gè)節(jié)點(diǎn)上的狀態(tài)信息進(jìn)行合并操作即可。

算子遷移、算子合并、算子分割等操作在基于DHT的系統(tǒng)上實(shí)現(xiàn)具有良好的擴(kuò)展性。DHT層為數(shù)據(jù)流處理系統(tǒng)在荷載大的情況下進(jìn)行負(fù)載脫落、查詢計(jì)劃間并行、查詢計(jì)劃內(nèi)并行提供了可以隨意擴(kuò)展的基礎(chǔ)平臺(tái)。

3結(jié)束語

本文給出了基于structured overlay network 的分布式數(shù)據(jù)流查詢處理模型，考慮了對(duì)于到達(dá)系統(tǒng)的大量數(shù)據(jù)流的分片存放策略；同時(shí)在查詢處理中對(duì)查詢內(nèi)的并行、查詢間的并行、算子在分布式節(jié)點(diǎn)的遷移等提供了很好的支持。對(duì)系統(tǒng)catalog目錄信息的分布式存放維護(hù)，從而消除了單節(jié)點(diǎn)查詢處理引擎在資源（CPU、內(nèi)存）上的約束。本文沒有考慮分布式查詢模型在網(wǎng)絡(luò)帶寬資源方面的問題，這將是以后要完善的地方。基于結(jié)構(gòu)化覆蓋網(wǎng)的分布式數(shù)據(jù)流查詢模型提高了系統(tǒng)性能、查詢服務(wù)質(zhì)量，并且基于Chord實(shí)現(xiàn)，具有很好的擴(kuò)展性。

參考文獻(xiàn)：

［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].IEEE 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 S.Dealing 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]. http://www.etse.urv.es/~cpairot/dhts.html.

［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.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”