Redis

基础类型

字符串（String）

在 Redis 中，字符串是最基本的数据类型，可以用来存储文本或二进制数据（如图片或序列化的对象），支持最大容量为 512 MB。

底层实现：Simple Dynamic String (SDS)

字符串在 Redis 中使用的是 Simple Dynamic String（SDS）作为底层实现，而不是标准的 C 字符串。SDS 提供了以下几个优点：

• 长度预存储：

  • SDS 结构中包含了字符串的当前长度，这避免了使用类似 strlen 这样的函数来计算长度，从而使得长度获取操作的时间复杂度为 O(1)。

• 空间预分配：

  • 当对一个 SDS 进行扩展操作时，Redis 不仅为所需的空间分配内存，还会根据条件额外分配未使用的空间（overallocation）。这个预分配的策略减少了连续执行多次字符串追加时的内存重分配次数。

• 惰性空间释放：

  • 当对 SDS 进行缩减操作时，Redis 并不立即使用 realloc 释放多余的内存，而是保留这部分内存供未来使用。只有在特定情况下，例如内存达到一定使用阈值，Redis 才会真正释放内存。

• 二进制安全：

  • SDS 保留和使用自己的长度属性，不依赖于空字符作为字符串的结束标志，因此可以安全地存储任何二进制数据，包括空字符。

• 兼容部分 C 字符串函数：

  • SDS 保持与 C 字符串的部分兼容性，结尾处有一个空字符，使得可以使用一部分标准的 C 字符串函数而不需要修改。

散列（Hash）

Redis 的散列可以看作是键值对的集合，适用于存储对象的属性和它们的值。例如，你可以用散列来存储用户的用户名、密码、邮箱等信息。

底层实现：压缩列表（ziplist）和哈希表（hashtable）

Redis 根据散列中元素的数量和元素的大小选择不同的底层实现：

• 压缩列表（ziplist）：

  • 当散列中的键值对数量较少且存储的数据较小时，Redis 使用压缩列表来存储散列。压缩列表是一个紧凑的数据结构，它将所有元素紧挨着存储在一块连续的内存区域中。

  • 压缩列表的优点是内存使用效率高，因为它减少了指针的使用和内存碎片。然而，因为它是线性的数据结构，插入和删除操作特别是在列表的中间部分可能较慢。

• 哈希表（hashtable）：

  • 当散列的键值对数量增加或单个键值对的大小变大时，Redis 会将底层实现从压缩列表转换为哈希表。哈希表通过键的哈希值来快速定位其对应的值，支持平均常数时间复杂度的访问、插入和删除操作。

  • 哈希表由数组和链表组成，数组的每个槽位（slot）都指向一个链表（或者为空）。链表用于解决哈希冲突，即不同的键经过哈希函数处理后可能得到相同的哈希值。

转换机制

• Redis 会根据散列操作的使用模式自动在压缩列表和哈希表之间转换。例如，如果一个散列是用压缩列表实现的，但由于添加了过多元素或某些元素太大，使得压缩列表不再是最优选择，Redis 就会将其内部结构转换为哈希表。

列表（List）

Redis 列表是一种按顺序存储的字符串集合，可以用来实现栈、队列或双端队列。列表中的每个元素都是一个字符串。

底层实现：压缩列表（ziplist）和双向链表（linked list）

Redis 列表根据元素数量和元素大小选择不同的底层实现：

• 压缩列表（ziplist）：

  • 当列表中的元素数量较少或每个元素的长度较短时，Redis 使用压缩列表作为底层实现。压缩列表将所有元素紧凑地存储在一块连续的内存区域中，以减少内存消耗。

  • 压缩列表的优点是内存使用效率高，适合存储小规模的数据。然而，由于其线性结构，对于中间位置的插入和删除操作性能较差。

• 双向链表（linked list）：

  • 当列表中的元素数量较多或元素较大时，Redis 使用双向链表作为底层实现。双向链表中的每个节点都包含一个指向前一个节点和后一个节点的指针。

  • 双向链表的优点是可以高效地进行插入和删除操作，无论是在列表的头部、尾部还是中间位置。此外，双向链表可以方便地实现从两端操作列表（如 LPUSH 和 RPUSH 操作）。

转换机制

• Redis 会根据列表的使用模式自动在压缩列表和双向链表之间转换。例如，如果一个列表最初是用压缩列表实现的，但随着元素数量增加或元素大小变大，压缩列表不再适用，Redis 就会将其内部结构转换为双向链表。

集合（Set）

Redis 集合是一种无序的字符串集合，集合中的每个元素都是唯一的。它可以高效地进行添加、删除、查找和集合间的操作（如交集、并集、差集等）。

