動態(tài)流調(diào)度策略(數(shù)據(jù)庫)

時間：2022-12-18 10:30:01 | 來源：信息時代

時間：2022-12-18 10:30:01 來源：信息時代

    動態(tài)流調(diào)度策略 : 數(shù)據(jù)流管理系統(tǒng)根據(jù)數(shù)據(jù)流的特點制定的動態(tài)的任務(wù)調(diào)度策略。調(diào)度策略是一種積極的優(yōu)化策略,是影響系統(tǒng)的整體性能最關(guān)鍵的因素之一。理想的調(diào)度策略應(yīng)當(dāng)能夠保證: ①在資源一定的情況下獲得最優(yōu)的性能; ②及時發(fā)現(xiàn)系統(tǒng)過載,并觸發(fā)相應(yīng)解決機制(如突發(fā)流量處理);③保證特定查詢的QoS需求;④部署簡單,操作方便。在部署調(diào)度策略時,主要性能指標(biāo)包括: 對元組的響應(yīng)時間、內(nèi)存需要量、吞吐量、精確度等。在實施過程中,系統(tǒng)為達(dá)到各種性能指標(biāo)的要求會發(fā)生沖突(例如較小的響應(yīng)時間必然要求較大的內(nèi)存),所以對實際系統(tǒng)而言,尋找各種指標(biāo)的平衡至關(guān)重要。在具體的數(shù)據(jù)流管理系統(tǒng)中,往往會根據(jù)數(shù)據(jù)流的特點和要達(dá)到的目的,以部分犧牲其他性能為代價,選取其中的一種或一部分性能作為主要衡量指標(biāo)。
數(shù)據(jù)流快速、無限、連續(xù)、實時的特點要求數(shù)據(jù)流系統(tǒng)能夠?qū)崟r地對數(shù)據(jù)進(jìn)行處理。任務(wù)處理的主要目標(biāo)是要在滿足任務(wù)的截止時間情況下實現(xiàn)連續(xù)查詢。在通常情況下,任務(wù)在執(zhí)行過程中已經(jīng)執(zhí)行的時間以及還剩余多長時間才能執(zhí)行完成是動態(tài)變化的。因此,數(shù)據(jù)流管理系統(tǒng)一般使用動態(tài)的調(diào)度策略。
目前流行的數(shù)據(jù)流管理系統(tǒng)中,主要研究在資源限制條件下如何提高系統(tǒng)的適應(yīng)性、如何降低系統(tǒng)的平均延時,以及如何在近似查詢結(jié)果質(zhì)量與系統(tǒng)資源之間取得折衷等,但都沒有針對查詢關(guān)于截止期的要求給出切實可行的調(diào)度方法。因此,問題可歸結(jié)為: 在資源限制、動態(tài)爆發(fā)的實時數(shù)據(jù)流環(huán)境中,針對數(shù)據(jù)流上查詢主要是連續(xù)查詢,如何設(shè)計可適應(yīng)的、精確的、實時的批任務(wù)調(diào)度算法,降低調(diào)度開銷最大化可滿足各個查詢截止期的元組數(shù),最終使得近似查詢結(jié)果質(zhì)量最高。
數(shù)據(jù)流上可用于截止期動態(tài)調(diào)度的常見方法有兩種:
一種是tuple-at-a-time調(diào)度,如TelegraphCQ系統(tǒng)中的Eddy的路由調(diào)度策略。每次調(diào)度一個元組,判斷該元組是否會在當(dāng)前執(zhí)行的查詢處理完之前到期,是則該查詢直接跳過該元組處理下一個元組,反之則處理該元組。這種方法的優(yōu)點在于,通過對每個元組動態(tài)選擇路由,從而不斷動態(tài)優(yōu)化查詢計劃中的操作符順序,具有很強的適應(yīng)性。但在快速時變的數(shù)據(jù)流環(huán)境中,該調(diào)度策略具有很大的系統(tǒng)開銷,如調(diào)度隊列維護(hù)、內(nèi)存管理及上下文切換開銷等。特別是在數(shù)據(jù)流爆發(fā)的情況下,系統(tǒng)開銷會大幅增加,使得各查詢可在截止期內(nèi)完成處理的數(shù)據(jù)流數(shù)據(jù)量大大減少。
第二種為批處理策略,典型的批調(diào)度策略有如下幾種。STREAM系統(tǒng)使用Chain式調(diào)度方法,討論在系統(tǒng)負(fù)載高峰時,如何優(yōu)化資源管理以實現(xiàn)運行時內(nèi)存使用的最小化。Aurora系統(tǒng)使用二級調(diào)度策略,對操作符以及數(shù)據(jù)流數(shù)據(jù)分別批處理,進(jìn)而降低系統(tǒng)開銷,提高處理效率。然而,上述批調(diào)度策略均基于統(tǒng)計計算(如服務(wù)開銷,操作符選擇度等),對每批數(shù)據(jù)的處理開銷進(jìn)行估計,因而也不能滿足精確的截止期需求。例如,估算一批數(shù)據(jù)(100個數(shù)據(jù)流數(shù)據(jù))中有80個可在截止期內(nèi)完成,則使用降載策略(load shedder)丟掉其中20個。然而,實際上在截止期內(nèi)完成的數(shù)據(jù)流數(shù)據(jù)很可能多于或少于80個。相應(yīng)地,可能會多丟棄了一些可在截止期內(nèi)完成處理的數(shù)據(jù)流數(shù)據(jù),或者會浪費系統(tǒng)資源處理了一些過期數(shù)據(jù),降低了近似查詢結(jié)果的質(zhì)量。