前言
只有光头才能变强
最近在学 Redis，我相信只要是接触过 Java 开发的都会听过 Redis 这么一个技术。面试也是非常高频的一个知识点，之前一直都是处于了解阶段。秋招过后这段时间是没有什么压力的，所以打算系统学学 Redis，这也算是我从零学习 Redis 的笔记吧。
本文力求讲清每个知识点，希望大家看完能有所收获。
一、介绍一下 Redis
首先，肯定是去官网看看官方是怎么介绍 Redis 的啦。https://redis.io/topics/introduction
如果像我一样，英语可能不太好的，可能看不太懂。没事，咱们 Chrome 浏览器可以切换成中文的，中文是我们的母语，肯定没啥压力了。Eumm…
读完之后，发现中文也就那样了。
一大堆没见过的技术：lua(Lua 脚本)、replication(复制)、Redis Sentinel(哨兵)、Redis Cluster(Redis 集群)，当然我们也会有看得懂的技术：transactions(事务)、different levels of on-disk persistence(数据持久化)、LRU eviction(LRU 淘汰机制)..
至少官方介绍 Redis 的第一句应该是可以很容易看懂：”Redis is an open source (BSD licensed),in-memory data structure store, used as a database,cache and message broker.”
Redis 是一个开源的，基于内存的数据结构存储，可用作于数据库、缓存、消息中间件。
从官方的解释上，我们可以知道：Redis 是基于内存，支持多种数据结构。
从经验的角度上，我们可以知道：Redis 常用作于缓存。
就我个人认为：学习一种新技术，先把握该技术整体的知识(思想)，再扣细节，这样学习起来会比较轻松一些。所以我们先以“内存”、“数据结构”、“缓存”来对 Redis 入门。
1.1 为什么要用 Redis？
从上面可知：Redis 是基于内存，常用作于缓存的一种技术，并且 Redis 存储的方式是以 key-value 的形式。
我们可以发现这不就是 Java 的 Map 容器所拥有的特性吗，那为什么还需要 Redis 呢？
Java 实现的 Map 是本地缓存，如果有多台实例 (机器) 的话，每个实例都需要各自保存一份缓存，缓存不具有一致性
Redis 实现的是分布式缓存，如果有多台实例 (机器) 的话，每个实例都共享一份缓存，缓存具有一致性。
Java 实现的 Map 不是专业做缓存的，JVM 内存太大容易挂掉的。一般用做于容器来存储临时数据，缓存的数据随着 JVM 销毁而结束。Map 所存储的数据结构，缓存过期机制等等是需要程序员自己手写的。
Redis 是专业做缓存的，可以用几十个 G 内存来做缓存。Redis 一般用作于缓存，可以将缓存数据保存在硬盘中，Redis 重启了后可以将其恢复。原生提供丰富的数据结构、缓存过期机制等等简单好用的功能。
参考资料：
为什么要用 redis 而不用 map 做缓存?https://segmentfault.com/q/1010000009106416
1.2 为什么要用缓存？
如果我们的网站出现了性能问题(访问时间慢)，按经验来说，一般是由于数据库撑不住了。因为一般数据库的读写都是要经过磁盘的，而磁盘的速度可以说是相当慢的(相对内存来说)
科普文：让 CPU 告诉你硬盘和网络到底有多慢 https://zhuanlan.zhihu.com/p/24726196
如果学过 Mybaits、Hibernate 的同学就可以知道，它们有一级缓存、二级缓存这样的功能(终究来说还是本地缓存)。目的就是为了：不用每次读取的时候，都要查一次数据库。
有了缓存之后，我们的访问就变成这样了：
二、Redis 的数据结构
本文不会讲述命令的使用方式，具体的如何使用可查询 API。
Redis 命令参考：http://doc.redisfans.com/
try Redis(不用安装 Redis 即可体验 Redis 命令)：http://try.redis.io/
Redis 支持丰富的数据结构，常用的有 string、list、hash、set、sortset 这几种。学习这些数据结构是使用 Redis 的基础！
“Redis is written in ANSI C”–>Redis 由 C 语言编写
首先还是得声明一下，Redis 的存储是以 key-value 的形式的。Redis 中的 key 一定是字符串，value 可以是 string、list、hash、set、sortset 这几种常用的。
但要值得注意的是：Redis 并没有直接使用这些数据结构来实现 key-value 数据库，而是基于这些数据结构创建了一个对象系统。
简单来说：Redis 使用对象来表示数据库中的键和值。每次我们在 Redis 数据库中新创建一个键值对时，至少会创建出两个对象。一个是键对象，一个是值对象。
Redis 中的每个对象都由一个 redisObject 结构来表示：
typedef struct redisObject{
// 对象的类型
unsigned type 4:;
// 对象的编码格式
unsigned encoding:4;
// 指向底层实现数据结构的指针
void * ptr;
//…..
}robj;
简单来说就是 Redis 对 key-value 封装成对象，key 是一个对象，value 也是一个对象。每个对象都有 type(类型)、encoding(编码)、ptr(指向底层数据结构的指针)来表示。
下面我就来说一下我们 Redis 常见的数据类型：string、list、hash、set、sortset。它们的底层数据结构究竟是怎么样的！
2.1SDS 简单动态字符串
简单动态字符串(Simple dynamic string,SDS)
Redis 中的字符串跟 C 语言中的字符串，是有点差距的。
Redis 使用 sdshdr 结构来表示一个 SDS 值：
struct sdshdr{
// 字节数组，用于保存字符串
char buf[];
// 记录 buf 数组中已使用的字节数量，也是字符串的长度
int len;
// 记录 buf 数组未使用的字节数量
int free;
}
例子：
2.1.1 使用 SDS 的好处
SDS 与 C 的字符串表示比较
sdshdr 数据结构中用 len 属性记录了字符串的长度。那么获取字符串的长度时，时间复杂度只需要 O(1)。
SDS 不会发生溢出的问题，如果修改 SDS 时，空间不足。先会扩展空间，再进行修改！(内部实现了动态扩展机制)。
SDS 可以减少内存分配的次数(空间预分配机制)。在扩展空间时，除了分配修改时所必要的空间，还会分配额外的空闲空间(free 属性)。
SDS 是二进制安全的，所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据。
2.2 链表
对于链表而言，我们不会陌生的了。在大学期间肯定开过数据结构与算法课程，链表肯定是讲过的了。在 Java 中 Linkedxxx 容器底层数据结构也是链表 +[xxx]的。我们来看看 Redis 中的链表是怎么实现的：
使用 listNode 结构来表示每个节点：
typedef strcut listNode{
// 前置节点
strcut listNode *pre;
// 后置节点
strcut listNode *pre;
// 节点的值
void *value;
}listNode
使用 listNode 是可以组成链表了，Redis 中使用 list 结构来持有链表：
typedef struct list{
// 表头结点
listNode *head;
// 表尾节点
listNode *tail;
// 链表长度
unsigned long len;
// 节点值复制函数
void *(*dup) (viod *ptr);
// 节点值释放函数
void (*free) (viod *ptr);
// 节点值对比函数
int (*match) (void *ptr,void *key);
}list
具体的结构如图：
2.2.1Redis 链表的特性
Redis 的链表有以下特性：
无环双向链表
获取表头指针，表尾指针，链表节点长度的时间复杂度均为 O(1)
链表使用 void * 指针来保存节点值，可以保存各种不同类型的值
2.3 哈希表
声明：《Redis 设计与实现》里边有“字典”这么一个概念，我个人认为还是直接叫哈希表比较通俗易懂。从代码上看：“字典”也是在哈希表基础上再抽象了一层而已。
在 Redis 中，key-value 的数据结构底层就是哈希表来实现的。对于哈希表来说，我们也并不陌生。在 Java 中，哈希表实际上就是数组 + 链表的形式来构建的。下面我们来看看 Redis 的哈希表是怎么构建的吧。
在 Redis 里边，哈希表使用 dictht 结构来定义：
typedef struct dictht{
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size-1
unsigned long sizemark;
// 哈希表已有节点数量
unsigned long used;
}dictht
我们下面继续写看看哈希表的节点是怎么实现的吧：
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *value;
uint64_tu64;
int64_ts64;
}v;
// 指向下个哈希节点，组成链表
struct dictEntry *next;
}dictEntry;
从结构上看，我们可以发现：Redis 实现的哈希表和 Java 中实现的是类似的。只不过 Redis 多了几个属性来记录常用的值：sizemark(掩码)、used(已有的节点数量)、size(大小)。
同样地，Redis 为了更好的操作，对哈希表往上再封装了一层(参考上面的 Redis 实现链表)，使用 dict 结构来表示：
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
//rehash 索引
// 当 rehash 不进行时，值为 -1
int rehashidx;
}dict;
//———————————–
typedef struct dictType{
// 计算哈希值的函数
unsigned int (*hashFunction)(const void * key);
// 复制键的函数
void *(*keyDup)(void *private, const void *key);
// 复制值得函数
void *(*valDup)(void *private, const void *obj);
// 对比键的函数
int (*keyCompare)(void *privdata , const void *key1, const void *key2)
// 销毁键的函数
void (*keyDestructor)(void *private, void *key);
// 销毁值的函数
void (*valDestructor)(void *private, void *obj);
}dictType
所以，最后我们可以发现，Redis 所实现的哈希表最后的数据结构是这样子的：
从代码实现和示例图上我们可以发现，Redis 中有两个哈希表：
ht[0]：用于存放真实的 key-vlaue 数据
ht[1]：用于扩容(rehash)
Redis 中哈希算法和哈希冲突跟 Java 实现的差不多，它俩差异就是：
Redis 哈希冲突时：是将新节点添加在链表的表头。
JDK1.8 后，Java 在哈希冲突时：是将新的节点添加到链表的表尾。
2.3.1rehash 的过程
下面来具体讲讲 Redis 是怎么 rehash 的，因为我们从上面可以明显地看到，Redis 是专门使用一个哈希表来做 rehash 的。这跟 Java 一次性直接 rehash 是有区别的。
在对哈希表进行扩展或者收缩操作时，reash 过程并不是一次性地完成的，而是渐进式地完成的。
Redis 在 rehash 时采取渐进式的原因：数据量如果过大的话，一次性 rehash 会有庞大的计算量，这很可能导致服务器一段时间内停止服务。
Redis 具体是 rehash 时这么干的：
(1: 在字典中维持一个索引计数器变量 rehashidx，并将设置为 0，表示 rehash 开始。
(2: 在 rehash 期间每次对字典进行增加、查询、删除和更新操作时，除了执行指定命令外；还会将 ht[0]中 rehashidx 索引上的值 rehash 到 ht[1]，操作完成后 rehashidx+1。
(3: 字典操作不断执行，最终在某个时间点，所有的键值对完成 rehash，这时将 rehashidx 设置为 -1，表示 rehash 完成
(4: 在渐进式 rehash 过程中，字典会同时使用两个哈希表 ht[0]和 ht[1]，所有的更新、删除、查找操作也会在两个哈希表进行。例如要查找一个键的话，服务器会优先查找 ht[0]，如果不存在，再查找 ht[1]，诸如此类。此外当执行新增操作时，新的键值对一律保存到 ht[1]，不再对 ht[0]进行任何操作，以保证 ht[0]的键值对数量只减不增，直至变为空表。
2.4 跳跃表(shiplist)
跳跃表 (shiplist) 是实现 sortset(有序集合)的底层数据结构之一！
跳跃表可能对于大部分人来说不太常见，之前我在学习的时候发现了一篇不错的文章讲跳跃表的，建议大家先去看完下文再继续回来阅读：
漫画算法：什么是跳跃表？http://blog.jobbole.com/111731/
Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成。其中 zskiplist 保存跳跃表的信息(表头，表尾节点，长度)，zskiplistNode 则表示跳跃表的节点。
按照惯例，我们来看看 zskiplistNode 跳跃表节点的结构是怎么样的：
typeof struct zskiplistNode {
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
zskiplistNode 的对象示例图(带有不同层高的节点)：
示例图如下：
zskiplist 的结构如下：
typeof struct zskiplist {
// 表头节点，表尾节点
struct skiplistNode *header,*tail;
// 表中节点数量
unsigned long length;
// 表中最大层数
int level;
} zskiplist;
最后我们整个跳跃表的示例图如下：
2.5 整数集合(intset)
整数集合是 set(集合)的底层数据结构之一。当一个 set(集合)只包含整数值元素，并且元素的数量不多时，Redis 就会采用整数集合 (intset) 作为 set(集合)的底层实现。
整数集合 (intset) 保证了元素是不会出现重复的，并且是有序的(从小到大排序)，intset 的结构是这样子的：
typeof struct intset {
// 编码方式
unit32_t encoding;
// 集合包含的元素数量
unit32_t lenght;
// 保存元素的数组
int8_t contents[];
} intset;
intset 示例图：
说明：虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组，但实际上 contents 数组并不保存任何 int8_t 类型的值，contents 数组的真正类型取决于 encoding 属性的值：
INTSET_ENC_INT16
INTSET_ENC_INT32
INTSET_ENC_INT64
从编码格式的名字我们就可以知道，16,32,64 编码对应能存放的数字范围是不一样的。16 明显最少，64 明显最大。
如果本来是 INTSET_ENC_INT16 的编码，想要存放大于 INTSET_ENC_INT16 编码能存放的整数值，此时就得编码升级(从 16 升级成 32 或者 64)。步骤如下：
1）根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。
2）将底层数组现有的所以元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位上，需要维持底层数组的有序性质不变。
3）将新元素添加到底层数组。
另外一提：只支持升级操作，并不支持降级操作。
2.6 压缩列表(ziplist)
压缩列表 (ziplist) 是 list 和 hash 的底层实现之一。如果 list 的每个都是小整数值，或者是比较短的字符串，压缩列表 (ziplist) 作为 list 的底层实现。
压缩列表 (ziplist) 是 Redis 为了节约内存而开发的，是由一系列的特殊编码的连续内存块组成的顺序性数据结构。
压缩列表结构图例如下：
下面我们看看节点的结构图：
压缩列表从表尾节点倒序遍历，首先指针通过 zltail 偏移量指向表尾节点，然后通过指向节点记录的前一个节点的长度依次向前遍历访问整个压缩列表。
三、Redis 中数据结构的对象
再次看回这张图，觉不觉得就很好理解了？
3.1 字符串 (stirng) 对象
在上面的图我们知道 string 类型有三种编码格式：
int：整数值，这个整数值可以使用 long 类型来表示
如果是浮点数，那就用 embstr 或者 raw 编码。具体用哪个就看这个数的长度了
embstr：字符串值，这个字符串值的长度小于 39 字节
raw：字符串值，这个字符串值的长度大于 39 字节
embstr 和 raw 的区别：
raw 分配内存和释放内存的次数是两次，embstr 是一次
embstr 编码的数据保存在一块连续的内存里面
编码之间的转换：
int 类型如果存的不再是一个整数值，则会从 int 转成 raw
embstr 是只读的，在修改的时候回从 embstr 转成 raw
3.2 列表 (list) 对象
在上面的图我们知道 list 类型有两种编码格式：
ziplist：字符串元素的长度都小于 64 个字节 && 总数量少于 512 个
linkedlist：字符串元素的长度大于 64 个字节 || 总数量大于 512 个
ziplist 编码的列表结构：
redis > RPUSH numbers 1 “three” 5
(integer) 3
linkedlist 编码的列表结构：
编码之间的转换：
原本是 ziplist 编码的，如果保存的数据长度太大或者元素数量过多，会转换成 linkedlist 编码的。
3.3 哈希 (hash) 对象
在上面的图我们知道 hash 类型有两种编码格式：
ziplist：key 和 value 的字符串长度都小于 64 字节 && 键值对总数量小于 512
hashtable：key 和 value 的字符串长度大于 64 字节 || 键值对总数量大于 512
ziplist 编码的哈希结构：
hashtable 编码的哈希结构：
编码之间的转换：
原本是 ziplist 编码的，如果保存的数据长度太大或者元素数量过多，会转换成 hashtable 编码的。
3.4 集合 (set) 对象
在上面的图我们知道 set 类型有两种编码格式：
intset：保存的元素全都是整数 && 总数量小于 512
hashtable：保存的元素不是整数 || 总数量大于 512
intset 编码的集合结构：
hashtable 编码的集合结构：
编码之间的转换：
原本是 intset 编码的，如果保存的数据不是整数值或者元素数量大于 512，会转换成 hashtable 编码的。
3.5 有序集合 (sortset) 对象
在上面的图我们知道 set 类型有两种编码格式：
ziplist：元素长度小于 64&& 总数量小于 128
skiplist：元素长度大于 64|| 总数量大于 128
ziplist 编码的有序集合结构：
skiplist 编码的有序集合结构：
有序集合 (sortset) 对象同时采用 skiplist 和哈希表来实现：
skiplist 能够达到插入的时间复杂度为 O(logn)，根据成员查分值的时间复杂度为 O(1)
编码之间的转换：
原本是 ziplist 编码的，如果保存的数据长度大于 64 或者元素数量大于 128，会转换成 skiplist 编码的。
3.6Redis 对象一些细节
(1：服务器在执行某些命令的时候，会先检查给定的键的类型能否执行指定的命令。
比如我们的数据结构是 sortset，但你使用了 list 的命令。这是不对的，服务器会检查一下我们的数据结构是什么才会进一步执行命令
(2：Redis 的对象系统带有引用计数实现的内存回收机制。
对象不再被使用的时候，对象所占用的内存会释放掉
(3：Redis 会共享值为 0 到 9999 的字符串对象
(4：对象会记录自己的最后一次被访问时间，这个时间可以用于计算对象的空转时间。
最后
本文主要讲了一下 Redis 常用的数据结构，以及这些数据结构的底层设计是怎么样的。整体来说不会太难，因为这些数据结构我们在学习的过程中多多少少都接触过了，《Redis 设计与实现》这本书写得也足够通俗易懂。
至于我们在使用的时候挑选哪些数据结构作为存储，可以简单看看：
string–> 简单的 key-value
list–> 有序列表(底层是双向链表)–> 可做简单队列
set–> 无序列表(去重)–> 提供一系列的交集、并集、差集的命令
hash–> 哈希表 –> 存储结构化数据
sortset–> 有序集合映射(member-score)–> 排行榜
如果大家有更好的理解方式或者文章有错误的地方还请大家不吝在评论区留言，大家互相学习交流~~~
参考博客：
Redis 简明教程 http://bridgeforyou.cn/2018/05/19/Redis-Tutorial/
五旬大爷教你一窥 redis 之谜 https://zhuanlan.zhihu.com/p/34762100
参考资料：
《Redis 设计与实现》
《Redis 实战》
一个坚持原创的 Java 技术公众号：Java3y，欢迎大家关注
原创技术文章导航：
文章的目录导航(脑图 + 海量视频资源)：https://github.com/ZhongFuCheng3y/3y