ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【golang】分布式缓存 - lru算法实现 [打印本页]

---

作者: 九天猎人    时间: 2022-9-16 17:12
标题: 【golang】分布式缓存 - lru算法实现
前言
　　最近复习操作系统，看到了lru算法，就去网上搜索下，因此发现了GeeCache，顺手写了一遍。研究下lru算法的实现。
正文:
　　lru使用map+链表实现。map里面存储了key以及其对应的链表节点。当我们根据某个key访问缓存值的时候，可以经过map快速定位到该链表节点。从而获取值
下面我们来看下它的具体实现:
首先，我们可以考虑下lru的结构：
　　1.map
　　2.链表
　　3.占用的内存大小
　　4.最大内存

1. type Cache struct {
2.         maxBytes  int64
3.         nbytes    int64
4.         ll     *list.List
5.         cache  map[string]*list.Element
6. }

复制代码

添加key:
lru算法的思想是经常访问的元素移动到队头,不常访问的元素移动到队尾。从而进行淘汰队尾元素。
当我们添加的key已经存在的时候，我们只需要更新其对应的值即可。
不存在的时候，需要插入链表和map
如果内存已经不够，我们需要开启淘汰算法

1. func (c *Cache) Add(key string,value Value)  {
2.         if v,ok := c.cache[key]; ok{
3.         //         移动到常用元素 --> 队头
4.                 c.ll.MoveToFront(v)
5.         //   获取旧值
6.                 kv := v.Value.(*entry)
7.                 c.nbytes += int64(value.Len()) - int64(kv.value.Len())
8.         // 更新值
9.                 kv.value = value
10.         }else{
11.                 ele := c.ll.PushFront(&entry{key,value})
12.                 c.cache[key] = ele
13.                 c.nbytes += int64(len(key)) + int64(value.Len())
14.         }
15.         if c.maxBytes != 0 || c.maxBytes < c.nbytes{
16. 　　　　//  淘汰算法
17.                 c.RemoveOldest()
18.         }
19. }

复制代码

　　下面我们来看淘汰算法:
　　　　在链表中移除队尾的元素，删除map中相应的key

1. func (c *Cache) RemoveOldest()  {
2.     ele := c.ll.Back()
3.     if ele != nil {
4.         c.ll.Remove(ele)
5.         kv := ele.Value.(*entry)
6.         delete(c.cache,kv.key)
7.         c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())
8.     }
9. }

复制代码

根据key获取缓存中元素就简单了，根据map定位到链表元素即可:

1. func (c *Cache) Get(key string)(value Value,ok bool)  {
2.         if ele,ok := c.cache[key];ok {
3.                 c.ll.PushFront(ele)
4.                 kv := ele.Value.(entry)
5.                 return kv.value,true
6.         }
7.         return
8. }

复制代码

　　
lru算法在GeeCache中的实现还是挺好理解的。记录下~
 

| 不骄不躁，保持学习

1. <br><br>

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4