數(shù)據(jù)流調(diào)度(數(shù)據(jù)庫)

時間：2022-11-20 20:30:01 | 來源：信息時代

時間：2022-11-20 20:30:01 來源：信息時代

    數(shù)據(jù)流調(diào)度 : 對數(shù)據(jù)流操作的執(zhí)行順序,可分成任務(wù)調(diào)度與任務(wù)內(nèi)操作符的調(diào)度。數(shù)據(jù)流任務(wù)調(diào)度是指根據(jù)一定的算法,從目前數(shù)據(jù)流管理系統(tǒng)中的一批連續(xù)查詢?nèi)蝿?wù)或一次性查詢?nèi)蝿?wù)中,選出若干個任務(wù),分配必要的資源,如內(nèi)存空間、外部設(shè)備等,為它們建立相應(yīng)任務(wù)進(jìn)程(或線程),最后把這些任務(wù)的程序調(diào)入內(nèi)存,等待調(diào)度程序去調(diào)度執(zhí)行。數(shù)據(jù)流操作符調(diào)度是指根據(jù)一定的算法,將查詢?nèi)蝿?wù)分解成一系列的操作并排定一定的執(zhí)行順序進(jìn)行調(diào)度執(zhí)行。
數(shù)據(jù)流任務(wù)調(diào)度的目標(biāo)是使任務(wù)運(yùn)行最大限度地發(fā)揮各種資源的利用率,并保持系統(tǒng)內(nèi)的各種活動充分運(yùn)行。
數(shù)據(jù)流系統(tǒng)的調(diào)度直接關(guān)系到查詢計劃的執(zhí)行和資源的分配,是數(shù)據(jù)流系統(tǒng)的核心問題之一。在實施過程中,系統(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ù)流應(yīng)用中,對系統(tǒng)的實時性要求較高,這一點與其他的實時系統(tǒng)相同。同時與其他的實時系統(tǒng)任務(wù)相比,數(shù)據(jù)流系統(tǒng)任務(wù)具有以下特點: 調(diào)度任務(wù)之間可能存在依賴關(guān)系; 調(diào)度任務(wù)之間可能共享滑動窗口; 調(diào)度任務(wù)可能存在不可搶占區(qū); 調(diào)度任務(wù)可能是一次性的任務(wù),也可能是連續(xù)周期性的任務(wù); 連續(xù)周期性的任務(wù)的每個周期需要的處理時間因滑動窗口規(guī)模的變化可能并不相同。
目前,數(shù)據(jù)流系統(tǒng)常用的調(diào)度算法有:
(1)先進(jìn)先出調(diào)度(FIFO):按到達(dá)順序處理每一個元組,在一個元組處理完成之后才會考慮下一個元組。FIFO策略在元組的最小化響應(yīng)時間方面起到很好的作用。但它沒有考慮運(yùn)算符的選擇率,對突發(fā)的數(shù)據(jù)流沒有適應(yīng)性,容易造成數(shù)據(jù)流元組的堆積,從而占用系統(tǒng)大量的內(nèi)存資源。
(2)環(huán)調(diào)度(round-robin): 在所有的運(yùn)算符之間循環(huán)。每個運(yùn)算符運(yùn)行一個固定的時間片,直到時間終止或隊列為空時停止。循環(huán)調(diào)度不會出現(xiàn)運(yùn)算符的饑餓狀態(tài),但它與FIFO一樣對于爆發(fā)性的數(shù)據(jù)流沒有適應(yīng)性。
(3)貪心調(diào)度(greedy): 在貪心調(diào)度策略中,每一個運(yùn)算符有一個靜態(tài)的優(yōu)先級(1-s)/t,其中,s為選擇率,t為運(yùn)算符處理一個元組的時間。這一策略考慮了運(yùn)算符的選擇率,按優(yōu)先級來調(diào)度運(yùn)算符,盡量使高選擇率的運(yùn)算符優(yōu)先,這樣可以減少內(nèi)存占用,但它的問題是沒有考慮路徑中運(yùn)算符之間的位置關(guān)系,使得輸出延遲很大。例如,假設(shè)有一快速且高選擇率的運(yùn)算符H跟隨在幾個很小選擇率的運(yùn)算符之后,雖然運(yùn)算符H比它前面的運(yùn)算符有更高的優(yōu)先級,然而,在很多時刻里H無法被調(diào)度,因為它的輸入隊列是空的,造成運(yùn)算符的饑餓狀態(tài)。
(4)鏈調(diào)度(chain):是在貪心算法的基礎(chǔ)上考慮了運(yùn)算符的位置關(guān)系,解決了具有高優(yōu)先級的運(yùn)算符的饑餓問題。但鏈調(diào)度只是單獨關(guān)注如何最小化運(yùn)行時內(nèi)存的最大使用量,忽略了輸出延遲這一重要方面。在輸入數(shù)據(jù)流爆發(fā)期間,鏈表要遭受元組的饑餓,即鏈表更喜歡操作那些落在低包絡(luò)線上最大斜率段的新元組,而忽略了系統(tǒng)中落在不太陡峭斜率段的更早的元組,從而導(dǎo)致這些元組的高延遲。雖然最小化運(yùn)行時內(nèi)存的使用量是很重要的,但許多數(shù)據(jù)流應(yīng)用系統(tǒng)也要求對輸入流的響應(yīng)時間應(yīng)在指定的時間間隔內(nèi)。
(5)基于Eddy的調(diào)度: 使用的調(diào)度規(guī)則類似于STREAM系統(tǒng)中的貪心調(diào)度,但是,Eddy調(diào)度的是元組,而不是運(yùn)算符的執(zhí)行。數(shù)據(jù)進(jìn)入Eddy,Eddy發(fā)送元組到運(yùn)算符,運(yùn)算符作為一個獨立的線程而執(zhí)行,其結(jié)果再返回給Eddy,元組被所有運(yùn)算符處理后,Eddy將其輸出。Eddy的目的是最大化吞吐量,不像STREAM關(guān)心的是隊列的大小。
(6) 多級調(diào)度: 在Aurora系統(tǒng)中,若干個box組合成一個superbox作為調(diào)度和執(zhí)行的基本單元。系統(tǒng)采用兩級調(diào)度,第一級調(diào)度決定哪些superbox被調(diào)度,第二級調(diào)度決定superbox內(nèi)部box的執(zhí)行次序。第一級調(diào)度有靜態(tài)調(diào)度和動態(tài)調(diào)度兩種,目前以靜態(tài)調(diào)度為主,可以通過各種調(diào)度算法(如round-robin)來實現(xiàn)。第二級調(diào)度采用三種調(diào)度策略:基于最大吞吐量的調(diào)度、基于最小延遲的調(diào)度和基于最小內(nèi)存消耗的調(diào)度。在Aurora系統(tǒng)中,由于大規(guī)模、高動態(tài)的系統(tǒng)特征和調(diào)度的粒度等方面因素,尋找最優(yōu)的調(diào)度方法是十分困難的,因此啟發(fā)式方法常常是很有效的。
(7)其他算法: Q.Jiang和S.Chakravarthy提出了一種基于算子路徑的進(jìn)度安排策略PCS(path capacity scheduling),通過為具有最大能力處理的路徑安排進(jìn)度的方式來達(dá)到最小化響應(yīng)時間的目的,進(jìn)而提出了segment scheduling策略,通過將算子路徑分解為若干片斷,在處理占用空間控制方面取得了較好的效果。
目前針對數(shù)據(jù)流實時任務(wù)調(diào)度算法的研究還不多,因此,參考傳統(tǒng)實時系統(tǒng)中單調(diào)速率(rate monotonic,RM)、截止期最早最優(yōu)先(earliest deadline first,EDF)、空閑時間最短最優(yōu)先(least slack first,LSF)、最早放行最優(yōu)先、可達(dá)截止期最早最優(yōu)先、價值最高最優(yōu)先(highest value first,HVF)、價值密度最大最優(yōu)先(highest value density first,HVDF)等調(diào)度策略算法,結(jié)合數(shù)據(jù)流負(fù)載模型以及連續(xù)查詢優(yōu)化技術(shù)、過載調(diào)整技術(shù),設(shè)計支持QoS最大化的實時任務(wù)調(diào)度算法是數(shù)據(jù)流調(diào)度算法研究的方向之一。