1. 前言

简单来说，Redis（Remote Dictionary Server）也是一个数据库，不过和传统数据库不同点在于 Redis 的数据存储在内存中，所以读写速度远超传统数据库（例如 MySQL ），同时因为Key—Value的数据存储形式非常零活，所以Redis被广泛应用在缓存方向，并且能适配各种实战的应用场景。

Redis 提供了多种语言的 API ，比如常见的 Java、C++、Python 等，基本是后端开发中最常用的缓存中间件。

掌握 MySQL 是后端开发的必备技能，掌握 Redis 则是一个简历加分项。

我们在之前的章节对 MySQL 常见的题目进行了剖析， 在本章中我们会介绍 Redis 相关的高频面试题。

2. Redis底层数据结构

面试官提问： 你有看过 Redis 源码吗？Redis 底层是用什么数据结构实现的？

题目解析：

这里谈到的数据结构不是 Redis 的五种对外基本数据结构：String（字符串类型）、Hash（哈希类型）、List（链表类型）、Set（集合类型）、ZSet（有序集合类型），而是更为底层的数据结构实现，例如双向链表、字典、压缩列表等。

Redis 底层是用标准 C 语言编写的，下面我们会结合 C 代码分析。

2.1 SDS 数据结构

2.1.1 定义

字符串是 Redis 中最常用的数据类型。

Redis 里的五种基础数据类型都是以唯一字符串作为 Key，通过这个 Key 映射不同的 Value 数据，不同数据类型的差异在于存储 Value 不同，String 类型的 Value 是字符串，List 类型的 Value 是列表。

Redis 没有使用 C 语言原生的字符数组表示字符串，而是定义了一个字符串结构体 SDS（Simple Dynamic String，简单动态字符串）。

SDS的结构体定义如下：

struct sdshdr{
     //记录buf数组中已使用字节的数量，等于SDS中已使用字符串的长度
     int len;
     //记录buf数组中未使用字节的数量
     int free;
     //字节数组，用于保存字符串
     char buf[];
}

然后候选人可以结合画图的方式解释SDS的数据结构：

​

如上图所示，当前字符串长度len = 4，未使用长度free = 0，buf数组存储的内容是"mooc\0"。

注意：C 语言中的字符串都是以'\0'结尾，并且计算len值时不包含末尾的'\0'；另外，长度为零的数组即char[] buf不占用内存。

其次，我们需要阐述 SDS 数据结构的优点：

2.1.2 常量时间获取字符串长度

对于传统的 C 字符串，如果要获取字符串长度，例如调用strlen()函数，会从头开始遍历字符串直到遇到'\0'，时间复杂度为O(n)；

对于 SDS 数据结构，能直接访问len属性获取字符串长度，时间复杂度为O(1) ，获取字符串长度的操作不会成为 Redis 的性能瓶颈。

2.1.3 避免缓冲区溢出

传统 C 语言字符串不会记录本身长度，在复制字符串的时候，如果分配的内存不够，会造成缓冲区溢出。

SDS 复制字符串时，会首先检查 free 变量，判断内存空间是否符合复制要求，如果不满足的话，会将空间扩展到所需要的程度，再执行复制操作，不存在缓冲区溢出的问题。

2.1.4 减少内存分配次数

传统 C 语言在对字符串进行修改时，会对数组重新分配内存，这个过程可能会涉及操作系统的系统调用，耗时较长。

在 Redis 中， SDS 提供了空间预分配和惰性空间释放两种优化规则：

规则一：空间预分配规则

调用 SDS 的 API 对 SDS 进行修改时，API 不仅会分配本次修改需要的内存空间，还会分配额外的内存空间。

这里遵循的两种定量分配规则：

• sdshdr的len字段值 < 1MB时，会分配和len同样大小的未使用空间；

• sdshdr的len字段值 > 1MB时，会分配1MB的未使用空间。

其中检测是否超过容量的C语言方法：

static int checkStringLength(client *c, long long size) {
    // 字符串长度为512M，如果超过，直接抛出错误，结束函数
    if (size > 512*1024*1024) {
        addReplyError(c,"string exceeds maximum allowed size (512MB)");
        return C_ERR;
    }
    return C_OK;
}

如上图所示，我们在 "mooc" 的基础上添加了’s’的字符，并且预留了一个字符的空间，所以free=1，

规则二：惰性空间释放规则

当调用 SDS API缩短 SDS 字符串时，程序不会立即回收内存空闲的字节，而是使用上述结构体中的free字段将空闲字节记录下来，将来如果有修改操作，则直接使用已分配的空闲内存，避免了重新分配。

2.1.5 二进制安全

SDS可以存储任何二进制数据，包括'\0'，因为判断 SDS 是否达到字符串终点不是通过末尾'\0'判断，而是通过len字段值。

传统 C 语言则是遇到'0'则判定字符串结束，所以传统字符串不能存储图片、视频等文件（遇到编码'\0'则数据会被截断）

3. 小结

本章节介绍了 Redis 最基础的 SDS 数据结构，有两点需要重点关注：

（1）Redis底层对 C 语言自带数据结构进行了封装优化。

（2）Redis 作为内存数据库，不能避免频繁的修改和查询操作，所以在设计最初，各种数据结构和操作实现的核心目的就是为了追求速度，遍历和内存分配等耗时的操作是难以忍受的。