用Redis玩转环形数组，性能提升其实没那么难理解

（引用来源：阿里云开发者社区文章《用Redis玩转环形数组，性能提升其实没那么难理解》）

你有没有遇到过这样一种情况：你的程序需要记录最近发生的100件事情，比如最近的100条用户操作日志，或者一个聊天窗口里最新的50条消息，最简单的方法是什么呢？很多人可能会想到用一个普通的列表（List）或者数组（Array）来存，新来一条，就往里加一条，但当数量超过上限，比如超过了100条，你就得把最老的那条删掉,这样才能保证列表里始终是最新的100条。

这个方法行不行？当然行，但如果这个列表访问非常频繁，每秒都有成千上万次读写，这个“删除最老数据”的操作就会变成一个性能瓶颈，因为你每次删除数组头部的元素，后面的所有元素都需要向前移动一位来填补空缺，数据量小的时候感觉不到，一旦数据量大、操作频繁,这种开销就非常可观了。

这时候，Redis里的一个数据结构——列表（List），配合其特定的命令，就能用一种非常巧妙的方式解决这个问题，这种方法的思想就很像我们常说的“环形数组”或者“循环缓冲区”。

什么是环形数组呢？你可以把它想象成一个圆环，这个圆环被分成了固定数量的小格子，比如10个，一开始，所有格子都是空的,我们用一个指针指向当前要写入数据的位置。

当第一个数据来的时候，我们把它放进指针指向的第一个格子，然后指针向前移动一格。 第二个数据来，放进第二个格子，指针再移动。 …… 当第11个数据来的时候，指针已经走完一圈，又回到了第一个格子的位置，这时候，我们不会去费力地把后面所有的数据都挪动一遍，而是直接“覆盖”掉第一个格子里那个最老的数据，然后把指针指向下一个格子（第二个格子）。

就这样，指针在这个环上不停地转圈，新数据总是覆盖掉最老的数据，这个圆环里，永远保存着最新的N条数据，这种方法的好处是，无论进行多少次插入操作，永远只是在固定位置进行写入和指针移动，不会引起大规模的数据搬迁，所以速度极快,性能非常稳定。

我们来看看Redis是怎么实现这个思想的，Redis的List结构支持一些非常强大的操作，其中两个关键命令是LPUSH和LTRIM。

• LPUSH key value：这个命令的作用是，将一个或多个值从列表的左边（头部）插入。
• LTRIM key start stop：这个命令是用来“修剪”列表的，它只保留指定下标范围内的元素,之外的元素全部删除。

聪明的你可能已经想到了组合方式,我们可以这样操作：

1. 每来一条新消息，我们先用LPUSH命令把它从列表的左边推进去，这样,最新的数据永远在列表的最前面。
2. 紧接着，我们执行一条命令：LTRIM key 0 99，这条命令的意思是：只保留列表中下标从0到99的这100个元素,剩下的全部扔掉。

因为LPUSH是从左边插入的，所以第100个元素就是列表里最老的数据。LTRIM 0 99执行后，如果列表长度超过了100，那么第101个及以后的元素（也就是更老的数据）就会被自动清除掉。

你看，这两个命令连续执行，效果就和我们手动维护一个环形数组一模一样：插入新元素，同时如果超出了容量限制，就丢弃最老的元素，这一切都是在Redis这个高性能的内存数据库中完成的，速度非常快，这两个操作是一个原子性的动作吗？单个命令是原子的，但两个命令组合在一起并不是，不过在绝大多数场景下，即使中间被其他命令打断，结果也依然是“列表大致保持了最新的N个元素”，是可以接受的，如果要求极强的原子性，可以用Redis的事务（例如MULTI/EXEC）或者Lua脚本来保证。

这种用Redis实现环形数组的方式，性能提升到底体现在哪里呢？其实核心就是避免了“数据搬运”。

回想一下我们开头说的普通数组的做法，它需要实实在在地在内存里移动大量数据，而Redis的LPUSH和LTRIM组合，本质上只是修改了列表的头尾指针（Redis内部的实现机制更复杂，但可以这么理解），并释放掉过期数据的内存，这是一个常量时间复杂度的操作（O(1)），与列表的长度无关，无论你的环形数组容量是100还是10万，这个“插入并修剪”的操作速度几乎是一样的。

总结一下，当你需要维护一个“仅保留最新N条记录”的集合时，用Redis的List配合LPUSH和LTRIM命令，是一个非常经典且高效的模式，它把繁琐的数据结构维护工作交给了Redis这个“专家”，让你的应用代码变得简洁，同时获得了极致的内存操作性能，这种性能提升的本质，就是用指针的移动和内存的分配回收，替代了昂贵的数据块搬运,道理其实一点也不难理解。