Redis底层设计与源码解析_hgetall 底层算法

一、Redis的五种基本数据类型

Redis有以下这五种基本类型：

• String（字符串）
• Hash（哈希）
• List（列表）
• Set（集合）
• zset（有序集合）

它还有三种特殊的数据结构类型

• Geospatial
• Hyperloglog
• Bitmap

1.1 String（字符串）

简介：String是Redis最基础的数据结构类型，它是二进制安全的，可以存储图片或者序列化的对象，值最大存储为512M

简单使用举例：set key value、get key等

应用场景：共享session、分布式锁，计数器、限流。

内部编码有3种，int（8字节长整型）/embstr（小于等于39字节字符串）/raw（大于39个字节字符串）

C语言的字符串是char[]实现的，而Redis使用SDS（simple dynamic string） 封装，

SDS源码如下： 

struct sdshdr{
  unsigned int len; // 标记buf的长度
  unsigned int free; //标记buf中未使用的元素个数
  char buf[]; // 存放元素的坑
}

SDS结构图如下：

Redis为什么选择SDS结构，而C语言原生的 char[]不香吗？

举例其中一点，SDS中，O(1)时间复杂度，就可以获取字符串长度；而C 字符串，需要遍历整个字符串，时间复杂度为O(n)

 1.2 Hash（哈希）

简介：在Redis中，哈希类型是指v（值）本身又是一个键值对（k-v）结构

简单使用举例：hset key field value 、hget key field

内部编码：ziplist（压缩列表） 、hashtable（哈希表）

应用场景：缓存用户信息等。

注意点：如果开发使用hgetall，哈希元素比较多的话，可能导致Redis阻塞，可以使用hscan。而如果只是获取部分field，建议使用hmget。

字符串和哈希类型对比如下图：

 

 1.3 List（列表）

简介：列表（list）类型是用来存储多个有序的字符串，一个列表最多可以存储2^32-1个元素。

简单实用举例： lpush  key  value [value ...] 、lrange key start end

内部编码：ziplist（压缩列表）、linkedlist（链表）

应用场景： 消息队列，文章列表,

一图看懂list类型的插入与弹出：

 

list应用场景参考以下：

lpush + lpop = Stack（栈）
lpush + rpop = Queue（队列）
lpsh + ltrim = Capped Collection（有限集合）
lpush + brpop = Message Queue（消息队列）

 1.4 Set（集合）

简介：集合（set）类型也是用来保存多个的字符串元素，但是不允许重复元素

简单使用举例：sadd key element [element ...]、smembers key

内部编码：intset（整数集合）、hashtable（哈希表）

注意点：smembers和lrange、hgetall都属于比较重的命令，如果元素过多存在阻塞Redis的可能性，可以使用sscan来完成。

应用场景： 用户标签、生成随机数抽奖、社交需求。

1.5 Zset （有序集合）

简介：已排序的字符串集合，同时元素不能重复

简单格式举例：zadd key score member [score member ...]，zrank key member

底层内部编码：ziplist（压缩列表）、skiplist（跳跃表）

应用场景：排行榜，社交需求（如用户点赞）。

 1.6 Redis三种特殊数据类型

Geospatial：Redis3.2推出的，地理位置定位，用于存储地理位置信息，并对存储的信息进行操作。

HyperLogLog：用来做基数统计算法的数据结构，如统计网站的UV。

Bitmaps ：用一个比特位来映射某个元素的状态，在Redis中，它的底层是基于字符串类型实现的，可以把bitmaps成作一个以比特位为单位的数组

二、Redis为什么这么快

 2.1 基于内存存储实现

我们都知道内存读写是比在磁盘快很多的，Redis基于内存存储实现的数据库，相对于数据存在磁盘的MySQL数据库，省去磁盘I/O的消耗。

 2.2 高效的数据结构

我们知道，Mysql索引为了提高效率，选择了B+树的数据结构。

其实合理的数据结构，就是可以让你的应用/程序更快。

先看下Redis的数据结构&内部编码图：

 

