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 中定义：
代码语言：javascript复制type (
LoaderFunc func(interface{}) (interface{}, error) // 自动加载回调函数
LoaderExpireFunc func(interface{}) (interface{}, *time.Duration, error) // 过期回调函数
EvictedFunc func(interface{}, interface{}) // 淘汰回调函数
PurgeVisitorFunc func(interface{}, interface{}) // 清除所有 key 回调函数
AddedFunc func(interface{}, interface{}) // 新增 key 回调函数
DeserializeFunc func(interface{}, interface{}) (interface{}, error) // 反序列化回调函数
SerializeFunc func(interface{}, interface{}) (interface{}, error) // 序列化回调函数
)计数统计
•HitCount：命中次数•MissCount：未命中次数•LookupCount：查找次数（HitCount MissCount）•HitRate：命中率（HitCount / LookupCount）
官方代码[1] 注解版代码[2] godoc 文档[3]
基本架构
接口
代码语言：javascript复制type Cache interface {
Set(key, value interface{}) error
SetWithExpire(key, value interface{}, expiration time.Duration) error
Get(key interface{}) (interface{}, error)
GetIFPresent(key interface{}) (interface{}, error)
GetALL(checkExpired bool) map[interface{}]interface{}
get(key interface{}, onLoad bool) (interface{}, error)
Remove(key interface{}) bool
Purge()
Keys(checkExpired bool) []interface{}
Len(checkExpired bool) int
Has(key interface{}) bool
statsAccessor
}CacheBuilder
CacheBuilder 用来构造缓存对象，以及各种个性化化配置、策略。由 cache.go/CacheBuilder 结构表示：
代码语言：javascript复制cache.go[4] 中有详细注解。
// CacheBuilder 构造缓存对象，以及各种个性化化配置、策略。
// 构建 cache 时，会赋值给 baseCache 中对应的字段
type CacheBuilder struct {
clock Clock // cache 时钟
tp string // 缓存类型：TYPE_SIMPLE，TYPE_LRU，TYPE_LFU，TYPE_ARC
size int // 缓存大小
loaderExpireFunc LoaderExpireFunc // key 过期时的回调函数
evictedFunc EvictedFunc // 淘汰 key 时的回调函数
purgeVisitorFunc PurgeVisitorFunc // 清空缓存所有 key 时的回调函数
addedFunc AddedFunc // 新增 key 时的回调函数
expiration *time.Duration // 失效时间
deserializeFunc DeserializeFunc // 序列化回调函数
serializeFunc SerializeFunc // 反序列化回调函数
}
// 构建 cache
func buildCache(c *baseCache, cb *CacheBuilder) {
c.clock = cb.clock
c.size = cb.size
c.loaderExpireFunc = cb.loaderExpireFunc
c.expiration = cb.expiration
c.addedFunc = cb.addedFunc
c.deserializeFunc = cb.deserializeFunc
c.serializeFunc = cb.serializeFunc
c.evictedFunc = cb.evictedFunc
c.purgeVisitorFunc = cb.purgeVisitorFunc
c.stats = &stats{}
}设置回调函数
这里仅列举了 loaderExpireFunc （key 过期时的回调函数）的具体实现；其他回调（淘汰 key 时的回调、序列化回调、反序列化回调等等）的设置方式相同。
// 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 {
cb.loaderExpireFunc = loaderExpireFunc
return cb
}设置淘汰策略
这里仅列举一个 LRU 淘汰策略 的设置（LFU，ARC 的设置方式相同）。
// 设置淘汰策略
func (cb *CacheBuilder) EvictType(tp string) *CacheBuilder {
cb.tp = tp
return cb
}
// 设置淘汰策略
func (cb *CacheBuilder) LRU() *CacheBuilder {
return cb.EvictType(TYPE_LRU)
}baseCache
baseCache 是 gcache 的基础数据结构，包含缓存大小、回调、失效时间、读写锁、命中率等，由 cache.go/baseCache 结构表示：
代码语言：javascript复制type baseCache struct {
clock Clock
size int
loaderExpireFunc LoaderExpireFunc
evictedFunc EvictedFunc
purgeVisitorFunc PurgeVisitorFunc
addedFunc AddedFunc
deserializeFunc DeserializeFunc
serializeFunc SerializeFunc
expiration *time.Duration
mu sync.RWMutex
loadGroup Group
*stats
}SimpleCache
gcache 中 SimpleCache 由 simple.go/SimpleCache 结构表示：
代码语言：javascript复制// SimpleCache has no clear priority for evict cache. It depends on key-value map order.
type SimpleCache struct {
baseCache
items map[interface{}]*simpleItem
}SimpleCache 中 simpleItem 由 simple.go/simpleItem 结构表示：
代码语言：javascript复制type simpleItem struct {
clock Clock
value interface{}
expiration *time.Time
}源码参考 simple.go[5]
设置超时时间
超时时间的设定方式：在当前时间的基础上加上超时时间 expiration。
代码语言：javascript复制// Set a new key-value pair with an expiration time
func (c *SimpleCache) SetWithExpire(key, value interface{}, expiration time.Duration) error {
c.mu.Lock()
defer c.mu.Unlock()
item, err := c.set(key, value)
if err != nil {
return err
}
t := c.clock.Now().Add(expiration)
item.(*simpleItem).expiration = &t
return nil
}键值对失效判断
simpleItem 的超时判断，其他（lruItem，lfuItem，arcItem）超时判断逻辑相同，即检查过期时间 expiration 是否在当前时间 now 之前。
代码语言：javascript复制// IsExpired returns boolean value whether this item is expired or not.
// 键值对是否超时
func (si *simpleItem) IsExpired(now *time.Time) bool {
if si.expiration == nil {
return false
}
if now == nil {
t := si.clock.Now()
now = &t
}
return si.expiration.Before(*now)
}设置键值对
我们通过 SET 方法为 SimpleCache 设置键值对：
代码语言：javascript复制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 遍历是随机的）。
代码语言：javascript复制gc.Set("k4", "v4")：如图，展示了随机淘汰 items 中 1 个键值对，并新增键值对过程中，SimpleCache 的变化（为了在接下来操作中表述简单，此处未设置失效时间）：
20191025000537
20191025000736
20191025000755
LRUCache
gcache 中 LRUCache 由 lru.go/LRUCache 结构表示：
代码语言：javascript复制// Discards the least recently used items first.
type LRUCache struct {
baseCache
items map[interface{}]*list.Element
evictList *list.List
}• baseCache 为缓存基础数据结构，包含缓存大小以及各种回调函数；• items 是一个 map 类型，可以在 O(1) 时间内找到指定键值对，值为 lruItem；• evictList 是一个双向链表，用来淘汰最近未使用的键值对，是实现 LRU 策略的关键结构；
LRUCache 中 lruItem 由 lru.go/lruItem 结构表示：
代码语言：javascript复制type lruItem struct {
clock Clock
key interface{}
value interface{}
expiration *time.Time
}设置键值对
我们通过 SET 方法为 LRUCache 设置键值对：
代码语言：javascript复制gc := gcache.New(3).
LRU().
Build()
gc.Set("k1", "v1")
gc.Set("k2", "v2")
gc.Set("k3", "v3")如图，展示了设置上述 3 个键值对之后 LRUCache 的状态（为了在接下来操作中表述简单，此处未设置失效时间）：
20191009201627
关键代码：
代码语言：javascript复制// set a new key-value pair
func (c *LRUCache) Set(key, value interface{}) error {
c.mu.Lock()
defer c.mu.Unlock()
_, err := c.set(key, value)
return err
}
func (c *LRUCache) set(key, value interface{}) (interface{}, error) {
var err error
if c.serializeFunc != nil {
value, err = c.serializeFunc(key, value)
if err != nil {
return nil, err
}
}
// Check for existing item
var item *lruItem
// 查找 key 是否已经存在，如果存在直接更新对应的 value
if it, ok := c.items[key]; ok {
c.evictList.MoveToFront(it)
item = it.Value.(*lruItem)
item.value = value
} else {
// Verify size not exceeded
// 判断是否超出缓存大小，如果超出就先删除一个元素
if c.evictList.Len() >= c.size {
c.evict(1)
}
item = &lruItem{
clock: c.clock,
key: key,
value: value,
}
// 新数据加入链表首部
c.items[key] = c.evictList.PushFront(item)
}
if c.expiration != nil {
t := c.clock.Now().Add(*c.expiration)
item.expiration = &t
}
if c.addedFunc != nil {
c.addedFunc(key, value)
}
return item, nil
}读取键值对
我们通过 LRUCache 方法读取 gcache 中的键值对。当 key 存在时，返回对应的键值对；当 key 不存在时返回错误 KeyNotFoundError（如果设置有回调，则为返回回调执行结果）。
会涉及到键值对顺序，hitCount、missCount 的变化。
1.读取成功 执行 GET("k2") 读取键值对。缓存命中次数（hitCount） 1，k2 在被移动到淘汰链表首部。读取后成功后 LRUCache 状态（流程）：
20191009201726.png
20191024172010.png
20191024171744.png
2.读取失败（访问不存在的键） 执行 GET("k4") 读取键值对。缺失次数（missCount） 1，淘汰链表顺序不变，LRUCache 状态：
20191009202004.png
关键代码：
代码语言：javascript复制// 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) {
v, err := c.get(key, false)
if err == KeyNotFoundError {
return c.getWithLoader(key, true)
}
return v, err
}
func (c *LRUCache) get(key interface{}, onLoad bool) (interface{}, error) {
v, err := c.getValue(key, onLoad)
if err != nil {
return nil, err
}
if c.deserializeFunc != nil {
return c.deserializeFunc(key, v)
}
return v, nil
}
func (c *LRUCache) getValue(key interface{}, onLoad bool) (interface{}, error) {
c.mu.Lock()
item, ok := c.items[key]
// 命中缓存
if ok {
it := item.Value.(*lruItem)
// 缓存未过期
if !it.IsExpired(nil) {
c.evictList.MoveToFront(item)
v := it.value
c.mu.Unlock()
if !onLoad {
c.stats.IncrHitCount()
}
return v, nil
}
c.removeElement(item)
}
c.mu.Unlock()
if !onLoad {
c.stats.IncrMissCount()
}
return nil, KeyNotFoundError
}缓存满时增加键值对
当 LRUCache 缓存满时再增加键值对，会先执行淘汰策略。淘汰链表尾部键值对，并删除 items 中对应 key。
代码语言：javascript复制gc.Set("k5", "v5")淘汰链表尾部键值对 和 items 对应元素：
20191009202529
关键代码：
代码语言：javascript复制// evict removes the oldest item from the cache.
func (c *LRUCache) evict(count int) {
for i := 0; i < count; i {
ent := c.evictList.Back()
if ent == nil {
return
} else {
c.removeElement(ent)
}
}
}
func (c *LRUCache) removeElement(e *list.Element) {
c.evictList.Remove(e)
entry := e.Value.(*lruItem)
delete(c.items, entry.key)
if c.evictedFunc != nil {
entry := e.Value.(*lruItem)
c.evictedFunc(entry.key, entry.value)
}
}k5 键值对，插入到链表头部位置：
20191009202241
LFUCache
gcache 中 LFUCache 由 lfu.go/LFUCache 结构表示：
代码语言：javascript复制// Discards the least frequently used items first.
// LFUCache 会优先删除访问频次最少的键值对
type LFUCache struct {
baseCache
items map[interface{}]*lfuItem
freqList *list.List // list for freqEntry
}• baseCache 为缓存基础数据结构，包含缓存大小以及各种回调函数；• items 是一个 map 类型，可以在 O(1) 时间内找到指定键值对，值为 lruItem；• freqList 是一个双向链表，用来淘汰最近未使用的键值对，是实现 LRU 策略的关键结构；
LFUCache 中 freqEntry 由 lfu.go/freqEntry 结构表示：
代码语言：javascript复制type freqEntry struct {
freq uint
items map[*lfuItem]struct{}
}LFUCache 中 lfuItem 由 lfu.go/lfuItem 结构表示：
代码语言：javascript复制type lfuItem struct {
clock Clock
key interface{}
value interface{}
freqElement *list.Element
expiration *time.Time
}如图，展示了未设置任何键值对时 LFUCache 的状态：
20191009194655
设置键值对
同样，我们通过 SET 方法为 LFUCache 设置键值对：
代码语言：javascript复制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 的键值对：
20191009195650.png
2.创建 freqEntry(freq = 1) 新节点（插入到 freq = 0 节点之后），然后把 key = lfuItem1 的键值对添加到节点 items 中，并修改命中次数（hitCount）：
20191009200747.png
注意： 随着读取操作的发生，freqList 会越来越长（如果某个 key 读取次数最多达到 N 次，那么 freqList 长度就等于 N 1）。 这样的话，就可能会带来内存问题。
缓存满时增加键值对
当 LFUCache 缓存满时再增加键值对，会先执行淘汰策略。从链表首部（访问频次为 0 的节点）开始删除指定个数（默认 1）的键值对，并删除 items 中对应 key。
代码语言：javascript复制gc.Set("k5", "v5")1.从链表首部节点开始选择待淘汰键值对：
20191009200845.png
2.淘汰 步骤 1 中选定的键值对：
20191009200926.png
3.新节点加入到链表首部节点（freq = 0）中，并更新 items：
20191009202934.png
ARCCache
ARC(Adaptive Replacement Cache) 融合了 LRU 和 LFU 的特点，在二者之间取得一个平衡，同时也使得算法看起来更复杂一些。 gcache 中 ARCCache 由 arc.go/ARCCache 结构表示：
代码语言：javascript复制// Constantly balances between LRU and LFU, to improve the combined result.
type ARC struct {
baseCache
items map[interface{}]*arcItem
part int
t1 *arcList
t2 *arcList
b1 *arcList
b2 *arcList
}如图，展示了未设置任何键值对时 ARCCache 的状态：
20191012163848
相比 LRUCache，LFUCache 来讲，ARCCache 的逻辑复杂了很多。如图，给出 ARCCache 键值对转移状态图：
20191025102517
键值对状态图与失效时间有关，这里给出键值对的流转图示。
设置键值对
同样，我们通过 SET 方法为 ARCCache 设置键值对：
代码语言：javascript复制gc := gcache.New(3).
ARC().
Build()
gc.SetWithExpire("k1", "v1", 10 * time.Second)
gc.Set("k2", "v2")
gc.Set("k3", "v3")ARCCache 的内部存储就复杂了很多，大致流程参考前面给的【ARCCache 键值对转移状态图】。键值对如下：
20191012165433
关键代码：
代码语言：javascript复制func (c *ARC) Set(key, value interface{}) error {
c.mu.Lock()
defer c.mu.Unlock()
_, err := c.set(key, value)
return err
}
func (c *ARC) set(key, value interface{}) (interface{}, error) {
var err error
if c.serializeFunc != nil {
value, err = c.serializeFunc(key, value)
if err != nil {
return nil, err
}
}
item, ok := c.items[key]
if ok {
item.value = value
} else {
item = &arcItem{
clock: c.clock,
key: key,
value: value,
}
c.items[key] = item
}
if c.expiration != nil {
t := c.clock.Now().Add(*c.expiration)
item.expiration = &t
}
defer func() {
if c.addedFunc != nil {
c.addedFunc(key, value)
}
}()
if c.t1.Has(key) || c.t2.Has(key) {
return item, nil
}
// 高频访问
// 移动键值对 (from b1 to t2)
if elt := c.b1.Lookup(key); elt != nil {
c.setPart(minInt(c.size, c.part maxInt(c.b2.Len()/c.b1.Len(), 1)))
c.replace(key)
c.b1.Remove(key, elt)
c.t2.PushFront(key)
return item, nil
}
// 高频访问
// 移动键值对 (from b2 to t2)
if elt := c.b2.Lookup(key); elt != nil {
c.setPart(maxInt(0, c.part-maxInt(c.b1.Len()/c.b2.Len(), 1)))
c.replace(key)
c.b2.Remove(key, elt)
c.t2.PushFront(key)
return item, nil
}
// 缓存满：选择性淘汰 t1，b1，b2
if c.isCacheFull() && c.t1.Len() c.b1.Len() == c.size {
if c.t1.Len() < c.size {
c.b1.RemoveTail()
c.replace(key)
} else {
pop := c.t1.RemoveTail()
item, ok := c.items[pop]
if ok {
delete(c.items, pop)
if c.evictedFunc != nil {
c.evictedFunc(item.key, item.value)
}
}
}
} else {
total := c.t1.Len() c.b1.Len() c.t2.Len() c.b2.Len()
if total >= c.size {
if total == (2 * c.size) {
if c.b2.Len() > 0 {
c.b2.RemoveTail()
} else {
c.b1.RemoveTail()
}
}
c.replace(key)
}
}
// t1 新增键值对
c.t1.PushFront(key)
return item, nil
}读取键值对
执行 GET("k1") 操作（第 1 次读），ARCCache 会将键值对从 t1 移到 t2。或者从 Ghost list 中捞回。
gc.Get("k1")
gc.Get("k2")
gc.Get("k3")1.假如在访问的过程中键值对 k1 过期了，则会被移到 b1 中：
20191025003420
2.可以看到，t1 中的其他键值对，依次被移动到了 t2 中：
20191025003158
3.再次执行 gc.Get("k2") 操作时，由于键值已经在 t2 中，会改变键值对的排序：
20191025005129
4.再次执行 gc.Set("k1", "v1") 操作时，由于键值对已经在 b1 中，则会把 k1 捞出来，并且放到 t2 中（认为是高频访问）：
20191025005827
关键代码：
代码语言：javascript复制// 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) {
v, err := c.get(key, false)
if err == KeyNotFoundError {
return c.getWithLoader(key, true)
}
return v, err
}
func (c *ARC) get(key interface{}, onLoad bool) (interface{}, error) {
v, err := c.getValue(key, onLoad)
if err != nil {
return nil, err
}
if c.deserializeFunc != nil {
return c.deserializeFunc(key, v)
}
return v, nil
}
func (c *ARC) getValue(key interface{}, onLoad bool) (interface{}, error) {
c.mu.Lock()
defer c.mu.Unlock()
if elt := c.t1.Lookup(key); elt != nil {
c.t1.Remove(key, elt)
item := c.items[key]
if !item.IsExpired(nil) {
c.t2.PushFront(key)
if !onLoad {
c.stats.IncrHitCount()
}
return item.value, nil
} else {
// TODO else 可以去掉
delete(c.items, key)
c.b1.PushFront(key)
if c.evictedFunc != nil {
c.evictedFunc(item.key, item.value)
}
}
}
if elt := c.t2.Lookup(key); elt != nil {
item := c.items[key]
if !item.IsExpired(nil) {
c.t2.MoveToFront(elt)
if !onLoad {
c.stats.IncrHitCount()
}
return item.value, nil
} else {
// TODO else 可以去掉
delete(c.items, key)
c.t2.Remove(key, elt)
c.b2.PushFront(key)
if c.evictedFunc != nil {
c.evictedFunc(item.key, item.value)
}
}
}
if !onLoad {
c.stats.IncrMissCount()
}
return nil, KeyNotFoundError
}缓存满时增加键值对
当缓存满时新增键值对，ARCCache 会淘汰 t1，b1，b2 中的数据（参考 SET 方法）。
图略
淘汰策略：
代码语言：javascript复制// replace
// 1. 淘汰数据 t1, t2 数据到 b1 b2
// 2. 从 items 中删除键值对
func (c *ARC) replace(key interface{}) {
if !c.isCacheFull() {
return
}
var old interface{}
if c.t1.Len() > 0 && ((c.b2.Has(key) && c.t1.Len() == c.part) || (c.t1.Len() > c.part)) {
// t1 淘汰到 b1
old = c.t1.RemoveTail()
c.b1.PushFront(old)
} else if c.t2.Len() > 0 {
// t2 淘汰到 b2
old = c.t2.RemoveTail()
c.b2.PushFront(old)
} else {
// t1 淘汰到 b1
old = c.t1.RemoveTail()
c.b1.PushFront(old)
}
item, ok := c.items[old]
if ok {
// 删除已淘汰的数据
delete(c.items, old)
if c.evictedFunc != nil {
c.evictedFunc(item.key, item.value)
}
}
}引用 操作系统之页面置换算法[6] 谈谈缓存和基本的缓存算法[7] 缓存算法（FIFO 、LRU、LFU三种算法的区别）[8] Go gcache 源码分析（图解）[9] 常用缓存淘汰算法（LFU、LRU、ARC、FIFO、MRU）[10] 缓存机制Cache ARC算法（一）[11] gcache 源码分析[12] 阿里P8架构师谈：详解Memcached、Redis等缓存的特征、原理、应用[13] 一文深入了解：分布式系统中的缓存架构[14]
References
[1] 官方代码: https://github.com/bluele/gcache
[2] 注解版代码: https://github.com/LeungGeorge/gcache
[3] godoc 文档: https://godoc.org/github.com/bluele/gcache
[4] cache.go: https://github.com/LeungGeorge/gcache/blob/master/cache.go
[5] simple.go: https://github.com/LeungGeorge/gcache/blob/master/simple.go
[6] 操作系统之页面置换算法: https://www.cnblogs.com/fkissx/p/4712959.html
[7] 谈谈缓存和基本的缓存算法: https://www.ezlippi.com/blog/2015/02/cache.html
[8] 缓存算法（FIFO 、LRU、LFU三种算法的区别）: https://www.cnblogs.com/hongdada/p/10406902.html
[9] Go gcache 源码分析（图解）: https://segmentfault.com/a/1190000020002827?utm_source=tag-newest
[10] 常用缓存淘汰算法（LFU、LRU、ARC、FIFO、MRU）: https://blog.csdn.net/youanyyou/article/details/78989956
[11] 缓存机制Cache ARC算法（一）: https://blog.csdn.net/WSKINGS/article/details/46416451
[12] gcache 源码分析: http://mckee.cn/golang/gcache
[13] 阿里P8架构师谈：详解Memcached、Redis等缓存的特征、原理、应用: https://youzhixueyuan.com/explain-the-principles-of-memcached-and-redis.html
[14] 一文深入了解：分布式系统中的缓存架构: https://juejin.im/entry/5b59615a5188251af86bf5c9
