王輝宇，陽 旺

中南大學 計算機學院，長沙410006

1 引言

近年來，隨著互聯(lián)網(wǎng)絡(luò)技術(shù)的不斷發(fā)展和移動終端的技術(shù)革新，移動終端的數(shù)量與日俱增，呈現(xiàn)出爆炸式增長的趨勢。截至2018年底，我國手機網(wǎng)民規(guī)模達8.17億，網(wǎng)民通過手機接入互聯(lián)網(wǎng)的比例高達98.6%[1]。用戶手機安裝的應(yīng)用數(shù)量根據(jù)使用的手機性能的不同而有所差異。平均每臺高中低端手機中安裝的應(yīng)用數(shù)量分別為59、50和45，而低端手機用戶安裝的APP數(shù)量與高中端手機有一定差距，其差距主要來源于手機內(nèi)部存儲（Random Access Memory，RAM）與外部存儲（Read-Only Memory，ROM）的不同。雖然目前手機外存在不斷地增長，但是對應(yīng)的應(yīng)用大小也在逐漸增大（由于業(yè)務(wù)的擴展使得應(yīng)用大小增加）。因此單純地增大外存并不能從根本上解決問題，只會增加手機的成本。對于用戶而言，可能只使用應(yīng)用的部分功能，因此應(yīng)用大小的增加對于部分用戶而言只會占用存儲空間而并未改善其使用的功能。

針對以上問題，目前主流的方案是應(yīng)用程序的輕量化設(shè)計。以微信小程序和Android Instant app為例的輕量化應(yīng)用滿足了用戶小需求的及時化場景，并且無需安裝，用完即走。但是輕量化應(yīng)用值包含了原生應(yīng)用的部分功能，導(dǎo)致此類應(yīng)用只能作為對原生APP使用場景的一種補充，而無法替代原生APP。而流式應(yīng)用分發(fā)系統(tǒng)[2]基于透明計算[3]的思想，采用“存儲與計算分離，按需加載”的思想，用于集中存儲和管理移動終端程序，從根本上釋放終端的存儲空間。此外，將應(yīng)用存儲于服務(wù)器中，移動終端無需考慮應(yīng)用的安裝、維護、管理、升級等問題。但是所有資源均從服務(wù)器中獲取，與當前的網(wǎng)絡(luò)狀況息息相關(guān)，因此移動終端的緩存設(shè)計對流式應(yīng)用分發(fā)系統(tǒng)而言至關(guān)重要。它通過有限的存儲空間，實現(xiàn)無應(yīng)用限制的使用。此外合理的緩存替換算法，可以增加緩存命中率，減少網(wǎng)絡(luò)訪問次數(shù)，加快應(yīng)用啟動速度。

2 相關(guān)工作

流式應(yīng)用技術(shù)的核心是“按需加載，流式執(zhí)行”，應(yīng)用資源存儲于遠程服務(wù)器，通過流的形式按需加載到終端。文獻[4]提出一種基于Android的流式應(yīng)用分發(fā)系統(tǒng)，應(yīng)用的分發(fā)由服務(wù)器管理平臺處理，客戶端無需執(zhí)行任何操作；文獻[5]在該系統(tǒng)上通過位置信息對其進行應(yīng)用智能推薦；文獻[6]提出基于情景感知的流式應(yīng)用分發(fā)系統(tǒng)，通過對用戶情景數(shù)據(jù)的收集，利用極端梯度提升算法（eXtreme Gradient Boosting，Xgboost）給用戶推薦相應(yīng)的應(yīng)用。但是流式應(yīng)用分發(fā)系統(tǒng)在網(wǎng)速受限的情況下，加載速度較慢，導(dǎo)致應(yīng)用啟動緩慢，并且在用戶頻繁使用應(yīng)用的過程中，客戶端需要不斷地向服務(wù)器請求數(shù)據(jù)，容易導(dǎo)致高并發(fā)情況，使得服務(wù)器負載加重，而通過無線網(wǎng)絡(luò)方式連接互聯(lián)網(wǎng)，往往帶來流量消耗的費用增加。因此，如何有效地減少客戶端訪問服務(wù)器的頻率成為流式應(yīng)用分發(fā)系統(tǒng)亟待解決的問題。

