cachego内存模型原理剖析

cachego 内存模型原理剖析

cachego github地址
cachego 是一个拥有分片机制的轻量级内存缓存库，API 友好，支持多种数据淘汰机制，可以应用于所有的 GoLang 应用程序中

功能特性

  • 以键值对形式缓存数据，极简的 API 设计风格
  • 引入 option function 模式，简化创建缓存参数
  • 提供 ttl 过期机制，支持限制键值对数量
  • 提供 lru 清理机制，提供 lfu 清理机制
  • 引入分片机制提高并发，分片与内存淘汰策略可灵活搭配
  • 支持懒清理机制，每一次访问的时候判断是否过期
  • 支持哨兵清理机制，每隔一定的时间间隔进行清理
  • 自带 singleflight 机制，减少缓存穿透的伤害
  • 支持上报缓存状况，可自定义多个缓存上报点

LRU算法

LRU（Least Recently Used）称为最近最少使用算法。基本的思想是：长期不被使用的数据，在未来被用到的几率也不大，因此当新的数据进来时，就可以优先将这些数据替换掉。

算法实现

cachego LRU策略底层实现为双向链表，头部为最活跃元素，尾部为最近最少使用元素。元素在使用后(插入/查询/更新)元素会移动到头部，当元素数超限后从尾部移除元素以供插入新元素

LRU算法实现

核心代码解读

  • lruCache 元素存储结构体
