一、LRU
SET
GET
DELETE
Loader
二、LFU
SET
GET
DELETE
Loader
- 多种淘汰策略，LRU、LFU、simple；
- 提供loder，singleflight方式；
- 时间窗口的概念是通过整个cache表的过期时间来实现的；
- 过期删除，访问时才被删除；
- 过期和淘汰策略是分开的：访问过期会删除，添加元素会淘汰（淘汰时不看过期时间）；
- LRU/LFU更新记录时开销O(1)，假如用堆之类相比开销很大；
大锁的改进：
读写锁
锁的粒度，整个map，单独item
锁的实现：CAS
一、LRU
LRU淘汰的思想是近期不被访问的元素，在未来也不太会被访问，时间的局部性。
缺点就是低频、偶发的访问会干扰，因为访问一次就会被放在最热，“容错性”较差。
// Discards the least recently used items first.
type LRUCache struct {
baseCache
items map[interface{}]*list.Element //k-(lruItem为value的链表节点)
evictList *list.List. //维护顺序的双向链表
}
type lruItem struct {
clock Clock
key interface{}
value interface{}
expiration *time.Time
}
SET
更新位置，更新value，更新时间
检查淘汰，新增节点，更新时间；
// 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
// Check for existing item
var item *lruItem
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) //添加元素
}
//如果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
}
// Set a new key-value pair with an expiration time
func (c *LRUCache) 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.(*lruItem).expiration = &t
return nil
}
淘汰
链表的实现方便清除一个/多个；
// 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)
}
}
}
GET
// 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.
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) 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
}
DELETE
// Remove removes the provided key from the cache.
func (c *LRUCache) Remove(key interface{}) bool {
c.mu.Lock()
defer c.mu.Unlock()
return c.remove(key)
}
func (c *LRUCache) remove(key interface{}) bool {
if ent, ok := c.items[key]; ok {
c.removeElement(ent)
return true
}
return false
}
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)
}
}
Loader
- 用户提供loader方式，loaderExpireFunc可以基于key获取到对应的value；
// Set a loader function.
// loaderFunc: create a new value with this function if cached value is expired.
func (cb *CacheBuilder) LoaderFunc(loaderFunc LoaderFunc) *CacheBuilder {
cb.loaderExpireFunc = func(k interface{}) (interface{}, *time.Duration, error) {
v, err := loaderFunc(k)
return v, nil, err
}
return cb
}
- 提供统一的加载方法，使用singleflight，执行c.loaderExpireFunc(key)。
此处提供了cb的封装函数，可以针对获取的value做不同的处理；比如直接返回用户，或者加入缓存。
// load a new value using by specified key.
func (c *baseCache) load(key interface{}, cb func(interface{}, *time.Duration, error) (interface{}, error), isWait bool) (interface{}, bool, error) {
v, called, err := c.loadGroup.Do(key, func() (v interface{}, e error) {
defer func() {
if r := recover(); r != nil {
e = fmt.Errorf("Loader panics: %v", r)
}
}()
return cb(c.loaderExpireFunc(key))
}, isWait)
if err != nil {
return nil, called, err
}
return v, called, nil
}
- LRU的loder
func (c *LRUCache) getWithLoader(key interface{}, isWait bool) (interface{}, error) {
if c.loaderExpireFunc == nil {
return nil, KeyNotFoundError
}
value, _, err := c.load(key, func(v interface{}, expiration *time.Duration, e error) (interface{}, error) {
if e != nil {
return nil, e
}
c.mu.Lock()
defer c.mu.Unlock()
item, err := c.set(key, v)
if err != nil {
return nil, err
}
if expiration != nil {
t := c.clock.Now().Add(*expiration)
item.(*lruItem).expiration = &t
}
return v, nil
}, isWait)
if err != nil {
return nil, err
}
return value, nil
}
二、LFU
LFU是基于访问次数来淘汰元素，所以需要额外维护访问次数的顺序。
-
可以基于map+堆，但是堆的操作开销是o(logn)的，开销过大；
- 需要一种O(1)时间的LFU算法，论文：http://dhruvbird.com/lfu.pdf；
挂在次数为1的元素可以用链表实现，gcache使用的map简单；
用链表可以基于过期时间再排序，就是需要额外的开销了。
// Discards the least frequently used items first.
type LFUCache struct {
baseCache
items map[interface{}]*lfuItem
freqList *list.List // list for freqEntry
}
type lfuItem struct {
clock Clock
key interface{}
value interface{}
freqElement *list.Element
expiration *time.Time
}
//每个访问次数单元，维护多个次数相同的lfuItem
type freqEntry struct {
freq uint
items map[*lfuItem]struct{}
}
SET
// Set a new key-value pair with an expiration time
func (c *LFUCache) 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.(*lfuItem).expiration = &t
return nil
}
func (c *LFUCache) set(key, value interface{}) (interface{}, error) {
var err error
// Check for existing item
item, ok := c.items[key]
if ok {
item.value = value
} else {
// Verify size not exceeded
if len(c.items) >= c.size {
c.evict(1)
}
item = &lfuItem{
clock: c.clock,
key: key,
value: value,
freqElement: nil,
}
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
}
淘汰
淘汰的过程中，只是遍历随机淘汰，并不是按照过期时间；
// evict removes the least frequence item from the cache.
func (c *LFUCache) evict(count int) {
entry := c.freqList.Front()
for i := 0; i < count; {
if entry == nil {
return
} else {
for item, _ := range entry.Value.(*freqEntry).items {
if i >= count {
return
}
c.removeItem(item)
i++
}
entry = entry.Next()
}
}
}
GET
过期删除；
命中缓存，更新频次；
// 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.
func (c *LFUCache) Get(key interface{}) (interface{}, error) {
v, err := c.get(key, false)
if err == KeyNotFoundError {
return c.getWithLoader(key, true)
}
return v, err
}
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
}
频次更新
func (c *LFUCache) increment(item *lfuItem) {
currentFreqElement := item.freqElement //当前lfuItem对应的链表节点
currentFreqEntry := currentFreqElement.Value.(*freqEntry)//当前链表节点的freqEntry
nextFreq := currentFreqEntry.freq + 1 //计算频次
delete(currentFreqEntry.items, item) //当前freqEntry删除这个lfuItem
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{}{}//下一个freqEntry记录lfuItem
item.freqElement = nextFreqElement //lfuItem绑定到新的链表节点
}
DELETE
// Remove removes the provided key from the cache.
func (c *LFUCache) Remove(key interface{}) bool {
c.mu.Lock()
defer c.mu.Unlock()
return c.remove(key)
}
func (c *LFUCache) remove(key interface{}) bool {
if item, ok := c.items[key]; ok {
c.removeItem(item)
return true
}
return false
}
// removeElement is used to remove a given list element from the cache
func (c *LFUCache) removeItem(item *lfuItem) {
delete(c.items, item.key) //删除map的关系
delete(item.freqElement.Value.(*freqEntry).items, item) //删除freq的关系
if c.evictedFunc != nil {
c.evictedFunc(item.key, item.value)
}
}
Loader
LFU的loader跟LRU相同，加载数据，存入缓存。
func (c *LFUCache) getWithLoader(key interface{}, isWait bool) (interface{}, error) {
if c.loaderExpireFunc == nil {
return nil, KeyNotFoundError
}
value, _, err := c.load(key, func(v interface{}, expiration *time.Duration, e error) (interface{}, error) {
if e != nil {
return nil, e
}
c.mu.Lock()
defer c.mu.Unlock()
item, err := c.set(key, v)
if err != nil {
return nil, err
}
if expiration != nil {
t := c.clock.Now().Add(*expiration)
item.(*lfuItem).expiration = &t
}
return v, nil
}, isWait)
if err != nil {
return nil, err
}
return value, nil
}
有疑问加站长微信联系（非本文作者）
