基于用户行为的流式应用分发系统缓存设计

王辉宇，阳 旺

中南大学 计算机学院，长沙410006

1 引言

近年来，随着互联网络技术的不断发展和移动终端的技术革新，移动终端的数量与日俱增，呈现出爆炸式增长的趋势。截至2018年底，我国手机网民规模达8.17亿，网民通过手机接入互联网的比例高达98.6%[1]。用户手机安装的应用数量根据使用的手机性能的不同而有所差异。平均每台高中低端手机中安装的应用数量分别为59、50和45，而低端手机用户安装的APP数量与高中端手机有一定差距，其差距主要来源于手机内部存储（Random Access Memory，RAM）与外部存储（Read-Only Memory，ROM）的不同。虽然目前手机外存在不断地增长，但是对应的应用大小也在逐渐增大（由于业务的扩展使得应用大小增加）。因此单纯地增大外存并不能从根本上解决问题，只会增加手机的成本。对于用户而言，可能只使用应用的部分功能，因此应用大小的增加对于部分用户而言只会占用存储空间而并未改善其使用的功能。

针对以上问题，目前主流的方案是应用程序的轻量化设计。以微信小程序和Android Instant app为例的轻量化应用满足了用户小需求的及时化场景，并且无需安装，用完即走。但是轻量化应用值包含了原生应用的部分功能，导致此类应用只能作为对原生APP使用场景的一种补充，而无法替代原生APP。而流式应用分发系统[2]基于透明计算[3]的思想，采用“存储与计算分离，按需加载”的思想，用于集中存储和管理移动终端程序，从根本上释放终端的存储空间。此外，将应用存储于服务器中，移动终端无需考虑应用的安装、维护、管理、升级等问题。但是所有资源均从服务器中获取，与当前的网络状况息息相关，因此移动终端的缓存设计对流式应用分发系统而言至关重要。它通过有限的存储空间，实现无应用限制的使用。此外合理的缓存替换算法，可以增加缓存命中率，减少网络访问次数，加快应用启动速度。

2 相关工作

流式应用技术的核心是“按需加载，流式执行”，应用资源存储于远程服务器，通过流的形式按需加载到终端。文献[4]提出一种基于Android的流式应用分发系统，应用的分发由服务器管理平台处理，客户端无需执行任何操作；文献[5]在该系统上通过位置信息对其进行应用智能推荐；文献[6]提出基于情景感知的流式应用分发系统，通过对用户情景数据的收集，利用极端梯度提升算法（eXtreme Gradient Boosting，Xgboost）给用户推荐相应的应用。但是流式应用分发系统在网速受限的情况下，加载速度较慢，导致应用启动缓慢，并且在用户频繁使用应用的过程中，客户端需要不断地向服务器请求数据，容易导致高并发情况，使得服务器负载加重，而通过无线网络方式连接互联网，往往带来流量消耗的费用增加。因此，如何有效地减少客户端访问服务器的频率成为流式应用分发系统亟待解决的问题。

目前解决此类问题，主要是通过缓存设计将从网络中加载过来的资源缓存于本地。缓存设计又可分为硬件层面与软件层面。文献[7]介绍了一种基于自旋转移矩随机存储器（Spin-Transfer Torque-Magnetoresistive Random-Access Memory，STT-MRAM）的新型非易失性末级存储，该存储方案通过新颖地读出电路增强了STT-MRAM的可靠性与典型的纠错码。文献[8]基于内存驻留数据库管理系统提出将部分分解的存储和即时查询相结合的思想，消除了CPU低效的函数调用，实现了在不牺牲CPU效率的情况下节省带宽。文献[9]针对新型的非易失性存储器需要严格地按照顺序执行存储器写入导致的系统性能降低问题，提出了一种松散顺序一致性机制。其主要通过消除事务结束时执行的持久化提交记录的写入，以减少开销，允许通过推测性写入来放宽事务之间的写入顺序。

