Redis 面试必备 > reids 内存过期和数据持久化机制
redis为什么使用近似的LRU

Redis LRU 有个很重要的点,你通过调整每次回收时检查的采样数量,以实现调整算法的精度。这个参数可以通过以下的配置指令调整:

maxmemory-samples 5

Redis 为什么不使用真实的 LRU 实现是因为这需要太多的内存。不过近似的 LRU 算法对于应用而言应该是等价的。使用真实的LRU 算法与近似的算法可以通过下面的图像对比。

用于生成图像的 Redis 服务被填充了指定数量的键。这些键将被从头到尾访问,所以当使用LRU算法时第一个键是最佳的回收候选键。接着添加超过50%的键,用于强制旧键被回收。

你可以看到三种点在图片中, 形成了三种带.

  • 浅灰色带是已经被回收的对象。

  • 灰色带是没有被回收的对象。

  • 绿色带是被添加的对象。

  • 在 LRU 实现的理论中,我们希望的是,在旧键中的第一半将会过期。Redis的LRU算法则是概率的过期旧的键。

你可以看到,在都是五个采样的时候 Redis 3.0 比 Redis 2.8 要好,Redis2.8 中在最后一次访问之间的大多数的对象依然保留着。使用10个采样大小的 Redis 3.0 的近似值已经非常接近理论的性能。

注意 LRU 只是个预测键将如何被访问的模型。另外,如果你的数据访问模式非常接近幂定律,大部分的访问将集中在一个键的集合中,LRU 的近似算法将处理得很好。


什么是幂定律

1932年,哈佛大学的语言学专家Zipf在研究英文单词出现的频率时,发现如果把单词出现的频率按由大到小的顺序排列,则每个单词出现的频率与它的名次的常数次幂存在简单的反比关系,这种分布就称为Zipf定律,它表明在英语单词中,只有极少数的词被经常使用,而绝大多数词很少被使用.实际上,包括汉语在内的许多国家的语言都有这种特点。


19世纪的意大利经济学家Pareto研究了个人收入的统计分布,发现少数人的收入要远多于大多数人的收入,提出了著名的80/20法则,即20%的人口占据了80%的社会财富.个人收入X不小于某个特定值x的概率与x的常数次幂亦存在简单的反比关系,即为Pareto定律。


Zipf定律与Pareto定律都是简单的幂函数,我们称之为幂律分布;还有其它形式的幂律分布,像名次—规模分布,规模—概率分布,这四种形式在数学上是等价的。近似  f(x) = 1/x 的图像

幂律分布表现为一条斜率为幂指数的负数的直线,这一线性关系是判断给定的实例中随机变量是否满足幂律的依据。


实际上,幂律分布广泛存在于物理学、地球与行星科学、计算机科学、生物学、生态学、人口统计学与社会科学,经济与金融学等众多领域中,且表现形式多种多样。在自然界与日常生活中,包括地震规模大小的分布(古登堡-里希特定律),月球表面上月坑直径的分布,行星间碎片大小的分布,太阳耀斑强度的分布,计算机文件大小的分布,战争规模的分布,人类语言中单词频率的分布,大多数国家姓氏的分布,科学家撰写的论文数的分布,论文被引用的次数的分布,网页被点击次数的分布,书籍及唱片的销售册数或张数的分布,每类生物中物种数的分布,甚至电影所获得的奥斯卡奖项数的分布等,都是典型的幂律分布。 以网页被点击次数的分布为例,尽管中国向七千九百万网民提供的网站接近六十万个,但只有为数不多的网站,才拥有网民一次访问难以穷尽的丰富内容,拥有接纳许多人同时访问的足够带宽,进而有条件演化成热门网站,拥有极高的点击率,像新浪、搜狐、网易等门户网站。网页被点击次数的幂律分布其幂指数在0.60-1.03之间,而网站访问量的幂律分布其幂指数则接近1。克里斯·安德森的“长尾理论”即是幂律的口语化表达。