用于云存儲數據服務器的I/O請求調度算法

李　宇

(北京交通大學軟件學院, 北京 100044)

在大數據時代,人們日常會產生大量的數據(如視頻、照片、個人狀態等),以Facebook為例,其每天存儲三億張用戶上傳的照片[1].為了吸引用戶,國內外互聯網公司紛紛推出相應的云存儲產品,如Dropbox[2]、百度云網盤[3]、騰訊微云[4]、360云盤[5]等.在云存儲應用環境中,用戶的數據(如視頻、語音、圖片、文字等)集中存放在分布式文件系統(distributed file system, DFS)中,用戶通過瀏覽器/云存儲客戶端向應用服務器發送數據請求,由應用服務器連接DFS來獲取數據并返回給用戶在上述應用環境中,用戶的數據請求具有以下特點:一方面,云存儲的用戶量非常龐大,數據服務器會收到大量的并發I/O請求;另一方面,不同類型I/O請求的發送頻率和對響應時間的要求也不盡相同(如在線播放視頻和瀏覽圖片時,對端到端的延遲和數據傳輸帶寬的要求有很大差別).

目前，在云計算存儲環境下的I/O調度相關研究主要集中在虛擬機資源的合理調度上.同時考慮能耗和負載的虛機調度算法[6],允許虛機重新聲明CPU片段供使用.面向云存儲的I/O資源效用優化調度算法[7]通過服務水平目標,采用最早截止時間優先算法或者預計效益來提高總收益率.動態優先級排序[8]基于多屬性決策理論,以離差最大化方法計算I/O任務的優先級評估屬性權重并綜合評估,將虛擬域的差異體現在虛擬機的I/O調度上.

當前常用DFS(如Ceph[9]、GlusterFS[10]、HDFS[11]等)的設計關注點均在如何高效地存儲和查詢元數據、如何把數據均勻地分散到不同的數據服務器,以及數據的可靠性等方面,對數據服務器守護進程(data server daemon, DSD)的I/O請求調度并沒有進行特別的設計,采用的是先來先服務(first in first out, FIFO)策略,將所有并發請求同等對待,以盡力而為(best effort)的方式順序處理.這種調度策略側重于減小開銷和有效利用網絡帶寬,能夠提高系統整體的平均響應時間.然而,它并未考慮不同類型I/O請求的時效性要求,使得需要實時響應的I/O請求(如在線視頻播放)和普通I/O請求(如圖片瀏覽)一同排隊等待,前者可能會被阻塞相當長的時間而無法得到及時處理,從而導致整個系統服務質量降低.

針對上述問題,本文提出一種用于DSD基于優先級的周期性調度算法(priority-based periodic scheduling algorithm, PPSA).PPSA首先對來自客戶端的I/O請求進行分類,并賦予不同的優先級;然后以合適的時長作為周期,以分時間片的方式對不同優先級的I/O請求進行周期性的調度.PPSA在保障實時請求響應性能的同時,也兼顧了其他優先級請求的響應性能.

1　算法概述

當前主流的云存儲應用環境中,用戶使用數據的方式基本都是“一次寫、多次讀”(write once, read everywhere)模式:用戶上傳的文件或者分享給別的用戶,或者是對已有數據的備份,只有很小部分文件在上傳之后會被修改[12].因此,本文主要研究DFS中數據服務器讀I/O請求的調度問題,寫I/O請求仍采用原來的調度方式.后文如無特別說明,所有出現的I/O請求均指讀I/O請求.

1.1　工作原理

PPSA的工作原理見圖1,它工作在DFS的DSD內.客戶端收到上層應用發出的I/O請求后,通過網絡將其發送到存儲相應數據的服務器DSD緩沖隊列中;之后,分類器根據分類配置文件對I/O請求進行分類,并把分類后的I/O請求放入對應優先級的請求隊列;最后由調度器統一進行調度.

圖1　PPSA工作原理Fig.1　Working principle of PPSA

