gcache 源码分析

发表于 | 分类于
字数统计 5.1k | 阅读时长 23
首先介绍 FIFO 、LRU、LFU 三种缓存算法的特征、基本思想，然后再从源码解读 gcache 的实现。

缓存清除策略

FIFO

FIFO（First In First Out）是一种先进先出的调度策略。
先进先出策略，最先进入缓存的数据在缓存空间不够的情况下（超出最大元素限制）会被优先被清除掉，以腾出新的空间接受新的数据。策略算法主要比较缓存元素的创建时间。在数据实效性要求场景下可选择该类策略，优先保障最新数据可用。

缺点：

判断一个页面置换算法优劣的指标就是缺页率，而 FIFO 算法的一个显著的缺点是，在某些特定的时刻，缺页率反而会随着分配页面的增加而增加，这称为 Belady 现象。产生 Belady 现象现象的原因是，FIFO 置换算法与进程访问内存的动态特征是不相容的，被置换的内存页面往往是被频繁访问的，或者没有给进程分配足够的页面，因此 FIFO 算法会使一些页面频繁地被替换和重新申请内存，从而导致缺页率增加。因此，FIFO 算法的使用场景较少。

LRU

LRU（Least Recently Used）是一种最近最少使用策略。
最近最少使用策略，无论是否过期，根据元素最后一次被使用的时间戳，清除最远使用时间戳的元素释放空间。策略算法主要比较元素最近一次被get使用时间。在热点数据场景下较适用，优先保证热点数据的有效性。

LFU

LRU（Least Frequency Used）是一种最少使用调度策略。
最少使用策略，无论是否过期，根据元素的被使用次数判断，清除使用次数较少的元素释放空间。策略算法主要比较元素的hitCount（命中次数）。在保证高频数据有效性场景下，可选择这类策略。

ARC

ARC 是为了提高缓存效果介于 LRU 和 LFU 设置的算法。借助 LRU 和 LFU 基本思想实现，以获得可用缓存的最佳使用。

OPT

OPT（OPTimal replacement）是一种理论上最佳的页面置换算法。
淘汰以后永远用不到的数据项；如果没有，则淘汰最久以后再用到的数据项。属于理想型算法，不可能实现（因为无法知道全局的访问序列）。但是，可以最为评价其他算法优劣的参考标准。

gcache 源码分析

概述

gcache 是基于 Golang 实现的一个内存级 Cache 基础库，支持带失效时间的 Cache。

在这篇文章里，我们将主要从键值对的读写过程，以及数据变化的角度来阐述 gcache 的基本原理，详细操作可参考源代码。

多种缓存策略

gcache 目前包括 Simple，LFU（Least Frequency Used），LRU（Least Recently Used），ARC（Adaptive Replacement Cache）四种缓存策略。

  • Simple：普通缓存策略，随机淘汰。
  • LRU：Least Recently Used，优先替换最近最少使用的内容。
  • LFU：Least Frequently Used，优先替换访问次数最少的内容。
  • ARC：Adaptive Replacement Cache，ARC介于 LRU 和 LFU 之间。

支持回调策略

gcache 的回调函数原型（定制化操作），在 cache.go 中定义：

1
2
3
4
5
6
7
8
9
type (
trueLoaderFunc       func(interface{}) (interface{}, error)                 // 自动加载回调函数
trueLoaderExpireFunc func(interface{}) (interface{}, *time.Duration, error) // 过期回调函数
trueEvictedFunc      func(interface{}, interface{})                         // 淘汰回调函数
truePurgeVisitorFunc func(interface{}, interface{})                         // 清除所有 key 回调函数
trueAddedFunc        func(interface{}, interface{})                         // 新增 key 回调函数
trueDeserializeFunc  func(interface{}, interface{}) (interface{}, error)    // 反序列化回调函数
trueSerializeFunc    func(interface{}, interface{}) (interface{}, error)    // 序列化回调函数
)

计数统计

  • HitCount：命中次数
  • MissCount：未命中次数
  • LookupCount：查找次数（HitCount + MissCount）
  • HitRate：命中率（HitCount / LookupCount）

官方代码
注解版代码
godoc 文档

基本架构