目前解決此類問題，主要是通過緩存設(shè)計將從網(wǎng)絡(luò)中加載過來的資源緩存于本地。緩存設(shè)計又可分為硬件層面與軟件層面。文獻[7]介紹了一種基于自旋轉(zhuǎn)移矩隨機存儲器（Spin-Transfer Torque-Magnetoresistive Random-Access Memory，STT-MRAM）的新型非易失性末級存儲，該存儲方案通過新穎地讀出電路增強了STT-MRAM的可靠性與典型的糾錯碼。文獻[8]基于內(nèi)存駐留數(shù)據(jù)庫管理系統(tǒng)提出將部分分解的存儲和即時查詢相結(jié)合的思想，消除了CPU低效的函數(shù)調(diào)用，實現(xiàn)了在不犧牲CPU效率的情況下節(jié)省帶寬。文獻[9]針對新型的非易失性存儲器需要嚴格地按照順序執(zhí)行存儲器寫入導(dǎo)致的系統(tǒng)性能降低問題，提出了一種松散順序一致性機制。其主要通過消除事務(wù)結(jié)束時執(zhí)行的持久化提交記錄的寫入，以減少開銷，允許通過推測性寫入來放寬事務(wù)之間的寫入順序。

除從緩存的結(jié)構(gòu)和性能指標上對緩存進行優(yōu)化外，還可通過適當?shù)木彺嫣鎿Q策略增加緩存命中率。文獻[10]在移動透明計算系統(tǒng)（Transparent Computing System，TCOS）中設(shè)計了基于預(yù)取機制的緩存替換策略（Cache Replacement Algorithm based on Prefetching Mechanism，BPF-CR）。該策略設(shè)置三個不同等級的主隊列，對不同隊列采取不同的緩存替換策略，當下一級隊列的數(shù)據(jù)再次被訪問時，將移入上一級隊列中，并設(shè)置副隊列用于存儲緩存淘汰的數(shù)據(jù)。文獻[11]在實現(xiàn)透明手表應(yīng)用程序的緩存設(shè)計時提出了N-LRU策略。該策略結(jié)合應(yīng)用程序的大小、使用概率以及當前網(wǎng)絡(luò)帶寬計算策略優(yōu)先級。

流式應(yīng)用分發(fā)系統(tǒng)中各用戶相互獨立，用戶之間數(shù)據(jù)不可共享，緩存對象為應(yīng)用程序。因此挖掘用戶使用應(yīng)用的行為規(guī)律有利于提高流式應(yīng)用的緩存命中率。文獻[12]通過對Android系統(tǒng)中豌豆莢平臺的數(shù)百萬數(shù)據(jù)進行分析，研究用戶使用應(yīng)用的行為過程，如用戶的偏好、用戶對應(yīng)用的選擇、應(yīng)用程序的生命周期等。文獻[13]關(guān)注于移動應(yīng)用程序之間的相互依賴性，通過數(shù)據(jù)挖掘算法對應(yīng)用程序進行分類。由此可知，用戶使用應(yīng)用的行為具有一定的規(guī)律性。文獻[14]通過對應(yīng)用程序使用日志數(shù)據(jù)進行分析，預(yù)測應(yīng)用的使用情況。

流式應(yīng)用分發(fā)系統(tǒng)中緩存策略的選擇需要考慮用戶行為、應(yīng)用使用大小等問題。由于客戶端在達到緩存替換策略的觸發(fā)條件時仍能進行緩存，因此緩存替換策略的執(zhí)行時間應(yīng)在緩存溢出前完成，故算法的復(fù)雜性可能會影響到應(yīng)用的啟動速度。

3 總體框架設(shè)計

3.1 框架介紹

流式應(yīng)用分發(fā)系統(tǒng)采用的是C/S架構(gòu)，如圖1所示。服務(wù)器端主要是應(yīng)用資源存儲模塊和應(yīng)用推送模塊，客戶端主要是流式加載模塊、緩存模塊和緩存替換策略模塊?？蛻舳撕头?wù)器端通過無線網(wǎng)絡(luò)進行通信。

圖1 流式分發(fā)系統(tǒng)框架

