前言:

Redis作为一款优秀的中间件，是目前市场上最好的开源内存 NoSQL 数据库之一，在缓存、计数和排名等实时分析、分布式锁、用户会话数据管理等等场景中大放异彩，相信很多开发者都听说过甚至频繁使用过，从使用层面上，与我们直接接触最多就是Redis的五种对象，分别是字符串、列表、集合、有序集合、哈希。这五种对象在Redis底层中实际上是使用六种数据结构实现的，分别是SDS(简单动态字符串)、链表、字典、跳跃表、整数集合、压缩列表，我们直接使用的对象至少都会使用到一种底层数据结构实现，在不同场景中会选择合适的底层数据结构实现。Redis作为内存数据库，对内存的使用极为敏感，一个对象由多种数据结构实现，可以优化不同场景的使用效率，使内存得到最大程度的利用，提高性能。下面主要是着重介绍六种底层数据结构，以及五种对象与底层数据结构的关联.

六种数据结构介绍

一、SDS(简单动态字符串)

说明:

Redis没有直接使用C语言字符串来表示，而是自己实现一种名为简单动态字符串(simple dynamic string, SDS)来表示，将其用作Redis的默认字符串表示

SDS结构定义

 struct sdshdr {
 //记录buf数组中已使用字节的数量
 //等于SDS所保存字符串的长度
 int len;
 //记录buf数组中未使用字节的数量
 int free;
 //字节数组， 用于保存字符串
 //最后一个字节则保存了空字符'\0',遵循C字符串以空字符结尾的惯例 
 //不计算在SDS的len属性里面 
 char buf[];
};

SDS图示说明

SDS的优点

1. 常数复杂度获取字符串长度。因为 C 字符串并不记录自身的长度信息， 所以为了获取一个 C 字符串的长度， 程序必须遍历整个字符串， 对遇到的每个字符进行计数， 直到遇到代表字符串结尾的空字符为止， 这个操作的复杂度为 O(N)
2. 杜绝缓冲区溢出。C字符串不记录字符串长度，有些不安全的API，比如char *strcat(char *dest, const char *src);，将一个src字符串拼接到dest后面可能会导致缓存区溢出。而SDS在执行拼接字符串操作时，会检查dest字符串的长度是否足够，如果不够，会先扩大长度，再进行拼接操作
3. 减少修改字符串时带来的内存重分配次数。C字符串，比如长度为N的字符串底层实现就是N+1长度的数组(末尾多了一个保存空字符的字符空间)，字符串长度和数组的长度有对应的相关关系，每次修改时候，都需要重新分配数组的空间，会导致频繁的内存重分配，效率低；SDS保存字符串的数组存在未使用的字节，SDS 实现了空间预分配(扩大数组时分配额外的空间)和惰性空间释放(缩小数组时不释放多余的空间)两种优化策略
4. 二进制安全。C 字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。而 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据， 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的，它被读取时就是什么样。
5. 兼容部分C字符串函数。虽然SDS有不少特性和C字符串不同，但是SDS一样遵循C字符串以空字符结尾的惯例，这样有些C字符串函数是可以兼容用的

二、链表

说明:

C语言是没有实现链表数据结构的，Redis自然要自己实现，Redis的链表结构没有很特殊的地方，可以从数据结构相关书籍查阅到相关定义。

链表结构定义:

typedef struct listNode {
 //前置节点
 struct listNode * prev;
 //后置节点
 struct listNode * next;
 //节点的值
void * value;
}listNode;

链表图示说明:

链表list结构定义:

typedef struct list {
  //表头节点
  listNode * head;
  //表尾节点
  listNode * tail;
  //链表所包含的节点数量
  unsigned long len;
  //节点值复制函数
  void *(*dup)(void *ptr);
  //节点值释放函数
  void (*free)(void *ptr);
  //节点值对比函数
  int (*match)(void *ptr,void *key);
} list;

list图示说明:

参数说明:
head:指向链表头部
tail:指向链表尾部
len:指链表的长度，图中有三个节点，len为3
函数说明:
dup:函数用于复制链表节点所保存的值
free:函数用于释放链表节点所保存的值
match:函数则用于对比链表节点所保存的值和另一个输入值是否相等

特点:双端(带有prev、next指针)、无环(表头表尾指针指向NULL)、带表头指针表尾指针、带链表长度计数器(len字段保存长度)、多态(链表节点使用 void* 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值)

应用总结:

链表被广泛用于实现Redis的各种功能，比如列表键(最基本、最常用)、发布与订阅、慢查询、监视器等

三、字典

说明:

字典在高级语言中是一种很普遍的数据结构，比如Java的map实现，它是一种保存key-value(键值对)的抽象数据结构，C语言是没有的，Redis构建了自己的字典实现。Redis字典所使用的哈希表由dict.h中的dictht定义

dictht结构定义:

 typedef struct dictht {
 //哈希表数组
 dictEntry **table;
 //哈希表大小
 unsigned long size;
//哈希表大小掩码， 用于计算索引值
//总是等于size-1
 unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
} dictht;

哈希表图示:

图中展示了一个大小为 4 的空哈希表（没有包含任何键值对）

哈希表节点定义:

typedef struct dictEntry {
     //键
     void *key;
     //值
     union {
      void *val;
      uint64_tu64;
      int64_ts64;
    } v;
 //指向下个哈希表节点， 形成链表
struct dictEntry *next;
} dictEntry;

既然是哈希表，那么就会存在哈希键冲突的场景，解决哈希冲突有好几种方法，这里是采用链地址法，next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接起来在一起。
哈希冲突例子

字典定义:

typedef struct dict {
 //类型特定函数
 dictType *type;
 //私有数据
 void *privdata;
 //哈希表
 dictht ht[2];
 // rehash索引
 //当rehash不在进行时， 值为-1
 in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

属性解释:

• type: type属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数,Redis 会为用途不同的字典设置不同的类型特定函数
• privdata: privdata 属性保存了需要传给那些类型特定函数的可选参数
• ht: 这是包含了两个项的数组，数组中的每一项都是一个dictht哈希表，为什么需要两个项呢？熟悉Java hashmap的人都知道，在一定条件下(元素长度超过数组长度的75%)，会触发rehash的操作。随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会对ht[0]哈希表进行rehash使用。
• trehashidx: trehashidx记录了rehash的进度，如果目前没有进行rehash，它的值为-1

字典定义图示:

这是普通状态的字典的示意图

字典重点特性:

• 字典被广泛用于实现 Redis 的各种功能， 其中包括数据库和哈希键。
• Redis 中的字典使用哈希表作为底层实现， 每个字典带有两个哈希表， 一个用于平时使用， 另一个仅在进行 rehash 时使用。
• 当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
• 哈希表使用链地址法来解决键冲突， 被分配到同一个索引上的多个键值对会连接成一个单向链表。
• 在对哈希表进行扩展或者收缩操作时， 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面， 并且这个 rehash 过程并不是一次性地完成的， 而是渐进式地完成的。

四、跳跃表

说明:

跳跃表(skiplist)是一种有序数据结构，它通过每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表节点结构定义:

 typedef struct zskiplistNode {
   //层
 struct zskiplistLevel {
   //前进指针
   struct zskiplistNode *forward;
   //跨度
   unsigned int span;
 } level[];
 //后退指针
 struct zskiplistNode *backward;
 //分值
 double score;
 //成员对象
 robj *obj;
} zskiplistNode;

看了说明和节点定义的代码，这里解释下各个参数的意义和作用

• 层：层(level[])可以包含多个元素，这里的多个元素的数值都是一样的，相当于冗余数据了，每个元素都包含一个指向其他节点的指针， 程序可以通过这些层来加快访问其他节点的速度， 一般来说， 层的数量(数量是随机的，介于1-32)越多层，访问其他节点的速度就越快，是用空间换时间的做法。
• 前进指针：就是指向其他节点的指针，包含在层里面
• 跨度: 用于记录两个节点的距离，和遍厉其实无关，是用于计算排位(rank)的，排位可以理解为距离大小
• 后退指针: 用于从表尾向表头方向访问节点： 跟可以一次跳过多个节点的前进指针不同， 因为每个节点只有一个后退指针， 所以每次只能后退至前一个节点
• 分值: 是一个 double 类型的浮点数， 跳跃表中的所有节点都按分值从小到大来排序
• 成员对象: 是一个指针， 它指向一个字符串对象

跳跃表

虽然仅靠多个跳跃表节点就可以组成一个跳跃表，如图5-8:

但通过使用一个 zskiplist 结构来持有这些节点， 程序可以更方便地对整个跳跃表进行处理， 比如快速访问跳跃表的表头节点和表尾节点， 又或者快速地获取跳跃表节点的数量（也即是跳跃表的长度）等信息，如图5-9:

zskiplist结构定义:

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

重点总结:

• 跳跃表是有序集合的底层实现之一
• Redis的跳跃表实现由zskiplist和zskiplistNode两部分组成，其中zskiplist用于保存跳跃表的信息，如表头、表尾节点信息，长度；zskiplistNode则表示跳跃表节点
• 跳跃表的节点按照分值大小进行排序，当分值相同时，节点按照成员对象大小进行排序

五、整数集合

说明:

整数集合，整数代表的是int，集合代表的是set，连起来就是intset。整数集合是集合键(Redis五大对象中的set对象)的底层实现之一，为什么说底层实现之一呢？之前说了，每一个对象的底层实现至少用一种底层数据结构实现。可能读者已经想到了，intset就是针对当一个集合只有整数值元素的场景的实现方式。Redis还有一个约束，就是这个集合的元素不是很多时(小于512吧)。

intset结构定义:

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

刚才有说到整数元素小于512时候，会采用intset方式存储，大于512自然要换方式实现了，这会就涉及到升级了。

升级

每当我们要将一个新元素添加到整数集合里面， 并且新元素的类型比整数集合现有所有元素的类型都要长时， 整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。
升级整数集合并添加新元素共分为三步进行：

• 根据新元素的类型， 扩展整数集合底层数组的空间大小， 并为新元素分配空间。
• 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。
• 将新元素添加到底层数组里面。
  升级的动机是很明显的，Redis作为一个内存型数据库，内存资源是很重要的，Redis的每一个设计都是想极大的提高内存利用效率，整数集合保存元素的数组的元素类型是根据存储的元素大小所变化的，动态适应，提高内存利用效率

升级的好处

• 提高灵活性。C 语言是静态类型语言， 为了避免类型错误， 我们通常不会将两种不同类型的值放在同一个数据结构里面。比如说， 我们一般只使用 int16_t 类型的数组来保存 int16_t 类型的值， 只使用 int32_t 类型的数组来保存 int32_t 类型的值， 诸如此类。但是， 因为整数集合可以通过自动升级底层数组来适应新元素， 所以我们可以随意地将 int16_t 、 int32_t 或者 int64_t 类型的整数添加到集合中， 而不必担心出现类型错误， 这种做法非常灵活
• 节约内存。

重点总结

• 整数集合是集合键的底层实现之一
• 整数集合的底层实现为数组， 这个数组以有序、无重复的方式保存集合元素， 在有需要时， 程序会根据新添加元素的类型， 改变这个数组的类型
• 升级操作为整数集合带来了操作上的灵活性， 并且尽可能地节约了内存
• 整数集合只支持升级操作，不支持降级操作

六、压缩列表

说明:

压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。压缩列表也是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点(entry)，一个节点可以保存一个字节数组或一个整数值。

压缩列表构成图:

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值， 其中， 字节数组可以是以下三种长度的其中一种：

• 长度小于等于 63 （2^{6}-1）字节的字节数组；
• 长度小于等于 16383 （2^{14}-1） 字节的字节数组；
• 长度小于等于 4294967295 （2^{32}-1）字节的字节数组；
  而整数值则可以是以下六种长度的其中一种：
• 4 位长，介于 0 至 12 之间的无符号整数；
• 1 字节长的有符号整数；
• 3 字节长的有符号整数；
• int16_t 类型整数；
• int32_t 类型整数；
• int64_t 类型整数。
  每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成， 如图 7-4 所示
  
  压缩列表属性节点属性:
• previous_entry_length: 节点的 previous_entry_length 属性以字节为单位， 记录了压缩列表中前一个节点的长度。previous_entry_length 属性的长度可以是 1 字节或者 5 字节;如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节： 前一节点的长度就保存在这一个字节里面。如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节： 其中属性的第一字节会被设置为 0xFE （十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。

重点总结

• 压缩列表是一种为了节约内存而开发的顺序型数据结构。压缩列表被用作列表键和哈希键的底层实现之一
• 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值
• 添加新节点到压缩列表，或者从列表删除节点，可能会引发连锁的更新操作，但这种操作出现的几率并不高

到此，已经介绍完Redis的六种底层数据结构，可以看出，每一种数据结构都不是为了设计而设计，都是围绕如何节约内存、实现更佳的性能而考虑，下面主要是简单谈下我们使用Redis接触到的五种对象，它们的应用场景，以及和Redis底层数据结构的关联。

五种对象介绍

前面的内容大篇幅地介绍了Redis的六种底层数据结构，然而Redis并没有直接使用这些数据结构，而是用对象系统的方式把底层数据结构封装起来，成了五种常用的对象，分别是字符串对象、列表对象、集合对象、有序集合对象、哈希对象。一种对象至少使用一种底层数据结构

对象结构定义:

typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 指向底层实现数据结构的指针
    void *ptr;

    // ...

} robj;