除从缓存的结构和性能指标上对缓存进行优化外，还可通过适当的缓存替换策略增加缓存命中率。文献[10]在移动透明计算系统（Transparent Computing System，TCOS）中设计了基于预取机制的缓存替换策略（Cache Replacement Algorithm based on Prefetching Mechanism，BPF-CR）。该策略设置三个不同等级的主队列，对不同队列采取不同的缓存替换策略，当下一级队列的数据再次被访问时，将移入上一级队列中，并设置副队列用于存储缓存淘汰的数据。文献[11]在实现透明手表应用程序的缓存设计时提出了N-LRU策略。该策略结合应用程序的大小、使用概率以及当前网络带宽计算策略优先级。

流式应用分发系统中各用户相互独立，用户之间数据不可共享，缓存对象为应用程序。因此挖掘用户使用应用的行为规律有利于提高流式应用的缓存命中率。文献[12]通过对Android系统中豌豆荚平台的数百万数据进行分析，研究用户使用应用的行为过程，如用户的偏好、用户对应用的选择、应用程序的生命周期等。文献[13]关注于移动应用程序之间的相互依赖性，通过数据挖掘算法对应用程序进行分类。由此可知，用户使用应用的行为具有一定的规律性。文献[14]通过对应用程序使用日志数据进行分析，预测应用的使用情况。

流式应用分发系统中缓存策略的选择需要考虑用户行为、应用使用大小等问题。由于客户端在达到缓存替换策略的触发条件时仍能进行缓存，因此缓存替换策略的执行时间应在缓存溢出前完成，故算法的复杂性可能会影响到应用的启动速度。

3 总体框架设计

3.1 框架介绍

流式应用分发系统采用的是C/S架构，如图1所示。服务器端主要是应用资源存储模块和应用推送模块，客户端主要是流式加载模块、缓存模块和缓存替换策略模块。客户端和服务器端通过无线网络进行通信。

图1 流式分发系统框架

服务器端的功能主要是存储应用资源，管理用户个人信息，并且根据用户的需求将应用推送给客户端。在服务器端和客户端之间，通过无线网络进行交互，其中主要有两部分资源的交互：第一部分为网络文件系统（Network File System，NFS）[15]，应用资源通过NFS加载网络资源，客户端在通过NFS访问服务器资源时，如同访问本地资源；第二部分为文本通信，主要通信的内容是待安装或卸载的应用程序少量信息，如文件名，采用的是消息队列遥测传输（Message Queuing Telemetry Transport，MQTT）协议[16]，它是一个发布/订阅者模式的协议，并且通信消耗的网络流量几乎可以忽略不计。

客户端主要是流式加载来自服务器的资源，在本地进行安装运行，缓存是在流式加载的过程中将资源保存到本地主存中，进行持久化存储，缓存替换在缓存大小达到一定值后会被触发，将优先级低的缓存块替换。缓存替换算法的优劣直接影响应用缓存的频率，从而影响客户端流量的消耗、应用启动的时延等。

3.2 系统实现原理

在原生的Android系统中，应用被下载之后首先会被拷贝到/data/app/下（系统级应用安装在/system/app/下），并通过监听机制inotify监听该目录。而在流式应用分发系统中，APK文件存储于服务器，因此在本地创建一个与/data/app/同级的新目录/data/metaosapp/，并通过NFS实现挂载。由于metaosapp文件夹资源来自于服务器，当该文件内容发生变化，客户端只有在主动更新文件内容时文件属性才会发生变化，此时才能被inotify监听到。因此，本文通过MQTT实现客户端与服务器之间的通信，当服务器向该挂载目录中删除或添加应用时，通知客户端更新目录，从而执行安装卸载命令。客户端/data/data/目录用于存储用户使用应用的信息，同上，创建新目录/data/metaosdata/并实现网络化。

3.3 缓存实现原理

流式应用分发系统的缓存设计主要是为了缓存客户端通过NFS从服务器中加载的资源，而在Linux内核中，提供了FS-Cache[17]用于实现网络文件系统缓存。Android操作系统基于Linux内核，因此本文通过FSCache实现流式应用分发系统缓存设计。

