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（扩容）时使用。

最终，你会发现其实所谓的字典就是两个哈希表组成的。图式结构如下：