下半年利用空余时间研究和分析了部分 Redis 源码,本文从网络模型、数据结构和内存管理、持久化和多机协作四个角度对 redis 的设计思路进行了分析,若有不正确之处,希望各路大神指出。
Redis 是业界普遍应用的缓存组件,研究一个组件框架,最直观的办法就是从应用方的角度出发,将每个步骤的考虑一番,从这些步骤入手去研究往往能够最快的体会到一个组件框架的设计哲学。以 Redis 为例,每当发起一条请求时,redis 是如何管理管理网络请求,收到请求后又是通过什么样的数据结构进行组织并操作内存,这些数据又是如何 dump 到磁盘实现持久化,再到多机环境下如何同步和保证一致性…… 本文就是从网络模型、数据结构设计与内存管理、持久化方法和多机四个角度简要描述了 redis 的设计和自己的一点体会。
Redis 是典型的基于 Reactor 的事件驱动模型,单进程单线程,高效的框架总是类似的。网络模型与 spp 的异步模型几乎一致。
Redis 流程上整体分为接受请求处理器、响应处理器和应答处理器三个同步模块,每一个请求都是要经历这三个部分。
Redis 集成了
等多种事件管理机制,可以根据操作系统版本自由选择合适的管理机制,其中 libevent 是最优选择的机制。
- libevent/epoll/kqueue/select
Redis 的网络模型有着所有事件驱动模型的优点,高效低耗。但是面对耗时较长的操作的时候,同样无法处理请求,只能等到事件处理完毕才能响应,之前在业务中也遇到过这样的场景,删除 redis 中全量的 key-value,整个操作时间较长,操作期间所有的请求都无法响应。所以了解清楚网络模型有助于在业务中扬长避短,减少长耗时的请求,尽可能多一些简单的短耗时请求发挥异步模型的最大的威力,事实上在 Redis 的设计中也多次体现这一点。
Redis 的字符串是对 C 语言原始字符串的二次封装,结构如下:
- struct sdshdr {
- long len;
- long free;
- char buf[];
- };
可以看出,每当定义一个字符串时,除了保存字符的空间,Redis 还分配了额外的空间用于管理属性字段。
动态内存管理方式,动态方式最大的好处就是能够较为充分的利用内存空间,减少内存碎片化,与此同时带来的劣势就是容易引起频繁的内存抖动,通常采用 "空间预分配" 和 "惰性空间释放" 两种优化策略来减少内存抖动,redis 也不例外。
每次修改字符串内容时,首先检查内存空间是否符合要求,否则就扩大 2 倍或者按 M 增长;减少字符串内容时,内存并不会立刻回收,而是按需回收。
关于内存管理的优化,最基本的出发点就是浪费一点空间还是牺牲一些时间的权衡,像 STL、tcmalloc、protobuf3 的 arena 机制等采用的核心思路都是 "预分配迟回收",Redis 也是一样的。
判断字符串结束与否的标识是 len 字段,而不是 C 语言的'\0',因此是二进制安全的。
放心的将 pb 序列化后的二进制字符串存入 redis。
简而言之,通过 redis 的简单封装,redis 的字符串的操作更加方便,性能更友好,并且屏蔽了 C 语言字符串的一些需要用户关心的问题。
字典的底层一定是 hash,涉及到 hash 一定会涉及到 hash 算法、冲突的解决方法和 hash 表扩容和缩容。
Redis 使用的就是常用的 Murmurhash2,Murmurhash 算法能够给出在任意输入序列下的散列分布性,并且计算速度很快。之前做共享内存的 Local-Cache 的需求时也正是利用了 Murmurhash 的优势,解决了原有结构的 hash 函数散列分布性差的问题。
链地址法解决 hash 冲突,通用解决方案没什么特殊的。多说一句,如果选用链地址解决冲突,那么势必要有一个散列性非常好的 hash 函数,否则 hash 的性能将会大大折扣。Redis 选用了 Murmurhash,所以可以放心大胆的采用链地址方案。
维持 hash 表在一个合理的负载范围之内,简称为 rehash 过程。
rehash 的过程也是一个权衡的过程,在做评估之前首先明确一点,不管中间采用什么样的 rehash 策略,rehash 在宏观上看一定是:分配一个新的内存块,老数据搬到新的内存块上,释放旧内存块。
老数据何时搬?怎么搬?就变成了一个需要权衡的问题。
第一部分的网络模型上明确的指出 Redis 的事件驱动模型特点,不适合玩长耗时操作。如果一个 hashtable 非常大,需要进行扩容就一次性把老数据 copy 过去,那就会非常耗时,违背事件驱动的特点。所以 Redis 依旧采用了一种惰性的方案:
新空间分配完毕后,启动 rehashidx 标识符表明 rehash 过程的开始;之后所有增删改查涉及的操作时都会将数据迁移到新空间,直到老空间数据大小为 0 表明数据已经全部在新空间,将 rehashidx 禁用,表明 rehash 结束。
将一次性的集中问题分而治之,在 Redis 的设计哲学中体现的淋漓尽致,主要是为了避免大耗时操作,影响 Redis 响应客户请求。
变长整数存储,整数分为 16/32/64 三个变长尺度,根据存入的数据所属的类型,进行规划。
每次插入新元素都有可能导致尺度升级(例如由 16 位涨到 32 位),因此插入整数的时间复杂度为 O(n)。这里也是一个权衡,内存空间和时间的一个折中,尽可能节省内存。
Redis 的 skilplist 和普通的 skiplist 没什么不同,都是冗余数据实现的从粗到细的多层次链表,Redis 中应用跳表的地方不多,常见的就是有序集合。
Redis 的跳表和普通 skiplist 没有什么特殊之处。
Redis 的链表是双向非循环链表,拥有表头和表尾指针,对于首尾的操作时间复杂度是 O(1),查找时间复杂度 O(n),插入时间复杂度 O(1)。
Redis 的链表和普通链表没有什么特殊之处。
AOF 持久化日志,RDB 持久化实体数据,AOF 优先级大于 RDB。
机制:通过定时事件将 aof 缓冲区内的数据定时写到磁盘上。
为了减少 AOF 大小,Redis 提供了 AOF 重写功能,这个重写功能做的工作就是创建一个新 AOF 文件代替老的 AOF,并且这个新的 AOF 文件没有一条冗余指令。(例如对 list 先插入 A/B/C,后删除 B/C,再插入 D 共 6 条指令,最终状态为 A/D,只需 1 条指令就可以)
实现原理就是读现有数据库的状态,根据状态反推指令,跟之前的 AOF 无关。同样,为了避免长时间耗时,重写工作放在子进程进行。
SAVE 和 BGSAVE 两个命令都是用于生成 RDB 文件,区别在于 BGSAVE 会 fork 出一个子进程单独进行,不影响 Redis 处理正常请求。
定时和定次数后进行持久化操作。
简而言之,RDB 的过程其实是比较简单的,满足条件后直接去写 RDB 文件就结束了。
避免单点是所有服务的通用问题,Redis 也不例外。解决单点就要有备机,有备机就要解决固有的数据同步问题。
Redis 最初的同步做法是 sync 指令,通过 sync 每次都会全量数据,显然每次都全量复制的设计比较消耗资源。改进思路也是常规逻辑,第一次全量,剩下的增量,这就是现在的 psync 指令的活。
部分重同步实现的技术手段是 "偏移序号 + 积压缓冲区",具体做法如下:
(1)主从分别维护一个 seq,主每次完成一个请求便 seq+1,从每同步完后更新自己 seq;
(2)从每次打算同步时都是携带着自己的 seq 到主,主将自身的 seq 与从做差结果与积压缓冲区大小比较,如果小于积压缓冲区大小,直接从积压缓冲区取相应的操作进行部分重同步;
(3)否则说明积压缓冲区不能够 cover 掉主从不一致的数据,进行全量同步。
本质做法用空间换时间,显然在这里牺牲部分空间换回高效的部分重同步,收益比很大。
本质:多主从服务器的 Redis 系统,多台主从上加了管理监控,以保证系统高可用性。
Redis 的官方版集群尚未在工业界普及起来,下面主要介绍一下集群的管理体系和运转体系。
集群的数据区由 slot 组成,每个节点负责的 slot 是在集群启动时分配的。
客户请求时如果相应数据 hash 后不属于请求节点所管理的 slots,会给客户返回 MOVED 错误,并给出正确的 slots。
从这个层面看,redis 的集群还不够友好,集群内部的状态必须由客户感知。
主从服务器,从用于备份主,一旦主故障,从代替主。
通过 Redis 的研究,深刻体会到的一点就是:所有设计的过程都是权衡和割舍的过程。同样放到日常的工作和开发中也是如此,一句代码写的好不好,一个模块设计的是否科学,就从速度和内存的角度去衡量看是否需要优化,并去评估每一种优化会收益到什么,同时会损失什么,收益远大于损失的就是好的优化,这样往往对于开发和提升更有针对性,更能提高效率。
来源: http://www.bubuko.com/infodetail-1994885.html