提到 Redis，我想大家并不陌生，基本上每个项目中都会有它的身影出现。作为一款性能卓越的中间件，其功能强大，在系统中经常扮演着十分重要的角色，像缓存、分布式锁和消息队列等，都是我们所熟知的功能。Redis 在我们的项目中频繁出现的原因，主要是它可以提升系统的性能，支撑起系统的高并发。那么 Redis 这么优秀的原因是什么呢？这时我们可能会想到它基于内存的存储介质，多路复用的IO方式，以及主模块的单线程模型等等，但往往忽视了一点，就是 Redis 在底层数据结构上的实现。
当提及 Redis 的数据结构，我们一般会想到 STRING、LIST、SET、ZSET、HASH等，没错，这些在我们平时使用 Redis 的过程中，是直接能够感知到的数据结构。不过，这仅仅是从使用者的角度去看，如果从内部实现角度，这些高层的数据结构还依赖于更底层的实现，在 Redis 对象系统的实现源码中，就可以找到底层数据结构的编码，如下所示。
注：若没作说明，本文源码参考 Redis 6.0.0版本。

编码常量	常量值	编码对应的底层数据结构
OBJ_ENCODING_RAW	0	简单动态字符串
OBJ_ENCODING_INT	1	long类型的整数
OBJ_ENCODING_HT	2	字典
OBJ_ENCODING_ZIPMAP	3	压缩映射
OBJ_ENCODING_LINKEDLIST	4	双端链表
OBJ_ENCODING_ZIPLIST	5	压缩列表
OBJ_ENCODING_INTSET	6	整数集合
OBJ_ENCODING_SKIPLIST	7	跳跃表和字典
OBJ_ENCODING_EMBSTR	8	embstr编码的简单动态字符串
OBJ_ENCODING_QUICKLIST	9	快表
OBJ_ENCODING_STREAM	10	流

下面，我们依次介绍下 Redis 的底层数据结构，来看看它们是如何实现的。
简单动态字符串 Redis 是采用 C 语言实现的，但 Redis 并没有直接使用 C 语言中传统的字符串表示，而是自己构建了一个名为简单动态字符串（simple dynamic string，SDS）的抽象类型，在 Redis 的不同版本中，其实现也是不同的，我们先来看一下 2.8 版本的实现。

struct sdshdr { int len; int free; char buf[]; };

其中：

属性	说明
len	记录 buf 数组中已使用字节的数量，等于 SDS 所保存字符串的长度
free	记录 buf 数组中未使用字节的数量
buf	字节数组，用于保存字符串，遵循 C 字符串以空字符结尾的惯例，但保存空字符的 1 字节空间不计算在 len 属性里

与C字符串的比较
那就有一个问题，Redis 为什么构建了自己的字符串类型，它与 C 字符串的区别在哪，有着什么样的优势呢，下面我们就来看一下。

1. 降低获取字符串长度的复杂度

• C 字符串：获取字符串长度时，需要对字符串进行遍历，时间复杂度为 O(n)。
• SDS：其实现中通过 len 属性记录了字符串的长度，使得获取字符串长度的时间复杂度降低到了O(1)，这就确保了获取字符串长度不会成为 Redis 的性能瓶颈。

2. 拼接操作安全性

• C 字符串：进行拼接操作时，使用者需要先检查是否分配了足够的空间，如果忘记了，就有可能造成缓冲区溢出，导致其它空间的值被修改。
• SDS：进行字符串修改时，API 会先检查是否有足够的空间，不满足的话，会按照一定的策略进行空间扩展，然后再执行修改操作，这样就杜绝了缓冲区的溢出。

3. 减少内存重分配的次数

对于字符串，我们经常会进行修改操作，变长或者变短，这会涉及到内存重分配，可能需要执行系统调用，如果修改操作执行得比较频繁，过多的内存重分配操作就会影响到系统的性能。

