Redis中数据结构

Redis中用到的所有数据结构知识点

简单动态字符串

Redis使用SDS(简单动态字符串)作为字符串表示

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

比起C字符串，SDS具有以下优点：1）常数复杂度获取字符串长度。2）杜绝缓冲区溢出。3）减少修改字符串长度时所需的内存重分配次数。4）二进制安全。5）兼容部分C字符串函数。

通过使用SDS而不是C字符串，Redis将获取字符串长度所需的复杂度从O（N）降低到了O（1），这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。例如，因为字符串键在底层使用SDS来实现，所以即使我们对一个非常长的字符串键反复执行STRLEN命令，也不会对系统性能造成任何影响，因为STRLEN命令的复杂度仅为O（1）。

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

//每个链表节点的结构---使用双向链表结构
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的链表实现的特性可以总结如下：

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

❑无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。

❑带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。

❑带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O（1）。

❑多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

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

字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。

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

字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等。

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

//哈希表结构
typedef struct dictht{
   //哈希表数组---dictEntry结构保存着一个键值对
    dictEntry **table;
   //哈希表大小
    unsigned long size;
   //哈希表大小掩码，用于计算哈希值，总是等于size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
}distht;

哈希表 

//哈希表节点结构
typedef struct distEntry{
    //键
    void * key;
    //值v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    }
    //指向下一个哈希表节点，形成链表--next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题。
    struct distEntry *next;
}distEntry;

Redis字典结构

//Redis字典结构
typedef struct dist{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    distht ht[2];
    //rehash索引
    //当rehash不再进行时，该值为-1
    int trehashindex
}

字典
type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的：❑type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。❑而privdata属性则保存了需要传给那些类型特定函数的可选参数。

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。

如何解决键冲突？

Redis的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O（1）），排在其他已有节点的前面

举个例子，假设程序要将键值对k2和v2添加到图1所示的哈希表里面，并且计算得出k2的索引值为2，那么键k1和k2将产生冲突，而解决冲突的办法就是使用next指针将键k2和k1所在的节点连接起来，如图2所示。
因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O（1）），排在其他已有节点的前面。
图1
图1：包含俩个键值对的哈希表
图2
图2：使用链表解k2与k1冲突

rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

负载因子=哈希表已保存节点数量/哈希表大小

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

1）为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）：

❑如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2 n（2的n次方幂）；

❑如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2 n。

2）将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。

3）当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

渐进式rehash

rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

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

1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。

2）在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。

3）在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。

4）随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找，诸如此类。

在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

跳跃表

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

跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。Redis使用跳跃表作为有序集合键的底层实现之一。和链表、字典等数据结构被广泛地应用在Redis内部不同，Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构

//跳跃表节点结构
typedef struct zskiplistNode{
    //层--随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。
    //作用：跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度
    struct    zskiplistLevel{
        //前进指针---每个层都有一个指向表尾方向的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点
        struct zskiplistNode *forward;
        //跨度---用于记录两个节点之间的距离
        unsigned int span;
    }level[];
    //后退指针--用于从表尾向表头方向访问节点。
    struct zskiplistNode * bachward;
    //分值--跳跃表中的所有节点都按分值从小到大来排序。
    double score;
    //成员对象--是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值。
    robj *obj;
}zskiplistNode;

//跳跃表结构
typedef struct zskiplist{
    //表头节点
    struct zskiplistNode *header;
    //表尾节点
    struct zskiplistNode *tail;
   //表中节点的数量
    unsigned long length;
     //表中层数最大的节点的层数
    int level;
}zskiplist;

header和tail指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度为O（1）。通过使用length属性来记录节点的数量，程序可以在O（1）复杂度内返回跳跃表的长度。level属性则用于在O（1）复杂度内获取跳跃表中层高最大的那个节点的层数量，注意表头节点的层高并不计算在内。

图用虚线标记了在跳跃表中查找分值为3.0、成员对象为o3的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为3，所以目标节点在跳跃表中的排位为3。

跳跃表结构示例1

在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。

在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）
跳跃表结构示例2

整数集合

整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

typedef struct intset{
    //编码方法--INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64
    //当进行升级时，contents集合中保存的都是编码指定类型的整数值
    uint32_t encoding;
    //集合包含的元素数量--contents数组的长度
    uint32_t length;
    //保存元素的数量---，各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。
    int8_t contents[];
}intset;

整数集合升级

当将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade）。

整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存。

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

压缩列表（难点*）

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

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

Redis中对象

Redis数据库是一种键值对存储数据库，基于内存存储。
Redis并没有直接使用上述数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象(String)、列表对象(List)、哈希对象(Hash)、集合对象(Set)和有序集合(Zset)对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。

Redis使用对象来表示数据库中的键和值，当在Redis中创建一个键值对时，实际上会创建俩个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对像、集合对象或有序集合对象其中一种。Redis的键对象都为字符串对象,因此我们实际上说的类型，指的是值的类型。