服務(wù)器端的功能主要是存儲應(yīng)用資源，管理用戶個人信息，并且根據(jù)用戶的需求將應(yīng)用推送給客戶端。在服務(wù)器端和客戶端之間，通過無線網(wǎng)絡(luò)進行交互，其中主要有兩部分資源的交互：第一部分為網(wǎng)絡(luò)文件系統(tǒng)（Network File System，NFS）[15]，應(yīng)用資源通過NFS加載網(wǎng)絡(luò)資源，客戶端在通過NFS訪問服務(wù)器資源時，如同訪問本地資源；第二部分為文本通信，主要通信的內(nèi)容是待安裝或卸載的應(yīng)用程序少量信息，如文件名，采用的是消息隊列遙測傳輸（Message Queuing Telemetry Transport，MQTT）協(xié)議[16]，它是一個發(fā)布/訂閱者模式的協(xié)議，并且通信消耗的網(wǎng)絡(luò)流量幾乎可以忽略不計。

客戶端主要是流式加載來自服務(wù)器的資源，在本地進行安裝運行，緩存是在流式加載的過程中將資源保存到本地主存中，進行持久化存儲，緩存替換在緩存大小達到一定值后會被觸發(fā)，將優(yōu)先級低的緩存塊替換。緩存替換算法的優(yōu)劣直接影響應(yīng)用緩存的頻率，從而影響客戶端流量的消耗、應(yīng)用啟動的時延等。

3.2 系統(tǒng)實現(xiàn)原理

在原生的Android系統(tǒng)中，應(yīng)用被下載之后首先會被拷貝到/data/app/下（系統(tǒng)級應(yīng)用安裝在/system/app/下），并通過監(jiān)聽機制inotify監(jiān)聽該目錄。而在流式應(yīng)用分發(fā)系統(tǒng)中，APK文件存儲于服務(wù)器，因此在本地創(chuàng)建一個與/data/app/同級的新目錄/data/metaosapp/，并通過NFS實現(xiàn)掛載。由于metaosapp文件夾資源來自于服務(wù)器，當該文件內(nèi)容發(fā)生變化，客戶端只有在主動更新文件內(nèi)容時文件屬性才會發(fā)生變化，此時才能被inotify監(jiān)聽到。因此，本文通過MQTT實現(xiàn)客戶端與服務(wù)器之間的通信，當服務(wù)器向該掛載目錄中刪除或添加應(yīng)用時，通知客戶端更新目錄，從而執(zhí)行安裝卸載命令?？蛻舳?data/data/目錄用于存儲用戶使用應(yīng)用的信息，同上，創(chuàng)建新目錄/data/metaosdata/并實現(xiàn)網(wǎng)絡(luò)化。

3.3 緩存實現(xiàn)原理

流式應(yīng)用分發(fā)系統(tǒng)的緩存設(shè)計主要是為了緩存客戶端通過NFS從服務(wù)器中加載的資源，而在Linux內(nèi)核中，提供了FS-Cache[17]用于實現(xiàn)網(wǎng)絡(luò)文件系統(tǒng)緩存。Android操作系統(tǒng)基于Linux內(nèi)核，因此本文通過FSCache實現(xiàn)流式應(yīng)用分發(fā)系統(tǒng)緩存設(shè)計。

FS-Cache在文件系統(tǒng)緩存中只是作為一個緩存接口，其實際的緩存操作交由緩存后端CacheFiles[18]實現(xiàn)，通過CacheFiles管理緩存文件和目錄，可以將從網(wǎng)絡(luò)文件系統(tǒng)中加載的資源永久緩存于本地。CacheFiles緩存后端主要包括cachefilesd守護進程和cachefiles模塊。cachefilesd用于cachefiles模塊的管理，如初始化相關(guān)信息、監(jiān)聽目錄文件等。cachefiles模塊則通過接收cachefilesd指定執(zhí)行相關(guān)操作，如目錄文件創(chuàng)建、緩存生成等。

圖2為流式應(yīng)用緩存實現(xiàn)原理?？蛻舳耸紫葐討?yīng)用程序，然后CacheFiles判斷緩存是否命中與一致性，若緩存命中且客戶端與服務(wù)器緩存資源一致，則直接從緩存中獲取資源，否則，通過NFS按需加載，同時將從服務(wù)器加載的資源緩存于本地。當緩存空間不足時，則執(zhí)行緩存替換操作，當應(yīng)用啟動資源加載完畢后，應(yīng)用便可正常使用。

