计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (18): 90-98.DOI: 10.3778/j.issn.1002-8331.1707-0250

• 大数据与云计算 • 上一篇    下一篇

Redis压缩列表研究与优化设计

张慧宁1,李拥军2,王绍东3   

  1. 1.广东石油化工学院 实验教学部,广东 茂名 525000
    2.华南理工大学 计算机科学与工程学院,广州 510006
    3.腾讯科技有限公司 MIG安全云部,广东 深圳 518000
  • 出版日期:2018-09-15 发布日期:2018-10-16

Research and optimization design of Redis ziplist

ZHANG Huining1, LI Yongjun2, WANG Shaodong3   

  1. 1.Department of Experimental Teaching, Guangdong University of Petrochemical Technology, Maoming, Guangdong 525000, China
    2.College of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China
    3.MIG Security Cloud Department, Tencent Technology Co. Ltd., Shenzhen, Guangdong 518000, China
  • Online:2018-09-15 Published:2018-10-16

摘要: 针对Redis压缩列表(ziplist)更新机制在最坏情况下存在连锁更新问题,透彻分析Redis压缩列表更新机制实现原理,提出两种优化方案,方案一,通过优化连锁更新算法,将其修改为基于统计的顺序遍历更新机制,有效解决压缩列表在出现连锁更新情况下,时间复杂度较高的问题。新机制将更新时间复杂度由[O(N2)]下降为[O(N)],当出现大量节点的连锁更新时,消耗时间与无连锁更新时插入节点的时间接近。方案二,通过优化压缩列表节点结构体,消除了连锁更新现象,从而减少了由于连锁更新带来的额外时间,相比优化更新函数,性能更好。实验表明新方案在不影响原有功能情况下,优化效果显著。

关键词: Redis, 压缩列表, 连锁更新, 优化

Abstract: Aiming at solving the chain update problem exists in Redis ziplist update mechanism in the worst case, after thoroughly analyzing realization principle of Redis ziplist update mechanism, two kinds of optimization schemes are proposed, scheme one, by optimizing the chain update algorithm, modify it to sequential traversal update mechanism based on statistics, which is an effective solution for the problem of high time complexity when chain update occurs in Redis ziplist. The new mechanism reduces the update time complexity from [O(N2)] to [O(N)]. When there is a chain update of a large number of nodes, consumption of time spent is close to the time which the node is inserted without chain update. Scheme two, by optimizing the compression list node structure, eliminates the chain update phenomenon, thereby reducing the additional time due to the chain update. Comparing with optimizing the update function, it has better performance. Experiments show that the new scheme brings remarkable optimization effect without affecting the original function.

Key words: Redis, ziplist, chain update, optimization