你好，我是 redis
一个叫Antirez的男人带我来到这个充满复杂的世界上。
聊到我的出生，那跟MySQL大哥脱不了关系呀，我是来帮助他的，所谓天降猛男redis就是我了，真想对他说：
“
我还没有来到这个世界上的时候，刚开始挺好的，互联网前期，咱们的用户请求也不多，主要是一些静态网站和小游戏，这 有啥难的 ，MYSQL大哥一个顶俩好吧。但天有不测风云，历史不会停止步伐的。用户请求的数据也随之暴涨，每天用户的 每一次请求 都变成了对它的一个又一个的 读写操作 ，MYSQL直呼“快杀了我吧”，每年的“618”或者过年买票的时候，都是MYSQL受苦受累的日子啊！
”
反思 问题 出现在哪里，MYSQL大哥开始头头分析起来，原来有一大半的用户请求tm都是 读操作 ，而且经常又是查一个东西，简直浪费我 磁盘IO 的时间。后来我的爸爸突发奇想，你看看别人 CPU的缓存 是很快的呀，给数据库加个缓存就解决了呗，于是我就出生了！出生没几天，我就来给MYSQL大哥解决问题，效果也还不错，我们也成为了 好基友 ，常常手拉手在后端服务器中配合，大致如图：
为了方便与内存对接，我支持好几种数据结构的存储：
“
String
Hash
List
Set
SortedSet
Bitmap
......
”
因为把MYSQL里 登记的数据 都放到我的内存里来，就不去执行慢如蜗牛的I/O操作，所以下次找我肯定比找MYSQL要 省去 不少的时间呢。
可别小瞧这一个微小的操作，可帮MYSQL大哥减轻了不小的负担！我缓存的数据也逐渐增长，有
相当部分
的时间都给他挡住了用户请求，这下他可就清闲自在了！
“
那今天就给大家聊一聊，咱的看家本领，内存是如何 管 上面的数据类型的。说着，我拿笔给大家 画 一张图：
”
看看，我的肚子里用了一个redisObject对象来展示所有的 value和key 。type就是value对象是 那种 数据类型，第二个encoding就是不同的数据类型在Redis内部是如何 放 的。
譬如： type=String 则表示value存储的是一个普通字符串，那我推断出 encoding 可以是raw或者是int。但是我稍加思索，哎，还要解释下 底层数据结构 ，你知道吗？底层的底层，你有了解过吗？跟着我摆起来哈。
下面是各自对应的数据结构；
可以看出来，有很多类型都是使用 两种结构 ，就像set在元素比较少的时候，且都是数字的情况下会用 整数列表 ，随着数据增加就变成 哈希表 。但是我有一个比较大的疑问，这些类型都对应不同的数据结构，想想redis 整体的结构
是啥样的呢？再举个例子，现在有一个
key对应的value
是我们的list类型的，那就对应着上面的双向链表啊？那咱第一步就要找到这个key,就可找到双向链表了噻；
其实啊，我这里是有一个大的哈希表的，在 你们的眼 里可能就是类似的长数组，在它上面的每个空间，都可以看做一个哈希桶，长这样：
每一个key经过我肚子里面的hash算法就会给你算出一个位置，怎么来算请看下面：
哈希算法：Redis计算哈希值和索引值方法如下：
//1、使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
//2、使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值
index = hash & dict->ht[x].sizemask;
那它就对应一个哈希桶呗。 壮士请注意 ，这个过程是很快的哈。只有O(1)哦，这个过程咱就算出 内存地址 ，那你就直接去找就行了。然后我们把这个key放到hash桶里面去。记住啊壮士，这个桶里面 保存的是引用 哈，不是你的 那个对象（狗头） 。就好比哈希桶里面保存的是key家的门牌号一样（实质内存地址），那我们就用了0(1)的复杂度就这样找到这个key。，因为用key去查找value的时候，只需要在经过依次hash能马上找到哈希桶，就能定位到这个 键值对 的内存地址了。
“
hash算法是不能保证 所有的key 经过算法出来的值都一样，那就是会有哈希冲突的存在，就是 两个key放到了同一个桶 中，这可怎么办呢？
”
我们就用 链表 来解决这个问题，就是两个在一个桶中的元素，我们就用一个next指针把它们 连在一起 ，经过hash算出来之后找到一个键值对， 对比看着 如果不是，根据next指针再找下一个比就行。我们都知道链表是一种常用的数据结构，而C语言内部是 没有内置 这种数据结构的实现，所以我redis会自己构建了 链表 的实现。
其中每个
链表节点
使用一个listNode结构表示:(下图的右部分）：
//链表节点
typedef struct listNode{
struct listNode * prev;
struct listNode * next;
void * value;
}
下图是有两部分，由list和listNode两个数据结构构成。一部分是“ 统筹部分 ”是左边，一部分是“ 具体实施 “：右边；
head指向具体 双向链表的头
tail指向具体 双向链表的尾
len双向链表的
长度
；
可以看出每个链表节点都有指向 前置节点prev 和 后置节点next 的指针，组成一个双向链表。每个链表结构，有表头表尾指针和链表长度等信息。另外表头节点和前置和表尾节点的 后置都是NULL ，所以是无环链表。
在总结下：
typedef struct list {
//表头节点
listNode * head;
//表尾节点
listNode * tail;
//链表长度
unsigned long len;
//节点值复制函数
void *(*dup) (void *ptr);
//节点值释放函数
void (*free) (void *ptr);
//节点值对比函数
int (*match)(void *ptr, void *key);
}
“
那么当元素越来越多之后，一个哈希桶所 对应的链表 就会越来越长，我们知道链表上的遍历时间复杂度是O(n)的，那么会严重 影响性能 ，Redis这种追求快的数据库看来是绝对不能够 容忍 的，那么要怎么处理，就是rehash操作。
”
redis会在 内部再新建 一个长度为原始长度2倍的空哈希表，然后原哈希表上的元素 重新rehash 到新的哈希表中去，然后我们再使用新的哈希表即可。
那么，这样还是有个问题要解决呀！
要知道redis中存储的数据可能是成百万上千万的，我们 重新rehash 一次未免太耗时了吧，因为redis中操作大部分是 单线程 的。
“
这个过程可能会阻断其他操作很长时间，这是不能忍受的，那要怎么处理呢？
”
首先redis是采用了 渐进式rehash 的操作，就是会有一个变量，指向第一个哈希桶，然后redis每执行一个添加key，删除key的类似命令，就顺便 copy一个哈希桶中的数据 到新的哈希表中去，这样细水长流的操作，是不会影响什么性能，就会所有的数据都被重新hash到新的哈希表中。
那么在这个过程中，当然再有写的操作，会直接把数据放到新的哈希表中，保证旧的肯定有 copy完 的时候，如果这段时间对数据库的操作比较少，也没有关系，redis 内部也有定时 任务，每隔一段时间也会copy一次。
SDS的全称"simple dynamic string"。redis中所有场景中出现的字符串，基本都是由SDS来实现的。
所有 非数字的key 。例如 set msg "hello world" 中的key msg.
字符串数据类型的值 。例如 set msg "hello world"中的msg的值"hello wolrd"
最后是两者结合：
非字符串数据类型中的“字符串值”
。例如 RPUSH fruits "Apple""banana""cherry"中的"apple" "banana" "cherry"都是;
上面的例子，我们可以很直观地看到我们在平常使用redis的时候，创建的字符串到底是一个什么样子的数据类型。除了用来保存字符串以外，SDS还被用作 缓冲区 （buffer）AOF模块中的 AOF缓冲区 。
/*
* 保存字符串对象的结构
*/
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
SDS示例
那么传统的C字符串使用长度为 N+1的字符串数组 来表示 长度为N的字符串 ，所以为了获取一个长度为C字符串的长度，必须遍历整个字符串。
这样做在获取字符串长度的时候，字符串扩展等操作的时候 效率比较低 。C语言用这种 简单 的字符串表示方式，但是并不能满足Redis对字符串在安全性、效率以及功能方面的要求：
“
和C 字符串不同，SDS的数据结构中，有专门用于 保存字符串长度 的变量，我们可以通过获取len属性的值，如下图的，直接知道字符串长度：
”
我们现在假设程序中有两个在内存中 紧邻着的字符串s1和s2 ，其中s1保存了字符串“ redis ”，而s2 则保存了字符串“ MongoDb ”：
如果我们现在将s1的内容修改为 redis cluster ，但是我又忘了重新为 s1分配足够的空间 ，这时候就会出现以下问题：
我们可以看到，原本s2中的内容已经 被S1的给占领 了，s2现在是cluster，而不是“Mongodb”。Redis 中SDS 的 空间分配策略 完全 杜绝 了发生缓冲区溢出的可能性：
“
我们需要对一个SDS进行修改的时候，redis会在执行 拼接操作 之前，预先检查给定SDS空间是否是足够的，如果不够，会先 拓展SDS 的空间 ，然后再执行拼接操作；
”
C字符串在进行字符串的扩充和收缩的时候，都常常会面临着 内存空间 重新分配的问题。
下面我们对SDS进行拓展，那就需要进行 空间的拓展 ，redis会将SDS的长度修改为13字节，并且将未使用空间同样修改成1字节；
因为在上一次修改字符串的时候已经拓展了空间，再次进行修改字符串的时候你会发现空间是足够使用，因此就不要进行空间拓展了。
通过这种 预分配策略 ，SDS将连续增长N次字符串所需的 内存重分配次数 从必定N次会降低为最多N次
我们在观察SDS的结构的时候,可以看到里面有free属性，是用于 记录空余空间 的。我们除了在拓展字符串的时候会使用到free来进行记录空余空间以外，在对字符串进行收缩的时候，我们也可以使用free 属性来进行 记录剩余空间 ，这样做的好处就是避免下次对字符串进行再次修改的时候，我们 再对 字符串的空间进行拓展。
“
但是，我们并不是说不能释放SDS中空余的空间，SDS 提供了相应的API，让我们可以在 有需要 的时候，会 自行释放 SDS的空余空间；
”
通过惰性空间释放，SDS避免了缩短字符串时所需的 内存重分配 操作，并未将来可能有的增长操作提供了优化，嗯值得点赞！
强调 的是C字符串中的字符必须符合某种 编码 ，并且除了字符串的末尾之外，字符串里面不包含 空字符 ，否则最先被程序读入的空字符将被误认为是字符串结尾，那就尴尬了，这些 限制 使得C字符串只能保存文本数据，而不能保存想图片，音频，视频，压缩文件这样的 二进制 数据。
“
但是在Redis中，不是靠空字符来判断字符串的结束的，而是通过 len 这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的。
”
如这样：
虽然SDS的API都是二进制安全的，但他们同样要遵循C字符串以 空字符串结尾 的惯例。
|
C字符串 |
SDS |
|
获取字符串长度的复杂度为O（N) |
获取字符串长度的复杂度为O(1) |
|
API 是不安全的，可能会造成缓冲区溢出 |
API 是安全的，不会造成缓冲区溢出 |
|
修改字符串长度N次必然需要执行N次内存重分配 |
修改字符串长度N次最多执行N次内存重分配 |
|
只能保存文本数据 |
可以保存二进制数据和文本文数据 |
|
可以使用所有<String.h>库中的函数 |
可以使用一部分<string.h>库中的函数 |
压缩表是一种Redis用来 节省内存 的一系列特殊编码的 顺序性连续存储 的表结构，我们知道数组这种数据结构，每一个空间的大小都是一样的，这样我们存储较小元素节点的时候就会造成 内存的浪费 ，而压缩链表可以做到每一个元素的节点的 大小都不一样 。当一个哈希键只含少量键值对，并且每个键值对的键和值也是小整数值或者长度比较短的字符串的时候，Redis就采用压缩列表做底层实现;
长这样：
图里 entry 的结构是这样的：
previous_entry_length属性以字节为单位，记录了压缩列表中 前一个节点的长度 。该属性的长度可以是1字节或者是5字节。如果前一个节点的长度 小于
254 字节，那么该属性长度为1字节，保存的是小于 254的值。那如果前一节点的长度
大于等于
254字节，那么长度需要为5字节，属性的第一字节会被设置为0xFE (254)之后的4个字节保存其长度。
zlbytes ：4 字节。记录整个压缩列表占用的内存字节数，在内存重分配或者计算 zlend 的位置时使用。
zltail ：4 字节。记录压缩列表表尾节点记录压缩列表的起始地址有多少个字节，可以通过该属性直接确定表尾节点的地址，无需遍历。
zllen ：2 字节。记录了压缩列表包含的节点数量，由于只有2字节大小，那么小于65535时，表示节点数量。等于 65535 时，需要遍历得到总数。
entry ：列表节点，长度不定，由内容决定。
zlend
：1字节，特殊值 0xFF ，来标记压缩列表的结束。
压缩列表节点保存的是 一个字节数组 或者 一个整数值 ：字节数组可以是下列值：
先找到列表尾部元素：
然后再根据 ziplist 节点元素中的 previous_entry_length 属性，来逐个来遍历:
再次看看 entry元素的结构，有一个 previous_entry_length 字段，它的长度要么都是1个字节，要么都是5个字节：
g3
程序需要 不断 的对压缩列表进行 空间重分配 工作，直到结束。
除了增加操作，删除操作也有可能带来“连锁更新”。请看下面这张图， ziplist 中所有 entry 节点的长度都在250字节至253字节之间，big节点长度大于254字节，small节点小于254字节：
在我看来，压缩列表实际上 类似于一个数组 ，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在 表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的entry数；压缩列表在表尾还有一个 zlend ，表示列表结束罢了。
“
又叫 符号表 或者关联数组、或映射（map），是一种用于 保存键值对 的抽象数据结构。字典中的每一个键key都是唯一的，通过key可以对值来进行 查找或修改 。C语言中没有内置这种数据结构的实现，所以字典依然是 Redis自己实现的；示例：
”
redis > SET msg "hello world"
OK
（“msg”，“hello world”）这个就是字典;
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
//总是等于 size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}dictht
哈希表是数组(表）table 组成，table里面每个元素都是指向 dict.h 或者 dictEntry 这个结构，dictEntry 结构：
typedef struct dictEntry{
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下一个哈希表节点，形成链表
struct dictEntry *next;
}dictEntry
哈希表就略微有点复杂。哈希表的制作方法一般有两种，一种是： 开放寻址法 ，一种是拉链法。redis的哈希表的制作使用的是 拉链法 。
哈希1
“
也是分为两部分：左边橘黄色部分和右边蓝色部分，同样，也是”统筹“和”实施“的关系。具体 哈希表的实现 ，都是在 蓝色部分 实现的,好！先来看看蓝色部分：
”
这也会分为左右两边“统筹”和“实施”的两部分。
右边部分很容易理解：就是通常用 拉链表实现 的哈希表的样式；数组就是bucket，一般不同的key首先会定位到不同的bucket，若key重复，就用链表把 冲突的key串 起来。
哈3
哈4
“
再来看看哈希表总体图中左边橘黄色的“统筹”部分，其中有两个关键的属性：ht和 rehashidx。ht是一个 数组 ，有且只有俩元素ht[0]和ht[1];其中，ht[0]存放的是 redis中使用的哈希表 ，而ht[1]和rehashidx和哈希表是有 rehash 有关系的。
”
rehash指的是 重新计算 键的哈希值和索引值，然后将键值对 重排 的过程。
（load factor）=ht[0].used/ht[0].size；
第一个大于等于 ht[0].used*2的 2^n(2的n次方幂);
第一个大于等于 ht[0].used的 2^n(2的n次方幂)。(以下部分属于细节分析，可以跳过直接看扩容步骤)
对于收缩，我当时陷入了疑虑：收缩标准是加载因子 小于0.1 的时候，也就是说假如哈希表中有4个元素的话，哈希表的长度只要大于40，就会进行收缩，假如有一个长度大于40，但是 存在的元素为4 即( ht[0].used为4)的哈希表，进行收缩，那收缩后的值为多少？
我想了一下：按照前文所讲的内容，应该是4。但是，假如是4， 存在和收缩后的长度相等 ，是不是又该扩容？
假如收缩后 长度为4
，不仅不会收缩，甚至还会
报错
；
我们回过头来再看看设定：题目可能成立吗？哈希表的扩容都是 2倍增长的 ，最小是4， 4 ===》 8 ====》 16 =====》 32 ======》 64 ====》 128
“
也就是说：不存在长度为 40多的情况，只能是64。但是如果是64的话，64 X 0.1（收缩界限）= 6.4 ，也就是说在减少到6的时候，哈希表就会收缩，会缩小到多少呢？是8。此时，再继续减少到4，也不会再收缩了。所以，根本不存在一个长度大于40，但是存在的元素为4的哈希表的。
”
在"扩容步骤"和"收缩步骤" 两幅动图中每幅图的 第四步骤 “将ht[0]中的数据利用哈希函数 重新计算 ，rehash到ht[1]”，并不是一步完成的，而是分成N多步，循序渐进地完成的。因为hash中有可能存放几千万甚至上亿个key，毕竟Redis中每个 hash中可以存 2^32-1 键值对 （40多亿），假如一次性将这些键值rehash的话，可能会导致服务器在一段时间内停止服务，毕竟哈希函数就得 计算一阵子呢 (对吧(#^.^#))。
渐进式refresh和下图中左边橘黄色的“统筹”部分中的rehashidx密切相关：
甚至在进行期间，每次对哈希表的增删改查操作，除了正常执行之外，还会顺带将ht[0]哈希表相关键值对 rehash 到ht[1]。
以扩容步骤 举例 ：
整数集合是 集合键 的底层实现方式之一。
跳表这种数据结构长这样：
redis中把跳表抽象成如下所示：
看这个图，左边“统筹”，右边实现。
redis中并没有 直接使用 以上所说的那种数据结构来实现键值数据库，而是基于一种对象，对象底层再 间接的引用 上文所说的 具体 的数据结构。
就像这样：
其中：embstr和raw都是由 SDS动态字符串 构成的。唯一区别是： raw 是分配内存的时候，redis object和sds各分配一块内存，而embstr是redisobject和raw 在一块儿内存 中。
列表
哈希
set
zset
是一种 有序 数据结构，它通过在 每个节点 中维持 多个指向其它节点 的指针，从而达到快速访问节点的目的。具有如下 性质 ：
1、由很多层结构组成；
2、每一层都是一个有序的链表，排列顺序为由高层到底层，且至少包含两个链表节点，分别是前面的 head节点 和后面的 nil节点 ；
3、最底层的链表包含了所有的元素；
4、如果一个元素出现在某一层的链表中，那么在 该层之下 的链表也全 都会出现 （上一层的元素是当前层的元素的子集）；
5、链表中的每个节点都包含两个指针，一个指向 同层的下一个链表节点 ，另一个指向 下层的同一个链表节点 ；
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;
“
①、搜索：从最高层的链表节点开始，如果比 当前节点要大 和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到 最底层的最后一个节点 ，如果找到则返回，反之则返回空。
②、插入：首先确定 插入的层数 ，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定 插入的层数k 后，则需要将 新元素 插入到从底层到k层。
③、删除：在各个层中找到包含 指定值的节点
，然后将节点从链表中删除即可，如果删除以后
只剩下
头尾两个节点，则删除这一层。
”
用于保存 整数值 的集合抽象数据类型，它可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中 不会出现重复 元素。定义如下：
typedef struct intset{
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
}intset;
整数集合的每个元素都是 contents 数组 的一个数据项，它们按照从小到大的 顺序排列 ，并且不包含任何重复项。
需要注意的是虽然 contents 数组声明为 int8_t 类型，但是实际 上contents数组并不保存 任何 int8_t 类型的值 ，其真正类型有 encoding 来决定。
当我们新增的元素类型比原集合元素类型的长度要大时，需要对 整数集合 进行升级，才能将新元素放入整数集合中。具体步骤：
1、根据新元素类型，扩展整数集合底层数组的大小，并为 新元素 分配空间。
2、将底层数组现有的所有元素都转成与新元素相同类型的元素，并将 转换后的元素 放到正确的位置，放置过程中，维持整个元素 顺序 都是有序的。
3、将新元素添加到整数集合中是有序的呀！
整数集合不支持降级操作，一旦对数组进行了升级， 编码 就会一直保持升级后的状态
“
大多数情况下，Redis使用 简单字符串SDS作为字符串 的表示，相对于C语言字符串，SDS具有常数复杂度获取字符串长度，杜绝了 缓存区的溢出 ，减少了修改字符串长度时所需的 内存重分配次数 ，以及二进制安全能存储各种类型的文件，并且还兼容部分C函数。
”
通过为链表设置不同类型的特定函数，Redis链表可以保存各种 不同类型的值 ，除了用作列表键，还在发布与订阅、慢查询、监视器等方面发挥作用（后面会介绍）。
Redis的字典底层使用 哈希表实现 ，每个字典通常有两个哈希表，一个平时使用，另一个用于rehash时使用，使用 链地址法 解决哈希冲突。
跳跃表通常是有序集合的底层实现之一，表中的节点按照 分值大小 进行排序。
整数集合是 集合键 的底层实现之一，底层由数组构成， 升级特性 能尽可能的节省内存。
压缩列表是Redis为 节省内存 而开发的顺序型数据结构，经常作为列表键和哈希键的底层实现。
原文链接：
https://mp.weixin.qq.com/s?__biz=MzAwMDg2OTAxNg==&mid=2652049856&idx=1&sn=05d77ad89bb84bf55cea9e17e6192a04&utm_source=tuicool&utm_medium=referral
京公网安备 11010802035086号