Redis 是速度非常快的非关系型（NoSQL）内存键值数据库，可以存储键和五种不同类型的值之间的映射。

Redis的五种基本类型

String

Redis 是用 C 语言开发完成的，但在 Redis 字符串中，并没有使用 C 语言中的字符串，而是用一种称为 SDS（Simple Dynamic String）的结构体来保存字符串。

struct sdshdr {
    int len;
    int free;
    char buf[];
}

• len：用于记录 buf 中已使用空间的长度；
• free：buf 中空闲空间的长度；
• buf[]：存储实际内容。

优点：

• 常数时间内可以获得字符串的长度；
• 避免了缓冲区溢出；
• 减少字符串修改时带来的内存重新分配的次数；
  • 空间预分配。如果对 SDS 修改后，len 的长度小于 1M，那么程序将分配和 len 相同长度的未使用空间。
  • 惰性空间释放。当对 SDS 进行缩短操作时，程序并不会回收多余的内存空间，而是使用 free 字段将这些字节数量记录下来不释放，后面如果需要 append 操作，则直接使用 free 中未使用的空间，减少了内存的分配。
• 二进制安全。字符串结束不是'\0'，而是由SDS中的len来决定。

应用场景：缓存、计数器、分布式锁等。

List

Redis列表是简单的字符串列表，按照插入顺序排序。可以添加一个元素导列表的头部（左边）或者尾部（右边）。

在版本3.2之前，Redis 列表list使用两种数据结构作为底层实现。

• 压缩列表ziplist；
• 双向链表linkedlist；

因为双向链表占用的内存比压缩列表要多， 所以当创建新的列表键时， 列表会优先考虑使用压缩列表， 并且在有需要的时候， 才从压缩列表实现转换到双向链表实现。

压缩列表转化成双向链表条件：

创建新列表时 redis 默认使用 redis_encoding_ziplist 编码， 当以下任意一个条件被满足时， 列表会被转换成 redis_encoding_linkedlist 编码：

• 试图往列表新添加一个字符串值，且这个字符串的长度超过 server.list_max_ziplist_value （默认值为 64 ）。
• ziplist 包含的节点超过 server.list_max_ziplist_entries （默认值为 512 ）。

注意：这两个条件是可以修改的，在 redis.conf 中。

压缩列表ziplist：

• 一个特殊的双向链表。没有维护双向指针:prev next；而是存储上一个 entry的长度和 当前entry的长度，通过长度推算下一个元素在什么地方。
• 字段、值比较小，才会用ziplist；

ziplist使用一块连续的内存，每一个节点（entry）都是连续存储的，其包含了如下内容：

每一个存储节点（entry）都是一个zlentry (zip list entry)。ziplist每一个存储节点、都是一个 zlentry，就是上文所说的entry；

typedef struct zlentry {    // 压缩列表节点
    unsigned int prevrawlensize, prevrawlen;    // prevrawlen是前一个节点的长度，prevrawlensize是指prevrawlen的大小，有1字节和5字节两种
    unsigned int lensize, len;  // len为当前节点长度 lensize为编码len所需的字节大小
    unsigned int headersize;    // 当前节点的header大小
    unsigned char encoding; // 节点的编码方式
    unsigned char *p;   // 指向节点的指针
} zlentry;

void zipEntry(unsigned char *p, zlentry *e) {   // 根据节点指针返回一个enrty
    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);    // 获取prevlen的值和长度
    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);  // 获取当前节点的编码方式、长度等
    e->headersize = e->prevrawlensize + e->lensize; // 头大小
    e->p = p;
}

ziplist的主要优点是节省内存，但它上面的查找操作只能按顺序查找（可以是从前往后、也可以从后往前）ziplist将数据按照一定规则编码在一块连续的内存区域，目的是节省内存，这种结构并不擅长做修改操作。一旦数据发生改动，就会引发内存realloc，可能导致内存拷贝。

双向链表linkedlist

当链表entry数据超过512、或单个value 长度超过64，底层就会转化成linkedlist编码；

linkedlist是标准的双向链表，Node节点包含prev和next指针，可以进行双向遍历；还保存了 head 和 tail 两个指针，因此，对链表的表头和表尾进行插入的复杂度都为 (1) —— 这是高效实现 LPUSH 、 RPOP、 RPOPLPUSH 等命令的关键。