FS-Cache在文件系统缓存中只是作为一个缓存接口，其实际的缓存操作交由缓存后端CacheFiles[18]实现，通过CacheFiles管理缓存文件和目录，可以将从网络文件系统中加载的资源永久缓存于本地。CacheFiles缓存后端主要包括cachefilesd守护进程和cachefiles模块。cachefilesd用于cachefiles模块的管理，如初始化相关信息、监听目录文件等。cachefiles模块则通过接收cachefilesd指定执行相关操作，如目录文件创建、缓存生成等。

图2为流式应用缓存实现原理。客户端首先启动应用程序，然后CacheFiles判断缓存是否命中与一致性，若缓存命中且客户端与服务器缓存资源一致，则直接从缓存中获取资源，否则，通过NFS按需加载，同时将从服务器加载的资源缓存于本地。当缓存空间不足时，则执行缓存替换操作，当应用启动资源加载完毕后，应用便可正常使用。

图2 流式应用缓存实现

CacheFiles缓存替换策略的触发通过设置三组参数实现，如表1所示。与传统的缓存空间设置不同，Cache-Files缓存替换策略并非在缓存溢出时触发，而是在缓存空间使用率达到某一条件时触发，直至满足另一条件时结束。触发条件主要由两部分组成——实际缓存空间大小与文件存储数量。并且通过bstop/fstop参数的设置，可以使得缓存剔除操作与缓存生成同时进行，以避免等待缓存替换所花费的时间。

表1 缓存替换策略触发参数

缓存空间只是客户端存储空间的一部分，缓存替换的触发除了达到缓存空间上限之外，同时还考虑了客户端的剩余存储空间。在满足客户端可用存储空间足够时，会自适应调节缓存空间的总大小，以提高客户端存储空间的利用率和缓存替换算法的命中率。其主要是通过调节上述三组参数的数值以控制缓存剔除的开启与关闭。

4 缓存替换策略

4.1 用户行为预测策略

本文缓存设计的对象为应用程序，而应用的使用者为用户，根据调研发现，用户使用应用时具有主观意识，而CacheFiles默认使用的最近最少使用策略（Least Recently Used，LRU）仅考虑缓存块的访问时间，因此无法有效地提高缓存命中率。而本文中，缓存块的主体是应用程序，主体的使用者是用户，因此可以根据用户的使用行为预测应用的使用时间，故本文提出了用户行为预测（User Behavior Prediction，UBP）缓存替换策略。该策略通过记录应用启动时间并分析预测应用下次的使用时间。

UBP缓存替换策略从时间预测上分为两类：一类是预测当前可能会运行的应用程序，因为存在部分应用，在使用时通常会和某些应用同时使用，所以可以根据其中某一应用的启动预测另一应用可能会被使用；另一类是预测应用下次使用时间，通常用户会在某种特定的场景下使用某些应用。根据这些特点，对历史记录中各时间点应用的使用情况进行分析，替换缓存中预测时间距当前时间最久的应用。

UBP策略将应用的使用时间分为两部分：一个是横向时间轴，表示时间点，单位毫秒；另一个是纵向时间轴，表示天数，单位日。纵向的时间轴用于预测事件在某时间点的发生概率或可信度。对所有时间点进行加权平均，得到应用的预测值。由于存在部分应用得到的预测值相同，如某些应用使用时间完全相同，因此预测值并不能完全区分应用的优先级，故UBP策略除了对应用进行预测，同时还对应用的使用时长进行统计。如图3所示，综合四种子策略的优先级值，得出UBP策略的CBP（Combined Behavior Prediction，CBP）值，用于量化该应用缓存在不久将来使用的可能性。

图3 UBP缓存替换策略

4.1.1 关联性规则

为了挖掘用户在不同时间使用的应用之间的关联性，本文采用加权频繁项集算法[19]挖掘不同时间点应用之间的关联性。算法核心是通过当前时间点正在运行的应用预测将可能使用的应用。

应用关联性挖掘的是正在运行程序的应用与缓存中应用的关联性，因此对于数据集中的频繁项只需要包含当前正在运行的应用或缓存中的应用。每个频繁项的使用时间不同，因此对应用的关联性采取加权频繁项集挖掘。

