Redis对象底层数据结构

SDS(简单动态字符串)

Redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符数组，以下简称C字符串），而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。

在Redis里面，C字符串只会作为字符串字面量（string literal）用在一些无须对字符串值进行修改的地方，比如打印日志： redisLog(REDIS_WARNING,"Redis is now ready to exit, bye bye..."); 当Redis需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis就会使用SDS来表示字符串值，比如在Redis的数据库里面，包含字符串值的键值对在底层都是由SDS实现的。

struct sdshdr {
// 记录buf 数组中已使用字节的数量
// 等于SDS 所保存字符串的长度
int len;
 // 记录buf 数组中未使用字节的数量
int free;
// 字节数组，用于保存字符串
char buf[];
 };

redis中所定义SDS，如上所示。字符串内容由一个char数组定义的buf保存，结构中还保存了字符串的实际长度（不包括最后的‘\0’结束标志）以及buf的可用空间大小。

SDS有如下几个特点：

• 字符串内容以‘\0’结尾，当字符串为非二进制内容时，可以兼容c字符串的部分函数。
• SDS中记录了字符串的长度，可以通过常数时间复杂度获取字符串的长度。
• SDS中记录了buf的剩余空间，可以有效杜绝缓冲区溢出。
• SDS中buf需要扩展时，会同时分配额外的空间，以便减少空间扩展次数。当扩展后的字符串实际占用空间小于1M,同时会分配多一倍的字符串实际占用空间，当扩展后的字符串实际占用空间大于等于1M,同时会分配额外的1M空间。SDS不会因为字符串长度变短而释放空间（惰性空间释放）。

链表

Redis使用的c语言并没有内置链表这种数据结构，所以Redis构建了自己的链表实现，作为redis列表的底层数据结构

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

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;

Redis中定义的链表结构，如上list所示，具有以下特性：

双端：链表节点带有prev和next指针，获取某个节点的前置节- 点和后置节点的复杂度都是O（1）。

• 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。
• 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。
• 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O（1）。
• 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

字典

字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

除了用来表示数据库之外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

哈希表&哈希表节点

typedef struct dictht {
     // 哈希表数组 （表节点指针数组）
     dictEntry **table;

     // 哈希表大小
     unsigned long size;

     // 哈希表大小掩码，用于计算索引值
     // 总是等于size-1
     unsigned long sizemask;

     // 该哈希表已有节点的数量
     unsigned long used;
 } dictht;

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

 Redis中字典的底层实现hash表实现如上所示。

hash表如dictht所示，其包含的数据由一个指针数组table关联，table的大小记录在size中，used记录了哈希表目前包含节点的数量。

table中每个元素是一个指向哈希表节点的dicEntry指针。哈希表节点存储了一个键值对 key - v, 以及一个指向另外一个节点的指针next。这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题。所以Redis中哈希表是采用链地址法来解决键冲突问题。

基于哈希表的字典

typedef struct dict {

     // 类型特定函数
     dictType *type;

     // 私有数据
     void *privdata;

     // 哈希表
     dictht ht[2]; 

    // rehash 索引
     // 当rehash不在进行时，值为-1
     int rehashidx;
} dict;


typedef struct dictType {
     // 计算哈希值的函数
     unsigned int (*hashFunction)(const void *key);

     // 复制键的函数
     void *(*keyDup)(void *privdata, const void *key);

     // 复制值的函数
     void *(*valDup)(void *privdata, const void *obj);

     // 对比键的函数
     int (*keyCompare)(void *privdata, const void *key1, const void *key2);

     // 销毁键的函数
     void (*keyDestructor)(void *privdata, void *key);

     // 销毁值的函数
     void (*valDestructor)(void *privdata, void *obj);
 } dictType;

Redis中基于哈希表的字典完整结构如上所示。

• type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。
• type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。 
• 而privdata属性则保存了需要传给那些类型特定函数的可选参数。
• ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht0哈希表，ht1哈希表只会在对ht0哈希表进行rehash时使用。
• 除了ht1之外，另一个和rehash有关的属性就是rehashidx，它记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。

rehash（重新散列）

为了hash表的负载因子( ht0.used/ht0.size )维持在一个合理范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作来完成，Redis对字典的哈希表执行rehash的步骤如下：

1. 为字典的ht1哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht0当前包含的键值对数量（也即是ht0.used属性的值）： 如果执行的是扩展操作，那么ht1的大小为第一个大于等于ht0.used*2的2^n（2的n次方幂）； 如果执行的是收缩操作，那么ht1的大小为第一个大于等于ht0.used的2^n 。
2. 将保存在ht0中的所有键值对rehash到ht1上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht1哈希表的指定位置上。
3. 当ht0包含的所有键值对都迁移到了ht1之后（ht0变为空表），释放ht0，将ht1设置为ht0，并在ht1新创建一个空白哈希表，为下一次rehash做准备。