圖2 流式應(yīng)用緩存實現(xiàn)

CacheFiles緩存替換策略的觸發(fā)通過設(shè)置三組參數(shù)實現(xiàn)，如表1所示。與傳統(tǒng)的緩存空間設(shè)置不同，Cache-Files緩存替換策略并非在緩存溢出時觸發(fā)，而是在緩存空間使用率達到某一條件時觸發(fā)，直至滿足另一條件時結(jié)束。觸發(fā)條件主要由兩部分組成——實際緩存空間大小與文件存儲數(shù)量。并且通過bstop/fstop參數(shù)的設(shè)置，可以使得緩存剔除操作與緩存生成同時進行，以避免等待緩存替換所花費的時間。

表1 緩存替換策略觸發(fā)參數(shù)

緩存空間只是客戶端存儲空間的一部分，緩存替換的觸發(fā)除了達到緩存空間上限之外，同時還考慮了客戶端的剩余存儲空間。在滿足客戶端可用存儲空間足夠時，會自適應(yīng)調(diào)節(jié)緩存空間的總大小，以提高客戶端存儲空間的利用率和緩存替換算法的命中率。其主要是通過調(diào)節(jié)上述三組參數(shù)的數(shù)值以控制緩存剔除的開啟與關(guān)閉。

4 緩存替換策略

4.1 用戶行為預(yù)測策略

本文緩存設(shè)計的對象為應(yīng)用程序，而應(yīng)用的使用者為用戶，根據(jù)調(diào)研發(fā)現(xiàn)，用戶使用應(yīng)用時具有主觀意識，而CacheFiles默認使用的最近最少使用策略（Least Recently Used，LRU）僅考慮緩存塊的訪問時間，因此無法有效地提高緩存命中率。而本文中，緩存塊的主體是應(yīng)用程序，主體的使用者是用戶，因此可以根據(jù)用戶的使用行為預(yù)測應(yīng)用的使用時間，故本文提出了用戶行為預(yù)測（User Behavior Prediction，UBP）緩存替換策略。該策略通過記錄應(yīng)用啟動時間并分析預(yù)測應(yīng)用下次的使用時間。

UBP緩存替換策略從時間預(yù)測上分為兩類：一類是預(yù)測當前可能會運行的應(yīng)用程序，因為存在部分應(yīng)用，在使用時通常會和某些應(yīng)用同時使用，所以可以根據(jù)其中某一應(yīng)用的啟動預(yù)測另一應(yīng)用可能會被使用；另一類是預(yù)測應(yīng)用下次使用時間，通常用戶會在某種特定的場景下使用某些應(yīng)用。根據(jù)這些特點，對歷史記錄中各時間點應(yīng)用的使用情況進行分析，替換緩存中預(yù)測時間距當前時間最久的應(yīng)用。

UBP策略將應(yīng)用的使用時間分為兩部分：一個是橫向時間軸，表示時間點，單位毫秒；另一個是縱向時間軸，表示天數(shù)，單位日?？v向的時間軸用于預(yù)測事件在某時間點的發(fā)生概率或可信度。對所有時間點進行加權(quán)平均，得到應(yīng)用的預(yù)測值。由于存在部分應(yīng)用得到的預(yù)測值相同，如某些應(yīng)用使用時間完全相同，因此預(yù)測值并不能完全區(qū)分應(yīng)用的優(yōu)先級，故UBP策略除了對應(yīng)用進行預(yù)測，同時還對應(yīng)用的使用時長進行統(tǒng)計。如圖3所示，綜合四種子策略的優(yōu)先級值，得出UBP策略的CBP（Combined Behavior Prediction，CBP）值，用于量化該應(yīng)用緩存在不久將來使用的可能性。

圖3 UBP緩存替換策略

4.1.1 關(guān)聯(lián)性規(guī)則

