一種多協(xié)議融合的服務(wù)器集群緩存設(shè)計

一種多協(xié)議融合的服務(wù)器集群緩存設(shè)計

1減少了訪問延遲,減輕了網(wǎng)絡(luò)阻塞隨著私家車應(yīng)用的快速普及，世界上的移動網(wǎng)絡(luò)向internet提出了新的要求。解決這個問題的一個重要辦法是緩存用戶訪問過的主頁。緩存的主頁作為一個復(fù)本存放,在下一次訪問時,用戶不必連接到該主頁的駐留網(wǎng)站(originalserver),而是由上一次保留的復(fù)本提供,從而降低了訪問延遲,減輕了Web服務(wù)器負(fù)載,同時釋放了本該占用的網(wǎng)絡(luò)帶寬,改善了網(wǎng)絡(luò)阻塞現(xiàn)象。但性能提高的基礎(chǔ)和前提是正確性,由于高速緩存機(jī)制本身的特點,存在產(chǎn)生錯誤的因素,特別是在服務(wù)器集群等并行計算環(huán)境下,(即cache一致性問題),所以只有解決了高速緩存的一致性問題,才能充分發(fā)揮它的作用。2代理服務(wù)器存儲機(jī)制減少訪問延遲和延遲的實現(xiàn)方法一般說來,Web緩存有3種緩存實現(xiàn)方式,即客戶端、服務(wù)器端以及代理服務(wù)器端緩存機(jī)制?？蛻舳说木彺嫱ǔＪ怯蔀g覽器在用戶本地實現(xiàn)的,如Netscape公司的Navigator和Communicator瀏覽器、Microsoft公司的InternetExplorer瀏覽器都提供了緩存用戶一定時期內(nèi)訪問過的主頁信息的緩存機(jī)制。這種緩存機(jī)制的主要特點是緩存的每個主頁信息長度有限、實現(xiàn)的一致性策略和替換策略都比較簡單,它經(jīng)常提供給用戶的是一些失效了的陳舊信息,因此是一種不大可靠的緩存機(jī)制。服務(wù)器端的緩存機(jī)制是由Web服務(wù)器軟件在服務(wù)器上實現(xiàn)的,通常在服務(wù)器上實現(xiàn)二級或三級cache作為緩存空間,它比存放主頁的硬盤具有更高的訪問速度。當(dāng)服務(wù)器響應(yīng)用戶對某個主頁的訪問請求后,也在緩存空間保留一個復(fù)本,下一次如果有相同的訪問請求,就直接將緩存空間保存的復(fù)本提供給用戶。這種緩存機(jī)制能夠適當(dāng)?shù)亟档驮L問延遲,但是對服務(wù)器的要求較高,增加了服務(wù)器軟件的復(fù)雜度。為了更好地降低延遲,一些服務(wù)器還實現(xiàn)了預(yù)取(pre-fetching)功能。最后一種緩存方式是代理服務(wù)器緩存機(jī)制,這里簡稱為代理緩存。用戶對某個網(wǎng)站的主頁訪問請求到達(dá)代理服務(wù)器后,一旦服務(wù)器存放有該主頁的復(fù)本,服務(wù)器直接提供給用戶作為響應(yīng);如果服務(wù)器沒有該主頁的復(fù)本,則將請求重定向到駐留網(wǎng)站,獲得該主頁給用戶,并且在服務(wù)器上保存一個復(fù)本。這種緩存機(jī)制的工作方式如圖一所示,它具有多個用戶可以共享所有主頁復(fù)本的特點,降低了訪問延遲和費用。同時,由這些代理服務(wù)器提供的緩存服務(wù)還可以連接在一起,構(gòu)成層次型(hierarchy)緩存模型,在Internet緩存協(xié)議(ICP,InternetCacheProtocol)中詳細(xì)描述了這種模型的規(guī)范。典型的代理緩存機(jī)制有Colorado大學(xué)實現(xiàn)的HarvestObjectCache、Netscape公司的NetscapeProxyServer以及在Harvest基礎(chǔ)上NLANR開發(fā)的Squid緩存系統(tǒng)等。比較3種緩存方式,代理緩存機(jī)制是解決WorldWideWeb訪問速度慢、服務(wù)器負(fù)載重和網(wǎng)絡(luò)阻塞等問題的最好辦法。它具有客戶端緩存機(jī)制降低訪問延遲的優(yōu)點,因為通常代理服務(wù)器都是和客戶機(jī)在同一個局域網(wǎng)內(nèi),主頁信息從代理服務(wù)器到達(dá)客戶機(jī)的延遲時間可以忽略不計。其次,因為緩存由專門的代理服務(wù)器實現(xiàn)和維護(hù),緩存機(jī)制可以占用較大的磁盤空間,有利于存放日益增多的大容量多媒體信息。另外,緩存的一致性維護(hù)策略和替換策略可以做得比較復(fù)雜,從而提高命中率(hitrate)和減少抖動(thrashing)。最后,由所有代理服務(wù)器構(gòu)成的層次型緩存,可以將最接近用戶的主頁復(fù)本返回給用戶,增加了信息的本地化(locality),也降低了訪問延遲。但是,目前這些緩存系統(tǒng)基本都是基于用戶對某個主頁的訪問進(jìn)行緩存的,并以此來計算命中率,實際上不能真正反映用戶的訪問行為,因此性能仍然比較低,通常有效命中率只在40%左右。一個高效、實用的代理緩存機(jī)制必須記錄和分析用戶的訪問行為,并且不只是考慮提高命中率,也要考慮降低緩存機(jī)制的訪問延遲,基于網(wǎng)站的代理緩存系統(tǒng)一Site-basedCache就是針對這些問題的一種解決方案。在這一系統(tǒng)中,每個網(wǎng)站被當(dāng)成一個由用戶訪問過的該網(wǎng)站主頁為元素構(gòu)成的向量,緩存的一致性維護(hù)是由服務(wù)器后臺進(jìn)行的,而緩存的替換算法以整個向量為對象進(jìn)行計算。同時,對某個網(wǎng)站的主頁存放目錄結(jié)構(gòu)按命中率進(jìn)行重新排列,提供用戶最短路徑得到所需的主頁,這樣可以相當(dāng)明顯地降低訪問延遲,也提高了實際命中率。Site-basedCache是在一個可擴(kuò)展Web服務(wù)器集群上實現(xiàn)的,因此具有更多的可用空間,可以緩存大數(shù)據(jù)量的主頁信息。3基于服務(wù)器組的網(wǎng)站緩沖3.1web服務(wù)器集群為了解決單臺主機(jī)作為Web服務(wù)器存在的響應(yīng)時間長、容量不夠等問題,當(dāng)前大部分提供Web信息服務(wù)的網(wǎng)站都采用了服務(wù)器集群的技術(shù),通過網(wǎng)絡(luò)連接一群Web服務(wù)器,一致對Internet用戶提供服務(wù)。一般由一臺服務(wù)器進(jìn)行訪問重定向,維持系統(tǒng)內(nèi)負(fù)載平衡;其他服務(wù)器既可以各自提供幾種Web服務(wù),也可以所有服務(wù)器協(xié)同提供全部的Web服務(wù)。這樣一個服務(wù)器系統(tǒng)是一個高性能、可擴(kuò)展的Web服務(wù)器集群,可以有效分擔(dān)某個網(wǎng)站的負(fù)載,改善服務(wù)。目前NCSA、WhiteHouse、Microsoft等大型網(wǎng)站都采用了這種集群系統(tǒng)。該系統(tǒng)由多臺Web服務(wù)器和一臺HTTP重定向器組成。在HTTP重定向器上運行負(fù)載分析和動態(tài)分配進(jìn)程,完成將客戶機(jī)請求在Web服務(wù)器集群內(nèi)部進(jìn)行調(diào)度的任務(wù)。采用100M以太網(wǎng)通過交換機(jī)連接各Web服務(wù)器和HTTP重定向器。為了提供用戶單一系統(tǒng)映像以及提高系統(tǒng)內(nèi)文件訪問的速度,在Web服務(wù)器集群平臺上建立一個并行Web文件系統(tǒng),提供統(tǒng)一命名空間,共享每個Web服務(wù)器的存儲空間。和傳統(tǒng)的由單臺計算機(jī)做服務(wù)器相比,集群具有這樣一些優(yōu)點:可擴(kuò)展能力強(qiáng),基本可以實現(xiàn)服務(wù)器性能隨規(guī)模的可比擴(kuò)展;I/O帶寬高,吞吐量大,在HTTP重定向器的調(diào)度下,所有Web服務(wù)器可以同時響應(yīng)服務(wù)請求;可建立的服務(wù)連接多,響應(yīng)請求時間短,服務(wù)及時;成本低,原有設(shè)備可充分利用;容錯性好,使用可靠等。它不僅可以提供足夠大的緩存空間,并且具有并行計算能力,是實現(xiàn)基于網(wǎng)站的代理緩存機(jī)制的理想服務(wù)器平臺。3.2主要用戶訪問行為產(chǎn)生在Site-basedCache系統(tǒng)中,目前支持的協(xié)議是HTTP(HyperTextTransferProtocol)1.0和1.1版本。HTTP協(xié)議將WorldWideWeb上所有的信息資源以一個統(tǒng)一的資源識別符表示,即URI(UniformResourceIdentifier),用戶的每個訪問請求都是以這個URI為請求地址的。已有的一些緩存系統(tǒng)都是針對用戶訪問的某個具體的主頁進(jìn)行緩存,實際上也就要求用戶在下一次訪問這個主頁時也必須清楚該主頁的URI,這將影響代理緩存系統(tǒng)提供資源共享的性能。為了改善代理緩存的服務(wù),需要對用戶的訪問行為進(jìn)行分析。產(chǎn)生這樣結(jié)果的是由于一般緩存系統(tǒng)針對孤立的某個主頁進(jìn)行操作,這些主頁在緩存空間是互不相關(guān)地存放的,緩存策略不能自動地發(fā)現(xiàn)哪些信息有用,而哪些信息可以被更換出去。同樣,這種互不相關(guān)的存放方式不能幫助用戶以最短的路徑獲得信息,即使用戶所需的主頁已被緩存,經(jīng)過多次的連接調(diào)用才能得到主頁復(fù)本,可能并未減少訪問延遲時間。因此,需要記錄用戶的訪問行為并進(jìn)行分析,以此指導(dǎo)用戶最快獲得目標(biāo)主頁。考慮到用戶的訪問具有的局部性特點,在一次連續(xù)的訪問過程中,訪問請求通常是到達(dá)同一個網(wǎng)站的,以網(wǎng)站為單位分析用戶訪問行為可以作為緩存系統(tǒng)的有效輔助信息,由此產(chǎn)生了基于網(wǎng)站的代理服務(wù)器緩存系統(tǒng)的設(shè)想。借助于上面定義的網(wǎng)站圖,可以對用戶的訪問行為進(jìn)行跟蹤記錄和分析。Site-basedCache工作原理是在一個可擴(kuò)展的Web服務(wù)器集群系統(tǒng)上實現(xiàn)的,設(shè)計緩存空間為4GB和8GB,可以存放大量的主頁內(nèi)容,包括一些多媒體信息。Web服務(wù)器集群的特點是每臺服務(wù)器單獨可以對外提供服務(wù),這樣一些訪問請求可能在不同的服務(wù)器上進(jìn)行處理。為了在服務(wù)器集群上只保存一份緩存復(fù)本,需要將所有服務(wù)器的空間進(jìn)行共享。在服務(wù)器集群系統(tǒng)上建立這樣一個并行文件系統(tǒng),它提供和URI定義相同的目錄結(jié)構(gòu),這樣的文件系統(tǒng)可以加快服務(wù)器檢索緩存復(fù)本的速度,從而提高響應(yīng)時間;另一方面,為使服務(wù)器平臺對Site-basedCache透明,緩存系統(tǒng)在訪問文件時不必考慮文件實際存放在哪臺服務(wù)器上。4集體系統(tǒng)的內(nèi)存實現(xiàn)4.1監(jiān)聽一般程序從原理上看,集群系統(tǒng)是一個并行系統(tǒng),并行系統(tǒng)較單機(jī)在Cache一致性上處理更為復(fù)雜。一般來說,并行系統(tǒng)產(chǎn)生高速緩存不一致主要有3個原因:①共享可寫數(shù)據(jù)引起(Sharingofwritabledata);②進(jìn)程遷移引起;③I/O操作引起,例如以DMA方式傳送數(shù)據(jù),DMA控制器直接對主存進(jìn)行操作(讀或?qū)?,但此時各個高速緩沖中可能有相應(yīng)數(shù)據(jù)的復(fù)本,就會造成內(nèi)存與高速緩存之間的不一致。目前,在集群系統(tǒng)的產(chǎn)品中大多數(shù)都采用基于總線的存儲器結(jié)構(gòu)?？偩€是保證高速緩存一致性最方便的技術(shù),它允許系統(tǒng)中各個處理機(jī)能夠監(jiān)測對存儲器進(jìn)行的所有操作,如果這些操作破壞了本地高速緩存中數(shù)據(jù)的一致性狀態(tài),高速緩存控制器就可以采取相應(yīng)的動作維護(hù)高速緩存的一致性。采用這種機(jī)制維護(hù)高速緩存一致性的協(xié)議的系統(tǒng)中,每個高速緩存都在監(jiān)聽其它高速緩存的操作,所以稱為監(jiān)聽總線協(xié)議。而對于可擴(kuò)展多處理機(jī)系統(tǒng),常常采用互連網(wǎng)絡(luò)實現(xiàn)多處理機(jī)互連,其網(wǎng)絡(luò)帶寬隨著處理機(jī)數(shù)目的增加而增大,但是這些網(wǎng)絡(luò)沒有方便的監(jiān)聽機(jī)制,也難于進(jìn)行有效的廣播,所以常常采用基于目錄的協(xié)議。目前廣泛使用的HTTP/1.1協(xié)議對一個主頁的復(fù)本生存期(TTL,TimeToLive)定義為:①如果響應(yīng)中有“Cache-Control:max-age=...”通用頭,那么生存期=maxage值;②否則,如果響應(yīng)中有Expires實體頭,那么生存期=Expires值一Date值;③否則,Cache可以根據(jù)某種啟發(fā)式算法給出一個生存期。但是,若在這種情況下給出的生存期超過24小時,而且響應(yīng)的年齡雖大于24小時但仍小于生存期,從而被認(rèn)定是新鮮時,必須在響應(yīng)中增加一個警告碼為13的Waring響應(yīng)頭。同時還提供了Age響應(yīng)頭記錄某個主頁復(fù)本的當(dāng)前年齡。參考這些規(guī)定,在Site-basedCache中對緩存復(fù)本設(shè)定當(dāng)前年齡pCurrentAge為本次訪問時間HTTP＿date減去該主頁在駐留網(wǎng)站創(chuàng)建的時間Date。每個緩存復(fù)本的生存期按以上的規(guī)則定義,在響應(yīng)中沒有Expires等實體頭時設(shè)定生存期pTTL為緩存復(fù)本當(dāng)前年齡的兩倍(在第一次訪問時設(shè)定,以后再命中時不再修改)。這樣判斷一個緩存復(fù)本是否有效,并作為響應(yīng)返回給客戶的條件是pCurrentAge<pTTL,即一個緩存復(fù)本變成陳舊(stale),需要從駐留網(wǎng)站更新以維護(hù)一致性的條件是pTTL>pCurrentAge。然而在pTTL>pCurrentAge情況下,并不一定要強(qiáng)制從駐留網(wǎng)站下載整個主頁。由于在駐留網(wǎng)站可用Last-Modified實體頭指明主頁的最近修改時間,由代理服務(wù)器發(fā)出的訪問請求可以增加If-Modified-Since頭,使GET成為條件取,其含義是當(dāng)GET所確定的資源在指定的時間后確實改變了,就完成GET的功能;否則,返回一個304(沒有改變)響應(yīng)。響應(yīng)304是不含實體的。這樣當(dāng)主頁實際沒有改變時,可以節(jié)省帶寬。這時修改緩存復(fù)本的生存期pTTL為當(dāng)前年齡pCurrentAge的1.5倍。在Site-basedCache工作流程中,當(dāng)緩存機(jī)制在代理服務(wù)器上檢索到對應(yīng)于用戶訪問請求的主頁復(fù)本時,先進(jìn)行緩存的一致性判斷,如果緩存復(fù)本仍然有效,則直接作為響應(yīng)返回;否則,進(jìn)行條件取,必要時更新代理服務(wù)器上的緩存復(fù)本。4.2工作集lru及其程序當(dāng)新的主存字塊需要調(diào)入高速緩存存儲器而它的可用位置又已經(jīng)被占滿時,就產(chǎn)生替換算法問題。常見的替換算法有先進(jìn)先出(FIFO)算法、近期最少使用(LRU)算法、分段LRU算法(SegmentedLRU)、工作集LRU(WorsetLRU)和基于次數(shù)的替換算法(LFU)。(1)FIFO算法:總是把一組中最先使用的字塊替換出去。它不需要隨時記錄各個字塊的使用情況,所以實現(xiàn)容易,開銷小。(2)LRU算法:把一組中近期最少使用的字塊替換出去。這種替換算法需隨時記錄高速緩存存儲器中各個字塊的使用情況,以便確定近期最少使用的字塊。這種算法利用了訪問的時間局部性,即如果最近訪問了某塊數(shù)據(jù),該塊將會在短時間內(nèi)很可能被再次訪問;如果近期沒有訪問某個數(shù)據(jù)塊,該塊很可能在短期內(nèi)不會被訪問。LRU替換算法的平均命中率比FIFO要高,并且當(dāng)分組容量加大時,能提高LRU替換算法的命中率。這種算法簡單有效,廣泛應(yīng)用于商業(yè)文件系統(tǒng)之中。(3)分段LRU算法:建立在LRU算法基礎(chǔ)上的替換算法。這種算法基于以下思想,即被訪問超過一次的塊很可能被再次訪問,因此應(yīng)該盡量避免替換被訪問次數(shù)超過一次的塊。在分段LRU算法中,緩存分成兩個部分,探測段(ProbeSegment)和保護(hù)段(ProtectedSegment)。在這兩個段中,數(shù)據(jù)按照最近被訪問的時間排序。當(dāng)將一個新塊存入緩存時,由于該塊還沒有被訪問超過一次,該塊要被存放在探測段尾部;如果用戶訪問的塊是已在緩存中的塊,由于該塊被訪問的次數(shù)已經(jīng)超過一次,該塊將被移到保護(hù)段的尾部。當(dāng)保護(hù)段滿時,被從保護(hù)段舍棄的塊要被作為最近被訪問的塊放入探測段的尾部。利用這個結(jié)構(gòu),在選擇被替換塊時,就能直接選擇探測段頭部的塊作為被替換塊。(4)基于次數(shù)的替換算法LFU:是選擇緩存中被訪問次數(shù)最少的塊為被替換塊的替換算法。這種算法中,要為每個緩存塊維護(hù)一個計數(shù)器,記錄該塊的被訪問次數(shù)。在替換時,選擇被訪問次數(shù)最少的塊進(jìn)行替換。這種算法有兩個缺點:第一,維護(hù)和利用訪問次數(shù)比訪問時間困難得多;第二,當(dāng)某些短期內(nèi)被訪問多次,卻在以后不再被訪問的塊會長期占據(jù)緩存,降低緩存的利用率。為了解決這些問題,LFU算法在實際應(yīng)用中要進(jìn)行適當(dāng)?shù)母倪M(jìn)。以上介紹的替換算法在替換時都只是利用緩存塊被訪問的狀態(tài)信息(如訪問時間、訪問次數(shù)等),沒有考慮這些訪問可能來自不同的程序,而且這些不同的應(yīng)用程序可能具有不同的數(shù)據(jù)訪問特征,因此這些算法存在如下3個問題:(1)某些應(yīng)用程序的訪問局部性比較差,如果緩存這些訪問應(yīng)用訪問的塊,會將其它應(yīng)用的具有較高緩存價值的塊替換掉,降低緩存的有效性。例如,一些大型文件系統(tǒng)的順序訪問可能會將緩存中所有的塊都替換出緩存,而代以將來可能不會再被訪問的這些大型文件系統(tǒng)的順序訪問塊。這些塊占用緩存空間,會阻礙其他重要的數(shù)據(jù)進(jìn)入緩存,因此降低了緩存的有效性。(2)對于某種應(yīng)用有效的替換算法可能對其他應(yīng)用并不有效。如果緩存系統(tǒng)允許應(yīng)用程序定義哪種替換算法,就可以使應(yīng)用程序能夠更有效地使用緩存。(3)某些應(yīng)用程序可以提供將來的塊訪問信息,但以上討論的替換算法都沒有考慮使用這些信息。如果能夠在替換時使用這些信息,可以實現(xiàn)更準(zhǔn)確的替換,從而提高緩存的利用率。(4)以上的算法在選擇被替換塊時沒有考慮到公平性。如果某個程序快速地對大量數(shù)據(jù)塊進(jìn)行訪問,會使緩存區(qū)中所有塊都屬于該程序,從而會影響其他程序的運行。工作集LRU是一種較好解決以上問題的緩存管理算法。工作集LRU為每個執(zhí)行程序分配一個單獨的內(nèi)存區(qū)域,在每個區(qū)域內(nèi)部使用LRU算法,每個程序只替換自己的頁面。分配給程序的區(qū)域大小由系統(tǒng)來動態(tài)調(diào)整。這種方法具有以下優(yōu)點:(1)可以將更多的內(nèi)存分配給具有較高訪問局部性的應(yīng)用程序,以適應(yīng)這些應(yīng)用程序的訪問特征。(2)對某些區(qū)域可以使用有應(yīng)用指定的替換策略而不使用LRU,這樣用戶可以將應(yīng)用指示結(jié)合到緩存管理中。(3)通過由系統(tǒng)為每個程序分配相應(yīng)的系統(tǒng)內(nèi)存來保證公平性。但是工作集LRU也具有一些缺點,如果分給每個應(yīng)用程序的區(qū)域調(diào)整得太慢,許多應(yīng)用程序可能無法利用動態(tài)多程序環(huán)境中的可用內(nèi)存:如果調(diào)整得太快,會導(dǎo)致過多得系統(tǒng)調(diào)整開銷,超過工作集LRU法所帶來的性能改善。下面我們做個比較,看看基于document-based的Cache和si