写点什么

我见过最详细的 Redis 解析:不懂 Redis 为什么高性能?如何做高可用

用户头像
极客good
关注
发布于: 刚刚

> **2\. 渐进式 rehash 的好处** 将 rehash 操作分摊到字典的每个增/删/改/查操作上,避免集中 rehash 带来庞大的计算量而导致服务器停顿。 > **3\. rehash 过程中的查找/插入操作** > > 1. 查找:在 rehash 过程中会同时使用 ht[0]和 ht[1],如果要查找某个 key,会先在 ht[0]中查找,如果没找到,继续在 ht[1]中查找。 > 2. 插入:在 rehash 过程中新增的键值对会被保存到 ht[1],保证了 ht[0]的键值对数量只减不增。 > ## 跳跃表 ### 特点 跳跃表基于分值从小到大排序,查找的过程近似二分查找。 ### 结构定义 跳跃表基于有序链表实现,通过在链表的基础上增加多级索引提升查找的效率。跳跃表每一层都是一个链表,最底层链表包含所有元素,链表的每个节点包含 2 个指针,一个 forward 指针指向同一链表中该节点的下一个节点,一个 backward 指向同一链表中该节点的前一个节点。 typedef struct zskiplist { //头节点、尾节点 struct zskiplistNode *header, *tail; //跳跃表长度(包含的节点数量) unsigned long length; //跳跃表内层数最大的节点的层数 int level; } zskiplist; typedef struct zskiplistNode { //对象,唯一 robj *obj; //分值,跳跃表根据分值从小到大排列 double score; //后退指针,指向当前节点的上一个节点,用于从表尾遍历 struct zskiplistNode *backward; //层级数组 struct zskiplistLevel { //前进指针,用于从表头遍历 struct zskiplistNode *forward; //前进指针指向的节点和当前节点的跨度 unsigned int span; } level[]; } zskiplistNode; ![](https://static001.geekbang.org/infoq/df/df556c563ff194e46de4e675c9c7eb3c.png) ### 操作过程 1. 查找:从当前最高的 level 开始,向前查找,如果当前节点的 score 小于插入节点的 score,继续查找下一个节点;反之,则往下一层继续查找(类似于二分查找)。 ![](https://static001.geekbang.org/infoq/4a/4ac47e9e7bd0180e9352f0e25e88014e.png) 2. 插入:从当前最高的 level 开始,向前查找,如果当前节点的 score 小于插入节点的 score,继续查找下一个节点;反之,则往下一层继续查找,直到第一层为止。跳跃表插入操作的时间复杂度是 O(logN)。 3. 删除:自上而下查找第一次出现该节点的索引,并逐层找到每一层对应的节点。删除每一层查找到的节点,如果该层只剩下 1 个节点,删除整个一层(原链表除外)。跳跃表删除操作的时间复杂度是 O(logN)。 > ## 整数集合 ### 特点 整数集合可以去重且有序的保存整数值。 > **整数集合通过二分查找法获取元素查找和插入位置定位。** ### 结构定义 整数集合可以保存 16 位、32 位、64 位的整数,集合中整数的类型取决于 encoding 属性。 typedef struct intset { //编码方式:int16_t、int32_t、int64_t uint32_t encoding; //元素数量 uint32_t length; //保存元素的数组 int8_t contents[]; } intset; ![](https://static001.geekbang.org/infoq/de/de58578bfaa524a57f7a9e183cb8483f.png) ### 类型升级 当插入的新元素的类型比整数集合现有的元素类型长,会触发类型升级。 类型升级的过程: 1. 根据新元素类型扩展整数集合底层数组 intset.contents 空间大小,并为新元素分配空间; 2. 将现有的元素转换成与新元素相同的类型,并有序放到数组正确的位置; 3. 将新元素添加到数组; 整数集合通过类型升级操作提升了集合的灵活性,不用担心出现类型错误,而且升级操作只会在需要的时候进行,节约内存。 > **整数集合不支持类型降级操作。** > ## 压缩列表 ### 特点 压缩列表是顺序存储的数据结构,为了节约内存而开发的。 ### 结构定义 一个压缩列表可以包含任意个节点,每个节点可以包含一个字节数组或一个整数值。 ![](https://static001.geekbang.org/infoq/f4/f4d9e17cdbd714e4671df1c5f6bd0131.png) 1. zlbytes:记录压缩列表大小; 2. zltail:尾节点偏移量(通过 zltail 可以确定尾节点位置); 3. zllen:记录压缩列表节点数量; 4. entry:压缩列表节点; 5. zlend:标记压缩列表末端; ![](https://static001.geekbang.org/infoq/a3/a3706f6754ebe6b80e178940016c297a.png) 1. previour_entry_length:记录前一个节点所占字节数(可以根据当前节点起始地址+previour_entry_length 计算前一个节点的起始地址,实现从表尾向表头遍历); * 如果前一个节点<254 字节,previour_entry_length=1 字节; * 如果前一个节点>254 字节,previour_entry_length≥5 字节; 2. encoding:content 数据类型和长度; 3. content:节点值,可以是一个字节数组或整数值; ### 连锁更新 压缩列表的每个节点 previour_entry_length 属性都记录了前一个节点的长度,前一个节点大小变化(增/删/改)可能会导致 previour_entry_length 需要进行内存重分配(1 字节→5 字节或 5 字节→1 字节),可能产生连锁反应,导致多个节点的 previour_entry_length 都需要进行内存重分配。 # 基础数据类型 Redis 使用基本数据结构实现了对象系统,包含字符串对象、列表对象、哈希对象、集合对象、有序集合对象五种类型。可以根据使用场景选择对象的编码,提高 Redis 的灵活性和效率。 typedef struct redisObject { //对象类型(字符串、列表、哈希表、集合、有序集合) unsigned type:4; //对象编码 unsigned encoding:4; //记录对象最后一次被访问的时间,用于计算对象的空转时长 unsigned lru:REDIS_LRU_BITS; //对象引用计数,用于内存回收和对象共享 int refcount; //指向底层实现数据结构 void *ptr; } robj; > **在执行命令时,Redis 根据对象类型判断该对象是否能执行执行的命令,通过获取 redisObject.type 实现。** > ## 字符串(string) Redis 字符串是可变的,基于 SDS 实现。 > **在 Redis 中,long、double 类型的浮点数会先转为字符串再进行保存,读取时再将字符串转为浮点数。** ### 编码 1. int:long 型整数; 2. raw:长度>32 字节的字符串; 3. embstr:长度<32 字节的字符串,只读; > **raw 编码会调用 2 次内存分配函数来创建 redisObject 结构和 sdshdr 结构,embstr 编码只调用一次内存分配函数分配一块连续的内存空间,空间中一次包含 redisObject 结构和 sdshdr 结构。** > >![](https://static001.geekbang.org/infoq/b1/b118af8d73ed651fd65347709e99d71c.png) ### 编码转换 1. int 编码的字符串保存的不再是整数值,int → raw; 2. 修改 embstr 编码的字符串,embstr → raw; ### 命令 127.0.0.1:6379> set name1 java # 添加 OK 127.0.0.1:6379> mset name2 c name3 go # 批量添加 OK 127.0.0.1:6379> keys * # 获取所有 key 1) "name3" 2) "name2" 3) "name1" 127.0.0.1:6379> mget name1 name3 # 批量获取 1) "java" 2) "go" 127.0.0.1:6379> set a 1 OK 127.0.0.1:6379> incr a # 自增 1 (integer) 2 127.0.0.1:6379> incrby a 10 # 自增 10 (integer) 12 127.0.0.1:6379> decr a # 自减 1 (integer) 11 127.0.0.1:6379> decrby a 5 # 自减 5 (integer) 6 > ## 列表(list) ### 编码 1. ziplist:使用压缩列表实现,每个节点保存一个列表元素; ![](https://static001.geekbang.org/infoq/0e/0e645ebb2b66a86ed34c2888380b2cd8.png) 2. linkedlist:使用双向链表实现,每个节点保存一个字符串类型的列表元素; ![](https://static001.geekbang.org/infoq/dc/dc119059f421b18d375e80252bb668cb.png) ### 编码转换 列表所有字符串元素长度<64 字节且列表包含的元素数量<512 个时使用 ziplist 编码,否则使用 linkedlist 编码。 ### 命令 127.0.0.1:6379> rpush books java c go python 添加 (integer) 4 127.0.0.1:6379> llen books # 获取长度 (integer) 4 127.0.0.1:6379> lpop books # 出队(先进先出) "java" 127.0.0.1:6379> rpop books # 出栈(后进先出) "python" 127.0.0.1:6379> lrange books 0 -1 # 获取所有元素 1) "c" 2) "go" 127.0.0.1:6379> lindex books 1 # 获取索引为 1 的元素 "go" > ## 哈希表(hash) ### 编码 1. ziplist:使用压缩列表实现,同一个键值对的两个节点紧挨在一起,键在前,值在后; ![](https://static001.geekbang.org/infoq/23/23d36fa1c9d3d06aee3802076c57d834.png) 2. hashtable:使用字典实现; ![](https://static001.geekbang.org/infoq/83/83cc81aed35f9ee31683650ee4d9ed13.png) ### 编码转换 哈希表所有键和值得字符串长度<64 字节且哈希表包含的键值对数量<512 个时使用 ziplist 编码,否则使用 hashtable 编码。 ### 命令 127.0.0.1:6379> hset books book1 java # 添加 (integer) 1 127.0.0.1:6379> hmset books book2 go book3 c # 批量添加 OK 127.0.0.1:6379> hgetall books # 获取所有键值对 1) "book1" 2) "java" 3) "book2" 4) "go" 5) "book3" 6) "c" 127.0.0.1:6379> hlen books # 获取长度 (integer) 3 > ## 集合(set) ### 编码 1. intset:使用整数集合实现; ![](https://static001.geekbang.org/infoq/35/356ed901940e7e73816a5f4b85359b8e.png) 2. hashtable:使用字典实现,每个键都是字符串类型的集合元素,值为 NULL; ![](https://static001.geekbang.org/infoq/7f/7fe73d8294ee111f718e07eeb13aaf7e.png) ### 编码转换 集合所有元素都是整数值且集合包含的元素数量<512 个时使用 intset 编码,否则使用 hashtable 编码。 ### 命令 127.0.0.1:6379> sadd books c # 添加 (integer) 1 127.0.0.1:6379> sadd books java go python # 批量添加 (integer) 3 127.0.0.1:6379> sm ``` 【一线大厂 Java 面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】 浏览器打开:qq.cn.hn/FTf 免费领取 ``` embers books # 获取所有元素(无序,并不会和插入顺序一致) 1) "java" 2) "python" 3) "go" 4) "c" 127.0.0.1:6379> sismember books html # 查询某个元素是否存在 (integer) 0 127.0.0.1:6379> sismember books java (integer) 1 127.0.0.1:6379> scard books # 获取长度 (integer) 4 127.0.0.1:6379> spop books # 弹出一个元素 "java" > ## 有序集合(zset) ### 编码 1. ziplist:使用压缩列表,每个集合元素使用两个紧挨在一起的节点保存,第一个节点保存元素,第二个节点保存元素的分值; ![](https://static001.geekbang.org/infoq/03/03ce96abbdbde868c749a75f561cc4da.png) 2. skiplist:使用 zset 结构实现,一个 zset 结构包含一个跳跃表和一个字典,跳跃表和字典中的元素通过指针共享对象。 * 跳跃表按分值从小到大保存所有元素,通过跳跃表可以对有序集合进行范围操作; * 字典实现对象到分值的映射,字典中的每个键值对都保存了一个集合元素,实现 O(1)复杂度查找对象分值; ![](https://static001.geekbang.org/infoq/69/69aeba2d95a2be239fda3309a63f90cb.png) ### 编码转换 有序集合所有元素长度<54 字节且包含的元素数量<128 个时使用 ziplist 编码,否则使用 skpilist 编码。 ### 命令 127.0.0.1:6379> zadd books 5 java # 添加 (integer) 1 127.0.0.1:6379> zadd books 2 c (integer) 1 127.0.0.1:6379> zadd books 6 go (integer) 1 127.0.0.1:6379> zadd books 9 html (integer) 1 127.0.0.1:6379> zrange books 0 10 # 获取正序排名[0,10]的元素 1) "c" 2) "java" 3) "go" 4) "html" 127.0.0.1:6379> zrange books 2 3 # 获取正序排名[2,3]的元素 1) "go" 2) "html" 127.0.0.1:6379> zrevrange books 0 -1 # 获取逆序排名的所有元素 1) "html" 2) "go" 3) "java" 4) "c" 127.0.0.1:6379> zcard books #获取长度 (integer) 4 127.0.0.1:6379> zscore books java # 获取指定元素的分值 "5" 127.0.0.1:6379> zrangebyscore books 3 7 #获取分值[3,7]的元素 1) "java" 2) "go" 127.0.0.1:6379> zrem books c # 删除元素 (integer) 1 127.0.0.1:6379> zrange books 0 -1 # 获取所有元素 1) "java" 2) "go" 3) "html" > ## 总结 ![](https://static001.geekbang.org/infoq/5e/5e89d712d51509b806299c8b32efee0e.png) # 特殊数据类型 > ## Geo Redis 3.2 版本以后,提供了基于 geohash 和有序集合实现地理位置相关功能的 Geo 模块。 ### 实现原理 Geo 基于 geohash 和有序集合实现,使用有序集合保存位置对象,分值为位置对象经纬度对应的 52 为 geohash 值。 ### 命令 127.0.0.1:6379> geoadd users:locations 120.346111 31.556381 user1 120.375821 31.5603682 user2 # 添加地理位置信息 (integer) 2 127.0.0.1:6379> geopos users:locations user1 # 获取 user1 地理位置 1) 1) "120.34611314535140991" 2) "31.55637987511895659" 127.0.0.1:6379> geodist users:locations user1 user2 m # 计算 user1 和 user2 位置距离(m:距离以米为单位) "2850.3519" 127.0.0.1:6379> georadius users:locations 120.375821 31.556381 5 km withcoord withdist withhash asc count 100 #获取指定范围 5km 范围以内最多 100 个元素(asc:按距离从近到远排序,desc:按距离从远到近排序,count 100:最多返回 100 个元素) 1) 1) "user2" 2) "0.4433" # withdist:距离目标位置的距离 3) (integer) 4054421167795118 4) 1) "120.37582129240036011" # withcoord :元素的经纬度 2) "31.5603669915025975" 2) 1) "user1" 2) "2.8157" 3) (integer) 4054421060663027 4) 1) "120.34611314535140991" 2) "31.55637987511895659" 127.0.0.1:6379> georadiusbymember users:locations user1 5 km withcoord withdist withhash asc count 100 # 获取指定元素 5km 范围以内最多 100 个元素 1) 1) "user1" 2) "0.0000" 3) (integer) 4054421060663027 4) 1) "120.34611314535140991" 2) "31.55637987511895659" 2) 1) "user2" 2) "2.8504" 3) (integer) 4054421167795118 4) 1) "120.37582129240036011" 2) "31.5603669915025975" ### 应用场景 1. 查找附近的人; > ## HyperLogLog HyperLogLog 是一种概率数据结构,提供不精确的去重计数方案,标准误差是 0.81%。 ### HyperLogLog 和 set 的区别 1. set 存储统计元素,所以元素较多时需要占据大量内存空间; 2. HyperLogLog 不存储统计元素,仅存储存在的标记,最多只需要 12K 内存空间; ### 命令 127.0.0.1:6379> pfadd users1 user1 user3 user5 user7 # 添加 (integer) 1 127.0.0.1:6379> pfcount users1 # 统计 users1 (integer) 4 127.0.0.1:6379> pfadd users2 user1 user2 user4 (integer) 1 127.0.0.1:6379> pfcount users2 (integer) 3 127.0.0.1:6379> pfmerge users1 users2 # 将 users1 和 users2 合并累加计数,形成新的 users1 OK 127.0.0.1:6379> pfcount users1 (integer) 6 ### 应用场景 1. 统计日/月活用户:每天使用一个 HyperLogLog 记录日活,使用用户 id 作为标识,合并当月每天 HyperLogLog 即可得到月活; 2. 统计网页访客 UV:使用 cookie 作为标识,相同的客户端访问最多只计数 1 次; > ## 布隆过滤器 布隆过滤器是一种数据结构。当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在。 ### 实现原理 布隆过滤器基于一个位数组+多个哈希函数实现。 1. 插入 向布隆过滤器中添加 key 时,首先使用多个哈希函数对 key 进行 hash 得到一个哈希值,然后再将各个哈希值对位数组长度进行取模运算得到索引值,每个 hash 函数都会算得一个不同的索引值,再将位数组对应索引位置都置为 1。 2. 查找 向布隆过滤器查找某个 key 是否存在时,首先使用多个哈希函数对 key 进行 hash 得到一个哈希值,然后再将各个哈希值对位数组长度进行取模运算得到索引值,每个 hash 函数都会算得一个不同的索引值,判断位数组中这几个索引位置的值是否都为 1,只要有一个位为 0,那么说明这个 key 不存在,如果都为 1,并不说明这个 key 就一定存在,只是极有可能存在,因为这些位被置为 1 可能是因为其它的 key 存在所致。 ### 应用场景 1.过滤垃圾邮件; 2.URL 去重; 3.防止缓存穿透; # 持久化 Redis 的持久化方式主要有 2 种:RDB 持久化和 AOF 持久化。 > ## RDB 持久化 RDB 持久化可手动执行,也可根据服务器定期执行 bgsave。 ### 实现原理 RDB 持久化将某个时间点上的数据保存到 RDB 文件中(快照),再将 RDB 文件保存到磁盘。在服务器启动时,可以通过载入 RDB 文件还原数据。 > **服务器启动时会自动执行 RDB 文件的载入(RDB 文件存在且未开启 AOF 功能),载入过程中服务器处于阻塞等待状态。** 可以通过 save/bgsave 命令执行 RDB 持久化操作。 > #### save 命令 执行 save 命令会使 Redis 服务器进程会阻塞等待直到 RDB 文件创建完毕,在服务器进程阻塞期间,服务器不能处理任何命令请求。 > #### bgsave 命令 bgsave 命令会派生出一个 Redis 服务器进程的子进程,由子进程负责创建 RDB 文件,当 RDB 创建完成后,子进程向父进程发送信息,服务器进程在此期间可以继续处理命令请求并轮询等待子进程的信号。 ![](https://static001.geekbang.org/infoq/49/49f6ab89f724eca24aeb60f3172dbdd7.png) > **1\. 为什么 bgsave 要使用子进程而不是用线程?** 利用操作系统的写时复制机制,避免不必要的内存拷贝。 > **2\. 自动执行 bgsave** 服务器会根据配置的 save 选项(保存条件)定期执行 bgsave,save 选项的内容以【秒数-修改数】格式保存在 redisServer.saveparam 数组中。每次调用 serverCron()函数时会检查 save 选项保存的条件是否满足(满足 save 选项的任一条件),如果满足就执行 bgsave 命令。 > > * 根据 redisServer.dirty(上一次成功执行 save/bgsave 命令后服务器数据执行了多少次修改)获取修改次数; > * 根据 redisServer.lastsave(上一次成功执行 save/bgsave 命令的时间)获取间隔时间。 ### RDB 文件结构 ![](https://static001.geekbang.org/infoq/75/75a9db96fb837504ae21d682df6eed45.png) 1. REDIS:RDB 文件的开头是一个 5 字节的“REDIS”字符串,在服务器启动载入文件时校验是否为 RDB 文件; 2. db_version:4 字节的字符串整数,记录 RDB 文件的版本号,如 006 代表 RDB 文件的版本为第 6 版; 3. database:各个数据库保存的键值对数据; ![](https://static001.geekbang.org/infoq/38/38f726b9eac00b152825641cdddef595.png) * SELECTDB:1 字节,标记接下来要读取的是数据库号码; * db_number:数据库号码,读入 db_number 后会执行 select 命令切换数据库; * key_value_pairs:数据库中所有键值对,未过期键会记录键类型、键、值,过期键会额外保存过期键标志、过期时间; 4. EOF:1 字节,标志 RDB 文件正文内容结束。 5. check_sum:8 字节无符号整数的校验和,通过 REDIS+db_version+database+EOF 计算得出,在载入 RDB 文件时用于校验 RDB 文件是否损坏。 > ## AOF 持久化 AOF 持久化以 Redis 命令请求协议的格式(纯文本)保存服务器执行的写命令,在服务器启动时,可以通过执行 AOF 文件中的写命令还原数据。 ### 执行过程 1. 命令追加:服务器每执行完一个写命令,会将写命令追加到 redisServer.aof_buf 缓冲区(字符串)末尾; 2. 文件写入:每次执行 serverCron()函数时将 redisServer.aof_buf 缓冲区中的数据写入 AOF 文件中; 3. 文件同步:根据服务器配置的持久化行为判断是否需要 AOF 文件刷入磁盘; * always:将 redisServer.aof_buf 缓冲区中所有数据写入 AOF 文件并将 AOF 文件刷入磁盘。最慢,但是安全性最高; * everysec:默认值,将 redisServer.aof_buf 缓冲区中所有数据写入 AOF 文件,如果距离上一次将 AOF 文件刷入磁盘时间超过 1s,则再次将 AOF 文件刷入磁盘。较快,但是出现故障会丢失 1s 的命令数据; * no:将 redisServer.aof_buf 缓冲区中所有数据写入 AOF 文件,由操作系统决定何时将 AOF 文件刷入磁盘。最快,但是出现故障会丢失上次 AOF 文件同步之后的数据; > **在操作系统中,write()系统调用先将写入的数据保存在内核缓冲区中,再刷入磁盘。** ### 如何载入 AOF 文件 服务器启动载入 AOF 文件时,只需要将 AOF 文件中的所有命令执行一遍就可以还原数据。 1. 创建一个不带网络连接的伪客户端(Redis 命令只能在客户端上下文中执行); 2. 通过伪客户端执行 AOF 文件中的命令; ### AOF 重写 服务器运行的越久,AOF 文件中的内容将会越多,文件体积越来越大,使用 AOF 文件还原数据耗时也就越长,通过 AOF 重写能解决 AOF 文件膨胀的问题。 > #### 什么是 AOF 重写? Redis 会创建一个新的 AOF 文件替代现有的 AOF 文件,新旧两个 AOF 文件保存的数据相同,但是新的 AOF 文件中不包含冗余命令,所以新的 AOF 文件通常会比旧的 AOF 文件体积小很多。 > #### AOF 重写过程 > **AOF 重写不需要操作当前 AOF 文件。** 1. rewriteaof 命令会派生出一个 Redis 服务器进程的子进程,由子进程负责读取服务器当前数据,并为每个键值对生成一条命令写入新的 AOF 文件中; 2. 服务器会将在子进程重写期间执行的写命令保存到 AOF 重写缓冲区 redisServer.aof_rewrite_buf_blocks 中,也就是在 AOF 重写期间服务器每执行一个写命令,都需要保存进 AOF 缓冲区和 AOF 重写缓冲区; 3. 当子进程完成 AOF 重写后,向父进程发送一个信号; 4. 父进程接收到子进程的信号,将 AOF 重写缓冲区取中的所有内容添加到新的 AOF 文件中,并对新的 AOF 文件改名,覆盖现有的 AOF 文件;(这个过程父进程是阻塞不接收客户端请求的) ![](https://static001.geekbang.org/infoq/6a/6a436e6a549faded779c90b72df2bb62.png) > ## 比较 AOF 和 RDB 1. RDB 保存某一刻的数据快照,全量备份; 2. RDB 的 bgsave 命令通过多进程的写时复制机制来实现持久化; 3. AOF 通过缓冲区保存写命令后再写入文件,增量备份; 4. AOF 更新频率高于 RDB,如果服务器开启了 AOF,会优先使用 AOF 文件还原数据;

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
我见过最详细的Redis解析:不懂Redis为什么高性能?如何做高可用