為了挖掘用戶在不同時間使用的應(yīng)用之間的關(guān)聯(lián)性，本文采用加權(quán)頻繁項集算法[19]挖掘不同時間點應(yīng)用之間的關(guān)聯(lián)性。算法核心是通過當前時間點正在運行的應(yīng)用預(yù)測將可能使用的應(yīng)用。

應(yīng)用關(guān)聯(lián)性挖掘的是正在運行程序的應(yīng)用與緩存中應(yīng)用的關(guān)聯(lián)性，因此對于數(shù)據(jù)集中的頻繁項只需要包含當前正在運行的應(yīng)用或緩存中的應(yīng)用。每個頻繁項的使用時間不同，因此對應(yīng)用的關(guān)聯(lián)性采取加權(quán)頻繁項集挖掘。

算法1關(guān)聯(lián)性規(guī)則算法

輸入：所有時間點集合T←{T1,T2,…,Tm}，各時間點集合Tt←{D1,D2,…,Dn}。

輸出：關(guān)聯(lián)性規(guī)則優(yōu)先級R。

1.N←0

2.for t←1 to m do

3.提取某時間點t的歷史數(shù)據(jù)作為數(shù)據(jù)集Tt，對每個項集進行處理，只保留相關(guān)應(yīng)用（運行中的應(yīng)用和緩存中的應(yīng)用），得到L1

4.根據(jù)最小支持度min sup篩選L1得到C1，并從C1中提取兩個集合Su與Sc，其中Su←{fi,fi+1,…,fj}表示C1中運行的應(yīng)用集合，Sc←{fx,fx+1,…,fy}表示C1中緩存的應(yīng)用集合

5.通過C1將Su和Sc元素組合得到L2，并根據(jù)最小支持度得到C2

6.if L2表不為空then

7. Rt←{confidence(fi?fk)|fi∈Su},fk為緩存中的應(yīng)用，則fk在時間點t的關(guān)聯(lián)性規(guī)則值為Rt中的最大值Rt

8.R←R+Rt，N←N+1

9.end if

10.end for

11.R←R/N

12.Rc表示當前時間點的關(guān)聯(lián)性規(guī)則算法優(yōu)先級，R取R和Rc中的最大值

13.輸出R

如算法1所示，首先對數(shù)據(jù)集進行掃描，得到頻繁一項集L1，再根據(jù)最小支持度min sup得到一階候選項集C1，將存在于C1中的運行應(yīng)用和緩存應(yīng)用組合，重復(fù)前面的步驟得到頻繁二項集L2以及二階候選項集C2，通過C2求出每個運行中應(yīng)用對緩存應(yīng)用的置信度，取其最大值。根據(jù)以上步驟，對所有時間點的最大置信度取平均值。為保證當前時間點具有更高的信任度，再將求得的平均值和當前時間點的最大置信度相比，將兩者中的較大值作為關(guān)聯(lián)性規(guī)則優(yōu)先級。

4.1.2 時間點預(yù)測

關(guān)聯(lián)性規(guī)則只能用于預(yù)測即將要被使用的應(yīng)用，但是緩存中大部分的應(yīng)用可能并不會立刻被使用，因此還需對緩存中的應(yīng)用下次使用的時間進行預(yù)測。

時間點預(yù)測主要通過分析歷史記錄中各時間點使用應(yīng)用的分布情況，得出各時間點的使用概率。由于某時間點的應(yīng)用使用概率需要同時考慮使用次數(shù)以及使用時間，本文采用LRFU（Least Recently Frequently Used）策略計算應(yīng)用各時間點使用概率。緩存應(yīng)用的使用時間并不僅限于一個時間點，通過以上計算可以得到緩存應(yīng)用在多個時間點的概率。不同時間點具有不同的權(quán)值，而應(yīng)用使用時間的預(yù)測為某具體時間點，多個時間點之間的優(yōu)先級值不是線性疊加關(guān)系。本文在得到緩存應(yīng)用在各時間點概率與該時間點權(quán)值乘積時，取其中的最大值作為預(yù)測回歸點，通過加權(quán)平均的方式計算時間點預(yù)測的優(yōu)先級。時間點預(yù)測算法優(yōu)先級計算過程如下：

（1）緩存應(yīng)用近期使用總數(shù)據(jù)集U，時間點集合

T={t1,t2,…,tn}；

