How to set up LRU algorithm in redis

1. Set Redis to use the LRU algorithm

LRU (Least Recently Used) least recently used algorithm is one of many replacement algorithms. A sort of.
There is a maxmemory concept in Redis, mainly to limit the memory used to a fixed size. The LRU algorithm used by Redis is an approximate LRU algorithm.

(1) Set maxmemory

As mentioned above, maxmemory is to limit the maximum memory usage of Redis. There are several ways to set its size. One method is to set it through CONFIG SET, as follows:

127.0.0.1:6379> CONFIG GET maxmemory
1) "maxmemory"
2) "0"
127.0.0.1:6379> CONFIG SET maxmemory 100MB
OK
127.0.0.1:6379> CONFIG GET maxmemory
1) "maxmemory"
2) "104857600"

The other method is to modify the configuration file redis.conf:

maxmemory 100mb

Note that under 64bit systems, maxmemory is set to 0 Indicates that Redis memory usage is not limited. Under 32bit systems, maxmemory implicitly cannot exceed 3GB.
When Redis memory usage reaches the specified limit, you need to choose a replacement strategy.

(2) Replacement policy

When Redis memory usage reaches maxmemory, you need to select the set maxmemory-policy to replace the old data.
The following are the replacement strategies that can be selected:

• noeviction: No replacement, which means that even if the memory reaches the upper limit, no replacement will be performed. All commands that can cause memory increase will return error

• allkeys-lru: Prioritize deleting the keys that are least frequently used recently to save new data

• volatile-lru: Only set the Select the least frequently used key among the expired keys to delete to save new data

• allkeys-random: Randomly select some keys from all-keys. Delete to save new data

• volatile-random: Only select some keys from the expired set keys to delete to save new data

• volatile-ttl: Only select the key with the shortest survival time (TTL) from the expired set key to delete it to save new data

It should be noted that:

(1) The method of setting maxmemory-policy is similar to the method of setting maxmemory, which can be modified dynamically through redis.conf or CONFIG SET.

(2) If there is no matching key that can be deleted, then the volatile-lru, volatile-random and volatile-ttl strategies are the same as the noeviction replacement strategy - no keys will be replaced.

(3) It is very important to choose the appropriate replacement strategy, which mainly depends on the access mode of your application. Of course, you can also dynamically modify the replacement strategy and output it by using the Redis command - INFO The cache hit rate can then be used to tune the replacement strategy.

Generally speaking, there are some common experiences:

• If all keys are most frequently used recently, then you need to select allkeys-lru to replace the most recent ones. The least frequently used key. If you are not sure which strategy to use, it is recommended to use allkeys-lru.

• If the access probabilities of all keys are similar, you can use the allkeys-random strategy to replace the data.

• If you have enough understanding of the data and can specify a hint for the key (specified through expire/ttl), you can choose volatile-ttl for replacement.

volatile-lru and volatile-random are often used when one Redis instance is used for both caching and persistence. However, it is better to use two Redis instances to solve the problem. this problem.

Setting the expiration time expire will occupy some memory, but with allkeys-lru there is no need to set the expiration time, thus making more effective use of memory.

(3) How the replacement strategy works

It is very important to understand how the replacement strategy is executed, such as:

1. The client executes a new command, causing the database to need to add data (such as set key value)

2. Redis will check the memory usage. If the memory usage exceeds maxmemory, it will be deleted according to the replacement strategy. Some keys

3. The new command is successfully executed

Our continuous writing of data will cause the memory to reach or exceed the upper limit maxmemory, but the replacement strategy will Memory usage drops below the upper limit.

If a lot of memory needs to be used at one time (such as writing a large set at once), then the memory usage of Redis may exceed the maximum memory limit for a period of time.

(4) Approximate LRU algorithm

LRU in Redis is not a strict LRU algorithm implementation, but an approximate LRU implementation, mainly to save memory occupy and improve performance. Redis has such a configuration - maxmemory-samples. Redis's LRU is to take out the configured number of keys, and then select the least frequently used key among them for replacement. The default is 5, as follows:

maxmemory-samples 5

