【导读】本文对本地缓存库 gocache 做了详细分析。
gcache 是一个用 go 实现的并发安全的本地缓存库。他可以实现如下功能:
其实 github 上已经有了很详细的例子,其中有简单 key/value、设置超时时间、设置淘汰策略、设置回调函数等各种例子。这里简单摘抄一些简单的例子:
package main
import (
"github.com/bluele/gcache"
"fmt"
)
func main() {
gc := gcache.New(20).
LRU().
Build()
gc.Set("key", "ok")
value, err := gc.Get("key")
if err != nil {
panic(err)
}
fmt.Println("Get:", value)
}
Get: ok
package main
import (
"github.com/bluele/gcache"
"fmt"
"time"
)
func main() {
gc := gcache.New(20).
LRU().
Build()
gc.SetWithExpire("key", "ok", time.Second*10)
value, _ := gc.Get("key")
fmt.Println("Get:", value)
// Wait for value to expire
time.Sleep(time.Second*10)
value, err = gc.Get("key")
if err != nil {
panic(err)
}
fmt.Println("Get:", value)
}
Get: ok
// 10 seconds later, new attempt:
panic: ErrKeyNotFound
package main
import (
"github.com/bluele/gcache"
"fmt"
)
func main() {
gc := gcache.New(20).
LRU().
LoaderFunc(func(key interface{}) (interface{}, error) {
return "ok", nil
}).
Build()
value, err := gc.Get("key")
if err != nil {
panic(err)
}
fmt.Println("Get:", value)
}
Get: ok
// 缓存 builder 对象,存放时间、大小和各种回调函数
type CacheBuilder struct {
clock Clock
tp string
size int
loaderExpireFunc LoaderExpireFunc
evictedFunc EvictedFunc
purgeVisitorFunc PurgeVisitorFunc
addedFunc AddedFunc
expiration *time.Duration
deserializeFunc DeserializeFunc
serializeFunc SerializeFunc
}
// 设置策略 设置 CacheBuilder 的回调函数属性
func (cb *CacheBuilder) LRU() *CacheBuilder {
return cb.EvictType(TYPE_LRU)
}
// 设置过期时间 设置 CacheBuilder 的 Expiration 属性
func (cb *CacheBuilder) Expiration(expiration time.Duration) *CacheBuilder {
cb.expiration = &expiration
return cb
}
// 设置驱除回调函数
func (cb *CacheBuilder) EvictedFunc(evictedFunc EvictedFunc) *CacheBuilder {
cb.evictedFunc = evictedFunc
return cb
}
// 判断 size 和类型
func (cb *CacheBuilder) Build() Cache {
if cb.size <= 0 && cb.tp != TYPE_SIMPLE {
panic("gcache: Cache size <= 0")
}
return cb.build()
}
// 根据 type 来新建相对应的 cache 对象
func (cb *CacheBuilder) build() Cache {
switch cb.tp {
case TYPE_SIMPLE:
return newSimpleCache(cb)
case TYPE_LRU:
return newLRUCache(cb)
case TYPE_LFU:
return newLFUCache(cb)
case TYPE_ARC:
return newARC(cb)
default:
panic("gcache: Unknown type " + cb.tp)
}
}
// 举例一个 SimpleCache
func newSimpleCache(cb *CacheBuilder) *SimpleCache {
c := &SimpleCache{}
buildCache(&c.baseCache, cb)
c.init()
c.loadGroup.cache = c
return c
}
// init 初始化 simple 中的 map
func (c *SimpleCache) init() {
if c.size <= 0 {
c.items = make(map[interface{}]*simpleItem)
} else {
c.items = make(map[interface{}]*simpleItem, c.size)
}
}
// 初始化回调函数
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{}
}
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
}
type statsAccessor interface {
HitCount() uint64
MissCount() uint64
LookupCount() uint64
HitRate() float64
}
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 中最简单的一种,其中比较重要的函数就是 Get,Set。
在 SimpleCache 结构体中 items 保存这 simpleItem。simpleItem 结构体中保存具体值和过期时间。
Get,Set 函数就是通过操作 items 属性来保存和获取缓存中的值的。下面我们详细看一下代码:
type SimpleCache struct {
baseCache
items map[interface{}]*simpleItem
}
type simpleItem struct {
clock Clock
value interface{}
expiration *time.Time
}
func (c *SimpleCache) 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
}
}
// 检查是否存在 key
item, ok := c.items[key]
if ok {
item.value = value
} else {
// 检查是否超过设置的大小范围
if (len(c.items) >= c.size) && c.size > 0 {
// 如果超过大小则驱逐一个
c.evict(1)
}
// 组成 simpleItem 对象
item = &simpleItem{
clock: c.clock,
value: value,
}
c.items[key] = 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
}
// SimpleCache 驱逐方法
// 驱逐策略则是最简单的淘汰一个,因为 map 的特性 range 访问的是随机的数据。所以驱逐出去的数据也是随机的一个。
func (c *SimpleCache) evict(count int) {
now := c.clock.Now()
current := 0
for key, item := range c.items {
if current >= count {
return
}
if item.expiration == nil || now.After(*item.expiration) {
defer c.remove(key)
current++
}
}
}
// get 函数 从缓存中获取数据
func (c *SimpleCache) get(key interface{}, onLoad bool) (interface{}, error) {
// 内部方法根据 key 获取值
v, err := c.getValue(key, onLoad)
if err != nil {
return nil, err
}
if c.deserializeFunc != nil {
return c.deserializeFunc(key, v)
}
return v, nil
}
// 内部获取方法
// 1. 加锁
// 2. 判断是否过期 如果过期直接删除数据
// 3. 如果没有过期则返回数据 增加 hit 基数器
// 4. 如果没有命中 增加 MissCount
func (c *SimpleCache) getValue(key interface{}, onLoad bool) (interface{}, error) {
c.mu.Lock()
item, ok := c.items[key]
if ok {
if !item.IsExpired(nil) {
v := item.value
c.mu.Unlock()
if !onLoad {
c.stats.IncrHitCount()
}
return v, nil
}
c.remove(key)
}
c.mu.Unlock()
if !onLoad {
c.stats.IncrMissCount()
}
return nil, KeyNotFoundError
}
LRU 在之前已经介绍过了,意思是最近最少使用。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。
gcache 实现的方法是通过链表来实现这个策略。当每次 get 或者 set 之后则把这个节点放到链表的头部,当需要超过 size 时则删除链表尾部的节点数据。这样就实现了最近最少使用的策略。
type LRUCache struct {
baseCache
items map[interface{}]*list.Element
evictList *list.List
}
type lruItem struct {
clock Clock
key interface{}
value interface{}
expiration *time.Time
}
// 先加锁防止多线程修改数据,调用内部 set 方法设置数据。
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
// 从 items map 中获取值
if it, ok := c.items[key]; ok {
// 如果 key 原本就存在,则重新设置然后移动节点到链表的头部
c.evictList.MoveToFront(it)
item = it.Value.(*lruItem)
item.value = value
} else {
// 如果超过 size 则调用 evict 函数根据 LRU 策略去除缓存中的一个数据
if c.evictList.Len() >= c.size {
c.evict(1)
}
// 创建对象然后放入链表和 items 中
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
}
// 判断调用 added 回调函数
if c.addedFunc != nil {
c.addedFunc(key, value)
}
return item, nil
}
// 驱逐函数
func (c *LRUCache) evict(count int) {
// 循环删除链表尾部的节点
for i := 0; i < count; i++ {
ent := c.evictList.Back()
if ent == nil {
return
} else {
c.removeElement(ent)
}
}
}
LFU:意思是最近最不常用。LFU Cache 先淘汰一定时间内被访问次数最少的页面。
LFU 策略,淘汰的是访问次数最少的,意味着 cache 需要保存每个缓存数据的访问次数。但如何保存访问次数呢,我们可以看下面的结构体定义。
items map[interface{}]*lfuItem :保存数据,保证访问时候的高效
lfuItem:保存在 map 中,其中存放这 key、value、过期时间、一个链表节点的地址。这个地址用来方便操作链表中的数据。
freqList:链表结构,保存 freqEntry
freqEntry:包含两个字段一个是 freq 用来保存访问次数,另一个是 items map 类型用来保存次访问次数的具体数据,可以是多个
gcache 的 LFU 使用一个 map 来保存数据 一个链表(包含次数和 map)来保存缓存中数据被访问的次数。初次 set 时访问次数默认为 0。如果淘汰则是淘汰被访问次数最少的,则可以从链表的头部开始扫描,一直找到最少的。
图一 是 set5 个字符串到 cache 中,5 个字符串不重复。items 中的数据我们不看只画了链表中的数据状态。
这个时候链表中只有一个节点,这个节点数据中的 freq 为 0,意味着这个节点中的数据都是没有被访问的。
图二 是经过几次 get 和一次 set 操作后的链表数据结果。可以看到链表的每一个节点都代表着一个访问次数并且依次递增。
每次 get 访问数据时候通过上面提到的 lfuItem 中的指针获取到节点在链表所在的位置,把数据往后移动一个节点。如果没有节点测创建一个以此类推。那么得到的结果就是越靠近头部的数据访问次数是最少的。如果淘汰则优先淘汰这些数据。
type LFUCache struct {
baseCache
items map[interface{}]*lfuItem
freqList *list.List // list for freqEntry
}
type freqEntry struct {
freq uint
items map[*lfuItem]struct{}
}
type lfuItem struct {
clock Clock
key interface{}
value interface{}
freqElement *list.Element
expiration *time.Time
}
func (c *LFUCache) Set(key, value interface{}) error {
c.mu.Lock()
defer c.mu.Unlock()
_, err := c.set(key, value)
return err
}
// set 内部方法
func (c *LFUCache) 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
}
}
// 检查 key 是否存在
item, ok := c.items[key]
if ok {
// 存在则直接赋值
item.value = value
} else {
// 不存在并且数量超出则执行驱逐函数
if len(c.items) >= c.size {
c.evict(1)
}
// 新建 item 对象
item = &lfuItem{
clock: c.clock,
key: key,
value: value,
freqElement: nil,
}
// 把新建的 lfuitem 对象放到链表第一个节点中
el := c.freqList.Front()
fe := el.Value.(*freqEntry)
fe.items[item] = struct{}{}
item.freqElement = el
c.items[key] = 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
}
// 驱逐函数
func (c *LFUCache) evict(count int) {
// 获取链表第一个节点
entry := c.freqList.Front()
// 循环 count
for i := 0; i < count; {
if entry == nil {
return
} else {
// 循环判断啊链表节点中是否有数据 如果没有则调用 next 继续循环
for item, _ := range entry.Value.(*freqEntry).items {
if i >= count {
return
}
c.removeItem(item)
i++
}
entry = entry.Next()
}
}
}
func (c *LFUCache) 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
}
// 判断是否过期,如果没过期则获取并且执行 increment 函数操作链表
func (c *LFUCache) getValue(key interface{}, onLoad bool) (interface{}, error) {
c.mu.Lock()
item, ok := c.items[key]
if ok {
if !item.IsExpired(nil) {
c.increment(item)
v := item.value
c.mu.Unlock()
if !onLoad {
c.stats.IncrHitCount()
}
return v, nil
}
c.removeItem(item)
}
c.mu.Unlock()
if !onLoad {
c.stats.IncrMissCount()
}
return nil, KeyNotFoundError
}
// 将 lfuItem 放入下一个节点中的 map 中,如果没有则创建一个新的 lfuItem
func (c *LFUCache) increment(item *lfuItem) {
currentFreqElement := item.freqElement
currentFreqEntry := currentFreqElement.Value.(*freqEntry)
nextFreq := currentFreqEntry.freq + 1
delete(currentFreqEntry.items, item)
nextFreqElement := currentFreqElement.Next()
if nextFreqElement == nil {
nextFreqElement = c.freqList.InsertAfter(&freqEntry{
freq: nextFreq,
items: make(map[*lfuItem]struct{}),
}, currentFreqElement)
}
nextFreqElement.Value.(*freqEntry).items[item] = struct{}{}
item.freqElement = nextFreqElement
}
ARC:Adaptive Replacement Cache,ARC 介于 LRU 和 LFU 之间。
ARC 是介于 LRU 和 LFU 之间的算法。也是通过 map 来存储数据,保证存取的性能。那是如何实现 LRU 和 LFU 又是如何平衡两个策略的呢?
结构体可以参看下面的代码:
items
: map 数据结构保存 key,value 则是 arcItem 结构体,其中包含了 key、value、过期时间。注意其中没有像 LFU 的链表指针。t1
:LRU 策略,set 之后会放入 t1 中限制数量跟整个 cache 数量相同。t2
:LFU 策略,当 get 访问之后会从 t1 移动到 t2 之中,不过无论访问几次都会在 t2 之中,不像 LFU 一样会记录访问次数。b1
:接收 t1(LRU)策略淘汰的缓存数据。如果超过 size 则直接从 cache 中删除。b2
:接收 t2(LFU)策略淘汰的缓存数据。跟 b1 一样超过 size 也会从 cache 中删除。那每次 Set、Get 数据又是怎么流动的呢?下面图解:
图一:是初始化并且添加 5 条数据之后 cache 内部数据结构。items 保存全部数据,因为没有访问数据则所有数据都会放到 t1 中。
图二:获取了aaa、bbb、ddd、eee
4 个数据,然后有 set 了 fff 到 cache 中。假设这个 cache 的 size 为 5。
其中aaa、bbb、ddd、eee
被移动到了 t2 中,剩下的 ccc 没有访问则会继续保留再 t1 之中。但是最后一条语句又设置了fff
到 cache 中。发现 size 已经满则需要淘汰一个数据,则会淘汰 t1 中的数据 ccc 移动到 b1 中。items 之中则没有 ccc 数据了。
最终的数据流动如下图:
type ARC struct {
baseCache
items map[interface{}]*arcItem
part int
t1 *arcList
t2 *arcList
b1 *arcList
b2 *arcList
}
type arcItem struct {
clock Clock
key interface{}
value interface{}
expiration *time.Time
}
type arcList struct {
l *list.List
keys map[interface{}]*list.Element
}
func (c *ARC) Set(key, value interface{}) error {
c.mu.Lock()
defer c.mu.Unlock()
_, err := c.set(key, value)
return err
}
// 1. 判断缓存中是否有数据
// 2. 在 b1,b2 中查看是否存在,如果存在则删除 b1 b2 重新放入到 t2 中
// 3.
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
}
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
}
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
}
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)
}
}
c.t1.PushFront(key)
return item, nil
}
如果 t1 中存在则从 t1 移动到 t2,如果存在再 t2 之中则放到 t2 的头部节点。
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 {
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 {
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
}
自此 gcache 所有的策略都已经分析完了。看完分析可以看出来 gcache 支持的策略很多,并且使用十分简单。只要在声明的时候确定好策略就可以使用对应的策略。更加支持各种回调函数,让逻辑更加灵活复合各种需求。
写这篇文章也在网上找了一些资料,但是都不是特别的详细所以不停的调试和画图分析出来的结果。希望能对大家能有所帮助。
转自:
segmentfault.com/a/1190000020002827
- EOF -
Go 开发大全
参与维护一个非常全面的Go开源技术资源库。日常分享 Go, 云原生、k8s、Docker和微服务方面的技术文章和行业动态。
关注后获取
回复 Go 获取6万star的Go资源库
分享、点赞和在看
支持我们分享更多好文章,谢谢!