用於分布式共享流處理系統的查詢部署計劃的製作方法

2023-06-08 22:50:36

專利名稱：用於分布式共享流處理系統的查詢部署計劃的製作方法
用於分布式共享流處理系統的查詢部署計劃對相關申請的交叉引用本申請要求在2008年1月29日提交的臨時申請序列號61/024，300的優先權，該 臨時申請的內容通過引用完全結合於此。
背景技術：
在過去的數年間，流處理系統(SPS)已經在廣泛應用範圍內獲得了相當大的關 注，所述廣泛應用範圍包括行星尺度傳感器網絡或「顯宏鏡」、網絡性能和安全性監視、多玩 家在線遊戲以及基於饋給(feed)的信息糅合。這些SPS由大數量的地理上散布的實體來 表徵，所述實體包括生成潛在大量數據流的數據發布者以及在這些數據流上登記大數量的 並發查詢的客戶端。例如，客戶端發送查詢到數據發布者，以接收某些處理結果。SPS應該提供高的網絡和工作負荷可擴縮性，以便能夠向客戶端提供所請求的數 據流。高網絡可擴縮性表示適當地處理系統部件的增加的地理分布的能力，而工作負荷可 擴縮性則處理大數量的同時用戶查詢。為了獲得兩種類型的可擴縮性，SPS應該能夠橫向 擴展(scaleout)並將它的處理分布在網絡中的多個節點上。已經提出了 SPS的分布式版本，但是這些分布式SPS的部署可能是困難的。當部 署是針對在應用共享處理部件的共享處理環境中操縱基於流的查詢的SPS時，進一步加劇 了與部署SPS相關聯的困難。首先，應用經常表達服務質量(QoS)規格，所述服務質量規格 描述輸出的各種特性與其有用性之間的關係，所述有用性例如效用、響應延遲、端到端損失 率或等待時間等。例如，在很多實時金融應用中，查詢答案僅僅當它們被及時接收到時才是 有用的。當在多個機器上處理承載金融數據的數據流時，提供數據流的QoS受到該多個機 器中每一個機器的影響。因此，如果一些機器超負荷，則這些機器將對提供數據流的QoS產 生影響。此外，預期流處理應用在具有大數量的不可靠節點的公共網際網路上操作，這些不可 靠節點中的一些或全部可能僅在暫時的基礎上貢獻它們的資源，諸如在對等設置中的情況 那樣。此外，流處理以及將數據流傳輸到客戶端可能需要多個節點以鏈式或樹式工作，以處 理並傳輸所述流，其中一個節點的輸出是另一節點的輸入。因此，如果處理移動到網絡中的 新節點，則該鏈或樹中的下遊處理和QoS可能受影響。例如，如果處理移動到新地理位置中 的新節點，它可能將端到端等待時間增加到對於客戶端來說不可接受的點。


