一种移动透明计算系统中的双缓存协作策略

王大成, ,,

(中南大学 信息科学与工程学院,长沙 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.