面试：Redis为什么快呢？查询为何会变慢？

欢迎关注公众号【 Ccww技术博客 】，原创技术文章第一时间推出

越努力，越幸运，

本文已收藏在GitHub中JavaCommunity, 里面有面试分享、源码分析系列文章，欢迎收藏，点赞

https://github.com/Ccww-lx/JavaCommunity

在实际开发， Redis 使用会频繁，那么在使用过程中我们该如何正确抉择数据类型呢？哪些场景下适用哪些数据类型。而且在面试中也很常会被面试官问到Redis数据结构方面的问题：

• Redis为什么快呢？

• 为什么查询操作会变慢？

• Redis Hash rehash过程

• 为什么使用哈希表作为Redis的索引

当我们分析理解了 Redis 数据结构，可以为了我们在使用 Redis 的时候，正确抉择数据类型使用，提升系统性能。

Redis 底层数据结构

Redis 是一个 内存 键值 key-value 数据库，且键值对数据保存在 内存 中，因此 Redis 基于内存的数据操作，其效率高，速度快；

其中， Key 是 String 类型， Redis 支持的 value 类型包括了 String 、 List 、 Hash 、 Set 、 Sorted Set 、 BitMap 等。 Redis 能够之所以能够广泛地适用众多的业务场景，基于其多样化类型的 value 。

而 Redis 的 Value 的数据类型是基于为 Redis 自定义的对象系统 redisObject 实现的，

typedef struct redisObject{
//类型
unsigned type:4;
//编码
unsigned encoding:4;
//指向底层实现数据结构的指针
void *ptr;
    ….. 
}

redisObject 除了记录实际数据，还需要额外的内存空间记录数据长度、空间使用等元数据信息，其中包含了 8 字节的元数据和一个 8 字节指针，指针指向具体数据类型的实际数据所在位置：

           

其中， 指针指向的就是基于 Redis 的底层数据结构存储数据的位置， Redis 的底层数据结构： SDS ，双向链表、跳表，哈希表，压缩列表、整数集合实现的。

那么Redis底层数据结构是怎么实现的呢？

Redis底层数据结构实现

我们先来看看 Redis 比较简单的 SDS ,双向链表，整数集合 。

SDS 、双向链表和整数集合

SDS ，使用 len 字段记录已使用的字节数，将获取字符串长度复杂度降低为O(1)，而且 SDS 是 惰性释放空间 的，你 free 了空间，系统把数据记录下来下次想用时候可直接使用。不用新申请空间。

                                   

整数集合，在内存中分配一块地址连续的空间，数据元素会挨着存放，不需要额外指针带来空间开销，其特点为 内存紧凑节省内存空间，查询复杂度为O(1)效率高，其他操作复杂度为O(N)；

双向链表， 在内存上可以为非连续、非顺序空间，通过额外的指针开销前驱/后驱指针串联元素之间的顺序。

其特点为节插入/更新数据复杂度为O(1)效率高，查询复杂度为O(N)；

Hash 哈希表

哈希表，其实类似是一个数组，数组的每个元素称为一个哈希桶，每个哈希桶中保存了键值对数据，且哈希桶中的元素使用 dictEntry 结构，

                                               

因此，哈希桶元素保存的并不是键值对值本身，而是指向具体值的指针， 所以在保存每个键值对的时候会额外空间开销，至少有增加24个字节， 特别是 Value 为 String 的键值对，每一个键值对就需要额外开销24个字节空间。当保存数据小，额外开销比数据还大时，这时为了节省空间，考虑换数据结构。

那来看看全局哈希表全图：

虽然哈希表操作很快，但 Redis 数据变大后，就会出现一个潜在的风险： 哈希表的冲突问题和 rehash 开销问题 ， 这可以解释为什么哈希表操作变慢了？

当往哈希表中写入更多数据时，哈希冲突是不可避免的问题 ， Redis 解决哈希冲突的方式，就是 链式哈希 ，同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接，如图所示：

当哈希冲突也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。

