动态字符串SDS(simple dynamic string )

我们都知道Redis中保存的Key是字符串，value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。

不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

// c语言，声明字符串
char* s = "hello"
// 本质是字符数组： {'h', 'e', 'l', 'l', 'o', '\0'}

对于上述存储方式而言：

• 获取字符串的长度需要通过运算（strlen()）
• 非二进制安全 字符串的结尾是以 “\0” 字符标识，字符串⾥⾯不能包含有 “\0” 字符，因此不能保存⼆进制数据
• 不可修改

因此直接使用C语言中的字符串对于 Redis 而言是有缺陷的。

SDS结构定义

Redis 是⽤ C 语⾔实现的，但是它没有直接使⽤ C 语⾔的 char* 字符数组来实现字符串，⽽是⾃⼰封装了⼀个名为简单动态字符串（simple dynamic string SDS） 的数据结构来表示字符串，也就是 Redis 的String 数据类型的底层数据结构是 SDS

就本质而言，SDS是一个结构体，源码定义如下：

struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; //buf已保存的字符串字节数，不包含结束标示\0uint8_t alloc; //buf申请的总的字节数，不包含结束标示\0unsigned char flags; //不同SDS的头类型，用来控制SDS的头大小char buf[]; //存储的字符串内容
};	

可见 SDS的构成是由头部信息（len alloc flags） ＋ 真实string数据 构成的
例如：一个包含字符串“name”的SDS结构如下：

针对上面的定义，你是否有诸多疑问？如果没有，那么请看接下来的问题你是否清楚；如果有，那么我相信通过下面的问题能够帮你解惑：

Q1：既然len 表示已保存字符串的字节数，那根据上面给出的SDS源码定义，uint8_t表示的最大值为255，且不包含\0,这意味着真实有效字符串长度最大只能是254，但是Redis 中设置key对应的value时长度可能会超过254，这怎么解决？

A1：结论：Redis中提供了多种SDS存储方案，通过设置flags可以选择合适的存储结构，具体如下
flags可选择的值：

• #define SDS_TYPE_8 1 1yte
• #define SDS_TYPE_16 2 2byte
• #define SDS_TYPE_32 3 4byte
• #define SDS_TYPE_64 4 8byte

通过对flags的设置，相应地，SDS结构中的 len alloc 字段的类型也会与之变化。例如，flags设置为 SDS_TYPE_16,此时len 和alloc 的类型就为uint16_t，这样可保存的字符串长度就足够了

Q2：一个SDS为什么要设置这么多不同大小的结构，直接使用SDS_TYPE_64不就能存储所有string类型的value了？

A2：结论：理论上是可以的，但是如果使用SDS_TYPE_64，意味着SDS头部信息中的len 和 alloc 两个字段各占8byte，并且日常使用set key value 时 value的长度绝大多数不会超过254byte，因此使用SDS_TYPE_8就可以满足大部分需求，相比之下，使用SDS_TYPE_64就会造成大量的内存资源浪费

Q3：C中的字符串定义不是二进制安全的，那SDS中是如何保证二进制安全的？

A3：SDS头部信息中记录了字符串的真实长度（len）以及buf的容量（alloc）,因此在SDS这种结构下，字符串取多长，字符串中是否由特殊字符（如\0）这些内容都不需要关心，只需要根据字符串的起始地址 + 字符串长度即可获取其值，因此是二进制安全的。至于数据部分最后的\0是为了兼容C语言而存在的

SDS动态扩容

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力。
例如一个内容为“hi”的SDS：

假如我们要给SDS追加一段字符串,Amy，这里首先会申请新内存空间:

• 如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；
• 如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

最终，扩容后的结果如下所示：

SDS的优点：

1. 获取字符串长度的时间复杂度为O(1)
2. 支持动态扩容
3. 减少内存分配次数
4. 二进制安全

IntSet

IntSet 结构定义

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征

结构定义如下：