（2）根據(jù)歷史數(shù)據(jù)集U得出緩存應(yīng)用各時間點的概率P(t),t∈T；

（3）結(jié)合各時間點的權(quán)值函數(shù)ψ(t)，得出應(yīng)用在各時間點的優(yōu)先級H(t)=ψ(t)P(t),t∈T；

（4）選擇H中的最大值作為預(yù)測回歸點，此時的時間點為回歸時間點tk；

（5）對所有時間點進行加權(quán)平均，回歸點權(quán)重為ζ，剩余所有時間點權(quán)重均為，剩余時間點集合為T′=T{tk}，因此T=

4.2 A-RBFS緩存替換策略

客戶端可以后臺運行應(yīng)用，因此當前時刻正在運行的程序可能存在多個，并且當緩存空間較大時，緩存中存在近期內(nèi)未使用的應(yīng)用，而UBP策略是基于用戶行為的緩存替換策略，只有短期內(nèi)的行為才具有信服力，故本文在UBP策略的基礎(chǔ)上提出了A-RBFS策略。其根據(jù)應(yīng)用最近一次使用時間，將緩存應(yīng)用按時間順序分為四個區(qū)域，如圖4所示，分別是Recently-Block、Behavior-Block、Frequency-Block和Size-Block，只有當該區(qū)域后面所有的緩存區(qū)域內(nèi)緩存被替換完之后才會對該區(qū)域緩存塊進行緩存剔除。不同區(qū)域的緩存塊采用不同的緩存策略：Recently-Block表示短時間內(nèi)使用的緩存應(yīng)用，采用LRU策略，最久未使用的緩存應(yīng)用將被替換；Behavior-Block表示近期內(nèi)被使用緩存應(yīng)用，采用UBP策略，根據(jù)計算得到的CBP值進行緩存替換；Frequency-Block表示短期未使用的緩存應(yīng)用，并可根據(jù)時間再劃分成多個Frequency-Block，采用最不經(jīng)常使用（Least Frequently Used，LFU）策略，將使用頻率最低的緩存應(yīng)用替換；Size-Block表示長期未使用的緩存應(yīng)用，采用Size策略，根據(jù)緩存應(yīng)用的大小，替換最大的緩存。

圖4 A-RBFS區(qū)域分布

算法2描述了A-RBFS的主要流程，根據(jù)應(yīng)用的使用時間將應(yīng)用分配到不同的Block中，按照順序依次將Block內(nèi)所有應(yīng)用加入剔除列表，直到剔除列表應(yīng)用總大小大于緩存策略待釋放的緩存空間大小，并對當前Block采用對應(yīng)的緩存替換策略，將部分低優(yōu)先級應(yīng)用添加到剔除列表。

算法2 A-RBFS緩存替換策略

輸入：待釋放的緩存空間大小Χ，根據(jù)時間劃分的有序集合B←{B1,B2,B3,B4}，緩存應(yīng)用集合Sc。

輸出：替換的緩存應(yīng)用集合S。

1.for i←1 tocard(Sc)do

2.將Sc中每個元素根據(jù)最近一次使用時間存入B的子集中

3.end for

4.k←0

5.while k＜4 do

6. if(Χ＞?(Bi))then△ ?(Bi)表示Bi中所有應(yīng)用的總大小

7. Χ←Χ-?(Bi)

8. else

9.exit

10.end if

11.k←k+1

12.end while

13.將Bk前的應(yīng)用添加到S集合中

14.對Bk中的應(yīng)用進行不同的緩存替換策略，k=1采用Size策略，k=2采用LFU策略，k=3采用UBP策略，k=4采用LRU策略

15.將替換的應(yīng)用加入到S集合

16.輸出S

5 實驗

5.1 緩存有效性測試

本文實驗設(shè)備主要包括客戶端、路由器和服務(wù)器，客戶端通過Wi-Fi接入路由器，服務(wù)器與路由器處于同一網(wǎng)段，客戶端通過NFS掛載到服務(wù)器?？蛻舳?、路由器和服務(wù)器的配置如下：

（1）客戶端為LG Nexus5，處理器為高通驍龍800（MSM8974），RAM容量2 GB，ROM容量16 GB，搭載基于Android 4.4的流式應(yīng)用分發(fā)系統(tǒng)。