本發明的實施例將在以下說明中參考下面的附圖進行詳細說明。圖1示出根據實施例的系統；圖2示出根據實施例的在圖1中所示的系統中的數據流；圖3示出根據實施例的系統中的覆蓋(overlay)節點、系統中的查詢的示例、以及 用於操作符(operator)的候選主機的示例；圖4示出根據實施例的用於初始查詢放置的方法的流程圖；圖5示出根據實施例的最優化方法的流程4
圖6示出根據實施例的用於部署計劃生成的方法的流程圖；圖7示出根據實施例的用於解決衝突的方法的流程圖；以及圖8示出根據實施例的計算機系統的框圖。
具體實施例為了簡化和例示目的，通過主要參考實施例的示例來說明實施例的原理。在以下 的說明中，闡述許多具體細節以便提供對實施例的徹底理解。但是，對於本領域普通技術人 員來說顯而易見的是，可以在不局限於這些特定細節的情況下實現實施例。在一些情況中， 沒有詳細說明公知的方法和結構，從而避免不必要地使實施例模糊不清。根據實施例，分布式SPS(DSPS)在覆蓋網絡中提供在多個覆蓋節點上的分布式流 處理。這裡互換地使用節點和覆蓋節點。DSPS處理數據流並將數據流傳輸給客戶端。數據 流包括數據饋給(a feed ofdata)。例如，數據流可以包括RSS饋給或實時金融數據流。數 據流還可以包括多媒體。數據流可以包括數據的連續或周期性傳輸(諸如實時報價或RSS 饋給)，或者數據流可以包括不必連續或周期性傳輸的一組數據，諸如來自對公寓列表的請 求的結果。應該注意，由DSPS執行的流處理包括共享流處理，其中操作符可由多個數據流 共享，如下所述。DSPS包括自適應的基於覆蓋的框架，所述自適應的基於覆蓋的框架將流處理查詢 分布在多個可用節點上。這些節點使用分布式資源目錄服務進行自組織。資源目錄服務被 用於通告和發現節點中的可用計算機資源。DSPS在考慮節點的資源約束以及每個應用(例如數據流)的QoS期望的同時提供 多個共享的流處理查詢的數據流部署，與此同時維持低帶寬消耗。根據實施例，DSPS使用 主動方法，其中，節點周期性地協作以預先計算數據流的備選部署計劃。部署計劃在此也稱 為計劃。在運行時間期間，當違反計算機資源或QoS度量約束時，DSPS能夠對改變做出快 速反應，並通過應用最適合的預先計算的部署計劃來遷移到可行部署計劃。此外，即便沒有 發生任何違反，也能夠應用這些計劃中的最佳計劃來周期性地改進系統的帶寬消耗。圖1示出根據實施例的流處理系統100。該系統100包括由覆蓋節點111構成的 覆蓋網絡110、資源目錄120和網絡監視服務130。覆蓋網絡110包括底層網絡基礎結構，所述底層網絡基礎結構包括計算機系統、 路由器等，但是覆蓋網絡110提供關於流處理的附加功能，包括基於流的查詢處理服務。例 如，覆蓋網絡110可以在網際網路或其他公共或私有計算機網絡上構建。覆蓋網絡110由覆 蓋節點111構成，所述覆蓋節點111提供流處理功能。覆蓋節點111經由形成覆蓋路徑的 邏輯鏈路彼此連接，並且每個邏輯鏈路可以包括在底層網絡中的多個跳(hop)。根據實施例，覆蓋節點111可操作以提供基於流的查詢處理服務。例如，覆蓋節點 111包括用於查詢的操作符。查詢包括主控(host)於流處理系統中的節點上的多個操作 符。該查詢可以響應於接收並登記對於信息的客戶端查詢或請求而提供。操作符是查詢的 函數。操作符可以包括在節點上運行的軟體，其可操作以對數據流執行特定操作。覆蓋節 點的計算機資源的一部分可用於為該查詢提供操作符。覆蓋節點可以執行其他功能，由此 當選擇覆蓋節點來主控操作符時可以考慮覆蓋節點上的負荷。操作符的示例包括聯接、聚集、過濾等。操作符可以包括通常用於傳統資料庫中的查詢的操作符，但是，系統100中的操作符對數據流進行操作。操作符可以由多個查詢共 享，其中，每個查詢可以由一個或多個數據流表示。並且，由操作符創建子查詢。在一個意 義上，由多個操作符構成的任何查詢具有多個子查詢，每個操作符具有一個子查詢，即便查 詢針對單個客戶端。在另一意義上，當來自另一客戶端的新查詢能夠使用先前查詢的結果 作為部分結果時，先前查詢變成新查詢的子查詢。例如，關於其中先前查詢可部分地用於新 查詢的情況，可以由節點對表示先前請求的結果的數據流執行過濾操作。例如，原始客戶端 查詢可以請求在加利福尼亞北部中所有公寓列表，以及可以在節點處執行過濾操作以導出 僅僅帕洛阿爾託的列表。聯接操作是將傳統資料庫中的兩個表格進行聯接，諸如僱員的地址和僱員ID的 聯接。除了具有連續或周期性地傳輸的數據的數據流之外，對數據流應用相同的操作，使用 滑動窗來確定在流中何處執行聯接。例如，聯接操作符具有作為一個輸入的第一流以及作 為另一輸入的第二流。如果來自流的數據具有在滑動窗中的時間戳，則執行聯接。滑動窗 的示例可以是2分鐘窗，但是可以使用其他長度的窗。操作符可以在不同的覆蓋節點處進行分派，以及可以隨著網絡上查詢的分布被最 優化而隨著時間進行再分配。最優化可以考慮數種類型的度量。這些類型的度量可以包括 節點級度量(諸如CPU利用率、存儲器利用率等)以及服務提供商度量(諸如帶寬消耗) 等。並且，考慮諸如等待時間的Q0S度量。下面更詳細描述最優化。可以將對於數據的客戶端查詢提交到覆蓋網絡110。用於查詢的操作符的位置定 義查詢的部署計劃，其也在下面進行更詳細說明。根據網絡中可用的資源和查詢的要求，每 個查詢能夠具有多個備選的預先計算的部署計劃。通過覆蓋網絡110中的節點111之間的 覆蓋鏈路，互連查詢的操作符。每個操作符將操作符的輸出轉發到查詢計劃中的下一個處 理操作符。因此，查詢部署創建具有與登記查詢的數據流一致的拓撲結構的覆蓋網絡。如 果操作符Oi將其輸出轉發到操作符Op Oi稱為Oj的上遊操作符(或其發布者)，而A則稱 為Oi的下遊操作符(或其訂戶)。操作符能夠具有多個發布者(例如聯接、合併操作符)， 以及由於它們能夠跨查詢共享，它們也能夠具有多個訂戶。Oi的訂戶集合被表示為SUbtli， 而它的發布者的集合則被表示為PUbtlit5系統100還包括數據源140和客戶端150。數據源140發布數據流，而客戶端則訂 閱它們的數據興趣，所述數據興趣被表達為面向流的連續查詢。系統100經由在覆蓋節點 111中部署的操作符將來自發布者的數據流送到客戶端。所發布的數據流的示例可以包括 RSS饋給、來自傳感器網絡的數據、來自在網際網路上玩的多玩家遊戲的數據等。創建用於查詢的部署計劃包括識別要在部署查詢的覆蓋節點上主控的操作符。 為了發現用於主控操作符的潛在的覆蓋節點，使用資源目錄120。資源目錄120可以是 在多個覆蓋節點上提供的分布式服務。在一個實施例中，資源目錄120基於在Basu等人 的「Nodewiz :Peer_to-peer resource discovery for grids，，中描述的 NodeWiz 系統。 NodeWiz系統是用於資源發現的可擴縮的基於樹的覆蓋基礎結構。覆蓋節點110使用資源目錄120來通告每個節點的可用計算機資源的屬性，以及 高效地執行多屬性查詢來發現所通告的資源。例如，每個覆蓋節點發送它的可用計算機資 源能力(capacity)到資源目錄120，並且資源目錄120存儲該信息。能力屬性的示例包括 CPU能力、存儲器能力、I/O能力等。並且，在最優化期間，覆蓋節點或某其他實體可以發送查詢到資源目錄120來識別具有預定可用能力的覆蓋節點，其能夠被用於執行重定位的操 作符。資源目錄120能夠適配操作符的分派，使得分布通告和執行查詢的負荷在節點上是 平衡的。網絡監視服務130收集覆蓋節點111之間的覆蓋鏈路的統計量。統計量的一 個示例包括等待時間統計量。網路監視服務130可以基於在Yalagandula等人的「s3 =A scalable sensing service formonitoring large networked systems，，中描述的 S3。網 絡監視服務130是用於對大的聯網系統進行實時和可配置監視的可擴縮感測服務。可以包 括覆蓋節點111的基礎結構能夠被用於測量QoS、節點級以及服務提供商度量，同時它以可 擴縮方式聚集數據。此外，推理算法能夠用於基於網絡路徑的小集合來導出所有節點對的 路徑性質。在最優化期間，能夠查詢網絡監視服務130來識別提供必需的QoS的節點之間 的端到端覆蓋路徑或覆蓋鏈路，例如具有小於閾值的等待時間的路徑。圖2示出部署數據流的示例。例如，實時金融發布者140a響應於一個或多個客戶 端查詢而生成具有實時股票報價的數據流。金融新聞發布者140b還生成金融新聞的數據 流。在節點llla-e處的操作符用於通過執行它們的相應操作符來提供子查詢，以便向客戶 端提供期望的數據。例如，客戶端150a_c想要股票報價以及不同公司的對應金融新聞，並 且客戶端150b和150c需要數據流的特定分類。操作符對來自發布者的原始數據流執行子 查詢，以提供期望的數據給客戶端。在最優化期間，可能確定需要從節點Illa移走聯接操作符，因為節點Illa超負 荷或存在QoS度量約束違反。聯接操作符可以移動到節點lllf，但是下遊操作符將受影響。 最優化預先計算可行部署計劃，所述可行部署計劃不會違反QoS度量約束或節點的計算機 資源能力。系統100實現最優化協議，該最優化協議促進操作符在覆蓋網絡中的節點間的分 布，以便每個查詢的QoS期望以及節點的相應資源約束不被違反。最優化包括預先計算用 於所有登記的查詢的備選可行部署計劃。每個節點維持關於它的本地操作符的放置的信 息，並周期性地與其「緊密鄰域」中的節點協作以形成分布總操作符集合的部署計劃。部署 計劃識別操作符和用於主控操作符的節點，從而為數據流提供從發布者到客戶端的端到端 覆蓋路徑。只要針對現有部署計劃發生計算機資源或QoS度量約束違反，系統都能夠通過應 用來自預先計算的集合中的最合適計劃來快速反應。此外，即便沒有違反，系統也能夠通過 應用比當前部署更高效的部署來周期性地改進其當前狀態。最優化過程包括主動的、分布式的、操作符放置，其基於通知下遊操作符/節點它 們的上遊操作符的可行放置。以這種方式，覆蓋節點能夠做出關於它們的本地和上遊操作 符的放置的決策，所述決策將以可能的最佳方式影響它們的共享查詢。此方法的一個主要 優點是，節點能夠自己做出放置決策，這提供對於任何QoS度量約束違反的快速反應。每個操作符周期性地發送部署計劃到它的訂閱的下遊操作符，所述部署計劃描述 它們的上遊操作符的可能放置。這些計劃被稱為部分的，因為它們僅僅部署查詢的操作符 的子集。當節點接收到來自上遊節點的部分計劃時，它通過添加它們的上遊操作符的可能 放置來擴展該計劃。滿足計劃中共享操作符的所有查詢的QoS約束的部分計劃被傳播到其 他節點。
7
為了識別可行部署計劃，執行k_向前(k-ahead)搜索。該k_向前搜索發現從本 地操作符向前k個操作符的放置，其例如導致最低的等待時間。可以使用其他QoS度量而 不是等待時間。基於最小的等待時間，儘可能早地在最優化過程中消除可能違反QoS限制 (例如大於閾值的等待時間)的部分計劃。並且，每個節點最終化它的本地部分計劃。這 可以包括每個節點評估它對於帶寬消耗和所有受影響查詢的等待時間的影響。使用最終計 劃，節點能夠在運行時間做出快速的放置決策。應該注意到，可以使用數種類型的度量來選擇部署計劃。例如，當選擇備選可 行部署計劃集合時，由客戶端提供的一個或多個QoS度量(諸如端到端等待時間)以及 一個或多個節點級度量(諸如計算機資源的可用能力)能夠被用於確定路徑是否是可 行路徑。此外，另一種類型的度量(例如服務提供商度量，諸如最小總帶寬消耗、聯合 (consolidation)等)能夠被用於為數據流從可行部署計劃集合中選擇一個路徑來部署。現在詳細描述最優化過程，以及下方表1中的符號定義被用於描述最優化過程。表1 符號定義^JL操作符Oi的成本rof操作符Oi的輸入率查詢屮的 Q0S必查詢qt的響應等待時間SUb0i Oi的訂戶(下遊操作符)PUb0i Oi的發布者(上遊操作符)h (Oi)操作符Oi的主控節點Ci 節點Iii的能力義在η,上主控的操作符集合共享操作符Oi的查詢集合
、操作符Oi的候選主機A Oi的上遊操作符0(qt) 查詢qt中的操作符集合每個覆蓋節點周期性地識別其所有本地操作符的部分部署計劃集合。假設操作符 Qi由查詢集合仏εβ。,所共享。還令^是0i的上遊操作符的集合。在圖3中示出示例。查詢 Q1和q2共享操作符O1和o2，並且弋二 PoA =IoltO2) o用於0i的部分部署計劃將每個操作符~ e Oy eg, U h}分派到網絡中的覆蓋節點 之一。每個部分計劃P與下述相關聯(a)部分成本，PCp，例如它發生的帶寬消耗，以及(b) 它影響的每個查詢的部分等待時間，/。例如，用於02的部分計劃將操作符O1和 O2分派到兩個節點，評估由這些放置導致消耗的帶寬，以及針對每個查詢Q1和q2的直到操 作符O2的響應等待時間。圖3還示出了候選節點、候選鏈路以及這些鏈路的等待時間，當確定節點鏈路能 否用作可行部署計劃的一部分時對其進行評估。下面更詳細描述用於部署計劃生成的對候
8選節點和QoS度量(例如等待時間)的評估。圖4示出根據實施例的用於查詢的初始放置的方法400。在步驟401，客戶端登記 查詢。例如，圖2中所示的客戶端150a發送客戶端查詢到發布者140a和140b以請求股票 報價和相關的金融新聞。在步驟402，當前部署的該查詢的任何操作符和數據流被識別。圖2中所示的資源 目錄120可以用於存儲關於部署的操作符和流的信息。在步驟403，對於不存在的任何操作符，識別具有充足計算機資源能力且最接近發 布者或它們的發布者操作符的節點來主控該操作符。注意這用於節點的初始分派/查詢的 初始放置。可以選擇可能不最接近發布者或它們的發布者操作符的其他節點以進行最優 化。在步驟404，使用來自步驟402的操作符和數據流(如果有的話)，以及來自步驟 403的操作符(如果有的話)來部署查詢。例如，用於查詢的數據流被發送到登記查詢的客 戶端。在步驟405，開始最優化過程。最優化過程識別在一個或多個度量方面可能優於當 前部署計劃的部署計劃。圖5示出了根據實施例的用於最優化過程的方法500。方法500的一個或多個步 驟可以在方法400中的步驟405處執行。在步驟501，周期性地啟動計劃生成過程。該過程創建反映最當前的節點工作負荷 和網絡狀況的可行部署計劃。這些預先計算的部署計劃被存儲在覆蓋節點上，並且當檢測 到QoS違反時或如果確定能否通過部署其中一個預先計算的計劃來改善帶寬消耗或另一 度量，可以使用這些預先計算的部署計劃。下面參考方法600更詳細地描述計劃生成過程。在步驟502，節點確定是否發生了 QoS度量約束違反。例如，將QoS度量(諸如等 待時間)與作為約束的閾值進行比較。如果超出閾值，則發生了 QoS違反。為了檢測這些違反，每個覆蓋節點對於每個本地操作符監視到它的發布者的位置 的等待時間。它還周期性地接收共享其本地操作符的所有查詢的等待時間，並且它量化它 們的距它們的QoS期望的「鬆弛(slack) 」，也就是每個查詢能夠容忍的等待時間的增加。例 如，假設操作符Oi具有單個發布者0m並由查詢qt共享，該查詢qt具有響應延遲Clqt以及鬆弛 Slackqto如果在Oi與Om之間的覆蓋鏈路的等待時間增加了 Ad(h(0m)，h(0i)) > Slackqt, 則查詢qt的QoS被違反，且應該立即應用不同的部署。在步驟503，如果發生了 QoS違反，確定能否使用預先計算的計劃之一來改善QoS。 該計劃應該充分改善QoS以移除QoS違反。在存儲在Oi的主機處的所有最終計劃上，針對計劃ρ執行搜索，計劃P將qt的等 待時間減少至少Ap^ =^ -Qos,'。在滿足該條件的所有計劃中，移除不遷移Oi和0m(也就 是包括瓶頸鏈路)並滿足下述條件的任何計劃P +^iKom ), Koi)) < QoSqt -々。如果存在能夠用於改善QoS的預先計算的計劃，則在步驟504部署該預先計算的 計劃。例如，如上所述，移除不遷移(也就是包括瓶頸鏈路)並滿足Ap/糹+Ad(Mom), /i(o,.)) < QoSqt - 的任何計劃P。從剩餘的計劃中，應用對帶寬消耗改善最多的一個計劃。
否則，如步驟505，將對於能夠改善QoS的可行計劃的請求發送到其他節點。例如， 該請求被傳播到它的下遊訂戶/操作符。也就是，如果在Oi的主機處不能發現能夠滿足qt 的QoS的部署，則節點針對違反的查詢qt向它的訂戶發送對於合適計劃的請求。該請求還 包括關於擁塞鏈路的元數據(例如它的新等待時間)。接收到這種請求的節點嘗試發現能 夠滿足查詢qt的QoS的計劃。由於下遊節點存儲遷移較多操作符的計劃，它們更可能發現 用於qt的可行部署。傳播繼續，直到達到主控所違反查詢的最後操作符的節點為止。在步驟506，確定是否能夠響應於該請求而識別出計劃。如果不能識別出計劃，則 在步驟507不能滿足該查詢。可以通知客戶端不能滿足該查詢，並且客戶端可以登記另一 查詢。否則，響應於該請求而識別的、能夠充分改善QoS以移除QoS違反的計劃被部署。重要的是要注意，識別新的部署計劃具有小的開銷。本質上，節點必須搜索充分減 小查詢的等待時間的計劃。最終計劃能夠基於它們所影響的查詢來進行索引，並基於它們 對於每個查詢的等待時間的影響來進行分類。因此，當發生QoS違反時，我們的系統能夠非 常快地識別它的「恢復」部署。在步驟502-507，可以響應於QoS違反而部署新計劃。這些步驟中的很多步驟也 可以在如下時候進行部署當沒有發生QoS違反，但是確定出新計劃能夠提供比現有計劃 更好的QoS或更好的節點級(例如計算機資源能力)或服務提供商度量(例如帶寬消耗) 時。圖6示出了根據實施例的用於部署計劃生成的方法600。方法600的一個或多個 步驟可以在方法500中的步驟501處作為計劃生成過程執行。可以在方法600之前執行k-向前搜索，並且下面對該k-向前搜索進行更詳細描 述。k-向前搜索使得每個節點知道能夠用於部分部署計劃的本地操作符的候選主機。在步驟601，在葉節點處生成部分部署計劃。令Oi是在節點nv上執行的葉操作符。 節點nv創建部分計劃的集合，每個部分計劃將Oi分派到不同的候選主機 e aO1、並且評估 它的部分成本和共享Oi的所有查詢的部分等待時間。如果&,是用於(^的輸入源的集合，且
是代表源s發布數據的節點，則查詢qt的部分等待時間(也就是從源到~的等
待時間)是，二 最終，由於該計劃分派了第一操作符，它的部分帶寬
ο
消耗為零。在步驟602，消除不可行的部分部署計劃。一旦創建了部分計劃，則做出關於該部 分計劃是否應該向下遊轉發以及是否應該通過添加更多操作符遷移來擴充的決策。僅僅當 部分計劃能夠導致可行部署時，才傳播該部分計劃。該決策基於k_向前搜索的結果。三元 組(0i，nj，qt)的k_向前等待時間表示在Oi之前的k個操作符的所有可能放置上查詢1的 最小等待時間開銷，其中假設Oi放置在Hj上。如果查詢直至操作符Oi的等待時間加上之 前k個操作符的最小等待時間違反了查詢的QoS，則部分計劃不能導致任何可行的部署。更
具體地，如果存在至少一個查詢義e β。,使得/^彳+ γ^ηj,qi)> QoSqt，則將操作符0i放置到
節點~的部分計劃ρ是不可行的。注意，k_向前等待時間，雖然它沒有消除可行計劃，但它沒有識別出所有不可行的 部署。因此，所傳播的計劃是「潛在地」可行的計劃，但其可能在以後的步驟中被證明不可行。此外，存在關於參數k的權衡。向前搜索的操作符越多，則k_向前搜索的開銷就 越高，但是就能越早地發現不可行的計劃。在步驟603，沒有消除的部分計劃連同用於評估新部分計劃的影響的元數據被向 下遊轉發。這些包括從步驟602識別出的可行的部分部署計劃。該元數據可以包括部分等 待時間和/或用於確定計劃可行性的其他度量。假設處理操作符Oi的節點nv從它的發布者om e /^&。;接收到部分計劃ρ。為了例 示目的假設單個發布者，但是下面的公式能夠以簡單明了的方式被推廣用於多個發布者。 注意，共享Oi的每個查詢也共享它的發布者。因此，每個接收的計劃包括部分等待時間
。最優化過程通過添加本地操作符Oi到其候選主機的遷移來對這些計劃中的每 個計劃進行擴充。對於每個候選主機 €Λ ,節點ην驗證資源可用性。例如，它解析計劃ρ來檢查
是否也已經將任何上遊操作符分派到η」。為了促進此，連同每個計劃發送關於每個計劃 中包括的每個操作符的期望負荷要求的元數據。如果~的殘餘能力足以處理包括Oi的 所有分派的操作符，則新的部分計劃f的影響被估計為-.Plfqt =d{_hp(PnXnj)Nq, e麼以及 <-嚴「+O^F(Oa)，其中，hp(οω)是在部分計劃ρ中的om的主機。對於每個新的部
分計劃f，我們還基於k-向前等待時間乂義)來檢查它能否導致可行的部署，並僅僅傳 播可行的部分計劃。在步驟604，接收到在步驟603處轉發的部分計劃的中間上遊節點確定部分計劃 可行性，如上所述。例如，接收該計劃的中間節點是該查詢的操作符的候選者。該中間節 點驗證它的用於主控操作符的計算機資源可用性，並且確定如果該節點主控操作符時對於 QoS的影響。在步驟605，基於對於服務提供商度量的影響來選擇可行的部分計劃，所述服 務提供商度量諸如帶寬消耗。在步驟606，將所選擇的可行部分計劃存儲在覆蓋節點中。例如，在節點上創建的 部分計劃被「最終化」並被本地存儲。為了最終化部分計劃，評估該部分計劃對於當前帶寬 消耗以及對於它所影響的查詢的等待時間的影響。為了實現該過程，維持關於由每個本地 操作符的上遊操作符消耗的帶寬以及直到該本地操作符的查詢等待時間的統計量。例如， 在圖3中，如果O1是葉操作符，η2維持關於從O1到O2的帶寬消耗以及直到操作符O2的等待 時間的統計量。對於每個計劃，當前部署與該計劃所建議的部署之間的這些度量的差異被 評估，並作為元數據連同對應的最終計劃被一起存儲。因此，每個節點存儲用於它的本地和 上遊操作符的可行部署的集合，以及這些部署對於系統成本及查詢的等待時間的影響。在 圖3中，叫存儲遷移操作符{0l，ο2}的計劃，而Ii4將存儲放置{0l，02，04}的計劃。組合併擴充從上遊節點接收的部分計劃能夠生成大量的最終計劃。為了應對此問 題，可以採用許多消除試探法。例如，在對查詢等待時間具有類似影響的最終計劃中，保持 那些具有最小帶寬消耗的最終計劃，而如果它們對帶寬具有類似影響，則保持將查詢等待 時間減小最多的那些最終計劃。如上所述，節點執行k_向前搜索來識別用於本地操作符的候選主機。在步驟601，
葉節點創建部分計劃。可以使用k_向前搜索來創建部分計劃。
11
在k_向前搜索中，每個節點nv針對每個本地操作符A_ e 以及用於該操作符的 每個候選主機而運行k-向前搜索。如果是用於Oi的候選主機的集合，則該搜索針對共 享Oi的每個查詢識別Oi之前的k個操作符的最小等待時間放置，其中假設Oi放置在節點 nJ e Ai上。直觀地，如果將Oi遷移到節點IIj做出了用於每個查詢qt的下k個下遊操作符 的最好放置決策(例如關於等待時間)，則搜索嘗試識別出對於每個查詢仏6 等待時 間的最小影響。下面描述了 k-向前搜索的步驟，其最初評估ι-向前等待時間，然後導出針 對每個三元組(0i，nj; qt)的k_向前等待時間值，其中，A e °nr y ^麼^t ^ Qol。對於每個操作符A e ，nv執行以下的步驟1.通過查詢資源目錄服務來識別本地操作符Oi的候選主機 的集合。對於這些候選節點的每一個，它針對等待時間d(rv nt), V G A0^nt e 而查詢聯網監視服務。Oi操作符關於它的候選nj以及查詢幻^麼的卜向
前等待時間是八 而)二二、伶(η,，",)}。在圖3中，卯緣=α3，以及ηι將向Ii2請求用 於操作符O2的候選主機、，以及將估計I-向前等待時間以 仏；！二乂㈨而)=… ^。並 且，對於ο2，我們假設M(M6J1) = 5ms以及M(H) = 棚。3.搜索輪循(in rounds)繼續，其中，對於每個操作符Oi，節點等待查詢仏e込^中 它的訂戶Om完成(k-l)_向前等待時間的評估，之後它們繼續估計k-向前等待時間。0i操作 符關於它的候選η」以及查詢識e &的k-向前等待時間是乂("A)、=。使用圖3中的示例描述最後步驟。在此情況下， ？^㈨，的卜！！！叫卯+化丨㈨而丨瀏+以 ，「卜於^^因此，假設O1遷移到n5，具有下兩個操作符 的最小等待時間的放置將Q1的部分響應等待時間增加15ms，並將q2的部分等待時間增加 25ms，其中，隨著將更多操作符分派到查詢，每個部分等待時間增加。共享查詢的並發修改需要特別注意，因為它們能夠關於它們的受影響的查詢的最 終等待時間創建衝突。例如，在圖3中，假設qi和q2的QoS沒有被滿足，以及節點Ii3和Ii4 並發地決定對每個查詢應用不同的部署計劃。這些計劃的並行執行不保證它們的QoS期望 將被滿足。為了解決此問題，可以複製操作符。每當遷移操作符無法滿足所有它們的依賴的 (dependent)查詢的QoS度量約束時，通過複製操作符來實現部署計劃。但是，複製處理增 加了帶寬消耗以及系統中的處理負荷。因此，過程識別能否利用備選候選計劃來解決衝突， 以及如果沒有可用的候選計劃，則它應用複製。過程使用在計劃生成階段期間創建的元數 據來識別對於複製解決方案的備選方案。更具體地，它使用現有的部署計劃來(1)決定應 用通過遷移的計劃是否滿足了所有並發地違反的查詢；(2)每當安全時允許多個遷移，也 就是允許並行遷移；以及(3)當不能使用現有的計劃時，構建非衝突計劃。在下面的段落 中，使用以下定義來描述該過程。
對於直接依賴的定義如果兩個查詢Qi和q^共享操作符，也就是使得 Qi e Q(Ok)且q」e Q(Ok)，則該兩個查詢Qi和q」是直接依賴的。從而，Qi和q」是每個操作 符Ok的依賴查詢。注意，查詢Qi的依賴查詢集合是Dqi，且操作符Ok的依賴查詢是。那 麼，如果0(qi)是查詢qi中的操作符集合，則A·
丄O直接依賴的查詢不具有獨立的計劃，並因此，它們的部署計劃的並發修改需要特 別處理以避免任何衝突和延遲約束的違反。對於間接依賴的定義如果Phr^) = 0且A·, I D0t ，則兩個查詢Qi和q」是間 接依賴的。間接依賴的查詢具有獨立的(不重疊的)計劃。但是，對它們的部署計劃的並發 修改會影響它們共有的依賴查詢。因此，過程也解決這些衝突，確保滿足依賴查詢的QoS期 望。為了檢測並發修改，使用基於租賃(lease based)的方法。一旦節點決定應該應用新 的部署，則鎖定在計劃中的所有操作符以及它們的上遊操作符。嘗試遷移已經鎖定的操作 符的節點檢查它們的修改是否不與進行中的當前修改發生衝突。如果存在衝突，它嘗試識 別備選非衝突部署。否則，它通過複製操作符來應用它的初始計劃。在下面的段落中描述 基於租賃的方法。假設節點決定了將計劃ρ應用於查詢q。它將請求鎖定(q，P) (REQUEST L0CK(q, P))消息轉發到它的發布者和訂戶。為了處理間接依賴，接收到鎖定請求的每個節點，也將 該鎖定請求發送到查詢q的它的本地操作符的訂戶。該請求向執行任何查詢操作符以及它 們的依賴者的節點通知新的部署計劃，並請求鎖定q及其依賴者。假定沒有查詢具有鎖定 (這對沒有依賴者的查詢總是成立的)，一旦發布者/訂戶從它們自身的發布者/訂戶接收 到該查詢的遷移租賃(q) (MIGRLEASE(q))請求，則該發布者/訂戶利用MIGR LEASE (q)準 許來進行答覆。已經準許了遷移租賃的節點不被允許準許另一遷移租賃，直到所述租賃已 經被釋放(或期滿，基於某個期滿閾值)為止。一旦節點η從所有它的發布者和訂戶接收到q的遷移租賃，它將計劃P應用於 該查詢。它將解析部署計劃，以及對於主控將操作符ο遷移到節點η的每個節點發送 MIGRATE (ο, η)消息。在查詢計劃的自頂向下的方向上應用遷移，也就是，最上遊的節點遷移 它們的操作符(如果計劃需要)，並且一旦該過程完成，則緊接操作符被通知該改變並訂閱 操作符的新位置。隨著節點更新它們的連接，它們還應用計劃所指定的任何本地遷移。一 旦部署了整個計劃，則將釋放鎖定(q) (RELEASE LOCK (q))請求轉發到操作符及它們的依賴 者的舊位置，其釋放對於查詢的鎖定。在主控計劃中包括的操作符的所有節點以及共享該計劃的操作符的所有查詢上， 發送鎖定請求。一旦已經準許了鎖定，則將通過複製或遷移租賃來滿足任何以後的鎖定請 求。遷移租賃允許通過遷移部署計劃的操作符來應用該部署計劃。但是，如果由於查詢網 絡上的並發修改導致不能準許這樣的租賃，能夠準許複製租賃，允許節點通過複製涉及的 操作符來應用該查詢的部署計劃。以這種方式，僅僅該特定查詢將受到影響。應該注意到的一個性質是，如果由查詢集合Aii共享操作符Oi，則根植於(rooted from)Oi的子計劃也由相同的查詢集合共享。現在假設兩個依賴的查詢Qi和q」，該兩個依 賴的查詢qi和q」的QoS度量約束均被違反。查詢qi發送REQUESTL0CK(qi，pi)請求到該
13下遊操作符並且對於查詢q^也類似。此外，知道該依賴的共享操作符將相同的請求轉發到 它們的訂戶，以也向依賴的查詢通知所請求的鎖定。由於查詢共享一些操作符，至少一個操 作符將接收到兩個鎖定請求。在接收到第一請求後，它應用下述的過程，也就是基於兩個計 劃的元數據來識別衝突並解決它們。但是，當對於鎖定的第二請求到達時，用於接收的第一 共享節點不將其轉發到任何發布者，因為用於該查詢的遷移租賃已經被準許。下面的段落描述了當嘗試對於直接和間接依賴解決衝突時所遇到的不同情形。對 於直接依賴，遇到對直接依賴的計劃的並發修改。關於並行遷移，並發修改並非總是衝突的。如果兩個部署計劃不影響相同的查詢 集合，則該兩個計劃能夠並行地應用。例如，在圖3中，如果Ii3和Ii4決定分別僅遷移O3和 O4,則能夠應用該兩個改變。在這種情形下，由II3和II4決定的這兩個計劃應當分別不會顯 示出對查詢Q1和％的影響。部署計劃包括所有需要的信息(要遷移的操作符、新主機、對 於查詢的影響)，以高效地識別這些情形，並因此對多個非衝突的計劃準許遷移租賃。關於冗餘遷移，為了保證查詢的QoS期望，由多個計劃的並發部署定義的多個遷 移可能經常是不必要的。很經常地，節點可能並行地識別QoS違反，並嘗試通過應用它們自 己的本地存儲的部署計劃來解決它們。在這種情形下，很可能的是任一個計劃將足以重新 配置當前部署。但是，每個計劃包括對所有受影響的查詢的影響的評估。因此，如果兩個計 劃P1和P2均影響相同的查詢集合，則應用任何一個依然會提供我們的查詢的可行部署。因 此，應用首先獲得遷移租賃的計劃，而忽略第二計劃。關於備選遷移計劃，不能並行應用重新定位共享操作符的部署計劃。在這種情形 下，請求鎖定的第一計劃遷移操作符，同時進行嘗試以識別新的備選非衝突部署計劃來滿 足任何未被滿足的QoS期望。由於第一計劃正遷移共享的操作符，則搜索下遊操作符的主 機以尋找在該遷移之上建立的任何計劃。例如，在圖3中，如果第一計劃遷移操作符O1，但 是q2的QoS依然沒有被滿足，則搜索節點Ii4以尋找包括對於O1的相同遷移並能夠通過也 遷移O4而進一步減少q2的響應延遲的任何計劃。關於間接依賴，查詢可能不共享操作符，但是依然共享依賴者。因此，如果進行嘗 試以修改間接依賴的查詢的部署，則考慮對它們的共享的依賴者的影響。在這種情形下，如 果要應用的計劃影響依賴查詢的重疊集合，對第一鎖定請求準許遷移租賃，以及對任何以 後請求準許複製租賃。但是，在它們不影響相同查詢的QoS的情形下，能夠並行地應用這些 計劃。圖7示出用於共享查詢的並發修改的方法700。在步驟701，節點確定例如由於違 反QoS度量約束而導致應該應用新的部署計劃。在步驟702，鎖定計劃中的所有操作符，除非這些操作符已經被鎖定。如果任何操 作符被鎖定，則在步驟703做出關於是否存在衝突的確定。在步驟704，如果存在衝突，則節點嘗試識別備選非衝突部署。在步驟705，如果不存在衝突，則節點複製操作符並應用它的初始計劃。圖8示出計算機系統800的例示框圖，所述計算機系統800可以在圖1中所示的 系統100中用作節點(也就是覆蓋節點)。計算機系統800包括一個或多個處理器，所述處 理器諸如處理器802，以提供用於執行軟體的執行平臺。經由通信總線805傳送來自處理器802的命令和數據。計算機系統800還包括主
14存儲器804和數據儲存器806，所述主存儲器804諸如隨機存取存儲器(RAM)，其中軟體在 運行時間期間可以駐留在所述主存儲器中。數據儲存器806包括例如硬碟驅動器和/或可 移除存儲驅動器、或非易失性存儲器，其中可以存儲軟體的副本，所述可移除存儲驅動器代 表軟盤驅動器、磁帶驅動器、緊緻盤驅動器等。數據儲存器806還可以包括R0M(只讀存儲 器)、EPROM(可擦除可編程ROM)、EEPROM(電可擦除可編程ROM)。除了用於路由以及這裡 描述的其他步驟的軟體之外，可以將路由表、網絡度量和其他數據存儲在主存儲器804和/ 或數據儲存器806中。用戶利用一個或多個I/O裝置807與計算機系統800對接，所述I/O裝置諸如鍵 盤、滑鼠、指示筆、顯示器等。提供網絡接口 808，用於與其他節點和計算機系統進行通信。這裡描述的方法的一個或多個步驟以及這裡描述的其他步驟可以實現為嵌入在 計算機可讀介質上的軟體，以及例如由處理器802在計算機系統800上執行，所述計算機可 讀介質諸如存儲器804和/或數據儲存器806。這些步驟可以由電腦程式實施，所述計 算機程序可以以活動和不活動的多種形式存在。例如，它們可以作為由用於執行一些步驟 的程序指令組成的(一個或多個)軟體程序而存在，所述程序指令採用原始碼、目標代碼、 可執行代碼或其他格式。上面的任何一種可以實施在計算機可讀介質上，所述計算機可讀 介質包括存儲裝置和壓縮或非壓縮形式的信號。適當的計算機可讀存儲裝置的示例包括傳 統的計算機系統RAM(隨機存取存儲器)、R0M(只讀存儲器)、EPROM(可擦除可編程ROM)、 EEPROM(電可擦除可編程ROM)以及磁碟或光碟或磁帶或光帶。計算機可讀信號(不管是否 使用載波調製)的示例是主控或運行電腦程式的計算機系統可以配置來訪問的信號，包 括通過網際網路或其他網絡下載的信號。前述的具體示例包括在⑶ROM上或經由網際網路下 載來分布程序。在某種意義上，作為抽象實體的網際網路自身是計算機可讀介質。這對於一 般的計算機網絡同樣成立。因此要理解，下面列舉的那些功能可以由能夠執行上述功能的 任何電子裝置來執行。雖然參考示例描述了實施例，但是本領域技術人員將能夠對所描述的實施例做出 多種修改，而不偏離請求保護的實施例的範圍。
權利要求
一種在分布式共享流處理系統中為查詢提供部署計劃的方法，所述方法包括為當前部署在所述流處理系統中的查詢存儲預先計算的可行部署計劃的集合，其中查詢包括主控在所述流處理系統中的節點上的多個操作符以響應於客戶端對於信息的請求而提供數據流；確定是否違反了所述查詢的QoS度量約束；以及響應於確定違反了所述QoS度量約束，從所述可行部署計劃的集合中選擇部署計劃以用於提供所述查詢。
2.根據權利要求1所述的方法，其中，存儲可行部署計劃的集合包括 識別多個部分部署計劃；基於QoS度量從所述多個部分部署計劃中識別可行的部分部署計劃； 基於運行每個計劃的操作符的節點的計算機資源的可用性，識別所述可行的部分部署 計劃的子集；選擇所述可行的部分部署計劃的子集中的一個或多個來最優化服務提供商度量；以及 存儲所選擇的計劃。
3.根據權利要求2所述的方法，其中，識別多個部分部署計劃包括對於所述查詢在葉 節點處識別多個部分部署計劃；以及將確定為可行的部分部署計劃連同元數據一起向下遊轉發到用於主控所述部分部署 計劃中的操作符的節點，所述元數據由下遊節點用於利用它的本地執行的操作符的放置來 擴充所述部分部署計劃並量化所述放置對QoS度量的影響。
4.根據權利要求3所述的方法，其中，對於所述查詢在葉節點處識別多個部分部署計 劃包括執行k-向前搜索以確定對QoS度量的影響從而提供k個下遊操作符的最佳放置。
5.根據權利要求4所述的方法，其中，所述k-向前搜索包括對於每個部分部署計劃，識別候選節點來主控所述部分部署計劃中的操作符； 發送請求到主控下遊操作符的節點，以請求該下遊操作符的第二候選主機集合以及對 於所述候選者的QoS度量的估計；對於每個候選節點，評估是否違反了 QoS度量約束；以及對於後續下遊操作符重複發送請求和評估QoS度量的步驟，以確定不違反所述QoS度 量約束的部分計劃。
6.根據權利要求3所述的方法，其中，識別所述可行的部分部署計劃的子集包括 在每個下遊節點處，確定所述節點是否具有足夠的可用計算機資源來主控所述操作符；基於所述QoS度量來估計所述部分計劃的影響；以及 僅僅向下遊傳播滿足所述QoS度量約束的部分計劃。
7.根據權利要求6所述的方法，其中，選擇所述可行的部分部署計劃的子集中的一個 或多個以最優化服務提供商度量包括對於每個本地操作符的所有上遊操作符維持關於所述服務提供商度量的統計量；以及 基於所述統計量選擇所述可行的部分部署計劃的子集中的一個或多個來存儲。
8.根據權利要求1所述的方法，其中，確定是否違反了所述查詢的QoS度量約束包括 在所述查詢中的每個節點監視其操作符的到其發布者的位置的QoS度量；每個節點基於所述QoS度量的監視來確定是否違反了 QoS度量約束。
9.根據權利要求8所述的方法，其中，每個節點確定是否違反了QoS度量約束包括 對於每個節點，確定共享在所述節點上主控的操作符的所有查詢的QoS度量；確定是否對於任何查詢違反了 QoS度量的容限。
10.一種用於在分布式流處理系統中解決衝突以部署用於查詢的部署計劃的方法，所 述方法包括確定應該為現有查詢應用新部署計劃；對於在所述新部署計劃中的每個操作符，如果該操作符尚未被鎖定，則鎖定該操作符；如果所述操作符已經被鎖定，確定是否存在衝突；如果存在衝突，識別備選部署計劃；如果不存在衝突，複製所述操作符並部署所述新部署計劃。
11.根據權利要求10所述的方法，其中，鎖定操作符包括確定要應用所述新部署計劃的節點發送鎖定請求到所述查詢的它的發布者以及訂戶；以及接收到所述請求的每個節點發送所述請求到所述查詢的它的操作符的訂戶。
12.根據權利要求11所述的方法，其中，如果所述查詢的本地操作符還沒有被鎖定則 接收到所述請求的節點鎖定該操作符，其中鎖定所述操作符防止所述節點允許鎖定的操作 符的另一遷移直至該鎖定被釋放為止。
13.根據權利要求10所述的方法，其中，如果所述查詢與另一查詢具有直接或間接的 依賴則衝突在操作中存在，其中所述直接依賴基於所述查詢與所述另一查詢是否共享操作 符，並且所述間接依賴是當所述查詢與所述另一查詢不共享操作符但是存在所述查詢以及 所述另一查詢兩者與其共享操作符的第三查詢時。
14.一種存儲軟體的計算機可讀存儲介質，所述軟體包括指令，所述指令在執行時實現 包括以下步驟的方法在分布式流處理系統中，為當前部署在覆蓋網絡中的查詢創建部分部署計劃，從而向 數據流提供端到端覆蓋路徑；存儲關於由所述查詢的本地操作符的上遊操作符消耗的帶寬的統計量； 存儲關於直至所述本地操作符的查詢等待時間的統計量；對於每個部分部署計劃，評估所述部分部署計劃與當前部署的查詢的消耗帶寬和等待 時間之間的差異；以及對於每個部分部署計劃，如果評估的差異指示所述部分部署計劃優於所部署的查詢並 且所述部分部署計劃滿足QoS度量約束，則存儲所述部分部署計劃和用於後續評估所述部 分部署計劃的元數據。
15.根據權利要求14所述的計算機可讀介質，其中，所述查詢包括由所述覆蓋網絡中 的節點主控的多個操作符，並且每個節點創建、評估以及存儲部分部署計劃，所述部分部署 計劃一同形成用於所述查詢的多個預先計算的部署計劃。
全文摘要
一種用於在分布式共享流處理系統中為查詢提供部署計劃的方法，包括為當前部署在流處理系統中的查詢存儲可行部署計劃集合。查詢包括主控在流處理系統中的節點上的多個操作符以響應於對於信息的客戶端請求而提供數據流。該方法還包括確定是否違反了所述查詢的QoS度量約束，以及響應於確定違反了QoS度量約束，從所述可行部署計劃集合中選擇部署計劃以用於提供查詢。
文檔編號H04L12/56GK101933018SQ200980103432
公開日2010年12月29日 申請日期2009年1月29日 優先權日2008年1月29日
發明者O·帕帕馬諾伊, S·巴納傑, S·巴舒 申請人:惠普開發有限公司