为了解决哈希冲突带了的链过长的问题，进行 rehash 操作 ，增加现有的哈希桶数量，分散单桶元素数量。那么 rehash 过程怎么样执行的呢？

Rehash

为了使 rehash 操作更高效，使用两个全局哈希表：哈希表 1 和哈希表 2，具体如下：

• 将哈希表 2 分配更大的空间，

• 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；

• 释放哈希表 1 的空间

但由于表1和表2在重新映射复制时数据大，如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。

为了避免这个问题，保证 Redi s能正常处理客户端请求， Redis 采用了 渐进式 rehash 。

每处理一个请求时，从哈希表 1 中依次将索引位置上的所有 entries 拷贝到哈希表 2 中，把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

在理解完 Hash 哈希表相关知识点后，看看不常见的压缩列表和跳表。

压缩列表与跳表

压缩列表，在数组基础上，在压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

优点： 内存紧凑节省内存空间，内存中分配一块地址连续的空间，数据元素会挨着存放，不需要额外指针带来空间开销；查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。

跳表，在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示：

比如查询33

特点：当数据量很大时，跳表的查找复杂度为O(logN)。

综上所述，可以得知底层数据结构的时间复杂度：

数据结构类型 时间复杂度 哈希表 O(1) 整数数组 O(N) 双向链表 O(N) 压缩列表 O(N) 跳表 O(logN)

Redis 自定义的对象系统类型即为 Redis 的 Value 的数据类型， Redis 的数据类型是基于底层数据结构实现的，那数据类型有哪些呢？

Redis数据类型

String 、 List 、 Hash 、 Sorted Set 、 Set 比较常见的类型，其与底层数据结构对应关系如下：

数据类型 数据结构 String SDS(简单动态字符串) List 双向链表压缩列表 Hash 压缩列表哈希表 Sorted Set 压缩列表跳表 Set 哈希表整数数组

数据类型对应特点跟其实现的底层数据结构差不多，性质也是一样的,且

String ，基于SDS实现，适用于简单 key-value 存储、 setnx key value 实现分布式锁、计数器(原子性)、分布式全局唯一ID。

List ， 按照元素进入 List 的顺序进行排序的，遵循FIFO(先进先出)规则，一般使用在 排序统计以及简单的消息队列。

Hash ， 是字符串 key 和字符串 value 之间的映射，十分适合用来表示一个对象信息 ，特点添加和删除操作复杂度都是O(1)。

Set ，是 String 类型元素的无序集合，集合成员是唯一的，这就意味着集合中不能出现重复的数据。基于哈希表实现的，所以添加，删除，查找的复杂度都是 O(1)。

Sorted Set ，  是 Set 的类型的升级， 不同的是每个元素都会关联一个 double 类型的分数，通过分数排序，可以范围查询。 

那我们再来看看这些数据类型， Redis Geo 、 HyperLogLog 、 BitMap ？

Redis Geo ， 将地球看作为近似为球体，基于GeoHash 将二维的经纬度转换成字符串，来实现位置的划分跟指定距离的查询。特点一般使用在跟位置有关的应用。

HyperLogLog ， 是一种 概率 数据结构，它使用概率算法来统计集合的近似基数 ， 错误率大概在0.81%。当集合元素数量非常多时，它计算基数所需的空间总是固定的，而且还很小，适合使用做 UV 统计。

BitMap ，用一个比特位来映射某个元素的状态， 只有 0 和 1 两种状态，非常典型的二值状态，且其本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型  ，优势大量节省内存空间，可是使用在二值统计场景。

在理解上述知识后，我们接下来讨论一下根据哪些策略选择相对应的应用场景下的 Redis 数据类型？

选择合适的 Redis 数据类型策略

在实际开发应用中，Redis可以适用于众多的业务场景，但我们需要怎么选择数据类型存储呢？

主要依据就是时间/空间复杂度，在实际的开发中可以考虑以下几个点：

• 数据量，数据本身大小

• 集合类型统计模式

• 支持单点查询/范围查询

• 特殊使用场景