渐进式rehash

考虑到hash表中的键值对可能非常多，如果一次性完成rehash操作，rehash操作过程中可能因为庞大的计算量导致服务器不能正常处理请求，所以rehash操作是分多次渐进完成的。

以下是哈希表渐进式rehash的详细步骤：

1. 为ht1分配空间，让字典同时持有ht0和ht1两个哈希表。
2. 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
3. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht0哈希表在rehashidx索引上的所有键值对rehash到ht1，当rehash工作完成之后，程序将rehashidx属性的值增一。
4. 随着字典操作的不断执行，最终在某个时间点上，ht0的所有键值对都会被rehash至ht1，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。新添加到字典的键值对一律会被保存到ht1里面，而ht0则不再进行任何添加操作，这一措施保证了ht0包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

跳跃表

Redis中常用的有序集合键的底层实现用到了跳跃表，其结构如下所示。

typedef struct zskiplistNode {

     // 层
     struct zskiplistLevel {
         //前进指针
         struct zskiplistNode *forward;
         // 跨度
         unsigned int span;
     } level[];

     // 后退指针
     struct zskiplistNode *backward;

     // 分值
     double score;

     // 成员对象
     robj *obj;
 } zskiplistNode;


typedef struct zskiplist {
     // 表头节点和表尾节点
     structz skiplistNode *header, *tail;
     // 表中节点的数量
     unsigned long length;
     // 表中层数最大的节点的层数
     int level;
 } zskiplist;

上图左边第一个表示了 zskiplist结构，管理整个跳表，右边四个节点描述了4个zskiplistNode结构，代表了跳表中的节点。

zskiplist结构中的header指向的头节点分值score和obj无意义，length字段记录的长度不包含该头节点，level记录了跳表中目前最高层次节点的层数。

zskiplistNode结构中 obj指向节点实际存储的成员对象（o1,o2,o3），score表示节点的分值，跳表中节点按分值从小到大排列，backward指向前驱节点。level（L1、L2、……、LN）记录了该节点的各层信息。

（L1、L2、……、LN）层信息结构为zskiplistLevel结构所定义的层信息，其中包含了指向该层下一节点的指针forward，以及距离本层下一节点的距离span, 相邻节点的距离为1。因此计算从头节点遍历到某个节点所经过的路径的span之和就可以得到该节点的在整个跳表中的排名。

整数集合

整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。整数集合的结构如下。

typedef struct intset {
// 编码方式
uint32_t encoding;

// 集合包含的元素数量
uint32_t length;

// 保存元素的数组
int8_t contents[];
} intset;

 实际元素有序的保存在contents中，其中不存在重复元素。contents虽然被定义为int8_t，但其并不保存int8_t的元素。根据实际需要，编码方式encoding会从16位到64位升级，分别对应INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64三种编码类型。encoding为上述三种值时，contents分别为 int16_t、int32_t、int64_t的数组。

说明：在能满足表示集合中元素范围的情况下，redis总时采用最省空间的编码方式，当有超出当前编码方式表示的范围的新元素加入，整数集合会对所有元素升级编码方式、重新申请空间。编码方式一旦被升级，不会再降级。

压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

压缩列表结构如上图所示，其节点数据存放在entryX中，每个节点entryX结构如下图所示。

previous_entry_length: 字段代表前一个节点（entry)的长度，有了这个值，就可以通过当前节点的起始地址进行指针偏移运算得到前一个节点的起始地址，从而直接访问前一个节点。

• 如果前一节点的长度小于254字节，那么previous_entry_length属性的长度为1字节：前一节点的长度就保存在这一个字节里面。
• 如果前一节点的长度大于等于254字节，那么previous_entry_length属性的长度为5字节：其中属性的第一字节会被设置为0xFE（十进制值254），而之后的四个字节则用于保存前一节点的长度。

encoding: 记录了节点的content属性所保存数据的类型以及长度。

• 一字节、两字节或者五字节长，值的最高位为00、01或者10的是字节数组编码：这种编码表示节点的content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录；

• 一字节长，值的最高位以11开头的是整数编码：这种编码表示节点的content属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录；

content: 保存节点的值，可以是一个字节数组或整数，值的类型和长度，根据encoding的值确定。

Redis对象与底层数据结构关系

typedef struct redisObject {
// 类型
unsigned type:4;

// 编码
unsigned encoding:4;

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

redis对象数据结构的核心定义如上代码片段所示：

• type 描述了这个该对象的类型，不同取值分别可以表示，字符串对象、列表对象、哈希对象、集合对象、有序集合对象。
• encoding 表示对象的编码方式，决定了 ptr指向的结构的实际类型(文章前面描述的各种结构)
• ptr 指向实际存储结构

不同类型的对象，其采用的底层结构，如下图所示。