（2）路由器為FW300R，300 Mb/s無線傳輸速率，符合IEEE 802.11n標準。

（3）服務(wù)器采用戴爾OptiPlex 3010商務(wù)臺式電腦，處理器為i5-3470，主頻3.2 GHz，8 GB內(nèi)存和1 TB 7 200轉(zhuǎn)機械硬盤，搭載Ubuntu 16.04操作系統(tǒng)。

通過對流式應(yīng)用分發(fā)系統(tǒng)緩存的設(shè)計，使得應(yīng)用啟動資源的獲取方式分為兩種：一種是從遠程服務(wù)器中獲取，稱之為冷啟動；另一種是從本地緩存中獲取，稱之為暖啟動。本文從Android應(yīng)用市場中選取不同大小及類別的應(yīng)用，用于測試流式應(yīng)用分發(fā)系統(tǒng)中冷啟動與暖啟動情況下的流量消耗和啟動延時。表2所示為應(yīng)用程序在冷啟動情況下的流量消耗和啟動延時。由表中數(shù)據(jù)可知，在冷啟動狀態(tài)下，應(yīng)用需要加載部分用于啟動的必備資源，而資源僅存在于服務(wù)端，因此只能通過網(wǎng)絡(luò)加載，并且在加載部分必備資源前應(yīng)用無法正常啟動，而應(yīng)用啟動的時間則取決于當前的網(wǎng)速。這不僅導(dǎo)致流量消耗增加，同時還影響用戶體驗。在暖啟動狀態(tài)下，資源存在于本地緩存中，客戶端只需要判斷緩存一致性，消耗的流量較少，并且應(yīng)用的啟動時延小于0.1 s，用戶無法感知。但是緩存并不長存于客戶端中，合適的緩存替換策略能夠增加緩存命中率，減少緩存替換次數(shù)，從而使得客戶端流量消耗和應(yīng)用延時啟動次數(shù)減少。

表2 流式應(yīng)用分發(fā)系統(tǒng)冷啟動各指標狀況

5.2 緩存替換策略性能測試

為了選取合適的緩存替換策略，本文對LFU、LRU、Size、UBP、UBP-L以及A-RBFS策略緩存性能進行測試和分析，主要測試流量消耗、命中率、緩存替換次數(shù)三方面的指標。其中，A-RBFS策略結(jié)合了LRU、UBP、LRU與Size策略。由于UBP策略只關(guān)注于分析用戶行為進行預(yù)測，而未考慮當前的客戶端應(yīng)用程序的運行狀態(tài)，因此除以上幾種策略外，還新增了UBP-L（User Behavior Prediction-Last）策略。該策略在UBP的基礎(chǔ)上增加對當前客戶端應(yīng)用程序運行狀態(tài)的考慮，即只考慮ARBFS策略中的Recently-Block與Behavior-Block。實驗數(shù)據(jù)通過Android API提供的接口，獲取志愿者60天內(nèi)的應(yīng)用使用記錄，志愿者由各年齡段各職業(yè)人員組成。在應(yīng)用使用時，通過網(wǎng)絡(luò)加載的資源緩存于本地后還將緩存于客戶端內(nèi)存中，本實驗中將客戶端運行內(nèi)存大小設(shè)為1 GB。

應(yīng)用市場中應(yīng)用品類繁多，應(yīng)用大小各不相同，為保證大部分應(yīng)用能緩存于客戶端，且緩存中能存儲若干個應(yīng)用，實驗中采取的緩存空間大小從800 MB開始，緩存開始剔除因子為0.8，結(jié)束剔除因子為0.6，即當剩余緩存空間小于20%時開始進行緩存替換，直到剩余緩存空間大于40%時剔除結(jié)束。

5.2.1 緩存流量消耗測試

圖5 緩存空間大小和流量消耗關(guān)系

