redis缓存淘汰策略LRU和LFU对比与分析
一、Redis占用内存大小
我们知道Redis是基于内存的key-value数据库,因为系统的内存大小有限,所以我们在使用Redis的时候可以配置Redis能使用的最大的内存大小。
1、通过配置文件配置
通过在Redis安装目录下面的redis.conf配置文件中添加以下配置设置内存大小
//设置Redis最大占用内存大小为100M
maxmemory 100mb
2、通过命令修改
Redis支持运行时通过命令动态修改内存大小
//设置Redis最大占用内存大小为100M
127.0.0.1:6379> config set maxmemory 100mb
//获取设置的Redis能使用的最大内存大小
127.0.0.1:6379> config get maxmemory
如果不设置最大内存大小或者设置最大内存大小为0,在64位操作系统下不限制内存大小,在32位操作系统下最多使用3GB内存
二、Redis的内存淘汰
既然可以设置Redis最大占用内存大小,那么配置的内存就有用完的时候。那在内存用完的时候,还继续往Redis里面添加数据不就没内存可用了吗?
实际上Redis定义了几种策略用来处理这种情况:
noeviction(默认策略):对于写请求不再提供服务,直接返回错误(DEL请求和部分特殊请求除外) allkeys-lru:从所有key中使用LRU算法进行淘汰 volatile-lru:从设置了过期时间的key中使用LRU算法进行淘汰 allkeys-random:从所有key中随机淘汰数据 volatile-random:从设置了过期时间的key中随机淘汰 volatile-ttl:在设置了过期时间的key中,根据key的过期时间进行淘汰,越早过期的越优先被淘汰
当使用volatile-lru、volatile-random、volatile-ttl这三种策略时,如果没有key可以被淘汰,则和noeviction一样返回错误
三、如何获取及设置内存淘汰策略
获取当前内存淘汰策略:
127.0.0.1:6379> config get maxmemory-policy
通过配置文件设置淘汰策略(修改redis.conf文件):
maxmemory-policy allkeys-lru
通过命令修改淘汰策略:
127.0.0.1:6379> config set maxmemory-policy allkeys-lru
四、LRU算法
什么是LRU?
上面说到了Redis可使用最大内存使用完了,是可以使用LRU算法进行内存淘汰的,那么什么是LRU算法呢?
LRU(Least Recently Used),即最近最少使用,是一种缓存置换算法。在使用内存作为缓存的时候,缓存的大小一般是固定的。当缓存被占满,这个时候继续往缓存里面添加数据,就需要淘汰一部分老的数据,释放内存空间用来存储新的数据。这个时候就可以使用LRU算法了。其核心思想是:如果一个数据在最近一段时间没有被用到,那么将来被使用到的可能性也很小,所以就可以被淘汰掉。
其原理是维护一个双向链表,key -> node,其中node保存链表前后节点关系及数据data。新插入的key时,放在头部,并检查是否超出总容量,如果超出则删除最后的key;访问key时,无论是查找还是更新,将该Key被调整到头部。
使用php实现一个简单的LRU算法
代码地址:
https://github.com/rogeriopvl/php-lrucache
<?php namespace LRUCache; /** * Class that implements the concept of an LRU Cache * using an associative array as a naive hashmap, and a doubly linked list * to control the access and insertion order. * * @author Rogério Vicente * @license MIT (see the LICENSE file for details) */ class LRUCache { // object Node representing the head of the list private $head; // object Node representing the tail of the list private $tail; // int the max number of elements the cache supports private $capacity; // Array representing a naive hashmap (TODO needs to pass the key through a hash function) private $hashmap; /** * @param int $capacity the max number of elements the cache allows */ public function __construct($capacity) { $this->capacity = $capacity; $this->hashmap = array(); $this->head = new Node(null, null); $this->tail = new Node(null, null); $this->head->setNext($this->tail); $this->tail->setPrevious($this->head); } /** * Get an element with the given key * @param string $key the key of the element to be retrieved * @return mixed the content of the element to be retrieved */ public function get($key) { if (!isset($this->hashmap[$key])) { return null; } $node = $this->hashmap[$key]; if (count($this->hashmap) == 1) { return $node->getData(); } // refresh the access $this->detach($node); $this->attach($this->head, $node); return $node->getData(); } /** * Inserts a new element into the cache * @param string $key the key of the new element * @param string $data the content of the new element * @return boolean true on success, false if cache has zero capacity */ public function put($key, $data) { if ($this->capacity <= 0) { return false; } if (isset($this->hashmap[$key]) && !empty($this->hashmap[$key])) { $node = $this->hashmap[$key]; // update data $this->detach($node); $this->attach($this->head, $node); $node->setData($data); } else { $node = new Node($key, $data); $this->hashmap[$key] = $node; $this->attach($this->head, $node); // check if cache is full if (count($this->hashmap) > $this->capacity) { // we're full, remove the tail $nodeToRemove = $this->tail->getPrevious(); $this->detach($nodeToRemove); unset($this->hashmap[$nodeToRemove->getKey()]); } } return true; } /** * Removes a key from the cache * @param string $key key to remove * @return bool true if removed, false if not found */ public function remove($key) { if (!isset($this->hashmap[$key])) { return false; } $nodeToRemove = $this->hashmap[$key]; $this->detach($nodeToRemove); unset($this->hashmap[$nodeToRemove->getKey()]); return true; } /** * Adds a node to the head of the list * @param Node $head the node object that represents the head of the list * @param Node $node the node to move to the head of the list */ private function attach($head, $node) { $node->setPrevious($head); $node->setNext($head->getNext()); $node->getNext()->setPrevious($node); $node->getPrevious()->setNext($node); } /** * Removes a node from the list * @param Node $node the node to remove from the list */ private function detach($node) { $node->getPrevious()->setNext($node->getNext()); $node->getNext()->setPrevious($node->getPrevious()); } } /** * Class that represents a node in a doubly linked list */ class Node { /** * the key of the node, this might seem reduntant, * but without this duplication, we don't have a fast way * to retrieve the key of a node when we wan't to remove it * from the hashmap. */ private $key; // the content of the node private $data; // the next node private $next; // the previous node private $previous; /** * @param string $key the key of the node * @param string $data the content of the node */ public function __construct($key, $data) { $this->key = $key; $this->data = $data; } /** * Sets a new value for the node data * @param string the new content of the node */ public function setData($data) { $this->data = $data; } /** * Sets a node as the next node * @param Node $next the next node */ public function setNext($next) { $this->next = $next; } /** * Sets a node as the previous node * @param Node $previous the previous node */ public function setPrevious($previous) { $this->previous = $previous; } /** * Returns the node key * @return string the key of the node */ public function getKey() { return $this->key; } /** * Returns the node data * @return mixed the content of the node */ public function getData() { return $this->data; } /** * Returns the next node * @return Node the next node of the node */ public function getNext() { return $this->next; } /** * Returns the previous node * @return Node the previous node of the node */ public function getPrevious() { return $this->previous; } }
假如一次访问key 1,5,1,3,5,2,4,1,2
五、LRU在Redis中的实现
近似LRU算法
Redis使用的是近似LRU算法,它跟常规的LRU算法还不太一样。近似LRU算法通过随机采样法淘汰数据,每次随机出5(默认)个key,从里面淘汰掉最近最少使用的key。
可以通过maxmemory-samples参数修改采样数量: 例:maxmemory-samples 10 maxmenory-samples配置的越大,淘汰的结果越接近于严格的LRU算法
Redis为了实现近似LRU算法,给每个key增加了一个额外增加了一个24bit的字段,用来存储该key最后一次被访问的时间。
Redis3.0对近似LRU的优化
Redis3.0对近似LRU算法进行了一些优化。新算法会维护一个候选池(大小为16),池中的数据根据访问时间进行排序,第一次随机选取的key都会放入池中,随后每次随机选取的key只有在访问时间小于池中最小的时间才会放入池中,直到候选池被放满。当放满后,如果有新的key需要放入,则将池中最后访问时间最大(最近被访问)的移除。
当需要淘汰的时候,则直接从池中选取最近访问时间最小(最久没被访问)的key淘汰掉就行。
LRU算法的对比
我们可以通过一个实验对比各LRU算法的准确率,先往Redis里面添加一定数量的数据n,使Redis可用内存用完,再往Redis里面添加n/2的新数据,这个时候就需要淘汰掉一部分的数据,如果按照严格的LRU算法,应该淘汰掉的是最先加入的n/2的数据。
生成如下各LRU算法的对比图:
你可以看到图中有三种不同颜色的点:
浅灰色是被淘汰的数据 灰色是没有被淘汰掉的老数据 绿色是新加入的数据
我们能看到Redis3.0采样数是10的时候生成的图最接近于严格的LRU。而同样使用5个采样数,Redis3.0也要优于Redis2.8。
Redis并没有使用严格的LRU算法,因为维护一个那么大的双向链表需要的内存空间较大。
显然LRU的缺陷是明显的,最新访问的数据被当做热数据显然是不合理的,热数据顾名思义就是被访问频次叫高的数据,显然是不同的概念
六、LFU算法
LFU算法是Redis4.0里面新加的一种淘汰策略。它的全称是Least Frequently Used,它的核心思想是根据key的最近被访问的频率进行淘汰,很少被访问的优先被淘汰,被访问的多的则被留下来。
LFU算法能更好的表示一个key被访问的热度。假如你使用的是LRU算法,一个key很久没有被访问到,只刚刚是偶尔被访问了一次,那么它就被认为是热点数据,不会被淘汰,而有些key将来是很有可能被访问到的则被淘汰了。如果使用LFU算法则不会出现这种情况,因为使用一次并不会使一个key成为热点数据。LFU原理使用计数器来对key进行排序,每次key被访问的时候,计数器增大。计数器越大,可以约等于访问越频繁。具有相同引用计数的数据块则按照时间排序。
LFU一共有两种策略:
volatile-lfu:在设置了过期时间的key中使用LFU算法淘汰key allkeys-lfu:在所有的key中使用LFU算法淘汰数据
设置使用这两种淘汰策略跟前面讲的一样,不过要注意的一点是这两种策略只能在Redis4.0及以上设置,如果在Redis4.0以下设置会报错
新加入数据插入到队列尾部(因为引用计数为1);
队列中的数据被访问后,引用计数增加,队列重新排序;
当需要淘汰数据时,将已经排序的列表最后的数据块删除。
l 命中率
一般情况下,LFU效率要优于LRU,且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录,一旦数据访问模式改变,LFU需要更长时间来适用新的访问模式,即:LFU存在历史数据影响将来数据的“缓存污染”效用。
l 复杂度
需要维护一个队列记录所有数据的访问记录,每个数据都需要维护引用计数。
l 代价
需要记录所有数据的访问记录,内存消耗较高;需要基于引用计数排序,性能消耗较高。
LFC算法存在两个问题:
1、在LRU算法中可以维护一个双向链表,然后简单的把被访问的节点移至链表开头,但在LFU中是不可行的,节点要严格按照计数器进行排序,新增节点或者更新节点位置时,时间复杂度可能达到O(N)。
2、只是简单的增加计数器的方法并不完美。访问模式是会频繁变化的,一段时间内频繁访问的key一段时间之后可能会很少被访问到,只增加计数器并不能体现这种趋势。
第一个问题很好解决,可以借鉴LRU实现的经验,维护一个待淘汰key的pool。第二个问题的解决办法是,记录key最后一个被访问的时间,然后随着时间推移,降低计数器。
更多请参考:https://www.zhangshengrong.com/p/zD1yQg6b1r/
zz:https://blog.csdn.net/raoxiaoya/article/details/103141022
推荐这些文章:
460. LFU 缓存机制(困难)
题目:
get(key) 方法会去缓存中查询键 key,如果 key 存在,则返回 key 对应的 val,否则返回 -1。
put(key, value) 方法插入或修改缓存。如果 key 已存在,则将它对应的值改为 val;如果 key 不存在,则插入键值对 (key, val)。
当缓存达到容量 capacity 时,则应该在插入新的键值对之前,删除使用频次(后文用 freq&nbs...
Redis 缓存过期删除/淘汰策略分析
Redis 缓存删除
Redis 键过期删除,定期删除(主动)和惰性删除(被动)
Redis 内存不足时,缓存淘汰策略
key 键过期删除
我们用 redis 作为缓存数据库,设置 k-v 数据的时候,可以给这条数据设置一个过期时间。比如,set 命令设置过期时间:
set testkey redisvalue EX 60
EX: 表示秒, EX 60 表示这个键值60秒后过期。
那好,现在就有一个问题了,redis 怎么检查数据缓存时间到期了?然后删除它。
想一想,检测到期数据一般有两种方法,
第一:主动检测
第二:被动检测
什么是主动?
...
1.执行构造器语句,初始化加载因子,并且将table表等初始化为null
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
2.执行put方法,因为是基本数据类型所以先进行一个装箱操作
public V put(K key, V value) {
return putVal...
设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。
它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
示例:
LRUCache cache = n...
146. LRU 缓存
class LRUCache {
class Node {
Node prev;
Node next;
int key;
int value;
public Node(){}
public Node(int key, int value){
this.key = key;
this.value = value;
}
}
Map<Integer, Node> cache = ...
缘由:看到redis的缓存淘汰机制,便自己实现了一下
代码实现(双向链表+HashMap)
package com.jarjune.jdalao.framework.algorithm;
import java.util.*;
/**
* LRU
* @author jarjune
* @version 1.0.1
* @date 2020/11/19
*/
public class LRUCache<K, V> {
// 缓存Node
private Map<K, Node<K, V>> cache;
// ...
定义Node结点
注意这里的构造函数是要初始化的有参的构造函数。
class Node{
Node pre,next; //定义结点的前后结点
int key,val;
public Node(int key,int val){
this.key=key;
this.val=val;
}
}
手写双向链表
需要用到上面定义的 Node Class类,其实主要就是注意指针的边界条件。
还有在这三个函数:
void addFirst(Node n)
void remove(Node n)
Node removeLast(...
文章链接:https://www.dianjilingqu.com/51322.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。