1.SDS

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

  • SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小。

  • 通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

    1. 空间预分配：惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。

      • 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。
      • 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。

    2. 惰性空间释放：惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。

1）常数复杂度获取字符串长度。

2）杜绝缓冲区溢出。

3）减少修改字符串长度时所需的内存重分配次数。

4）二进制安全。

5）兼容部分C字符串函数。

2.链表


//==================链表节点=============
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;

在这里插入图片描述

3.字典

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


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


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

在这里插入图片描述

  • ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
  • rehashidx记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。
  • Redis的哈希表使用链地址法（separate chaining）来解决键冲突，为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O（1）），排在其他已有节点的前面。

3.1 rehash

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

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做准备。

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

  1. 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
  2. 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。

3.2 渐进式rehash

redis的rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。这样做的原因在于，如果ht[0]里的键值对非常大，那么要一次性将这些键值对全部rehash到ht[1]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

以下是哈希表渐进式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进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找。
  • 在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作。

4.跳跃表

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;
  • 跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
  • 跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。
  • Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构

  • level：每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。header默认层高32。
  • 每个层都有一个指向表尾方向的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。
  • 跨度（level[i].span）：用于记录两个节点之间的距离。在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

5.整数集合

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

在这里插入图片描述

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。

6.压缩列表

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

属性 类型 长度 作用
zlbytes uint32_t 4 压缩列表占用的内存字节数
zltail uint32_t 4 表尾节点距离列表起始地址的字节数，因此可通过起始字节直接计算得到表尾地址
zllen uint16_t 2 节点数量。小于65535时，值就是节点数量；大于时，需要遍历列表才能计算得出节点数量。
entry_X 列表的节点 即保存的节点。长度由各自节点内容决定
zlend uint8_t 1 特殊值0xFF(255)，标记压缩列表末端

  • previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度。

    压缩列表的从表尾向表头遍历操作就是使用这一原理实现的，只要我们拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的previous_entry_length属性，程序就可以一直向前一个节点回溯，最终到达压缩列表的表头节点。

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

  • content属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。

6.1 连锁更新

每个节点的previous_entry_length属性都记录了前一个节点的长度：

  • 如果前一节点的长度小于254字节，那么previous_entry_length属性需要用1字节长的空间来保存这个长度值。

  • 如果前一节点的长度大于等于254字节，那么previous_entry_length属性需要用5字节长的空间来保存这个长度值。

    如果 原有的节点都小于 254 字节, 突然间插入一个大于等于 254 字节,原有节点的previous_entry_length的1个字节已经不满足需求，需要扩展至5字节， 压缩列表将会发生空间重分配(连锁更新);

    删除节点, 也会发生导致连锁更新。

    但是因为进行连锁更新，要求列表由连续多个长度在250到253字节的节点，这种情况并不多见，所以基本不用担心它的性能问题。

6.2快速链表 quicklist

redis 3.2以后，quicklist作为列表键的实现底层实现之一，代替了压缩列表

typedef struct quicklist {
    //指向头部(最左边)quicklist节点的指针
    quicklistNode *head;
    //指向尾部(最右边)quicklist节点的指针
    quicklistNode *tail;
    //ziplist中的entry节点计数器
    unsigned long count;  
    //quicklist的quicklistNode节点计数器
    unsigned int len; 
    //保存ziplist的大小，配置文件设定，占16bits
    int fill : 16;      
    //保存压缩程度值，配置文件设定，占16bits，0表示不压缩
    unsigned int compress : 16; 
} quicklist;


typedef struct quicklistNode {
    struct quicklistNode *prev;     //前驱节点指针
    struct quicklistNode *next;     //后继节点指针
    //不设置压缩数据参数recompress时指向一个ziplist结构
    //设置压缩数据参数recompress指向quicklistLZF结构
    unsigned char *zl;
    //压缩列表ziplist的总长度
    unsigned int sz;              
    //ziplist中包的节点数，占16 bits长度
    unsigned int count : 16;    
    //表示是否采用了LZF压缩算法压缩quicklist节点，1表示压缩过，2表示没压缩，占2 bits长度
    unsigned int encoding : 2;       
    //表示一个quicklistNode节点是否采用ziplist结构保存数据，2表示压缩了，1表示没压缩，默认是2，占2bits长度
    unsigned int container : 2;   
    //标记quicklist节点的ziplist之前是否被解压缩过，占1bit长度
    //如果recompress为1，则等待被再次压缩
    unsigned int recompress : 1;
    //测试时使用
    unsigned int attempted_compress : 1; 
    //额外扩展位，占10bits长度
    unsigned int extra : 10; 
} quicklistNode;

在这里插入图片描述

7.对象

Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。

前面介绍的动态字符串（SDS）、双端链表、字典、压缩列表、整数集合等等，Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。

这样做的好处：

  1. 我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
  2. Redis的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放。
  3. Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。
