Redis学习-lru和redis实现

lru实现

数组实现

用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。

链表实现

利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

hashmap + 链表

整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点， 其中 head 代表双向链表的表头，tail 代表尾部。首先预先设置 LRU 的容量，如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 O(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。

Redis的LRU实现

redis服务器实际使用的是惰性删除和定期删除两种策略：通过配合使用这两种删除策略，服务器可很好的使用CPU的时间和避免浪费内存空间之间取得平衡。

如果按照HashMap和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以Redis采用了一个近似的做法，就是随机取出若干个key，然后按照访问时间排序后，淘汰掉最不经常使用的.

redis中有很多数据类型（以后会出一个redis系列），为了实现key-value新老判断，不能像上面算法题中简单的链表就能实现.

Redis采用了一个全局时钟在redisServer这个struct中的lruclock，这个时钟供每个object更新自己object的时间。其中存储了服务器自启动之后的lru时钟，该时钟是全局的lru时钟。

默认的LRU时钟的分辨率是1秒，可以通过改变REDIS_LRU_CLOCK_RESOLUTION宏的值来改变，Redis会在serverCron()中调用updateLRUClock定期的更新LRU时钟，更新的频率和hz参数有关，默认为100ms一次。

Redis最为一款优秀的内存数据库，用途非常广泛，其缓存代码设计和实现很值得学习，实现步骤主要有：

用一个全局时钟作为参照 对每个object初始化和操作的时候都更新它各自的lru时钟 随机挑选几个key，根据lru时钟计算idle的时间排序放入EvictionPool中，最终挑选idle时间最长的free，以释放空间。至于为什么随机和只选择5个，是为了性能考虑，如果做到全局一个一个排序就非常消耗CPU，而实际应用中没必要这么精确。

redis lru配置

Redis配置中和LRU有关的有三个：

maxmemory: 配置Redis存储数据时指定限制的内存大小，比如100m。当缓存消耗的内存超过这个数值时, 将触发数据淘汰。该数据配置为0时，表示缓存的数据量没有限制, 即LRU功能不生效。64位的系统默认值为0，32位的系统默认内存限制为3GB maxmemory_policy: 触发数据淘汰后的淘汰策略 maxmemory_samples: 随机采样的精度，也就是随即取出key的数目。该数值配置越大, 越接近于真实的LRU算法，但是数值越大，相应消耗也变高，对性能有一定影响，样本值默认为5。