LRU键值对缓存结构体（单机非并发）
最近最少使用，相对于仅考虑时间因素的 FIFO 和仅考虑访问频率的 LFU，LRU 算法可以认为是相对平衡的一种淘汰算法。LRU 认为，如果数据最近被访问过，那么将来被访问的概率也会更高。LRU 算法的实现非常简单，维护一个队列，如果某条记录被访问了，则移动到队尾，那么队首则是最近最少访问的数据，淘汰该条记录即可。
LRU 算法需要用链表管理所有的数据，会造成大量额外的空间消耗。除此之外，大量的节点被访问就会带来频繁的链表节点移动操作，从而降低了 Redis 性能。所以 Redis 对该算法做了简化，Rdedis LRU 算法并不是真正的 LRU，Redis 通过对少量的 key 采样，并淘汰采样的数据中最久没被访问过的 key。
Redis 为何使用近似 LRU 算法淘汰数据，而不是真实 LRU？_51CTO博客_redis有几种数据淘汰策略
字典(map)的意义
存储键值对映射关系，让键值对按key查找和插入新键值对的时间复杂度为O(1)（常数级）
双向链表(double linked list)的意义
移动某个被访问到的键值对到队尾和在队尾新增、删除一条记录的时间复杂度为O(1)
查找：通过字典确定双向链表的节点，然后将节点移动到队尾。当缓存被命中执行的逻辑。
删除：缓存淘汰的实际执行的逻辑。
新增/修改：当键存在，更新键值移到队尾（已有的缓存被更新）；当键不存在，在双向队列添加新纪录（缓存内不存在，从数据库访问，并写入缓存）。
获取长度：返回双向链表长度
广泛使用的分布式缓存系统的LRU缓存淘汰策略，如何处理单个元素的大小超过LRU的最大字节数容量的情况？
chatgpt
# gpt回答1
在 Redis 中，LRU（最近最少使用）是默认的缓存淘汰策略之一。当单个元素的大小超过 Redis 的最大容量时，Redis 采取的处理方式取决于具体的配置和版本。
在旧版本的 Redis（例如 Redis 2.x）中，当单个元素的大小超过 Redis 的最大容量时，Redis 会将该元素存储在磁盘上，而不是内存中。这被称为虚拟内存（Virtual Memory）功能。虚拟内存允许 Redis 将不常访问的数据存储在磁盘上，从而节省内存空间。但需要注意的是，虚拟内存功能会引入额外的磁盘访问延迟，可能影响性能。
然而，从 Redis 3.0 开始，虚拟内存功能已被弃用，并且在最新的 Redis 版本中（如 Redis 6.x）已经移除。这意味着当单个元素的大小超过 Redis 的最大容量时，Redis 不会自动处理该情况，而是返回一个错误。
为了处理超过最大容量的单个元素，可以采取以下一些解决方案：
1. 应用层处理：在应用层中，可以对超过最大容量的元素进行分片或压缩，以确保其大小不超过 Redis 的限制。这需要在应用程序中进行额外的逻辑处理。
2. 数据分割：将大于最大容量的元素拆分为多个较小的部分，并将它们存储为多个键。这样可以确保每个键的大小在 Redis 的限制范围内。在读取时，应用程序需要重新组合这些部分。
3. 使用其他缓存系统：如果单个元素的大小可能超过 Redis 的限制，可以考虑使用其他支持更大元素大小的缓存系统，如 Memcached。
# gpt回答2
需要注意的是，以上解决方案都需要在应用程序中进行额外的处理，并且可能会引入一些复杂性。因此，在设计应用程序时，应尽量避免超过 Redis 最大容量的单个元素。
在 GroupCache 和 Memcached 这两个分布式缓存系统中，处理单个元素大小超过最大容量的情况也会有一些不同的策略。
GroupCache：GroupCache 是一个由 Golang 实现的分布式缓存系统，它的设计目标是高性能和低延迟。当单个元素的大小超过 GroupCache 的最大容量时，GroupCache 不会自动处理该情况，而是返回一个错误。因此，类似于 Redis，应用程序需要在应用层处理超过最大容量的元素，例如分片存储或压缩元素。
Memcached：Memcached 是一个广泛使用的分布式内存缓存系统，它被设计为简单高效。当单个元素的大小超过 Memcached 的最大容量时，Memcached 会将该元素拆分成多个较小的部分，并将这些部分存储为多个键。在读取时，应用程序需要重新组合这些部分。这种方式称为值分片（Value Sharding），它允许存储和检索大于最大容量的元素。
需要注意的是，无论是 GroupCache 还是 Memcached，处理超过最大容量的单个元素都需要在应用程序中进行额外的处理。这可能需要在应用程序中实现分片、压缩或值分片的逻辑。因此，在设计应用程序时，仍然建议尽量避免超过缓存系统的最大容量限制。
5、缓存大Key
当访问缓存时，如果key对应的value过大，读写、加载很容易超时，容易引发网络拥堵。另外缓存的字段较多时，每个字段的变更都会引发缓存数据的变更，频繁的读写，导致慢查询。如果大key过期被缓存淘汰失效，预热数据要花费较多的时间，也会导致慢查询。
所以我们在设计缓存的时候，要注意缓存的粒度，既不能过大，如果过大很容易导致网络拥堵；也不能过小，如果太小，查询频率会很高，每次请求都要查询多次。
解决方案：
方案一：设置一个阈值，当value的长度超过阈值时，对内容启动压缩，降低kv的大小。
方案二：评估大key所占的比例，由于很多框架采用池化技术，如：Memcache，可以预先分配大对象空间。真正业务请求时，直接拿来即用。
方案三：颗粒划分，将大key拆分为多个小key，独立维护，成本会降低不少
方案四：大key要设置合理的过期时间，尽量不淘汰那些大key。
redis之bigkey（看这一篇就够） - MrSatan - 博客园 (cnblogs.com)
在设计上直接为双向链表节点的Value大小设一个限制可能是一个比较方便的选择，这可以让系统做出让系统元素进一步分割或者拒绝写入缓存的依据。
具体到我写的这段LRU缓存结构体上，过大的元素会实际地插入双线链表，最后又因maxBytes的检查而弹出该元素，这导致链表插入的时间和为链表节点分配的内存空间被浪费。如果为entry.Value的值添加限制，并在修改缓存中已有键值对或者新增键值对前进行检查，因该情形产生的资源浪费应该能够被避免。
但考虑到参考项目后续可能有相关情况的处理可能与我自己处理产生矛盾，故保留TODO，后续扩展。