Redis中的每个对象都由一个redisObject结构表示，该结构中和保存数据有关的三个属性分别是type属性、encoding属性和ptr属性

typedef struct redisobject{
    //类型----五种对象类型：REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET
    //分别代表字符串对象、列表对象、哈希对象、集合对象、有序集合对象
    unsigned type:4;
    //编码--对象使用什么数据结构作为底层实现
    unsigned encoding:4;
    //指向底层实现数据结构的指针--类似引用
    void *ptr
}redisobject;

TYPE命令的实现方式也与此类似，当我们对一个数据库键执行TYPE命令时，命令返回的结果为数据库键对应的值对象的类型，而不是键对象的类型
例子

字符串对象的编码方式有：long、raw、embstr

列表对象的编码可以是ziplist或者linkedlist

哈希对象的编码可以是ziplist或者hashtable。

哈希对象存储对象方式一：ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾。
压缩列表存储哈希对象

哈希对象存储对象方式二：hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存：❑字典的每个键都是一个字符串对象，对象中保存了键值对的键；❑字典的每个值都是一个字符串对象，对象中保存了键值对的值。
字典存储哈希对象

集合对象的编码可以是intset或者hashtable。intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为NULL。
Redis集合对象存储方式

有序集合的编码可以是ziplist或者skiplist。

ziplist编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向。

重点

skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表

typedef struct zset{
    zskiplist *zsl;
    dict *dick;
}zset;

zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score属性则保存了元素的分值。通过这个跳跃表，程序可以对有序集合进行范围型操作，比如ZRANK、ZRANGE等命令就是基于跳跃表API来实现的。

zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O（1）复杂度查找给定成员的分值。ZSCORE命令就是根据这一特性实现的，而很多其他有序集合命令都在实现的内部用到了这一特性。

有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。值得一提的是，虽然zset结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。

思考题 为什么有序集合需要同时使用跳跃表和字典来实现？

在理论上，有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现，但无论单独使用字典还是跳跃表，在性能上对比起同时使用字典和跳跃表都会有所降低。举个例子，如果我们只使用字典来实现有序集合，那么虽然以O（1）复杂度查找成员的分值这一特性会被保留，但是，因为字典以无序的方式来保存集合元素，所以每次在执行范围型操作——比如ZRANK、ZRANGE等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少O（NlogN）时间复杂度，以及额外的O（N）内存空间（因为要创建一个数组来保存排序后的元素）。

另一方面，如果我们只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值这一操作的复杂度将从O（1）上升为O（logN）。因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。
Redis有序集合数据结构

类型检测与命令多态

Redis中操作键的命令分为俩类，其中一种是可以对任何类型的键进行操作的，例如：DEL、EXPIRE、RENAME、TYPE、OBJECT等命令。

另一种是对特定类型的键操作：

  • SET、GET、APPEND、STRLEN等命令可对字符串进行操作（S）
  • HSET、HGET、HDEL、HLEN等命令可对哈希键进行操作（H）
  • RPUSH、LPOP、LINSERT、LLEN等命令只能对列表键执行；（R、L)
  • SADD、SPOP、SINTER、SCARD等命令只能对集合键执行；(S)
  • ZADD、ZCARD、ZRANK、ZSCORE等命令只能对有序集合键执行；(Z)

类型特定命令所进行的类型检查是通过redisObject结构的type属性来实现的：

❑在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行命令所需的类型，如果是的话，服务器就对键执行指定的命令；

❑否则，服务器将拒绝执行命令，并向客户端返回一个类型错误。

Redis除了会根据值对象的类型来判断键是否能够执行指定命令之外，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令。
执行步骤

Redis内存回收

因为C语言并不具备自动内存回收功能，所以Redis在自己的对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。对象的整个生命周期可以划分为创建对象、操作对象、释放对象三个阶段。

对象的引用计数信息会随着对象的使用状态而不断变化：

❑在创建一个新对象时，引用计数的值会被初始化为1；

❑当对象被一个新程序使用时，它的引用计数值会被增一；

❑当对象不再被一个程序使用时，它的引用计数值会被减一；

❑当对象的引用计数值变为0时，对象所占用的内存会被释放。

对象共享

除了用于实现引用计数内存回收机制之外，对象的引用计数属性还带有对象共享的作用。在Redis中，让多个键共享同一个值对象需要执行以下两个步骤：

1）将数据库键的值指针指向一个现有的值对象；

2）将被共享的值对象的引用计数增一。

目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。

Redis不共享包含字符串的对象，但共享字符串键对象，共享对象不单单只有字符串键可以使用，那些在数据结构中嵌套了字符串对象的对象（linkedlist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象，以及zset编码的有序集合对象）都可以使用这些共享对象。