1.2　I/O請求分類

在云存儲應用環境中,用戶的數據請求最終由應用服務器進行處理,而應用服務器則通過訪問DFS中的數據服務器來獲取用戶需要的數據,并將其傳回給用戶.根據當前主流云存儲系統的業務類型,可以把應用服務器發出的I/O請求分為如下4類:

(1) 實時I/O請求:通常為在線視頻/音頻播放類I/O請求.這類請求可對應于實時可變比特率(real-time variable bit rate, rt-VBR)類[13],其生成和發送具有突發性和一定的連續性,要求最小的延遲和一定范圍內的傳輸帶寬保證,用符號t0表示;

(2) 非實時I/O請求:通常為文件瀏覽類(如在線瀏覽圖片、文檔等)I/O請求.這類請求可對應于非實時可變比特率(non-real-time variable bit rate, nrt-VBR)類,允許一定程度的數據響應延遲,用符號t1表示;

(3) 下載I/O請求:通常為數據下載類I/O請求.這類請求可對應于不指明比特率(unspecified bit rate, UBR)類,對傳輸帶寬和延遲沒有要求,可采用“盡力而為”的方式提供服務,用符號t2表示;

(4) 預取I/O請求:為提高系統I/O性能,可通過對歷史訪問信息的分析,由DFS客戶端預測未來的I/O請求并進行預取操作[14].這類請求對應于可用比特率(available bit rate, ABR)類[15],對傳輸帶寬和延遲沒有要求,且不要求一定被處理.這類I/O請求可在系統空閑時進行處理,若系統負載較重,在一定期限內未得到處理,則可直接丟棄,用符號t3表示.

在云存儲應用環境中,可采用專一功能的應用服務器/集群來處理不同類型的用戶數據請求(如視頻播放服務器/集群、文件服務器/集群、下載服務器/集群).因此,可以通過分類配置文件來配置與應用服務器/集群相對應的I/O請求類別.此外,在該配置文件中還可以配置不同I/O請求類型的其他要求(如在線視頻播放時所要求的最小傳輸帶寬、最大傳輸延遲等),以便分類器對I/O請求進行更加精確的分類.

對于預取請求,由DFS客戶端在發送請求時設置一個PREFETCH標志,PPSA分類器可根據該標志識別出這類I/O請求.

1.3　算法參數

在PPSA中,來自DFS客戶端的I/O請求經分類器后進入4個不同的請求隊列(隊列0～3).其中,隊列0中的I/O請求均為實時請求(t0類),隊列1中的I/O請求均為非實時請求(t1類),以此類推.這4個隊列的優先級分別為Pri0、Pri1、Pri2和Pri3,則有Pri0>Pri1>Pri2>Pri3.

對I/O請求進行基于優先級的調度時,高優先級隊列中的請求應當優先處理.但若嚴格按照優先級的大小順序來進行處理,在有大量突發高優先級請求的情況下,低優先級的I/O請求可能會長時間等待,甚至發生超時.基于公平性的考慮,PPSA中的I/O請求處理采用一種周期性的調度策略——選取一個適當長度的時間段T作為調度周期,并把每個周期分為4個時間段:實時請求處理階段、非實時請求處理階段、下載請求處理階段和預取請求處理階段,各時間段內的時間片優先用于處理對應類型的I/O請求.在一個調度周期內,把實時請求、非實時請求、下載請求和預取請求對應的時間段時長分別記為Trt、Tnrt、Tdld和Tpre,如圖2所示,其計算方法如式(1)～(4).

(1)

Tnrt=(T-Trt-Tpre)β,

(2)

Tdld=(T-Trt-Tpre)(1-β),

(3)

Tpre=Tσ,

(4)

