LRU算法介绍
LRU 是 Least Recently Used 的缩写，即最近最少使用。
-
LRU 算法常用于页面置换算法，为虚拟页式存储管理服务。
-
LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理。
-
此外，LRU算法也经常被用作缓存淘汰策略。
本文将基于 LRU 算法的思想，使用Java语言实现我们的缓存类。
借鉴源码实现 LRU 缓存
SpringMVC
在 spring-webmvc 源码中，有一个缓存 View 的类，用到了 LRU 算法。
<dependency>
<groupId>org.springframework</groupId>
<artifactId>spring-webmvc</artifactId>
<version>5.1.0.RELEASE</version>
</dependency>
有一个 org.springframework.web.servlet.view.AbstractCachingViewResolver 用 LinkedHashMap 实现 LRU 缓存。我只保留源码中和 LRU 算法关系紧密的代码。
import org.springframework.lang.Nullable;
import org.springframework.web.servlet.View;
import org.springframework.web.servlet.view.AbstractUrlBasedView;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.util.LinkedHashMap;
import java.util.Locale;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public abstract class AbstractCachingViewResolver {
/** Default maximum number of entries for the view cache: 1024. */
public static final int DEFAULT_CACHE_LIMIT = 1024;
/** Dummy marker object for unresolved views in the cache Maps. */
private static final View UNRESOLVED_VIEW = new View() {
@Override
@Nullable
public String getContentType() {
return null;
}
@Override
public void render(@Nullable Map<String, ?> model, HttpServletRequest request, HttpServletResponse response) {
}
};
/** The maximum number of entries in the cache. */
private volatile int cacheLimit = DEFAULT_CACHE_LIMIT;
/** Whether we should refrain from resolving views again if unresolved once. */
private boolean cacheUnresolved = true;
/** Fast access cache for Views, returning already cached instances without a global lock. */
private final Map<Object, View> viewAccessCache = new ConcurrentHashMap<>(DEFAULT_CACHE_LIMIT);
/** Map from view key to View instance, synchronized for View creation. */
@SuppressWarnings("serial")
private final Map<Object, View> viewCreationCache =
new LinkedHashMap<Object, View>(DEFAULT_CACHE_LIMIT, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Object, View> eldest) {
if (size() > getCacheLimit()) {
viewAccessCache.remove(eldest.getKey());
return true;
}
else {
return false;
}
}
};
/**
* Specify the maximum number of entries for the view cache.
* Default is 1024.
*/
public void setCacheLimit(int cacheLimit) {
this.cacheLimit = cacheLimit;
}
/**
* Return the maximum number of entries for the view cache.
*/
public int getCacheLimit() {
return this.cacheLimit;
}
/**
* Enable or disable caching.
* <p>This is equivalent to setting the {@link #setCacheLimit "cacheLimit"}
* property to the default limit (1024) or to 0, respectively.
* <p>Default is "true": caching is enabled.
* Disable this only for debugging and development.
*/
public void setCache(boolean cache) {
this.cacheLimit = (cache ? DEFAULT_CACHE_LIMIT : 0);
}
/**
* Return if caching is enabled.
*/
public boolean isCache() {
return (this.cacheLimit > 0);
}
/**
* Whether a view name once resolved to {@code null} should be cached and
* automatically resolved to {@code null} subsequently.
* <p>Default is "true": unresolved view names are being cached, as of Spring 3.1.
* Note that this flag only applies if the general {@link #setCache "cache"}
* flag is kept at its default of "true" as well.
* <p>Of specific interest is the ability for some AbstractUrlBasedView
* implementations (FreeMarker, Tiles) to check if an underlying resource
* exists via {@link AbstractUrlBasedView#checkResource(Locale)}.
* With this flag set to "false", an underlying resource that re-appears
* is noticed and used. With the flag set to "true", one check is made only.
*/
public void setCacheUnresolved(boolean cacheUnresolved) {
this.cacheUnresolved = cacheUnresolved;
}
/**
* Return if caching of unresolved views is enabled.
*/
public boolean isCacheUnresolved() {
return this.cacheUnresolved;
}
@Nullable
public View resolveViewName(String viewName, Locale locale) throws Exception {
if (!isCache()) {
return createView(viewName, locale);
}
else {
Object cacheKey = getCacheKey(viewName, locale);
View view = this.viewAccessCache.get(cacheKey);
if (view == null) {
synchronized (this.viewCreationCache) {
view = this.viewCreationCache.get(cacheKey);
if (view == null) {
// Ask the subclass to create the View object.
view = createView(viewName, locale);
if (view == null && this.cacheUnresolved) {
view = UNRESOLVED_VIEW;
}
if (view != null) {
this.viewAccessCache.put(cacheKey, view);
this.viewCreationCache.put(cacheKey, view);
}
}
}
}
return (view != UNRESOLVED_VIEW ? view : null);
}
}
protected abstract View createView(String viewName, Locale locale);
/**
* Clear the entire view cache, removing all cached view objects.
* Subsequent resolve calls will lead to recreation of demanded view objects.
*/
public void clearCache() {
// Clearing all views from the cache;
synchronized (this.viewCreationCache) {
this.viewAccessCache.clear();
this.viewCreationCache.clear();
}
}
/**
* Return the cache key for the given view name and the given locale.
* <p>Default is a String consisting of view name and locale suffix.
* Can be overridden in subclasses.
* <p>Needs to respect the locale in general, as a different locale can
* lead to a different view resource.
*/
protected Object getCacheKey(String viewName, Locale locale) {
return viewName + '_' + locale;
}
}
首先，看两个关键性方法：新增缓存的方法 resolveViewName ，清除缓存的方法 clearCache 。
有两个核心 Map：
-
viewAccessCache 用于查询缓存 View
-
viewCreationCache 支持 LRU 算法，在超出容量限制会回调 removeEldestEntry 方法
成员变量 cacheUnresolved 可以动态调节是否缓存 value == null 的键。
MyBatis
在 mybatis 源码中，有一个表示缓存的类，用到了 LRU 算法。
<dependency>
<groupId>org.mybatis</groupId>
<artifactId>mybatis</artifactId>
<version>3.0.5</version>
</dependency>
org.apache.ibatis.cache.Cache 接口的其中一个实现 LruCache 也是借助 LinkedHashMap 实现的。
import org.apache.ibatis.cache.Cache;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
public class LruCache implements Cache {
private final Cache delegate;
private Map<Object, Object> keyMap;
private Object eldestKey;
public LruCache(Cache delegate) {
this.delegate = delegate;
setSize(1024);
}
public String getId() {
return delegate.getId();
}
public int getSize() {
return delegate.getSize();
}
public void setSize(final int size) {
keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
private static final long serialVersionUID = 4267176411845948333L;
@Override
protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
boolean tooBig = size() > size;
if (tooBig) {
eldestKey = eldest.getKey();
}
return tooBig;
}
};
}
public void putObject(Object key, Object value) {
delegate.putObject(key, value);
cycleKeyList(key);
}
public Object getObject(Object key) {
keyMap.get(key); //touch
return delegate.getObject(key);
}
public Object removeObject(Object key) {
return delegate.removeObject(key);
}
public void clear() {
delegate.clear();
keyMap.clear();
}
public ReadWriteLock getReadWriteLock() {
return delegate.getReadWriteLock();
}
private void cycleKeyList(Object key) {
keyMap.put(key, key);
if (eldestKey != null) {
delegate.removeObject(eldestKey);
eldestKey = null;
}
}
}
这个类没用 synchronized 关键字的原因是因为 Cache 实现一层套一层，同步的工作交给了 SynchronizedCache 这个类来完成。
建链的过程可以参考 MapperBuilderAssistant # useNewCache
总结
SpringMVC 这个 LRU 实现，更复杂一些，但是支持动态调整缓存的大小。
MyBatis 的 LRU 实现更简单。