Guava Cache 1（脉络）
2017-12-26 本文已影响0人
心中的理想乡
这次终于把guava cache整个流程给打通了，有种打通任督二脉的感觉。可能在各种对数字操作取值的细节上面还有待细研究（例如segment初始大小为什么设置成4？为什么很多地方固定移位？为什么hash值要这么取值？），在初始化、put操作，get操作这三大操作内部怎么样子，做了什么事情，都算是看明白了。代码上面，google写的几乎都是面向过程的代码，所以看起来比较没那么舒服，我分享起来，也加大了难度，很容易就容易冷场。我想来想去，我觉得，以后除了展示整体的架构图，类图，时序图之外，对于每个方法里面做了什么事，我想了个办法，来让人一眼就明白：就是用中文来写伪代码！我试试
整体设计
下面的图更能说明Guava Cache的整体结构：
866881-20160119220057750-1755985024.jpg
主要有以下几点：
- 初始化segment数组和JDK1.7里面的HashMap是差不多的，基本没差别
- 可是，再每个segment下面会初始化一个ReferenceEntry数组，而且这个数组是AtomicReferenceArray类型的，用于多线程并发操作
- 每个ReferenceEntry对象里面，有三个很重要的属性：key、valueReference、next，分别对应着键值对的，键和值，还有指向下一个节点的指针
- 说明ReferenceEntry数组每个元素都是一个链表，这种也是传统的一个设计
- 每个segment下面，还会有四个重要的队列：
- keyReferenceQueue（用于软引用与弱引用的时候）
- valueReferenceQueue（用于软引用与弱引用的时候）
- writeQueue（用于时间淘汰算法）
- accessQueue（用于LRU、时间淘汰算法）
初始化过程
针对guavacache的初始化，我画了个时序图
初始化时序图.png
//中文伪代码
public class LocalCache{
LocalCache(CacheBuilder<? super K, ? super V> builder, @Nullable CacheLoader<? super K, V> loader){
//获取各种使用CacheBuilder初始化的参数
//各种位运算获取segment数组大小与referenceEntry数组大小
//初始化一个segment类型的数组Segment[size]
//初始化每个segment
}
static class Segment<K, V> extends ReentrantLock{
Segment(LocalCache<K, V> map, int initialCapacity, long maxSegmentWeight, StatsCounter statsCounter){
//segment内部持有Localcache与maxSegmentWeight
//初始化ReferenceEntry数据
//初始化keyReferenceQueue、valueReferenceQueue、writeQueue、accessQueue
}
}
}
put的过程
//中文伪代码
public class LocalCache{
@Override
public V put(K key, V value) {
//通过二次hash找到对应的ReferenceEntry数组的索引值
//这里调用segment的put方法
}
static class LocalLoadingCache<K, V> extends LocalManualCache<K, V> implements LoadingCache<K, V> {
@Override
public void put(K key, V value) {
localCache.put(key, value);
}
}
static class Segment<K, V> extends ReentrantLock{
@Nullable
V put(K key, int hash, V value, boolean onlyIfAbsent) {
try{
//加锁
//使用基于时间（最后写时间或是最后访问时间）淘汰策略，淘汰一下元素
//扩容（如果超出最大限制的话）
//通过二次hash的值定位到那个ReferenceEntry
for（遍历这个ReferenceEntry链表）{
if(这个entry的hash值等于传入的hash && entry的key不等于null && 传入的key值等于当前key)
//这个时候说明命中了元素
//取当前ReferenceEntry的valueReference里面对应的具体value值
if(value等于null){
if(valueReference是已经被初始化的状态){
//这说明value值是软引用或是弱引用，已经被GC回收了
//将当前的键值对放入到删除的监听队列里面，并且将当前Segment的容量减去当前元素的容量
//设置传入的值到链表当中去
//将当前Segment的容量加上当前元素的容量
//元素数目加一
}else{
//这种情况说明这个值没有被初始化过
//直接设置值，并加容量
}
//这里做一次基于LRU的缓存淘汰策略
return null
}else{
//这种情况说明这个元素的value不为null切命中
//将当前元素放入删除监听队列并减去当前Segment容量
//删除当前找到的值
//设置传入的值到这个链表中
//这里再一次做基于LRU的缓存淘汰
return value
}
}
//这里说明没有找到对应的key值
//心初始化一个ReferenceEntry并将传入的value包装成valueReference并set进当前ReferenceEntry
//将ReferenceEntry设置到对应的索引位置
//元素数目加一
//这里进行LRU缓存淘汰
return null
}finally{
//释放锁
//将整个过程中删除队列中删除的值，一个个回调用户自定义的删除回调监听函数
}
}
}
}
get（普通的get）的过程
//中文伪代码
public class LocalCache{
static class LocalLoadingCache<K, V> extends LocalManualCache<K, V> implements LoadingCache<K, V> {
@Override
public V get(K key) throws ExecutionException {
return localCache.getOrLoad(key);
}
}
V getOrLoad(K key) throws ExecutionException {
return get(key, defaultLoader);
}
V get(K key, CacheLoader<? super K, V> loader) throws ExecutionException {
//这里是二次hash找到那个最终的ReferenceEntry那个hash值
int hash = hash(checkNotNull(key));
return segmentFor(hash).get(key, hash, loader);
}
static class Segment<K, V> extends ReentrantLock{
V get(K key, int hash, CacheLoader<? super K, V> loader) throws ExecutionException {
//检查key值与加载器不能为空
try{
if(如果元素数目不为0){
//获取当前hash对应的ReferenceEntry
if(entry不为null){
//获取当前时间
value = (entry){
if(entry里面的key为null){
return null
}
if(entry里面的value为null){
return null
}
if(entry根据设置的时间超时){
//将对应的写队列或是访问队列里面的值淘汰
return null
}
return entry.value
}
if(value不为null){
//将此value最后访问时间设置成上面获取到的当前时间
if(设置了刷新时间 && 当前超过了刷新时间 && 当前entry不是正在加载中的entry){
//使用用户设置的加载器刷新当前值
if(如果当前值不为空){
return value
}
}
return entry.value
}
//获取当前entry里面的ValueReference
if(ValueReference是正在加载状态的){
//循环等待正在加载的value
//将等待的value记录到访问队列
return value
}
}
return 用用户自定义加载器加载那个value
}
}catch(异常){
//异常处理
}finally{
//基于过期时间进行淘汰
//将整个过程中删除队列中删除的值，一个个回调用户自定义的删除回调监听函数
}
}
}
}
