美文网首页
Golang Gcache中的LRU和LFU

Golang Gcache中的LRU和LFU

作者: 梦工厂 | 来源:发表于2020-10-31 22:47 被阅读0次

    源码：https://github.com/bluele/gcache

    一、LRU
    SET
    GET
    DELETE
    Loader
二、LFU
    SET
    GET
    DELETE
    Loader
    1. 多种淘汰策略，LRU、LFU、simple；
    2. 提供loder，singleflight方式；
    3. 时间窗口的概念是通过整个cache表的过期时间来实现的；
    4. 过期删除，访问时才被删除；
    5. 过期和淘汰策略是分开的：访问过期会删除，添加元素会淘汰（淘汰时不看过期时间）；
    6. 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
    1. 用户提供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
}
    1. 提供统一的加载方法，使用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
}
    1. 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是基于访问次数来淘汰元素，所以需要额外维护访问次数的顺序。

    1. 可以基于map+堆，但是堆的操作开销是o(logn)的，开销过大；


    2. 需要一种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
}

    相关文章

      网友评论

          本文标题：Golang Gcache中的LRU和LFU

          本文链接：https://www.haomeiwen.com/subject/iiuevktx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|Golang Gcache中的LRU和LFU|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！