typedef struct intset {uint32_t encoding; //编码方式，支持存放16位、32位、64位整数uint32_t length; //元素个数int8_t contents[]; //整数数组，保存集合数据
} intset;其中的encoding包含三种模式，表示存储的整数大小不同：
/* Note that these encodings are ordered, so:* INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t)) //2字节整数
#define INTSET_ENC_INT32 (sizeof(int32_t)) //4字节整数
#define INTSET_ENC_INT64 (sizeof(int64_t)) //8字节整数

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为:

• encoding：4字节
• length：4字节
• contents：2字节 * 3 = 6字节

从上述contents 大小的计算以及 contents 的 类型 int8_t contents[] 可以看出，IntSet中contents是指向数组首地址的指针，仅仅是记录数据首元素地址，而访问数组中的每一个元素时的步长是由encoding来决定的。

上述例子中encoding的值为INTSET_ENC_INT16，因此寻址步长为2byte，也即数组每个元素的大小为2byte，因此contents中存储的元素占用6byte

IntSet的升级

现在，假设有一个intset，元素为{5,10，20}，采用的编码是INTSET_ENC_INT16，则每个整数占2字节：

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，因此intset会自动升级编码方式到合适的大小。

具体流程如下：

1. 升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
2. 倒序依次将数组中的元素拷贝到扩容后的正确位置
   
3. 插入新元素
   
4. 将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4
   

关键源码解读

IntSet新增流程

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {// 获取当前值编码uint8_t valenc = _intsetValueEncoding(value);// 要插入的位置uint32_t pos; if (success) *success = 1;// 判断编码是不是超过了当前intset的编码if (valenc > intrev32ifbe(is->encoding)) {// 超出编码，需要升级return intsetUpgradeAndAdd(is,value);} else {// 在当前intset中查找值与value一样的元素的角标posif (intsetSearch(is,value,&pos)) {//如果找到了，则无需插入，直接结束并返回失败if (success) *success = 0; return is;}// 数组扩容is = intsetResize(is,intrev32ifbe(is->length)+1);// 移动数组中pos之后的元素到pos+1，给新元素腾出空间if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);}// 插入新元素_intsetSet(is,pos,value);// 重置元素长度is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

IntSet升级流程

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {// 获取当前intset编码uint8_t curenc = intrev32ifbe(is->encoding);// 获取新编码uint8_t newenc = _intsetValueEncoding(value);// 获取元素个数int length = intrev32ifbe(is->length); // 判断新元素是大于0还是小于0 ，小于0插入队首、大于0插入队尾int prepend = value < 0 ? 1 : 0;// 重置编码为新编码is->encoding = intrev32ifbe(newenc);// 重置数组大小is = intsetResize(is,intrev32ifbe(is->length)+1);// 倒序遍历，逐个搬运元素到新的位置，_intsetGetEncoded按照旧编码方式查找旧元素while(length--) // _intsetSet按照新编码方式插入新元素_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));/* 插入新元素，prepend决定是队首还是队尾*/if (prepend)_intsetSet(is,0,value);else_intsetSet(is,intrev32ifbe(is->length),value);// 修改数组长度is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

总结：

1. Redis会确保Intset中的元素唯一、有序
2. 具备类型升级机制，可以节省内存空间
3. 底层采用二分查找方式来查询

Dict

Dict结构定义

我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

我们先来了解一下 哈希表 和 哈希节点 的源码定义：

// 哈希表 DictHashTable
typedef struct dictht {// 指针数组，数组中的每一个元素是一个指向entry的指针dictEntry **table; // 哈希表大小unsigned long size;     // 哈希表大小的掩码，总等于size - 1unsigned long sizemask;     // entry个数unsigned long used; 
} dictht;// 哈希节点 DictEntry
typedef struct dictEntry {void *key; // 键union {void *val;uint64_t u64;int64_t s64;double d;} v; // 值// 下一个Entry的指针，用于解决哈希冲突struct dictEntry *next; 
} dictEntry;

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。

