移动客户机中缓存技术的应用研究

摘要：在移动计算环境中，移动性和断接性是它的最主要的两个特点。为了支持断接操作，数据时常需要先存储到移动客户机中。缓存技术成为移动计算环境中的重要技术。本文研究了基于广播技术中客户机端缓存的管理技术，讨论了缓存管理的粒度问题、缓存一致性策略和缓存替换策略三个关键问题。

关键词：移动环境；数据缓存；广播技术

中图分类号：TP311文献标识码：A文章编号：1009-3044(2007)18-31657-02

Research on Application of Caching Technology in Mobile Client

ZENG Li-juan,LOU Song-tao

(Henan Vocational Technicol College Department of Information Engineering,Zhengzhou 450012,China)

Abstract:In the mobile computing environment, mobility and disconnection are the two important characters. In order to support disconnect operation, some datum are often need to store into mobile clients in advance. Caching becomes the very important technology in the mobile environment. This paper researches the caching technique based on broadcasting. Three key issues of mobile cache management such as caching granularity, coherence strategy and replacement policy were discussed.

Key words: mobile environment;data caching;broadcasting technique

1 引言

随着互联网的不断延伸和无线接入技术的快速发展，人们希望能在任何时间、任何地点、访问任何数据的需求已逐渐成为现实，信息系统正在走出传统的机房与桌面，帮助用户随时随地获取相关信息，做出正确决策。因此，一种新的移动数据库管理系统应运而生并迅速发展起来，它不仅能够管理移动终端本地的数据与信息，而且还能连接中心数据库处理各种企业事务，满足用户在移动环境下的各种信息处理需求。

由于移动计算环境是传统的基于固定网络的分布式计算环境的扩展，所以除了必须解决传统分布式计算环境的所有问题外，还必须考虑计算终端的移动性、网络连接的断接性以及上下行网络链路的不对称性等问题。

缓存技术在传统的分布式数据库中得到了广泛的应用，它通过在客户机上缓存部分数据，减少了对数据库服务器的访问，提高了性能 但传统的缓存技术要求客户机保持与服务器的连接，以维护缓存的一致性。在移动计算环境中，由于无线网络带宽的不足和网络的频繁断接性，传统的缓存技术并不适应移动数据库中的缓存管理，因此必须寻求新的解决方案。所以，为了使移动客户机(mobile Eliot，MC)在断接状态下可以继续访问数据库中的数据，减少因为断接或网络延迟而造成的无谓的损失，研究支持断接操作的客户端缓存技术是十分必要的。

2 移动缓存中的三大关键问题及解决方案

2.1 CM的工作状态

MC缓存的核心问题是缓存管理器（cache manager,CM）。CM在MC上缓存服务器数据库的一个子集。为了支持移动用户的断接操作，CM具有3种不同的工作状态：联机状态、脱机状态和集成状态。根据与服务器的网络连接状况的不同，CM将在这3种状态之间转换。如下图1所示。

(1)联机状态：当移动客户端在联机状态下，缓存处于收集状态，依靠与中心数据库的同步服务器上的数据复制工作，并且随时准备进去断接状态。

(2)断接状态：当移动客户端断接时，依靠缓存中的数据满足移动客户端用户的数据访问需要，直到重新联机为止。

(3)集成状态：当移动客户端与中心服务器重新联机的时候，缓存进入集成状态，缓存内容通过同步服务器与中心数据库通过一定的同步策略进行同步，然后重新进机状态。

图1 MC缓存管理器的状态转换

2.2 缓存管理器机制的3个关键性技术

2.2.1缓存粒度问题

传统的C/S环境下的缓存机制通常都是基于页面的，但是在移动计算环境中，基于页面的缓存粒度不适合移动缓存管理。

(1)移动计算环境中，由于无线网络的低带宽，大多采用数据广播技术，移动终端通过接收广播的热点数据建立移动数据缓存。这种情况下，某个MC端基于页面缓存的局部性大的页面在另外一个MC端局部性可能很小。

(2)由于移动终端自身资源的限制性，如果以页面为缓存粒度，在访问局部性比较低的情况下，需要在低带宽的无线网络环境下传输较长的时间。

高能耗和低的响应时间使得我们寻求比页面小的缓存粒度。我们考虑到可以以记录缓存、属性缓存、混合缓存作为粒度单位。分别说明如下： ①记录缓存：向表中插入一条记录时候，该记录的每一个属性数据都有存储。也就是说，在向服务器请求数据建立客户缓存的时候，需要传输整条记录的数据，此时，缓存的数据有一部分对用户来说是冗余的；② 属性缓存：向表中插入记录的时候，只对用户频繁访问的属性数据进行存储。在向服务器请求数据建立客户缓存的时候，只需要传输用户可能感兴趣的属性数据；③混合缓存：根据用户访问的实际情况，对某些表的缓存采用记录缓存，对另外的某些表采用属性缓存，这种方式称为混合缓存。

2.2.2缓存的替换策略

由于移动终端的缓存容量很有限，当空间已满而且需要增加新的数据时，就需要应用缓存替换策略。

