01 什么是 Redis？
官方是这么描述的：
Redis （用 C 语言实现的）是一个开源的，基于内存的数据结构存储，可用作于数据库、缓存、消息中间件。
信息简洁明了，一下就知道了三个点：基于内存、用作缓存、多种数据结构。
的了，那就从这三个方面开始研究呗。
1.0 为什么要用 Redis 做缓存？
上面说了，用作缓存。有些小伙伴可能会问：有 MySQL 数据库就得了呗？干嘛还要缓存？而且为啥要用 Redis 做？Map 不行嘛？
- 第一、二个问题，都知道 MySQL 数据是存在磁盘的，而 CPU 访问磁盘是非常慢的。如果遇到并发高的时候，所有线程每次都要访问磁盘，估计得挂。
到底有多慢？请看链接：zhuanlan.zhihu.com/p/24726196
Redis 和 Map 做下对比，就知道为啥不合适了。
- Map 是本地缓存，如果在多台机器部署，必须每个机器都要复制一份，否则造成缓存不一致；Redis 是分布式缓存，部署在多台机器，也是用的同一份缓存，保持了一致性，问题不大。
- Map 做缓存，数据量大的话会导致 JVM 内存飙升，进而拖垮程序，并且 JVM 挂了，还会导致数据丢失；Redis 可以用更大容量的内存（看你的配置，即几十 G 都没问题）做缓存，并且还可以持久化到磁盘。
02 Redis 的数据结构
你可能第一反应不就 "String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Sorted Set（有序集合）么？"，太简单了，我都会。
老铁你错了，你说的是 Redis 的数据类型只有 5 种，也就是他的表现形式。而我说的数据结构是底层的，有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组，它们的对应关系如下：
由上图可知 String 类型的底层实现只有一种数据结构，而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构都是集合。
看到这里，你可能又有疑问了。这些数据结构都是值的底层实现，键和值本身之间用什么结构组织？
2.0 键和值用什么结构组织？
实际上，Redis 使用了一个哈希表来保存所有键值对。它的存储是以 key-value 的形式的。key 一定是字符串，value 可以是 string、list、hash、set、sortset 中的随便一种。
一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。每个哈希桶中保存了键值对数据，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。这点从下图可以看出：
** 哈希桶中的 entry 元素中保存了 *key 和 value 指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过 value 指针被查找到。
redis 的键值都是 redisObject 对象，即在创建时会生成一个用于键名的 redisObject 对象和一个用于键值的 redisObject 对象。这点从源码也可以看出来：
typedef struct redisObject { // 类型 unsigned type:4; // 编码 unsigned encoding:4; // 指向数据的指针 void *ptr; // 记录对象最后一次被程序访问时间，用于计算空转时长(当前时间-lru) unsigned lru:22; /* lru time (relative to server.lruclock) */ // 引用计数，用于内存回收 int refcount; } robj;
也就是说上图 entry 中的健值指针就分别指向这样一个 redisObject。其中 type、 encoding 和 ptr 是最重要的三个属性。type 记录了对象所保存的值的类型，它的值可能是以下常量的其中一个。
/* * 对象类型 */ #define REDIS_STRING 0 // 字符串 #define REDIS_LIST 1 // 列表 #define REDIS_SET 2 // 集合 #define REDIS_ZSET 3 // 有序集 #define REDIS_HASH 4 // 哈希表
encoding 记录了 对象所保存的值的编码，它的值可能是以下常量的其中一个.
/* * 对象编码 */ #define REDIS_ENCODING_RAW 0 // 编码为字符串 #define REDIS_ENCODING_INT 1 // 编码为整数 #define REDIS_ENCODING_HT 2 // 编码为哈希表 #define REDIS_ENCODING_ZIPMAP 3 // 编码为 zipmap #define REDIS_ENCODING_LINKEDLIST 4 // 编码为双端链表 #define REDIS_ENCODING_ZIPLIST 5 // 编码为压缩列表 #define REDIS_ENCODING_INTSET 6 // 编码为整数集合 #define REDIS_ENCODING_SKIPLIST 7 // 编码为跳跃表
比如，我们在 redis 里面 put ("狗哥",666)，在 redisObject 实际上是这样存放的：
2.1 SDS 简单动态字符串
简单动态字符串 (Simple dynamic string,SDS)
跟传统的 C 语言字符串不一样，Redis 使用了 SDS 来构建自己的字符串对象，源码如下：
struct sdshdr{ // 字节数组，用于保存字符串 char buf[]; // 记录buf数组中已使用的字节数量，也是字符串的长度 int len; // 记录buf数组未使用的字节数量 int free; }
图示：
buf 属性是一个 char 类型的数组，最后一个字节保存了空字符 '\0'，不算入 len 长度。
2.1.0 为什么使用 SDS？
SDS 比 C 字符串好在哪？
- 常数复杂度获取字符串长度：C 字符串不记录长度，统计长度只能逐个遍历字符，复杂度是 O (N)；而 SDS 在 len 属性中记录了自身长度，复杂度仅为 O (1)。
- 不会发生缓冲区溢出：SDS 不会发生溢出的问题，如果修改 SDS 时，空间不足。先会扩展空间，再修改！(内部实现了动态扩展机制)。
- SDS 可以减少内存分配的次数 (空间预分配 & 惰性空间释放)。在扩展空间时，除了分配修改时所必要的空间，还会分配额外的空闲空间 (free 属性)。
- SDS 是二进制安全的，所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据。
2.2 链表
链表，大家都很熟悉了吧？在 Java 中 LinkedList 的底层数据结构就是链表 + 数组实现的。那 Redis 中的链表是怎样的呢？
按照惯例，上源码。它使用 listNode 结构（源码位于 adlist.h）表示链表的每个节点：
typedef strcut listNode{ //前置节点 strcut listNode *pre; //后置节点 strcut listNode *pre; //节点的值 void *value; }listNode
多个 listNode 可以通过 prev 和 next 指针组成一个双向链表，像这样：
节点表示出来了，整个链表又该怎么表示呢？Redis 使用 list 结构（源码位于 adlist.h）来构建链表，上源码：
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.0 Redis 链表的特性
- 双端：有 prev 和 next 两个指针；可以前后移动。
- 无环：链表不闭环，prev 和 next 都指向 null，链表访问以 null 为终点。
- 获取带表头指针、表尾指针、节点数量的时间复杂度均为 O (1)。
- 链表使用 void * 指针来保存节点值，可以保存各种不同类型的值。
2.3 哈希表
哈希表，大家也都不陌生吧？在 Java 中哈希表的底层数据结构就是数组 + 链表实现的。那 Redis 中的哈希表是怎样实现的呢？
按照惯例，上源码。哈希表使用 dictht 结构（源码位于 dict.h）表示哈希表，源码如下：
typedef struct dictht{ // 哈希表数组 dictEntry **table; // 哈希表大小，也即 table 大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于size-1 unsigned long sizemark; // 哈希表已有节点数量 unsigned long used; }dictht
sizemark 和哈希值决定一个键应该被放到 table 数组的那个索引上。PS：就是 Java 中计算哈希值决定位置的方法。
图示一个大小为 4 的空哈希表（不包含任何键值）
哈希表节点使用 dictEntry 结构表示，每个 dictEntry 都保存着一个键值对。源码如下：
typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_tu64; int64_ts64; }v; // 指向下个哈希节点，组成链表 struct dictEntry *next; }dictEntry;
key 解释得很清楚了；说说 v 属性，它 保存着键值对中的值，可以是一个指针，或者是一个 uint64_t 整数，又或者是一个 int64_t 整数。
**next 则是执行下一个哈希表节点的指针，可以将多个哈希值相同的键值对连接在一起作为一个链表，以此来解决键冲突（collision）的问题。**PS：参考 Java 中 HashMap 是怎么解决冲突的。旧文：《HashMap 源码解读》有提过。
图示通过 next 指针把相同索引值的键 k1 和 k0 连接在一起。
为了更好实现 rehash（扩容）；Redis 又在哈希表之上封装了一层，称之为字典。由 dict 结构表示，源码如下：
typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void * privdata; // 哈希表，代表两个哈希表 dictht ht[2]; // rehash索引 // 当rehash不在进行时， 值为 - 1 in trehashidx; /*rehashing not in pro gress if rehashidx==-1*/ }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
type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。
- type 是一个指向 dictType 的指针，每个 dictType 保存了一簇用于操作特定类型键值对的函数，Redis 为用途不同的字典设置不同的类型特定函数
- 而 privdata 则保存了传给类型特定函数的可选参数
- ht 是包含了两个哈希表的数组；ht [0] 存放真实数据，ht [1] 在对 ht [0] 进行 rehash（扩容）时使用。
最终，你会发现其实所谓的字典就是两个哈希表组成的。图式结构如下：