• C 字符串：修改N次字符串，需要执行 N 次内存重分配。
• SDS：通过 free 属性实现了空间预分配和惰性空间释放，将修改 N 次字符串，需要执行内存重分配的次数从 N 次降低为最多 N 次。
  a. 空间预分配：当要对字符串的长度进行扩展时，如果空间不够，SDS 是会通过一定的策略分配更多的空间，将未使用的空间记录到 free 属性中，这样就避免下次扩展时再进行申请空间的操作。
  b. 惰性空间释放：当要缩短字符串时，SDS 并不会释放掉其对应的空间，而是记录到 free 属性中，以便于下次扩展空间时使用。

4. 二进制安全

• C 字符串：字符必须符合某种编码，并且必须以空字符结尾，这就导致其他位置不能出现空字符，限制了 C 字符串保存的内容只能是文本数据，不能保存图片、音频等二进制数据。
• SDS：虽然也以空字符结尾，但它是以 len 属性的值来判断是否结束，所以可以保存任何格式的二进制数据，数据在写入时是什么样，被读取时就是什么样。

5. 兼容性

SDS 遵循 C 字符串以空字符结尾的惯例，这样就可以重用一部分 C 字符串的库函数。
版本优化
上面我们分析了 Redis 为何设计了自己的字符串类型，但你以为这样就可以了吗，在 3.2 及之后的版本中，Redis 又对 SDS 进行了升级，下面我们来看一下。

struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; };

其中：

属性	说明
len	记录 buf 数组中已使用字节的数量，等于 SDS 所保存字符串的长度
alloc	字节数组的总长度，alloc - len 就是之前版本中的 free
flags	类型标识，低三位存储类型，高5位预留，在 sdshdr5 中存储已使用长度
buf	字节数组，用于保存字符串，遵循 C 字符串以空字符结尾的惯例，但保存空字符的 1 字节空间不计算在 len 和 alloc 属性里

文章图片

所做优化

• 3.0 及之前的版本，不同的字符串占用的头部都是相同的，对于短字符串来说，很浪费空间，所以 3.2 及之后的版本针对不同长度的字符串进行了类型优化，可以节省更多内存空间。
• 取消了编译时的对齐填充，让编译器以紧凑的形式分配内存，进一步节省了内存空间；而且也可以方便地进行一些操作，比如，要得到该 SDS 的类型，直接向低地址偏移 1 个字节来获取 flags 字段等。

使用场景
Redis 中字符串对象的底层实现之一就使用了 SDS，像 AOF 模块中的 AOF 缓冲区，以及客户端状态中的输入缓冲区，也是由SDS实现的。前言中列举的 OBJ_ENCODING_EMBSTR、OBJ_ENCODING_INT 也是字符串对象的底层实现，这两种底层结构会在讲解 Redis 的对象系统中讲解。
链表 链表提供了高效的节点重排能力，以及顺序性的节点访问方式，而且增删节点只需要修改前后节点的指针，非常方便，可以灵活地调整链表的长度。链表是一种非常常见的数据结构，像高级编程语言中都有它的身影，比如 Java 中的 LinkedList，但 C 语言中却没有内置自己的链表实现，所以 Redis 自己实现了一个链表结构。
实现

