WhatAKitty Daily

A Programmer's Daily Record

一起写个Cache架构【一】——基础缓存

WhatAKitty   阅读次数loading...

实现目标

基础缓存就是实现一个缓存该有的功能,在这个版本中先不会考虑性能问题(性能将在之后的版本进行优化)。
我们暂时定义的功能有如下:

  • 内存级缓存
  • 缓存过期
  • 无缓存存在则根据数据源自动载入数据

设计思路

  1. 定义Cache接口
  2. 定义数据源加载辅助接口
  3. 定义内存级缓存实现类,并组合缓存过期辅助类

构建骨架

接下来,根据我们的思路构建一个缓存架构的骨架。

构建Cache接口

由于需要针对不同的应用场景,所以对于不同的应用场景需要有不同的缓存实例。
在这里,参考guava和jodd的缓存实现,定义了不同对象类型的缓存实例。即定义Cache<K, V>泛型接口。在该接口内包含如下方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* 加入可过期的缓存
*/
void put(K key, V value, long timeout);

/**
* 获取缓存
* 如果缓存不存在,则通过CacheLoader加载原数据
*/
Optional<V> get(K key, CacheLoader<V> loader) throws InterruptedException, CacheLoaderFailedException;

/**
* 删除缓存
*/
boolean remove(K key);

/**
* 清理所有缓存
*/
boolean clearAll();

/**
* 获取已缓存的数量
*/
int size();

/**
* 获取已缓存的key集合
*/
Set<K> keys();

/**
* 是否存在某个缓存
*/
boolean contains(K key);

/**
* 缓存快照
* 会根据执行时候的时间点,拷贝一份缓存内容
*/
Map<K, CacheObject<K, V>> snapshot();

上述基本包含了缓存需要的所有操作,最重要的其实就是获取与存入这两个方法。

实现内存级缓存

根据定义的缓存接口,就可以实现内存级缓存了。

现在有个问题,该将缓存存入到哪种容器内?笔者在这里是通过 HashMap 来存储缓存内容,并通过 StampedLock锁 来保证并发情况下的数据共享问题。

JDK本身其实有并发的Map集合ConcurrentHashMap。不过,在实现缓存的过程中需要使用各种复合操作,而其本身的复合操作并不一定能够完全满足以后的功能扩展(ConcurrentHashMap无法在客户端级别加锁保证独占式访问,详细可以看这篇文章);所以,直接选择了HashMap + StampedLock的形式来保证多线程访问,这样,以后对于一些新功能易于扩展(以后可以考虑参照JDK8的ConcurrentHashMap直接实现自己的容器,例如像guava就是参照了JDK7的ConcurrentHashMap的分段锁原理)。

确定好容器之后,接下来就该实现我们的putget方法了。

put方法

由于存入缓存是写操作,我们需要保证在写的过程中,读线程处于阻塞状态。

1
2
3
4
5
6
7
8
9
10
11
12
// 阻塞获取写锁
long stamp = stampedLock.writeLock();

try {
// 根据缓存的过期时间创建一个缓存对象
CacheObject<K, V> cacheObject = CacheObject.createValueCache(key, value, timeout);
// 将缓存对象存入到缓存容器内
cacheMap.put(key, cacheObject);
} finally {
// 解锁写锁
stampedLock.unlockWrite(stamp);
}

如上代码,笔者在执行缓存对象的创建与存入之前,做了一步加锁操作。加锁操作,一个是为了防止HashMap在多线程环境下造成的死循环异常,再者也是为了防止出现sizeget这些方法在多线程环境下数据不准确的情况,而这个很可能导致缓存击穿的事情发生,这样缓存也就没有意义了。

get方法

我们在获取缓存的时候,如果出现缓存为空的情况,则需要通过CacheLoader来辅助获取原数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 判断cacheLoader是否为空,为空则抛出非法参数异常
Asserts.notNull(loader);
// 阻塞获取读锁(在这里其实可以优化为乐观读,笔者在这里先偷懒,之后实现)
long stamp = stampedLock.readLock();

try {
// 通过缓存容器获取缓存
CacheObject<K, V> 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<V> 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的实现则返回空 -> 如果存在则返回内容 -> 如果已经过期或者不存在缓存 -> 获取写锁 -> 重新载入原数据 -> 释放锁

至于如果通过缓存对象获取缓存的值,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 更新最新的访问时间
lastAccess = System.currentTimeMillis();
// 访问次数+1
accessCount++;
// 异步任务为空,则返回缓存的值
if (futureResult == null) {
return Optional.ofNullable(result);
}
// 是否已经计算过值
if (!futureResult.isDone()) {
// 未进行过计算,执行异步任务
futureResult.run();
}
// 阻塞获取异步的结果
return Optional.ofNullable(futureResult.get());

缓存过期

针对于缓存过期的问题,笔者这里设计了两种实现方式。

  • 懒过期:在获取的时候,同时判断缓存是否已经过期。保证能够实时移除过期缓存。
  • 定时清理:启动一个清理线程,对于已经过期的缓存,做删除操作,防止存储的失效缓存过大的问题。

懒过期

懒过期的机制其实很好实现,只要在获取的时候,判断下缓存对象是否过期即可,我们将get方法更改如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 判断cacheLoader是否为空,为空则抛出非法参数异常
Asserts.notNull(loader);
// 阻塞获取读锁(在这里其实可以优化为乐观读,笔者在这里先偷懒,之后实现)
long stamp = stampedLock.readLock();

try {
// 通过缓存容器获取缓存
CacheObject<K, V> 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<V> 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(),这个的判断逻辑是在缓存对象内实现:

1
2
3
4
5
6
// 判断是否支持过期
if (ttl == 0) {
return false;
}
// 支持过期,且上次访问加上过期时间是否小于当前的时间点,如果是的话,则为过期否则为有效缓存
return lastAccess + ttl < System.currentTimeMillis();

定时清理

定时清理的机制稍微有点麻烦,笔者在这里通过一个辅助类来实现这个机制。

通过辅助类实现这个机制的原因是:将该清理操作能够应用于所有实现了Cache接口的缓存实例,并由缓存实现自己决定是否需要定时清理这个机制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
final class CacheTimeoutHelper<K, V> {

// 缓存实例
private final Cache<K, V> cache;
// 定期间隔时间
private final long delay;
// 过期清理线程池
private final ScheduledExecutorService executor;
// 是否已经开始执行清理操作
private volatile boolean started = false;

/**
* 实例化缓存清理辅助类
*
* 传入缓存实例以及定时清理间隔的时间
*/
CacheTimeoutHelper(Cache<K, V> 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<V> 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架构
分析与计划
基础缓存