动手写分布式缓存 - GeeCache第一天 LRU 缓存淘汰策略 | 极客兔兔

[geektutu]

https://geektutu.com/post/geecache-day1.html

7天用 Go语言/golang 从零实现分布式缓存 GeeCache 教程(7 days implement golang distributed cache from scratch tutorial)，动手写分布式缓存，参照 groupcache 的实现。本文介绍常用的三种缓存淘汰(失效)算法：先进先出(FIFO)，最少使用(LFU) 和 最近最少使用(LRU)，并实现 LRU 算法和相应的测试代码。

[Zealot666]

大佬nb！！！

[PualrDwade]

add方法的代码是否有bug?，如果是更新，为什么不重新计算nbytes？方法上面一步就已经return了

[geektutu]

@PualrDwade 感谢指出，后续没有更新场景，只有新增和淘汰，所以就忘记测试这个场景了。代码已经更新，并添加相应的测试用例防护了。

[liyu4]

我提一个问题， lru当然是比较权衡的方案，但是比如周期性或者突发的查询会造成缓存的命中了下降，或者说缓存污染吧， 其实还应该介绍下lru-k的方案，lru可以认为是lru-1， 那么lru-k就可以结合lfu的一些优点了。

[geektutu]

@liyu4 好建议，有时间尽快补上。

[xuyang404]

add方法最后的那段for是不是应该改为if才对？

[geektutu]

add方法最后的那段for是不是应该改为if才对？

for 是没问题的，可能会 remove 多次，添加一条大的键值对，可能需要淘汰掉多个键值对，直到 nbytes < maxBytes。

[xiaoxfan]

@geektutu

add方法最后的那段for是不是应该改为if才对？

for 是没问题的，可能会 remove 多次，添加一条大的键值对，可能需要淘汰掉多个键值对，直到 nbytes < maxBytes。

更新之后也可能需要淘汰，不能直接return

// Add adds a value to the cache.
func (c *Cache) Add(key string, value Value) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.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())
	}
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOldest()
	}
}

[geektutu]

@xiaoxfan 感谢指出问题，更新完也是需要淘汰的，你的修改是正确的。

[OwenLiGithub]

func (c *Cache) Get(key string) (value Value, ok bool) { if ele, ok := c.cache[key]; ok { c.ll.MoveToFront(ele) kv := ele.Value.(*entry) return kv.value, true } return } 不太明白kv := ele.Value.(*entry)这个段代码，ele是链表节点的指针，*ele就是节点了，这样ele.Value.(*entry)是啥意思？

[geektutu]

@noendfoli list 存储的是任意类型，使用时需要类型转换，建议先学习下 Go语言类型转换的基础语法。

[OwenLiGithub]

