类似思路的一个库

[phuslu]

作者你好，我前段时间也处于相同的初衷的编写了一个 lru 库。

1. 实现尽量简单 2. 内存和GC负担尽量小 3. 使用分片而不是 RCU 加速(因为会有 GC 负担)

https://github.com/phuslu/lru

随机的混合写的速度是明显快于其他库的，不过 zipf 分布应该不如 RCU 的实现 (otter 等）

[lxzan]

memorycache最初非常简单，后面搞了些骚操作

在公司项目里拿它当时间堆用

[lxzan]

你的Benchmark怎么没放并发混合读写

[phuslu]

是指一定比列的set和get么，代码就是就是啊，展开readme的代码段可以看到

[lxzan]

是指一定比列的set和get么，代码就是就是啊，展开readme的代码段可以看到

readme里面没看到

[lxzan]

作者你好，我前段时间也处于相同的初衷的编写了一个 lru 库。

1. 实现尽量简单 2. 内存和GC负担尽量小 3. 使用分片而不是 RCU 加速(因为会有 GC 负担)

https://github.com/phuslu/lru

随机的混合写的速度是明显快于其他库的，不过 zipf 分布应该不如 RCU 的实现 (otter 等）

明天学习下

[phuslu]

是指一定比列的set和get么，代码就是就是啊，展开readme的代码段可以看到

readme里面没看到

我用github markdown收缩了一下代码，点这个三角就可以展开

也是用 github action 跑的这个测试。https://github.com/phuslu/lru/blob/master/.github/workflows/benchmark.yml

[lxzan]

被函数名字误导了，后缀都是Get

otter怎么那么慢，我测试它快得惊人

[lxzan]

可能我的测试写得不太好，你这个更加随机乱序

[lxzan]

读写比例是多少

[phuslu]

readme 上也提到是 read:write 是 9:1，对于真实缓存情况也许写比例稍微高了点。可以通过代码里面的 writeradio 参数调节

[phuslu]

在我这个随机混合读写测试中，各个库的性能表现没有太大的差异，我认为这更符合现实世界: 没有魔法

不过对于 zipf 分布，以 otter 为代表的 RCU 的实现的确可以获得明显优势，但是也是以 GC 压力为代价的。

而我这个库一个初衷就是以 fastcache/bigcache 为目标，在GC压力/内存占用尽量小的情况下，实现泛型接口让cache变得更易用而不是只能用 []byte 做 key/value

[lxzan]

mc也是有gc优化的，如果kv是值类型就是零gc

[lxzan]

你的lru没有用堆或时间轮维护ttl，所以快一些

自己实现了map？优秀

[phuslu]

因为初始化时候就创建了固定大小的 list 和 hashtable。只要保证 LRU 策略正确就可以了，主动去删除ttl的项，我认为对于定长的lru没啥意义。

速度方面我认为主要是紧凑的数据结构达到的，比如map大小和KV无关，本质只是一个 []uint64。

而且也是因为定长的关系，map 直接初始化的list大小*1.25就可以了，不需要考虑 resize 情况。

[phuslu]

如果背后启动一个goroutine使用随机的驱逐策略也是可以做到的，我觉得并不会性能造成明显影响。只是我不喜欢这个实现，实在要做的话，我也预期做成一个选项，比如 WithBackgroudEviction(true) 什么的。

之前为了精确测量每个cache库的内存占用，我曾经试用这个库 https://github.com/DmitriyVTitov/size 但是很多库背后都有一个或多个goroutine在做类似工作，导致这个库调用 size.Of 时候都会panic。

所以才会变成现在的用 readme 里面的内存测量方法。

[lxzan]

如果有堆的话，能做的事情更多一些。我现在用mc做指数时间递增重试和超时取消订单。操作堆增加了几十ns是非常划算的, 功能丰富了许多.

我以前也自己造过map, 扩容方面不知道怎么优雅的处理, 后面就直接用runtime.map了. 链表这里我们想到一块了, 用数组下标模拟指针. https://github.com/lxzan/memorycache/blob/main/deque.go

[lxzan]

自己造map还有个好处是避免重复计算哈希

[phuslu]

用堆的好处可以让cache变成延时队列，功能的确丰富很多。不过我的场景是“泛型fastcache”，所以功能要求不多，而在内存压力和速度上期望尽可能快。

自己实现map好处我还是觉得不需要存 key 和value，只需要存hash值和index就可以，这样速度和内存都同时得到改善。

[lxzan]

自己实现map好处我还是觉得不需要存 key 和value，只需要存hash值和index就可以，这样速度和内存都同时得到改善。

mc 的 map 也是如此, 用的 map<uint64, uint32> , 多了哈希冲突的副作用

思路确实很像, mc 比起 phuslu/lru 就多了个四叉堆

[phuslu]

嗯是的，除了hash碰撞，uint64 开销其实也有点大，我后来转成了uint32 类型的hash值，大概快了5~10ns

[lxzan]

嗯是的，除了hash碰撞，uint64 开销其实也有点大，我后来转成了uint32 类型的hash值，大概快了5~10ns

uint32 碰撞概率太高了，所以我用了 uint64。你是自制的map，本来就需要处理冲突，所以可以用 uint32.

[phuslu]

类似思路还有 freelru 这个库，比较巧合是几乎是同一时期各自实现的。

[phuslu]

还有一点我发现几乎所有泛型cache库都忽略的一点，泛型函数因为不能自动内联（inline)导致调用成本都挺高。比如我刚刚又作这样的手动内联优化，在混合读写测试中速度又提高了3~5ns

https://github.com/phuslu/lru/commit/20d7b5cf03839f232086b62c18157b342c8b9039

也可以查看我这个cache的其他函数，都是尽量减少函数调用一点点挤出的ns级的性能。

具体原因可以参见 https://www.infoq.cn/article/xprmcl5qbf6yvdroajyn

[lxzan]

以前跑压测的时候发现过泛型性能比非泛型稍差，不过没有深入研究。

go的抽象是有开销的，我已经放弃了和c++比性能。

[phuslu]

我一直认为 go 的优化应该是 fasthttp 作者那种思路，尽量减少内存使用和 GC 压力。本身的优化因为 comipler/runtime 的限制并不能有什么黑魔法(我自己的测试结果显示这些库的读写差异并不大)。

比如 Ristretto(也包含了 Theine/Otter) 这种用 RCU 手法来换 zipf 下的读写性能有点不值当(比如 Ristretto 社区有抱怨内存飙升并的issue，并且Otter作者一直回避或者声称GC压力不要紧)，比较适合数据库缓存场景。在完全随机混合读写的场景下表现都较差。

刚刚我又改了改测试代码，让测试的key做了一个 sha1 让其更加“随机化”，这样测试出来结果所有库都有下降，但是 RTO 的下降更多。

[lxzan]

我对无锁结构不熟，只能用分段锁优化了。

如果想让一个库受欢迎，易用性可能比性能更重要，需要在性能和易用性功能性方面做平衡。

有点想把map<uint64, uint32>改为map<string, uint32>了，即使概率极低，依然如梗在喉 😂

[lxzan]

作为库的开发者，很多时候我们是自己和自己卷，和竞品卷，卷着卷着性能就到天花板了。

[phuslu]

otter 作者到 https://github.com/phuslu/lru/issues 发帖挑战我这个库了。

总体看下来有点吹毛求疵的意思，我小心的回复了一下，其他问题我准备琢磨好再回他。

[lxzan]

有些地方他说的也挺有道理，以前otter没火的时候也在mc下面发过issue🤣

我也用github action跑压测，结果蛮稳定的。

[phuslu]

和 otter 作者沟通基本完毕，按照他的意见修改了测试代码并且补上了 zipf 分布的测试。

在 zipf 分布下，otter 的性能的确要好些。

[lxzan]

安慰下自己, 虽然otter性能好, 但mc在功能方面胜过它. 实际业务中需要极限性能再考虑别的 :)

[phuslu]

差距没有我预期的那么大（zipf测试下phuslu/lru和otter性能最接近），并且otter作者验证了我的库的命中率和rto们差不多。考虑我的实现的内存和gc方面的优势，我还是继续用自己的。

[lxzan]

各个 LRU 库命中率都一样, 同一种驱逐算法

[lxzan]

mc也是零gc设计，但是kv经常会有指针结构(string, slice...)，真正要达到零gc，会增加使用成本，浪费内存。