看Ehcache是如何实现LRU,LFU，以及惰性删除过期KEY
站长
· 阅读数 39
大家好，我是小趴菜，之前讲过使用Spring Cache作为本地缓存实现简单，但是有太多缺点，比如实现缓存淘汰，今天我们来讲讲Ehcache这个本地缓存是如何基于LRU,LFU来实现缓存淘汰的
如何使用
在resources目录下新建ehcache2.xml文件
<?xml version="1.0" encoding="UTF-8"?>
<ehcache xmlns:xsi = "http://www.w3.org/2001/XMLSchema-instance"
xsi:noNamespaceSchemaLocation = "http://ehcache.org/ehcache.xsd"
updateCheck = "false">
<!-- 磁盘缓存位置 -->
<diskStore path="d:\ehcache2"/>
<!-- 默认缓存 -->
<defaultCache
eternal="false"
maxEntriesLocalHeap="1000"
timeToIdleSeconds="3600"
timeToLiveSeconds="1800"
overflowToDisk="true"
memoryStoreEvictionPolicy = "LRU">
</defaultCache>
<!-- 此缓存最多可以存活timeToLiveSeconds秒，如果期间超过timeToIdleSeconds秒未访问，缓存失效 -->
<cache
name = "userCache"
eternal = "false"
maxElementsInMemory = "4"
overflowToDisk = "false"
diskPersistent = "false"
timeToIdleSeconds = "120"
timeToLiveSeconds = "180"
memoryStoreEvictionPolicy = "LRU"/>
<!-- maxElementsInMemory 内存中最大缓存对象数，看着自己的heap大小来搞 -->
<!-- eternal：true表示对象永不过期，此时会忽略timeToIdleSeconds和timeToLiveSeconds属性，默认为false -->
<!-- maxElementsOnDisk：硬盘中最大缓存对象数，若是0表示无穷大 -->
<!-- overflowToDisk：true表示当内存缓存的对象数目达到了maxElementsInMemory界限后，
会把溢出的对象写到硬盘缓存中。注意：如果缓存的对象要写入到硬盘中的话，则该对象必须实现了Serializable接口才行。-->
<!-- diskSpoolBufferSizeMB：磁盘缓存区大小，默认为30MB。每个Cache都应该有自己的一个缓存区。-->
<!-- diskPersistent：是否缓存虚拟机重启期数据 -->
<!-- diskExpiryThreadIntervalSeconds：磁盘失效线程运行时间间隔，默认为120秒 -->
<!-- timeToIdleSeconds： 设定允许对象处于空闲状态的最长时间，以秒为单位。当对象自从最近一次被访问后，
如果处于空闲状态的时间超过了timeToIdleSeconds属性值，这个对象就会过期，
EHCache将把它从缓存中清空。只有当eternal属性为false，该属性才有效。如果该属性值为0，
则表示对象可以无限期地处于空闲状态 -->
<!-- timeToLiveSeconds：设定对象允许存在于缓存中的最长时间，以秒为单位。当对象自从被存放到缓存中后，
如果处于缓存中的时间超过了 timeToLiveSeconds属性值，这个对象就会过期，
EHCache将把它从缓存中清除。只有当eternal属性为false，该属性才有效。如果该属性值为0，
则表示对象可以无限期地存在于缓存中。timeToLiveSeconds必须大于timeToIdleSeconds属性，才有意义 -->
<!-- memoryStoreEvictionPolicy：当达到maxElementsInMemory限制时，
Ehcache将会根据指定的策略去清理内存。可选策略有：LRU（最近最少使用，默认策略）、
FIFO（先进先出）、LFU（最少访问次数）。-->
<cache name="user"
maxEntriesLocalHeap="2000"
eternal="false"
timeToIdleSeconds="600"
timeToLiveSeconds="0"
overflowToDisk="false"
statistics="true">
</cache>
</ehcache>
我们可以设置缓存的过期时间，以及整合缓存的容量限制，包括各种的淘汰机制，那么Ehcache底层又是如何实现的呢？
容量限制
对于容量限制来说是很好实现的，对于EhCache底层是使用 net.sf.ehcache.store.chm.SelectableConcurrentHashMap类来实现缓存的存储的
在这个类中有一个全局属性,它就是用来判断缓存容量是否到达限制，每次存入的是一个新的key，那么就会判断这时候缓存的个数是否有超出这个值，超出了就要将某些KEY进行淘汰
如何判断KEY是否失效
EhCahce并不是简单的使用一个Map,然后将KEY和Value设置进去，EhCache对缓存的数据做了一个封装，也就是 net.sf.ehcache.Element这个类,这个类里面就封装了这个缓存的很多配置
public class Element implements Serializable, Cloneable {
private static final AtomicLongFieldUpdater<Element> HIT_COUNT_UPDATER = AtomicLongFieldUpdater.newUpdater(Element.class, "hitCount");
private static final boolean ELEMENT_VERSION_AUTO = Boolean.getBoolean("net.sf.ehcache.element.version.auto");
private static final long NOT_SET_ID = 0;
/**
* 缓存的KEY
*/
@IgnoreSizeOf
private final Object key;
/**
* 缓存的VALUE
*/
private final Object value;
/**
* 这个缓存被访问的次数，LRU淘汰策略就是根据这个值来进行比较的
*/
private volatile long hitCount;
/**
* 这个缓存在容器中有效时间，过了这个时间就失效，没配置就永不失效
*/
private volatile int timeToLive = Integer.MIN_VALUE;
/**
*
*/
private volatile int timeToIdle = Integer.MIN_VALUE;
/**
*
*/
private transient long creationTime;
/**
*
*/
private transient long lastAccessTime;
/**
*
*/
private volatile long lastUpdateTime;
Ehcache在获取缓存的时候，走的是下面这个逻辑 net.sf.ehcache.Cache 这个类
public final Element get(Object key) throws IllegalStateException, CacheException {
getObserver.begin();
checkStatus();
if (disabled) {
getObserver.end(GetOutcome.MISS_NOT_FOUND);
return null;
}
//拿到这个缓存的元素
Element element = compoundStore.get(key);
//如果没有，说明那么直接就走我们自己的业务逻辑，比如去查询数据库
if (element == null) {
getObserver.end(GetOutcome.MISS_NOT_FOUND);
return null;
} else if (isExpired(element)) { //如果有，那么就判断这个缓存是否过期
//过期了就尝试剔除这个缓存
tryRemoveImmediately(key, true);
getObserver.end(GetOutcome.MISS_EXPIRED);
return null;
} else if (!skipUpdateAccessStatistics(element)) {
element.updateAccessStatistics();
}
getObserver.end(GetOutcome.HIT);
return element;
}
我们看下判断是否过期的逻辑，主要是在 isExpired(element);这个方法
public final boolean isExpired(Element element) throws IllegalStateException, NullPointerException {
checkStatus();
//最后的判断逻辑的实现，依然是在这个Element中
return element.isExpired(configuration);
}
public boolean isExpired(CacheConfiguration config) {
if (cacheDefaultLifespan) {
if (config.isEternal()) {
timeToIdle = 0;
timeToLive = 0;
} else {
//重ehcache2.xml配置文件中，拿到TimeToIdleSeconds，TimeToLiveSeconds这两个
//值，然后设置到timeToIdle,timeToLive给两个属性
timeToIdle = TimeUtil.convertTimeToInt(config.getTimeToIdleSeconds());
timeToLive = TimeUtil.convertTimeToInt(config.getTimeToLiveSeconds());
}
}
//判断是否过期
return isExpired();
}
public boolean isExpired() {
if (!isLifespanSet() || isEternal()) {
return false;
}
//获取当前时间
long now = getCurrentTime();
//KEY距离上次访问的时间有没有超过配置文件设置的值，或者这个KEY的存活时间有没有超过限制
long expirationTime = getExpirationTime();
return now > expirationTime;
}
我们发现，EhCache判断KEY是否失效不是实时的，而是惰性删除,也就是只有当客户端访问了这个KEY的时候才会去判断是否失效，惰性删除在redis中也使用到，就是删除过期KEY的时候
基于LRU来实现缓存淘汰
LRU是基于最近最少使用来淘汰具体的KEY的，在EhCache底层，当是新增一个新的缓存的时候，新增结束之后，会判断当前缓存个数是否达到了我们设置的最大缓存元素的值。如果达到了，就要淘汰掉具体对应个数的缓存
private void checkCapacity(final Element elementJustAdded) {
if (maximumSize > 0 && !isClockEviction()) {
int evict = Math.min(map.quickSize() - maximumSize, MAX_EVICTION_RATIO);
//计算出要淘汰多少个元素才能满足最大元素的限制
for (int i = 0; i < evict; i++) {
removeElementChosenByEvictionPolicy(elementJustAdded);
}
}
}
private boolean removeElementChosenByEvictionPolicy(final Element elementJustAdded) {
//如果没有设置淘汰策略，也就是没有在配置文件中配置是使用LRU，还是LFU等
//那么默认是采用随机淘汰一个元素
if (policy == null) {
return map.evict();
}
//根据配置的淘汰策略选出要淘汰的元素
Element element = findEvictionCandidate(elementJustAdded);
if (element == null) {
LOG.debug("Eviction selection miss. Selected element is null");
return false;
}
// 选出要淘汰的元素判断是否过期，过期了就淘汰
if (element.isExpired()) {
remove(element.getObjectKey());
notifyExpiry(element);
return true;
}
if (storePinned) {
return false;
}
//如果没有过期就执行删除
return evict(element);
}
private Element findEvictionCandidate(final Element elementJustAdded) {
Object objectKey = elementJustAdded != null ? elementJustAdded.getObjectKey() : null;
Element[] elements = sampleElements(objectKey);
//根据淘汰策略选择要淘汰的KEY，在这里就有分支了，比如是使用LRU,或者是LFU
return policy.selectedBasedOnPolicy(elements, elementJustAdded);
}
public Element selectedBasedOnPolicy(Element[] sampledElements, Element justAdded) {
//如果只有一个元素，直接淘汰掉
if (sampledElements.length == 1) {
return sampledElements[0];
}
Element lowestElement = null;
//开始遍历缓存中的每一个元素
for (Element element : sampledElements) {
if (element == null) {
continue;
}
if (lowestElement == null) {
//这里主要是避免淘汰的是刚存进去的元素
if (!element.equals(justAdded)) {
lowestElement = element;
}
} else if (compare(lowestElement, element) && !element.equals(justAdded)) {
lowestElement = element;
}
}
return lowestElement;
}
主要是看else if分支的compare方法，这里有三个实现类，我们先看LRU的
public boolean compare(Element element1, Element element2) {
//判断两个元素距离上次被访问时间哪个元素间隔时间长
return element2.getLastAccessTime() < element1.getLastAccessTime();
}
我们可以发现，EhCache在Element这个缓存元素中有有保存这个缓存每次被访问的时间，如果这个元素距离上次被访问的时间是最长的，那么就会被淘汰掉
淘汰掉一个之后，然后会继续循环剩下的元素，直到缓存总的元素数量没有超出最大容量的限制
基于LFU来实现缓存淘汰
LFU是基于最近最少使用来淘汰具体的KEY，我们直接进入到LruPolicy中
public boolean compare(Element element1, Element element2) {
return element2.getHitCount() < element1.getHitCount();
}
LFU就是根据这个元素被访问的次数来选定的，EhCache中每次这个缓存元素被访问一次，那么它的hitCount就会被+1，淘汰的时候就淘汰掉这个值最小的就行了
总结
其实看源码并不是说看懂流程就可以了，而是要学习那些优秀框架底层的设计思想，就比如说EhCache中删除过期的KEY，它可以选择定期的去扫描，也可以给每个KEY定义一个过期的回调函数，但是这些都太费性能，所以可以选择惰性删除，只有当客户端访问了这个KEY才判断这个KEY是否过期
至此大家可以尝试自己实现一个缓存，然后配置缓存的失效时间，缓存淘汰策略等
转载自:https://juejin.cn/post/7352162941313712179