typedef struct list { listNode *head; // 表头节点 listNode *tail; // 表尾节点 void *(*dup)(void *ptr); // 节点值复制函数 void (*free)(void *ptr); // 节点值释放函数 int (*match)(void *ptr, void *key); // 节点值对比函数 unsigned long len; // 链表包含的节点数量 } list; typedef struct listNode { struct listNode *prev; // 前置节点 struct listNode *next; // 后置节点 void *value; // 节点值 } listNode;

文章图片

Redis实现的链表可以总结如下：

• 双端无环链表，以 O(1) 的时间复杂度获取某个节点的前置节点和后置接点；表头的前置节点和表尾的后置节点为 null，对链表的访问以 null 结束。
• 以 O(1) 的时间复杂度获取表头节点和表尾节点。
• 以 O(1) 的时间复杂度获取链表的长度。
• 节点使用 void* 指针保存节点值，具有多态性，可以用于保存各种不同类型的值，可以通过 list 结构的三个属性（dup、free、match）设置类型特定函数。

使用场景
Redis 中列表对象的底层实现之一就使用了链表，但在 Redis 3.2 之后，被快表取代，除了这个，像 Redis 中的发布与订阅、慢查询、监视器等功能也使用到了链表，以及 Redis 服务器本身的客户端状态信息，以及客户端的输出缓冲区，也都使用到了链表。
字典 同链表一样，C 语言没有像 Java 等高级编程语言一样内置自己的字典实现，所以 Redis 构建了自己的字典实现。Redis 的字典是一个用于维护 key 和 value 映射关系的数据结构，底层使用哈希表实现，一个哈希表里可以有多个哈希节点，每个哈希节点保存了一个键值对。
实现

// 字典结构定义 typedef struct dict { // 类型特定函数 dictType *type; // 私有数据，保存了需要传给类型特定函数的可选参数 void *privdata; // 哈希表 dictht ht[2]; // rehash索引 当没有进行rehash是，值为 -1 long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */ } dict; // 类型特定函数结构定义 typedef struct dictType { // 计算哈希值的函数 uint64_t (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj); } dictType; // 哈希表结构定义 typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值，总是等于 size - 1 unsigned long sizemask; // 哈希表已有节点的数量 unsigned long used; } dictht; // 哈希表节点结构定义 typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; double d; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;

文章图片

从上面字典的结构定义，可以看出，它类似 Java 中的 HashMap。谈到哈希，总会伴随一些问题的出现，比如，采用的哈希算法，哈希冲突的解决，重哈希等问题，下面我们来看下 Redis 设计的字典是如何解决这些问题的。
哈希算法
Redis 使用的哈希算法为 MurmurHash 算法；其索引值的计算，依赖于哈希值和 sizemask 属性。当给定一个 KV 值时，其索引值的计算过程如下：

• 首先根据类型特定函数中设置的哈希函数，计算出 key 的哈希值：hash = dict -> type -> hashFunction(key)
• 然后再根据哈希值和 sizemask 属性，计算出索引值：index = hash & dict -> ht[x].sizemask

哈希冲突
从哈希表节点结构定义中，可以看出，Redis 字典解决哈希冲突的方法为链地址法，因为哈希表节点中没有指向链表表尾的指针，所以采用的是头插法，也就是后插入的节点在前面。
rehash
随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，这时其负载因子可能会在一个不合理的范围内，太多就会造成哈希冲突的增加，影响查询的效率，太低就会造成空间存储效率的下降，因此当负载因子超过设定的阈值，哈希表就会进行相应的扩展或者收缩。其中，哈希表的负载因子计算方式为：load_factor = ht[0].used / ht[0].size。
rehash的条件

• 服务器目前没有活动着的保存 RDB、AOF 重写或者 Redis 加载的模块派生的子进程，比如执行 BGSAVE 或者 BGREWRITEAOF 等命令时，并且负载因子大于等于 1，执行扩展操作。
• 如果存在（1）中所述的进程，比如服务器正在执行 BGSAVE 或者 BGREWRITEAOF 命令，并且负载因子大于等于 5，执行扩展操作。
• 哈希表的负载因子小于 0.1 时，会执行收缩操作。

可以看出，当 BGSAVE 或者 BGREWRITEAOF 命令执行时，负载因子的阈值会变大，这是因为这两个命令需要创建当前服务器进程的子进程，而大多数操作都采用写时复制来优化子进程的使用效率，所以这里调整阈值上限，可以避免不必要的内存写入操作，最大限度地节约内存，这一点可以从源码中得知。

/* This function is called once a background process of some kind terminates, * as we want to avoid resizing the hash tables when there is a child in order * to play well with copy-on-write (otherwise when a resize happens lots of * memory pages are copied). The goal of this function is to update the ability * for dict.c to resize the hash tables accordingly to the fact we have o not * running childs. */ void updateDictResizePolicy(void) { if (!hasActiveChildProcess()) dictEnableResize(); else dictDisableResize(); }/* Return true if there are no active children processes doing RDB saving, * AOF rewriting, or some side process spawned by a loaded module. */ int hasActiveChildProcess() { return server.rdb_child_pid != -1 || server.aof_child_pid != -1 || server.module_child_pid != -1; }

那 rehash 的扩展和收缩操作的空间是怎么来决定的呢？

• 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n；
• 如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n。

Redis 在执行 rehash 时，也是比较特别的，它并不是一次性、集中式的完成的，而是分多次、渐进式地完成。这样做的原因在于，如果哈希表中只有很少的键值对，那么可以瞬间将 ht[0] 中的所有数据转移到 h[1] 中，但如果数据的量级达到了百万千万或者亿呢，那么一次性的转移对于 Redis 将是个灾难。这时，rehashidx 这个属性就有了用武之地，当执行 rehash 时，它会记录 rehash 的进度，每次对字典执行添加、删除、查找或者更新时，程序除了会执行指定的操作外，还会将 rehashidx 索引上的键值对重新哈希到 ht[1] 中。特别的，在执行 rehash 期间，添加操作会把新的键值对直接放到 h[1] 中。
使用场景
Redis 中的哈希对象的底层实现之一就是字典，当包含的键值对比较多，或者键值对中的元素都是比较长的字符串时，Redis 就会使用字典作为哈希对象的底层实现。还有一个重要的用途就是，我们通过 Redis 提供的 API 操作数据时，数据存放的数据结构也是字典。
（本文作者：李强）
【Redis-数据结构详解（上）】

本文系哈啰技术团队出品，未经许可，不得进行商业性转载或者使用。非商业目的转载或使用本文内容，敬请注明“内容转载自哈啰技术团队”。

推荐阅读

• 

  什么是对公负债业务
• 

  做生鲜电商需要办什么营业执照
• 

  威能壁挂炉代码百度如何解决
• 

  拍鸟用什么相机好
• 

  荒野行动物品怎么拆分 如何分开扔掉道具
• 

  黄雅琼个人资料介绍 黄雅琼个人资料介绍
• 

  怎样做稻谷酒
• 

  天山雪菊哪里买 天山雪菊多少钱才能买到
• 

  鹅蛋和什么东西不能吃
• 

  电池容量|骁龙870基本“零差评”，这四款价格两千左右，入手用三年
• 

  mongodb数据库迁移到另一台服务器 mongodb 迁移数据
• 

  紫叶草怎么种植 紫叶草怎么养
• 

  补办车牌号一般几天可以下来
• 

  3m汽车膜分几个档次 汽车贴膜什么牌子好
• 

  前端|实习生 Git 不熟练，还没脸去问是种什么体验
• 

  开发转数据分析,数据分析好还是大数据开发好
• 

  熊童子多肉服盆的注意事项有哪些 多肉熊童子用什么盆好看
• 

  地板出汗怎么办 地板如何去汗，地板如何去汗渍
• 

  冠状沟白色污垢是什么
• 

  mysql中的锁指的是什么 mysql导致锁的原因

• mysql|mysql 分区表 归档_详解 MySQL 数据库冷数据归档
• 内网渗透|内网渗透---反弹shell详解（内有各种姿势的详细过程）
• Datenlord | Rust 语言无锁数据结构的内存管理
• Go类型安全的HTTP请求示例详解
• SpringBoot工程打包与运行的实现详解
• java内部类的最详细详解
• 详解SpringBoot启动代码和自动装配源码分析
• 数据结构|Map和Set
• 笔记|Redis-redis概念、配置、Sentinel高可用
• linux|HTTP 协议详解 —— URI、HTTP protocol、HTTP headers