ＳＭＪ：基于大綱的數據流多連接操作
2009-01-01 00:00:00尹田田張俊虎
計算機應用研究 2009年5期
(1.中國科學院 自動化研究所 中法聯合實驗室 北京 100190;2.青島理工大學 計算機學院 山東 青島 266033)
摘 要：研究了Ad hoc網絡的特點及應用情況，分析了在Ad hoc網絡中傳統數據流多連接查詢處理策略所面臨的問題，并在此基礎上提出了一種基于大綱的多數據流連接優化算法(SMJ)。實驗結果顯示SMJ算法可以極大降低Ad hoc網絡數據流連接查詢處理的通信代價。
關鍵詞：自組織網絡;大綱；數據流；多連接；多數據流連接算法
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2009)05-1847-05
SMJ:synopsisbased data stream multijoin operation
YIN Tiantian1，ZHANG Junhu2
(1.LIAMA Institute of Automation Chinese Academy of Sciences Beijing 100190 China；2.School of Computer Science Engineering Qingdao Technological University Qingdao Shandong 266033 China)Abstract:This paper studied the characteristics and the applications of Ad hoc networks and analyzed the problems of the traditional methods of multistream join processing in Ad hoc networks. Based on this，proposed a synopsisbased multistream join optimization algorithm——SMJ.The experiments show that this method can greatly reduce the communication cost.
Key words:Ad hoc network; synopsis; data stream; multijoin；SMJ algorithm
0 引言
Ad hoc網絡是一種邏輯意義上的組網方式，是在不依賴基礎網絡設施的前提下由一定范圍內的移動終端動態地建立可以互連的網絡。它在軍事、基于無線傳感器網絡(WSNs)的應用、事件監測系統、無線P2P應用等領域使用廣泛。
Ad hoc網絡具有以下主要特點：
a)無中心。Ad hoc網絡是一個對等式網絡，節點可以隨時加入或離開網絡。
b)自組織。網絡的布設或展開無須依賴于任何預設的網絡設施。
c)多跳路由。當節點要與其覆蓋范圍之外的節點進行通信時，需要中間節點的多跳轉發。
d)動態拓撲。Ad hoc網絡中節點位置可以改變。節點可以隨時加入或離開網絡，從而使網絡拓撲結構動態變化。
數據流是一種持續產生的數據元組的序列。在Ad hoc網絡中，許多應用需要處理多數據流連接查詢。例如由傳感器組成的Ad hoc網絡可用于監測某個區域動物活動情況。 網絡中的每個節點都能記錄經過本節點的動物編號，并且每個節點都能知道自己的地理位置。網絡上任意節點可查詢：在三個不同位置的節點site1、site2、site3都出現過動物的編號，本文用R1、R2、R3分別表示site1、site2、site3三個節點上的數據流。R1、R2、R3的模式為{ID，time}。其中：ID為某一動物的惟一標志；time為該動物出現的時間，即元組的時間標簽。數據流的查詢可以表示成一個多連接R1 join R2 joinR3。
為優化該查詢，以查詢處理過程中所產生的通信代價作為優化目標。通信代價是一個查詢處理過程中單位時間內網絡任意兩個節點之間所傳輸數據量的總和。
1 相關工作
最近出現了很多數據流管理系統(DSMS)，如面向監控應用數據流處理的Aurora[1]系統；面向電信記錄數據流處理的TelegraphCQ[2]系統；面向傳感器網絡數據流處理的Fjord[3]系統等。還有很多文章討論了多數據流連接查詢的自適應處理技術。Eddy[4]是一種數據流查詢機制，可以在集中式的環境下持續不斷地為多連接查詢操作符重新排序，以提高結果輸出速度。AGreedy[5]算法是一種動態改變多連接執行順序以減少中心節點計算代價的算法。 Joseph等人[6]提出了自適應地調整查詢樹以獲得數據流多連接最大化輸出速度的技術。 Tian等人[7]解釋了動態查詢計劃遷移的具體算法。
以上系統是將所有數據流傳送到一個節點處理，沒有考慮分布在不同數據源節點上的多數據流連接查詢通信代價問題。在Ad hoc網絡中，通信所產生的能耗遠遠高于本地計算產生的能耗，降低通信代價尤為重要。Deddy[8]和SwAP[9]，實現了分布式的多數據流連接查詢。這兩者使用Lottery routing策略，啟發式地決定分布式數據流上多連接執行順序。但是前者優化查詢處理的響應時間，后者優化后的通信代價依然很高。
基于以上問題，本文提出了一種基于大綱的多數據流連接優化算法SMJ。通過大綱信息進行多數據流連接查詢，能避免傳輸不能產生最終結果的數據元組，并在每個連接時段優化多數據流連接執行順序。實驗顯示SMJ算法與Lotteryrouting算法相比能更大程度地降低多數據流連接查詢的通信代價。
2 多數據流連接的執行順序
R1，…，Rn是數據源節點site1，…，siten上的數據流。 若要執行多數據流連接R1 joinR2 join…join Rn，則每個數據源節點sitei上[tj-1，tj]時段新產生的數據塊ΔRinew要與其他節點tj-1時刻之前產生的數據塊R1old，…，Ri-1old，Ri+1old，…，Rnold依次進行連接，即ΔRinew按照一定次序先傳遞到節點site1，…，sitei-1，sitei+1，…，siten中的某一個節點上連接，然后將其連接結果傳遞到另一個節點上作連接，依此類推，直到所有的連接執行完畢，將最終結果傳送到查詢節點。
按照這種多數據流的連接方式，不同的執行順序會產生相同的最終結果，但會產生不同的通信代價。下面用上文動物監測的實例來說明這個問題。
表 1~3顯示了數據流R1、R2、R3在t1時刻前的數據。ΔR2(表 4)是site2節點在[t1，t2]時段產生的新數據塊。ΔR′2 (表5)是site2節點在[t2，t3]時段產生的新數據塊。 表6顯示了site1，site2，site3之間的單位數據通信代價。對于site2上每塊新數據，都有兩種不同的執行順序進行連接操作。例如，ΔR2的連接可有以下兩種方案：
1548
a）首先傳遞到site1以完成ΔR2 join R1，然后將中間結果ΔR2 join R1傳遞到site3以完成（ΔR2 joinR1)join R3。
b)首先傳遞到site3以完成ΔR2 join R3，然后將中間結果ΔR2 join R3傳遞到site1以完成（ΔR2 joinR3）join R1。
假定wij代表節點sitei sitej之間的單位數據通信代價。|R|代表R的大小。 那么上述兩種情況所產生的通信代價分別為
方案1代價:|ΔR2|×w21+|ΔR2 join R1|×w13；
方案2代價:|ΔR2|×w23+|ΔR2 join R3|×w31。
根據表6所示的通信代價矩陣，對于ΔR2，兩種執行順序所產生的通信代價分別為：a)3×18+3×25=129；b)3×20+2×25=110。所以，對于ΔR2最優的執行順序是第二種。
對于ΔR′2，兩種不同的執行順序的通信代價分別為：a)3×18+2×25=104；b)3×20+2×25=110。那么ΔR′2的最優執行順序是第一種。
從上面的例子可以看出，針對不同時段的不同數據，應采用不同的執行順序，以降低通信代價。最優的執行順序是隨時間變化的。要降低通信代價，必須在不同時段按照最優的執行順序執行多連接操作。
通過上面的分析，可知，影響數據流多連接通信代價大小因素有以下三個:
a)連接屬性值的重疊度。兩個數據表之間的重疊度用它們之間在連接屬性上相同取值的個數表示。重疊度越大，兩數據表在進行連接操作所產生的結果越多。
b)數據流數據產生的速度。數據源節點產生數據的速度越快，單位時間內產生的數據量越多，單位時間內產生的結果也越多。
c)數據節點之間拓撲結構的變化。兩個節點之間單位數據傳輸代價越大，傳輸同樣數據的通信代價越大。
為了以最小的通信代價實現多數據流連接查詢處理，一個好的處理策略應該能夠針對當前時段多數據流上連接屬性值的重疊度、數據源節點之間拓撲結構的變化。各數據流上數據產生的速度，產生相應的最優執行順序。為此，將多數據流的持續連接轉換為多個連接時段內的多個數據塊間的連接，并引入大綱信息來處理多數據流連接優化。通過大綱信息可避免傳輸新生成數據塊中不能產生最終結果的元組，并在每個時段，為能夠產生最終結果的元組確定最優執行順序。
3 基于大綱的多數據流連接算法SMJ
本章將詳細描述基于大綱的多數據流連接優化算法SMJ。假設要處理的查詢Q=R1 join R2 join… join Rn。其中：R1 … Rn是來自節點site1，…，siten上的數據流。
3.1 基于大綱中心的多連接執行順序的優化
基本定義如下：
a)大綱向量。它是一個m×1維的數據向量。設S表示數據流R在一定時間間隔之內的大綱向量。S中的每一項是在屬性A上具有一個特定的值的元組的數目，m對應A上所有可能取值的個數。設屬性A總共有四個可能值v1、v2、v3、v4(升序排列)，這四個不同的屬性值上所產生元組的數目分別是3、7、9、1、R在屬性A的大綱向量就是一個4× 1維的數據向量S=[3，7，9，1]。 表7是R1、R2、R3在連接屬性ID上的大綱向量，這里假設連接屬性的可能取值為1~10，Si表示Ri的大綱向量。在以后的敘述中用Si(a)來表示Ri中屬性A值為a元組數目。
b)增量大綱向量。每個數據流上產生的新數據塊的大綱向量叫做增量大綱向量。如表 4所示的新數據塊ΔR2，其增量大綱向量ΔS2=[0，0，1，1，0，0，0，1，0，0] 這是因為ΔR2在連接屬性ID=3，4，8上各產生一個元組，因此其增量大綱向量ΔR2在其3、4、8位置上的分量的取值為1，其他為0。
c）通信代價矩陣。數據源節點之間單位數據傳送代價構成的矩陣，記做通信代價矩陣W，其元素wij是節點sitei與sitej之間傳送單位數據的代價，
使用大綱信息和通信代價矩陣，可以按照如下方式確定某執行順序的通信代價。如第2章提到對新數據塊ΔRinew的多連接:ΔRinew join R如上所述，使用大綱信息和數據源節點之間通信代價矩陣可確定某個執行順序的通信代價 可以據此選出不同的執行順序中通信代價最小的執行順序。 仍然是用上文提到的用動物習性監測的例子來說明 如何使用大綱信息去除不能產生最終結果的元組和確定最優的執行順序。
案2的通信代價)，比原來減少為110-90=20。
綜上所述，通過大綱的方式處理多連接優化具有以下特點：
a)去除不能產生最終連接結果的元組，減少數據傳輸量。
b)利用大綱信息，能夠描述每個數據流在連接屬性值上的統計信息，為每個時間段產生的數據確定最優的連接執行順序。
c)對每個時間段產生的數據，針對連接屬性值重疊度 網絡拓撲和數據產生速度的變化自適應地確定最優執行順序。
3.2 SMJ算法基本思想
本節介紹基于大綱的多數據流連接優化算法SMJ。 首先引入大綱中心的概念：
大綱中心——到網絡中所有數據源節點的距離和最小的節點。 它維護并不斷更新多數據流連接查詢中所有數據流的大綱向量，動態地獲取數據源節點之間的拓撲信息。通過這些信息，大綱中心動態地為每個數據流上的每塊新數據確定一個最優的執行順序。新數據按照這個數據依次路由到不同的節點上進行連接操作，完成最終結果。它維護兩種信息，即所有數據流的大綱向量S1，…，Sn數據源節點之間的單位數據通信代價矩陣W。
基于大綱的多數據流連接查詢處理算法SMJ的工作機制如下:
a）某一個數據源節點sitei上的數據流產生新的數據塊時，該數據塊被緩存，相應的增量大綱向量被發送到大綱中心，用于大綱中心作更新。如表4所示的新數據塊ΔR2，其增量大綱向量為ΔS2=[0，0，1，1，0，0，0，1，0，0]。
b）當大綱中心收到來自數據源節點sitei的增量大綱向量時，執行：(a)更新相應數據流的大綱向量；(b)根據更新的增量大綱向量產生濾波大綱向量；(c)根據更新濾波向量產生最優執行順序； (d)向節點sitei返回最優執行順序和濾波向量。例如 對表 4所示的新數據塊ΔR2，大綱中心收到ΔS2后進行更新操作：S2←S2+ΔS2。 將ΔS2與其他大綱向量作元素乘操作，得到濾波向量ΔS′2←ΔS2⊙S1⊙S3=[0，0，1，1，0，0，0，0，0，0]。其中不為0的元素即為能產生最終結果的元組。為ΔS′2確定最優的執行順序{3，1}(算法將在3.3節詳細解釋)。將此執行順序附在ΔS′2后面發送回site2。
c)當節點sitei收到大綱中心返回的濾波大綱向量和執行順序后，節點首先根據濾波向量從新數據塊中去除不能產生最終結果的元組，將剩余元組按照指定的順序依次發送到不同的節點上完成連接，并將最終結果發送到查詢節點。例如，site2收到ΔS′2和執行順序{3，1}后，先半連接操作ΔR2←ΔR2 semijoin ΔS′2，然后ΔR2依次被發送到site3，site1作連接以完成最終結果。
3.3 SMJ算法詳細描述
根據以上的分析，得出基于大綱的最優執行順序選擇算法SMJE。這種算法窮舉每一種可能的執行順序，從中選出代價最小的執行順序。SMJE算法如下：
由于算法SMJE窮舉出每一種可能的執行順序，它的計算復雜度為O(n!)。本文提出了一種基于動態規劃的啟發式算法SMJH，算法復雜度只有O(n2)。SMJH算法如下：
4 基于滑動窗口的多數據流連接優化
數據流具有無界的特性，多數據流連接應用采用滑動窗口技術將無界的數據流連接轉換成連續的有界數據集的連接。其中有界數據集由當前時間推后Tw時間(時間窗)內的數據組成[10]。如算法SMJ僅需少許修改，即可適應基于滑動窗口的多數據流連接查詢。
當某數據流產生了新數據塊時，會有一些舊元組r的時間戳tr超出窗口Tw，|tc-tr|>Tw。其中，tc為當前時間戳。這種位于時間窗外的數據將被刪除。某數據流中有數據被刪除時，為已刪除數據建立減量大綱向量，并將其發送到大綱中心作相應更新。減量大綱向量是已刪除數據的大綱向量，當大綱中心收到減量大綱向量時，對相應數據流的大綱向量作減操作。
例如，對第2章提到的例子，設數據流R2的時間窗Tw為2個時間單位，那3章提到的算法進行處理。
5 實驗及結果分析
5.1 實驗設置
假設存在一個配置在一個區域內的監測網絡，隨機選擇其中的幾個節點作為數據源節點，滿足：
a)每個數據源節點對應一個數據流。
b)任意兩數據源節點間的單位數據通信代價是一個1~10的隨機數。
c）每個數據流單位時間產生的元組個數，符合參數λ=5的泊松分布。
d）所有連接都在同一個屬性上，連接屬性值符合1~20的均勻分布。
e）所有數據流的運行時間都是30個時間單位，時間窗為3個時間單位。
f）設一個大綱向量元組為一個普通數據元組的1/4。
5.2 實驗算法
基于大綱的多數據流連接優化算法SMJ在優化多連接執行順序時可采用兩種方式：a)啟發式 稱之為SMJH算法；b)窮舉式，稱之為SMJE算法。將其與Lottery routing[4]算法比較，以測試SMJ算法性能。
Lottery routing算法在Deddy[8]和SwAP[9]得以在分布式環境中實現。這種算法為某個數據源節點產生的新數據塊，引入歷史向量h。其中h由n個bit位表示，n是數據源節點個數，每個bit位表示這塊數據是否已被某個數據源節點處理過，是則為0； 否則為1。 每個數據源節點sitek維護一個到其他數據源節點的選擇因子向量sf={sf1k，…，sfk-1k，sfk+1k，…，sfnk}。其中：sfik是節點sitek向節點sitei發送數據元組個數和節點sitei產生的相應結果元組個數的比率。 節點sitek根據每次向sitei發送的數據量以及sitei反饋給sitek產生的結果數動態修改sfik。對于sitek上一塊具有歷史向量h的數據，它選擇向量sf⊙h中最大元素對應的節點作為下一個要傳送到的節點。
5.3 結果分析
實驗中，本文研究了無滑動窗口和有滑動窗口條件下進行多數據流連接時，不同算法的單位時間通信代價隨時間積累和數據源節點數目增加的變化情況。
圖1（a）和（b）分別顯示了無滑動窗口和有滑動窗口條件下，算法Lottery routing、SMJH和SMJE在進行多數據流連接時所產生的單位時間通信代價與數據源節點數目之間的關系：無論是否基于滑動窗口，多數據流連接所需的中間連接結果的傳送次數會隨數據源節點數目的增加而增多，導致三個算法進行多數據流連接時的單位時間通信代價一致增大。其中Lottery routing計算多數據流連接所產生的單位時間通信代價最大 而SMJH所產生的單位時間通信代價又略高于SMJE。另外，由圖1（b）可知，在基于滑動窗口的多數據流連接優化方面，隨著數據源節點數目的增多，SMJH/E在減少通信代價方面的優勢尤為明顯。
圖2（a）和（b）分別顯示了非滑動窗口連接和滑動窗口連接的情況下 單位時間通信代價隨時間的變化。實驗結果顯示，非滑動窗口多連接查詢，單位時間通信代價隨著時間增加而增加。這是因為對非滑動窗口連接，每個數據源節點上的數據隨時間逐步增多，因此參與計算的數據量逐步增大，從而使單位時間通信代價增加。對于基于滑動窗口的連接，開始時單位時間通信代價隨時間增加而增加，而后單位時間通信代價趨向一個常值。這是因為開始時，每個數據源節點上的數據量未滿一個窗口 此時隨時間增長 節點上積累的數據增多；當數據源節點中的數據開始超過一個窗口時，舊數據會被刪除，使等待處理的數據量不會變化太大，從而使單位時間通信代價趨于常值。
總之 基于大綱的多連接執行順序優化算法SMJ在降低通信代價方面表現出色：算法SMJH在非滑動窗口多連接時，比Lottery routing算法降低20%~40%的通信代價；在滑動窗口連接的情況下可以降低50%~70%的通信代價。算法SMJE在非滑動窗口多連接時，比Lottery routing算法降低40%~60%的通信代價；在滑動窗口多連接的情況下降低60%~85%的通信代價。
6 結束語
本文研究了在Ad hoc網絡環境下數據流多連接查詢處理。首先分析了數據流多連接不同的執行順序對通信代價的影響；然后分析了影響數據流多連接通信代價的三個因素，即連接屬性值的重疊度、數據流數據產生的速度、數據節點之間拓撲結構的變化。在此基礎上，提出了一種基于大綱多數據流連接優化算法SMJ來優化數據流多連接查詢的執行順序，并且與Lottery routing算法進行比較。實驗結果顯示，SMJ能夠很好地優化數據流多連接執行順序，提高Ad hoc網絡環境中的多連接查詢執行效率。
致謝 本文是在中國科學院自動化所中法聯合實驗室（LIAMA，CASIA）的NETQUET項目組中完成的。LIAMA、中法信息、自動化與應用數學聯合實驗室，由中國科學院和法國計算機研究院等多家頂級研究機構聯合創辦，是國家級國際聯合研究中心之一。NETQUEST組主要研究無線網絡分布式查詢處理。感謝Stéphane Grumbach和Christophe Bobineau兩位法國教授的指導。Stéphane Grumbach是中法實驗室法方主任，博士生導師，主要研究方向為數據庫理論；Christophe Bobineau是法國國立高等數學與計算機學院副研究員。
參考文獻：
［1］ABADI D J，CARNEY D，ETINTEMEL U C，et al.Aurora:a new model and architecture for data stream management[J].VLDB Journal，2003，12(2):120139.
［2］CHANDRASEKARAN S，COOPER O，DESHPANDE A，et al.TelegraphCQ:continuous dataflow processing for an uncertain world[C]//Proc of CIDR.2003.
［3］MADDEN S，FRANKLIN M J.Fjording the stream:an architecture for queries in a production system[C]//Proc of ICDE Workshops.2002:555566.
［4］AVNUR R，HELLERSTEIN J M.Eddies:continuously adaptive query processing[C]//Proc of SIGMOD Conference.2000:261272.
［5］BABU S，MOTWANI R，MUNAGALA K，et al.Adaptive ordering of pipelined stream filters[C]//Proc of SIGMOD Conference.2004:407418.
［6］GOMES J S，CHOI H A.Finding:optimal join tree for multijoin stream queries in a production system[C]//Proc of ICDCS Workshops.2006.
［7］YANG Yin，KRAMER J，PAPADIAS D，et al.HybMig:a hybrid approach to dynamic plan migration for continuous queries[J].IEEE Trans on Knowledge of Data Engineering，2007，19（3）:398411.
［8］FENG Tian，DEWITT D J.Tuple routing strategies for distributed eddies[C]//Proc of VLDB.2003:334-344.
［9］ZHOU Yongluan，OOI B C，TAN K L，et al.An adaptable distributed query processing architecture[J].Data Knowledge Engineering，2005，53(3):283309.
［10］ZHANG Dongdong，LI Jianzhong，KIMELI K，et al.Sliding window based multijoin algorithms over distributed data streams[C]//Proc of ICDE.2006.
