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

 

推荐这些文章:

Leetcode 460. LFU 缓存机制(困难)

460. LFU 缓存机制(困难)
题目:
get(key) 方法会去缓存中查询键 key,如果 key 存在,则返回 key 对应的 val,否则返回 -1。
put(key, value) 方法插入或修改缓存。如果 key 已存在,则将它对应的值改为 val;如果 key 不存在,则插入键值对 (key, val)。
当缓存达到容量 capacity 时,则应该在插入新的键值对之前,删除使用频次(后文用 freq&nbs...

Redis 缓存过期删除/淘汰策略分析

Redis 缓存过期删除/淘汰策略分析
Redis 缓存删除

Redis 键过期删除,定期删除(主动)和惰性删除(被动)
Redis 内存不足时,缓存淘汰策略

key 键过期删除
我们用 redis 作为缓存数据库,设置 k-v 数据的时候,可以给这条数据设置一个过期时间。比如,set 命令设置过期时间:
set testkey redisvalue EX 60

EX: 表示秒, EX 60 表示这个键值60秒后过期。
那好,现在就有一个问题了,redis 怎么检查数据缓存时间到期了?然后删除它。
想一想,检测到期数据一般有两种方法,

第一:主动检测
第二:被动检测

什么是主动?
...

集合源码分析06——HashMap源码分析

 
 
 

 

 
 
   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...

面试题 16.25. LRU 缓存

设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。
它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
示例:
LRUCache cache = n...

力扣HOT100解题记录p1

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 = ...

LRU算法的实现

缘由:看到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;

// ...

缓存淘汰策略 LRU

定义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(...

文章标题:redis缓存淘汰策略LRU和LFU对比与分析
文章链接:https://www.dianjilingqu.com/51322.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>