彩铃铃音服务器缓存算法的设计与实现

论文摘要

随着彩铃业务的成熟和发展，如何有效地存储和管理大容量的铃音数据成为了一个重要的技术问题。本文提出新增铃音服务器网元作为集中式铃音数据存储方案，利用高效的磁盘缓存算法满足了系统设计容量的要求。该方案的重点是缓存算法的设计与实现。首先，在理想环境下建立了缓存分配的数学模型，用动态规划算法给出了理想模型的最优解；为了进一步提高速度和减少空间消耗，针对理想模型的特点用贪婪算法得到了模型的近似最优解。其次，通过分析现网中实际的彩铃铃音订阅数据，为铃音流行度建立了数学模型，证明了铃音播放流行度服从Zipf分布的结论，并利用该结论对经典缓存算法LRU（Least Recently Used）和LFU（Least Frequently Used）进行了分析和验证。针对经典算法的不足和铃音服务器应用的特点，本文创新性地提出了一种新的缓存替换算法LFU-EA（LFU with Exponential Aging），该算法采用指数平滑公式作为频率老化机制，使用灵活的手段来平衡资源访问模式中的频率特性和时间特性，能够很好地与缓存周期性替换模型结合起来，适宜应用在磁盘缓存系统中。实验结果表明LFU-EA算法比经典算法的缓存命中率提高了10％左右。为了有效地实现LFU-EA算法，我们引入了受限二叉堆数据结构用于快速过滤大量铃音文件，并实现了应用双散列技术的通用散列容器，该技术从理论上有效地保证了高负载下容器的性能不会退化，适宜应用在对实时性要求很高的场合。实验证明该容器比标准容器速度更快并且占用更少的内存空间。最后，详细介绍了具体实现中的负载均衡策略，给出了应用Reactor模式和Leader／Followers模式作为软件并发架构的理由，讨论了容错机制的设计等等问题。本文提出的流行度建模技术和缓存替换算法LFU-EA对于其它的磁盘缓存系统也有良好的借鉴意义。

论文目录

• 摘要
• ABSTRACT
• 第1章 彩铃业务与铃音服务器
• 1.1 彩铃业务的发展
• 1.1.1 彩铃市场和用户规模增长
• 1.1.2 彩铃铃音资源增长
• 1.2 彩铃业务呼叫处理流程
• 1.2.1 目标网方案
• 1.2.2 普通彩铃呼叫的正常处理流程
• 1.2.3 智能用户彩铃呼叫的正常处理流程
• 1.3 彩铃平台组网结构
• 1.4 铃音服务器
• 1.5 铃音传输协议
• 1.5.1 NFS协议的优点
• 1.5.2 NFS协议性能测试
• 1.6 系统容量的估算
• 1.7 本章小结
• 第2章 模型的建立与求解
• 2.1 理想模型
• 2.1.1 理想缓存分配模型
• 2.1.2 理想缓存分配模型的近似解法
• 2.2 预测模型
• 2.2.1 铃音播放流行度建模与Zipf分布
• 2.2.2 铃音订阅次数和铃音播放次数的关系
• 2.2.3 服从Zipf分布内在原因的初步解释
• 2.3 本章小结
• 第3章 缓存算法设计
• 3.1 经典缓存替换算法
• 3.1.1 LRU策略
• 3.1.2 LFU策略
• 3.1.3 LRU和LFU对Zipf访问模式的模拟结果
• 3.1.4 经典缓存替换算法的不足
• 3.2 一种新的缓存替换算法
• 3.2.1 LFU算法的缓存污染问题
• 3.2.2 适用于铃音磁盘缓存的LFU-EA算法
• 3.2.3 缓存周期性替换模型
• 3.2.4 算法验证
• 3.3 本章小结
• 第4章 关键数据结构和算法实现
• 4.1 缓存信息的存储结构
• 4.2 通用散列容器的设计
• 4.2.1 好的散列函数的原则
• 4.2.2 双散列技术
• 4.2.3 散列函数的选择
• 4.3 通用散列容器的实现
• 4.3.1 实现通用散列函数接口
• 4.3.2 散列桶和散列元素的抽象
• 4.3.3 利用内存池优化内存管理
• 4.3.4 关于自动增长特性
• 4.4 通用散列容器性能测试
• 4.5 并发访问控制
• 4.6 本章小结
• 第5章 系统实现
• 5.1 系统架构
• 5.1.1 部署视图及工作流程
• 5.1.2 铃音播放统计协议
• 5.1.3 负载均衡策略
• 5.2 并发模型
• 5.2.1 Reactor模式
• 5.2.2 Leader/Followers模式
• 5.3 软件模块实现
• 5.3.1 模块划分
• 5.3.2 通用组件
• 5.3.3 应用层组件
• 5.3.4 关于产生唯一ID
• 5.4 缓存一致性
• 5.5 容错设计
• 5.6 本章小结
• 结束语
• 参考文献
• 致谢