式中:vi為調度周期T內的實時請求對應的DFS客戶端與DSD之間的一條I/O流所需的傳輸帶寬,則∑vi表示一個調度周期T內所有實時I/O流所需的傳輸帶寬之和;V為DS的總網絡傳輸帶寬;α為調節因子,以確保預留的時間片能夠滿足所有實時請求的需求;β為調節因子,用于平衡非實時請求和下載請求的處理時長;σ為比例系數,可由用戶自行設定.

圖2　周期性調度示意Fig.2　Periodic scheduling process

1.4　數據結構

對PPSA來說,請求隊列中I/O請求的組織是影響算法性能的一個重要因素,因此,必須對這些請求進行有效的組織和管理.由于所有I/O請求的目標均是數據服務器(DS)上的文件,所以,可以I/O請求的目標文件為依據來組織它們.

PPSA的每個請求隊列中I/O請求的組織方式如圖3所示.其中,哈希表存放的是DS上文件的全路徑與請求列表的映射,格式為:.每一個進入隊列的請求,根據其目標文件在DS上全路徑的哈希值被插入相應請求隊列的隊尾.

圖3　請求隊列數據結構Fig.3　Data structure of a request queue

為了提高效率,PPSA還對哈希表中每個隊列內的所有請求建立了一棵紅黑樹,并以每個請求數據在其目標文件內的偏移量作為關鍵字.由于紅黑樹中不同節點的關鍵字必須不同,所以,對于偏移量相同的I/O請求,在樹的相應節點中使用不同的指針指向對應的請求即可.

2　算法流程

PPSA在一個調度周期T內為各類I/O請求分配時間片配額,配額內的時間片優先用于處理對應類型的I/O請求.在同一時刻如果有多類請求滿足調度條件,則根據其優先級的高低來依次處理實時請求、非實時請求和下載請求.在調度周期內如果某類I/O請求的時間片配額有剩余,則剩余的時間片可被其他種類的I/O請求按優先級從高到低的順序來使用.在前三類請求均處理完畢后,若仍有空閑時間片,則進行預取請求的處理.

PPSA優先考慮高優先級請求的響應性能,同時,通過時間片資源的預分配,可有效保障其他種類I/O請求所需的數據傳輸帶寬.PPSA的處理流程如下:

Algorithm PPSA

Output:時間片配額分配

Begin

loop

統計當前所有I/O流的傳輸帶寬之和∑vi

步驟1基于時間片配額處理取請求

/*一個調度周期即為一個統計窗口*/

更新一個統計窗口內隊列Q的相關統計數據,包括:每條實時I/O請求流成功傳送給目標DFS客戶端的數據總量Rrti

callhandle_Q(非實時請求隊列Q(t1),Tnrt)

更新一個統計窗口內隊列Q的相關統計數據,包括:隊列Q成功傳送給所有DFS客戶端的數據總量Rnrt

callhandle_Q(下載請求隊列Q(t2),Tdld)

更新一個統計窗口內隊列Q的相關統計數據,包括:隊列Q成功傳送給所有DFS客戶端的數據總量Rdld

步驟2基于優先級處理請求

/*分別計算當前調度周期內剩余的時間片Trt、Tnrt和Tdld的長度.按優先級從高到低進行處理*/

for eachQin {Q(t0),Q(t1),Q(t2)}; do

callhandle_Q(Q,trest)

end for

步驟3處理預取請求

callhandle_Q(Q(t3),trest)

/*采用bestjofk策略(j=8,k=10)預測I/O請求的未來趨勢,并根據預測結果來調節算法參數.之前對Tnrt、Tdld和Tpre的值進行了修改*/

根據式(2)～(4)重新計算Tnrt、Tdld和Tpre

Unrt←Rnrt/(TnrtV)

/*對最近10個統計窗口的8個,當Unrt超過100%或小于90%時,對參數β做正或負0.1的修正,對參數α做正或負0.05的修正*/

Udld←Rdld/(TdldV)

/*對最近10個統計窗口的8個,當Udld超過100%或者小于90%時,對參數β做負或正0.1的修正,對參數α做負或正0.05的修正*/

