![](https://csdnimg.cn/release/download_crawler_static/18693882/bg1.jpg)
收稿日期
作者简介 胡红 女 安徽人 华东交通大学信息工程学院硕士研究生 研究方向 移动数据库
文章编号
移 动 数 据 库 自 适 应 缓 存 失 效 算 法 的 研 究
胡 红
余为益
胡应平
华东交通大学 信息工程学院 江西 南昌 上饶师范学院 江西 上饶
南昌陆军学院 江西 南昌
摘要 在移动客户端建立缓存可以提高移动数据库系统的性能 也会带来服务器上的数据和缓存中的数据不一致的问题 即
缓存一致性问题 通常采用基于广播的缓存失效算法来维护缓存的一致性 传统的采用同步广播方式或异步广播方式的缓存
失效算法各有优缺点 该文在分析传统算法优缺点和一些现有算法的基础上 提出了一种改进的基于计数器的自适应缓存失
效算法 该算法结合了两种传统的算法 可以提高缓存的利用率 同时可以降低通信开销
关 键 词 失效报告 缓存 移动数据库 缓存一致性
中图分类号 TP 文献标识码 A
0 引言
缓存失效算法是解决缓存一致性问题的常用算
法 通常采用广播的方式发送缓存失效报告 维护缓
存数据的一致性 传统的缓存失效算法有同步广播
方式和异步广播方式两种 两者相结合的缓存失效
算法可以提高算法的效率 本文讨论的是移动客户
端的缓存管理问题 本文后面部分的客户端或客户
机如无特别说明 均指移动客户端或移动客户机
1 基于缓存失效报告的缓存管理
当客户端收到失效报告时 会将缓存中的对应
项失效 通常缓存中的每一缓存项都有一个有效位
使其失效就是将其有效位设为 invalid 用户请求某
一数据项时 客户机要确定该数据项是否在缓存中
如果在缓存中 还要判断缓存中的数据项是否有效
若有效 则用缓存内容回答查询 若无效 说明缓存
数据还未更新 则把查询提交给服务器 如果不在缓
存中 则将查询直接提交给服务器
更新的数据项的内容通常要在失效报告之后采
取广播的传送方式或经用户请求采取点对点的传送
方式 当采取广播的方式传送数据项时 客户端从广
播中下载失效的数据项对应的数据项 存入缓存中
并将使有效位设为 valid 这个过程叫做缓存的更新
过程Validate Cache 当采取点对点的方式传送时
数据项直接传送到客户端并执行缓存的更新过程
2 传统的同步 异步广播方式的缓存失效算法
同步广播方式是指服务器跟踪最近一个广播周
期内被更新的数据项 定期广播失效报告 IRInvali
dation Report 失效报告通常含有数据项 ID 和时间
戳 在连接的情况下 客户机要知道缓存项是否有
效 必须等到下一个广播周期到来时才能确定 因为
它当前知道的是上一个广播周期内数据的更新 而
当前这个广播周期内数据的更新要等到下一个广播
周期到来时才知道 在断连的情况下 当断连的时间
t W L 时 仍然可以知道缓存的有效性 其中 L
为广播周期 W 为失效广播窗口大小 而 t W L
时 就要使所有缓存项失效
异步广播方式是指 当有数据更新时就立即广
播失效报告 在连接的情况下 客户机可以在等待一
个最大传输时延从服务器知道数据更新到失效报
第 卷第 期
年 月
华 东 交 通 大 学 学 报
Journal of East China Jiaotong University
Vol No
Aug