1、简单动态字符串（SDS）

定义

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

说明：键、值、SDS 还被用作缓冲区（buffer）： AOF 模块中的 AOF 缓冲区， 以及客户端状态中的输入缓冲区

字符串和 SDS 之间的区别

C 字符串SDS获取字符串长度的复杂度为 O(N) 。获取字符串长度的复杂度为 O(1) 。API 是不安全的，可能会造成缓冲区溢出。API 是安全的，不会造成缓冲区溢出。修改字符串长度 N 次必然需要执行 N 次内存重分配。修改字符串长度 N 次最多需要执行 N 次内存重分配。只能保存文本数据。可以保存文本或者二进制数据。可以使用所有 <string.h> 库中的函数。/<string.h>可以使用一部分 <string.h> 库中的函数。 空间预分配用于优化 SDS 的字符串增长操作： 当 SDS 的 API 对一个 SDS 进行修改， 并且需要对 SDS 进行空间扩展的时候， 程序不仅会为 SDS 分配修改所必须要的空间， 还会为 SDS 分配额外的未使用空间。 其中， 额外分配的未使用空间数量由以下公式决定： 如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ， 那么程序分配和 len 属性同样大小的未使用空间， 这时 SDS len 属性的值将和 free 属性的值相同。 举个例子， 如果进行修改之后， SDS 的 len 将变成 13 字节， 那么程序也会分配 13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。 如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB 的未使用空间。 举个例子， 如果进行修改之后， SDS 的 len 将变成 30 MB ， 那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte。 通过空间预分配策略， Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。 /<string.h>

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;

特性

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

3、字典

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

渐进式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 操作已完成。

4、跳跃表

typedef struct zskiplist {
 // 头节点，尾节点
 struct zskiplistNode *header, *tail;
 // 节点数量
 unsigned long length;
 // 目前表内节点的最大层数
 int level;
} zskiplist;
typedef struct zskiplistNode {
 // 成员对象
 robj *obj;
 // 分值
 double score;
 // 后退指针
 struct zskiplistNode *backward;
 // 层
 struct zskiplistLevel {
 // 前进指针 

 struct zskiplistNode *forward;
 // 跨度
 unsigned int span;
 } level[];
} zskiplistNode;

5、整数集合

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

} intset;

说明

contents 数组是整数集合的底层实现： 整数集合的每个元素都是 contents 数组的一个数组项（item）， 各个项在数组中按值的大小从小到大有序地排列， 并且数组中不包含任何重复项。 length 属性记录了整数集合包含的元素数量， 也即是 contents 数组的长度。 虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组， 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值： 如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个项都是一个 int16_t类型的整数值 （最小值为 -32,768 ，最大值为 32,767 ）。 如果 encoding 属性的值为 INTSET_ENC_INT32 ， 那么 contents 就是一个 int32_t 类型的数组， 数组里的每个项都是一个 int32_t类型的整数值 （最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。 如果 encoding 属性的值为 INTSET_ENC_INT64 ， 那么 contents 就是一个 int64_t 类型的数组， 数组里的每个项都是一个 int64_t类型的整数值 （最小值为 -9,223,372,036,854,775,808 ，最大值为 9,223,372,036,854,775,807 ）

6、压缩链表

属性类型长度用途zlbytesuint32_t4 字节记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend的位置时使用。zltailuint32_t4 字节记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。zllenuint16_t2 字节记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。entryX列表节点不定压缩列表包含的各个节点，节点的长度由节点保存的内容决定。zlenduint8_t1 字节特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

定义

• 节点的 previous_entry_length属性以字节为单位， 记录了压缩列表中前一个节点的长度。
• 节点的 encoding属性记录了节点的 content属性所保存数据的类型以及长度：
• 节点的 content属性负责保存节点的值， 节点值可以是一个字节数组或者整数， 值的类型和长度由节点的 encoding属性决定。

7、对象

typedef struct redisObject {
 // 类型
 unsigned type:4;
 // 不使用(对齐位)
 unsigned notused:2;
 // 编码方式
 unsigned encoding:4;
 // LRU 时间（相对于 server.lruclock）
 unsigned lru:22;
 // 引用计数
 int refcount;
 // 指向对象的值
 void *ptr;
} robj;

