[转][转]Redis、Memcached、Guava、Ehcache中的算法

标签: | 发表时间:2015-04-07 02:56 | 作者:heiyeshuwu
出处:http://blog.csdn.net/heiyeshuwu


缓存那些事,一是内存爆了要用LRU(最近最少使用)、LFU(最少访问次数)、FIFO的算法清理一些;二是设置了超时时间的键过期便要删除,用主动或惰性的方法。

 

1. LRU

简单粗暴的Redis

今天看 Redis3.0的发行通告里说,LRU算法大幅提升了,就翻开源码来八卦一下,结果哭笑不得,这旧版的"近似LRU"算法,实在太简单,太偷懒,太Redis了。

Github的Redis项目里搜索lru,找到代码在redis.c的freeMemoryIfNeeded()函数里。

先看 2.6版的代码: 竟然就是随机找三条记录出来,比较哪条空闲时间最长就删哪条,然后再随机三条出来,一直删到内存足够放下新记录为止.......可怜我看 配置文档后的想象,一直以为它会帮我在整个Redis里找空闲时间最长的,哪想到我有一百万条记录的时候,它随便找三条就开始删了。

好,收拾心情再看 3.0版的改进:现在每次随机五条记录出来,插入到一个长度为十六的按空闲时间排序的队列里,然后把排头的那条删掉,然后再找五条出来,继续尝试插入队列.........嗯,好了一点点吧,起码每次随机多了两条,起码不只在一次随机的五条里面找最久那条,会连同之前的一起做比较......

中规中矩的Memcached

相比之下,Memcached实现的是再标准不过的LRU算法,专门使用了一个教科书式的双向链表来存储slab内的LRU关系,代码在 item.c里,详见 memcached源码分析-----LRU队列与item结构体,元素插入时把自己放到列头,删除时把自己的前后两个元素对接起来,更新时先做删除再做插入。

分配内存超限时,很自然就会从LRU的队尾开始清理。

同样中规中矩的Guava Cache

Guava Cache同样做了一个双向的Queue,见 LocalCache中的AccessQueue类,也会在超限时从Queue的队尾清理,见 evictEntries()函数

和Redis一样懒的Ehcache

文档,居然和Redis2.6一样,直接随机8条记录,找出最旧那条,刷到磁盘里,再看代码, Eviction类 和  OnHeapStore的evict()函数,的确如此。

小结

不过后来再想想,也许Redis本来就不是主打做Cache的,这种内存爆了需要通过LRU删掉一些元素不是它的主要功能,默认设置都是noeviction——内存不够直接报错的,所以就懒得建个双向链表,而且每次访问时都要更新它了,看Google Group里长长的讨论,新版算法也是社区智慧的结晶。但Ehache是专门做Cache的呀,也这么懒。

 

2. 过期键删除

如果能为每一个设置了过期的元素启动一个Timer,一到时间就触发把它删掉,那无疑是能最快删除过期键最省空间的,在Java里用一条 DeplayQueue存着,开条线程不断的读取就能做到。但因为该线程消耗CPU较多,在内存不紧张时有点浪费,似乎大家都不用这个方法。

所以有了惰性检查,就是每次元素被访问时,才去检查它是否已经超时了,这个各家都一样。但如果那个元素后来都没再被访问呢,会永远占着位子吗?所以各家都再提供了一个定期主动删除的方式。

Redis

代码在 redis.c的activeExpireCycle()里,看过文档的人都知道,它会在主线程里,每100毫秒执行一次,每次随机抽20条Key检查,如果有1/4的键过期了,证明此时过期的键可能比较多,就不等100毫秒,立刻开始下一轮的检查。不过为免把CPU时间都占了,又限定每轮的总执行时间不超过1毫秒。

Memcached

Memcached里有个文不对题的 LRU爬虫线程,利用了之前那条LRU的队列,可以设置多久跑一次(默认也是100毫秒),沿着列尾一直检查过去,每次检查LRU队列中的N条数据。虽然每条Key设置的过期时间可能不一样,但怎么说命中率也比Redis的随机选择N条数据好一点,但它没有Redis那种过期的多了立马展开下一轮检查的功能,所以每秒最多只能检查10N条数据,需要自己自己权衡N的设置。

Guava Cache

在Guava Cache里,同一个Cache里所有元素的过期时间是一样的,所以它比Memached更方便,顺着之前那条LRU的Queue检查超时,不限定个数,直到不超时为止。而且它这个检查的调用时机并不是100毫秒什么的,而是每次各种写入数据时的 preWriteCleanup()方法中都会调用。

吐槽一句,Guava的Localcache类里面已经4872行了,一点都不轻量了。

Ehcache

Ehcache更乱,首先它的内存存储中只有惰性检查,没有主动检查过期的,只会在内存超限时不断用近似LRU算法(见上)把内存中的元素刷到磁盘中,在文件存储中才有超时检查的线程, FAQ里专门解释了原因。

然后磁盘存储那有一条8小时左右跑一次的线程,每次遍历所有元素.....见 DiskStorageFactory里的DiskExpiryTask。 一圈看下来,Ehcache的实现最弱。


