概念分析

       LFU(Least Frequently Used)即最近最不常用.看名字就知道是个基于访问频次的一种算法。以前写过几篇关于用python实现lru算法的模块,有兴趣的朋友可以看看。 LRU是基于时间的,会将时间上最不常访问的数据给淘汰,在算法表现上是放到列表的顶部;LFU为将频率上最不常访问的数据淘汰.既然是基于频率的,就需要有存储每个数据访问的次数.从存储空间上,较LRU会多出一些持有计数的空间.

       LFU算法认为”如果数据过去访问频率很高,那么将来被访问的频率也很高“.  其实我个人对于缓存用的最多的是 Lru和Fifo ,LFU更加偏向于随机性比较大的场景。

我擦,最近爬虫很是凶猛呀  标记下文章的原文   http://xiaorui.cc


下面的图我是从别人那边偷来的….别打我

 

 下面简单讲解一下:

  1. 假设我们的lfu最大的存储空间控制为5个,此时访问D,D现在的访问频率计数是26;
  2. 访问D后,D的频率+1,也就是27了。 此时需要调整缓存池数据需要重新排序,D和C交换;
  3. 访问B,B的频率+1,由于A的频率仍然比B大,所以不需要调整;
  4. 当新数据F插入缓存池之前,由于已经空间满了,需要干掉一个! 因为E的频率最低,故淘汰E,将F插入缓存池,缓存池重新排序,F放到队尾.

3.优略分析

 【命中率

命中率方面还是要看你的应用的场景     大多数的场景下,一旦访问内容发生较大变化,LFU需要用更长的时间来适应,因为他是往队列的下面塞入,如果一定时间内对于新数据的访问频次量不够的话,后面再继续的不断的推入新的数据,根据Lfu的算法,被干掉的肯定是那些刚刚被推进来的,还没有被多次访问的那堆数据了。(历史的频率记录会是这些污染数据保持较长的一段时间)  ,这也是为啥大多数人用Lru的原因。

 【复杂度

需要维护所有的访问记录的频率数据结构,实现较LRU复杂.

 【存储成本

需要维护所有的访问记录的频率数据结构.

 【缺陷

仅仅从最近访问频率上考虑淘汰算法,可能会淘汰一些仍有价值的单元.内存和性能消耗较高.  

下面的是用python实现Lfu缓存算法的装饰器。  脚本里面增加了随机的访问的概念统计,Lfu非常适合这种随机性比较大,跟时间没太多关系的缓存。代码我已经推送到了pypi里面,有兴趣的朋友可以直接安装  



对Python及运维开发感兴趣的朋友可以加QQ群 : 478476595 !!!
{ 2000人qq大群内有各厂大牛,常组织线上分享及沙龙,对高性能及分布式场景感兴趣同学欢迎加入该QQ群 }

另外如果大家觉得文章对你有些作用!   帮忙点击广告. 一来能刺激我写博客的欲望,二来好维护云主机的费用.
如果想赏钱,可以用微信扫描下面的二维码. 另外再次标注博客原地址  xiaorui.cc  ……   感谢!
暂无相关产品