类型

对象对象 type 属性的值TYPE 命令的输出字符串对象REDIS_STRING"string"列表对象REDIS_LIST"list"哈希对象REDIS_HASH"hash"集合对象REDIS_SET"set"有序集合对象REDIS_ZSET"zset"

编码

类型编码对象OBJECT ENCODING 命令输出REDIS_STRINGREDIS_ENCODING_INT使用整数值实现的字符串对象。"int"REDIS_STRINGREDIS_ENCODING_EMBSTR使用 embstr 编码的简单动态字符串实现的字符串对象。"embstr"REDIS_STRINGREDIS_ENCODING_RAW使用简单动态字符串实现的字符串对象。"raw"REDIS_LISTREDIS_ENCODING_ZIPLIST使用压缩列表实现的列表对象。"ziplist"REDIS_LISTREDIS_ENCODING_LINKEDLIST使用双端链表实现的列表对象。"linkedlist"REDIS_HASHREDIS_ENCODING_ZIPLIST使用压缩列表实现的哈希对象。"ziplist"REDIS_HASHREDIS_ENCODING_HT使用字典实现的哈希对象。"hashtable"REDIS_SETREDIS_ENCODING_INTSET使用整数集合实现的集合对象。"intset"REDIS_SETREDIS_ENCODING_HT使用字典实现的集合对象。"hashtable"REDIS_ZSETREDIS_ENCODING_ZIPLIST使用压缩列表实现的有序集合对象。"ziplist"REDIS_ZSETREDIS_ENCODING_SKIPLIST使用跳跃表和字典实现的有序集合对象。"skiplist"

字符串对象

值编码可以用long类型保存的整数int长度太大的整数或者浮点数embstr或者raw小于等于39字节的字符串embstr大于39字节的字符串raw

字符串对象-embstr和raw区别

embstr 编码是专门用于保存短字符串的一种优化编码方式， 这种编码和 raw 编码一样， 都使用 redisObject 结构和 sdshdr 结构来表示字符串对象， 但 raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构， 而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间， 空间中依次包含 redisObject 和 sdshdr 两个结构。 优势 embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次。 释放 embstr 编码的字符串对象只需要调用一次内存释放函数， 而释放 raw 编码的字符串对象需要调用两次内存释放函数。 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面， 所以这种编码的字符串对象比起 raw 编码的字符串对象能够更好地利用缓存带来的优势。

列表对象

当列表对象可以同时满足以下两个条件时， 列表对象使用 ziplist 编码： 列表对象保存的所有字符串元素的长度都小于 64 字节； 列表对象保存的元素数量小于 512 个； 不能满足这两个条件的列表对象需要使用 linkedlist 编码。

哈希对象

当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码： 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节； 哈希对象保存的键值对数量小于 512 个； 不能满足这两个条件的哈希对象需要使用 hashtable 编码。

集合对象

当集合对象可以同时满足以下两个条件时， 对象使用 intset 编码： 集合对象保存的所有元素都是整数值； 集合对象保存的元素数量不超过 512 个； 不能满足这两个条件的集合对象需要使用 hashtable 编码。

hashtable 编码的集合对象使用字典作为底层实现， 字典的每个键都是一个字符串对象， 每个字符串对象包含了一个集合元素， 而字典的值则全部被设置为 NULL

有序集合对象

当有序集合对象可以同时满足以下两个条件时， 对象使用 ziplist 编码： 有序集合保存的元素数量小于 128 个； 有序集合保存的所有元素成员的长度都小于 64 字节； 不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

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

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

如果我们只使用字典来实现有序集合， 那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留， 但是， 因为字典以无序的方式来保存集合元素， 所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时， 程序都需要对字典保存的所有元素进行排序， 完成这种排序需要至少 O(N \\log N) 时间复杂度， 以及额外的 O(N) 内存空间 （因为要创建一个数组来保存排序后的元素）。 另一方面， 如果我们只使用跳跃表来实现有序集合， 那么跳跃表执行范围型操作的所有优点都会被保留， 但因为没有了字典， 所以根据成员查找分值这一操作的复杂度将从 O(1) 上升为 O(\\log N)