一種移動透明計算系統中的雙緩存協作策略

王大成, ,,

(中南大學 信息科學與工程學院,長沙 410000)

0 概述

透明計算是一種用戶無需感知計算機操作系統、支撐工具以及應用程序的所在,并能根據自己的需求從所使用的各種設備中找到相關計算服務,而這些服務又是位于分布式網絡的服務器中的計算模式[1]。為實現用戶按需索取服務的目標,透明計算將計算和存儲分離[2]。服務器存儲操作系統、應用程序以及用戶數據等軟件資源,終端接近裸機,只存儲最底層的BIOS和極少部分協議及管理程序[3]。當用戶需要服務時,透明計算系統將請求發送到服務器端,所需的操作系統、應用程序以分塊或流的形式通過網絡加載到終端上執行[4]。因此,傳輸過程中的網絡傳輸帶寬是影響系統性能的重要因素[5-7]。

為降低透明計算系統TCOS對網絡傳輸帶寬的依賴,同時提升系統性能,本文從緩存角度出發,提出一種雙緩存協作策略,并通過實驗對其效果進行驗證。

1 相關研究

為提高透明計算系統的可用性以及性能,研究者從傳輸的數據量、傳輸協議、緩存策略等方面對透明計算系統進行了優化。

文獻[8]從減少傳輸數據量角度出發,在底層緩存多個用戶請求,分類合并成一個數據包傳輸給服務器端進行處理,服務器端也將傳輸的數據進行合并壓縮傳輸。雖然這種方法減少了系統傳輸的數據量,但由于終端和服務器端需要進行合并和解析的處理,會造成響應時間增加。

文獻[9]致力于研究如何提高透明計算系統的性能,針對NCBP協議[10]在加載混雜內核或微內核結構的Windows系統前需要下載對應的加載器導致效率低的問題,提出一種可擴展啟動協議ENCBP,采用基于固件啟動代理的方法來引導啟動過程。雖然該方法可以減少加載Windows系統的時間,增加系統的安全性,但是需要定制額外的芯片來支持。大量研究從緩存策略出發,通過服務器端緩存或客戶端緩存的方法來減少數據傳輸量。

文獻[11]設置了服務器端緩存,將服務器端上常被訪問的數據塊緩存在內存中,在緩存數據進行替換時,采用新的置換算法LRU-AFS,設定了訪問頻率閾值,在替換緩存塊時,如果其頻率計數低于預設閾值,直接替換,否則重新選擇替換對象。

文獻[12]提出的TC-CRM替換算法基于客戶端請求的數據特征,將訪問頻率、最后訪問時間及訪問的數據塊長度作為替換的依據,優先替換訪問頻率低、最近被訪問的及長度較大的數據塊,保證了經常被訪問的數據塊駐留在服務器端緩存中,但是服務器傳輸到終端的數據量并沒有減少,傳輸時間也沒有減少,仍受帶寬影響。

文獻[13]通過客戶端緩存來減少傳輸時間及傳輸的數據量,在緩存中主要存儲了操作系統內核代碼,減少了內核加載使用的時間,加快了系統啟動速度,但是并未考慮將常用的應用軟件數據以及用戶私有數據放入緩存中,因此,系統啟動后應用服務的速度仍未得到提高。

本文提出一種將本地緩存與P2P緩存[14]相結合的緩存協作策略(TC-CCS),并以移動透明計算系統TCOS[12]為實例進行優化研究。TCOS系統面向的是移動終端,且存儲容量有限。通過在終端上開辟適當大小的緩存空間,緩存常用的數據來加快請求的處理速度,且多個終端請求的數據相同,可以相互共享。

2 TCOS系統

2.1 系統結構

TCOS系統是以透明計算為理念設計實現的面向移動終端的分布式系統,其結構如圖1所示。

圖1 TCOS系統結構

TCOS系統按照功能可劃分為3個部分:終端設備,主服務器,存儲服務器。

1)終端設備上內置了相應的管理程序,主要負責網絡配置、提供用戶登錄使用的交互界面、讓用戶可選擇操作系統使用等。虛擬磁盤驅動是終端上用來處理數據請求的。與一般的磁盤驅動不同,虛擬磁盤驅動讀寫的是服務器端的鏡像文件。通過將本地I/O請求封裝成特定的網絡數據包發送到服務器端,服務器端將處理的結果返回。