/*設置參數邊界為0.10和0.90*/

/*設置參數邊界為0.05和0.30*/

end loop

End

Algorithmhandle_Q

Input:請求隊列Q,Q對應的處理時長為Tq

Output:隊列Q相關的統計數據

Begin

if隊列Q非空 andTq>0 then

N←隊列Q哈希表的大小

for 隊列Q哈希表中的每文件file; do

/*時間片用完則返回,計算分配給每個目標文件的處理時長*/

t←Tq/N

pre_offset←上一次訪問的file的offset

ifpre_offset<0 orpre_offset>file對應的紅黑樹中的最大offsetthen

pre_offset←0

end if

whilet>0 do

req←file對應的紅黑樹中offset≥pre_offset且offset最小的請求

ifreq為預取請求andreq的等待時間超過設定的閾值 then

丟棄請求req

else

處理請求req

t←t—處理req的時間

Tq←Tq—處理req的時間

pre_offsetreq的offset

end if

end while

記錄file的pre_offset屬性

end for

end if

End

3　實驗及結果分析

為了檢驗PPSA的性能,使用PFSsim[16]進行了仿真實驗.PFSsim是一款基于OMNeT++[17]和DiskSim[18]的DFS仿真器,它是跟蹤驅動(trace-driven)的,主要用來測試和驗證DFS的I/O管理策略和一些新的設計思想.

PFSsim模擬的DFS的配置為1個元數據服務器和4個數據服務器(DS).設置DS的內存容量為8 GB,其本地文件系統(包括緩存)使用的內存為6.4 GB,緩存策略為LRU (least recently used );根據Linux的默認臟數據率(dirty_ratio,默認為內存大小的40%),設置最大臟數據大小為3.2 GB;頁面/塊大小均設置為4 KB;硬盤的訪問速度則根據真實的測量結果來設定(被測服務器配置8 GB內存,8塊15 000轉SAS硬盤組成RAID5陣列).客戶端和數據/元數據服務器之間的網絡帶寬設置為1 Gbit/s,網絡延遲為0.2 ms.

實驗中使用的工作負載特性為實時請求(t0類)和下載請求(t2類)的分布均為均勻分布,非實時請求(t1類)和預取請求(t3類)的分布均為泊松分布.

在實驗中,每個請求流由PFSsim中的一個客戶端組件來處理,每個請求所需的數據大小均為128 KB.t1類請求的平均到達速率為每秒2個請求,t2/t3類請求的平均到達速率為每秒1個請求.所有I/O請求均為同步讀請求,DFS客戶端收到一個請求的響應后,才會發送下一個請求.PPSA的調度周期為50 ms.

3.1　響應時間

該實驗用于測試在不同的系統負荷條件下,分別采用FIFO和PPSA方式進行調度時,系統對不同類型請求的響應時間.實驗設定了2種不同的負載環境,分別為

(1) 輕負載環境:每個DSD均接受20個t0類請求流(每個請求流要求的最小數據傳輸速度均為5 Mbit/s),50個t1類請求流,100個t2類請求流和50個t3類請求流.

(2) 重負載環境:每個DSD均接受20個t0類請求流(每個請求流要求的最小數據傳輸速度均為10 Mbit/s),200個t1類請求流,100個t2類請求流和50個t3類請求流.

實驗記錄了進入平穩狀態后,分別采用FIFO調度策略和PPSA調度策略時,DSD對不同類型I/O請求的響應時間.

從圖4中可以看出,在輕負載環境下,采用PPSA調度方式時,t0類請求和t1類請求的響應速度比FIFO調度策略有提高(前者t0類請求和t1類請求的平均響應時間分別為1 981 μs和2 000 μs,后者對應類型請求的平均響應時間分別為2 005 μs和2 008 μs),但差別不大.

