自知对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这里先过了，我们来看下一个问题吧。
网友评论