移动数据库缓存模型研究

摘要：

针对移动数据库系统性能有待提高的问题，提出了一种移动数据库缓存模型。采用基于消息摘要的同步算法，通过比较移动客户端与服务器消息摘要表中的消息摘要值，完成缓存同步，维护移动客户端缓存与服务器数据的一致性；该模型还考虑了数据的时效性与事务的优先级，设计了一种基于价值函数的缓存替换算法。实验结果表明，随着缓存数据个数的增加，所提算法的缓存命中率高于最近最少使用（LRU）和LA2U算法，同时随着访问频率的增加，事务的重启率低于LRU和LA2U，有效提高了移动数据库缓存的性能。

关键词：

移动数据库；缓存同步；缓存替换；一致性；数据有效性

0引言

在移动环境中，由于移动设备的移动性以及无线网络的不稳定，会有断连的情况出现，同时，移动设备没有过多的计算能力，并且还依靠电池。由于无线网络较窄的带宽，持久并稳定的访问网络是很难的[1-2]。移动设备在断连时使用缓存数据来处理多种任务。对于移动数据库，支持网络断开操作这一条件是关键[3]。而移动设备的存储能力必定不能与服务器相提并论，因此使用缓存替换技术相当重要。在断连的环境下，移动客户端和服务器都可以对数据进行操作，故两者存在不可避免的冲突。同步技术可以解决数据不一致，并保证数据的完整性，是移动数据库系统中的重要课题[4]。

移动数据库系统中要满足在断连的情况，移动客户端也能够进行操作，移动数据库需要采用复制缓存技术，与之相关的研究已有一些成果。

文献[5]提出的两级复制考虑了移动数据库计算环境中可信网络部分和无线不可靠网络部分的性能差异，能有效地解决移动计算环境中频繁断连的问题。其缺点是暂态事务要在基节点上重做，增加了系统的负荷。

文献[6]提出了根据数据的读写频率进行复制的动态复制算法。如果在移动数据库系统中对数据的读取很频繁，就选择大量的复制数据副本，这样缓存的命中率大大提高，同时还能减少服务的负载；如果在移动端对数据的更新操作很频繁，此时应该适当降低数据的复制，减少冲突，避免降低数据的更新速度。

文献[7]中的平均机制，通过衡量每个对象的访问频率来决定替换的数据。访问频率也可以通过平均访问时间衡量，当一个对象拥有最高的平均访问时间，则它被替换。这个方法的缺点是它对于数据更新的反应比较迟缓。

Acharya等[8]依据三级复制[9]中所具有的广播环境特点提出了一种实用缓存替换算法——LIX算法。该算法是在LRU（Least Recently Used）的基础上，充分考虑了广播频率对缓存的影响，LIX算法也是采用栈结构，不同于LRU算法的是，每个广播磁盘都有相对应的一个栈，而LIX维护的不是一个栈，是一组栈。缓存对象存放在栈中，栈与广播磁盘是相对应的。如果该缓存对象被命中，则将它移至栈顶。如果缓存没有命中，且缓存已经满了，LIX算法只比较每个栈中栈底对象的LIX值，其中LIX值最小的对象将被替换出缓存。每次缓存替换时，LIX算法的计算量只是一个常数值。当单个移动客户机的访问概率和服务器广播调度中采用的概率分布相差较大时，LIX算法的性能就越明显。

文献[10]中的LA2U（Least AccesstoUpdate Ratio）缓存替换算法是将客户端对数据的访问次数与服务器对同一数据的更新次数的比值作为衡量标准，选取比值大的数据放入缓存替换比值较小的数据。而LAUD（Least AccesstoUpdate Difference）替换策略是将查询频率与修改频率的差值作为衡量标准，选取差值大的数据放入缓存，将差值小的对象替换出去。这两个算法与传统分布式缓存替换的共同点是都考虑了访问频率，不同之处是LA2U和LAUD还将数据的更新频率列入考虑，因此这两种策略的核心思想是将修改频率高查询频率低的数据对象替换出去，选取修改频率低而查询频率又高的数据对象替换进来。LA2U是将客户端对数据的访问次数与服务器对同一数据的更新次数的比值作为衡量标准，选取比值大的数据放入缓存替换掉比值较小的数据。