2)主服務器上部署了Web管理平臺,負責認證用戶身份、管理用戶屬性、鏡像數據等,并對系統內的終端設備以及存儲服務器進行監控。

3)存儲服務器主要用于存放各類數據,包含操作系統鏡像、應用軟件鏡像和用戶數據鏡像,分別存放系統數據、應用軟件數據和用戶私有數據。其中,操作系統鏡像和應用軟件鏡像可以被用戶共享,用戶數據鏡像為每個用戶私有。

2.2 數據訪問流程

當用戶身份認證合法后,在終端上選擇某個操作系統進行使用時,數據的訪問流程如圖2所示。具體步驟如下:1)終端與存儲服務器建立連接;2)存儲服務器端根據用戶選擇的系統種類,打開對應的鏡像文件;3)虛擬磁盤驅動接收操作系統運行時產生的I/O請求發送到存儲服務器端進行處理;4)處理時按照讀、寫請求分類處理,將讀取的數據或寫入是否成功返回給虛擬磁盤驅動。至此,就完成了一次數據訪問。

圖2 TCOS數據訪問流程

3 TC-CCS策略

3.1 設計思想

從TCOS的架構可以看出,若所有終端在同一局域網內,和服務器端的數據傳輸交互都是通過一個出口(路由器或交換機)進行。當傳輸的數據量較大時,出口帶寬會形成瓶頸,限制了數據傳輸的效率,會影響用戶使用。

本文提出的TC-CCS策略通過在終端上設置緩存策略來解決帶寬帶來的系統瓶頸問題。首先對終端的數據訪問特點進行分析。在使用過程中,終端的數據訪問存在3個特點:1)數據類型不同,訪問的數據有操作系統數據、應用軟件數據和用戶私有數據;2)訪問的數據量的峰值出現在2個階段,第一階段為啟動操作系統,訪問的數據量根據系統種類不同,其范圍限制在300 MB～1 000 MB內,第二階段是使用“笨重”的應用軟件,有些軟件啟動時需要讀取的數據量也能達到上百兆之多;3)存在某些數據,如操作系統或應用軟件數據,被不同終端多次訪問。

針對數據訪問的特點,本文從以下方面對TC-CCS策略進行設計與實現:

1)設置本地緩存,用來緩存用戶常用的個人數據,如文檔等,這部分數據是私有的,數據量比較小,從用戶數據鏡像中讀取。

2)設置P2P緩存,并將其劃分成2個部分,分別用來緩存操作系統啟動數據以及應用軟件數據,從操作系統鏡像和應用軟件鏡像中讀取,用來加快啟動速度。這兩部分數據是共享的,且數據量比較大,考慮到局域網帶寬一般大于廣域網帶寬,從其他終端上讀取的速度比從服務器端讀取更快,因此,本文在局域網中構建P2P網絡。

3)緩存協作。在終端上存在本地緩存和P2P緩存2種。不同終端上的P2P緩存可以共享,相互協作來完成數據請求處理。

4)替換策略。P2P緩存中的系統啟動數據能加速系統啟動過程,對這部分數據標記不進行替換。

TC-CCS策略示意圖如圖3所示。

圖3 TC-CCS策略示意圖

3.2 緩存存儲結構Cache-Storage

TCOS系統中數據的基本處理和存儲單位是“數據塊”,且大小為4 KB,以偏移量為標識。因此,緩存塊的大小同樣設置成4 KB,在進行讀取和寫入時不需要進行額外處理。在緩存容量較大時,塊的數目可能非常多,且由于其偏移量并不連續,存儲時塊與塊之間存在空白區域,可能會為較少的緩存塊分配很大的存儲空間,再判斷緩存是否命中,查找代價大。因此,本文針對緩存文件的存儲設計了Cache-Storage結構。

如圖4所示,Cache-Storage將緩存文件分成3個部分存儲。

Header區存放的是文件的全局信息,包含文件類型、大小、Map區起始地址、Data區起始地址、Map區的塊大小、Data區的塊大小等。

Map區是為了加快數據塊的查找。其中,index表示數據塊的偏移量,data_offset表示在Data區的存儲地址。初始化文件時,所有塊對應的偏移量初始值均為FFFFFFFF。當某一數據塊尚未存儲時,其對應的偏移量均為初始值。