Yes Gain advantages in speed or accuracy of the LRU replacement algorithm by adjusting the number of samples.

The reason why Redis does not use the real LRU implementation is to save memory usage. Although not a true LRU implementation, they are almost equivalent in application. The following figure is a comparison between the approximate LRU implementation of Redis and the theoretical LRU implementation:

测试开始首先在Redis中导入一定数目的key，然后从第一个key依次访问到最后一个key，因此根据LRU算法第一个被访问的key应该最新被置换，之后再增加50%数目的key，导致50%的老的key被替换出去。 

在上图中你可以看到三种类型的点，组成三种不同的区域：

1. 淡灰色的是被置换出去的key

2. 灰色的是没有被置换出去的key

3. 绿色的是新增加的key

理论LRU实现就像我们期待的那样，最旧的50%数目的key被置换出去，Redis的LRU将一定比例的旧key置换出去。

可以看到在样本数为5的情况下，Redis3.0要比Redis2.8做的好很多，Redis2.8中有很多应该被置换出去的数据没有置换出去。在样本数为10的情况下，Redis3.0很接近真正的LRU实现。

LRU是一个预测未来我们会访问哪些数据的模型，如果我们访问数据的形式接近我们预想——幂律，那么近似LRU算法实现将能处理的很好。

在模拟测试中我们可以发现，在幂律访问模式下，理论LRU和Redis近似LRU的差距很小或者就不存在差距。

如果你将maxmemory-samples设置为10，那么Redis将会增加额外的CPU开销以保证接近真正的LRU性能，可以通过检查命中率来查看有什么不同。

通过CONFIG SET maxmemory-samples 动态调整样本数大小，做一些测试验证你的猜想。

2、LRU的实现

<?php
/**
 * LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面
 */
class LRU_Cache
{

    private $array_lru = array();
    private $max_size = 0;

    function __construct($size)
    {
        // 缓存最大存储
        $this->max_size = $size;
    }

    public function set_value($key, $value)
    {
        // 如果存在，则向队尾移动，先删除，后追加
        // array_key_exists() 函数检查某个数组中是否存在指定的键名，如果键名存在则返回true，如果键名不存在则返回false。
        if (array_key_exists($key, $this->array_lru)) {
            // unset() 销毁指定的变量。
            unset($this->array_lru[$key]);
        }
        // 长度检查，超长则删除首元素
        if (count($this->array_lru) > $this->max_size) {
            // array_shift() 函数删除数组中第一个元素，并返回被删除元素的值。
            array_shift($this->array_lru);
        }
        // 队尾追加元素
        $this->array_lru[$key] = $value;
    }

    public function get_value($key)
    {
        $ret_value = false;

        if (array_key_exists($key, $this->array_lru)) {
            $ret_value = $this->array_lru[$key];
            // 移动到队尾
            unset($this->array_lru[$key]);
            $this->array_lru[$key] = $ret_value;
        }

        return $ret_value;
    }

    public function vardump_cache()
    {
        echo "<br>";
        var_dump($this->array_lru);
    }
}

$cache = new LRU_Cache(5);                          // 指定了最大空间 6
$cache->set_value("01", "01");
$cache->set_value("02", "02");
$cache->set_value("03", "03");
$cache->set_value("04", "04");
$cache->set_value("05", "05");
$cache->vardump_cache();
echo "<br>";

$cache->set_value("06", "06");
$cache->vardump_cache();
echo "<br>";

$cache->set_value("03", "03");
$cache->vardump_cache();
echo "<br>";

$cache->set_value("07", "07");
$cache->vardump_cache();
echo "<br>";

$cache->set_value("01", "01");
$cache->vardump_cache();
echo "<br>";

$cache->get_value("04");
$cache->vardump_cache();
echo "<br>";

$cache->get_value("05");
$cache->vardump_cache();
echo "<br>";

$cache->get_value("10");
$cache->vardump_cache();
echo "<br>";

更多redis知识请关注redis入门教程栏目。

The above is the detailed content of How to set up LRU algorithm in redis. For more information, please follow other related articles on the PHP Chinese website!