文章来源:http://calvin1978.blogcn.com/articles/lru.html


作者:heiyeshuwu 发表于2015/4/6 18:56:12 原文链接
阅读:39 评论:0 查看评论

相关 [redis memcached guava] 推荐:

[转][转]Redis、Memcached、Guava、Ehcache中的算法

- - heiyeluren的blog(黑夜路人的开源世界)
缓存那些事,一是内存爆了要用LRU(最近最少使用)、LFU(最少访问次数)、FIFO的算法清理一些;二是设置了超时时间的键过期便要删除,用主动或惰性的方法. 今天看 Redis3.0的发行通告里说,LRU算法大幅提升了,就翻开源码来八卦一下,结果哭笑不得,这旧版的"近似LRU"算法,实在太简单,太偷懒,太Redis了.

转 redis vs memcached

- - 数据库 - ITeye博客
传统MySQL+ Memcached架构遇到的问题.   实际MySQL是适合进行海量数据存储的,通过Memcached将热点数据加载到cache,加速访问,很多公司都曾经使用过这样的架构,但随着业务数据量的不断增加,和访问量的持续增长,我们遇到了很多问题:.   1.MySQL需要不断进行拆库拆表,Memcached也需不断跟着扩容,扩容和维护工作占据大量开发时间.

谈谈Memcached与Redis

- - 互联网旁观者
Memcached是以LiveJurnal旗下Danga Interactive公司的Bard Fitzpatric为首开发的高性能分布式内存缓存服务器. 其本质上就是一个内存key-value数据库,但是不支持数据的持久化,服务器关闭之后数据全部丢失. Memcached使用C语言开发,在大多数像Linux、BSD和Solaris等POSIX系统上,只要安装了libevent即可使 用.

Redis和Memcached的区别

- - 互联网 - ITeye博客
Redis和Memcache都是将数据存放在内存中,都是内存数据库. 不过memcache还可用于缓存其他东西,例如图片、视频等等. Redis不仅仅支持简单的k/v类型的数据,同时还提供list,set,hash等数据结构的存储. 虚拟内存--Redis当物理内存用完时,可以将一些很久没用到的value 交换到磁盘.

Redis和Memcached的区别

- - 标点符
Redis的作者Salvatore Sanfilippo曾经对这两种基于内存的数据存储系统进行过比较:. Redis支持服务器端的数据操作:Redis相比Memcached来说,拥有更多的数据结构和并支持更丰富的数据操作,通常在Memcached里,你需要将数据拿到客户端来进行类似的修改再set回去.

Twemproxy——针对MemCached与Redis的代理

- - InfoQ cn
Twemproxy是一个代理服务器,可以通过它减少 Memcached或 Redis服务器所打开的连接数. Twemproxy有何用途呢. 通过代理的方式减少缓存服务器的连接数. 自动在多台缓存服务器间共享数据. 通过不同的策略与散列函数支持一致性散列. 运行在多个实例上,客户端可以连接到首个可用的代理服务器.

Guava cache

- - 孟飞阳的博客
Guava Cache是一个全内存的本地缓存实现,它提供了线程安全的实现机制. 整体上来说Guava cache 是本地缓存的不二之选,简单易用,性能好.    Guava Cache有两种创建方式:.   通过这两种方法创建的cache,和通常用map来缓存的做法比,不同在于,这两种方法都实现了一种逻辑——从缓存中取key X的值,如果该值已经缓存过了,则返回缓存中的值,如果没有缓存过,可以通过某个方法来获取这个值.

[转][转]Twemproxy——针对MemCached与Redis的代理

- - heiyeluren的blog(黑夜路人的开源世界)
Twemproxy是一个代理服务器,可以通过它减少 Memcached或 Redis服务器所打开的连接数. Twemproxy有何用途呢. 通过代理的方式减少缓存服务器的连接数. 自动在多台缓存服务器间共享数据. 通过不同的策略与散列函数支持一致性散列. 通过配置的方式禁用失败的结点. 运行在多个实例上,客户端可以连接到首个可用的代理服务器.

百万级运维经验二:Redis和Memcached的选择

- - CSDN博客系统运维推荐文章
看到很多人推荐使用Redis代替Memcached,我觉得这两个是不一样的东西,它们的关系应该是共存而不是替代. Memcached是个纯内存型的缓存系统,支持数据类型单一,单个缓存数据有限制,支持分布式,我觉得这是个很理想的缓存系统. Redis是个简单的NOSQL数据库,支持几种简单的数据类型,支持主从复制,支持持久化,可以看作是个内存型数据库.

读取memcached和redis中的数据,分析缓存数据大小

- - BlogJava-首页技术区
    最近项目快要见人了,所以很多性能分析的需求又提出来了. 之前已经做过几次类似的事情,这次记录下来把.     Memcached不能一次性读取所有的key,不能一次性读取缓存数据. 以前项目里面踩过这个坑,stats cachedump $slabId $limit只会dump出2M的key,如果所有的key超多2M那么dump出哪些key就要看命了.