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

来源：计算机工程与应用杂志2018年第18期北京时间：

作者：张慧宁1，李拥军2，王绍东3

单位：1.广东石油化工学院 实验教学部，广东 茂名 525000；2.华南理工大学 计算机科学与工程学院，广州 510006；3.腾讯科技有限公司 MIG安全云部，广东 深圳 518000

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

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