Data區是用來存儲數據塊內容的,塊與塊之間是連續存儲的。每次有新的數據塊寫入,直接存儲在Data區尾部,并將其data_offset值寫入到Map區對應的index位置上。

當需要讀取數據塊時,首先查詢Map區。如果數據塊對應的data_offset為初始值,表示此數據塊不存在,讀取失敗,如果不為初始值則按照data_offset直接在Data區讀取即可。當寫入數據塊時,如果data_offset值不為初始值,表示的是修改操作,直接進行覆蓋寫。如果為初始值,則是添加操作,將Data區末尾的地址作為數據塊對應的data_offset存儲在Map區的對應位置,然后再寫入數據。

3.3 P2P緩存

P2P緩存的目的是增加局域網內的數據訪問,減少對服務器端的訪問,降低對帶寬的壓力。在TCOS系統中,P2P緩存的是系統啟動數據和應用軟件啟動數據,能加快操作系統和應用軟件的啟動。這兩部分數據是被多數終端感興趣的,而且是可被共享的。用戶對系統啟動流程的修改,被當做是私有數據,不會被共享。

P2P緩存采用結構化的組織方式,使用分布式哈希表DHT[15]的思想,通過對數據進行分割,在每臺終端上只存儲特定的數據,當用戶需要讀取時,采用Chord算法[16]進行查找,而不是使用廣播或者非結構化中的泛洪式查找算法。數據塊定位過程如圖5所示,具體步驟如下:

1)將終端的IP地址進行哈希得到一個節點值,按照節點值從小到達構成一個Chord環。

2)根據節點值,獲取此節點和下一節點之間的距離,以此來劃分每個節點上存儲的數據塊。

3)對數據塊的偏移量進行哈希,按照哈希值的大小來決定存儲此塊的節點。在判斷數據塊能否被寫到P2P緩存中,也遵循此原則。如果終端讀取的數據塊的哈希值經過判斷不能存儲在本地時,就將其舍棄。

4)為每個節點建立路由表,它根據計算數據塊哈希值指數級增長時對應的各個結點,形成表中的信息。在查找某個數據塊時,進行比對,直接定位到對應的節點上,提高了查找的速率。

5)在查找到數據塊的位置后,與目標節點建立連接,發送請求進行讀取。

圖5 數據塊定位示意圖

在使用了DHT后,緩存數據的部署如下:以Centos啟動過程為例,大約需要讀取400 MB的數據量,終端有5臺,達到的的效果是在各個終端上的P2P緩存中包含約80 MB互不相同的系統啟動數據。當系統在啟動時,需要的數據基本上可以全部從P2P緩存中讀取到。

3.4 緩存替換算法TC-Replace

P2P緩存中包含系統啟動數據和應用軟件數據。系統啟動數據為每次啟動加速,這部分數據不進行替換,替換的是應用軟件數據。

本文提出TC-Replace替換算法,考慮到P2P緩存中的應用軟件數據可能經常被本地訪問或其他終端訪問,因此,替換時兼顧本地訪問和其他終端訪問的情況。該算法設計思想如下:首先設置了3個主隊列,分別是LRU[17]、LFU1和LFU2隊列。LRU中的數據至少被訪問2次,才能被移入LFU隊列。其中LFU1用來存放本地系統常訪問的數據,LFU2用來存放其他終端經常訪問的數據。為了區分數據塊的移動方向,本文定義緩存塊的屬性包含{localCount,shareCount},其中:localCount代表被本地系統訪問的次數,其最小值為1;shareCount代表被其他終端訪問的次數,其最小值為0。根據localCount和shareCount才能區分緩存塊到底是移動到LFU1還是LFU2中。LFU1隊列按照localCount排序,LFU2隊列按照shareCount排序。主隊列替換出去的緩存塊,先不完全淘汰,防止出現“幽靈命中”情況。通過設置2個副隊列,分別存放被LRU和LFU替換算法淘汰的緩存塊。從副隊列淘汰出去的緩存塊才是被完全淘汰。圖6表示的是一次緩存替換的過程,其中標號表示如下:

①表示新的數據加入,添加到LRU隊列;

②表示當LRU隊列中某一緩存塊被本地系統訪問,則添加到LFU1隊列;

③表示當LRU隊列中某一緩存塊被其他終端訪問,則添加到LFU2隊列;

④表示當LFU1和LFU2隊列中緩存塊被本地系統或其他終端再次訪問,根據訪問次數調整緩存塊在隊列中的位置;