在重負載環境下,采用PPSA調度方式時,t0類請求的響應時間相比FIFO調度方式有較大降低(前者平均值為2 045 μs,后者平均值為2 201 μs);而t1類請求的響應時間相比FIFO調度方式有所降低,但差別不是很大(前者平均值為2 152 μs,后者平均值為2 196 μs)

由于系統對每個I/O請求的響應時間包含了數據在網絡上的傳輸時間(約1 000 μs)和網絡延遲(400 μs),所以,采用PPSA調度方式,在重負載情況下DSD對實時請求的響應速度提高了20%左右,而對非實時請求的響應速度也有一定的提升.當然,這種性能提升是以低優先級請求響應性能的降低為代價的,可以通過調節算法的參數來對不同優先級的請求進行平衡.

(a) 輕負載循環下t0類I/O請求(b) 輕負載循環下t1類I/O請求(c) 重負載循環下t0類I/O請求(d) 重負載循環下t1類I/O請求圖4 不同調度策略的系統響應時間比較Fig.4 Comparison of system response times for different scheduling policies

3.2　平均等待隊列長度

該實驗用于比較DSD采用不同的調度算法時,系統在不同負荷下對各類請求的響應情況.統計各類請求的平均等待隊列長度和最大等待隊列長度,并將統計結果與FIFO算法及多隊列優先級調度算法相比較.實驗中,t0類請求流要求的最小數據傳輸速度均為5 Mbit/s.

表1為其他類型請求負載一定的條件下,t0類請求流的數量對不同類型請求隊列的平均隊列長度的影響.實驗中,t1類請求流的數量為200,t2類請求流的數量為300,t3類請求流的數量為100.從表1中可以看出,采用FIFO調度策略時,所有類型請求的平均等待隊列長度基本相同;這是因為在實驗中設置的條件使響應數據所需的傳輸帶寬超過了網絡帶寬,因此,不管t0類請求流的數量如何增加,系統對所有類型請求的響應性能都沒有變化.

表1　t0類請求流數目對系統響應性能的影響Tab.1　Effect of the number of class t0 request flows on the system response performance

采用優先級調度策略時,隨著t0類請求流數量的增加,系統優先保證高優先級請求的響應性能,但是對低優先級請求的性能不做保證;當t0類請求流的數量增加到100時,所有的t2類請求均無法得到響應.采用PPSA調度策略時,在算法的設定參數范圍內,系統的響應性能與優先級調度策略相當;當t0類請求流的數量增加到80時,由于算法的調節作用,t0類、t1類和t2類請求的響應性能均優于優先級調度策略;當t0類請求流的數量增加到100時,不僅t0類和t1類請求的響應性能有較大提高,而且t2類請求也能夠獲得一定的處理機會.

表2為其他類型請求負載一定的條件下,t1類請求流的數量對系統響應性能的影響.實驗中,t0類請求流的數量為80,t2類請求流的數量為200,t3類請求流的數量為100.從表2中可以得出和表1基本相同的結論,采用FIFO調度策略時,所有類型請求的響應性能基本相同;采用優先級調度策略時,在帶寬資源不夠時會犧牲低優先級請求的響應性能;采用PPSA調度策略時,雖然在帶寬資源不夠時會犧牲一些低優先級請求的響應性能,但算法保證這種性能犧牲不會超過一定的限度.

表2　t1類請求流數目對系統響應性能的影響Tab.2Effect of the number of class t1 request flows on the system response performance

4　結束語

PPSA算法在兼顧公平調度和更短的響應時間上,取得了更好的效果.在云存儲應用環境中,用戶數據一般存儲在DFS中.為了更好地響應不同種類的IO請求,在提高調度效率的同時兼顧不同類型請求調度的公平性,PPSA結合實際應用場景對I/O請求進行分類,并賦予不同的優先級;然后以經驗值為周期,以分時間片的方式對不同優先級的請求進行周期性的調度.仿真實驗結果顯示,PPSA在兼顧公平性的前提下,還能有效降低實時請求的響應時間,可以為云存儲用戶提供更好的使用體驗.