例如：我们存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置

这里 的 3 是sizemark的值，因为Dict在初始化的时候size最小是4

假设此时来了一组新的k-v，为k2 = v2, 并且经过运算，k2的hash值得到的角标也是1，此时就会产生哈希冲突，解决该冲突使用链地址法，且采用头插的方式，具体如下：

到这里，哈希表 和 哈希节点 的相关内容告一段落，我们接下来研究一下这个字典Dict的源码

// 字典Dict
typedef struct dict {dictType *type; // dict类型，内置不同的hash函数void *privdata;     // 私有数据，在做特殊hash运算时用// 一个Dict包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash时使用dictht ht[2]; long rehashidx;   // rehash的进度，-1表示未进行int16_t pauserehash; // rehash是否暂停，1则暂停，0则继续
} dict;

鉴于此，将上述的例子稍作更改，假设k1最终得到的角标是1， k2最终得到的角标是2，那么最终的组织结构应如下所示：

Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

1. 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程
2. 哈希表的 LoadFactor > 5

具体的源码如下：

static int _dictExpandIfNeeded(dict *d){// 如果正在rehash，则返回okif (dictIsRehashing(d)) return DICT_OK;    // 如果哈希表为空，则初始化哈希表为默认大小：4if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);// 当负载因子（used/size）达到1以上，并且当前没有进行bgrewrite等子进程操作// 或者负载因子超过5，则进行 dictExpand ，也就是扩容if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio){// 扩容大小为used + 1，底层会对扩容大小做判断，实际上找的是第一个大于等于 used+1 的 2^nreturn dictExpand(d, d->ht[0].used + 1);}return DICT_OK;
}

Dict的收缩

Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor < 0.1 时，会做哈希表收缩。
核心源码逻辑如下：

// t_hash.c # hashTypeDeleted() 
...
if (dictDelete((dict*)o->ptr, field) == C_OK) {deleted = 1;// 删除成功后，检查是否需要重置Dict大小，如果需要则调用dictResize重置if (htNeedsResize(o->ptr)) dictResize(o->ptr);
}
...// server.c 文件
int htNeedsResize(dict *dict) {long long size, used;// 哈希表大小size = dictSlots(dict);// entry数量used = dictSize(dict);// size > 4（哈希表初识大小）并且 负载因子低于0.1return (size > DICT_HT_INITIAL_SIZE && (used*100/size < HASHTABLE_MIN_FILL));
}int dictResize(dict *d){unsigned long minimal;// 如果正在做bgsave或bgrewriteof或rehash，则返回错误if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;// 获取used，也就是entry个数minimal = d->ht[0].used;// 如果used小于4，则重置为4if (minimal < DICT_HT_INITIAL_SIZE)minimal = DICT_HT_INITIAL_SIZE;// 重置大小为minimal，其实是第一个大于等于minimal的2^nreturn dictExpand(d, minimal);
}

Dict 的rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。过程是这样的：

1. 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
   ①如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
   ②如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）
2. 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
3. 设置dict.rehashidx = 0，标示开始rehash
4. 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
5. 释放原来的dict.ht[0]的内存，并将dict.ht[1]赋值给dict.ht[0]，同时把dict.ht[1]初始化为空哈希表

下面通过一个例子来说明上述的流程：

初始阶段，有一个Dict, 哈希表ht[0]中右4个有效元素，ht[1] 为null

此时需要插入一个新的键值对<k5,v5>，由于ht[0]中的有效元素已经为4，此时再插入ht[0]的时候负载因子一定会大于1，假设此时服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程，那么就会触发 Dict的扩容操作

接下来 就进入迁移流程

最后，做ht[0] 与 ht[1] 的交接工作

至此流程完毕