![20191024232913.png](/images

接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type Cache interface {
trueSet(key, value interface{}) error
trueSetWithExpire(key, value interface{}, expiration time.Duration) error
trueGet(key interface{}) (interface{}, error)
trueGetIFPresent(key interface{}) (interface{}, error)
trueGetALL(checkExpired bool) map[interface{}]interface{}
trueget(key interface{}, onLoad bool) (interface{}, error)
trueRemove(key interface{}) bool
truePurge()
trueKeys(checkExpired bool) []interface{}
trueLen(checkExpired bool) int
trueHas(key interface{}) bool

truestatsAccessor
}

CacheBuilder

CacheBuilder 用来构造缓存对象，以及各种个性化化配置、策略。由 cache.go/CacheBuilder 结构表示：

cache.go 中有详细注解。

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
// CacheBuilder 构造缓存对象，以及各种个性化化配置、策略。
// 构建 cache 时，会赋值给 baseCache 中对应的字段
type CacheBuilder struct {
trueclock            Clock            // cache 时钟
truetp               string           // 缓存类型：TYPE_SIMPLE，TYPE_LRU，TYPE_LFU，TYPE_ARC
truesize             int              // 缓存大小
trueloaderExpireFunc LoaderExpireFunc // key 过期时的回调函数
trueevictedFunc      EvictedFunc      // 淘汰 key 时的回调函数
truepurgeVisitorFunc PurgeVisitorFunc // 清空缓存所有 key 时的回调函数
trueaddedFunc        AddedFunc        // 新增 key 时的回调函数
trueexpiration       *time.Duration   // 失效时间
truedeserializeFunc  DeserializeFunc  // 序列化回调函数
trueserializeFunc    SerializeFunc    // 反序列化回调函数
}

// 构建 cache
func buildCache(c *baseCache, cb *CacheBuilder) {
truec.clock = cb.clock
truec.size = cb.size
truec.loaderExpireFunc = cb.loaderExpireFunc
truec.expiration = cb.expiration
truec.addedFunc = cb.addedFunc
truec.deserializeFunc = cb.deserializeFunc
truec.serializeFunc = cb.serializeFunc
truec.evictedFunc = cb.evictedFunc
truec.purgeVisitorFunc = cb.purgeVisitorFunc
truec.stats = &stats{}
}

设置回调函数

这里仅列举了 loaderExpireFunc （key 过期时的回调函数）的具体实现；其他回调（淘汰 key 时的回调、序列化回调、反序列化回调等等）的设置方式相同。

1
2
3
4
5
6
7
8
// Set a loader function with expiration.
// loaderExpireFunc: create a new value with this function if cached value is expired.
// If nil returned instead of time.Duration from loaderExpireFunc than value will never expire.
// 设置过期回调函数
func (cb *CacheBuilder) LoaderExpireFunc(loaderExpireFunc LoaderExpireFunc) *CacheBuilder {
truecb.loaderExpireFunc = loaderExpireFunc
truereturn cb
}

设置淘汰策略

这里仅列举一个 LRU 淘汰策略 的设置（LFU，ARC 的设置方式相同）。

1
2
3
4
5
6
7
8
9
10
// 设置淘汰策略
func (cb *CacheBuilder) EvictType(tp string) *CacheBuilder {
truecb.tp = tp
truereturn cb
}

// 设置淘汰策略
func (cb *CacheBuilder) LRU() *CacheBuilder {
truereturn cb.EvictType(TYPE_LRU)
}

baseCache

baseCache 是 gcache 的基础数据结构，包含缓存大小、回调、失效时间、读写锁、命中率等，由 cache.go/baseCache 结构表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type baseCache struct {
trueclock            Clock
truesize             int
trueloaderExpireFunc LoaderExpireFunc
trueevictedFunc      EvictedFunc
truepurgeVisitorFunc PurgeVisitorFunc
trueaddedFunc        AddedFunc
truedeserializeFunc  DeserializeFunc
trueserializeFunc    SerializeFunc
trueexpiration       *time.Duration
truemu               sync.RWMutex
trueloadGroup        Group
true*stats
}

SimpleCache

gcache 中 SimpleCache 由 simple.go/SimpleCache 结构表示：

1
2
3
4
5
// SimpleCache has no clear priority for evict cache. It depends on key-value map order.
type SimpleCache struct {
truebaseCache
trueitems map[interface{}]*simpleItem
}

SimpleCache 中 simpleItem 由 simple.go/simpleItem 结构表示：

1
2
3
4
5
type simpleItem struct {
trueclock      Clock
truevalue      interface{}
trueexpiration *time.Time
}

源码参考 simple.go

设置超时时间

超时时间的设定方式：在当前时间的基础上加上超时时间 expiration。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Set a new key-value pair with an expiration time
func (c *SimpleCache) SetWithExpire(key, value interface{}, expiration time.Duration) error {
truec.mu.Lock()
truedefer c.mu.Unlock()
trueitem, err := c.set(key, value)
trueif err != nil {
truetruereturn err
true}

truet := c.clock.Now().Add(expiration)
trueitem.(*simpleItem).expiration = &t
truereturn nil
}

键值对失效判断

simpleItem 的超时判断，其他（lruItem，lfuItem，arcItem）超时判断逻辑相同，即检查过期时间 expiration 是否在当前时间 now 之前。

1
2
3
4
5
6
7
8
9
10
11
12
// IsExpired returns boolean value whether this item is expired or not.
// 键值对是否超时
func (si *simpleItem) IsExpired(now *time.Time) bool {
trueif si.expiration == nil {
truetruereturn false
true}
trueif now == nil {
truetruet := si.clock.Now()
truetruenow = &t
true}
truereturn si.expiration.Before(*now)
}

设置键值对

我们通过 SET 方法为 SimpleCache 设置键值对：

1
2
3
4
5
6
7
gc := gcache.New(3).
    Simple().
    Build()

gc.Set("k1", "v1")
gc.Set("k2", "v2")
gc.Set("k3", "v3")

如图，展示了设置上述 3 个键值对之后 SimpleCache 的状态（为了在接下来操作中表述简单，此处未设置失效时间）：
20191024171029

读取键值对

由于 SimpleCache 没有排序策略，读取操作不会改变键值对的相对排序。

缓存满时增加键值对

当 SimpleCache 缓存满时再增加键值对，会先执行淘汰策略。随机淘汰 items 中的键值对（因为 golang 中，map 遍历是随机的）。

1
gc.Set("k4", "v4")

：
如图，展示了随机淘汰 items 中 1 个键值对，并新增键值对过程中，SimpleCache 的变化（为了在接下来操作中表述简单，此处未设置失效时间）：
20191025000537
20191025000736
20191025000755

LRUCache

gcache 中 LRUCache 由 lru.go/LRUCache 结构表示：

1
2
3
4
5
6
// Discards the least recently used items first.
type LRUCache struct {
truebaseCache
trueitems     map[interface{}]*list.Element
trueevictList *list.List
}
  • baseCache 为缓存基础数据结构，包含缓存大小以及各种回调函数；
  • items 是一个 map 类型，可以在 O(1) 时间内找到指定键值对，值为 lruItem；
  • evictList 是一个双向链表，用来淘汰最近未使用的键值对，是实现 LRU 策略的关键结构；

LRUCache 中 lruItem 由 lru.go/lruItem 结构表示：

1
2
3
4
5
6
type lruItem struct {
trueclock      Clock
truekey        interface{}
truevalue      interface{}
trueexpiration *time.Time
}

设置键值对

我们通过 SET 方法为 LRUCache 设置键值对：

1
2
3
4
5
6
7
gc := gcache.New(3).
    LRU().
    Build()

gc.Set("k1", "v1")
gc.Set("k2", "v2")
gc.Set("k3", "v3")

如图，展示了设置上述 3 个键值对之后 LRUCache 的状态（为了在接下来操作中表述简单，此处未设置失效时间）：
20191009201627

关键代码：

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
// set a new key-value pair
func (c *LRUCache) Set(key, value interface{}) error {
truec.mu.Lock()
truedefer c.mu.Unlock()
true_, err := c.set(key, value)
truereturn err
}

func (c *LRUCache) set(key, value interface{}) (interface{}, error) {
truevar err error
trueif c.serializeFunc != nil {
truetruevalue, err = c.serializeFunc(key, value)
truetrueif err != nil {
truetruetruereturn nil, err
truetrue}
true}

true// Check for existing item
truevar item *lruItem
true// 查找 key 是否已经存在，如果存在直接更新对应的 value
trueif it, ok := c.items[key]; ok {
truetruec.evictList.MoveToFront(it)
truetrueitem = it.Value.(*lruItem)
truetrueitem.value = value
true} else {
truetrue// Verify size not exceeded
truetrue// 判断是否超出缓存大小，如果超出就先删除一个元素
truetrueif c.evictList.Len() >= c.size {
truetruetruec.evict(1)
truetrue}
truetrueitem = &lruItem{
truetruetrueclock: c.clock,
truetruetruekey:   key,
truetruetruevalue: value,
truetrue}
truetrue// 新数据加入链表首部
truetruec.items[key] = c.evictList.PushFront(item)
true}

trueif c.expiration != nil {
truetruet := c.clock.Now().Add(*c.expiration)
truetrueitem.expiration = &t
true}

trueif c.addedFunc != nil {
truetruec.addedFunc(key, value)
true}

truereturn item, nil
}

读取键值对

我们通过 LRUCache 方法读取 gcache 中的键值对。当 key 存在时，返回对应的键值对；当 key 不存在时返回错误 KeyNotFoundError（如果设置有回调，则为返回回调执行结果）。

会涉及到键值对顺序，hitCount、missCount 的变化。

  1. 读取成功
    执行 GET("k2") 读取键值对。缓存命中次数（hitCount）+1，k2 在被移动到淘汰链表首部。读取后成功后 LRUCache 状态（流程）：
    201910092017262.png
    201910241720102.png
    201910241717442.png

  2. 读取失败（访问不存在的键）
    执行 GET("k4") 读取键值对。缺失次数（missCount）+1，淘汰链表顺序不变，LRUCache 状态：
    201910092020042.png

关键代码：

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
// Get a value from cache pool using key if it exists.
// If it dose not exists key and has LoaderFunc,
// generate a value using `LoaderFunc` method returns value.
// 读取键值对
// 如果存在缓存，则返回；
// 否则，如果定义了 LoaderFunc 回调，则执行回调。
func (c *LRUCache) Get(key interface{}) (interface{}, error) {
truev, err := c.get(key, false)
trueif err == KeyNotFoundError {
truetruereturn c.getWithLoader(key, true)
true}
truereturn v, err
}

func (c *LRUCache) get(key interface{}, onLoad bool) (interface{}, error) {
truev, err := c.getValue(key, onLoad)
trueif err != nil {
truetruereturn nil, err
true}
trueif c.deserializeFunc != nil {
truetruereturn c.deserializeFunc(key, v)
true}
truereturn v, nil
}

func (c *LRUCache) getValue(key interface{}, onLoad bool) (interface{}, error) {
truec.mu.Lock()
trueitem, ok := c.items[key]
true// 命中缓存
trueif ok {
truetrueit := item.Value.(*lruItem)
truetrue// 缓存未过期
truetrueif !it.IsExpired(nil) {
truetruetruec.evictList.MoveToFront(item)
truetruetruev := it.value
truetruetruec.mu.Unlock()
truetruetrueif !onLoad {
truetruetruetruec.stats.IncrHitCount()
truetruetrue}
truetruetruereturn v, nil
truetrue}
truetruec.removeElement(item)
true}
truec.mu.Unlock()
trueif !onLoad {
truetruec.stats.IncrMissCount()
true}
truereturn nil, KeyNotFoundError
}

缓存满时增加键值对

当 LRUCache 缓存满时再增加键值对，会先执行淘汰策略。淘汰链表尾部键值对，并删除 items 中对应 key。

1
gc.Set("k5", "v5")

淘汰链表尾部键值对 和 items 对应元素：
20191009202529

关键代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// evict removes the oldest item from the cache.
func (c *LRUCache) evict(count int) {
truefor i := 0; i < count; i++ {
truetrueent := c.evictList.Back()
truetrueif ent == nil {
truetruetruereturn
truetrue} else {
truetruetruec.removeElement(ent)
truetrue}
true}
}

func (c *LRUCache) removeElement(e *list.Element) {
truec.evictList.Remove(e)
trueentry := e.Value.(*lruItem)
truedelete(c.items, entry.key)
trueif c.evictedFunc != nil {
truetrueentry := e.Value.(*lruItem)
truetruec.evictedFunc(entry.key, entry.value)
true}
}

k5 键值对，插入到链表头部位置：
20191009202241

LFUCache

gcache 中 LFUCache 由 lfu.go/LFUCache 结构表示：

1
2
3
4
5
6
7
// Discards the least frequently used items first.
// LFUCache 会优先删除访问频次最少的键值对
type LFUCache struct {
truebaseCache
trueitems    map[interface{}]*lfuItem
truefreqList *list.List // list for freqEntry
}
  • baseCache 为缓存基础数据结构，包含缓存大小以及各种回调函数；
  • items 是一个 map 类型，可以在 O(1) 时间内找到指定键值对，值为 lruItem；
  • freqList 是一个双向链表，用来淘汰最近未使用的键值对，是实现 LRU 策略的关键结构；

LFUCache 中 freqEntry 由 lfu.go/freqEntry 结构表示：

1
2
3
4
type freqEntry struct {
truefreq  uint
trueitems map[*lfuItem]struct{}
}

LFUCache 中 lfuItem 由 lfu.go/lfuItem 结构表示：

1
2
3
4
5
6
7
type lfuItem struct {
trueclock       Clock
truekey         interface{}
truevalue       interface{}
truefreqElement *list.Element
trueexpiration  *time.Time
}

如图，展示了未设置任何键值对时 LFUCache 的状态：
20191009194655

设置键值对

同样，我们通过 SET 方法为 LFUCache 设置键值对：

1
2
3
4
5
6
7
gc := gcache.New(3).
    LFU().
    Build()

gc.Set("k1", "v1")
gc.Set("k2", "v2")
gc.Set("k3", "v3")

如图，展示了设置上述 3 个键值对之后 LFUCache 的状态（为了在接下来操作中表述简单，此处未设置失效时间）：
20191009195606

读取键值对

我们通过 GET 方法读取 LFUCache 中的键值对。当 key 存在时，返回对应的键值对；当 key 不存在时返回错误 KeyNotFoundError（如果设置有回调，则为返回回调执行结果）。

读取操作会改变键值对所在 freqEntry 节点，同时 hitCount、missCount 也会随之变化。
读取失败时，与 LRUCache 的逻辑一致，这里不再说明。

以执行 GET("k1") 读取键值对为例：

  1. 删除 freqEntry(freq = 0) 节点 items 中的 key = lfuItem1 的键值对：
    201910091956502.png

  2. 创建 freqEntry(freq = 1) 新节点（插入到 freq = 0 节点之后），然后把 key = lfuItem1 的键值对添加到节点 items 中，并修改命中次数（hitCount）：
    201910092007472.png

注意：
随着读取操作的发生，freqList 会越来越长（如果某个 key 读取次数最多达到 N 次，那么 freqList 长度就等于 N + 1）。
这样的话，就可能会带来内存问题。

缓存满时增加键值对

当 LFUCache 缓存满时再增加键值对，会先执行淘汰策略。从链表首部（访问频次为 0 的节点）开始删除指定个数（默认 1）的键值对，并删除 items 中对应 key。

1
gc.Set("k5", "v5")

  1. 从链表首部节点开始选择待淘汰键值对：
    201910092008452.png

  2. 淘汰 步骤 1 中选定的键值对：
    201910092009262.png

  3. 新节点加入到链表首部节点（freq = 0）中，并更新 items：
    201910092029342.png

ARCCache

ARC(Adaptive Replacement Cache) 融合了 LRU 和 LFU 的特点，在二者之间取得一个平衡，同时也使得算法看起来更复杂一些。
gcache 中 ARCCache 由 arc.go/ARCCache 结构表示：

1
2
3
4
5
6
7
8
9
10
11
// Constantly balances between LRU and LFU, to improve the combined result.
type ARC struct {
truebaseCache
trueitems map[interface{}]*arcItem

truepart int
truet1   *arcList
truet2   *arcList
trueb1   *arcList
trueb2   *arcList
}

如图，展示了未设置任何键值对时 ARCCache 的状态：
20191012163848

相比 LRUCache，LFUCache 来讲，ARCCache 的逻辑复杂了很多。如图，给出 ARCCache 键值对转移状态图：
20191025102517

键值对状态图与失效时间有关，这里给出键值对的流转图示。

设置键值对

同样，我们通过 SET 方法为 ARCCache 设置键值对：

1
2
3
4
5
6
7
gc := gcache.New(3).
    ARC().
    Build()

gc.SetWithExpire("k1", "v1", 10 * time.Second)
gc.Set("k2", "v2")
gc.Set("k3", "v3")

ARCCache 的内部存储就复杂了很多，大致流程参考前面给的【ARCCache 键值对转移状态图】。键值对如下：
20191012165433

关键代码：

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
func (c *ARC) Set(key, value interface{}) error {
truec.mu.Lock()
truedefer c.mu.Unlock()
true_, err := c.set(key, value)
truereturn err
}

func (c *ARC) set(key, value interface{}) (interface{}, error) {
truevar err error
trueif c.serializeFunc != nil {
truetruevalue, err = c.serializeFunc(key, value)
truetrueif err != nil {
truetruetruereturn nil, err
truetrue}
true}

trueitem, ok := c.items[key]
trueif ok {
truetrueitem.value = value
true} else {
truetrueitem = &arcItem{
truetruetrueclock: c.clock,
truetruetruekey:   key,
truetruetruevalue: value,
truetrue}
truetruec.items[key] = item
true}

trueif c.expiration != nil {
truetruet := c.clock.Now().Add(*c.expiration)
truetrueitem.expiration = &t
true}

truedefer func() {
truetrueif c.addedFunc != nil {
truetruetruec.addedFunc(key, value)
truetrue}
true}()

trueif c.t1.Has(key) || c.t2.Has(key) {
truetruereturn item, nil
true}

true// 高频访问
true// 移动键值对 (from b1 to t2)
trueif elt := c.b1.Lookup(key); elt != nil {
truetruec.setPart(minInt(c.size, c.part+maxInt(c.b2.Len()/c.b1.Len(), 1)))
truetruec.replace(key)
truetruec.b1.Remove(key, elt)
truetruec.t2.PushFront(key)
truetruereturn item, nil
true}

true// 高频访问
true// 移动键值对 (from b2 to t2)
trueif elt := c.b2.Lookup(key); elt != nil {
truetruec.setPart(maxInt(0, c.part-maxInt(c.b1.Len()/c.b2.Len(), 1)))
truetruec.replace(key)
truetruec.b2.Remove(key, elt)
truetruec.t2.PushFront(key)
truetruereturn item, nil
true}

true// 缓存满：选择性淘汰 t1，b1，b2
trueif c.isCacheFull() && c.t1.Len()+c.b1.Len() == c.size {
truetrueif c.t1.Len() < c.size {
truetruetruec.b1.RemoveTail()
truetruetruec.replace(key)
truetrue} else {
truetruetruepop := c.t1.RemoveTail()
truetruetrueitem, ok := c.items[pop]
truetruetrueif ok {
truetruetruetruedelete(c.items, pop)
truetruetruetrueif c.evictedFunc != nil {
truetruetruetruetruec.evictedFunc(item.key, item.value)
truetruetruetrue}
truetruetrue}
truetrue}
true} else {
truetruetotal := c.t1.Len() + c.b1.Len() + c.t2.Len() + c.b2.Len()
truetrueif total >= c.size {
truetruetrueif total == (2 * c.size) {
truetruetruetrueif c.b2.Len() > 0 {
truetruetruetruetruec.b2.RemoveTail()
truetruetruetrue} else {
truetruetruetruetruec.b1.RemoveTail()
truetruetruetrue}
truetruetrue}
truetruetruec.replace(key)
truetrue}
true}

true// t1 新增键值对
truec.t1.PushFront(key)
truereturn item, nil
}

读取键值对

执行 GET("k1") 操作（第 1 次读），ARCCache 会将键值对从 t1 移到 t2。或者从 Ghost list 中捞回。

1
2
3
gc.Get("k1")
gc.Get("k2")
gc.Get("k3")

  1. 假如在访问的过程中键值对 k1 过期了，则会被移到 b1 中：
    20191025003420

  2. 可以看到，t1 中的其他键值对，依次被移动到了 t2 中：
    ![20191025003158](/images

  3. 再次执行 gc.Get("k2") 操作时，由于键值已经在 t2 中，会改变键值对的排序：
    20191025005129

  4. 再次执行 gc.Set("k1", "v1") 操作时，由于键值对已经在 b1 中，则会把 k1 捞出来，并且放到 t2 中（认为是高频访问）：
    20191025005827

关键代码：

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
53
54
55
56
57
58
59
60
61
62
63
64
65
// Get a value from cache pool using key if it exists. If not exists and it has LoaderFunc, it will generate the value using you have specified LoaderFunc method returns value.
func (c *ARC) Get(key interface{}) (interface{}, error) {
truev, err := c.get(key, false)
trueif err == KeyNotFoundError {
truetruereturn c.getWithLoader(key, true)
true}
truereturn v, err
}

func (c *ARC) get(key interface{}, onLoad bool) (interface{}, error) {
truev, err := c.getValue(key, onLoad)
trueif err != nil {
truetruereturn nil, err
true}
trueif c.deserializeFunc != nil {
truetruereturn c.deserializeFunc(key, v)
true}
truereturn v, nil
}

func (c *ARC) getValue(key interface{}, onLoad bool) (interface{}, error) {
truec.mu.Lock()
truedefer c.mu.Unlock()
trueif elt := c.t1.Lookup(key); elt != nil {
truetruec.t1.Remove(key, elt)
truetrueitem := c.items[key]
truetrueif !item.IsExpired(nil) {
truetruetruec.t2.PushFront(key)
truetruetrueif !onLoad {
truetruetruetruec.stats.IncrHitCount()
truetruetrue}
truetruetruereturn item.value, nil
truetrue} else {
truetruetrue// TODO else 可以去掉
truetruetruedelete(c.items, key)
truetruetruec.b1.PushFront(key)
truetruetrueif c.evictedFunc != nil {
truetruetruetruec.evictedFunc(item.key, item.value)
truetruetrue}
truetrue}
true}
trueif elt := c.t2.Lookup(key); elt != nil {
truetrueitem := c.items[key]
truetrueif !item.IsExpired(nil) {
truetruetruec.t2.MoveToFront(elt)
truetruetrueif !onLoad {
truetruetruetruec.stats.IncrHitCount()
truetruetrue}
truetruetruereturn item.value, nil
truetrue} else {
truetruetrue// TODO else 可以去掉
truetruetruedelete(c.items, key)
truetruetruec.t2.Remove(key, elt)
truetruetruec.b2.PushFront(key)
truetruetrueif c.evictedFunc != nil {
truetruetruetruec.evictedFunc(item.key, item.value)
truetruetrue}
truetrue}
true}

trueif !onLoad {
truetruec.stats.IncrMissCount()
true}
truereturn nil, KeyNotFoundError
}

缓存满时增加键值对

当缓存满时新增键值对，ARCCache 会淘汰 t1，b1，b2 中的数据（参考 SET 方法）。

图略

淘汰策略：

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
// replace
// 1. 淘汰数据 t1, t2 数据到 b1 b2
// 2. 从 items 中删除键值对
func (c *ARC) replace(key interface{}) {
trueif !c.isCacheFull() {
truetruereturn
true}
truevar old interface{}
trueif c.t1.Len() > 0 && ((c.b2.Has(key) && c.t1.Len() == c.part) || (c.t1.Len() > c.part)) {
truetrue// t1 淘汰到 b1
truetrueold = c.t1.RemoveTail()
truetruec.b1.PushFront(old)
true} else if c.t2.Len() > 0 {
truetrue// t2 淘汰到 b2
truetrueold = c.t2.RemoveTail()
truetruec.b2.PushFront(old)
true} else {
truetrue// t1 淘汰到 b1
truetrueold = c.t1.RemoveTail()
truetruec.b1.PushFront(old)
true}
trueitem, ok := c.items[old]
trueif ok {
truetrue// 删除已淘汰的数据
truetruedelete(c.items, old)
truetrueif c.evictedFunc != nil {
truetruetruec.evictedFunc(item.key, item.value)
truetrue}
true}
}

引用
操作系统之页面置换算法
谈谈缓存和基本的缓存算法
缓存算法（FIFO 、LRU、LFU三种算法的区别）
Go gcache 源码分析（图解）
常用缓存淘汰算法（LFU、LRU、ARC、FIFO、MRU）
缓存机制Cache ARC算法（一）
gcache 源码分析
阿里P8架构师谈：详解Memcached、Redis等缓存的特征、原理、应用
一文深入了解：分布式系统中的缓存架构
Ristretto is a fast, concurrent cache library built with a focus on performance and correctness.
Caffeine Cache-高性能Java本地缓存组件

0%