⑤表示當LFU1淘汰緩存塊時,根據shareCount的值判斷能否進入LFU2中,如果不能則直接淘汰到副隊列2中。LFU2淘汰數據規則同上。這是為了保證被本地終端和其他終端感興趣的緩存塊盡可能的滯留在緩存中;

⑥表示LRU隊列淘汰數據到副隊列1中,LFU1和LFU2隊列淘汰數據到副隊列2中;

⑦表示在副隊列中的緩存塊可能被再次命中。副隊列1中的緩存塊被再次訪問后,直接添加到LRU中。副隊列2中的緩存塊被再次訪問后,區分是本地系統還是其他終端請求,然后添加到相應的LFU隊列;

⑧表示副隊列淘汰數據,這次是完全淘汰。

圖6 緩存替換過程

4 性能測試及分析

本節針對TC-CCS策略中緩存性能進行測試及分析。測試環境使用移動透明計算系統TCOS,設置1臺服務器、4臺相同配置的終端。終端與服務器經2個路由器相連。服務器和終端配置如下:

1)服務器采用Dell R720,處理器為Intel(R) Xeon(R) CPU E5-2609 v2@ 2.50 GHz,16 GB內存,硬盤容量6 TB,搭載CentOS release 6.5操作系統。

2)終端設備為普瑞吉開發板,處理器為Intel(R)Bay Trail D/I/M SOC,2 GB內存,存儲容量8 GB。

TC-CCS策略是為了解決局域網出口帶寬受限對系統性能造成影響的問題。在測試時,帶寬速率不容易限制,通過限制服務器的網卡上行和下行速度來模擬帶寬受限的情況。設置緩存大小為200 MB對其性能進行測試。

為測試TC-CCS策略對軟件啟動時間的影響,本文采用Eclipse作為啟動軟件,從服務器端讀取100 MB的數據,設置服務器端網卡上行速度分別為1 MB/s、2 MB/s、3 MB/s,測試了分別啟動1臺終端、2臺終端和3臺終端時使用TC-CCS策略和不使用TC-CCS策略的軟件啟動時間變化,測試結果如圖7所示。

圖7 啟動軟件時長對比

由圖7可知,未采用TC-CCS策略時,隨著終端啟動臺數的增加,Eclipse軟件啟動時間增長,這是因為啟動臺數越多,各個終端都需要從服務器上獲得數據量,數據量成倍增長。而隨著帶寬速率的增加,軟件啟動時間減少,這是因為帶寬速率增加,所傳輸的數據量增加,所以啟動時間縮短。當帶寬速率越低,啟動時間受帶寬影響越明顯。在使用TC-CCS策略后,若終端發現數據缺失,將首先從局域網其他終端取數據,只有局域網其他終端都不存在所需數據后,才向服務器端請求,因此,采用TC-CCS策略后,雖然隨著啟動臺數的增加,啟動時間有所增長,但帶寬速率的影響基本可忽略;而且當帶寬速率為1 MB/s且啟動3臺終端的情況下,使用TC-CCS策略的啟動時間比未使用TC-CCS策略縮短了約68%。

本文同時測試了TC-CCS策略對操作系統啟動時的影響,采用CentOS系統進行測試。系統啟動時,服務器端沒有限制網卡速度,測試了分別啟動1臺、2臺、3臺終端時使用TC-CCS策略和不使用TC-CCS策略的系統啟動時間變化,測試結果如圖8所示。

圖8 CentOS系統啟動時間對比

由圖8可知,隨著終端數目的增加,系統啟動時長也在增加,這是因為啟動過程中傳輸的數據量是隨著終端數目線性增長的,所以時長也在增加。當不使用TC-CCS策略時,系統啟動時長增加得更快,這是因為由于啟動所需的數據量較大,此時網絡會產生擁塞。而在使用TC-CCS策略后,系統啟動時也是首先從局域網其他終端取數據,只有局域網其他終端都不存在所需數據后,才向服務器端請求。因此,系統啟動時間增加的較慢。對比3臺終端的啟動時間可知,使用TC-CCS策略后,啟動速度提高了約40%。

最后本文測試了緩存替換算法TC-Replace的命中率,分別對比不同緩存大小情況下LRU、LFU、LRU-AFS、TC-CRM和TC-Replace算法請求100 MB文件的命中率,測試10次取平均值,測試結果如圖9所示。