这两种存储方式的优缺点

• 双向链表linkedlist便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
• ziplist存储在一段连续的内存上，所以存储效率很高。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝。

版本3.2之后，重新引入 quicklist，列表的底层都由quicklist实现。

quickList

可以认为quickList，是ziplist和linkedlist二者的结合；quickList将二者的优点结合起来。quickList是一个ziplist组成的双向链表，每个节点使用ziplist来保存数据。

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

typedef struct quicklist {
    quicklistNode *head; //头结点
    quicklistNode *tail; //尾节点
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes *///负数代表级别，正数代表个数
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off *///压缩级别
} quicklist;

• quickList就是一个标准的双向链表的配置，有head 有tail；
• 每一个节点是一个quicklistNode，包含prev和next指针；
• 每一个quicklistNode 包含 一个ziplist，*zp 压缩链表里存储键值；

所以quicklist是对ziplist进行一次封装，使用小块的ziplist来既保证了少使用内存，也保证了性能。

应用场景：链表、队列、微博关注人时间轴列表等。

Set

Set 就是一个集合,集合的概念就是一堆不重复值的组合。利用 Redis 提供的 Set 数据结构,可以存储一些集合性的数据。

Set的底层存储结构底层使用了intset和hashtable两种数据结构，intset可以理解为数组，hashtable就是普通的哈希表（key为set的值，value为null）。使用intset存储必须满足下面两个条件，否则使用hashtable，条件如下：

• 集合对象保存的所有元素都是整数值；
• 集合对象保存的元素数量不超过512个。

intset数据结构

intset内部其实是一个数组（int8_t coentents[]数组），而且存储数据的时候是有序的，因为在查找数据的时候是通过二分查找来实现的。

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

应用场景：去重、赞、踩、共同好友等。

Hash

Redis hash 是一个string类型的field和value的映射表，hash特别适合用于存储对象。

Redis的哈希对象的底层存储可以使用ziplist（压缩列表）和hashtable。当hash对象可以同时满足一下两个条件时，哈希对象使用ziplist编码。

• 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
• 哈希对象保存的键值对数量小于512个。

Redis的hash架构就是标准的hashtab的结构，通过挂链解决冲突问题。

应用场景：用户信息、Hash 表等。

Zset

Redis 有序集合和集合一样也是string类型元素的集合，且不允许重复的成员。

不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。zset底层的存储结构包括ziplist或skiplist，在同时满足以下两个条件的时候使用ziplist，其他时候使用skiplist，两个条件如下：

• 有序集合保存的所有元素的长度小于64字节；
• 有序集合保存的元素数量小于128个。

当skiplist作为zset的底层存储结构的时候，使用skiplist按序保存元素及分值，使用dict来保存元素和分值的映射关系。

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;

前进指针：用于从表头向表尾方向遍历；

后退指针：用于从表尾向表头方向回退一个节点，和前进指针不同的是，前进指针可以一次性跳跃多个节点，后退指针每次只能后退到上一个节点。

跨度：表示当前节点和下一个节点的距离，跨度越大，两个节点中间相隔的元素越多。

应用场景：访问量排行榜、点击量排行榜等。

编码转化

Redis 使用对象（redisObject）来表示数据库中的键值，当我们在 Redis 中创建一个键值对时，至少创建两个对象，一个对象是用做键值对的键对象，另一个是键值对的值对象。

typedef struct redisObject{
    //类型
   unsigned type:4;
   //编码
   unsigned encoding:4;
   //指向底层数据结构的指针
   void *ptr;
    //...
 }robj;

其中 type 字段记录了对象的类型，包含字符串对象、列表对象、哈希对象、集合对象、有序集合对象。

过期数据删除

三种删除策略：

• 定时删除。在这是键的过期时间的同时，创建一个定时器 Timer，让定时器在键过期时间来临时立即执行对过期键的删除；
• 惰性删除。键过期后不管，每次读取该键时，判断该键是否过期，如果过期删除该键返回空；
• 定期删除。每隔一段时间对数据库中的过期键进行一次检查。

总之

Redis性能如此高的原因，有如下几点：

• 纯内存操作；
• 单线程；
• 高效的数据结构；
• 合理的数据结构编码。