底层实现：整数集合（intset）和哈希表（hashtable）

Redis 集合根据存储的元素类型和数量选择不同的底层实现：

• 整数集合（intset）：

  • 当集合中的所有元素都是整数且数量较少时，Redis 使用整数集合作为底层实现。整数集合是一种紧凑的、有序的、存储整数值的数组。

  • 整数集合的优点是内存使用效率高，适用于存储小规模的整数集合。由于其有序性，可以通过二分查找进行快速的查找操作。

• 哈希表（hashtable）：

  • 当集合中的元素数量较多或包含非整数元素时，Redis 使用哈希表作为底层实现。哈希表通过键的哈希值来快速定位其对应的值，支持平均常数时间复杂度的添加、删除和查找操作。

  • 哈希表由数组和链表组成，数组的每个槽位（slot）都指向一个链表（或者为空）。链表用于解决哈希冲突，即不同的键经过哈希函数处理后可能得到相同的哈希值。

转换机制

• Redis 会根据集合操作的使用模式自动在整数集合和哈希表之间转换。例如，如果一个集合最初是用整数集合实现的，但由于添加了非整数元素或元素数量过多，使得整数集合不再适用，Redis 就会将其内部结构转换为哈希表。

有序集合（Sorted Set）

Redis 有序集合是一种带有分数的字符串集合。每个元素都有一个关联的分数，Redis 使用分数来对集合中的元素进行排序。有序集合非常适合需要按顺序访问数据的场景，比如排行榜、带有时间戳的日志等。

底层实现：跳表（skiplist）和哈希表（hashtable）

调表设计原理请参考这里

Redis 有序集合的底层实现是跳表和哈希表的组合：

• 跳表（skiplist）：

  • 跳表是一种用于维护有序数据的结构。它通过多层次的链表结构来实现高效的范围查询和有序遍历操作。

  • 在跳表中，底层是一个包含所有元素的有序链表。上层链表以更大的步长跳跃元素，使得查找操作能够跳过不必要的元素，从而加快查找速度。

  • 跳表适用于需要快速范围查询和按顺序访问元素的场景，能在 O(log n) 时间内完成插入、删除和查找操作。

• 哈希表（hashtable）：

  • 为了快速定位每个元素的分数，Redis 使用哈希表来存储元素和分数的映射关系。

  • 哈希表通过键的哈希值来快速定位元素，支持常数时间复杂度的分数查找和更新操作。

  • 这种双重结构使得有序集合能够高效地支持按分数查询、范围查询以及按分数更新元素。

Redis 的对象处理机制以及数据库的实现原理

对象处理机制

Redis 使用 redisObject 结构体管理所有的数据类型。每个 redisObject 包含以下信息：

• 类型：表示数据类型，如字符串、列表、集合、散列和有序集合。

• 编码：表示数据的存储方式，如字符串可以使用简单动态字符串（SDS）编码或整数编码。

• 引用计数：用于管理对象的内存生命周期，引用计数为零时对象可被释放。

• 最后访问时间：用于实现 LRU（Least Recently Used）淘汰策略。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:24;
    int refcount;
    void *ptr;
} robj;

数据库实现原理

• 内存数据存储：所有数据都存储在内存中，确保极快的读写性能。

• 键值对存储：使用字典（hashtable）来存储所有的键值对，每个数据库实例包含一个全局字典。

• 持久化：

  • RDB（Redis Database File）：定期生成内存快照并保存到磁盘，包含某一时刻的全部数据。

  • AOF（Append-Only File）：将每个写操作记录到日志文件中，重启时重新执行这些操作以恢复数据。

• 复制：主从复制将数据从主服务器复制到从服务器，提高数据可用性和可扩展性。

• 分片（分布式存储）：通过 Redis 集群将数据分布到多个节点，实现高可用和水平扩展。

• 事件驱动机制：使用事件驱动的单线程模型和多路复用机制来处理客户端请求，高效处理并发请求。

键值对存储

redisDb 结构体示例：

typedef struct redisDb {
    dict *dict;              /* The keyspace for this DB */
    dict *expires;           /* Timeout of keys with a timeout set */
    dict *blocking_keys;     /* Keys with clients waiting for data (BLPOP) */
    dict *ready_keys;        /* Blocked keys that received a PUSH */
    dict *watched_keys;      /* WATCHED keys for MULTI/EXEC CAS */
    int id;                  /* Database ID */
} redisDb;

• dict：用于存储键值对的字典。

• expires：存储有超时设置的键。

• blocking_keys：处理 BLPOP 命令的阻塞键。

• ready_keys：处理 PUSH 操作后解锁的键。

