动手写分布式缓存 - 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";notifications@github.com; Send time: Tuesday, Apr 21, 2020 11:38 AM To: "geektutu/geektutu-blog"geektutu-blog@noreply.github.com; Cc: "liow"649073762@qq.com; "Mention"mention@noreply.github.com; 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: "肚子上没肉耶";649073762@qq.com; Send time: Tuesday, Apr 21, 2020 11:43 AM To: "geektutu/geektutu-blog"reply@reply.github.com; "geektutu/geektutu-blog"geektutu-blog@noreply.github.com; Cc: "Mention"mention@noreply.github.com; Subject: Re: [geektutu/geektutu-blog] 动手写分布式缓存 - GeeCache第一天 LRU 缓存淘汰策略 | 极客兔兔 (#62)

明白了，interface类型转换是.(被转换类型)，谢谢兔兔 ------------------ Original ------------------ From: "Dai Jie";notifications@github.com; Send time: Tuesday, Apr 21, 2020 11:38 AM To: "geektutu/geektutu-blog"geektutu-blog@noreply.github.com; Cc: "liow"649073762@qq.com; "Mention"mention@noreply.github.com; 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]

lrutest.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)
}

[lambda7xx]

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

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

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

谢啦

[zhangzw001]

支持大佬

[tsaiyang]

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)是啥意思？

反序列化

[PenguinCats]

是否应该在 Add 的时候判断一下，value 的大小是否比 maxBytes 要大，这种情况下，不应该先插入，再删除别的吧？这样的话极端情况可能会清空整个缓存？这是否与预期相符呢？

[zagreos]

想请教一下 c.Add()的逻辑上是否有误，如果先加缓存，再删除的话，是不是在某个时刻实际占用空间已经比最大容量要大了。是否应该先RemoveOldest()，再插入？

[DamonGG]

没有明白为什么要约定 队首是 list.Back, 而队尾是list.Front。这种本末倒置的约定，是有什么特殊的含义么？

如果跟 list 的定义保持一致会有什么问题么？

望大佬解惑 🙊

[valiner]

c.nbytes 没有并发控制，有data race

[Stephen-swt]

@valiner c.nbytes 没有并发控制，有data race

cache.go里面增加的并发控制就是为了解决这个问题吧

[Stephen-swt]

@DamonGG 没有明白为什么要约定 队首是 list.Back, 而队尾是list.Front。这种本末倒置的约定，是有什么特殊的含义么？

如果跟 list 的定义保持一致会有什么问题么？

望大佬解惑 🙊

这应该是相对的概念，把最近访问的挪到Back，缓存超过时就移除Front；把最近访问的挪到front，就移除back的

[fy403]

新增一个lru-k实现，目前测试没问题：望各位大佬能给予一些指导/微笑 https://github.com/fy403/studyNotes/blob/master/otofys.io/gee-cache/geecache/lru/lru-k.go

1）数据第一次被访问，加入到访问历史记录表（简称记录表）；在记录表中对应的K单元中设置最后访问时间=now()，且设置访问次数为1；

2）如果数据访问次数没有达到K次，则访问次数+1。最后访问时间与当前时间间隔超过预设的值(如30秒)，访问次数清0并加1；

3）当数据访问计数超过(>=)K次后，则访问次数+1。将数据保存到LRU缓存队列中，缓存队列重新按照时间排序；

4）LRU缓存队列中数据被再次访问后，重新排序；

5）LRU缓存队列需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。

[fyyjyx-github]

geektutu您好，我有一个问题想请教下，就是不太理解为什么在计算当前所占用的内存时，其中双向链表中的Element元素所占用的内存是采用int64(kv.value.Len())来计算，Element在双向链表中不是一个大的结构体吗。

...

kv := ele.Value.(*entry)

// 为什么ele所占用的内存要将ele中的Value转化为entry后再使用Len（） c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())

...

[lijunyzzZ]

@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)是啥意思？ https://golang.org/ref/spec#Type_assertions

https://golang.org/ref/spec#Type_assertions

[liujing-siyang]

@fyyjyx-github geektutu您好，我有一个问题想请教下，就是不太理解为什么在计算当前所占用的内存时，其中双向链表中的Element元素所占用的内存是采用int64(kv.value.Len())来计算，Element在双向链表中不是一个大的结构体吗。

...

kv := ele.Value.(*entry)

// 为什么ele所占用的内存要将ele中的Value转化为entry后再使用Len（） c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())

...

注意第二个测试中cap := len(k1 + k2 + v1 + v2)；lru := New(int64(cap), nil)，也就是我们只关注list.Element中的Value，是约定好的

[liujing-siyang]

@Stephen-swt

@DamonGG 没有明白为什么要约定 队首是 list.Back, 而队尾是list.Front。这种本末倒置的约定，是有什么特殊的含义么？

如果跟 list 的定义保持一致会有什么问题么？

望大佬解惑 🙊

这应该是相对的概念，把最近访问的挪到Back，缓存超过时就移除Front；把最近访问的挪到front，就移除back的

可以看一下list源码，双向链表是一个环形列表，root是一个固定的虚拟头节点，next指向第一个节点，pre指向最后一个节点

[liujing-siyang]

Add函数中c.maxBytes == 0,就没有缓存能力了，那当Add一个元素后马上就要删除；如果加上c.maxBytes != 0这个条件，那么Add一个元素后就不会删除了。这个地方应该单独在处理？

[yinhuanyi]

测试用例好像写错了，是!ok才能打印key2的cache miss

func TestGet(t *testing.T) {
    // ...

    if _, ok := lru.Get("key2"); !ok {
        t.Fatalf("cache miss key2 failed")
    }
}

[demoManito]

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

1.17 已经支持了啊

[zachturing]

// 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是否会大于c.maxBytes c.nbytes += int64(value.Len()) - int64(kv.value.Len()) kv.value = value } else { ...) } .... }

[csxgogogo]

gsdg54sdg5s4d5gトオジビタからロピカなフアやャクヤなどがミドっぱくラバニラサ

[wjh791072385]

@zachturing // 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是否会大于c.maxBytes c.nbytes += int64(value.Len()) - int64(kv.value.Len()) kv.value = value } else { ...) } .... }

不用考虑，因为后面的for循环时会对是否超出maxBytes做出循环处理