Redis中Expiry处理的底层实现机制研究（redis过期底层实现）

Redis是一个开源的，支持网络，基于内存的数据存储系统，非常适合做缓存来使用。Redis存储的数据维护有一定的时间，这就涉及到Expiry处理，即舍弃指定时间后失效的数据。

#### Expiry实现机制

Redis使用两个二叉树来完成Expiry操作：一个是键值对结构的字典（dict），用来存放数据；另一个是定时器红黑树（ttl RB-tree），用来记录缓存时间信息。字典中的每个成员都会同时关联节点红黑树中的一个节点，这个节点中有个时间属性表示缓存的失效时间。

每次Redis在数据库中增加一个键值对时，都会在ttl RB-tree中增加相应的节点，并设置失效时间。随后，Redis会每秒扫描一次ttl RB-tree，将失效的节点从字典和ttl RB-tree移除。

Redis中的Expiry还使用了懒惰删除的方法，即在每次查询时，先检查这个节点是否失效，失效则移除，而不需要每次查询都去移除失效值。

#### Expiry原理图示

下面是Redis中Expiry实现操作的原理示意图：


图中表示，当一个新数据键值对被添加进字典（dict）中时，会同时在ttl RB-tree中增加一个节点，并设置节点的失效时间；随后，Redis会每秒扫描ttl RB-tree，将失效的节点从字典和ttl RB-tree中移除。

#### 代码实现

下面是Redis中Expiry实现代码：

dict *d = server.db[id].dict;
rb_tree *t = &server.db[id].expires;

/* 添加一个新节点 */
dictEntry *de = entry;
/* 新建ttl节点插入到红黑树t中 */
t->key = dict->key;
t->val = dict->val;
/* 设置节点失效时间 */
t->expire = expire;

/* 添加到绑定字典 */
dict linked list;
/* 扫描红黑树，移除失效的节点 */
rb_tree *scan = rb_search_gt(t, expire);
if (scan) {
    /* 移除待移除节点 */
    dict_delete(d, scan->key);
    /* 移除红黑树节点 */
    rb_delete_node(t, scan);
    /* 移除绑定字典元素 */
    dict_unlink(linked_list, scan);
}

从上面的实现可以看出，Redis中Expiry处理的数据结构和操作比较复杂，但是机制是非常好的，无论是从性能上还是安全性上都得到很好的保障。