【golang】分布式缓存-lru算法实现

前言

最近去博客园写文章了，好久没有更新博客了，搬运下~

正文

最近复习操作系统，看到了lru算法，就去网上搜索下，因此发现了GeeCache，顺手写了一遍。研究下lru算法的实现。

lru使用map+链表实现。map里面存储了key以及其对应的链表节点。当我们根据某个key访问缓存值的时候，可以经过map快速定位到该链表节点。从而获取值

首先，我们可以考虑下lru的结构：

1.map

2.链表

3.占用的内存大小

4.最大内存

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

添加key:

lru算法的思想是经常访问的元素移动到队头,不常访问的元素移动到队尾。从而进行淘汰队尾元素。

当我们添加的key已经存在的时候，我们只需要更新其对应的值即可。

不存在的时候，需要插入链表和map

如果内存已经不够，我们需要开启淘汰算法

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

下面我们来看淘汰算法:

在链表中移除队尾的元素，删除map中相应的key

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

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

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

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

| 不骄不躁，保持学习