类型(type):

编码(encoding):

不同类型和编码对象:

一、字符串对象

字符串是我们使用最多的也是Redis最基本的对象类型，一个key对应一个value，value不单单是string类型，也可以是int类型，Redis的string类型是二进制安全的，意思是可以存储任意类型的数据，比如图片(jpg格式等等)，整型，字符串等等，string类型的值最大能存储512MB。

二、列表对象

列表对象的编码可以是 ziplist 或者 linkedlist,ziplist 编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点（entry）保存了一个列表元素。linkedlist 编码的列表对象使用双端链表作为底层实现， 每个双端链表节点(node)都保存了一个字符串对象， 而每个字符串对象都保存了一个列表元素。

三、哈希对象

哈希对象的编码可以是 ziplist 或者 hashtable。
用ziplist编码要满足两个条件：1.哈希对象保存的所有键值对的字符串长度都小于64字节 2.哈希对象保存的所有键值对数量都小于512个；不能满足这两个条件的哈希对象需要使用hashtable编码(字典底层实现)

四、集合对象

集合对象的编码可以是 intset或者hashtable
使用intset编码两个条件:1.集合元素保存的都是int类型 2.集合保存的元素不超过512个
不满足使用instset编码条件需要使用hashtable。需要注意的是第二个条件的元素数量上限值是可以修改的，具体可以看Redis配置文件中set-max-intset-entries

五、有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist。
使用ziplist编码的两个条件:1. 有序集合保存的元素数量小于128个 2. 有序集合保存的所有元素成员长度都小于64个字节；
不能满足以上两个条件的有序集合对象将使用skiplist编码，需要注意的是以上两个条件的上限值都是可以修改的，具体可以看Redis配置文件zset-max-ziplist-entries选项和zet-max-ziplist-value选项的说明。
对于使用ziplist编码的有序集合对象来说，当使用ziplist编码所需的两个条件有任意一个不满足时候，就会执行对象的编码转换操作，原本保存在压缩列表里的所有集合元素都会被转移并保存到zset结构里面，对象的编码也会从ziplist变更为skiplist。

最后小总结

• Redis的键和值都是一个对象
• Redis一共有五种对象类型，分别是字符串、列表、哈希、集合、有序集合，每种类型的对象至少有两种或以上的编码方式，可以在不同的场景上节约对象存储内存，优化对象使用效率