1
2
3
4
5
6
7
8
9
type lruCache struct {
	*config

	elementMap  map[string]*list.Element // map，存在性判断;快速获取元素值
	elementList *list.List // 双向链表用于实现LRU
	lock        sync.RWMutex // 读写锁

	loader *loader
}
  • set操作
    1
    2
    3
    4
    5
    6
    7
    func (lc *lruCache) evict() (evictedValue interface{}) { // 内存淘汰策略
    	if element := lc.elementList.Back(); element != nil { // lru队列尾部先过期
    		return lc.removeElement(element)
    	}

    	return nil
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (lc *lruCache) set(key string, value interface{}, ttl time.Duration) (evictedValue interface{}) {
	element, ok := lc.elementMap[key]
	if ok { // update更新操作
		entry := lc.unwrap(element)
		entry.setup(key, value, ttl)

		lc.elementList.MoveToFront(element) // 元素移到队首
		return nil
	}

	if lc.maxEntries > 0 && lc.elementList.Len() >= lc.maxEntries { // 队列已满, 从队尾移除最近最少访问的元素
		evictedValue = lc.evict()
	}

	element = lc.elementList.PushFront(newEntry(key, value, ttl, lc.now)) // 新建元素, 头插
	lc.elementMap[key] = element

	return evictedValue
}
  • get操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    func (lc *lruCache) get(key string) (value interface{}, found bool) {
    	element, ok := lc.elementMap[key] // map存在性断定
    	if !ok {
    		return nil, false
    	}

    	entry := lc.unwrap(element)
    	if entry.expired(0) { // 过期直接判定不存在
    		return nil, false
    	}

    	lc.elementList.MoveToFront(element) // 移到队首
    	return entry.value, true
    }

总结

  • 代码实现上相对简单，通过map+双向链表实现LRU算法，核心set、get逻辑清晰
  • 不足处: 虽然有定时任务扫描过期key，但get时对于过期key未立即删除，会存在隐患，若队尾元素未过期，存在过期元素在队列中间，则理论上应该优先淘汰过期key。如果需要严格遵守LRU则可忽略此问题，因此可根据实际业务决定是否改造这一点

LFU算法

LFU（least frequently used）最近最不经常使用的算法，对于每个数据，维护其使用的次数以及最近的使用时间，删除的策略是：优先删除使用次数最少的数据，如果存在多个使用次数相同的数据，则优先删除最远一次使用的数据。

算法实现

cachego 是基于最小堆实现的LFU，使用 最小堆 来维护按访问频率排序的元素。当元素被访问时，更新其访问频率。当缓存满时，使用 最小堆 删除访问频率最小的元素

  • 最小堆
    一棵完全二叉树，非叶子结点的值不大于左孩子和右孩子的值
    小根堆

核心代码解读

  • lfuCache结构体

    1
    2
    3
    4
    5
    6
    7
    8
    9
    type lfuCache struct {
    	*config

    	itemMap  map[string]*heap.Item // 同样的map，存在性判断及常数get
    	itemHeap *heap.Heap // 小根堆
    	lock     sync.RWMutex

    	loader *loader
    }

  • set操作

    1
    2
    3
    4
    5
    6
    7
    func (lc *lfuCache) evict() (evictedValue interface{}) { // 内存淘汰策略
    	if item := lc.itemHeap.Pop(); item != nil { // 小根堆移除顶端元素
    		return lc.removeItem(item)
    	}

    	return nil
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (lc *lfuCache) set(key string, value interface{}, ttl time.Duration) (evictedValue interface{}) {
	item, ok := lc.itemMap[key]
	if ok {
		entry := lc.unwrap(item)
		entry.setup(key, value, ttl)

		item.Adjust(item.Weight() + 1) // 核心访问次数加1,调整小根堆
		return nil
	}

	if lc.maxEntries > 0 && lc.itemHeap.Size() >= lc.maxEntries { // 过期驱除顶端key
		evictedValue = lc.evict()
	}

	item = lc.itemHeap.Push(0, newEntry(key, value, ttl, lc.now)) // 加入小根堆
	lc.itemMap[key] = item

	return evictedValue
}
  • get操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    func (lc *lfuCache) get(key string) (value interface{}, found bool) {
    	item, ok := lc.itemMap[key]
    	if !ok {
    		return nil, false
    	}

    	entry := lc.unwrap(item)
    	if entry.expired(0) { // 过期判断
    		return nil, false
    	}

    	item.Adjust(item.Weight() + 1) // 访问次数加一
    	return entry.value, true
    }

总结

  • 巧妙利用小根堆特性实现LFU，每次过期等删除操作只需移除顶端元素即可，增、改、查操作访问次数自增后堆结点元素需交换保证最小堆特性
  • 不足处: 同样存在get操作唯一出过期key问题

Standard算法

cachego 默认存储及内存淘汰策略, 底层使用go原生map实现

算法实现

go 原生map

核心代码解读

  • standardCache结构体

    1
    2
    3
    4
    5
    6
    7
    8
    type standardCache struct {
    	*config

    	entries map[string]*entry // 原生map, entry存储key、value、过期时间等
    	lock    sync.RWMutex

    	loader *loader
    }

  • set操作

    1
    2
    3
    4
    5
    6
    7
    func (sc *standardCache) evict() (evictedValue interface{}) { // 内存淘汰策略
    	for key := range sc.entries { // 随机过期key
    		return sc.remove(key)
    	}

    	return nil
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (sc *standardCache) set(key string, value interface{}, ttl time.Duration) (evictedValue interface{}) {
	entry, ok := sc.entries[key]
	if ok {
		entry.setup(key, value, ttl)
		return nil
	}

	if sc.maxEntries > 0 && sc.size() >= sc.maxEntries { // 超限随机过期key
		evictedValue = sc.evict()
	}

	sc.entries[key] = newEntry(key, value, ttl, sc.now)
	return evictedValue
}
  • get操作
    1
    2
    3
    4
    5
    6
    7
    8
    func (sc *standardCache) get(key string) (value interface{}, found bool) {
    	entry, ok := sc.entries[key]
    	if ok && !entry.expired(0) {
    		return entry.value, true
    	}

    	return nil, false
    }

总结

  • gocahce支持三套内存模型以供用户选择底层存储及内存淘汰策略
  • 提供 ttl 过期机制，支持限制键值对数量
  • 支持懒清理机制，每一次访问的时候判断是否过期