Q：上述的步骤4是否可以一次性将所有元素做rehash？
A：Dict的rehash并不是一次性完成的。试想一下，如果Dict中包含数百万的entry，要在一次rehash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash
因此，rehash的最终完整流程应该是：

1. 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
   ①如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
   ②如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）
2. 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
3. 设置dict.rehashidx = 0，标示开始rehash
4. 每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]
5. 释放原来的dict.ht[0]的内存，并将dict.ht[1]赋值给dict.ht[0]，同时把dict.ht[1]初始化为空哈希表
6. 将rehashidx赋值为-1，代表rehash结束
7. 在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

总结：

Dict的结构：

• Dict底层是数组加链表来解决哈希冲突
• Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash

Dict的伸缩：

• 当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容
• 当LoadFactor小于0.1时，Dict收缩
• 扩容大小为第一个大于等于used + 1的2^n
• 收缩大小为第一个大于等于used 的2^n
• Dict采用渐进式rehash，每次访问Dict时执行一次rehash
• rehash时ht[0]只减不增，新增操作只在ht[1]执行，其它操作在两个哈希表

ZipList

ZipList 是一种特殊的“双端链表”(具有双端链表的特性但不是链表结构) ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)

关于ZIP List的组成字段介绍如下：

ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：

1. previous_entry_length：前一节点的长度，占1个或5个字节
   ①如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
   ②如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
2. encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
3. contents：负责保存节点的数据，可以是字符串或整数

ZipList中所有存储长度的数值均采用小端字节序

encoding 编码

ipListEntry中的encoding编码分为字符串和整数两种：

字符串

如果encoding是以00、01或者10开头，则证明content是字符串

例如，我们要保存字符串：ab和 bc

整数

如果encoding是以11开始，则证明content是整数，且encoding固定只占用1个字节

例如，一个ZipList中包含两个整数值：2和5

ZipList的连锁更新问题

ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节

• 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
• 如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

现在，假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如图所示：

假设现在需要插入一个大小为254byte的entry：

那么此时该entry的后一个节点中记录前一节点长度的变量pre_entry_len就不能用一个字节，而是要用5个字节来记录，同理，后续的每一个entry的pre_entry_len都需要用5个字节记录，因为他们的前一个entry大小都大于等于254字节了。

这种现象就被称为 ZipList的连锁更新

总结一下：ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。

ZipList特性：

• 压缩列表的可以看做一种连续内存空间的"双向链表"
• 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
• 如果列表数据过多，导致链表过长，可能影响查询性能
• 增或删较大数据时有可能发生连续更新问题

QuickList

Q1：ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？
A1：为了缓解这个问题，我们必须限制ZipList的长度和entry大小。

Q2：但是我们要存储大量数据，超出了ZipList最佳的上限该怎么办？
A2：我们可以创建多个ZipList来分片存储数据。

Q3：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？
A3：Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。

了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制

• 如果值为正，则代表ZipList的允许的entry个数的最大值
• 如果值为负，则代表ZipList的最大内存大小，分5种情况
  ①-1：每个ZipList的内存占用不能超过4kb
  ②-2：每个ZipList的内存占用不能超过8kb
  ③-3：每个ZipList的内存占用不能超过16kb
  ④-4：每个ZipList的内存占用不能超过32kb
  ⑤-5：每个ZipList的内存占用不能超过64kb

其默认值为 -2

除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数。

• 0：特殊值，代表不压缩
• 1：标示QuickList的首尾各有1个节点不压缩，中间节点压缩
• 2：标示QuickList的首尾各有2个节点不压缩，中间节点压缩（以此类推）

默认值：

QuickList源码

