之前就说了要来西索Redis，现在来辣！
本文的部分内容参考自《小林Coding》，部分地方根据源代码进行剖析。
Redis源码地址：github.com/redis/redis…
数据类型
本文的数据类型只讲底层结构和部分机制，不讲具体的使用，使用的话自行bing，但是会提一些应用场景
string
观其面
kv结构，最大长度512M，底层数据结构为int和sds（简单动态字符串）
- sds可以保存text数据和bin数据 使用len属性的值判断字符串是否结束，所有api都会以二进制形式处理sds存放在buf[]中的数据
- 采用len属性记录字符串长度，复杂度为O(1)
- sds api安全，append不会造成bof
字符串对象的内部encoding有3种
- 如果是整数值，且能用long表示，那么对象会将整数值保存在ptr种，并将void*转会为long，设置encoding为int
- 当类型是string的时候得分两种情况
其实吧，从这里就可以看出Redis对于字符字符串的管理还是挺不错的，你量少？行，那么给你分配连续的空间直接管理，量多？纳闷从新哪一个空间来管理。
好处可想而知：
embstrencoding将创建字符串对象所需的内存分配次数从rawencoding的两次降低为一次；- 释放
embstrencoding的字符串对象同样只需要调用一次内存释放函数； - 因为
embstrencoding的字符串对象的所有数据都保存在一块连续的内存里面可以更好的利用 CPU 缓存提升性能。
但是embstr也有缺点：
- 如果字符串的长度增加需要重新分配内存时，整个redisObject和sds都需要重新分配空间，所以embstr-encoding的字符串对象实际上是只读的，redis没有为embstrencoding的字符串对象编写任何相应的修改程序。当我们对embstrencoding的字符串对象执行任何修改命令（例如append）时，程序会先将对象的encoding从embstr转换成raw，然后再执行修改命令。
应用场景
- 缓存对象
- 计数
- 分布式锁
- 共享Session
这里分布式锁不太建议用string来实现，虽然Redis在1.6之后支持了setnx原子操作，不需要使用Lua脚本，但是任然没有解决可重入性问题，具体的解决方案使用Map，感兴趣的话可以看下我之前的文章：Redis分布式锁深入分析 – Karos (wzl1.top)
究其身
下面是RedisObject数据结构
这里LRU和LFU是啥？补补os吧，上链接：操作系统-超20000字的“总结” – Karos (wzl1.top)
type:4是啥？这里表示对象类型，后面的4是位域（这里还是做下补充吧C 位域 | 菜鸟教程 (runoob.com)）
在说sds之前，我们先来讨论一下C语言字符串的缺点吧：
- 获取字符串长度的时间复杂度为 O（N）；
- 字符串的结尾是以 “ ” 字符标识，字符串里面不能包含有 “ ” 字符，因此不能保存二进制数据；
- 字符串操作函数不高效且不安全，比如有缓冲区溢出的风险，有可能会造成程序运行终止；
前两点，不说，就说最后一个吧，虽然能够接受，还是要解释一下。
在C语言中，对字符串的各个操作都要通过函数进行，并且每个可修改字符串在定义的时候就已经固定了大小（感觉说的有点问题，好久没玩儿C了，一直用的都是C++的string，hhh~）
举个常见的例子，字符串拼接函数
char *strcat(char *dest, const char* src);
如果dest预留的长度小于src的长度，那么很有可能产生overflow，那么Redis的增强我们来看看吧
现在来对sds数据结构仔细说说吧，仔细看其实就是那几个玩意儿：
-
len，记录了字符串长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。
-
alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过
alloc - len计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出的问题。 -
flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在说明区别之处。
-
buf[]，字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。
因为 SDS 不需要用 “ ” 字符来标识字符串结尾了，而是有个专门的 len 成员变量来记录长度，所以可存储包含 “ ” 的数据。但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 “ ” 字符。因此， SDS 的 API 都是以处理二进制的方式来处理 SDS 存放在 buf[] 里的数据，程序不会对其中的数据做任何限制，数据写入的时候时什么样的，它被读取时就是什么样的。通过使用二进制安全的 SDS，而不是 C 字符串，使得 Redis 不仅可以保存文本数据，也可以保存任意格式的二进制数据。
节省空间
SDS 结构中有个 flags 成员变量，表示的是 SDS 类型。
Redis 一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
这 5 种类型的主要区别就在于，它们数据结构中的 len 和 alloc 成员变量的数据类型不同。
为什么这样设计？
主要是为了能灵活保存不同大小的字符串，从而有效节省内存空间。比如，在保存小字符串时，结构头占用空间也比较少。
冷知识，这里还用了
__attribute__ ((packed))取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐来进行优化。
扩容机制
/* Enlarge the free space at the end of the hisds string so that the caller
* is sure that after calling this function can overwrite up to addlen
* bytes after the end of the string, plus one more byte for nul term.
*
* Note: this does not change the *length* of the hisds string as returned
* by hi_sdslen(), but only the free buffer space we have. */
hisds hi_sdsMakeRoomFor(hisds s, size_t addlen) { //传入一个sds的char数组和需要增加的长度
void *sh, *newsh;
size_t avail = hi_sdsavail(s); //获取剩余空间
size_t len, newlen;
char type, oldtype = s[-1] & HI_SDS_TYPE_MASK;
int hdrlen;
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s; //剩余空间足够，无需扩展，直接返回
len = hi_sdslen(s); //获取当前sds长度
sh = (char*)s-hi_sdsHdrSize(oldtype);
newlen = (len+addlen); //计算新的长度
if (newlen < HI_SDS_MAX_PREALLOC) //动态扩容 HI_SDS_MAX_PREALLOC = 1MB
newlen *= 2;
else
newlen += HI_SDS_MAX_PREALLOC;
type = hi_sdsReqType(newlen); //重新获取SDS类型
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so hi_sdsMakeRoomFor() must be called
* at every appending operation. */
if (type == HI_SDS_TYPE_5) type = HI_SDS_TYPE_8; //扩容了，那么按照上文节约空间的原则，这里也要修改空间
hdrlen = hi_sdsHdrSize(type);
if (oldtype==type) {
newsh = hi_s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
newsh = hi_s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
hi_s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
hi_sdssetlen(s, len);
}
hi_sdssetalloc(s, newlen);
return s;
}
List
观其面
一个列表最多放2^{31}-1个（约40亿个）元素，按照插入顺序排序，用起来有一点像可以获取元素的双端队列，hhh~
下面来浅浅的说一下list的底层数据结构吧
其实通过之前对于容器的学习，对吧，比如Java的ArrayList、HashMap，当你的容量到达一部分以后，容器要么扩容，要么改变数据结构，Redis中List同理，那么什么时候改变呢？
Redis-List的改变由两个阙值确定，如下：
- list-max-ziplist-entries：列表元素个数阙值，default：512
- list-max-ziplist-value：列表元素值阙值，default：64
如果列表的元素不满足上面的条件，Redis 会使用双向链表作为 List 类型的底层数据结构，否则，采用压缩列表
冷知识：上面的情况只适用于老版本的Redis，在3.2之后，Redis采用QuickList实现，来代替上面的两种数据结构
应用场景——消息队列
命令没有必要细讲，网上全都是，我们直捣黄龙，说说应用场景。
说到消息队列，上面是一个最基本的概念图（像什么topic、订阅这些请移步专门讲MQ的文章）
要实现一个MQ，在存取消息的时候，要满足下面的需求：
- 保序
- 可处理重复消息
- 可靠性保证
Redis中有两种方式实现消息队列，List和Stream，这里我们主要讲讲list。
保序
使用lpush/rpop（或者反过来）进行消息生产和消费
为了保证实时性，也有BRPOP/BLPOP阻塞获取
重复消息处理
对于重复消息的判断：
- 每个消息都有一个全局ID
- 消费者记录已处理过的消息的 ID。当收到消息后，消费者程序就可对比收到的消息 ID 和已处理过的消息 ID集，来判断当前的消息有没有处理过。如果处理过，那么，消费程序就不进行处理了。
List 并不会为每个消息生成 ID 号，所以我们需要自行为每个消息生成一个全局唯一ID
消息可靠性的保证
如果在读取过程因消费者发生宕机，消息还没被消费完就已经出了消息队列怎么办？
其实Redis可以开启一个备份，BRPOPLPUSH，这个命令的作用是让消费者程序从一个 List 中读取消息，同时，Redis 会把这个消息再插入到另一个 List（可以叫作备份 List）留存。
缺陷
List 不支持多个消费者消费同一条消息，因为一旦消费者拉取一条消息后，这条消息就从 List 中删除了，无法被其它消费者再次消费。
要实现一条消息可以被多个消费者消费，那么就要将多个消费者组成一个消费组，使得多个消费者可以消费同一条消息，但是 List 类型并不支持消费组的实现。
这就要说起 Redis 从 5.0 版本开始提供的 Stream 数据类型了，Stream 同样能够满足消息队列的三大需求，而且它还支持「消费组」形式的消息读取。
究其身
双向链表
数据结构基础了，不知道的自行百度，或者看看我的文章（这个不是常规的双链表，建议以一定基础的同学可以看看，基础较为薄弱的还是bing吧，hhh）：【数据结构】异或双链表–拥有单链表的空间，效率如双链表 – Karos (wzl1.top)
在看源代码之前，我们来看一个图，这其实是Redis中list的双链表实现
/* Node, List, and Iterator are the only data structures used currently. */
// 链表节点信息
typedef struct listNode {
struct listNode *prev; //前驱
struct listNode *next; //后继
void *value; //值
} listNode;
// 链表迭代器，这个地方我会仔细说的
typedef struct listIter {
listNode *next; //后继地址
int direction; //遍历方向
} listIter;
typedef struct list {
listNode *head; //头指针
listNode *tail; //尾指针
void *(*dup)(void *ptr); //节点copy函数
void (*free)(void *ptr); //节点释放函数
int (*match)(void *ptr, void *key); //节点比较函数
unsigned long len;
} list;
具体的其实都很简单，我们来看看一些方法的具体实现，你到这里有没有疑问，C语言不是面向过程的吗？结构体里面怎么会有函数？其实那是函数指针，具体的可以看看这个文章
函数指针及其定义和用法，C语言函数指针详解 (biancheng.net)
那么这尼玛不就是接口了？那么多态是不是也能够实现？
C语言能否通过结构体实现面向对象编程？ - 知乎 (zhihu.com)
迭代器实现
// 链表迭代器，这个地方才是我会仔细说的
typedef struct listIter {
listNode *next; //后继地址
int direction; //遍历方向
} listIter;
listNode *listNext(listIter *iter)
{
listNode *current = iter->next;
if (current != NULL) {
if (iter->direction == AL_START_HEAD) //方向为0
iter->next = current->next;
else
iter->next = current->prev; //方向为1
}
return current;
}
从代码可以看出，我们使用的永远都是同一个迭代器，先不看if里面的内容，可以看出返回的是一个节点信息，同时迭代器里面的next指针进行移动，移动方向看遍历方向，0为往后继遍历，1为往前驱遍历
优势与缺陷
Redis 的链表实现优点如下：
- listNode 链表节点的结构里带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；
- list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1) ；
- list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需O(1) ；
- listNode 链表节使用 void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；
链表的缺陷也是有的：
- 链表每个节点之间的内存都是不连续的，意味着无法很好利用 CPU 缓存。能很好利用 CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用 CPU 缓存来加速访问。
- 还有一点，保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。
因此，Redis 3.0 的 List 对象在数据量比较少的情况下，会采用「压缩列表」作为底层数据结构的实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构。
不过，压缩列表存在性能问题（具体什么问题，下面会说），所以 Redis 在 3.2 版本设计了新的数据结构 quicklist，并将 List 对象的底层数据结构改由 quicklist 实现。
然后在 Redis 5.0 设计了新的数据结构 listpack，沿用了压缩列表紧凑型的内存布局，最终在最新的 Redis 版本，将 Hash 对象和 Zset 对象的底层数据结构实现之一的压缩列表，替换成由 listpack 实现。
压缩列表
压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。
下面我们对整个ziplist进行解释：
-
is an unsigned integer to hold the number of bytes that
the ziplist occupies, including the four bytes of the zlbytes field itself.
This value needs to be stored to be able to resize the entire structure
without the need to traverse it first.
zlbytes，一个无符号整数表示ziplist的占有内存字节数
-
is the offset to the last entry in the list. This allows
a pop operation on the far side of the list without the need for full
traversal. zltail，记录最后一个entry相对于起始地址的偏移量
-
is the number of entries. When there are more than
2^16-2 entries, this value is set to 2^16-1 and we need to traverse the
entire list to know how many items it holds. zllen，表示entry的数量
-
is a special entry representing the end of the ziplist.
Is encoded as a single byte equal to 255. No other normal entry starts
with a byte set to the value of 255.
zlend，标记压缩列表的结束点，固定值为0XFF（255）
针对于每一个entry：
-
prevlen，记录了「前一个节点」的长度，目的是为了实现从后向前遍历；
-
encoding，记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数。
-
data，记录了当前节点的实际数据，类型和长度都由
encoding决定；下面来看看官方的解释翻译：
每个ziplist中的entry都带有包含两个信息的元数据前缀。
首先，存储前一个entry的长度，以便能够从后向前遍历列表。
其次，提供entry的编码。它表示entry的类型，可以是整数或字符串，
并且对于字符串，它还表示字符串数据的长度。因此，一个完整的entry存储如下：
有时编码本身代表了entry，比如后面我们将看到的小整数。
在这种情况下，部分缺失，我们可以只有如下：
前一个entry的长度的编码方式如下：
如果这个长度小于254字节，它只会占用一个字节，表示长度为无符号8位整数。
当长度大于或等于254时，将占用5个字节。
第一个字节设置为254（FE）表示后面跟着一个更大的值。剩余的4个字节用来表示前一个entry的长度。
因此，实际上一个entry的编码方式如下：
或者
如果前一个entry的长度大于253字节，则使用以下编码：
0xFE
entry的编码字段取决于entry的内容。当entry是字符串时，编码的第一个字节的前两位将表示用于存储字符串长度的编码类型，后面跟着实际的字符串长度。当entry是整数时，前两位都设置为1。接下来的2位用于指定在此标头之后将存储什么类型的整数。不同类型和编码的概述如下。第一个字节通常足以确定entry的类型。
...
下面是对于entry的处理类型，和实际数据类型有点不同，只是为了便于操作
//ziplist.h
//这个结构体存储的是每个entry的data
/* Each entry in the ziplist is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
unsigned int slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} ziplistEntry;
//ziplist.c
/* We use this function to receive information about a ziplist entry.
* Note that this is not how the data is actually encoded, is just what we
* get filled by a function in order to operate more easily. */
/**
从上面的注释可以看到，这个存的是没有给entry的所有信息，但是进行了一些填充：
我们使用这个函数来接收关于zip列表entry的信息。请注意，这并不是数据的实际encoding方式，这只是为了更容易操作而由函数填充的内容。
**/
typedef struct zlentry {
unsigned int prevrawlensize;/*Bytes used to encode the previous entry len*/ //用于encoding前一段len的字节数
unsigned int prevrawlen; /* Previous entry len. */ //前一个entry的长度
unsigned int lensize; /* Bytes used to encode this entry type/len.
For example strings have a 1, 2 or 5 bytes
header. Integers always use a single byte.*/
unsigned int len; /* Bytes used to represent the actual entry.
For strings this is just the string length
while for integers it is 1, 2, 3, 4, 8 or
0 (for 4 bit immediate) depending on the
number range. */
unsigned int headersize; /* prevrawlensize + lensize. */
//记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数。
unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
the entry encoding. However for 4 bits
immediate integers this can assume a range
of values and must be range-checked. */
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
下面来说一说encoding，
encoding的空间大小跟存储数据的类型(str | integer)，以及str的长度有关
- 如果当前节点的数据是整数，则 encoding 会使用 1 字节的空间进行编码，也就是 encoding 长度为 1 字节。通过 encoding 确认了整数类型，就可以确认整数数据的实际大小了，比如如果 encoding 编码确认了数据是 int16 整数，那么 data 的长度就是 int16 的大小。
- 如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节/2字节/5字节的空间进行编码，encoding 编码的前两个 bit 表示数据的类型，后续的其他 bit 标识字符串数据的实际长度，即 data 的长度。
连锁更新
当我们新增或者修改某个元素的时候，如果需要扩容，导致后续元素的prevlen进行更新，甚至可能导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。
后面的我就直接引用小林coding
现在假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，如下图：
因为这些节点长度值小于 254 字节，所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。
这时，如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，即新节点将成为 e1 的前置节点，如下图：
因为 e1 节点的 prevlen 属性只有 1 个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作，并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。
多米诺牌的效应就此开始。
e1 原本的长度在 250～253 之间，因为刚才的扩展空间，此时 e1 的长度就大于等于 254 了，因此原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。
正如扩展 e1 引发了对 e2 扩展一样，扩展 e2 也会引发对 e3 的扩展，而扩展 e3 又会引发对 e4 的扩展.... 一直持续到结尾。
这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」，就像多米诺牌的效应一样，第一张牌倒下了，推动了第二张牌倒下；第二张牌倒下，又推动了第三张牌倒下....
QuickList
前面说过这是一种升级实现，是由LinkList+ZipList组合实现的。
quicklist 就是一个链表，而链表中的每个节点又是一个压缩列表。
大概的模型我认为大家的脑子里应该也有了，没有的话看看这张图
下面来看源代码，没翻译的地方对于现在来说也没多大用处
/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
* 'fill' is the user-requested (or default) fill factor.
* 'bookmarks are an optional feature that is used by realloc this struct,
* so that they don't consume memory when not used. */
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count; /* 总共的entry数目 */
unsigned long len; /* 总共的节点数 */
signed int fill : QL_FILL_BITS; /* fill factor for individual nodes */
/* 如果压缩被禁用，则为0，否则为quicklist末尾未压缩的quicklistNodes的数目。0=off */
unsigned int compress : QL_COMP_BITS;
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;
/* quicklistNode is a 32 byte struct describing a listpack for a quicklist.
* We use bit fields keep the quicklistNode at 32 bytes.
* count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually head = quicklist->tail = NULL;
quicklist->len = 0;
quicklist->count = 0;
quicklist->compress = 0;
quicklist->fill = -2;
quicklist->bookmark_count = 0;
return quicklist;
}
//迭代器
typedef struct quicklistIter {
quicklist *quicklist;
quicklistNode *current;
unsigned char *zi; /* points to the current element */
long offset; /* offset in current listpack */
int direction;
} quicklistIter;
//记录所有的list
typedef struct quicklistEntry {
const quicklist *quicklist;
quicklistNode *node;
unsigned char *zi;
unsigned char *value;
long long longval;
size_t sz;
int offset;
} quicklistEntry;
ListPack
QuickList虽然通过减少压缩列表的粒度再组合来缓解连锁更新的新能影响，但是仍然无法完全解决
在5.0以后使用listpack来代替压缩列表，其实和压缩列表的最大区别在于每个entry不再包含前一个节点的长度了 ，而是保存当且节点 的长度，所以避免了连锁更新。
- encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码；
- data，实际存放的数据；
- len，encoding+data的总长度；
这里应该都好理解，但是还是放一下源代码吧。
/* Each entry in the listpack is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
uint32_t slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} listpackEntry;、
/* Create a new, empty listpack.
* On success the new listpack is returned, otherwise an error is returned.
* Pre-allocate at least `capacity` bytes of memory,
* over-allocated memory can be shrunk by `lpShrinkToFit`.
* */
unsigned char *lpNew(size_t capacity) {
unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ? capacity : LP_HDR_SIZE+1);
if (lp == NULL) return NULL;
lpSetTotalBytes(lp,LP_HDR_SIZE+1);
lpSetNumElements(lp,0);
lp[LP_HDR_SIZE] = LP_EOF;
return lp;
}
然后呢？没了？确实没了，毕竟是以二进制进行存储，和压缩列表实现同理
在 6.2 发行版本中，Redis Hash 对象、ZSet 对象的底层数据结构的压缩列表还未被替换成 listpack，而 Redis 的最新代码已经将所有用到压缩列表底层数据结构的 Redis 对象替换成 listpack 数据结构来实现
这也是QuickLIst里面为什么出现ListPack的原因，那么既然解决了连锁更新，为什么还会有QuickList呢？
笔者个人的理解是如下：
- 在过度时段，list的实现就是QuickLst，又改回去的话又要分为双链表和ListPack，麻烦
- 我现在感觉如此更新过的QuickList就很像MySQL InooDB页结构和索引，试想一下在未来是不是可以抽象成B+树来加快查询？
