一种热点敏感的自适应跳跃表

• 作者: 刘丽霞 吉锋 文韬
• 来源期刊: 西南大学学报（自然科学版）
• 学科: 工学
• 关键词: 热点敏感 跳跃表 强化学习 SARSA 奖励塑形
• 年，卷（期）: 2020,（12）
• 所属期刊栏目: “大数据与行业应用”专题
• 页码范围: 1-14
• 页数: 14页
• 分类号: TP391
• 语种: 中文
• DOI: 10.13718/j.cnki.xdzk.2020.12.001

摘要

研究了利用访问局部性原理提升跳跃表查询效率的问题,同时研究了以上加速策略的自适应机制.首先改进了跳跃表查询操作,令其额外返回在特定层次上的访问路径子集;其次利用蓄水池采样对跳跃表查询操作进行采样,然后根据采样结果对跳跃表特定层次的工作负载进行预测,根据工作负载选择热点区域,在热点区域设置加速点以提升查询效率;最后根据查询效率的提升程度和系统负载变化情况,利用SARSA算法和奖励塑形机制自动调节加速点层级和规模,以达到查询加速和管理成本之间的平衡.实验证明:在访问倾斜的跳跃表应用场景下,该方法相比原生跳跃表查询算法有更低的延迟,在访问模式逐步变化的应用场景下,该方法能够随环境变化灵活调整加速策略.