2.3 SDS简单动态字符串

字符串长度处理：

Redis获取字符串长度，时间复杂度为O(1)，而C语言中，需要从头开始遍历，复杂度为O(n);

空间预分配：

字符串修改越频繁的话，内存分配越频繁，就会消耗性能，而SDS修改和空间扩充，会额外分配未使用的空间，减少性能损耗。

惰性空间释放：

SDS 缩短时，不是回收多余的内存空间，而是free记录下多余的空间，后续有变更，直接使用free中记录的空间，减少分配。

二进制安全：

Redis可以存储一些二进制数据，在C语言中字符串遇到'\0'会结束，而 SDS中标志字符串结束的是len属性。

2.4 字典

Redis 作为 K-V 型内存数据库，所有的键值就是用字典来存储。

字典就是哈希表，比如HashMap，通过key就可以直接获取到对应的value。

而哈希表的特性，在O(1)时间复杂度就可以获得对应的值。

 2.5 跳跃表

 

1. 跳跃表是Redis特有的数据结构，就是在链表的基础上，增加多级索引提升查找效率。

2. 跳跃表支持平均 O(logN)，最坏 O(N)复杂度的节点查找，还可以通过顺序性操作批量处理节点。

2.6 合理的数据编码

Redis 支持多种数据数据类型，每种基本类型，可能对多种数据结构。什么时候，使用什么样数据结构，使用什么样编码，是redis设计者总结优化的结果。

String：

如果存储数字的话，是用int类型的编码；如果存储非数字，小于等于39字节的字符串，是embstr；大于39个字节，则是raw编码。

List：

如果列表的元素个数小于512个，列表每个元素的值都小于64字节（默认），使用ziplist编码，否则使用linkedlist编码

Hash：

哈希类型元素个数小于512个，所有值小于64字节的话，使用ziplist编码，否则使用hashtable编码。

Set：

如果集合中的元素都是整数且元素个数小于512个，使用intset编码，否则使用hashtable编码。

Zset：

当有序集合的元素个数小于128个，每个元素的值小于64字节时，使用ziplist编码，否则使用skiplist（跳跃表）编码。

2.7 合理的线程模型

2.7.1 I/O多路复用

多路I/O复用技术可以让单个线程高效的处理多个连接请求，而Redis使用用epoll作为I/O多路复用技术的实现。

并且，Redis自身的事件处理模型将epoll中的连接、读写、关闭都转换为事件，不在网络I/O上浪费过多的时间。

2.7.2 什么是I/O多路复用

I/O ：

网络 I/O。

多路 ：

多个网络连接。

复用：

复用同一个线程。

IO多路复用其实就是一种同步IO模型，它实现了一个线程可以监视多个文件句柄；

一旦某个文件句柄就绪，就能够通知应用程序进行相应的读写操作；而没有文件句柄就绪时，就会阻塞应用程序，交出cpu。

2.7.3 单线程模型

Redis是单线程模型的，而单线程避免了CPU不必要的上下文切换和竞争锁的消耗。

也正因为是单线程，如果某个命令执行过长（如hgetall命令），会造成阻塞。

Redis是面向快速执行场景的数据库。所以要慎用如smembers和lrange、hgetall等命令。

Redis 6.0 引入了多线程提速，它的执行命令操作内存的仍然是个单线程。

2.8 虚拟内存机制

Redis直接自己构建了VM机制 ，不会像一般的系统会调用系统函数处理，会浪费一定的时间去移动和请求。

2.8.1 Redis的虚拟内存机制是啥呢？

虚拟内存机制就是暂时把不经常访问的数据(冷数据)从内存交换到磁盘中，从而腾出宝贵的内存空间用于其它需要访问的数据(热数据)。

通过VM功能可以实现冷热数据分离，使热数据仍在内存中、冷数据保存到磁盘。这样就可以避免因为内存不足而造成访问速度下降的问题。

三、Redis过期策略和内存淘汰策略

3.1 Redis的过期策略

