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

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

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