1.1.1. 19.LRU-淘汰算法

简介

当 Redis 超出内存限制时,内存数据会开始与磁盘发生频繁交换(swap)。交换行为会让 Redis 的性能急剧下降,这样的龟速可以说 Redis 不可用。

可以通过配置参数 「maxmemory」 来控制 Redis 内存超出的期望大小。

当实际内存超过 maxmemory 时,Redis 提供了 6 种策略(maxmemory-policy)来让用户决定该如何腾出空间以提供持续写服务:

  1. noeviction(默认):不会继续提供写服务,DEL 和读请求可以继续进行。保证数据不丢失,但是会让线上业务无法继续进行。
  2. volatile-lru:尝试淘汰设置了过期时间的 key,最少使用的 key 优先被淘汰。没有设置过期时间的 key 不会被淘汰,这样可以保证持久化的数据不会突然丢失。
  3. volatile-ttl:跟上面一样,除了淘汰策略不是 LRU,而是 key 的剩余寿命 tll,ttl 越小越先被淘汰。
  4. volatile-random:跟上面一样,不过淘汰的 key 是过期 key 集合中随机选出的。
  5. allkeys-lru:区别于 volatile-lru,这个淘汰策略针对所有 key 而不止过期的 key,这意味着持久化的 key 也会被淘汰。
  6. allkeys-random:跟上面一样,不过淘汰策略是随机的全体 key。

volatile-xxx 策略只针对带有过期时间的 key。 allkeys-xxx 策略针对的是所有 key。

所以,如果 Redis 是做缓存,那么应该使用 allkeys;如果还想做持久化那么必须采用 volatile-xxx 策略。

在 Redis 4.0 之后新增了两个算法:

  1. volatile-lfu:跟上面一样,不过淘汰的是,使用频率最小的有过期时间的 key。
  2. allkeys-lfu:跟上线一样,不过 key 是全体 key。

LRU(Least Recently Used) 算法

LRU 算法淘汰过程

实现 LRU 算法:

  1. key/value 字典外,和一个链表。
  2. 链表中的元素按照一定的顺序进行排列。
  3. 当空间满的时候,会踢掉链表尾部的元素。
  4. 当字典中的某个元素被访问时,将此元素的位置移动到表头。
  5. 位于链表尾部的元素就是访问频率较少的元素,会被踢掉。表头的元素是访问频繁的元素,所以不会被踢。

所以链表的顺序就是最近被访问的时间顺序。

近似 LRU 算法

Redis 采用的事一种近似的 LRU 算法。LRU 算法由于需要消耗大量额外内存,还需要对现有的数据结构进行较大改造,所以不使用。

近似的 LRU 算法很简单,在现有的数据结构基础上使用随机采样法来淘汰元素,就能达到与 LRU 算法近似的效果。

Redis 为实现近似 LRU 算法,它给每个 key 增加一个额外的小字段,这个字段长度 24 bit,也就是最后一次被访问的时间戳。

LRU 只进行懒惰处理。当 Redis 执行写操作时,发现内存超出了 maxmemory,就会执行一次 LRU 淘汰算法。随机取出 5(可以配置) 个 key,然后淘汰掉最旧的 key,如果淘汰后的内存还是超出 maxmemory,则继续执行,直到内存低于 maxmemory。

如何采样就看 maxmemory-policy 的配置(前面说的 6 种)。

随机 LRU 算法和严格 LRU 算法效果对比图

图中绿色的事新加入的 key,深灰色是老 key,浅灰色是被淘汰的 key。

可以看出,采样数量越大,近似 LRU 算法的效果越接近严格 LRU 算法。同时 Redis 3.0 在算法中增加了淘汰池,进一步提升了近似 LRU 算法的效果。

淘汰池也是一个数组,它的大小是 maxmemory-samples,在每一次淘汰循环中,新随机出来的 key 列表会和淘汰池中的 key 列表进行融合,淘汰掉最旧的一个 key 之后,剩余的较旧的 key 列表放入淘汰池中等待下一个循环使用。