本文的主要内容是设计了一个缓存模型，模型包括缓存的粒度、缓存同步以及缓存替换三个部分。本文选择元组为缓存粒度，采用了基于消息摘要的同步算法，设计了一种基于数据时效性与事务优先级的缓存替换算法，并通过实验验证了该模型中算法的有效性。

1缓存模型

如果一个移动设备的存储容量无限，那么就可以向移动客户端申请缓存所有的数据，显然在实际情况中，这是不现实的。缓存的粒度是缓存的基本问题，它可以优化缓存能力，因此，缓存粒度的选择对缓存模型有明显的影响。决定了缓存的粒度之后，下一步是要选择缓存同步算法，目的是要保持缓存的一致性。目前，已经有许多的缓存同步算法。移动客户端缓存命中率下降，客户端想添加一些新的数据缓存，此时就需要采用缓存替换算法来清除一些数据，为新的缓存数据腾出空间。据此，本文设计的缓存模型包括缓存粒度、缓存的同步以及缓存的替换。

1.1缓存粒度

对于缓存粒度的选择，移动数据库系统中缓存的粒度可以是一行记录，也可以是属性。如果是以记录为缓存，需要传输整条记录的数据，此时缓存数据对部分用户来说是冗余的。而属性粒度是只存储用户频繁访问的属性数据，显然，移动客户端能够缓存更多的数据，有效利用有限的存储空间，网络开销相对来说较小，响应速度相对来说更快。其缺点是单一以属性作为粒度，缓存的命中率较低，且不利于同步。

以元组为缓存粒度时，移动客户端保存有元组中的每一个属性，这样的好处是能大大地提高缓存的命中率，而且，在移动客户端与服务器进行缓存同步的时候，将一行记录作为粒度更方便。因此，为了方便缓存同步，本文将元组，也即一行记录作为缓存粒度[11]。

1.2同步算法

本文设计的缓存模型中采用文献[12]提出的基于消息摘要的缓存同步算法（Synchronization Algorithm based on Message Digest， SAMD）。该算法是采用比较消息摘要值的方式，通过两个消息摘要表中的标志值分析不一致的类型，然后使用主键来确定需要同步的那行数据。

基于消息摘要的算法将大量的数据压缩成一个消息摘要值，只需比较每行的消息摘要值，数据不一致性的检测得到简化，并最大限度地减少了存储空间的浪费。而且消息摘要函数的工作速度快，因此，对于计算能力较弱的移动客户端，负担也减少了。同步过程中，使用SQL批量处理查询移动客户端消息摘要表中的数据，查询结果通过网络发送到服务器端的数据库。这样，对移动客户端产生的负载是较小的，从而降低了网络访问所造成的开销。

但是该算法要维护一个单独的消息摘要表，从存储效率的角度来说，这是一个缺点。但SAMD算法不使用触发器、存储过程或时间戳。由于数据库设备厂商的独立性，SAMD算法能用于服务器端数据库和移动数据库的任意组合。SAMD只使用由国际标准化组织（International Organization for Standardization， ISO）的认证的标准的SQL语句，因此SAMD又具有可扩展性、适应性和灵活性等优点。

2缓存替换算法

缓存模型中的第三个主要内容是缓存替换。缓存替换算法的作用是当空间已满需要腾出缓存空间时如何选择缓存中被替换的数据。对于缓存中的数据，哪些数据在断连时一定不会用到，哪些数据必须得留下，移动用户自身也不能完全确定。如果将缓存中被频繁访问的数据替换出去，会降低缓存的命中率，影响缓存的性能。

2.1算法设计与分析