圖5為不同的緩存替換策略在不同的緩存空間大小中客戶端流量消耗情況。在緩存空間較小時，客戶端中緩存應(yīng)用數(shù)量較少，需要頻繁地進行緩存替換，此時流量消耗較大。LFU與A-RBFS策略能將較為頻繁的應(yīng)用緩存到本地，故性能優(yōu)于其他緩存替換策略，但是當緩存空間增大時，LFU策略不能在短時間內(nèi)適應(yīng)用戶的興趣變化，故性能提升較小。A-RBFS策略與其他五種策略相比，隨著緩存空間不斷增大，流量消耗最先達到平衡，而在平衡狀態(tài)下緩存空間的增大對減少流量消耗的提升相對較少。在A-RBFS策略流量消耗達到平衡狀態(tài)時，緩存空間大小為1 000 MB，流量消耗方面ARBFS策略比LFU策略減少了43.07%，比LRU策略減少了41.50%，比Size策略減少了81.79%，比UBP策略減少了75.31%，比UBP-L策略減少了50.59%。

圖6為緩存空間大小為1 000 MB情況下客戶端每周流量的消耗情況。其中LFU、LRU、Size、UBP、UBP-L與A-RBFS策略平均每周流量消耗分別為1.73 GB、1.64 GB、5.15 GB、3.93 GB、2.51 GB、0.97 GB。顯而易見，A-RBFS策略平均每周的流量消耗明顯小于其他緩存替換策略，且浮動范圍較小，其日均流量消耗僅為138.07 MB，在當前的移動互聯(lián)網(wǎng)情況下，仍處于可接受范圍之內(nèi)，并且在即將到來的5G時代中，流量消耗費用將進一步降低。

圖6 一周內(nèi)用戶應(yīng)用使用流量消耗

5.2.2 緩存替換次數(shù)測試

圖7所示為不同緩存替換策略在不同的緩存空間大小中緩存替換次數(shù)關(guān)系。由于緩存的部分命中率和完全命中率只能說明應(yīng)用緩存可能長期存在于緩存中，以及流式加載中應(yīng)用加載的方式主要是從本地獲取，并不能作為衡量緩存替換策略的優(yōu)劣，因此本文選用緩存替換次數(shù)比較各替換策略性能。在緩存空間小于1 000 MB時，LRU策略緩存替換次數(shù)高于LFU策略，而當緩存空間大于1 000 MB時，LFU、LRU和UBP-L策略性能持平，Size策略由于不常使用的大小較小的應(yīng)用長存于緩存中，導(dǎo)致實際可用緩存空間較少，使得緩存替換次數(shù)相對較高，UBP策略考慮正在運行的應(yīng)用程序，導(dǎo)致頻繁的緩存替換，并且在任何大小的緩存空間下，A-RBFS策略緩存替換次數(shù)都明顯小于其他五種緩存策略。

圖7 緩存空間大小與緩存替換次數(shù)關(guān)系

圖8為緩存空間大小為1 000 MB情況下客戶端每周緩存替換的次數(shù)情況。其中LFU、LRU、Size、UBP、UBP-L和A-RBFS策略平均每周緩存替換次數(shù)分別為7.36、6.63、22.63、17.50、10.75、2.25。同樣，A-RBFS策略的緩存替換次數(shù)明顯小于其他五種策略，并且日均替換次數(shù)為0.32。

圖8 一周內(nèi)客戶端緩存替換次數(shù)

6 結(jié)束語

本文通過實現(xiàn)流式應(yīng)用分發(fā)系統(tǒng)的緩存設(shè)計，節(jié)省了客戶端流量消耗，提高了應(yīng)用啟動速度，增強了用戶體驗。在緩存替換策略上，本文提出了根據(jù)用戶行為分析，將歷史時間分為橫向的時間點和縱向的天數(shù)時間軸，預(yù)測應(yīng)用的使用時間，剔除預(yù)測可能最后使用的緩存應(yīng)用。實驗結(jié)果表明，A-RBFS能夠有效地減少流量的消耗和緩存替換次數(shù)。

應(yīng)用啟動時主要獲取的是應(yīng)用的布局、圖片和音頻等，這些資源存在于APK中而沒有對其壓縮，因此未來工作和研究的主要方向是分離出APK中的所有應(yīng)用資源，對現(xiàn)有的Android操作系統(tǒng)安裝過程中生成的所有文件直接進行掛載而無需安裝，并對影響應(yīng)用啟動的所有資源進行緩存設(shè)計。