PHP 版实现 LRU 算法

自己写的 php 版的实现方式,很简洁

<?php
<?php

namespace App\Services;

use Auth;

class LruService
{
    public $_capacity;
    public $_maxLen;

    public function __construct($maxLen = 5)
    {
        $this->_maxLen = $maxLen;
        $this->_capacity = [];
    }

    public function set($key)
    {
//        如果容器中有当前 key,则删除,并添加到容器头部
        if (in_array($key, $this->_capacity)) {
            $this->get($key);
        } elseif (count($this->_capacity) < $this->_maxLen) {
//        如果容器长度小于最大长度,则直接添加
            $this->add($key);
        } else {
//        否则,删除末尾元素,并将新元素放入头部
            array_shift($this->_capacity);
            $this->add($key);
        }
        return $this->_capacity;
    }

    public function get($key)
    {
        if (in_array($key, $this->_capacity)) {
            unset($this->_capacity[$key]);
            $this->add($key);
        }
        return $key;
    }

    public function add($key)
    {
        $this->_capacity[$key] = $key;
    }
}

使用

<?php
    public function demo()
    {
        $server = new LruService(5);
        dump($server->set(1));
        dump($server->set(2));
        dump($server->set(3));
        dump($server->set(4));
        dump($server->get(1));
        dump($server->_capacity);
        dump($server->set(5));
        exit;
    }

结果:

array:1 [1 => 1
]
array:2 [1 => 1
  2 => 2
]
array:3 [1 => 1
  2 => 2
  3 => 3
]
array:4 [1 => 1
  2 => 2
  3 => 3
  4 => 4
]
1
array:4 [2 => 2
  3 => 3
  4 => 4
  1 => 1
]
array:5 [2 => 2
  3 => 3
  4 => 4
  1 => 1
  5 => 5
]

在 github 上看到一个更好实现方式:https://github.com/rogeriopvl/php-lrucache

PHP 版实现 LFU 算法

<?php

namespace App\Services;

use Auth;

class LruService
{
    public $_capacity;
    public $_maxLen;

    public function __construct($maxLen = 5)
    {
        $this->_maxLen = $maxLen;
        $this->_capacity = [];
    }

    public function set($key)
    {
//        如果容器中有当前 key,则删除,并添加到容器头部
        if (in_array($key, $this->_capacity)) {
            $this->get($key);
        } elseif (count($this->_capacity) < $this->_maxLen) {
//        如果容器长度小于最大长度,则直接添加
            $this->add($key);
        } else {
//        否则,删除末尾元素,并将新元素放入头部
            array_shift($this->_capacity);
            $this->add($key);
        }
        return $this->_capacity;
    }

    public function get($key)
    {
        if (in_array($key, $this->_capacity)) {
            unset($this->_capacity[$key]);
            $this->add($key);
        }
        return $key;
    }

    public function add($key)
    {
        $this->_capacity[$key] = $key;
    }
}
<?php
       $server = new LfuService(5);
        dump($server->set(1));
        dump($server->set(2));
        dump($server->set(3));
        dump($server->set(3));
        dump($server->set(4));
        dump($server->get(1));
        dump($server->get(1));
        dump($server->get(2));
        dump($server->get(2));
        dump($server->get(2));
        dump($server->get(3));
        dump($server->_capacity);
        dump($server->set(5));
        exit;

结果:

array:1 [1 => 1
]
array:2 [1 => 1
  2 => 1
]
array:3 [1 => 1
  2 => 1
  3 => 1
]
array:3 [1 => 1
  2 => 1
  3 => 2
]
array:4 [1 => 1
  2 => 1
  3 => 2
  4 => 1
]
1
1
2
2
2
3
array:4 [2 => 4
  1 => 3
  3 => 3
  4 => 1
]
array:5 [2 => 4
  1 => 3
  3 => 3
  4 => 1
  5 => 1
]
Copyright © Kagami丶 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-12-10 20:25:25

results matching ""

    No results matching ""