缓存命中率
缓存命中率是我们用来衡量缓存效果的关键指标。它的计算方式是缓存命中次数除以查询总次数。在实践中,要努力把缓存命中率提高到 90% 以上。不过,缓存命中率也受到业务模式的影响,有一些业务是没有办法做到 90% 以上的。比如说有一些场景是缓存计算时间很长的结果,但是大部分请求都是小请求,也就是都不会命中缓存,这种时候缓存命中率可能连一半都没有。但是因为这些小请求计算很快,所以走实时计算响应时间也能接受,而且实时计算的数据更加准确。
实现过期机制的一般思路
从系统设计的角度来说,过期之类的机制可以考虑使用四种思路。
定时删除:是指针对每一个需要被删除的对象启动一个计时器,到期之后直接删除。
延迟队列:也就是把对象放到一个延迟队列里面。当从队列里取出这个对象的时候,就说明它已经过期了,这时候就可以删除。
懒惰删除:是指每次要使用对象的时候,检查一下这个对象是不是已经过期了。如果已经过期了,那么直接删除。
定期删除:是指每隔一段时间就遍历对象,找到已经过期的对象删除掉。
类型 | 优点 | 缺点 |
---|---|---|
定时删除 | 时间精确,对象过期后立刻就会被删除 | 定时器开销大;如果对象的过期时间被重置,需要删除原本的定时器,增加新的定时器。 |
延迟队列 | 时间精确,对象过期后立刻就会被删除 | 队列本身开销。如果对象的过期时间被重置,需要调整对象在延迟队列中的位置 |
懒惰删除 | 实现简单;重置过期时间没影响 | 时间不精确;浪费内存 |
定期删除 | 实现简单;重置过期时间没影响 | 时间不精确;性能损耗不可控 |
淘汰算法
最有名的淘汰算法是 LRU 和 LFU。除了这两种,还有最佳置换算法(OPT)和先进先出置换算法(FIFO)等,但是用得都不如 LRU 和 LFU 多,所以这里主要聊 LRU 和 LFU 这两种。
LRU
LRU(Least Recently Used)是指最近最少使用算法。也就是说,缓存容量不足的时候,就从所有的 key 里面挑出一个最近一段时间最长时间未使用的 key。这个算法从实现上来说很简单,只需要把 key 用额外的链表连起来,然后每次被访问到的 key 都挪到队尾,那么队首就是最近最长时间未访问过的 key。也可以反过来,每次访问过的挪到队首,那么队尾就是最近最久未访问过的 key。比如说你可以借助 Java 的 LinkedHashMap 轻易实现 LRU 算法。这里访问是一个含糊的说法,你可以认为读写都是访问,也可以认为只有写是访问。所以有个 LRU 的变种是只有在写的时候,才会挪动这个 key,读并不会,也就是它倾向于保留写频繁的数据。
LFU
LFU(Least Frequently Used)是最不经常使用算法,它是根据对象的使用次数来确定淘汰对象的,每次都是将使用次数最低的淘汰掉。所以基本的思路就是按照访问频率来给所有的对象排序。每次要淘汰的时候,就从使用次数最少的对象里面找出一个淘汰掉。如果有好几个对象的访问频次恰好相等,而且又是最低的,那么你可以自由决策如何淘汰。标准做法是淘汰最先插入的,不过也有一些实现就是随机删一个,又或者删掉排序位置最小的那个。实现的基本思路就是每次读写的时候,对象上面的次数都加 1,然后调整位置。这个算法也有一些变种。最主要的变种是统计一段时间内的访问次数而不是整个生命周期的次数。比如说每个对象都只统计近一个小时内的访问次数。但是这种变种的实现复杂度就要高很多。