Redis唯快不破的秘密

前言

根据官方数据，Redis 的 QPS 可以达到约 100000（每秒请求数），有兴趣的可以参考官方的基准程序测试《How fast is Redis？》，地址：https://redis.io/topics/benchmarks

完全基于内存实现

内存直接由 CPU 控制，也就是 CPU 内部集成的内存控制器，所以说内存是直接与 CPU 对接，享受与 CPU 通信的最优带宽。Redis 将数据存储在内存中，读写操作不会因为磁盘的 IO 速度限制。

高效的数据结构

MySQL 为了提高检索速度使用了 B+ Tree 数据结构，所以 Redis 速度快应该也跟数据结构有关。Redis 提供给我们使用的 5 种数据类型：String、List、Hash、Set、SortedSet。

在 Redis 中，常用的 5 种数据类型和应用场景如下：

String： 缓存、计数器、分布式锁等。
List： 链表、队列、微博关注人时间轴列表等。
Hash： 用户信息、Hash 表等。
Set： 去重、赞、踩、共同好友等。
Zset： 访问量排行榜、点击量排行榜等。

当然是为了追求速度，不同数据类型使用不同的数据结构速度才得以提升。每种数据类型都有一种或者多种数据结构来支撑，底层数据结构有 6 种。

Redis数据类型与底层数据结构关系

Redis hash 字典

Redis 整体就是一个哈希表来保存所有的键值对，无论数据类型是 5 种的任意一种。哈希表，本质就是一个数组，每个元素被叫做哈希桶，不管什么数据类型，每个桶里面的 entry 保存着实际具体值的指针。

Redis全局哈希表

整个数据库就是一个全局哈希表，而哈希表的时间复杂度是 O(1)，只需要计算每个键的哈希值，便知道对应的哈希桶位置，定位桶里面的 entry 找到对应数据，这个也是 Redis 快的原因之一。

随着写入 Redis 的数据越来越多的时候，哈希冲突不可避免，会出现不同的 key 计算出一样的哈希值。

Redis 通过链式哈希解决冲突：也就是同一个桶里面的元素使用链表保存。但是当链表过长就会导致查找性能变差可能，所以 Redis 为了追求快，使用了两个全局哈希表。用于 rehash 操作，增加现有的哈希桶数量，减少哈希冲突。

开始默认使用 hash 表 1 保存键值对数据，哈希表 2 此刻没有分配空间。当数据越来多触发 rehash 操作，则执行以下操作：

给 hash 表 2 分配更大的空间；
将 hash 表 1 的数据重新映射拷贝到 hash 表 2 中；
释放 hash 表 1 的空间。

值得注意的是，将 hash 表 1 的数据重新映射到 hash 表 2 的过程中并不是一次性的，这样会造成 Redis 阻塞，无法提供服务。

而是采用了渐进式 rehash，每次处理客户端请求的时候，先从 hash 表 1 中第一个索引开始，将这个位置的所有数据拷贝到 hash 表 2 中，就这样将 rehash 分散到多次请求过程中，避免耗时阻塞。

SDS 简单动态字符

字符串结构使用最广泛，通常我们用于缓存登陆后的用户信息，key = userId，value = 用户信息 JSON 序列化成字符串。

C 语言中字符串的获取「MageByte」的长度，要从头开始遍历，直到「\0」为止，对于redis来说，这样是不能容忍的。

C 语言字符串结构与 SDS 字符串结构对比图如下所示：

C 语言字符串与SDS

两者的区别：

SDS有着O(1) 时间复杂度获取字符串长度
空间预分配：SDS 被修改后，程序不仅会为 SDS 分配所需要的必须空间，还会分配额外的未使用空间。分配规则如下：如果对 SDS 修改后，len 的长度小于 1M，那么程序将分配和 len 相同长度的未使用空间。如果对 SDS 修改后 len 长度大于 1M，那么程序将分配 1M 的未使用空间。
惰性空间释放：当对 SDS 进行缩短操作时，程序并不会回收多余的内存空间，而是使用 free 字段将这些字节数量记录下来不释放，后面如果需要 append 操作，则直接使用 free 中未使用的空间，减少了内存的分配。
二进制安全：在 Redis 中不仅可以存储 String 类型的数据，也可能存储一些二进制数据。二进制数据并不是规则的字符串格式，其中会包含一些特殊的字符如 ‘\0’，在 C 中遇到 ‘\0’ 则表示字符串的结束，但在 SDS 中，标志字符串结束的是 len 属性。

zipList 压缩列表

当一个列表只有少量数据的时候，那么 Redis 就会使用压缩列表来做列表键的底层实现。

ziplist 是由一系列特殊编码的连续内存块组成的顺序型的数据结构，ziplist 中可以包含多个 entry 节点，每个节点可以存放整数或者字符串。

struct ziplist<T> {
    int32 zlbytes; // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 元素个数
    T[] entries; // 元素内容列表，挨个挨个紧凑存储
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}