我们在set key的时候，可以给它设置一个过期时间，比如expire key 60。指定这key60s后过期，60s后，redis是如何处理的嘛？

我们先来介绍几种过期策略：

3.1.1 定时过期

每个设置过期时间的key都需要创建一个定时器，到过期时间就会立即对key进行清除。该策略可以立即清除过期的数据，对内存很友好；

但是会占用大量的CPU资源去处理过期的数据，从而影响缓存的响应时间和吞吐量。

3.1.2 惰性过期

只有当访问一个key时，才会判断该key是否已过期，过期则清除。该策略可以最大化地节省CPU资源，却对内存非常不友好。

极端情况可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存。

3.1.3 定期过期

每隔一定的时间，会扫描一定数量的数据库的expires字典中一定数量的key，并清除其中已过期的key。该策略是前两者的一个折中方案。

通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得CPU和内存资源达到最优的平衡效果。

expires字典会保存所有设置了过期时间的key的过期时间数据，其中，key是指向键空间中的某个键的指针，value是该键的毫秒精度的unix时间戳表示的过期时间。

键空间是指该Redis集群中保存的所有键。

Redis中同时使用了惰性过期和定期过期两种过期策略。

1. 假设Redis当前存放30万个key，并且都设置了过期时间，如果你每隔100ms就去检查这全部的key，CPU负载会特别高，最后可能会挂掉。

2. 因此，redis采取的是定期过期，每隔100ms就随机抽取一定数量的key来检查和删除的。

3. 但是呢，最后可能会有很多已经过期的key没被删除。这时候，redis采用惰性删除。在你获取某个key的时候，redis会检查一下，这个key如果设置了过期时间并且已经过期了，此时就会删除。

但是呀，如果定期删除漏掉了很多过期的key，然后也没走惰性删除。就会有很多过期key积在内存内存，直接会导致内存爆的。

或者有些时候，业务量大起来了，redis的key被大量使用，内存直接不够了，运维小哥哥也忘记加大内存了。

难道redis直接这样挂掉？不会的！Redis用8种内存淘汰策略保护自己~

3.2 Redis内存淘汰策略

全局的键空间选择性移除

noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。

allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。（这个是最常用的）

allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。

设置过期时间的键空间选择性移除

volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。

volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。

volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。

四、Redis的持久化机制

 Redis持久化机制

Redis是基于内存的非关系型K-V数据库，既然它是基于内存的，如果Redis服务器挂了，数据就会丢失。

为了避免数据丢失了，Redis提供了持久化，即把数据保存到磁盘。

Redis提供了RDB和AOF两种持久化机制，

它持久化文件加载流程如下：

4.1 RDB

RDB，就是把内存数据以快照的形式保存到磁盘上。

什么是快照?

可以这样理解，给当前时刻的数据，拍一张照片，然后保存下来。

RDB持久化，是指在指定的时间间隔内，执行指定次数的写操作，将内存中的数据集快照写入磁盘中，它是Redis默认的持久化方式。

执行完操作后，在指定目录下会生成一个dump.rdb文件，Redis 重启的时候，通过加载dump.rdb文件来恢复数据。

RDB触发机制主要有以下几种：

 

RDB的优点

适合大规模的数据恢复场景，如备份，全量复制等

RDB缺点

没办法做到实时持久化/秒级持久化。

新老版本存在RDB格式兼容问题

4.2 AOF

AOF（append only file） 持久化，采用日志的形式来记录每个写操作，追加到文件中，重启时再重新执行AOF文件中的命令来恢复数据。

它主要解决数据持久化的实时性问题。默认是不开启的。

AOF的工作流程如下：

AOF的优点

数据的一致性和完整性更高

AOF的缺点

AOF记录的内容越多，文件越大，数据恢复变慢。

视频教程、Redis常见题、Redis 常见面试题（2020最新版）、Redis五种数据类型底层原理、深入理解Redis底层数据结构、深入了解Redis底层数据结构 - 简书、Redis底层数据结构 - 简书、

redis原理之数据结构 - 简书、redis的5种数据结构及其底层实现原理