算法1关联性规则算法

输入：所有时间点集合T←{T1,T2,…,Tm}，各时间点集合Tt←{D1,D2,…,Dn}。

输出：关联性规则优先级R。

1.N←0

2.for t←1 to m do

3.提取某时间点t的历史数据作为数据集Tt，对每个项集进行处理，只保留相关应用（运行中的应用和缓存中的应用），得到L1

4.根据最小支持度min sup筛选L1得到C1，并从C1中提取两个集合Su与Sc，其中Su←{fi,fi+1,…,fj}表示C1中运行的应用集合，Sc←{fx,fx+1,…,fy}表示C1中缓存的应用集合

5.通过C1将Su和Sc元素组合得到L2，并根据最小支持度得到C2

6.if L2表不为空then

7. Rt←{confidence(fi⇒fk)|fi∈Su},fk为缓存中的应用，则fk在时间点t的关联性规则值为Rt中的最大值Rt

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

9.end if

10.end for

11.R←R/N

12.Rc表示当前时间点的关联性规则算法优先级，R取R和Rc中的最大值

13.输出R

如算法1所示，首先对数据集进行扫描，得到频繁一项集L1，再根据最小支持度min sup得到一阶候选项集C1，将存在于C1中的运行应用和缓存应用组合，重复前面的步骤得到频繁二项集L2以及二阶候选项集C2，通过C2求出每个运行中应用对缓存应用的置信度，取其最大值。根据以上步骤，对所有时间点的最大置信度取平均值。为保证当前时间点具有更高的信任度，再将求得的平均值和当前时间点的最大置信度相比，将两者中的较大值作为关联性规则优先级。

4.1.2 时间点预测

关联性规则只能用于预测即将要被使用的应用，但是缓存中大部分的应用可能并不会立刻被使用，因此还需对缓存中的应用下次使用的时间进行预测。

时间点预测主要通过分析历史记录中各时间点使用应用的分布情况，得出各时间点的使用概率。由于某时间点的应用使用概率需要同时考虑使用次数以及使用时间，本文采用LRFU（Least Recently Frequently Used）策略计算应用各时间点使用概率。缓存应用的使用时间并不仅限于一个时间点，通过以上计算可以得到缓存应用在多个时间点的概率。不同时间点具有不同的权值，而应用使用时间的预测为某具体时间点，多个时间点之间的优先级值不是线性叠加关系。本文在得到缓存应用在各时间点概率与该时间点权值乘积时，取其中的最大值作为预测回归点，通过加权平均的方式计算时间点预测的优先级。时间点预测算法优先级计算过程如下：

（1）缓存应用近期使用总数据集U，时间点集合

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

（2）根据历史数据集U得出缓存应用各时间点的概率P(t),t∈T；

（3）结合各时间点的权值函数ψ(t)，得出应用在各时间点的优先级H(t)=ψ(t)P(t),t∈T；

（4）选择H中的最大值作为预测回归点，此时的时间点为回归时间点tk；

（5）对所有时间点进行加权平均，回归点权重为ζ，剩余所有时间点权重均为，剩余时间点集合为T′=T{tk}，因此T=

4.2 A-RBFS缓存替换策略

客户端可以后台运行应用，因此当前时刻正在运行的程序可能存在多个，并且当缓存空间较大时，缓存中存在近期内未使用的应用，而UBP策略是基于用户行为的缓存替换策略，只有短期内的行为才具有信服力，故本文在UBP策略的基础上提出了A-RBFS策略。其根据应用最近一次使用时间，将缓存应用按时间顺序分为四个区域，如图4所示，分别是Recently-Block、Behavior-Block、Frequency-Block和Size-Block，只有当该区域后面所有的缓存区域内缓存被替换完之后才会对该区域缓存块进行缓存剔除。不同区域的缓存块采用不同的缓存策略：Recently-Block表示短时间内使用的缓存应用，采用LRU策略，最久未使用的缓存应用将被替换；Behavior-Block表示近期内被使用缓存应用，采用UBP策略，根据计算得到的CBP值进行缓存替换；Frequency-Block表示短期未使用的缓存应用，并可根据时间再划分成多个Frequency-Block，采用最不经常使用（Least Frequently Used，LFU）策略，将使用频率最低的缓存应用替换；Size-Block表示长期未使用的缓存应用，采用Size策略，根据缓存应用的大小，替换最大的缓存。