数据量，数据本身大小

当数据量比较大，数据本身比较小，使用 String 就会使用额外的空间大大增加，因为使用哈希表保存键值对，使用 dictEntry 结构保存，会导致保存每个键值对时额外保存 dictEntry 的三个指针的开销，这样就会导致数据本身小于额外空间开销，最终会导致存储空间数据大小远大于原本数据存储大小。

可以使用基于 整数数组 和 压缩列表 实现了 List 、 Hash 和 Sorted Set ，因为 整数数组 和 压缩列表 在内存中都是分配一块地址连续的空间，然后把集合中的元素一个接一个地放在这块空间内，非常紧凑，不用再通过额外的指针把元素串接起来，这就避免了额外指针带来的空间开销。而且采用集合类型时，一个 key 就对应一个集合的数据，能保存的数据多了很多，但也只用了一个 dictEntry ，这样就节省了内存。

集合类型统计模式

Redis 集合类型统计模式常见的有：

• 聚合统计（ 交集、差集、并集统计 ）： 对多个集合进行聚合计算时，可以选择 Set ；

• 排序统计（要求集合类型能对元素保序）： Redis 中 List 和 Sorted Set 是有序集合， List 是按照元素进入 List 的顺序进行排序的， Sorted Set 可以根据元素的权重来排序；

• 二值状态统计（ 集合元素的取值就只有 0 和 1 两种 ）： Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 ， Bitmap通过 BITOP 按位 与、或、异或的操作后使用 BITCOUNT 统计 1 的个数。

• 基数统计（ 统计一个集合中不重复的元素的个数 ）： HyperLogLog 是一种用于统计基数的数据集合类型 ，统计结果是有一定误差的，标准误算率是 0.81% 。需要精确统计结果的话，用 Set 或 Hash 类型。

Set 类型，适用统计用户/好友/关注/粉丝/感兴趣的人集合聚合操作，比如

• 统计手机APP每天的新增用户数

• 两个用户的共同好友

Redis 中 List 和 Sorted Set 是有序集合，使用应对集合元素排序需求 ，比如

• 最新评论列表

• 排行榜

Bitmap 二值状态统计，适用数据量大，且可以使用二值状态表示的统计，比如：

• 签到打卡，当天用户签到数

• 用户周活跃

• 用户在线状态

HyperLogLog 是一种用于统计基数的数据集合类型， 统计一个集合中不重复的元素个数 ，比如

• 统计网页的 UV ， 一个用户一天内的多次访问只能算作一次

支持单点查询/范围查询

Redis 中 List 和 Sorted Set 是有序集合支持范围查询，但是 Hash 是不支持范围查询的

特殊使用场景

消息队列 ，使用 Redis 作为消息队列的实现，要消息的基本要求 消息保序 、 处理重复的消息 和 保证消息可靠性 ，方案有如下：

• 基于 List 的消息队列解决方案

• 基于 Streams 的消息队列解决方案

基于List 基于Strems 消息保序 使用 LPUSH/RPOP 使用 XADD/XREAD 阻塞读取 使用 BRPOP 使用 XREAD block 重复消息处理 生产者自行实现全局唯一ID Streams自动生成全局唯一ID 消息可靠性 使用 BRPOPLPUSH 使用 PENDING List自动留存消息 适用场景 消息总量小 消息总量大，需要消费组形式读取数据

基于位置 LBS 服务 ，使用 Redis 的特定 GEO 数据类型实现， GEO 可以记录经纬度形式的地理位置信息，被广泛地应用在 LBS 服务中。 比如:打车软件是怎么基于位置提供服务的。

总结

Redis 之所以那么快，是因为其基于内存的数据操作和使用 Hash 哈希表作为索引，其效率高，速度快，而且得益于其底层数据多样化使得其可以适用于众多场景，不同场景中选择合适的数据类型可以提升其查询性能。

谢谢各位点赞，没点赞的点个赞支持支持

最后，微信搜《Ccww技术博客》观看更多文章，也欢迎关注一波。