圖9 緩存替換算法命中率對比

由圖9可知,隨著緩存容量的增加,5種算法的命中率都在增加。當緩存大小超過30 MB時,TC-Replace算法的命中率高于其他算法的命中率,這是因為TC-Replace替換算法考慮了透明計算系統中數據訪問的特性,結合使用了多級LRU和LFU策略的緩存隊列。而TC-CRM替換算法較LRU和LFU策略的命中率低,這是因為其考慮更多的是多個終端數據數據請求的共性:請求的短數據包較多,所以在替換時保留短數據包,而測試時針對單個數據塊來考慮,不存在短數據包和長數據包的區別。而LRU-AFS設置兩級緩存隊列,命中率略高于除TC-Replace之外的3種替換算法,但是因為2個隊列采用的都是LRU算法替換,導致了緩存中有些高頻數據被替換出去,所以其命中率低于TC-Replace算法。

5 結束語

網絡帶寬是影響透明計算性能的重要因素,特別是移動透明計算系統,由于其面向的是移動終端用戶,網絡信號不穩定導致帶寬更容易受限。本文提出的緩存協作策略TC-CCS,通過設置本地緩存和P2P緩存來增加局域網內部的數據交互,減少對外網的訪問,縮短用戶等待時間,減少網絡流量,并降低服務器端壓力,同時利用P2P緩存加快操作系統啟動速度。通過模擬網絡帶寬受限情況進行性能測試,結果表明,TC-CCS策略不僅能加快應用軟件的啟動,而且能將操作系統的啟動速度提高40%。由于該策略主要用于終端設備,因此下一步將從服務端緩存角度出發對其進行優化。

[1] ZHANG Y,GUO K,REN J,et al.Transparent computing:a promising network computing paradigm[J].Computing in Science and Engineering,2017,19(1):7-20.

[2] LI S,ZHOU Y,ZHANG Y.NSAP+:supporting transparent computing applications with a service-oriented protocol[J].Computing in Science and Engineering,2017,19(1):21-28.

[3] YI L,LI J,ZHANG Y.Improving the scalability of wearable devices via transparent computing technology[J].Computing in Science and Engineering,2017,19(1):29-37.

[4] PENG T,LIU Q,WANG G.A multilevel access control scheme for data security in transparent computing[J].Computing in Science and Engineering,2017,19(1):46-49.

[5] GUO K,HUANG Y,KUANG L,et al.CASP:a context-aware transparent active service provision architecture in a mobile internet environment[J].Computing in Science and Engineering,2017,19(1):7-12.

[6] ZHANG Y,ZHOU Y.TransOS:a transparent computing-based operating system for the cloud[J].International Journal of Cloud Computing,2011,1(4):287-301.

[7] 韋 理,張堯學,周悅芝.透明計算系統中緩存性能的仿真分析與驗證[J].清華大學學報(自然科學版),2009,10(49):128-130.

[8] 高 原,張堯學,周悅芝.一種基于透明計算的多媒體I/O訪問控制方法[J].湖南大學學報(自然科學版),2013,40(3):93-96.

[9] 韋 理,徐廣斌,張堯學,等.一種擴展的多操作系統遠程啟動協議ENCBP[J].計算機研究與發展,2009,46(6):905-912.

[10] 周悅芝,張堯學,王 勇.一種用于網絡計算的可定制啟動協議[J].軟件學報,2003,14(3):538-546.

[11] 譚成輝.基于分級Cache的透明計算系統研究與實現[D].長沙:湖南大學,2010.

[12] 徐 云.基于虛擬化技術的透明計算系統優化研究[D].長沙:中南大學,2015.

[13] 田 彪.移動透明計算環境下的緩存優化問題研究[D].長沙:中南大學,2016.

[14] 胡懋智,徐 恪,夏樹濤,等,TOW:一種新的 P2P實時流媒體緩存替換算法[J].小型微型計算機系統,2009,30(8):1485-1489.

[15] 李運娣,馮 勇.基于DHT的P2P搜索定位技術研究[J].計算機應用研究,2006,23(10):226-228.

[16] 曾曉云.基于Chord協議的混合P2P模型[J].計算機工程,2010,36(7):112-114.

[17] 張堯學,宋 虹,張 高.計算機操作系統教程[M].4版.北京:清華大學出版社,2013.