基于移动数据库数据广播的固有特点，客户机引入了基于代价的缓存替换策略。即替换算法需要考虑缓存不命中时，从数据广播中获得一个对象的代价。在多盘广播环境中，获得广播频率越高的磁盘中的数据项的代价越小，获得广播频率越高的磁盘中的数据项的代价越小。因此，考虑了一个较为理想的算法：PIX算法结合考虑了对象的广播频率，即将访问概率P与广播频率X的比值作为替换的衡量因子，选择P/X值最小的对象进行替换。例如，考虑两个对象M和N。M的访问概率为10%，广播频率是5%；N的访问概论为5%，广播频率是1%。由于M的PIX值小于N的PIX值，因此即使M具有更高的访问概率，当缓存已满时PIX算法仍选把M替换掉。这是由于客户机通过广播获得对象N的代价要比获得对象M的代价大（N的广播频率低）。

PIX算法在理论上是合理的，但在实际应用中，需要比较所有缓存对象的PIX值，代价过高。因此，采用了一种PIX和LRU相结合的算法，LIX算法。此算法是在LRU算法的基础上，加入了对象的广播频率因素。与LRU算法类似，LIX算法也采用栈结构实现替换，不同的是栈结构按广播频率划分。每个广播磁盘对应一个栈，每个缓存对象都被放入它所在的广播磁盘所对应的栈中。与LRU算法相同，若该对象被命中，将其移到栈顶。当发生缓存不命中且缓存已满时，LIX算法只需比较每个栈的栈底对象的LIX值，将其中LIX值最小的对象替换出缓存。

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文

图2演示了一个两盘广播中LIX算法的缓存替换过程。

图2 LIX算法缓存替换过程示意图

服务器一共有两个磁盘，相应的，客户机端的缓存也组织成两个栈。栈I中有对象a，b，c，根据访问概率排列，a位于栈顶，c位于栈底。栈2中有对象d, e，f，g，h。d位于栈顶，h位于栈底。假定缓存的空间仅可存放9个数据项，则缓存已满。现在若客户机需要访问数据项x，客户机首先在本地缓存中搜寻，发现没有，则到广播中获取。因为缓存已满，为了将获取的数据放入缓存，需要进行缓存替换。由于一个栈中具有最小LlX值的数据项一般在栈底，因此只需要比较两个栈的栈底数据项的LIX值，即c和h的LIX。若c的LIX值是0．4，h的LIX值是0．6，将c替换出去，但因为Z的广播频率属于磁盘2，所以将z置于栈2的顶端。

模拟分析和实际应用的结果都表明，在多盘广播中，采用LIX算法的客户机缓存性能要优于采用LRU算法的缓存性能， 而且单个客户机的本地访问概率分布和服务器的总体访问概率分布相差越大，这种性能优势就越明 。

2.2.3缓存一致性问题

移动数据库的特点决定了移动客户机上的缓存数据和数据服务器上的数据之间的一致性问题更加复杂。考虑到应用的实际情况，我们把一致性分为强一致性和弱一致性。缓存一致性问题的目标就是维护移动客户机缓存和固定数据库服务器数据之间的一致性。强一致性要求查询事务读取的值是数据服务器的最新值，要求更新事务立即提交；弱一致性可以在本地的缓存上执行。所以，如果客户机和数据库服务器之间处于联机状态，则缓存管理可以提供强一致性：如果处于断接状态下，缓存管理提供弱一致性。

客户端缓存数据的一致性问题的主要内容包括两个方面：① 服务器端数据的修改要及时通知到各个客户机并更改缓存中的内容。由服务器端数据的修改导致缓存数据的更新我们称为缓存数据的被动更新；② 客户端修改的数据要及时通知到服务器并及时提交修改，这种由客户端缓存内数据的更改提交到数据库服务器最终修改我们称为缓存数据的主动更新。

通常情况下，利用缓存数据的被动更新来实现缓存的一致性的效率更高。这种方式主要通过服务器定期广播各种信息来实现缓存一致性。广播的信息包括实际数据、数据的更新信息、锁表和日志等控制信息，广播不需要服务器知道移动客户机当前的位置和连接状态，移动客户机也无需建立与服务器的上行链路和发送数据请求，从而节约了能量，而且无需额外的开销，广播的信息就可以被许多移动用户接收。在这种方式中，缓存一致性直接取决于广播的频率，广播越频繁，缓存更新就越及时，缓存的一致性就会越高

3 结束语

移动数据库技术的研究与实现，是一个崭新的课题，至今还有许多问题有待解决。本文围绕移动数据库中一个重要的技术，缓存技术，讨论了该技术的一些重要指标。提出了缓存粒度的选取问题，缓存替换策略的一个算法和分析了缓存一致性所涉及到的一些问题。但在特定的应用环境下，可能还会面临到特殊的问题，需要进一步的研究。

参考文献：

[1]王珊,丁治明,张孝.移动数据库及其应用[J].计算机应用,2002,20(9):1-4.

[2]周恒.移动计算环境中的Cache技术研究.中国科学院软件研究所,2001.

[3]李霖,周兴铭.移动数据库中客户机的断接操作[J].计算机科学,1999,26(2):5-9.

[4]Ken C K,Leong H V,Antonio S.Semantic Query Caching Mobile Environment.Mobile Computing and Communications Review,1999,3(2):28-36.

[5]E Pitoura,G Samaras．Data Management for Mobile Computing[M].Kiuwer Academic Publishers,1997.

[6]Qun Ren,Dunham MH. Using Clustering for Effective Management of a Semantic Cache in Mobile Computing.In Proceedings of the International Workshop of Mobile,1999:94-101.

[7]X Sun,N N Kamel,L M Ni Processing implication on queries IEEE Trans on Software Engineering,1989,15(10):1168-1175.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文