图4 A-RBFS区域分布

算法2描述了A-RBFS的主要流程，根据应用的使用时间将应用分配到不同的Block中，按照顺序依次将Block内所有应用加入剔除列表，直到剔除列表应用总大小大于缓存策略待释放的缓存空间大小，并对当前Block采用对应的缓存替换策略，将部分低优先级应用添加到剔除列表。

算法2 A-RBFS缓存替换策略

输入：待释放的缓存空间大小Χ，根据时间划分的有序集合B←{B1,B2,B3,B4}，缓存应用集合Sc。

输出：替换的缓存应用集合S。

1.for i←1 tocard(Sc)do

2.将Sc中每个元素根据最近一次使用时间存入B的子集中

3.end for

4.k←0

5.while k＜4 do

6. if(Χ＞∂(Bi))then△ ∂(Bi)表示Bi中所有应用的总大小

7. Χ←Χ-∂(Bi)

8. else

9.exit

10.end if

11.k←k+1

12.end while

13.将Bk前的应用添加到S集合中

14.对Bk中的应用进行不同的缓存替换策略，k=1采用Size策略，k=2采用LFU策略，k=3采用UBP策略，k=4采用LRU策略

15.将替换的应用加入到S集合

16.输出S

5 实验

5.1 缓存有效性测试

本文实验设备主要包括客户端、路由器和服务器，客户端通过Wi-Fi接入路由器，服务器与路由器处于同一网段，客户端通过NFS挂载到服务器。客户端、路由器和服务器的配置如下：

（1）客户端为LG Nexus5，处理器为高通骁龙800（MSM8974），RAM容量2 GB，ROM容量16 GB，搭载基于Android 4.4的流式应用分发系统。

（2）路由器为FW300R，300 Mb/s无线传输速率，符合IEEE 802.11n标准。

（3）服务器采用戴尔OptiPlex 3010商务台式电脑，处理器为i5-3470，主频3.2 GHz，8 GB内存和1 TB 7 200转机械硬盘，搭载Ubuntu 16.04操作系统。

通过对流式应用分发系统缓存的设计，使得应用启动资源的获取方式分为两种：一种是从远程服务器中获取，称之为冷启动；另一种是从本地缓存中获取，称之为暖启动。本文从Android应用市场中选取不同大小及类别的应用，用于测试流式应用分发系统中冷启动与暖启动情况下的流量消耗和启动延时。表2所示为应用程序在冷启动情况下的流量消耗和启动延时。由表中数据可知，在冷启动状态下，应用需要加载部分用于启动的必备资源，而资源仅存在于服务端，因此只能通过网络加载，并且在加载部分必备资源前应用无法正常启动，而应用启动的时间则取决于当前的网速。这不仅导致流量消耗增加，同时还影响用户体验。在暖启动状态下，资源存在于本地缓存中，客户端只需要判断缓存一致性，消耗的流量较少，并且应用的启动时延小于0.1 s，用户无法感知。但是缓存并不长存于客户端中，合适的缓存替换策略能够增加缓存命中率，减少缓存替换次数，从而使得客户端流量消耗和应用延时启动次数减少。

表2 流式应用分发系统冷启动各指标状况

5.2 缓存替换策略性能测试

