关于面试:面试Redis为什么快呢查询为何会变慢呢

越致力，越侥幸，
本文已珍藏在 GitHub 中 JavaCommunity, 外面有面试分享、源码剖析系列文章，欢送珍藏，点赞
https://github.com/Ccww-lx/Ja…

在理论开发，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)。

综上所述，能够得悉底层数据结构的工夫复杂度：

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

Redis 数据类型

String、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 的音讯队列解决方案

基于地位 LBS 服务 ，应用Redis 的特定 GEO 数据类型实现，GEO 能够记录经纬度模式的地理位置信息，被宽泛地利用在 LBS 服务中。比方: 打车软件是怎么基于地位提供服务的。

总结

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

谢谢各位点赞，没点赞的点个赞反对反对
最初，微信搜《Ccww 技术博客》观看更多文章，也欢送关注一波。