通过本文你将了解到以下内容:
Redis 的作者, 发展演进和江湖地位
Redis 面试问题的概况
Redis 底层实现相关的问题包括:
常用数据类型底层实现, SDS 的原理和优势, 字典的实现原理, 跳表和有序集合的原理, Redis 的线程模式和服务模型
温馨提示: 内容并不难, 就怕你不看.
看不懂可以先收藏先 Mark, 等到深入研究的时间再翻出来看看, 你就发现真是 24K 干货呀! 停止吹嘘, 写点不一样的文字吧!
1.Redis 往事
Redis 是一个使用 ANSI C 编写的开源, 支持网络, 基于内存, 可选持久化的高性能键值对数据库. Redis 的之父是来自意大利的西西里岛的 Salvatore Sanfilippo,GitHub 网名 antirez, 笔者找了作者的一些简要信息并翻译了一下, 如图:
从 2009 年第一个版本起 Redis 已经走过了 10 个年头, 目前 Redis 仍然是最流行的 key-value 型内存数据库的之一.
优秀的开源项目离不开大公司的支持, 在 2013 年 5 月之前, 其开发由 VMware 赞助, 而 2013 年 5 月至 2015 年 6 月期间, 其开发由毕威拓赞助, 从 2015 年 6 月开始, Redis 的开发由 Redis Labs 赞助.
笔者也使用过一些其他的 NoSQL, 有的支持的 value 类型非常单一, 因此很多操作都必须在客户端实现, 比如 value 是一个结构化的数据, 需要修改其中某个字段就需要整体读出来修改再整体写入, 显得很笨重, 但是 Redis 的 value 支持多种类型, 实现了很多操作在服务端就可以完成了, 这个对客户端而言非常方便.
当然 Redis 由于是内存型的数据库, 数据量存储量有限而且分布式集群成本也会非常高, 因此有很多公司开发了基于 SSD 的类 Redis 系统, 比如 360 开发的 SSDB,Pika 等数据库, 但是笔者认为从 0 到 1 的难度是大于从 1 到 2 的难度的, 毋庸置疑 Redis 是 NoSQL 中浓墨重彩的一笔, 值得我们去深入研究和使用.
2.Redis 的江湖地位
Redis 提供了 Java,C/C++,C#, PHP ,JavaScript, Perl ,Object-C,Python,Ruby,Erlang,Golang 等多种主流语言的客户端, 因此无论使用者是什么语言栈总会找到属于自己的那款客户端, 受众非常广.
笔者查了 http://datanyze.com 网站看了下 Redis 和 MySQL 的最新市场份额和排名对比以及全球 Top 站点的部署量对比 (网站数据更新到写作当日 2019.12.11):
可以看到 Redis 总体份额排名第 9 并且在全球 Top100 站点中部署数量与 MySQL 基本持平, 所以 Redis 还是有一定的江湖地位的.
3. 聊聊实战
目前 Redis 发布的稳定版本已经到了 5.x, 功能也越来越强大, 从国内外互联网公司来看 Redis 几乎是标配了. 作为开发人员在日常笔试面试和工作中遇到 Redis 相关问题的概率非常大, 掌握 Redis 的相关知识点都十分有必要.
学习和梳理一个复杂的东西肯定不能胡子眉毛一把抓, 每个人都有自己的认知思路, 笔者认为要从充分掌握 Redis 需要从底向上, 从外到内去理解 Redis.
Redis 的实战知识点可以简单分为三个层次:
底层实现: 主要是从 Redis 的源码中提炼的问题, 包括但不限于底层数据结构, 服务模型, 算法设计等.
基础架构: 可用概况为 Redis 整体对外的功能点和表现, 包括但不限于单机版主从架构实现, 主从数据同步, 哨兵机制, 集群实现, 分布式一致性, 故障迁移等.
实际应用: 实战中 Redis 可用帮你做什么, 包括但不限于单机缓存, 分布式缓存, 分布式锁, 一些应用.
深入理解和熟练使用 Redis 需要时间锤炼, 要做到信手拈来着实不易, 想在短时间内突破只能从热点题目入手, 虽然这样感觉有些功利, 不过也算无可厚非吧, 为了吃饭我们还是倾向于原谅懒惰的自己, 要不然吃土喝风?
4. 底层实现热点题目
底层实现篇的题目主要是与 Redis 的源码和设计相关, 可以说是 Redis 功能的基石, 了解底层实现可以让我们更好地掌握功能, 由于底层代码很多, 在后续的基础架构篇中仍然会穿插源码来分析, 因此本篇只列举一些热点的问题.
Q1: Redis 常用五种数据类型是如何实现的?
Redis 支持的常用 5 种数据类型指的是 value 类型, 分别为: 字符串 String, 列表 List, 哈希 Hash, 集合 Set, 有序集合 Zset, 但是 Redis 后续又丰富了几种数据类型分别是 Bitmaps,HyperLogLogs,GEO.
由于 Redis 是基于标准 C 写的, 只有最基础的数据类型, 因此 Redis 为了满足对外使用的 5 种数据类型, 开发了属于自己独有的一套基础数据结构, 使用这些数据结构来实现 5 种数据类型.
Redis 底层的数据结构包括: 简单动态数组 SDS, 链表, 哈希表, 跳跃链表, 整数集合, 压缩列表, 对象.
Redis 为了平衡空间和时间效率, 针对 value 的具体类型在底层会采用不同的数据结构来实现, 其中哈希表和压缩列表是复用比较多的数据结构, 如下图展示了对外数据类型和底层数据结构之间的映射关系:
从图中可以看到 ziplist 压缩列表可以作为 Zset,Set,List 三种数据类型的底层实现, 看来很强大, 压缩列表是一种为了节约内存而开发的且经过特殊编码之后的连续内存块顺序型数据结构, 底层结构还是比较复杂的.
Q2: Redis 的 SDS 和 C 中字符串相比有什么优势?
在 C 语言中使用 N+1 长度的字符数组来表示字符串, 尾部使用'\0'作为结尾标志, 对于此种实现无法满足 Redis 对于安全性, 效率, 丰富的功能的要求, 因此 Redis 单独封装了 SDS 简单动态字符串结构.
在理解 SDS 的优势之前需要先看下 SDS 的实现细节, 找了 GitHub 最新的 src/sds.h 的定义看下:
- typedef char *sds;
- /* 这个用不到 忽略即可 */
- struct __attribute__ ((__packed__)) sdshdr5 {
- unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
- char buf[];
- };
- /* 不同长度的 header 8 16 32 64 共 4 种 都给出了四个成员
- len: 当前使用的空间大小; alloc 去掉 header 和结尾空字符的最大空间大小
- flags:8 位的标记 下面关于 SDS_TYPE_x 的宏定义只有 5 种 3bit 足够了 5bit 没有用
- buf: 这个跟 C 语言中的字符数组是一样的, 从 typedef char* sds 可以知道就是这样的.
- buf 的最大长度是 2^n 其中 n 为 sdshdr 的类型, 如当选择 sdshdr16,buf_max=2^16.
- */
- struct __attribute__ ((__packed__)) sdshdr8 {
- uint8_t len; /* used */
- uint8_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr16 {
- uint16_t len; /* used */
- uint16_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr32 {
- uint32_t len; /* used */
- uint32_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr64 {
- uint64_t len; /* used */
- uint64_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- #define SDS_TYPE_5 0
- #define SDS_TYPE_8 1
- #define SDS_TYPE_16 2
- #define SDS_TYPE_32 3
- #define SDS_TYPE_64 4
- #define SDS_TYPE_MASK 7
- #define SDS_TYPE_BITS 3
看了前面的定义, 笔者画了个图:
从图中可以知道 sds 本质分为三部分: header,buf,null 结尾符, 其中 header 可以认为是整个 sds 的指引部分, 给定了使用的空间大小, 最大分配大小等信息, 再用一张网上的图来清晰看下 sdshdr8 的实例:
在 sds.h/sds.c 源码中可清楚地看到 sds 完整的实现细节, 本文就不展开了要不然篇幅就过长了, 快速进入主题说下 sds 的优势:
O(1) 获取长度: C 字符串需要遍历而 sds 中有 len 可以直接获得;
防止缓冲区溢出 bufferoverflow: 当 sds 需要对字符串进行修改时, 首先借助于 len 和 alloc 检查空间是否满足修改所需的要求, 如果空间不够的话, SDS 会自动扩展空间, 避免了像 C 字符串操作中的覆盖情况;
有效降低内存分配次数: C 字符串在涉及增加或者清除操作时会改变底层数组的大小造成重新分配, sds 使用了空间预分配和惰性空间释放机制, 说白了就是每次在扩展时是成倍的多分配的, 在缩容是也是先留着并不正式归还给 OS, 这两个机制也是比较好理解的;
二进制安全: C 语言字符串只能保存 ascii 码, 对于图片, 音频等信息无法保存, sds 是二进制安全的, 写入什么读取就是什么, 不做任何过滤和限制;
老规矩上一张黄健宏大神总结好的图:
Q3:Redis 的字典是如何实现的? 简述渐进式 rehash 的过程.
字典算是 Redis5 中常用数据类型中的明星成员了, 前面说过字典可以基于 ziplist 和 hashtable 来实现, 我们只讨论基于 hashtable 实现的原理.
字典是个层次非常明显的数据类型, 如图:
有了个大概的概念, 我们看下最新的 src/dict.h 源码定义:
- // 哈希节点结构
- typedef struct dictEntry {
- void *key;
- union {
- void *val;
- uint64_t u64;
- int64_t s64;
- double d;
- } v;
- struct dictEntry *next;
- } dictEntry;
- // 封装的是字典的操作函数指针
- typedef struct dictType {
- uint64_t (*hashFunction)(const void *key);
- void *(*keyDup)(void *privdata, const void *key);
- void *(*valDup)(void *privdata, const void *obj);
- int (*keyCompare)(void *privdata, const void *key1, const void *key2);
- void (*keyDestructor)(void *privdata, void *key);
- void (*valDestructor)(void *privdata, void *obj);
- } dictType;
- /* 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;
- // 字典结构
- 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;
C 语言的好处在于定义必须是由最底层向外的, 因此我们可以看到一个明显的层次变化, 于是笔者又画一图来展现具体的层次概念:
关于 dictEntry
dictEntry 是哈希表节点, 也就是我们存储数据地方, 其保护的成员有: key,v,next 指针. key 保存着键值对中的键, v 保存着键值对中的值, 值可以是一个指针或者是 uint64_t 或者是 int64_t.next 是指向另一个哈希表节点的指针, 这个指针可以将多个哈希值相同的键值对连接在一次, 以此来解决哈希冲突的问题.
如图为两个冲突的哈希节点的连接关系:
关于 dictht
从源码看哈希表包括的成员有 table,size,used,sizemask.table 是一个数组, 数组中的每个元素都是一个指向 dictEntry 结构的指针, 每个 dictEntry 结构保存着一个键值对; size 属性记录了哈希表 table 的大小, 而 used 属性则记录了哈希表目前已有节点的数量. sizemask 等于 size-1 和哈希值计算一个键在 table 数组的索引, 也就是计算 index 时用到的.
如上图展示了一个大小为 4 的 table 中的哈希节点情况, 其中 k1 和 k0 在 index=2 发生了哈希冲突, 进行开链表存在, 本质上是先存储的 k0,k1 放置是发生冲突为了保证效率直接放在冲突链表的最前面, 因为该链表没有尾指针.
关于 dict
从源码中看到 dict 结构体就是字典的定义, 包含的成员有 type,privdata,ht,rehashidx. 其中 dictType 指针类型的 type 指向了操作字典的 API, 理解为函数指针即可, ht 是包含 2 个 dictht 的数组, 也就是字典包含了 2 个哈希表, rehashidx 进行 rehash 时使用的变量, privdata 配合 dictType 指向的函数作为参数使用, 这样就对字典的几个成员有了初步的认识.
字典的哈希算法
- // 伪码: 使用哈希函数, 计算键 key 的哈希值
- hash = dict->type->hashFunction(key);
- // 伪码: 使用哈希表的 sizemask 和哈希值, 计算出在 ht[0] 或许 ht[1] 的索引值
- index = hash & dict->ht[x].sizemask;
- // 源码定义
- #define dictHashKey(d, key) (d)->type->hashFunction(key)
Redis 使用 MurmurHash 算法计算哈希值, 该算法最初由 Austin Appleby 在 2008 年发明, MurmurHash 算法的无论数据输入情况如何都可以给出随机分布性较好的哈希值并且计算速度非常快, 目前有 MurmurHash2 和 MurmurHash3 等版本.
普通 Rehash 重新散列
哈希表保存的键值对数量是动态变化的, 为了让哈希表的负载因子维持在一个合理的范围之内, 就需要对哈希表进行扩缩容.
扩缩容是通过执行 rehash 重新散列来完成, 对字典的哈希表执行普通 rehash 的基本步骤为分配空间 -> 逐个迁移 -> 交换哈希表, 详细过程如下:
为字典的 ht[1] 哈希表分配空间, 分配的空间大小取决于要执行的操作以及 ht[0] 当前包含的键值对数量:
扩展操作时 ht[1] 的大小为第一个大于等于 ht[0].used*2 的 2^n;
收缩操作时 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n ;
扩展时比如 h[0].used=200, 那么需要选择大于 400 的第一个 2 的幂, 也就是 2^9=512.
将保存在 ht[0] 中的所有键值对重新计算键的哈希值和索引值 rehash 到 ht[1] 上;
重复 rehash 直到 ht[0] 包含的所有键值对全部迁移到了 ht[1] 之后释放 ht[0], 将 ht[1] 设置为 ht[0], 并在 ht[1] 新创建一个空白哈希表, 为下一次 rehash 做准备.
渐进 Rehash 过程
Redis 的 rehash 动作并不是一次性完成的, 而是分多次, 渐进式地完成的, 原因在于当哈希表里保存的键值对数量很大时, 一次性将这些键值对全部 rehash 到 ht[1] 可能会导致服务器在一段时间内停止服务, 这个是无法接受的.
针对这种情况 Redis 采用了渐进式 rehash, 过程的详细步骤:
为 ht[1] 分配空间, 这个过程和普通 Rehash 没有区别;
将 rehashidx 设置为 0, 表示 rehash 工作正式开始, 同时这个 rehashidx 是递增的, 从 0 开始表示从数组第一个元素开始 rehash.
在 rehash 进行期间, 每次对字典执行增删改查操作时, 顺带将 ht[0] 哈希表在 rehashidx 索引上的键值对 rehash 到 ht[1], 完成后将 rehashidx 加 1, 指向下一个需要 rehash 的键值对.
随着字典操作的不断执行, 最终 ht[0] 的所有键值对都会被 rehash 至 ht[1], 再将 rehashidx 属性的值设为 - 1 来表示 rehash 操作已完成.
渐进式 rehash 的思想在于将 rehash 键值对所需的计算工作分散到对字典的每个添加, 删除, 查找和更新操作上, 从而避免了集中式 rehash 而带来的阻塞问题.
看到这里不禁去想这种捎带脚式的 rehash 会不会导致整个过程非常漫长? 如果某个 value 一直没有操作那么需要扩容时由于一直不用所以影响不大, 需要缩容时如果一直不处理可能造成内存浪费, 具体的还没来得及研究, 先埋个问题吧!
Q4: 跳跃链表了解吗? Redis 的 Zset 如何使用跳表实现的?
ZSet 这种数据类型也非常有用, 在做排行榜需求时非常有用, 笔者就曾经使用这种数据类型来实现某日活 2000w 的 App 的排行榜, 所以了解下 ZSet 的底层实现很有必要, 之前笔者写过两篇文章介绍跳跃链表和 ZSet 的实现, 因此查阅即可.
深入理解跳跃链表 [一]
深入理解跳表在 Redis 中的应用
Q5:Redis 为什么使用单线程? 讲讲 Redis 网络模型以及单线程如何协调各种事件运行起来的?
Redis 在新版本中并不是单纯的单线程服务, 一些辅助工作会有 BIO 后台线程来完成, 并且 Redis 底层使用 epoll 来实现了基于事件驱动的反应堆模式, 在整个主线程运行工程中不断协调时间事件和文件事件来完成整个系统的运行, 笔者之前写过两篇相关的文章, 查阅即可得到更深层次的答案.
理解 Redis 单线程运行模式
理解 Redis 的反应堆模式
浅析 Redis 4.0 新特性之 LazyFree
5. 巨人的肩膀
- https://lynnapan.github.io/2017/07/14/redis_sds/
- http://redisbook.com/index.html
来源: https://www.cnblogs.com/backnullptr/p/12028566.html