基于用戶行為的流式應(yīng)用分發(fā)系統(tǒng)緩存設(shè)計(jì)

王輝宇，陽(yáng) 旺

中南大學(xué) 計(jì)算機(jī)學(xué)院，長(zhǎng)沙410006

1 引言

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

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

2 相關(guān)工作

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

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

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

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

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

3 總體框架設(shè)計(jì)

3.1 框架介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 緩存替換策略

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

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

UBP緩存替換策略從時(shí)間預(yù)測(cè)上分為兩類：一類是預(yù)測(cè)當(dāng)前可能會(huì)運(yùn)行的應(yīng)用程序，因?yàn)榇嬖诓糠謶?yīng)用，在使用時(shí)通常會(huì)和某些應(yīng)用同時(shí)使用，所以可以根據(jù)其中某一應(yīng)用的啟動(dòng)預(yù)測(cè)另一應(yīng)用可能會(huì)被使用；另一類是預(yù)測(cè)應(yīng)用下次使用時(shí)間，通常用戶會(huì)在某種特定的場(chǎng)景下使用某些應(yīng)用。根據(jù)這些特點(diǎn)，對(duì)歷史記錄中各時(shí)間點(diǎn)應(yīng)用的使用情況進(jìn)行分析，替換緩存中預(yù)測(cè)時(shí)間距當(dāng)前時(shí)間最久的應(yīng)用。

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

圖3 UBP緩存替換策略

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

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

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

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

輸入：所有時(shí)間點(diǎn)集合T←{T1,T2,…,Tm}，各時(shí)間點(diǎn)集合Tt←{D1,D2,…,Dn}。

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

1.N←0

2.for t←1 to m do

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

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

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

6.if L2表不為空then

7. Rt←{confidence(fi?fk)|fi∈Su},fk為緩存中的應(yīng)用，則fk在時(shí)間點(diǎn)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表示當(dāng)前時(shí)間點(diǎn)的關(guān)聯(lián)性規(guī)則算法優(yōu)先級(jí)，R取R和Rc中的最大值

13.輸出R

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

4.1.2 時(shí)間點(diǎn)預(yù)測(cè)

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

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

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

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

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

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

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

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

4.2 A-RBFS緩存替換策略

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

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

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

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

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

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

1.for i←1 tocard(Sc)do

2.將Sc中每個(gè)元素根據(jù)最近一次使用時(shí)間存入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.對(duì)Bk中的應(yīng)用進(jìn)行不同的緩存替換策略，k=1采用Size策略，k=2采用LFU策略，k=3采用UBP策略，k=4采用LRU策略

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

16.輸出S

5 實(shí)驗(yàn)

5.1 緩存有效性測(cè)試

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

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

（2）路由器為FW300R，300 Mb/s無(wú)線傳輸速率，符合IEEE 802.11n標(biāo)準(zhǔn)。

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

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

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

5.2 緩存替換策略性能測(cè)試

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

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

5.2.1 緩存流量消耗測(cè)試

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

圖5為不同的緩存替換策略在不同的緩存空間大小中客戶端流量消耗情況。在緩存空間較小時(shí)，客戶端中緩存應(yīng)用數(shù)量較少，需要頻繁地進(jìn)行緩存替換，此時(shí)流量消耗較大。LFU與A-RBFS策略能將較為頻繁的應(yīng)用緩存到本地，故性能優(yōu)于其他緩存替換策略，但是當(dāng)緩存空間增大時(shí)，LFU策略不能在短時(shí)間內(nèi)適應(yīng)用戶的興趣變化，故性能提升較小。A-RBFS策略與其他五種策略相比，隨著緩存空間不斷增大，流量消耗最先達(dá)到平衡，而在平衡狀態(tài)下緩存空間的增大對(duì)減少流量消耗的提升相對(duì)較少。在A-RBFS策略流量消耗達(dá)到平衡狀態(tài)時(shí)，緩存空間大小為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。顯而易見(jiàn)，A-RBFS策略平均每周的流量消耗明顯小于其他緩存替換策略，且浮動(dòng)范圍較小，其日均流量消耗僅為138.07 MB，在當(dāng)前的移動(dòng)互聯(lián)網(wǎng)情況下，仍處于可接受范圍之內(nèi)，并且在即將到來(lái)的5G時(shí)代中，流量消耗費(fèi)用將進(jìn)一步降低。

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

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

圖7所示為不同緩存替換策略在不同的緩存空間大小中緩存替換次數(shù)關(guān)系。由于緩存的部分命中率和完全命中率只能說(shuō)明應(yīng)用緩存可能長(zhǎng)期存在于緩存中，以及流式加載中應(yīng)用加載的方式主要是從本地獲取，并不能作為衡量緩存替換策略的優(yōu)劣，因此本文選用緩存替換次數(shù)比較各替換策略性能。在緩存空間小于1 000 MB時(shí)，LRU策略緩存替換次數(shù)高于LFU策略，而當(dāng)緩存空間大于1 000 MB時(shí)，LFU、LRU和UBP-L策略性能持平，Size策略由于不常使用的大小較小的應(yīng)用長(zhǎng)存于緩存中，導(dǎo)致實(shí)際可用緩存空間較少，使得緩存替換次數(shù)相對(duì)較高，UBP策略考慮正在運(yùn)行的應(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é)束語(yǔ)

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

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