一起写个Cache架构【一】——基础缓存
### 实现目标
基础缓存就是实现一个缓存该有的功能，在这个版本中先不会考虑性能问题（性能将在之后的版本进行优化）。
我们暂时定义的功能有如下：
* 内存级缓存
* 缓存过期
* 无缓存存在则根据数据源自动载入数据
### 设计思路
1. 定义Cache接口
2. 定义数据源加载辅助接口
3. 定义内存级缓存实现类，并组合缓存过期辅助类
### 构建骨架
接下来，根据我们的思路构建一个缓存架构的骨架。
#### 构建Cache接口
由于需要针对不同的应用场景，所以对于不同的应用场景需要有不同的缓存实例。
在这里，参考guava和jodd的缓存实现，定义了不同对象类型的缓存实例。即定义`Cache`泛型接口。在该接口内包含如下方法：
```java
/**
* 加入可过期的缓存
*/
void put(K key, V value, long timeout);
/**
* 获取缓存
* 如果缓存不存在，则通过CacheLoader加载原数据
*/
Optional get(K key, CacheLoader loader) throws InterruptedException, CacheLoaderFailedException;
/**
* 删除缓存
*/
boolean remove(K key);
/**
* 清理所有缓存
*/
boolean clearAll();
/**
* 获取已缓存的数量
*/
int size();
/**
* 获取已缓存的key集合
*/
Set keys();
/**
* 是否存在某个缓存
*/
boolean contains(K key);
/**
* 缓存快照
* 会根据执行时候的时间点，拷贝一份缓存内容
*/
Map> snapshot();
```
上述基本包含了缓存需要的所有操作，最重要的其实就是获取与存入这两个方法。
### 实现内存级缓存
根据定义的缓存接口，就可以实现内存级缓存了。
现在有个问题，该将缓存存入到哪种容器内？笔者在这里是通过 `HashMap` 来存储缓存内容，并通过 `StampedLock`锁 来保证并发情况下的数据共享问题。
JDK本身其实有并发的`Map`集合`ConcurrentHashMap`。不过，在实现缓存的过程中需要使用各种复合操作，而其本身的复合操作并不一定能够完全满足以后的功能扩展（`ConcurrentHashMap`无法在客户端级别加锁保证独占式访问，[详细可以看这篇文章](./Java并发集合.html#ConcurrentHashMap)）；所以，直接选择了`HashMap` + `StampedLock`的形式来保证多线程访问，这样，以后对于一些新功能易于扩展（以后可以考虑参照JDK8的`ConcurrentHashMap`直接实现自己的容器，例如像guava就是参照了JDK7的`ConcurrentHashMap`的分段锁原理）。
确定好容器之后，接下来就该实现我们的`put`和`get`方法了。
#### `put`方法
由于存入缓存是写操作，我们需要保证在写的过程中，读线程处于阻塞状态。
```java
// 阻塞获取写锁
long stamp = stampedLock.writeLock();
try {
// 根据缓存的过期时间创建一个缓存对象
CacheObject cacheObject = CacheObject.createValueCache(key, value, timeout);
// 将缓存对象存入到缓存容器内
cacheMap.put(key, cacheObject);
} finally {
// 解锁写锁
stampedLock.unlockWrite(stamp);
}
```
如上代码，笔者在执行缓存对象的创建与存入之前，做了一步加锁操作。加锁操作，一个是为了防止`HashMap`在多线程环境下造成的死循环异常，再者也是为了防止出现`size`、`get`这些方法在多线程环境下数据不准确的情况，而这个很可能导致缓存击穿的事情发生，这样缓存也就没有意义了。
#### `get`方法
我们在获取缓存的时候，如果出现缓存为空的情况，则需要通过`CacheLoader`来辅助获取原数据。
```java
// 判断cacheLoader是否为空，为空则抛出非法参数异常
Asserts.notNull(loader);
// 阻塞获取读锁（在这里其实可以优化为乐观读，笔者在这里先偷懒，之后实现）
long stamp = stampedLock.readLock();
try {
// 通过缓存容器获取缓存
CacheObject obj = cacheMap.get(key);
// 如果缓存为空并且cacheLoader是一个空实现（即永远返回空对象），则直接返回空内容
if (obj == null && loader instanceof CacheLoader.EmptyCacheLoader) {
return Optional.empty();
}
// 如果缓存为空
if (obj == null) {
// 尝试锁升级，将读锁升级到写锁；在这里尝试CAS自旋，防止线程状态切换带来的资源损耗
stamp = stampedLock.tryConvertToWriteLock(stamp);
// 判断锁升级是否成功
if (stamp == 0L) {
// 锁升级失败，阻塞获取写锁；其实这里会再次尝试CAS锁定，如果失败加入等待队列，不过这个不属于本篇文章的范畴，有兴趣的同学可以查看JDK8的StampedLock源码
stamp = stampedLock.writeLock();
}
// 创建一个异步任务
FutureTask futureTask = new FutureTask<>(loader::call);
// 以异步任务、key作为元素创建一个缓存对象
obj = CacheObject.createFutureCache(key, futureTask, 0L);
// 如果存在旧的缓存，则覆盖；否则新增
cacheMap.replace(key, obj);
}
// 返回缓存对象内的结果
return obj.getObject();
} catch (ExecutionException e) {
// 执行失败抛出异常
throw new CacheLoaderFailedException(e);
} finally {
// 释放锁（可能是升级后的写锁）
stampedLock.unlock(stamp);
}
```
大致思路其实是：读锁锁定 -> 如果不存在且无`CacheLoader`的实现则返回空 -> 如果存在则返回内容 -> 如果已经过期或者不存在缓存 -> 获取写锁 -> 重新载入原数据 -> 释放锁
至于如果通过缓存对象获取缓存的值，如下：
```java
// 更新最新的访问时间
lastAccess = System.currentTimeMillis();
// 访问次数+1
accessCount++;
// 异步任务为空，则返回缓存的值
if (futureResult == null) {
return Optional.ofNullable(result);
}
// 是否已经计算过值
if (!futureResult.isDone()) {
// 未进行过计算，执行异步任务
futureResult.run();
}
// 阻塞获取异步的结果
return Optional.ofNullable(futureResult.get());
```
### 缓存过期
针对于缓存过期的问题，笔者这里设计了两种实现方式。
* 懒过期：在获取的时候，同时判断缓存是否已经过期。保证能够实时移除过期缓存。
* 定时清理：启动一个清理线程，对于已经过期的缓存，做删除操作，防止存储的失效缓存过大的问题。
#### 懒过期
懒过期的机制其实很好实现，只要在获取的时候，判断下缓存对象是否过期即可，我们将`get`方法更改如下：
```java
// 判断cacheLoader是否为空，为空则抛出非法参数异常
Asserts.notNull(loader);
// 阻塞获取读锁（在这里其实可以优化为乐观读，笔者在这里先偷懒，之后实现）
long stamp = stampedLock.readLock();
try {
// 通过缓存容器获取缓存
CacheObject obj = cacheMap.get(key);
// 如果缓存为空并且cacheLoader是一个空实现（即永远返回空对象），则直接返回空内容
if (obj == null && loader instanceof CacheLoader.EmptyCacheLoader) {
return Optional.empty();
}
// 如果缓存为空或者【缓存过期】
if (obj == null || obj.isExpired()) { ①
// 尝试锁升级，将读锁升级到写锁；在这里尝试CAS自旋，防止线程状态切换带来的资源损耗
stamp = stampedLock.tryConvertToWriteLock(stamp);
// 判断锁升级是否成功
if (stamp == 0L) {
// 锁升级失败，阻塞获取写锁；其实这里会再次尝试CAS锁定，如果失败加入等待队列，不过这个不属于本篇文章的范畴，有兴趣的同学可以查看JDK8的StampedLock源码
stamp = stampedLock.writeLock();
}
// 创建一个异步任务
FutureTask futureTask = new FutureTask<>(loader::call);
// 以异步任务、key作为元素创建一个缓存对象
obj = CacheObject.createFutureCache(key, futureTask, 0L);
// 如果存在旧的缓存，则覆盖；否则新增
cacheMap.replace(key, obj);
}
// 返回缓存对象内的结果
return obj.getObject();
} catch (ExecutionException e) {
// 执行失败抛出异常
throw new CacheLoaderFailedException(e);
} finally {
// 释放锁（可能是升级后的写锁）
stampedLock.unlock(stamp);
}
```
即在 ① 的代码处，增加一个或判断` || obj.isExpired()`，这个的判断逻辑是在缓存对象内实现：
```java
// 判断是否支持过期
if (ttl == 0) {
return false;
}
// 支持过期，且上次访问加上过期时间是否小于当前的时间点，如果是的话，则为过期否则为有效缓存
return lastAccess + ttl < System.currentTimeMillis();
```
#### 定时清理
定时清理的机制稍微有点麻烦，笔者在这里通过一个辅助类来实现这个机制。
通过辅助类实现这个机制的原因是：将该清理操作能够应用于所有实现了Cache接口的缓存实例，并由缓存实现自己决定是否需要定时清理这个机制。
```java
final class CacheTimeoutHelper {
// 缓存实例
private final Cache cache;
// 定期间隔时间
private final long delay;
// 过期清理线程池
private final ScheduledExecutorService executor;
// 是否已经开始执行清理操作
private volatile boolean started = false;
/**
* 实例化缓存清理辅助类
*
* 传入缓存实例以及定时清理间隔的时间
*/
CacheTimeoutHelper(Cache cache, long delay) {
this.cache = cache;
this.delay = delay;
// 初始化线程池，如果核心线程池已满，则抛弃阻塞队列中最早的执行线程
this.executor = new ScheduledThreadPoolExecutor(Runtime.getRuntime().availableProcessors(),
new ThreadPoolExecutor.DiscardOldestPolicy());
}
public void start() {
// 设置启动标识
started = true;
// 线程调度
executor.schedule(() -> {
// 只需要遍历缓存，做一次get操作，会自动将过期缓存删除（可能存在bug）
for (K key : cache.keys()) {
try {
Optional value = cache.get(key);
// 如果值没有找到，则直接移除，不管存不存在（可能有值不存在，但是key存在的情况）
if (!value.isPresent()) {
cache.remove(key);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}, delay, TimeUnit.SECONDS);
}
/**
* 是否已经启动
*/
public boolean isStarted() {
return started;
}
}
```
### 总结
总体实现了缓存的基本功能，可能在性能上以及代码逻辑上存在一些可优化的地方，后期将会慢慢调整优化。
以下是Github的仓库地址：
https://github.com/LightweightJava/cache
欢迎各位给star或者和贡献代码。
** 一起写个Cache架构 **
[分析与计划](https://xuqiang.me/一起写个Cache架构【零】——分析与计划.html)
[基础缓存](https://xuqiang.me/一起写个Cache架构【一】——基础缓存.html)
