在Redis数据结构和对象机制中提到的图中，我们知道可以通过 redisObject 对象的 type 和 encoding 属性。Rediss可以决定 主要底层数据结构：SDS、QuickList、ZipList、HashTable、IntSet、ZskipList 。
先来看看传统的C 语言如何存储字符串：例如，一个 "Redis" 字符串：
为什么不用传统的呢？ C 语言模式，因为我们知道数组模式在获取字符串长度或扩展容量方面存在缺陷：例如，获得数组长度的复杂性是O(N), 而且数组扩容也不太方便。因此，我建立了一个简单的动态字符串。（simple dynamic String）抽象数据类型。
- sdshdr : 表示SDS 有五种类型。每种类型的数字表示 unit
- alloc：未使用的空间， 这里为0
- len：表示这个 SDS 保存了5 单位字符串
- buf：char类型的数组用于保存字符
SDS 位于 src/sds.h 和 src/sds.c 在中间，有五种结构（redis 6.0.6）
/* Note: sdshdr5 is never used, we just access the flags byte directly. * However is here to document the layout of type 5 SDS strings. */struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[];};struct __attribute__ ((__packed__)) sdshdr8 { ////保存字符串的长度 uint8_t len; /* used */ 除了头部和末尾的\0，剩余字节数 uint8_t alloc; /* excluding the header and null terminator */ //只有一个字节，前五名没有使用，后三位表示头部类型(sdshdr5\16\32\64) unsigned char flags; /* 3 lsb of type, 5 unused bits */ ////用于保存字符串的元素 char buf[];};struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[];};struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[];};struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[];};SDS 能以O(1) 获得字符串长度的复杂性：SDS 有 len 属性，而 C 字符串没有
SDS 可防止缓冲区溢出 ：
- 缓存区溢出：例如，在进行拼接操作之前，程序需要通过内存重新分配来扩大底层数组的空间大小——忘记缓冲区溢出
- SDS 记录自己的长度，因此在操作过程中会进行相应的空间扩展和修改，缓冲区不会溢出
SDS 可以减少修改字符串时的内存重分配次数 ：
- 空间预分配：当扩展字符串时，扩展的内存比实际需要的更多，从而减少连续执行字符串增长操作所需的内存重分配次数。
- 惰性空间释放：当字符串缩短时，程序不会立即使用内存重新分配来恢复缩短后多余的字节，而是使用
alloc将这些字节记录下来，等待将来使用。
SDS 实现二进制安全：
- C 字符串中的字符必须符合编码格式，除末尾外，中间不得包含空字符，否则将被误认为是空字符串的末尾。这将使 C 字符串只能保存文本数据，而不能保存图片、视频和其他二进制数据
- SDS 的
buf属性可以存储多种二进制数据len判断字符串是否结束，以判断字符串的长度
SDS 兼容部分 C 字符串函数：
- 遵循每个字符串都是以空字符串结束的惯例，可以重用 C 语言库
<string.h>函数的一部分
- 遵循每个字符串都是以空字符串结束的惯例，可以重用 C 语言库
Redis 以哈希表为底层实现的字典，代码位于 src/dict.h
2.1 2.1字典的实现.1 哈希表的结构定义typedef struct dictht { ///哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码，用于计算索引值 unsigned long sizemask; ///表示哈希表现有节点的数量 unsigned long used;} dictht;图为4大小的空哈希表：
table 属性：它是一个数组，数组的每个元素都指向 dictEntry 每一个结构指针 dictEntry 所有的结构都保留了一个键值对。其结构如下：
typedef struct dictEntry { ///键key void *key; ///值value，它可以是指针，int64、double 等类型 union { void *val; uint64_t u64; int64_t s64; double d; } v; //指向下一个 dictEntry 的指针，拉链法解决了哈希冲突 struct dictEntry *next;} dictEntry;size 属性：记录哈希表的大小
sizemask 属性：总是等于 size - 1
used 属性:记录哈希表现有节点(键值对)的数量
Redis 字典代码在中间 src/dict.h 中
typedef struct dict { //指向 dictType 结构的指针 dictType *type; //私有数据 void *privdata; //哈希表 dictht ht[2]; ///索引，当 rehash 不进行是的，值为 01 long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */} dict;一个没有进行 rehash 的字典
type 属性：指向 dictType 每一个结构指针 dictType 该结构保存了一簇函数，用于操作特定类型的键对
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;privdata 属性：保存需要传递给特定类型函数的可选参数
ht 属性：数组包含两个项，数组中的每个项都是一个项 dictht 哈希表。一般来说，字典只使用 ht[0] 哈希表，ht[1] 哈希表在对 ht[0] 哈希表进行 rehash 时使用。
rehashidx 属性：如果没有 rehash，它的值为 -1。
Redis 计算哈希值和索引值的方法如下：
# 使用字典设置的哈希函数，计算键key的哈希值hash = dict->type->hashFunction(key);# 使用哈希表 sizemask 计算索引值和哈希值（h[x] 指的是 ht[0] 或者 ht[1]）index = hash & dict->ht[x].sizemask;这里的 hashFunction(key)是使用 MurmurHash 算法计算键的哈希值，这个算法的一点是，即使输入键有规律，算法仍然可以给出良好的随机分布。算法的计算速度也很快。
前面提到的，Redis 哈希冲突是通过拉链解决的，每个哈希表节点都有一个 next 可以使用多个哈希表节点 next 该指针构成了解决哈希键冲突问题的单向链表。代码在 src/dict.c/dictAddRaw 中
dictEntry *dictAddRaw(dict *d, void *key){ int index; dictEntry *entry; dictht *ht; if (dictIsRehashing(d)) _dictRehashStep(d); // 1、执行rehash //如果索引等于 -1 表明字典中已经存在相同的字典 key if ((index = _dictKeyIndex(d, key)) == -1) // 2、索引定位 return NULL; ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 3、根据是否 rehash ，选择哈希表 entry = zmalloc(sizeof(*entry)); // 4、分配内存空间，执行插入 entry->next = ht->table[index]; ht->table[index] = entry; ht->used++; dictSetKey(d, entry, key); // 5、设置键 return entry;}其中 函数是哈希算法的具体代码_dictKeyIndex()中
static int _dictKeyIndex(dict *d, const void *key){ unsigned int h, idx, table; dictEntry *he; if (_dictExpandIfNeeded(d) == DICT_ERR) // 1、rehash 判断 return -1; h = dictHashKey(d, key); // 2、计算哈希值的哈希函数 for (table = 0; table <= 1; table++) { idx = h & d->ht[table].sizemask; // 3、计算索引值的哈希算法 he = d->ht[table].table[idx]; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) // 4、搜索键是否已经存在 return -1; he = he->next; } if (!dictIsRehashing(d)) break; // 5、rehash 判断 } return idx;}同 Java 中的 HashMap 与底层数据结构相同，哈希表存储的键值会增加或减少，在 Redis 通过执行 rehash(重新散列) 为了完成表的扩展和收缩。也就是说，保持哈希表中的负载因子在合理范围内。这里的负载因子是：load_factor = ht[0].used / ht[0].size
扩展：1.服务器正在执行中 BGSAVE 或者 BGREWRITEAOF 哈希表的负载因子大于或等于 5 时间；2.服务器尚未执行 BGSAVE 或者 BGREWRITEAOF 哈希表的负载因子大于或等于1时，为 ht[1] 分配空间大于原来的大小 ht[0] 两倍的2次幂
从ht[0] 的值移动到 ht[1] 需要重新计算原始 ht[0] 中元素的哈希值和索引；插入ht[1] 插入一个删除一个
ht[0] 所有元素迁移后，释放 ht[0]，新建的 ht[1] 设置为 ht[0] ，调用的是 dict.c/_dictExpandIfNeeded 函数：
static int _dictExpandIfNeeded(dict *d){ if (dictIsRehashing(d)) return DICT_OK; if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); // 初始哈希表的大小为0，需要设置为4 if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) // 负载因子超过5，执行 dictExpand { return dictExpand(d, d->ht[0].used*2); } return DICT_OK;}
收缩：当哈希表的负载因子小于 0.1 当哈希表被收缩时，它也将被分配 ht大小等于[1]
max(ht[0].used, DICT_HT_INTIAL_SIZE)。还需要迁移元素，具体操作和扩展相同
需要扩展或收缩哈希表 ht[0]键值对 rehash 到 ht[1] 中间。因为当键值对数量很大时，如果是一次性的、集中的，就会完成很多 rehash 动作很可能导致服务器停机。因此，需要渐进式 rehash 完成。渐进式 rehash 步骤如下：
为 ht[1] 在字典中，分配空间 rehashidx 变量设置为 0.这一步代码在 dict.c/dictExpand 中实现
int dictExpand(dict *d, unsigned long size){ dictht n; unsigned long realsize = _dictNextPower(size); // 找到比size大的最小2的幂 if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR; if (realsize == d->ht[0].size) return DICT_ERR; n.size = realsize; // 分配ht[1] realsize 的空间 n.sizemask = realsize-1; n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; if (d->ht[0].table == NULL) { // 处于初始化阶段 d->ht[0] = n; return DICT_OK; } d->ht[1] = n; d->rehashidx = 0; // rehashidx 设置为0，开始渐进式 rehash return DICT_OK;}在 rehash 对字典进行中对 CRUD 在操作过程中，除了这些制定的操作外。顺便说一句，它也将是 ht[0] 所有键值对被 rehash 到 ht[1] 中。 rehash 完成后，将会 rehashidx 属性值加1。
- rehash 时的 CRUD 操作将在两个哈希表中进行，例如在两个表中找到，并在两个表中添加元素 ht[1] 中添加
当 ht[0] 所有键值都是对的 rehash 到 ht[1] 后，将 rehashidx 属性值设为 -1，rehash 操作完成。
从本文的开头图可以看出，压缩列表(ZipList)它是列表键和哈希键的底层实现原理。它是为了节省内存而开发的。当列表中只含有少量元素或内部元素为小整数、短字符串时， Redis 就会使用 ZipList 实现列表键的底层。
3.1 压缩列表的组成压缩列表是由一系列特殊编码的连续内存块组成的顺序数据结构。压缩列表可以包含多个节点，相应的数据类型（字节数组或整数值）可以保存在每个节点中。如下图所示
zlbytesuint32_t4 记录整个压缩列表中占用的内存字节数：重新分配压缩列表中的内存， 或者计算 zlend 使用它的位置。zltailuint32_t4 压缩列表末节点与压缩列表的起始地址之间的字节记录： 表尾节点的地址可以通过这种偏移来确定，程序无需遍历整个压缩列表。zllenuint16_t2 压缩列表中包含的节点数量记录字节： 当该属性值小于时 UINT16_MAX （65535）时， 该属性的值是压缩列表中包含节点的数量； 当这个值等于 UINT16_MAX 时， 只有遍历整个压缩列表，才能计算出节点的真实数量。entryX列表节点不定压缩列表中包含的每个节点的长度取决于节点保存的内容。zlenduint8_t1 字节特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端如图为压缩列表实例：
- zlbytes 属性值为 0xd2(十进制 210) ,表示压缩列表的总长度 210 字节
- zltail 属性值为 0xb3(十进制 179)表示起始指针p 最后指针的偏移量是指针的偏移量 179
- zilen 属性值为 0x5(十进制 5)表示压缩列表包含五个 entry 节点
- entry1~entry5 :表示每个列表
- zlend 属性值表示压缩列表末端的属性值
每个压缩列表节点可以保存一个字节数组或一个整数值。其节点由字节数组组组成。 previous_entry_length、encoding、content 三个属性组成如下图所示：
previous_entry_length 属性: 以字节为单位，记录压缩列表中前一个字节的长度。
- 如果前一个字节的长度小于 254 字节，则 previous_entry_length 的值为 1 字节
- 如果前一个字节的长度大于或等于 254 字节，则 previous_entry_length 5字节值：该属性的第一个字节设置为 254，以下四个字节用于存储超过 1 字节的剩余长度。
encoding 属性：记录节点 content 属性保存的数据的类型和长度
1字节、2字节或5字节，最高值为00、01或10是字节数组编码：该编码表示节点 content 字节数组保存在属性中。
编码 编码长度 content属性保存值00bbbbbbbb1字节长度小于或等于63字节字节数组。01bbbbbbbbb xxxxxxxx2字节长度小于或等于16383字节字节数组。______________ aaaaaaaa bbbbbbbb cccccccc dddddddd5字节长度小于或等于4294967295字节数组。1字节，最高值以11开头的整数编码：整数值的类型和长度由编码除去最高两位后的其他位记录。
编码 编码长度 content属性保存值110000001字节int16_t类型的整数。110100001字节int32_t类型的整数。111000001字节int64_t类型的整数。111100001字节24位有符号整数。111111101字节8位置上有符号整数。1111xxxx1使用这个编码的节点没有相应的字节content属性， 因为编码本身xxxx四个位置中的一个已经保存了0和12之间的值， 所以它无须content属性。
content 属性:节点值可以是字节数组或整数，节点值的类型和长度可以由节点保存 encoding 属性决定。
以保存整数节点为例：
- encoding 是 11 开头说整数类型是存储的
- content 表示节点保存值为 10086
- 相对于普通的 list 而言，增加 encoding 选择性地存储字节和整数类型
- 有了 previous_entry_length 属性，遍历元素可以定位到下一个元素的精确位置，以降低搜索时间的复杂性
作为有序列表，跳表是一种有序的数据结构（Zset）使用。而且比平衡树更优雅，在 CRUD 可在对数期望时间内完成等操作。
如上图所示，这是一个跳跃表的例子，最左边是 zskiplist 结构中包含的属性包括：
- header属性:指向跳跃表的表头节点
- tail属性:指向跳跃表的表尾节点
- level属性：记录跳跃表中最大节点的层数
- length属性：记录跳跃表的长度，即目前包含节点的跳跃表数量
右边的四个是 zskiplistNode 结构中包含的属性包括：
- level属性：L1用于节点、L2、L3等字样标记节点各层
- backward属性：节点中使用 BW字样标记节点的后退指针，指向当前结点的前一个节点
- score属性:节点中保存的1.0、2.0等等分值
- obj属性：节点中的obj属性 o1、o2等是节点保存的成员对象
比如开始介绍的图片，zskiplist 结构代码在 redis.h/zskiplist 其定义如下：
typedef struct zskiplist { ///表头节点和表尾节点 structz skiplistNode *header, *tail; //表中节点的数量 unsigned long length; ///表中层数最大节点的层数 int level;} zskiplist;其中 zskiplistNode 该结构用于表示跳跃表节点，代码在 redis.h/zskiplistNode 中。
/* ZSETs use a specialized version of Skiplists */typedef struct zskiplistNode { //对象属性，指向字符串对象 sds ele; //分值 double score; //后退指针 struct zskiplistNode *backward; //层level struct zskiplistLevel { ///前进指针 struct zskiplistNode *forward; //跨度 unsigned int span; } level[];} zskiplistNode;level 属性：level 层中可以包含多个元素。层数越多，访问其他节点的速度就越快。程序通过幂次定律（power law, 数字越大，出现的概率就越小。随机生成一个介于1和32之间的值作为值 level 作为层高的数组大小：下图显示了不同层高的节点
向前和向后指针（
*forward和* backforward）：访问遍历跳跃表中所有节点的路径
span跨度属性：层跨度用于记录两个节点之间的距离：如上图所示，箭头上的数字表示节点之间的距离
**分值和成员（score 、sds ele）**：
- 分值是一个 double 跳跃表中的所有节点都按分数从小到大排序
- 成员对象(如o1、o2等)，它是一个指针，指向一个字符串对象，它保存了一个SDS 值
- 在同一个跳跃表中，每个节点保存的成员对象必须是唯一的，分数可以相同。成员对象小的会排在前面(表头)、会员对象较大的节点会排在后面(表尾)。还是这张图，图中 o1、O2和O3三个节点都保存了相同的整数值 10086.0。但成员对象的排名却是 o1->o2->o3
当一个集合中只有整数值元素，且集合中的元素数量较少时，Redis将使用整数集合作为集合键的底层
5.1 定义整数集合结构intset int16___可以保存的类型t、int32_t或int64_t的整数值，并确保集合中不会出现重复元素。其结构代码在 intset.h/intset 以32为例：
typedef struct intset { //编码方法 uint32_t encoding; ////集合中包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[];} intset;以具体的整数集合为例：
- encoding属性值 INTSET_ENC_INT16 :表示 contents 数组是一个 16 位的数组
- length属性值为5，表示contents 数组中含有五个元素
- contents 数组表示，这个数组从小到大储存五个元素
新元素的类型比现有类型要长，比如16位变成32位，在整数集合中称为升级（upgrade）。升级后，新元素可以添加到整数集合中，升级整数集合并添加新元素的步骤如下：
- 根据新元素的类型，扩大底层数组的空间大小，为新元素分配空间
- 将底层数组中现有的所有元素转换为与新元素相同的类型，并将转换后的元素放置在正确的位置。
- 在contents数组中添加新元素
集合不会降级。例如，在原16位数组中添加32位元素，然后删除新元素后，整数集合不会降级。
六、快速链表（QuickList）quicklist 一种以结构 ziplist 对于节点的双端链表结构，整体上是链表，但链表中的每个节点都是链表 ziplist.
其代码结构为src//quicklist.h 中
让我们来看看quicklistnodede 节点结构：
typedef struct quicklistNode { ///上一个quicklistnode节点 struct quicklistNode *prev; ///下一个quicklistnode节点 struct quicklistNode *next; //数据指针， unsigned char *zl; //表示zl指向 ziplist 的总大小 unsigned int sz; /* ziplist size in bytes */ ///表示ziplist中包含的数据项数 unsigned int count : 16; /* count of items in ziplist */ //ziplist是否被压缩，1没有，2被压缩 unsigned int encoding : 2; /* RAW==1 or LZF==2 */ //预留字段，目前是固定值，表示使用 ziplist 作为数据容器 unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */ ///需要暂时解压数据，此时设置 recompress = 1,有机会再次压缩数据 unsigned int recompress : 1; /* was this node previous compressed? */ //Redis 在自动化测试中使用 unsigned int attempted_compress : 1; /* node can't compress; too small */ //扩展字段，目前还没有使用 unsigned int extra : 10; /* more bits to steal for future usage */} quicklistNode;再来看看 quicklistLZF 结构表示压缩过的结构 ziplist，其结构如下：
typedef struct quicklistLZF { //压缩后 ziplist 的大小 unsigned int sz; /* LZF size in bytes*/ //柔性数组，储存压缩后 ziplist 字节数组 char compressed[];} quicklistLZF;再看最后一个 quicklist 结构
typedef struct quicklist { //指向头节点（quicklistnode 头节点） quicklistNode *head; ///指向尾节点(最右节点) quicklistNode *tail; //所有ziplistt所有ziplist 的数量 unsigned long count; /* total count of all entries in all ziplists */ //quicklist节点的个数 unsigned long len; /* number of quicklistNodes */ //设置ziplistt设置 的大小，存放 list-max-ziplist-size 参数的值 int fill : QL_FILL_BITS; /* fill factor for inpidual nodes */ ///设置节点压缩深度，存放 list-comress-depth 参数值为0时关闭 unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */ //尾部增加的书签只能忽略大量节点多余内存的使用，分批迭代后，不使用时不会增加内存费用 unsigned int bookmark_count: QL_BM_BITS; quicklistBookmark bookmarks[];} quicklist;- 可选择插入头部或尾部：
- ziplist的大小没有超过限制，新数据直接插入 ziplist 中
- 如果ziplist超过限制，新创建一个 quicklistNode 将新节点插入节点 quicklist 双向链表中
- 插入中间位置：
- 需要把当前 ziplist 将数据分成两个节点，然后将数据插入其中一个节点
根据node 找到对应的个数 ziplist,然后再调用 ziplist 的 index 能成功找到
6.2.3 删除操作利用 quicklistDelRange 函数：返回1表示成功删除指定区间元素，返回0表示未删除任何元素
删除区间时，会先找到 start 所在的 quicklistNode ，计算删除的元素是否小于删除的元素 count，如果删除的数量不符合要求，则移动到下一个 quicklistNode 继续删除，依次循环，直到删除完成。
参考资料：《Redis 设计与实现》
《Redis “开发与运维”
Redis数据结构-快速列表(quicklist)
https://pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html
湘公网安备43019002002060