为了选取合适的缓存替换策略，本文对LFU、LRU、Size、UBP、UBP-L以及A-RBFS策略缓存性能进行测试和分析，主要测试流量消耗、命中率、缓存替换次数三方面的指标。其中，A-RBFS策略结合了LRU、UBP、LRU与Size策略。由于UBP策略只关注于分析用户行为进行预测，而未考虑当前的客户端应用程序的运行状态，因此除以上几种策略外，还新增了UBP-L（User Behavior Prediction-Last）策略。该策略在UBP的基础上增加对当前客户端应用程序运行状态的考虑，即只考虑ARBFS策略中的Recently-Block与Behavior-Block。实验数据通过Android API提供的接口，获取志愿者60天内的应用使用记录，志愿者由各年龄段各职业人员组成。在应用使用时，通过网络加载的资源缓存于本地后还将缓存于客户端内存中，本实验中将客户端运行内存大小设为1 GB。

应用市场中应用品类繁多，应用大小各不相同，为保证大部分应用能缓存于客户端，且缓存中能存储若干个应用，实验中采取的缓存空间大小从800 MB开始，缓存开始剔除因子为0.8，结束剔除因子为0.6，即当剩余缓存空间小于20%时开始进行缓存替换，直到剩余缓存空间大于40%时剔除结束。

5.2.1 缓存流量消耗测试

图5 缓存空间大小和流量消耗关系

图5为不同的缓存替换策略在不同的缓存空间大小中客户端流量消耗情况。在缓存空间较小时，客户端中缓存应用数量较少，需要频繁地进行缓存替换，此时流量消耗较大。LFU与A-RBFS策略能将较为频繁的应用缓存到本地，故性能优于其他缓存替换策略，但是当缓存空间增大时，LFU策略不能在短时间内适应用户的兴趣变化，故性能提升较小。A-RBFS策略与其他五种策略相比，随着缓存空间不断增大，流量消耗最先达到平衡，而在平衡状态下缓存空间的增大对减少流量消耗的提升相对较少。在A-RBFS策略流量消耗达到平衡状态时，缓存空间大小为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，在当前的移动互联网情况下，仍处于可接受范围之内，并且在即将到来的5G时代中，流量消耗费用将进一步降低。

图6 一周内用户应用使用流量消耗

5.2.2 缓存替换次数测试

图7所示为不同缓存替换策略在不同的缓存空间大小中缓存替换次数关系。由于缓存的部分命中率和完全命中率只能说明应用缓存可能长期存在于缓存中，以及流式加载中应用加载的方式主要是从本地获取，并不能作为衡量缓存替换策略的优劣，因此本文选用缓存替换次数比较各替换策略性能。在缓存空间小于1 000 MB时，LRU策略缓存替换次数高于LFU策略，而当缓存空间大于1 000 MB时，LFU、LRU和UBP-L策略性能持平，Size策略由于不常使用的大小较小的应用长存于缓存中，导致实际可用缓存空间较少，使得缓存替换次数相对较高，UBP策略考虑正在运行的应用程序，导致频繁的缓存替换，并且在任何大小的缓存空间下，A-RBFS策略缓存替换次数都明显小于其他五种缓存策略。

图7 缓存空间大小与缓存替换次数关系

图8为缓存空间大小为1 000 MB情况下客户端每周缓存替换的次数情况。其中LFU、LRU、Size、UBP、UBP-L和A-RBFS策略平均每周缓存替换次数分别为7.36、6.63、22.63、17.50、10.75、2.25。同样，A-RBFS策略的缓存替换次数明显小于其他五种策略，并且日均替换次数为0.32。

图8 一周内客户端缓存替换次数

6 结束语

本文通过实现流式应用分发系统的缓存设计，节省了客户端流量消耗，提高了应用启动速度，增强了用户体验。在缓存替换策略上，本文提出了根据用户行为分析，将历史时间分为横向的时间点和纵向的天数时间轴，预测应用的使用时间，剔除预测可能最后使用的缓存应用。实验结果表明，A-RBFS能够有效地减少流量的消耗和缓存替换次数。

应用启动时主要获取的是应用的布局、图片和音频等，这些资源存在于APK中而没有对其压缩，因此未来工作和研究的主要方向是分离出APK中的所有应用资源，对现有的Android操作系统安装过程中生成的所有文件直接进行挂载而无需安装，并对影响应用启动的所有资源进行缓存设计。