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

摘要：

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

关键词：热点敏感、跳跃表、强化学习、SARSA、奖励塑形

所属期刊栏目：42

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金项目71672074

在线出版日期：2021-01-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：1-14