Redis 数据结构与内存管理策略（下）
标签： Redis Redis数据结构 Redis内存管理策略 Redis数据类型 Redis类型映射
Redis 数据类型特点与使用场景
String、List、Hash、Set、Zset
案例：沪江团购系统大促 hot-top 接口 cache 设计
Redis 内存数据结构与编码
OBJECT encoding key、DEBUG OBJECT key
简单动态字符串（simple dynamic string）
链表（linked list）
字典（dict）
跳表（skip list）
整数集合（int set）
压缩表（zip list）
Redis Object 类型与映射
Redis 内存管理策略
键 过期时间、生存时间
过期键删除策略
AOF 、RDB 处理过期键策略
Redis LRU 算法
Redis 持久化方式
RDB (Redis DataBase)
AOF (Append-only file)
字典（dict）dict 字典是基于 hash算法 来实现，是 Hash 数据类型的底层存储数据结构。我们来看下 redis 3.0.0 版本的 dict.h 头文件定义。
typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; int iterators; } dict; typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht; typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry;说到 hash table 有两个东西是我们经常会碰到的，首先就是 hash 碰撞 问题，redis dict 是采用链地址法来解决，dictEntry->next 就是指向下个冲突 key 的节点。
还有一个经常碰到的就是 rehash 的问题，提到 rehash 我们还是有点担心性能的。那么redis 实现是非常巧妙的，采用 惰性渐进式 rehash 算法 。
在 dict struct 里有一个 ht[2] 组数，还有一个 rehashidx 索引。redis 进行 rehash 的大致算法是这样的，首先会开辟一个新的 dictht 空间，放在 ht[2] 索引上，此时将 rehashidx 设置为0，表示开始进入 rehash 阶段，这个阶段可能会持续很长时间，rehashidx 表示 dictEntry 个数。
每次当有对某个 ht[1] 索引中的 key 进行访问时，获取、删除、更新，redis 都会将当前 dictEntry 索引中的所有 key rehash 到 ht[2] 字典中。一旦 rehashidx=-1 表示 rehash 结束。
跳表（skip list）skip list 是 zset 的底层数据结构，有着高性能的查找排序能力。
我们都知道一般用来实现带有排序的查找都是用 Tree 来实现，不管是各种变体的 B Tree 还是 B+ Tree，本质都是用来做顺序查找。
skip list 实现起来简单，性能也与 B Tree 相接近。
typedef struct zskiplistNode { robj *obj; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned int span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist;zskiplistNode->zskiplistLevel->span 这个值记录了当前节点距离下个节点的跨度。每一个节点会有最大不超过 zskiplist->level 节点个数，分别用来表示不同跨度与节点的距离。
每个节点会有多个 forward 向前指针，只有一个 backward 指针。每个节点会有对象 __*obj__ 和 score 分值，每个分值都会按照顺序排列。
整数集合（int set）int set 整数集合是 set 数据类型的底层实现数据结构，它的特点和使用场景很明显，只要我们使用的集合都是整数且在一定的范围之内都会使用整数集合编码。
SADD set:userid 100 200 300 (integer) 3 OBJECT encoding set:userid "intset"int set 使用一块连续的内存来存储集合数据，它是数组结构不是链表结构。
typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents[]; } intset;intset->encoding 用来确定 contents[] 是什么类型的整数编码，以下三种值之一。
#define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t))