typedef struct quicklist {// 头节点指针quicklistNode *head; // 尾节点指针quicklistNode *tail; // 所有ziplist的entry的数量unsigned long count;    // ziplists总数量unsigned long len;// ziplist的entry上限，默认值 -2 int fill : QL_FILL_BITS;// 首尾不压缩的节点数量unsigned int compress : QL_COMP_BITS;// 内存重分配时的书签数量及数组，一般用不到unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[];
} quicklist;typedef struct quicklistNode {// 前一个节点指针struct quicklistNode *prev;// 下一个节点指针struct quicklistNode *next;// 当前节点的ZipList指针unsigned char *zl;// 当前节点的ZipList的字节大小unsigned int sz;// 当前节点的ZipList的entry个数unsigned int count : 16;  // 编码方式：1，ZipList; 2，lzf压缩模式unsigned int encoding : 2;// 数据容器类型（预留）：1，其它；2，ZipListunsigned int container : 2;// 是否被解压缩。1：则说明被解压了，将来要重新压缩unsigned int recompress : 1;unsigned int attempted_compress : 1; //测试用unsigned int extra : 10; /*预留字段*/
} quicklistNode;

结构示意图：

QuickList的特点：

• 是一个节点为ZipList的双端链表
• 节点采用ZipList，解决了传统链表的内存占用问题
• 控制了ZipList大小，解决连续内存空间申请效率问题
• 中间节点可以压缩，进一步节省了内存

SkipList

kipList（跳表）首先是链表，但与传统链表相比有几点差异

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同。

跳表 的数据结构

// t_zset.c
typedef struct zskiplist {// 头尾节点指针struct zskiplistNode *header, *tail;// 节点数量unsigned long length;// 最大的索引层级，默认是1int level;
} zskiplist;// t_zset.c
typedef struct zskiplistNode {sds ele; // 节点存储的值double score;// 节点分数，排序、查找用struct zskiplistNode *backward; // 前一个节点指针struct zskiplistLevel {struct zskiplistNode *forward; // 下一个节点指针unsigned long span; // 索引跨度} level[]; // 多级索引数组
} zskiplistNode;

SkipList的特点：

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象，源码如下：

Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：

Redis中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

五种数据类型

String

String是Redis中最常见的数据存储类型：

• 其基本编码方式是 RAW，基于简单动态字符串SDS实现，存储上限为512MB。
• 如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。
• 如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

下面给出不同编码方式下的string 图解：
RAW

EMBSTR

INT

List

Redis的List类型可以从首、尾操作列表中的元素

在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码。

在3.2版本之后，Redis统一采用QuickList来实现List

//创建 quicklist obj
robj *createQuicklistObject(void) {// 申请内存并初始化QuickListquicklist *l = quicklistCreate();// 创建RedisObject，type为OBJ_LIST// ptr指向 QuickListrobj *o = createObject(OBJ_LIST,l);// 设置编码为 QuickListo->encoding = OBJ_ENCODING_QUICKLIST;return o;
}void pushGenericCommand(client *c, int where, int xx) {int j;// 尝试找到KEY对应的listrobj *lobj = lookupKeyWrite(c->db, c->argv[1]);// 检查类型是否正确if (checkType(c,lobj,OBJ_LIST)) return;// 检查是否为空if (!lobj) {if (xx) {addReply(c, shared.czero);return;}// 为空，则创建新的QuickListlobj = createQuicklistObject();quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,server.list_compress_depth);dbAdd(c->db,c->argv[1],lobj);}// 略 ...
}

list 的数据组织格式示意图：

Set

Set是Redis中的单列集合，满足下列特点：

• 不保证有序性
• 保证元素唯一（常用于判断元素是否存在）
• 求交集、并集、差集
  
  可以看出，Set对查询元素的效率要求非常高，因此：
• 为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null
• 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries(默认值512)时，Set会采用IntSet编码，以节省内存。

创建Set的核心代码：

执行Set的add操作核心代码：

下面通过一个例子说明上述ADD函数的逻辑：

假设初始set中存储了3个整型数据，此时Set采用的编码方式是IntSet

现在 执行 sadd s1 m1
此时根据add的逻辑，需要转换Set的编码方式为HT，因此会创建Dict,并将原来的三个整数存储进去同时存储m1

