Redis的expire的缓存过期策略是如何实现的？

自知对Redis的知识了解的还算不错，但当面试官问到expire是怎么实现的时候我突然懵了，虽然最后凭借了猜测也猜出了定期+惰性删除，但总感觉这块之前复习遗漏了，现在来重新梳理一下。

面试官：你知道expire设置过期时间的工作原理是什么吗？到期的数据是怎么过期的呢？

我：emmm...我觉得是采用了定期删除，每隔一段时间去扫描检测key对应的缓存是否过期，如果过期了就删除。

面试官：那如果key刚好在你两次扫描之间过期了呢？如果key特别多全量扫描不是很耗费性能吗？

我：嗯这样的话采用全量定期删除确认不够好，可以把全量改为随机抽取一部分进行检测，检测不到的那些数据可以在get的时候再检测是否过期，如果过期就删除数据并返回空。

过期策略通常有三种：

定时过期：每个设置过期时间的key都需要创建一个定时器，到过期时间就会立即清除。该策略可以立即清除过期的数据，对内存很友好；但是会占用大量的CPU资源去处理过期的数据，从而影响缓存的响应时间和吞吐量。
惰性过期：只有当访问一个key时，才会判断该key是否已过期，过期则清除。该策略可以最大化地节省CPU资源，却对内存非常不友好。极端情况可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存。(memcache只使用惰性删除 )
定期过期：每隔一定的时间（100ms），会扫描一定数量的数据库的expires字典中一定数量的key，并清除其中已过期的key。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得CPU和内存资源达到最优的平衡效果。
(expires字典会保存所有设置了过期时间的key的过期时间数据，其中，key是指向键空间中的某个键的指针，value是该键的毫秒精度的UNIX时间戳表示的过期时间。键空间是指该Redis集群中保存的所有键。)
Redis中同时使用了惰性过期和定期过期两种过期策略

面试官：嗯，没错。确实是这样的。那如果有些数据既没有被抽取到又没有被get的话怎么办，这样不就一直留在内存中了吗？

我：如果数据没有被检测删除导致数据堆积的话，最后应该还有Redis内存淘汰机制的，比如说最常见的LRU。

Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时，怎么处理需要新写入且需要申请额外空间的数据。主要有报错处理，时间维度移除和空间维度移除。

noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。
allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。
allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。
volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。
volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。
volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。

面试官：嗯那你能手写个LRU算法吗？

我：。。。好吧

LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

C++版本

   class LRUCache {
    public:
    LRUCache(int capacity) {
        cap=capacity;
    } 
    int get(int key) {
        if(hashtable.count(key)==0) return -1;
        else//更新到表头
        {
            auto iter = hashtable[key];
            cache.splice(cache.begin(),cache,iter);//移动到链表头
            return cache.begin()->second;
        }
    }
    
    void put(int key, int value) {
        if(hashtable.count(key)==0) {
            if(cache.size()==cap)   {
                hashtable.erase(cache.back().first);
                cache.pop_back();
            }
            cache.push_front(make_pair(key,value));
            hashtable[key]=cache.begin(); 
        }
        else {
            auto iter = hashtable[key];
            iter->second=value;
            cache.splice(cache.begin(),cache,iter);
            hashtable[key]=cache.begin();
        }
    }
    unordered_map<int,list<pair<int,int>>::iterator> hashtable;
    list<pair<int,int>> cache;
    int cap=0;
    };```

PHP版本

    //PHP
    class LRUCache 
    {
    protected $capacity;
    protected $hash;
    protected $used;
    
    public function __construct($capacity) 
    {
        $this->capacity = $capacity;
        $this->hash = [];
        $this->used = [];
    }
    public function get($key) 
    {
        if (isset($this->hash[$key])) {
            $index = array_search($key, $this->used);
            unset($this->used[$index]);
            $this->used[] = $key;
            return $this->hash[$key];
        }
        return -1;
    }
    public function put($key, $value) 
    {
        if (isset($this->hash[$key])) {
            $index = array_search($key, $this->used);
            unset($this->used[$index]);
            $this->hash[$key] = $value;
            $this->used[] = $key;
        } else {
            if (count($this->hash) == $this->capacity) {
                $k = array_shift($this->used);
                unset($this->hash[$k]);
            }

            $this->used[] = $key;
            $this->hash[$key] = $value;
        }
    }
    }```


面试官：Redis这里先过了，我们来看下一个问题吧。