typedef struct redisObject {
    //类型
	//键：总是字符串对象
	//值：符串对象、列表对象、哈希对象、集合对象和有序集合对象
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;

	//引用计数
    int refcount; 

	//记录对象最后一次被命令程序访问的时间
	unsigned lru:22;
    // ...
} robj;
类型 编码 对象
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象
REDIS_STRING REDIS_ENCODING_EMBSTR 这货redis3.0引入的，不管
REDIS_STRING REDIS_ENCODING_RAW sds实现的字符串对象
REDIS_LIST REDIS_ENCODING_ZIPLIST 使用压缩列表实现的列表对象
REDIS_LIST REDIS_ENCODING_LINKEDLIST 使用双向链表实现的列表对象
REDIS_HASH REDIS_ENCODING_ZIPLIST 使用压缩列表实现的哈希对象
REDIS_HASH REDIS_ENCODING_HT 使用字典实现的哈希对象
REDIS_SET REDIS_ENCODING_INTSET 使用整数集合实现的集合对象
REDIS_SET REDIS_ENCODING_HT 使用字典实现的集合对象
REDIS_ZSET REDIS_ENCODING_ZIPLIST 使用压缩列表实现的有序集合对象
REDIS_ZSET REDIS_ENCODING_SKIPLIST 使用跳跃表想和字典实现的有序集合对象

7.1 字符串对象

字符串对象的编码可以是int、raw或者embstr。

  • 如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long），并将字符串对象的编码设置为int。
  • 字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为raw。
  • 字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值。

embstr的创建只需分配一次内存，而raw为两次，分别创建redisObject结构和sdshdr结构。相对地，embstr释放内存的次数也由两次变为一次。embstr的objet和sds放在一起，更好地利用缓存带来的优势。redis并未提供任何修改embstr的方式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。

字符串对象是Redis五种类型的对象中唯一一种会被其他四种对象嵌套的对象。

embstr例图：

embstr编码的字符串对象

7.2 列表对象

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

  • 使用ziplist（redis 3.2以后，quicklist作为列表键的实现底层实现之一，代替了压缩列表）：

    1. 列表对象保存的所有字符串元素的长度都小于64字节。
    2. 列表对象保存的元素数量小于512个。

    ziplist编码的list

  • 使用linklist：

7.3 哈希对象

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

  • 使用ziplist

    1. 键和值的字符串长度小于64字节；
    2. 键值对数量少于512个；

    使用ziplist编码时

  • 使用hashtable

    使用hashtable编码时

7.4 集合对象

集合对象的编码可以是intset或hashtable

  • 使用inset

    1. 所有元素为整数值；
    2. 保存的元素不超过512个；

    使用inset编码的集合

  • 使用hashtable：字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为NULL。

    使用hashtable编码的集合

7.5 有序集合对象

有序集合的编码可以是ziplist或skiplist，压缩列表内的集合元素按分值从小到大排列

  • 使用ziplist：每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。

    在这里插入图片描述

  • 使用ziplist

    1. 元素数量少于128个；

    2. 元素长度小于64字节；

    • skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表： 
          typedef struct zset {
        zskiplist *zsl;
        dict *dict;
    } zset;

    思考：为什么额外添加一个字典？

    zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O（1）复杂度查找给定成员的分值，ZSCORE命令就是根据这一特性实现的。
    如果我们只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值这一操作的复杂度将从O（1）上升为O（logN）。因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。
    • 跳跃表和字典使用指针来共享相同的元素和分值，因此不会产生重复，也不会造成内存浪费

7.6 内存回收

Redis构建一个引用计数计数实现内存回收机制；引用计数由redisObject结构的refcount属性记录：

typedef struct redisObject{
    //...
    //引用计数
    int refcount; 
    //...
}
  • 创建新对象时，refcount被初始化为1；
  • 对象被新程序使用时，refcount++；
  • 对象不被一个程序使用时，refcount--；
  • 对象计数值为0时，对象占用的内存会被释放；

7.7 对象共享

  • 对象的计数属性带有对象共享的作用；
  • 当n个键保存同一个值时，这些键的值指针指向同一个值对象，值对象的refcount为n；
  • Redis在初始化服务器时，会创建一万个字符串对象（0~9999的字符串对象），当服务器需要用到这些值对象时，服务器会使用这些共享对象，而不是创建新对象；
  • Redis只对包含整数值的字符串对象进行共享，验证数字的时间复杂度为O(1)；

7.8 对象的空转时长

redisObject结构里有个lru属性，记录对象最后一次被命令程序访问的时间；

typedef struct redisObject{
    //...
    unsigned lru:22;
    //...
}

  • 使用命令OBJECT IDLETIME可以显示对象的空转时间，不会改变对象的空转时间；

  • 如果服务器打开maxmemory选项，并且回收内存的算法为volatile-lru或allkeys-lru，那么当服务器占用的内存数超过maxmemory选项设置的上限值是，空转时间较高的键会优先被服务器释放，回收内存；