此时 该Set的编码方式就变成了HT编码

ZSet

ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值，并且需要满足以下要求：

• 可以根据score值排序后
• member必须唯一
• 可以根据member查询分数

因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求

SkipList：可以排序，并且可以同时存储score和ele值（member）,但是SkipList 中 是以score大小做升序排列的，自身无法做到键唯一
HT（Dict）：可以键值存储，并且可以根据key找value，可以通过逻辑限制做到键唯一，但是无法做到可排序

那么。ZSet底层到底是用的是哪种数据结构呢？总的来讲，ZSet底层采用了两套数据结构来存储。分别是 SkipList + DH 组合 以及 ZipList数据结构

SkipList + DH

结构定义

// zset结构
typedef struct zset {// Dict指针dict *dict;// SkipList指针zskiplist *zsl;
} zset;robj *createZsetObject(void) {zset *zs = zmalloc(sizeof(*zs));robj *o;// 创建Dictzs->dict = dictCreate(&zsetDictType,NULL);// 创建SkipListzs->zsl = zslCreate(); o = createObject(OBJ_ZSET,zs);o->encoding = OBJ_ENCODING_SKIPLIST;return o;
}

内存结构图如下所示：

针对上述内存结构图，通过分析我们可以发现：同一份数据ZSet底层由于采用两种数据结构相结合的方式存储数据，导致数据多次存储，出现数据冗余，并且两种存储结构对于内存的开销相对是较大的

当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此ZSet还会采用ZipList结构来节省内存

ZipList

使用ZipList作为ZSet的底层数据结构需要满足以下两个条件：

1. 元素数量小于zset_max_ziplist_entries，默认值128
2. 每个元素都小于zset_max_ziplist_value字节，默认值64

具体源码实现如下：

其中zsetAdd函数中会针对ZSet当前的状态以及添加元素的具体情况 对 ZSet底层的数据结构作出相应的改变

int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {/* 判断编码方式*/// 是ZipList编码if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {unsigned char *eptr;// 判断当前元素是否已经存在，已经存在则更新score即可if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) {//...略return 1;} else if (!xx) {// 元素不存在，需要新增，则判断ziplist长度有没有超、元素的大小有没有超if (zzlLength(zobj->ptr)+1 >server.zset_max_ziplist_entries|| 	sdslen(ele) > server.zset_max_ziplist_value || !ziplistSafeToAdd(zobj->ptr, sdslen(ele))){ // 如果超出，则需要转为SkipList编码zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);} else {zobj->ptr = zzlInsert(zobj->ptr,ele,score);if (newscore) *newscore = score;*out_flags |= ZADD_OUT_ADDED;return 1;}} else {*out_flags |= ZADD_OUT_NOP;return 1;}}    // 本身就是SKIPLIST编码，无需转换if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {// ...略} else {serverPanic("Unknown sorted set encoding");}return 0; /* Never reached. */
}

ZipList本身没有排序功能，而且没有键值对的概念，因此需要由ZSet通过编码实现：

• ZipList是连续内存，因此score和element是紧挨在一起的两个entry， element在前，score在后
• score越小越接近队首，score越大越接近队尾，按照score值升序排列

具体内存结构图如下所示：

Hash

Hash结构与Redis中的Zset非常类似：

• 都是键值存储
• 都需求根据键获取值
• 键必须唯一

区别如下：

• zset的键是member，值是score；hash的键和值都是任意值
• zset要根据score排序；hash则无需排序

因此，Hash底层采用的编码与Zset也基本一致，只需要把排序有关的SkipList去掉即可

Hash结构默认采用ZipList编码，用以节省内存。 ZipList中相邻的两个entry 分别保存field和value。当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：

• ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
• ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）

至此，Redis底层的数据结构以及常见的五种数据类型的底层实现暂时告一段落。接下来我们将进入Redis 网络模型的学习，下篇见！