明白了，interface类型转换是.(被转换类型)，谢谢兔兔 ------------------ Original ------------------ From: "Dai Jie";[email protected]; Send time: Tuesday, Apr 21, 2020 11:38 AM To: "geektutu/geektutu-blog"[email protected]; Cc: "liow"[email protected]; "Mention"[email protected]; Subject: Re: [geektutu/geektutu-blog] 动手写分布式缓存 - GeeCache第一天 LRU 缓存淘汰策略 | 极客兔兔 (#62)

@noendfoli list 存储的是任意类型，使用时需要类型转换，建议先学习下 Go语言类型转换的基础语法。

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[OwenLiGithub]

兔兔，在测试怎么找不到New 方法，后面都可以调用这些方法了。。。。为什么跑的时候还会undefined

------------------ Original ------------------ From: "肚子上没肉耶";[email protected]; Send time: Tuesday, Apr 21, 2020 11:43 AM To: "geektutu/geektutu-blog"[email protected]; "geektutu/geektutu-blog"[email protected]; Cc: "Mention"[email protected]; Subject: Re: [geektutu/geektutu-blog] 动手写分布式缓存 - GeeCache第一天 LRU 缓存淘汰策略 | 极客兔兔 (#62)

明白了，interface类型转换是.(被转换类型)，谢谢兔兔 ------------------ Original ------------------ From: "Dai Jie";[email protected]; Send time: Tuesday, Apr 21, 2020 11:38 AM To: "geektutu/geektutu-blog"[email protected]; Cc: "liow"[email protected]; "Mention"[email protected]; Subject: Re: [geektutu/geektutu-blog] 动手写分布式缓存 - GeeCache第一天 LRU 缓存淘汰策略 | 极客兔兔 (#62)

@noendfoli list 存储的是任意类型，使用时需要类型转换，建议先学习下 Go语言类型转换的基础语法。

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[CaoGongHui]

有没有学习的小伙伴解释一下修改的方法中，更新已使用内容
c.nbytes += int64(value.Len()) - int64(kv.value.Len()) 中，要减去value的长度的，是因为更新的时候，这个节点原来的值没有了，所以内存空间就减少了，但是后面不是又给他加上了一个value了吗，这样统计已使用内存，不会少一块吗？
请问是我哪里理解错了呢？

[ghosx]

如果某条记录被访问了，则移动到队尾,代码中的队首队尾搞反了吧

func (c *Cache) Get(key string) (value Value, ok bool) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

[geektutu]

@ghosx 细心~ 队尾队首是个相对的概念，具体以实现为准吧。

[ghost]

@CaoGongHui 有没有学习的小伙伴解释一下修改的方法中，更新已使用内容
c.nbytes += int64(value.Len()) - int64(kv.value.Len()) 中，要减去value的长度的，是因为更新的时候，这个节点原来的值没有了，所以内存空间就减少了，但是后面不是又给他加上了一个value了吗，这样统计已使用内存，不会少一块吗？
请问是我哪里理解错了呢？

老的值被更新，但是没有从nbytes里面减去，只是被新的value覆盖了。所以只要加上差值即可。

[CaoGongHui]

@njcongtou 谢谢解惑~，感觉有点懂了，我再理解理解😄

[betnevs]

lru_test.go中TestGet函数里面 if _, ok := lru.Get("key2"); ok ，其中应该是“!ok"吧，这样没有key2才会走到t.Error("cache miss key2 failed")

[liuzehao]

@OwenLiGithub func (c *Cache) Get(key string) (value Value, ok bool) { if ele, ok := c.cache[key]; ok { c.ll.MoveToFront(ele) kv := ele.Value.(*entry) return kv.value, true } return } 不太明白kv := ele.Value.(*entry)这个段代码，ele是链表节点的指针，*ele就是节点了，这样ele.Value.(*entry)是啥意思？ 你看一下ele的类型，也就是Element这个结构体的源码，value字段存的值是interface{}类型的，意味着你需要自定义节点值的类型。作者把这个字段定义为了entry，所以他是想要把Element中的值取出来才用(*entry)转换了一下

[SalamanderJY]

膜代总

[laizhenxing]

新增或修改的时候，maxBytes=0 的时候，现在是可以添加的。测试用例设置了 maxBytes=0, 这个用例是可以通过的，还是有节点生成

[geektutu]

@laizhenxing maxBytes 设置为0，代表不对内存大小设限，这里和 groupcache 是一致的。所以不为0时，才会判断是否超过了限制。

for c.maxBytes != 0 && c.maxBytes < c.nbytes {
	c.RemoveOldest()
}

[laizhenxing]

@geektutu soga,好的，明白了

[zouguangjie]

菜鸟 value Value 报错了 Unresolved type 'Value' 什么情况？

[geektutu]

@zouguangjie

Value 是自定义的一个数据结构，定义在 lru.go#76 中。你的代码里是不是少写了这几行？

// Value use Len to count how many bytes it takes
type Value interface {
	Len() int
}

[UnbearableFate]

Go语言不存在在List声明之处就定义元素类型的说法嘛，类似于C++的std::list这样，感觉每次取value都要类型断言有一点不优雅

[geektutu]

@UnbearableFate 因为 Go 没有泛型的机制，所以只能用 interface{} 来代替任意的类型，官方的说法是最早在 1.17 支持，不过我对这个时间点比较悲观，可能得等到 2.0 版本了。

[lambda7xx]

get操作后，是不是要将key的指针移到最前面？？

[geektutu]

get操作后，是不是要将key的指针移到最前面？？

@lambda7xx ，Get 方法中，已经这么实现了。

if ele, ok := c.cache[key]; ok {
	c.ll.MoveToFront(ele)
}