CS-Notes Redis 完全指南五大数据类型、渐进式 rehash、持久化与主从复制实现原理【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 仓库的 Redis 笔记 编写系统梳理 Redis 的五种数据类型及其典型命令用法深入讲解其底层字典渐进式 rehash与跳跃表实现原理并完整覆盖使用场景、RDB/AOF 持久化、事务、事件模型、主从复制、Sentinel 与分片等核心机制。读完后你将能够理解 Redis 的数据结构选型依据、缓存淘汰策略的取舍并能用 HASH、SET、ZSET 组合完成一个论坛系统的数据层设计。一、概述Redis 是速度非常快的非关系型NoSQL内存键值数据库可以存储键和五种不同类型的值之间的映射。键的类型只能为字符串值支持五种数据类型字符串、列表、集合、散列表、有序集合。Redis 支持很多特性例如将内存中的数据持久化到硬盘中RDB 快照与 AOF 日志使用复制来扩展读性能主从复制、主从链使用分片来扩展写性能Redis Cluster。在 CS-Notes 中Redis 与 MySQL、数据库系统原理 共同构成数据库知识板块其作为分布式缓存时还需结合 缓存 一文理解命中率、淘汰策略与缓存雪崩等问题。二、五种数据类型与典型命令数据类型可以存储的值操作STRING字符串、整数或者浮点数对整个字符串或者字符串的其中一部分执行操作对整数和浮点数执行自增或者自减操作LIST列表从两端压入或者弹出元素对单个或者多个元素进行修剪只保留一个范围内的元素SET无序集合添加、获取、移除单个元素检查一个元素是否存在于集合中计算交集、并集、差集从集合里面随机获取元素HASH包含键值对的无序散列表添加、获取、移除单个键值对获取所有键值对检查某个键是否存在ZSET有序集合添加、获取、删除元素根据分值范围或者成员来获取元素计算一个键的排名STRINGSTRING是最简单的类型set/get/del是基本操作对整数类型还支持自增自减incr、decr这也是计数器场景的基础。 set hello world OK get hello world del hello (integer) 1 get hello (nil)LISTLIST支持从两端压入/弹出元素是消息队列场景的载体。lrange key 0 -1表示取出整个列表lindex按索引取值lpop弹出左侧元素。 rpush list-key item (integer) 1 rpush list-key item2 (integer) 2 rpush list-key item (integer) 3 lrange list-key 0 -1 1) item 2) item2 3) item lindex list-key 1 item2 lpop list-key item lrange list-key 0 -1 1) item2 2) itemSETSET是去重的无序集合重复添加同一元素返回 0sismember检查成员存在性srem移除成员。 sadd set-key item (integer) 1 sadd set-key item2 (integer) 1 sadd set-key item3 (integer) 1 sadd set-key item (integer) 0 smembers set-key 1) item 2) item2 3) item3 sismember set-key item4 (integer) 0 sismember set-key item (integer) 1 srem set-key item2 (integer) 1 srem set-key item2 (integer) 0 smembers set-key 1) item 2) item3HASHHASH存储字段到值的映射适合表示对象属性。重复设置相同字段不会生效返回 0hgetall一次取出所有键值对。 hset hash-key sub-key1 value1 (integer) 1 hset hash-key sub-key2 value2 (integer) 1 hset hash-key sub-key1 value1 (integer) 0 hgetall hash-key 1) sub-key1 2) value1 3) sub-key2 4) value2 hdel hash-key sub-key2 (integer) 1 hdel hash-key sub-key2 (integer) 0 hget hash-key sub-key1 value1 hgetall hash-key 1) sub-key1 2) value1ZSETZSET是带分值的有序集合成员按 score 排序。zadd重复添加同一成员同分值返回 0zrange ... withscores可附带分值输出zrangebyscore按分值范围查询。 zadd zset-key 728 member1 (integer) 1 zadd zset-key 982 member0 (integer) 1 zadd zset-key 982 member0 (integer) 0 zrange zset-key 0 -1 withscores 1) member1 2) 728 3) member0 4) 982 zrangebyscore zset-key 0 800 withscores 1) member1 2) 728 zrem zset-key member1 (integer) 1 zrem zset-key member1 (integer) 0 zrange zset-key 0 -1 withscores 1) member0 2) 982三、底层数据结构3.1 字典dictdictht是一个散列表结构使用拉链法解决哈希冲突/* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. */ typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht;每个键值对由dictEntry表示其中的next指针构成拉链typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry;Redis 的字典dict中包含两个哈希表dictht这是为了方便进行 rehash 操作。在扩容时将其中一个dictht上的键值对 rehash 到另一个dictht上面完成之后释放空间并交换两个dictht的角色typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; /* rehashing not in progress if rehashidx -1 */ unsigned long iterators; /* number of iterators currently running */ } dict;rehash 操作不是一次性完成而是采用渐进式方式这是为了避免一次性执行过多的 rehash 操作给服务器带来过大的负担。渐进式 rehash 通过记录dict的rehashidx完成它从 0 开始然后每执行一次 rehash 都会递增。例如在一次 rehash 中要把ht[0]rehash 到ht[1]这一次会把ht[0]上table[rehashidx]的键值对 rehash 到ht[1]上ht[0]的table[rehashidx]指向 null并令rehashidx。在 rehash 期间每次对字典执行添加、删除、查找或者更新操作时都会顺带执行一次渐进式 rehash。由于数据分散在两个dictht上查找操作也需要到对应的dictht去执行。核心调度逻辑在dictRehash函数中/* Performs N steps of incremental rehashing. Returns 1 if there are still * keys to move from the old to the new hash table, otherwise 0 is returned. * * Note that a rehashing step consists in moving a bucket (that may have more * than one key as we use chaining) from the old to the new hash table, however * since part of the hash table may be composed of empty spaces, it is not * guaranteed that this function will rehash even a single bucket, since it * will visit at max N*10 empty buckets in total, otherwise the amount of * work it does would be unbound and the function may block for a long time. */ int dictRehash(dict *d, int n) { int empty_visits n * 10; /* Max number of empty buckets to visit. */ if (!dictIsRehashing(d)) return 0; while (n-- d-ht[0].used ! 0) { dictEntry *de, *nextde; /* Note that rehashidx cant overflow as we are sure there are more * elements because ht[0].used ! 0 */ assert(d-ht[0].size (unsigned long) d-rehashidx); while (d-ht[0].table[d-rehashidx] NULL) { d-rehashidx; if (--empty_visits 0) return 1; } de d-ht[0].table[d-rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ while (de) { uint64_t h; nextde de-next; /* Get the index in the new hash table */ h dictHashKey(d, de-key) d-ht[1].sizemask; de-next d-ht[1].table[h]; d-ht[1].table[h] de; d-ht[0].used--; d-ht[1].used; de nextde; } d-ht[0].table[d-rehashidx] NULL; d-rehashidx; } /* Check if we already rehashed the whole table... */ if (d-ht[0].used 0) { zfree(d-ht[0].table); d-ht[0] d-ht[1]; _dictReset(d-ht[1]); d-rehashidx -1; return 0; } /* More to rehash... */ return 1; }从源码结构看有两点值得注意empty_visits n * 10限制了本次调用最多访问的空桶数量保证单次 rehash 的开销有上界不会长时间阻塞事件循环——这与 Redis 单线程模型的设计目标一致当ht[0].used 0时释放旧表、交换两个dictht的角色并把rehashidx复位为 -1标记 rehash 结束。3.2 跳跃表跳跃表是有序集合ZSET的底层实现之一基于多指针有序链表实现可以看成多个有序链表叠加在查找时从上层指针开始查找找到对应的区间之后再到下一层去查找例如上图中查找值为 22 的成员先在高层快速跳过无关区间再逐层下探最终定位到目标节点。与红黑树等平衡树相比跳跃表具有以下优点插入速度非常快因为不需要进行旋转等操作来维护平衡性更容易实现支持无锁操作。四、典型使用场景4.1 计数器可以对 String 进行自增自减运算从而实现计数器功能。Redis 这种内存型数据库的读写性能非常高很适合存储频繁读写的计数量例如商品浏览量、点赞数、接口限流计数等。4.2 缓存将热点数据放到内存中设置内存的最大使用量以及淘汰策略来保证缓存的命中率。关于缓存穿透、缓存雪崩、缓存一致性与 LRU/LFU 等更通用的缓存问题可进一步参考 缓存 一文其中给出了基于“双向链表 HashMap”的 LRU 完整实现。4.3 查找表例如 DNS 记录就很适合使用 Redis 进行存储。查找表和缓存类似也是利用了 Redis 快速的查找特性。但是查找表的内容不能失效而缓存的内容可以失效因为缓存不作为可靠的数据来源。4.4 消息队列List 是一个双向链表可以通过lpush和rpop写入和读取消息实现一个简易的消息队列。不过生产环境中最好使用 Kafka、RabbitMQ 等消息中间件它们提供消费确认、消息持久化、投递顺序等更完善的语义参见 消息队列。4.5 会话缓存可以使用 Redis 来统一存储多台应用服务器的会话信息。当应用服务器不再存储用户的会话信息也就不再具有状态一个用户可以请求任意一个应用服务器从而更容易实现高可用性以及可伸缩性。4.6 分布式锁实现在分布式场景下无法使用单机环境下的锁来对多个节点上的进程进行同步。最简单的做法是使用 Redis 自带的SETNXset if not exist命令实现分布式锁键不存在时插入成功即获得锁配合EXPIRE设置过期时间可避免持锁方宕机后锁无法释放的问题除此之外还可以使用官方提供的RedLock分布式锁实现。RedLock 的完整算法流程在 分布式 一文中有说明向 N 个互相独立的 Redis 实例依次申请锁只有从大多数N/2 1实例上成功获取锁、且耗时小于锁的过期时间才认为获取锁成功失败则到每个实例上释放锁。4.7 其它Set 可以实现交集、并集等操作从而实现共同好友等功能ZSet 可以实现有序性操作从而实现排行榜等功能。五、Redis 与 Memcached两者都是非关系型内存键值数据库主要有以下不同数据类型Memcached 仅支持字符串类型而 Redis 支持五种不同的数据类型可以更灵活地解决问题如排行榜、集合运算等需要结构化的场景。数据持久化Redis 支持两种持久化策略RDB 快照和 AOF 日志而 Memcached 不支持持久化。分布式Memcached 不支持分布式只能通过在客户端使用一致性哈希来实现分布式存储这种方式在存储和查询时都需要先在客户端计算一次数据所在的节点一致性哈希原理见 缓存 第六节。Redis Cluster 则实现了服务端对分布式的支持。内存管理机制在 Redis 中并不是所有数据都一直存储在内存中可以将一些很久没用的 value 交换到磁盘而 Memcached 的数据则会一直在内存中Memcached 将内存分割成特定长度的块来存储数据以完全解决内存碎片的问题。但是这种方式会使得内存的利用率不高例如块的大小为 128 bytes只存储 100 bytes 的数据那么剩下的 28 bytes 就浪费掉了。六、键的过期时间Redis 可以为每个键设置过期时间当键过期时会自动删除该键。对于散列表这种容器只能为整个键设置过期时间整个散列表而不能为键里面的单个元素设置过期时间。七、数据淘汰策略可以设置内存最大使用量当内存使用量超出时会施行数据淘汰策略。Redis 具体有 6 种淘汰策略策略描述volatile-lru从已设置过期时间的数据集中挑选最近最少使用的数据淘汰volatile-ttl从已设置过期时间的数据集中挑选将要过期的数据淘汰volatile-random从已设置过期时间的数据集中任意选择数据淘汰allkeys-lru从所有数据集中挑选最近最少使用的数据淘汰allkeys-random从所有数据集中任意选择数据进行淘汰noeviction禁止驱逐数据作为内存数据库出于对性能和内存消耗的考虑Redis 的淘汰算法实际实现上并非针对所有 key而是抽样一小部分并且从中选出被淘汰的 key。使用 Redis 缓存数据时为了提高缓存命中率需要保证缓存数据都是热点数据。可以将内存最大使用量设置为热点数据占用的内存量然后启用allkeys-lru淘汰策略将最近最少使用的数据淘汰。Redis 4.0 引入了volatile-lfu和allkeys-lfu淘汰策略LFU 策略通过统计访问频率将访问频率最少的键值对淘汰在数据访问呈幂律分布少数热点 key 承载大部分流量的场景下比 LRU 更贴合真实热度。八、持久化Redis 是内存型数据库为了保证数据在断电后不会丢失需要将内存中的数据持久化到硬盘上。8.1 RDB 持久化将某个时间点的所有数据都存放到硬盘上二进制快照。其特点是可以将快照复制到其它服务器从而创建具有相同数据的服务器副本如果系统发生故障将会丢失最后一次创建快照之后的数据如果数据量很大保存快照的时间会很长。8.2 AOF 持久化将写命令添加到 AOF 文件Append Only File的末尾。使用 AOF 持久化需要设置同步选项从而确保写命令同步到磁盘文件上的时机。这是因为对文件进行写入并不会马上将内容同步到磁盘上而是先存储到缓冲区然后由操作系统决定什么时候同步到磁盘选项同步频率always每个写命令都同步everysec每秒同步一次no让操作系统来决定何时同步三个选项的权衡always选项会严重减低服务器的性能everysec选项比较合适可以保证系统崩溃时只会丢失一秒左右的数据并且 Redis 每秒执行一次同步对服务器性能几乎没有任何影响no选项并不能给服务器性能带来多大的提升而且也会增加系统崩溃时数据丢失的数量。随着服务器写请求的增多AOF 文件会越来越大。Redis 提供了一种AOF 重写的特性能够去除 AOF 文件中的冗余写命令例如对同一个键的多次set重写时只保留当前最终状态从而压缩文件体积。九、事务一个事务包含了多个命令服务器在执行事务期间不会改去执行其它客户端的命令请求。事务中的多个命令被一次性发送给服务器而不是一条一条发送这种方式被称为流水线pipeline它可以减少客户端与服务器之间的网络通信次数从而提升性能。Redis 最简单的事务实现方式是使用MULTI和EXEC命令将事务操作包围起来MULTI之后开始入队命令EXEC触发原子执行期间可以插入DISCARD放弃事务。十、事件模型文件事件与时间事件Redis 服务器是一个事件驱动程序。10.1 文件事件服务器通过套接字与客户端或者其它服务器进行通信文件事件就是对套接字操作的抽象。Redis 基于Reactor 模式开发了自己的网络事件处理器使用 I/O 多路复用程序如 epoll来同时监听多个套接字并将到达的事件传送给文件事件分派器分派器会根据套接字产生的事件类型调用相应的事件处理器10.2 时间事件服务器有一些操作需要在给定的时间点执行时间事件是对这类定时操作的抽象。时间事件又分为定时事件让一段程序在指定的时间之内执行一次周期性事件让一段程序每隔指定时间就执行一次。Redis 将所有时间事件都放在一个无序链表中通过遍历整个链表查找出已到达的时间事件并调用相应的事件处理器。10.3 事件的调度与执行服务器需要不断监听文件事件的套接字才能得到待处理的文件事件但是不能一直监听否则时间事件无法在规定的时间内执行因此监听时间应该根据距离现在最近的时间事件来决定。事件调度与执行由aeProcessEvents函数负责伪代码如下def aeProcessEvents(): # 获取到达时间离当前时间最接近的时间事件 time_event aeSearchNearestTimer() # 计算最接近的时间事件距离到达还有多少毫秒 remaind_ms time_event.when - unix_ts_now() # 如果事件已到达那么 remaind_ms 的值可能为负数将它设为 0 if remaind_ms 0: remaind_ms 0 # 根据 remaind_ms 的值创建 timeval timeval create_timeval_with_ms(remaind_ms) # 阻塞并等待文件事件产生最大阻塞时间由传入的 timeval 决定 aeApiPoll(timeval) # 处理所有已产生的文件事件 procesFileEvents() # 处理所有已到达的时间事件 processTimeEvents()将aeProcessEvents函数置于一个循环里面加上初始化和清理函数就构成了 Redis 服务器的主函数def main(): # 初始化服务器 init_server() # 一直处理事件直到服务器关闭为止 while server_is_not_shutdown(): aeProcessEvents() # 服务器关闭执行清理操作 clean_server()从事件处理的角度来看服务器运行时就是不断循环执行「计算最近时间事件 → 阻塞等待文件事件 → 处理文件事件 → 处理时间事件」这一模型也解释了为什么 Redis 要求命令执行尽量快、避免长阻塞操作。十一、复制主从通过使用slaveof host port命令来让一个服务器成为另一个服务器的从服务器。一个从服务器只能有一个主服务器并且不支持主主复制。11.1 连接过程主服务器创建快照文件发送给从服务器并在发送期间使用缓冲区记录执行的写命令快照文件发送完毕之后开始向从服务器发送存储在缓冲区中的写命令从服务器丢弃所有旧数据载入主服务器发来的快照文件之后从服务器开始接受主服务器发来的写命令主服务器每执行一次写命令就向从服务器发送相同的写命令保持两者的数据一致。11.2 主从链随着负载不断上升主服务器可能无法很快地更新所有从服务器或者重新连接和重新同步从服务器将导致系统超载。为了解决这个问题可以创建一个中间层来分担主服务器的复制工作中间层的服务器是最上层服务器的从服务器又是最下层服务器的主服务器。十二、SentinelSentinel哨兵可以监听集群中的服务器并在主服务器进入下线状态时自动从从服务器中选举出新的主服务器从而为主从架构提供高可用能力哨兵集群通过多数派共识完成故障判定与主节点切换客户端可通过哨兵发现当前主服务器地址。十三、分片分片是将数据划分为多个部分的方法可以将数据存储到多台机器里面这种方法在解决某些问题时可以获得线性级别的性能提升。假设有 4 个 Redis 实例 R0、R1、R2、R3还有很多表示用户的键user:1、user:2、……有不同的方式来选择一个指定的键存储在哪个实例中最简单的方式是范围分片例如用户 id 从 0~1000 的存储到实例 R0 中用户 id 从 1001~2000 的存储到实例 R1 中等等。但是这样需要维护一张映射范围表维护操作代价很高还有一种方式是哈希分片使用 CRC32 哈希函数将键转换为一个数字再对实例数量求模就能知道应该存储的实例。根据执行分片的位置可以分为三种分片方式客户端分片客户端使用一致性哈希等算法决定键应当分布到哪个节点代理分片将客户端请求发送到代理上由代理转发请求到正确的节点上服务器分片Redis Cluster分片逻辑由服务器自身承担。十四、实战分析一个基于 Redis 的论坛系统该论坛系统功能如下可以发布文章可以对文章进行点赞在首页可以按文章的发布时间或者文章的点赞数进行排序显示。14.1 文章信息文章包括标题、作者、赞数等信息在关系型数据库中很容易构建一张表来存储这些信息在 Redis 中可以使用HASH来存储每种信息以及其对应的值的映射。Redis 没有关系型数据库中的“表”这一概念来将同种类型的数据存放在一起而是使用命名空间的方式来实现这一功能键名的前面部分存储命名空间后面部分的内容存储 ID通常使用:来进行分隔。例如下面的 HASH 的键名为article:92617其中article为命名空间ID 为 92617。14.2 点赞功能当有用户为一篇文章点赞时除了要对该文章的votes字段进行加 1 操作还必须记录该用户已经对该文章进行了点赞防止用户点赞次数超过 1。可以建立**文章的已投票用户集合SET**来进行记录。为了节约内存规定一篇文章发布满一周之后就不能再对它进行投票而文章的已投票集合也会被删除。可以为文章的已投票集合设置一个一周的过期时间就能实现这个规定——这正是“键的过期时间”特性在实际系统中的直接应用。14.3 对文章进行排序为了按发布时间和点赞数进行排序可以建立一个文章发布时间的有序集合和一个文章点赞数的有序集合。两个 ZSET 的 score 并不直接是时间和点赞数而是根据时间和点赞数间接计算出来的例如用时间戳偏移作为时间排序的分值这样zrevrange等命令即可直接输出按时间或点赞数排好序的文章列表。参考本文结构与技术内容均出自 CS-Notes 仓库的 notes/Redis.md配套延伸阅读包括 notes/缓存.md命中率、LRU/LFU、一致性哈希与 notes/分布式.mdRedLock 算法、分布式事务。原始笔记的参考资料包括Carlson J L.Redis in Action. 2013黄健宏《Redis 设计与实现》机械工业出版社2014Redis in Action电子书《Skip Lists: Done Right》等涉及渐进式 rehash、跳跃表、RDB/AOF 与分片的深入推导。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考