• watched_keys：处理事务（MULTI/EXEC）的监视键。

持久化

RDB

对内存数据的快照，RDB中存有每个周期时间节点下，内存中有的所有的数据。

• 恢复速度快并且效率高，但是会有丢失数据的风险。

AOF

对每条写命令的记录，AOF能快速复现当前数据。

• 效率低但是更实时持久化。

Redis过期与缓存问题

Key删除策略

• 定时删除:每设置过期时间的key都需要创建一个定时器,到过期时间就会立即清除,该策略可以立即清除过期的数据,对内存很友好,但是会占用大量的CPU资源去处理过期的数据,从而影响缓存的响应时间和吞吐量.

• 惰性删除:只有访问这个key的时候才会判断该key是否过期,过期则清除,该策略可最大化地节省CPU资源,却对内存非常不友好,极端情况可能出现大量的过期key没有再次被访问,从而不会被清除,占用大量内存.

• 定期删除:每隔一段时间,会扫描一定数量的数据库的expires字典中一定数量的key,并清除其中已过期的key,该策略是定时和惰性两者的一个折中方案,通过调整定时扫描的时间间隔和每次扫描的限时耗时,可以在不同情况下使得CPU和内存资源达到最优的平衡效果.

内存淘汰策略

• noeviction：默认策略，直接返回错误，不淘汰任何已经存在的redis键；

• allkeys-lru：所有的键使用LRU（最近最少使用）算法进行淘汰；

• volatile-lru：从设置了过期时间的key中使用LRU（最近最少使用）算法进行淘汰；

• allkeys-random：随机删除 redis 键；

• volatile-random：随机删除有过期时间的 redis 键；

• volatile-ttl：删除快过期的redis键；

• volatile-lfu：根据LFU算法从有过期时间的键删除；

• allkeys-lfu：根据LFU算法从所有键删除；

缓存穿透

缓存没有数据，数据库也没有数据，也就是返回为空的结果，大量请求访问数据库导致宕机

• 布隆过滤器

• 上层服务完整性校验

• 限流与降级

缓存击穿

缓存的数据过期的一瞬间，大量请求打到数据库中进行访问，导致数据库宕机

• 永不过期

• 异步更新快过期的key

• 互斥锁(setnx)限定同key只访问一次数据库

缓存雪崩

大量的key在同一时间过期，查询量巨大的情况下请求到数据库，导致数据库宕机

• 均匀过期，为过期时间增加一个随机值

• 双层缓存，二级缓存作为备用访问，过期时间比一级更长

• 加锁和队列，保证有限请求访问数据库

Redis部署方式

单机模式

单个进程负责数据的读写

哨兵模式

主从架构

• 主服务器负责读写，从服务负责读。

• 写操作由主库先操作，再同步给从库。

优点

• 避免宕机，使用哨兵系统

• 负载均衡，读写分离

Cluster集群

每个节点负责一部分数据的槽位。每次查找数据对16384进行取模。

MOVED错误

负载均衡，当通过一个节点访问数据，但是这个数据已经不在这个节点上时触发。

节点会返回这个错误，并同时返回拥有数据的节点的ip:port

而客户端会更新本地哈希槽缓存

ASK错误

如果某个 slot 的数据比较多，部分迁移到新实例，还有一部分没有迁移。

如果请求的 key 在当前节点找到就直接执行命令，否则时候就需要 ASK 错误响应了。

Redis事务

Redis事务功能是通过MULTI、EXEC、DISCARD和WATCH 四个原语实现的

Redis会将一个事务中的所有命令序列化，然后按顺序执行。

• redis 不支持回滚“Redis 在事务失败时不进行回滚，而是继续执行余下的命令”， 所以 Redis 的内部可以保持简单且快速。

• 如果在一个事务中的命令出现错误，那么所有的命令都不会执行；

• 如果在一个事务中出现运行错误，那么正确的命令会被执行。

  • MULTI命令用于开启一个事务，它总是返回OK。 MULTI执行之后，客户端可以继续向服务器发送任意多条命令，这些命令不会立即被执行，而是被放到一个队列中，当EXEC命令被调用时，所有队列中的命令才会被执行。

  • EXEC：执行所有事务块内的命令。返回事务块内所有命令的返回值，按命令执行的先后顺序排列。当操作被打断时，返回空值 nil 。

  • 通过调用DISCARD，客户端可以清空事务队列，并放弃执行事务， 并且客户端会从事务状态中退出。

  • WATCH 命令可以为 Redis 事务提供 check-and-set （CAS）行为。 可以监控一个或多个键，一旦其中有一个键被修改（或删除），之后的事务就不会执行，监控一直持续到EXEC命令。