Java应用缓存介绍与LRU(Least Recently Used)算法

发表于   |   分类于   |  

引言

对于大规模的Java Web应用来说，会有大量的数据和大量的用户，对于如何提升网站的响应速度成为了我们开发人员的一个挑战。对于缓存来说，它可以解决其中的一部分问题。在这篇文章中，我会介绍什么是缓存，它的工作流程是什么样的，被缓存的数据应该具有什么样的特性。最后我会介绍一个非常受欢迎的缓存算法 - LRU，并给出了一个具体的实现。

cache

缓存的大致工作流程

缓存就是把我们频繁访问的数据（并且这些数据比较消耗时间计算或读取）放到内存中，以便我们下次用到这样的数据时，就不用重新计算或者重新读取。比如从数据库中查询出的结果、IO读取一些配置文件的信息等。Java中的缓存接口通常如下所示：

1
2
3
4
public interface Cache {
    Object get(final Object key);
    Object put(final Object key, final Object value);
}

一个普通应用缓存的大致流程如下图：

application cache

应用程序用一个key从缓存中取数据（get方法），如果在缓存中并没有发现这个key，那么应用程序从一个非常耗时的数据源中取数据并把获取到的数据放到缓存中（put方法）。因此，接下来的请求就可以从缓存中取得数据了。

缓存数据应该具有的特性

由于缓存需要用到应用的内存，因此我们需要去控制缓存的大小，把一些不常用的数据从缓存中清除。被缓存的数据应该具有 Temporal locality 和 Spatial locality，下面我把wikipedia 中对这2条性质的定义翻译一下。

Spatial locality

如果某一特定时间的某个特定存储位置被引用到，那么在不久的将来它附近的位置很可能会被再次引用到。

Temporal locality

如果某一特定时间的某个特定存储位置被引用到，那么在不久的将来它很可能会被再次引用到。Temporal locality 是 Spatial locality 的一个特例，即未来将要被访问到的位置和当前的位置是相同的。

如果我们缓存的数据并不满足上面的两个性质，缓存命中率非常低，因此会导致缓存的元素很快地被清除出去。由于增大维护缓存的开销，并没有达到缓存应有的效果，反而会导致应用程序的性能下降。

缓存的性能评价指标

hit/miss ratio 是一个主要的评价缓存性能的指标。我们计算它通过缓存命中的次数 / 缓存没有命中的次数

当我们评估缓存的性能时，我们可以让程序运行一段时间后来计算上面的hit/miss ratio，如果这个ratio很高，则证明缓存性能很好; 如果这个ratio的值很小，则表示应用缓存的数据不应该被缓存，或者同样有可能是因为我们的缓存size太小，导致不能捕获到缓存数据的temporal locality.

LRU算法

缓存 Eviction Policy

缓存 Eviction Policy 就是当一个新的元素加入到缓存中时，如果导致缓存大小已经超过了所允许的范围，它会从缓存中移除一个已经存在的元素。eviction policy 确保缓存的大小不会超过一个我们自己指定的阙值。

LRU是一个很受欢迎的具有Eviction Policy功能的一个算法。LRU受欢迎的原因就是它同时捕获了数据访问的2个性质 - temporal locality 和 spatial locality

LRU算法实现

一个典型的LRU缓存实现由一个Map和一个linked list组成，Map存储缓存的元素，linked list 保持追踪最近最少使用的缓存元素。当一个缓存元素被更新时，把它从linked list中移除，并把它放入到linked list中的头部。如果当一个新的元素加入到列表中时，LRU会把这个元素加入到linked list的头部，同时LRU也会判断缓存大小是否超过了限制，如果超过了限制，则位于linked list尾部的元素将被移除。

下面我用LinkedHashMap来实现一个简单的LRU缓存：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.LinkedHashMap;
import java.util.Map;
public LRUCache<K, V> extends LinkedHashMap<K, V> {
  private int cacheSize;
  public LRUCache(int cacheSize) {
    super(16, 0.75, true);
    this.cacheSize = cacheSize;
  }
  // This method is called just after a new entry has been added
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() >= cacheSize;
  }
}

上面的代码仅仅是一个简单的实现，并不足以用到真实的应用中。如果大家想要一个可以在真实应用中使用的产品，建议大家看看caffeine，基于Java 8的一个高性能缓存库。或者可以参考一下Apache Commons的LRUMap

二级缓存

在object-relational mapping (ORM)框架（Hibernate）或者data mapping (DM) 框架（iBatis）都提供了二级缓存的功能。二级缓存封装了缓存逻辑的复杂性，不让客户端看见。通过减小不必要的数据库，二级缓存提高了ORM 或者 DM框架的性能，下图解释了二级缓存的工作流程：

Level-2 Cache

从上图我们可以看到，客户端应用并没有直接去访问缓存，而是访问ORM 或者 DM框架提供的更高级的接口。

总结

恰当的使用缓存可以大大提高我们应用程序的性能。但是，在选择是否使用缓存之前，我们必须要看看被缓存的数据是否符合temporal locality 或者 spatial locality，如果数据并不符合这样的性质，缓存不仅不会使我们的应用程序性能提升，而且还会导致性能下降，这是因为维护缓存的开销要比从缓存中获益的开销要小。因此，在使用缓存之前，我们一定要认真想一想，数据是否具有上面的2个特性。