基于流行程度的ia64間隔緩存策略

基于流行程度的ia64間隔緩存策略

1存儲優(yōu)化技術隨著計算、存儲和通信等技術的發(fā)展，大規(guī)模媒體服務得到了廣泛應用于娛樂、教育、經(jīng)濟等領域的廣泛應用。對于具有實際價值的基于數(shù)據(jù)傳輸方式的流媒體服務系統(tǒng)來說，無論采用何種類型的數(shù)據(jù)傳輸方式，提高媒體服務器的性能，支持更多的連續(xù)用戶，并提供更好的服務，都是一個非常重要的問題。在國內(nèi)外發(fā)表了許多研究活動，如分布式并行服務器結構、存儲子系統(tǒng)的設計、p2p技術的應用、可靠的傳輸、訪問控制策略等。在這些改進服務器性能的技術中，堆棧管理技術發(fā)揮著非常重要的作用。即使在廣泛使用的分布式系統(tǒng)中，單服務器緩沖區(qū)管理在整個系統(tǒng)的性能中也起著重要作用。2沖突存儲的間隔存儲策略目前,已有很多的商用流媒體服務器,包括Darwin,RealServer,WindowsMediaServer等,此外,也有很多試驗性流媒體系統(tǒng)以及包括Berkeley連續(xù)媒體工具、Dali多媒體軟件庫、GStreamer、LiveCast等流媒體系統(tǒng)開發(fā)工具.流媒體的緩存管理問題,則往往從實際系統(tǒng)中剝離開來,把這些工作交給RealProxy,DarwinStreamingProxy,WindowsMediaProxy這些專門的緩存應用來實現(xiàn),而現(xiàn)存的多種緩存算法在其中都可得到應用.在緩存算法調度方面,傳統(tǒng)的LRU等緩存調度算法依據(jù)的是數(shù)據(jù)訪問中的時間局部性原理,且在管理離散數(shù)據(jù)時能夠達到較好的性能.但在流媒體服務系統(tǒng)中影片的數(shù)據(jù)量通常很大,用戶的行為一般是順序訪問,時間局部性不強,因此LRU等算法的命中率并不高.文獻[14,15,16,17,18,19,20]提出了幾種不同的緩存管理策略.其中間隔緩存策略是一種目前得到廣泛認可的算法,它能夠有效地處理并發(fā)用戶對視頻流的訪問,很多的工作也是在其基礎上進行改進.除此之外還有用來處理VCR操作的混合型緩存管理算法等等.然而已有的各種算法通常沒有考慮媒體對象流行程度的特點,將最“熱門”和最“冷門”的媒體對象同等對待,致使緩存利用率受到了影響.而且由于傳統(tǒng)的32位機中內(nèi)存的數(shù)量極其有限,因此以往很多工作都把精力放在減小總緩存數(shù)量上,這更從根本上限制了緩存利用率的提高.為了解決這一問題,本文提出了基于流行程度的間隔緩存策略.本文將詳細介紹該算法的實現(xiàn),并對其性能進行理論分析和模擬驗證.3采用流行的間隔緩沖策略pic及其性能分析模式3.1并發(fā)流數(shù)的季節(jié)變化為了更好地理解實際流媒體點播系統(tǒng)中的用戶行為特征,有針對性地設計緩存調度策略,本文對一個實際商業(yè)流媒體點播系統(tǒng)中的用戶日志做了統(tǒng)計和分析.該數(shù)據(jù)庫共有4951部影片,長度從30～120min不等;在本文的研究中截取了起止時間為2004年1月13日開始共45天的數(shù)據(jù),這段時間系統(tǒng)總共處理了3487672條有效的用戶請求.分析發(fā)現(xiàn),系統(tǒng)中的并發(fā)流數(shù)隨著時間很有規(guī)律的改變.圖1顯示了2004年2月2日每小時的用戶數(shù)的變化,其余每天的變化情況與之非常相似.每天并發(fā)用戶數(shù)的最小值出現(xiàn)在7∶00～9∶00之間,而最大值出現(xiàn)在21∶00左右.每天的最大用戶數(shù)約為7000,其中周一略低于平均值,而周日略高.影片的流行程度也顯示出一定的規(guī)律性.最流行的影片基本是固定的,如圖2所示,點播率在top10100的影片的改變很緩慢,其中top10的變化率平均約為每小時2部影片.此外,在同一時刻,系統(tǒng)中所有用戶的點播行為呈現(xiàn)出明顯的傾斜,例如最熱門的10部影片的點播數(shù)約占點播總數(shù)的15%～20%,而影片數(shù)只占總影片數(shù)的0.2%.3.2系統(tǒng)的傾斜技術由第3.1節(jié)的分析可知,流媒體點播系統(tǒng)中的用戶行為有著明顯的傾斜性,熱門影片被點播的概率遠遠高于它們的影片數(shù)的比例.因此一種合理的做法就是在緩存分配上同樣向這些影片傾斜,從而提高被緩存的用戶數(shù),增加系統(tǒng)的吞吐量.對于IA-64系統(tǒng)來說,一個極端的情況就是可將某些影片的數(shù)據(jù)全部緩存起來.由此出發(fā),本文將整個內(nèi)存分為兩部分:一部分采用經(jīng)典的Interval算法進行管理;而另一部分保存最流行的幾部影片的全部數(shù)據(jù).系統(tǒng)只需定期統(tǒng)計所有影片的點播概率,更新需要保存的影片即可.直觀上看來,如果緩存前10部影片,每部影片長1h,播放速率為384Kbps,那么這一部分總共只需要1687.5MB的緩存空間,但卻至少可以為15%的用戶提供服務.下面給出算法的詳細描述.3.2.1用戶共享關系到所有用戶在介紹PIC算法之前,首先簡單介紹一下算法中需要用到的一些定義:對一部影片moviei,訪問它的所有用戶用Sij順序表示;用戶Sij訪問過的數(shù)據(jù)將被Si(j+1)再次訪問,且在此之前沒有其他用戶訪問這些數(shù)據(jù),稱它們?yōu)橄嗬^流,構成的配對用pairi表示,其中Sij稱為前趨流,Si(j+1)稱為后繼流;pairi被緩存,含義是前趨流訪問過的數(shù)據(jù)塊被緩存,使后繼流可以從緩存得到服務.3.2.2讀取或更換相關文件為前趨的配對(1)在緩存池中,每部影片擁有一個數(shù)據(jù)塊表.該表的每個節(jié)點對應一個數(shù)據(jù)塊,保存指向該塊的指針、塊號、有效性、訪問次數(shù)、訪問時間、訪問狀態(tài)等信息.每個數(shù)據(jù)塊可能處于3種訪問狀態(tài):①該影片為最流行的m部影片之一(記做topm).澤所有數(shù)據(jù)塊都被保存在數(shù)據(jù)塊表中,直到影片退出topm為止.②該影片不屬于topm,但根據(jù)Interval算法,該數(shù)據(jù)塊所屬的配對應該被緩存.因此該塊被保存在數(shù)據(jù)塊表中,直到已經(jīng)被該配對的后繼流讀取,或者該配對需被替換出緩存.③若該數(shù)據(jù)塊所屬的配對不應被緩存,則該塊被前趨流讀取之后就被送回空閑池,后繼流需再次從空閑池獲得一個數(shù)據(jù)塊并從磁盤讀取數(shù)據(jù).(2)為了查找某一用戶的前趨和后繼,每部影片還分配一個用戶表.每個節(jié)點對應一個用戶,保存該用戶當前的訪問位置、緩存狀態(tài)等信息,所有用戶按訪問位置排序.緩存狀態(tài)(readstate)表示以該用戶為前趨的配對能否被緩存:1——可以緩存,該用戶訪問過的數(shù)據(jù)塊全部保留在數(shù)據(jù)塊表中,后繼流從內(nèi)存得到服務;0——不能緩存,該用戶訪問過的數(shù)據(jù)塊將被放回空閑池,后繼流從磁盤獲得數(shù)據(jù).(3)對于不屬于topm的影片,需要一個配對表對它們進行管理.每個節(jié)點對應某一部影片的一個配對,保存所屬影片、前趨指針、后繼指針、配對的位置、間隔大小等信息.所有影片生成的全部配對按照間隔大小進行排序,PIC依次選擇間隔最短的配對進行緩存.(4)PIC還維護一個影片表.其中的每個節(jié)點對應一部正在被點播的影片,保存影片的大小、點播次數(shù)、流行程度等信息,影片的數(shù)據(jù)塊表和用戶表的表頭指針也由該節(jié)點維護.影片的流行程度(popstate)表示影片是否為當前最流行的m部影片:1——在topm中;0——不在topm中.PIC定時統(tǒng)計所有影片的點播數(shù),選出新的topm并更新影片的popstate.(5)最后有一個計時器(freshtimer),表示統(tǒng)計topm的時間間隔.計時器每次超時都需要重新統(tǒng)計最流行的m部影片并進行相應的處理.3.2.3將該影片納入不同的對配對表進行刪除,重新生成配對表計時器超時以后,算法首先從所有被點播的影片中找出原來的topm(popstate=1),再根據(jù)點播次數(shù)統(tǒng)計出新的topm.若某部影片原來不屬于topm而現(xiàn)在屬于,則需要從空閑池中分配空間,把整個文件都讀到它的數(shù)據(jù)塊表中;同時所有訪問該影片的用戶都不再由配對表調度,因此將屬于該影片的配對刪除,使用戶的readstate=1;最后使影片的popstate=1.若某部影片原來屬于topm而現(xiàn)在不屬于,則它的所有用戶需按照訪問位置重新生成配對,加入配對表;再對所有的配對重新進行調度,確定每個用戶的readstate;最后使該影片的popstate=0.3.2.4用戶請求的響應(1)生成配對并修改首先在被點播影片對應的用戶表中生成相應的用戶節(jié)點.若該影片popstate=1,則直接將用戶的readstate置1即可.否則須根據(jù)訪問位置找出對應的前趨和后繼,生成配對并插入配對表.注意若一個用戶Sij既有前趨Sim,又有后繼Sin,則Sim和Sin必然已經(jīng)構成了一個配對,需將其從表中刪除,而后才能插入新的配對.重新檢查所有的配對,依次選擇間隔最小的進行緩存,并修改相應用戶的readstate.(2)數(shù)據(jù)通訊的讀取首先檢查對應影片的數(shù)據(jù)塊表是否有所需數(shù)據(jù),若命中,則只需向用戶發(fā)送數(shù)據(jù)即可,否則需從磁盤將數(shù)據(jù)讀入數(shù)據(jù)塊表.數(shù)據(jù)發(fā)送完以后還需根據(jù)用戶的readstate決定該數(shù)據(jù)塊應保留(readstate=1)還是應放回空閑池(readstate=0).(3)提取配對信息首先檢查被點播影片的popstate,若為1,則直接將用戶節(jié)點從表中刪除即可,同時修改影片的點播數(shù).否則應找出該用戶的前趨和后繼,將相應的配對從配對表中刪除.注意若用戶Sij既有前趨Sim,又有后繼Sin,則結束該用戶以后Sim和Sin必然構成一個新的配對,需將其插入配對表.此外,如果原來的配對是被緩存的,則將所有分配給它的數(shù)據(jù)塊放回空閑池.重新檢查所有配對的緩存狀態(tài)并修改相應用戶的readstate.當有新的用戶請求被接受時,執(zhí)行adduser操作;當用戶結束點播時,執(zhí)行closeuser操作;當用戶順序播放時,則執(zhí)行read操作;而對于所有的VCR操作,簡單起見,只需將它們分解成3種基本操作的組合:首先執(zhí)行closeuser操作,然后將用戶移動到用戶表的正確位置,再執(zhí)行adduser操作,最后執(zhí)行read操作完成數(shù)據(jù)讀取和發(fā)送.可見在該算法中,只有當添加用戶和關閉用戶時需要重新檢查緩存狀態(tài)、分配或者回收內(nèi)存.3.2.5把大量的閑置塊作為pairj.對于那些不屬于topm的影片,需要根據(jù)配對表決定哪些數(shù)據(jù)可以被緩存.按照間隔由小到大的順序遍歷配對表,找到第1個未被緩存的節(jié)點,記做pairi.如果有足夠的空閑塊,則直接給對應影片的數(shù)據(jù)塊表分配所需的數(shù)量.如果空閑空間不足,則再按照間隔由大到小的順序遍歷配對表,找到第1個被緩存的節(jié)點,記做pairj.若pairj的間隔大于pairi,則不再緩存pairj,將數(shù)據(jù)塊分配給pairi,多余的塊放回空閑池;否則pairi不能被緩存,進而間隔大于pairi的配對都不能被緩存.若某個配對的緩存狀態(tài)已被改變,則需修改其前趨用戶的readstate.3.3mt部影片的sd可達性為了比較準確地分析PIC的性能,本文在文獻的基礎上提出了一個針對PIC的性能分析數(shù)學模型.假設該模型中共有M部影片,每部均為D分鐘,播放速率均為r(MBps).用戶請求的到達模式是Poisson過程,平均到達速率為λ.因此相鄰用戶的時間間隔服從指數(shù)分布,數(shù)學期望為T=1λ.影片的點播模式仍然用Zipf分布來近似,因此第i部影片的點播概率為Pi=C?i(1-θ),其中C為常數(shù),θ為傾斜因子.令最熱門的m部影片被全部緩存,而其他影片由經(jīng)典的Interval算法進行調度.當m=0時,PIC退化為Interval算法.系統(tǒng)中的并發(fā)流數(shù)為NS,那么相鄰用戶的時間間隔的平均值T=D?NS.間隔上限L表示所有長度小于等于L的配對都被緩存,而其他配對不能被緩存.顯然L必須為數(shù)據(jù)塊大小的整數(shù)倍.令數(shù)據(jù)塊為b(MB),則L=l×b,其中l(wèi)是非負整數(shù).假設磁盤的平均數(shù)據(jù)定位時間為Tseek(s),磁盤到緩存的數(shù)據(jù)塊傳輸時間為Tdata(s).因此總的讀數(shù)據(jù)時間為Tsev=Tseek+Tdata.令磁盤帶寬為B(MBps),則Tdata=b?B,Tsev=Tseek+b?B.由于整個系統(tǒng)中的相鄰用戶到達間隔服從指數(shù)分布,因此訪問某個影片i的相鄰用戶到達間隔也服從指數(shù)分布,數(shù)學期望為ti(因此λi=1ti),且ti=ΤΡi.(1)ti=TPi.(1)對于由Interval調度的影片i(m<i≤M),若它的兩個相繼流構成一個配對,則這兩個流的間隔X必須小于等于影片長度D.由于X的概率密度是fi(x)(fi(x)=λieλix),概率分布函數(shù)為Fi(x),因此X<D的概率為fi(x)Fi(D),(2)fi(x)Fi(D),(2)同時影片i的一個配對的間隔大小的期望值為EΙi=1Fi(D)D∫0xfi(x)dx.(3)EIi=1Fi(D)∫0Dxfi(x)dx.(3)從而緩存影片i的一個配對所需緩存大小的期望值為Ri=-(EΙi×r)?b-×b?(4)Ri=?(EIi×r)?b?×b?(4)注意Ri應該是塊大小b的整數(shù)倍.又由到達間隔的分布知,緩存影片i的一個配對所需的緩存大小K也是指數(shù)分布,期望值即Ri.令K的概率密度為gi(k)(gi(k)=1Rie-1Rik),概率分布為Gi(k),則b≤K≤L的概率為gi(k)Gi(L)-Gi(b),(5)gi(k)Gi(L)?Gi(b),(5)被緩存的配對所需空間大小的期望值為Ιi=1Gi(L)-Gi(b)L∫bkgi(k)dk.(6)注意,由于引入了間隔上限L,影片i的一個配對的Ii值并不等于EIi.在這里,L是一個未知量,需要通過該模型計算它的值.由于系統(tǒng)中的并發(fā)流數(shù)為NS,影片i的點播概率為Pi,因此點播影片i的并發(fā)流數(shù)為NS×Pi,這也就是形成的配對總數(shù)(假設最后一個用戶與影片末尾的假想用戶形成配對).對于最熱門的m部影片,所有NS×Pi個流都被緩存,所需空間大小即為影片大小.而對于其他影片,一個配對被緩存(即b≤K≤L)的概率為Gi(L)-Gi(b).因此影片i被緩存的流數(shù)(當m<i≤M)也就是被緩存的配對數(shù)為Νi={ΝS×Ρi,1≤i≤m?ΝS×Ρi(Gi(l×b)-Gi(b)),m＜i≤Μ.(7)影片i占用的緩存總數(shù)為{r×D,1≤i≤mΝi×Ιi,m＜i≤Μ.(8)由于系統(tǒng)中共有M部影片且緩存大小固定,所以有CacheSize≥m∑i=1r×D+Μ∑i=m+1Νi×Ιi=m×r×D+ΝS×Μ∑i=m+1(Ρi×l×b∫bkgi(k)dk).(9)此時可以從式(9)得到L的值.而總的被緩存流數(shù)為Μ∑i=1Νi.(10)命中率為hit-ratio=Μ∑i=1ΝiΝS.(11)點播過程中為了保證數(shù)據(jù)的連續(xù)性,當一個數(shù)據(jù)塊開始播放時就發(fā)出對下一個數(shù)據(jù)塊的請求.令Tmax表示從請求發(fā)出到數(shù)據(jù)建立可以允許的最大間隔,顯然Tmax就是一個工作循環(huán),即Tmax=roundsize=b?r.從式(11)知從磁盤得到服務的流數(shù)為NS(1-hitratio),而每個流的數(shù)據(jù)讀取時間為Tsev.因此為了使用戶點播不出現(xiàn)中斷,必須滿足NS(1-hitratio)Tsev≤Tmax,即ΝS(1-hit-ratio)(Τseek+b?B)≤b?r.(12)在求出L的值以后,還必須通過式(12)來驗證它的合理性.3.4系統(tǒng)參數(shù)分析根據(jù)前面的性能分析模型,我們可對PIC算法的各個參數(shù)進行細致的分析,找出影響算法性能的關鍵因素,從而為流媒體點播系統(tǒng)的設計人員提供性能參考,在此次分析中的系統(tǒng)參數(shù)如表1所示:3.4.1pic性能分析大內(nèi)存是64位系統(tǒng)的優(yōu)勢之一,也是本文研究緩存調度算法的出發(fā)點之一.令緩存從1GB增加到32GB,根據(jù)PIC性能分析模型可計算在該值一定的情況下Cache命中率的情況.由圖3可以看出,系統(tǒng)可以支持的最大并發(fā)流數(shù)隨緩存的增加而迅速增加.同時可以看出在大規(guī)模流媒體點播系統(tǒng)中,若緩存空間過小,則PIC無法達到很好的效果.這項分析可以幫助設計人員計算增加內(nèi)存的成本與收益之比,以確定每個流的平均費用和最佳的配置.3.4.2緩沖的特性分析首先固定被全部緩存的影片數(shù)m,計算系統(tǒng)可以支持的最大并發(fā)流數(shù)和對應的命中率,進而得到二者的函數(shù)曲線,如圖4所示,橫軸為全部緩存的影片數(shù)m.可以看出緩存性能在m從0增加到5時變化很大,而m繼續(xù)增大時算法的性能有一定的波動,在m=25左右達到峰值,再增大m,性能反而有所下降.這是因為m實際上代表了PIC中兩部分緩存的劃分比例,當m太大時,Interval算法調度的部分過小,使這一部分的命中率下降較大,因此導致整體性能的下降,從而使得整個性能呈現(xiàn)鋸齒形.3.5算法的模擬驗證為了檢驗改進后的算法在實際系統(tǒng)中的性能,我們建立了一個VOD服務器緩存管理的模擬環(huán)境,對本算法進行了進一步的實驗和分析.(1)雙1.5ghs監(jiān)控系統(tǒng)環(huán)境測試環(huán)境為一臺ItaniumⅡ服務器,雙1.5GHzCPU,平均磁盤傳輸速率約為160Mbps,物理內(nèi)存為16GB,64位Linux操作系統(tǒng).(2)disk發(fā)揮數(shù)據(jù)請求和存儲功能模擬服務器的系統(tǒng)結構可用圖5表示,其中的箭頭方向反映了媒體數(shù)據(jù)的傳輸方向,用戶與服務器、服務器各個模塊之間的命令傳輸忽略不計.該服務器由3個主要的管理模塊組成:ServiceManager模塊負責與用戶的通信,它從MemoryManager模塊獲得需要的媒體數(shù)據(jù)并按照穩(wěn)定的速率傳送給用戶;MemoryManager模塊負責管理緩存,當收到ServiceManager的數(shù)據(jù)請求時,它首先檢查緩存是否命中,命中則直接將數(shù)據(jù)傳輸給ServiceManager,否則向DiskManager發(fā)出數(shù)據(jù)請求,并將返回的數(shù)據(jù)同時送ServiceManager和緩存;DiskManager模塊管理硬盤數(shù)據(jù)的存放、查詢和讀取,除了為MemoryManager提供媒體數(shù)據(jù)之外還要提供影片的屬性如長度、編碼格式等信息.這里假設服務器與用戶之間的高速網(wǎng)絡能夠滿足所有的數(shù)據(jù)傳輸要求;此外與ms級的磁盤傳輸時間相比,緩存的數(shù)據(jù)傳輸時間通常是ns級,因此可以忽略不計.為使測試更加接近真實情況,測試數(shù)據(jù)全部從第3.1節(jié)中所描述的實際VOD系統(tǒng)數(shù)據(jù)庫中獲得,而沒有采用常用的Possion分布和Zipf分布假設.實際測試時共選擇了3組測試用例,分別是2004-01-19(Mon)至2004-01-25(Sun)期間、2004-02-01(Sun)至2004-02-08(Sun)期間以及2004-02-09(Mon)至2004-02-15(Sun)期間,總共3周的用戶記錄.其中1月22日為中國的春節(jié),2月14日為情人節(jié),因此這兩周的用戶行為帶有一定的特殊性,2月1日至2月8日覆蓋了普通的一周,較有代表性.以2月1日為例,當天共有80909次用戶訪問,發(fā)生了約200萬次讀操作.(3)把其加入空塊及散發(fā)塊在具體實現(xiàn)改進算法時,本著充分利用大內(nèi)存優(yōu)勢的目的,在算法中引入了拖后寫策略.該策略在系統(tǒng)中維護一個空閑塊隊列,對于不能被緩存的流,當讀完一個數(shù)據(jù)塊之后,并不立即釋放,而是將其放入空閑塊隊列末尾;而當一個流需要被緩存時,首先從空閑隊列頭部取得緩存空間.這樣位于隊列末尾的塊就有可能在換出內(nèi)存前再次被訪問.實際上在經(jīng)典的Interval算法中也可采用該策略,但由于物理內(nèi)存較小,空閑塊很快會被用盡,因此一個數(shù)據(jù)塊在替換之前被再次訪問的概率很小,這種策略實際上不能發(fā)揮太大的作用.但在大內(nèi)存的情況下,特別是在系統(tǒng)剛剛啟動的一段時間內(nèi),空閑隊列很長,隊尾的數(shù)據(jù)塊被重復讀取的可能性就大得多,可以充分發(fā)揮這種策略的優(yōu)勢.(4)che中性情況經(jīng)過實際測試,我們發(fā)現(xiàn),在本測試中所用的3組測試用例都表現(xiàn)出相近的結果,我們以2月1日至8日這一組的結果為例對結果進行分析.在測試中,我們每5min計算一次并發(fā)用戶數(shù)NS,結果如圖6所示.可看到,NS的變化很有規(guī)律,最大值在2000左右,出現(xiàn)的時間在晚上9點左右,最小值則小于10,出現(xiàn)在早上7,8點鐘.而對于Cache命中率,我們也是每隔5