文章目录1. redis数据库的概述1概述2为什么使用redis3关系型数据库和非关系型数据库对比2. redis的数据类型1概述2字符串类型3散列类型hash(map)4列表类型list5无序集合类型set6有序集合类型zset(有序且唯一)3. redis的通用操作4. redis多个数据库间的操作5. redis的持久化机制1概述2rdb(Redis Database)3aof(Apend Only File)4RDBAOF(混合持久化)5持久化选择的建议6. redisTemplate1) jedis和redisTemplate的区别2) redisTemplate操作redis7. redis的过期策略1定期删除2惰性删除3内存淘汰机制8. redis的优缺点1优点2缺点8. 缓存穿透1概念2原因3处理方法9. 缓存击穿1概念2原因3处理方法10. 缓存雪崩1概念2原因3处理方法11. 布隆过滤器1概念2核心原理3优点4缺点5应用场景6 变种与优化12. redis类型和编码关系1redis对象的类型2redis对象的编码3redis对象类型和编码的对应关系4String 类型和对应编码5list 类型和对应编码6hash 类型和对应编码7set 类型和对应编码8zset 类型和对应编码13. redis底层数据结构1SDS2embstr3raw4ziplist5linkedlist6hashtable7skiplist1. redis数据库的概述1概述redis其实就是缓存技术当浏览器第一次访问服务器的时候程序会从数据库中查询获取数据之后将数据放入redis缓存中。 那么之后浏览器再去访问服务器时不会直接再查询数据库而是先看redis缓存中有没有如果有的话直接从redis缓存中获取没有的话再查询数据库获取。 redis(缓存技术)的作用就是解决频繁的去操作数据库带来的效率低问题。2为什么使用redis1. 浏览器的数据一般都是通过数据库查询获取到的针对一些经常变化的数据我们需要从数据库获取但是针对一些变化量很慢 甚至很长一段时间可能都不变化的数据如果也每次都从数据库获取那么就会加大数据库的负担同时效率也会比较低。 2. 这时候使用缓存技术redis当浏览器第一次访问服务器的时候程序会从数据库中查询获取数据之后将数据放入redis缓存中 那么之后浏览器再去访问服务器时不会直接再查询数据库而是从redis中直接获取就可以大大加快效率。3关系型数据库和非关系型数据库对比1数据模型 关系型数据库表格结构行和列严格遵循Schema设计。 schema设计是为数据库构建一个清晰、高效、可扩展的蓝图或者数据结构说明书的过程。 一个完整的数据库schema通常定义了以下内容 1表数据的核心容器。 2字段表中数据的属性。 3数据类型规定每个字段存储什么类型的数据。 4主键能唯一标识表中每条数据的字段。 5外键用来连接不同的表的关系字段建立表与表之间的关联。 6约束保证数据完整性的规则如非空、唯一性、默认值等。 非关系型数据库灵活模型文档、键值、列族、图等。 2扩展方式 关系型数据库垂直扩展提升单机性能 非关系型数据库水平扩展分布式集群 3事务支持 关系型数据库强一致性ACID 非关系型数据库最终一致性BASE理论或部分支持ACID 4查询语言 关系型数据库标准SQL 非关系型数据库非标准化 5适用场景 关系型数据库复杂事务、强一致性要求 非关系型数据库高并发、大数据量、灵活结构2. redis的数据类型1概述redis的key全部都是字符串命名一般是项目名_子模块名_key名称 value 有5种数据类型分别是 1字符串类型String 2哈希类型hash 3列表类型list 4无序集合类型set 5有序集合类型zset2字符串类型设置set key value 获取get key 删除del key3散列类型hash(map)设置单个hset key subkey1 subvalue1 //设置一个键值对 设置多个hmset key subkey1 subvalue1 subkey2 subvalue2… //设置多个键值对 获取单个hget key subkey1 //获取一个子键的值 获取多个hmget key subkey1 subkey2... //获取多个子键的值 获取一个key(map) 中的所有信息hgetall key 删除一个key(map)的一个或多个子键hdel key subkey1 subkey2 ... 删除整个key(map)del key4列表类型list从左端开始插入数据lpush key member1 member2... 从右端开始插入数据rpush key member1 member2.. : 获取 lrange key startindex endindex //查看索引从startindex到endindex的数据 lrange key 0 -1 //全查 从左边开始删除lpop key //左边弹出(删除)一个 从右边开始删除rpop key //右边弹出(删除)一个5无序集合类型set添加sadd key member1 member2… 查看smembers key 删除srem key member1 member2…6有序集合类型zset(有序且唯一)num排序字段 添加zadd key num1 value1 num2 value2... //如果有重复值后面会覆盖前面的 获取成员的num值zscore key value 获取元素的长度zcard key 删除指定成员zrem key value1 value2...3. redis的通用操作1. 查询所有的key keys * 2. 断是否有指定的keyexists key //若有返回1,否则返回0 3. 重命名rename key 新key 4. 判断一个key的类型type key 5. 直接删除del key4. redis多个数据库间的操作1. 切换到指定index的库select index 2. 将当前库的数据移动到指定库中move key 指定数据库 3. 返回当前库中有多少个keydbsize 4. 清空当前数据库数据flushdb 5. 清空当前实例下所有的数据库数据flushall //删库不用5. redis的持久化机制1概述持久化机制想让redis服务器关闭的时候数据还能够保存下来也就是将数据从内存保存到磁盘。 redis的持久化有3种机制 1rdb(快照方式) //默认开启的 2aof(配置文件命令方式) //默认不开启 3混合持久化RDBAOF(Redis 4.0 以后支持)2rdb(Redis Database)1. 默认状态 默认是开启的 2. 设置方式 在redis.windows.conf 中 查找save 3. 保存策略 # after 900 sec (15 min) if at least 1 key changed # after 300 sec (5 min) if at least 10 keys changed # after 60 sec if at least 10000 keys changed 即 1 如果1分钟之内有10000个数据存到了redis中就保存到磁盘一份。 2 如果5分钟之内有10个数据存到了redis中就保存到磁盘一份。。 3 如果15分钟之内有1个数据存到了redis中就保存到磁盘一份。 4. 工作原理 快照生成定期将内存中的数据集生成二进制快照文件(默认文件名为dump.rdb)。 5. 触发方式 1自动触发配置文件设置了保存策略满足保存策略会自动触发。 2手动触发执行SAVE阻塞主进程或BGSAVE后台异步生成默认方式。 6. 恢复数据 重启redis的时候会自动加载rdb文件。 7. 优点 1高性能生成紧凑的二进制文件恢复速度快。 2备份方便文件体积小适合全量备份和灾难恢复。 3最小化内存占用通过fork子进程生成快照主进程无需额外内存开销除了fork瞬间的页表复制。 8. 缺点 1数据丢失触发保存需要条件如果写入或者修改了数据还没有触发保存那么这些数据会丢失。 2大数据量时延迟fork子进程在数据量大时可能阻塞主进程尤其在虚拟内存不足时。3aof(Apend Only File)1. 默认状态 默认不开启 2. 设置方式 在redis.windows.conf 中 查找appendonly设置成 yes表示开启。 3. 保存策略 1)appendfsync always每次都写入往redis中写一个磁盘保存一个。 2)appendfsync everysec每秒写入一秒往磁盘保存一次。 3appendfsync no不写入不往磁盘上保存服务一关数据就清空。 4. 工作原理 日志记录记录每个写操作命令如SET、DEL到AOF文件。 5. 触发方式 1) 手动执行BGREWRITEAOF. 2) 自动触发根据auto-aof-rewrite-percentage和auto-aof-rewrite-min-size配置。 6. 优点 1高数据安全可配置为近乎实时持久化。 2易修复AOF文件为追加日志格式损坏时可通过redis-check-aof工具修复。 3可读性AOF文件为文本格式便于人工分析。 7. 缺点 1文件体积大相同数据集下AOF文件通常比RDB大。 2恢复速度慢需要逐条执行命令恢复耗时长。 3写性能影响高频同步策略如always可能降低吞吐量。4RDBAOF(混合持久化)1. 实现方式 1需要Redis 4.0 以上才可以。 2. 设置方式 设置 aof-use-rdb-preamble 值为yes 那么AOF文件由2部分组成 1RDB格式的快照数据快速恢复基础数据集。 2AOF日志记录快照后的写操作。 3. 优点 1兼顾RDB的快速恢复和AOF的低数据丢失风险。 2文件体积小于纯AOF恢复速度快于纯AOF。5持久化选择的建议1允许分钟级数据丢失RDB 2需要高数据安全性AOF 3平衡恢复速度与数据安全混合持久化(RDBAOF) 4灾备与历史版本回溯RDB定期备份 AOF实时日志6. redisTemplate1) jedis和redisTemplate的区别1. jedis是redis官方推荐的面向java操作redis的客户端是最基础的。 2. redisTemplate是SpringDataRedis中对 jedis API的高度封装相对于Jedis来说可以更方便的更换redis的java客户端比jedis多了自动管理连接池的特性更容易和其他Spring框架搭配使用。2) redisTemplate操作redis1. String redisTemplate.opsForValue().set(key,value); //保存字符串数据不设置有效时间 redisTemplate.opsForValue().set(key,value,10,min); //保存字符串数据设置有效时间 redisTemplate.opsForValue().get(key); //获取key对应的值 2. 哈希(map) redisTemplate.opsForHash().put(key,key1,value1,key2,value2); //存多个key/value redisTemplate.opsForHash().putAll(key,map); //直接存map redisTemplate.opsForHash().hasKey(key,key1); //确定key是否存在 3. list redisTemplate.opsForList().leftPush(key,value); //从左边插入 redisTemplate.opsForList().leftPop(); //弹出最左边的元素 4. set redisTemplate.opsForSet().add(a1,a2…); //保存数据 5. zset redisTemplate.opsForZSet().add(“zset1”,”ww”) //保存数据7. redis的过期策略1定期删除redis 每过100ms 就会随机检查发现过期的key就会删除掉。 实时删除太消耗cpu资源尤其在高并发的情况下需要消耗大量时间来处理请求。2惰性删除redis 在获取某个key的时候会先检查下这个key是否设置了过期时间以及是否已经过期如果过期那么就会删除掉。3内存淘汰机制在redis.conf 中有一行配置maxmemory-policy allkeys-lru 当内存不足以容纳新写入的数据时redis会在键空间中移除最近最少使用的key。8. redis的优缺点1优点获取数据比较快速 快速的原因为 1. 纯内存操作。 2. 单线程避免了频繁的上下文切换。 3. 采用非阻塞 I/O 多路复用机制 只有单个线程通过跟踪每个I/O 流的状态来管理多个I/O流。2缺点1缓存和数据库双写一致性原则 一致性分为最终一致性和强一致性如果数据库有强一致性要求那么就不能使用redis。 采用正确的更新策略先更新数据库再更新缓存针对可能存在的删除缓存失败的问题可以提供一个补偿措施。比如利用消息队列。 2缓存雪崩 3缓存穿透 4缓存的并发竞争问题8. 缓存穿透1概念故意去请求缓存中不存在的数据导致所有的请求都到数据库上造成数据库压力过大或连接异常。2原因1恶意攻击故意请求不存在的数据。 2业务逻辑错误例如查询条件为负数或不存在的主键。3处理方法1缓存空对象当查询数据库返回空时将空结果或特殊标记缓存起来并设置较短的过期时间。这样后续请求会命中缓存保护数据库。 缺点如果有大量不同的不存在的key会缓存大量空对象占用内存。 2提供一个能迅速判断请求是否有效的拦截机制比如布隆过滤器内部维护一系列合法 有效的key迅速判断出请求的key是否合法。9. 缓存击穿1概念一个热点key在过期时大量请求同时访问这个key导致所有请求都落到数据库上引起数据库压力激增。2原因1热点数据过期。3处理方法1设置热点数据永不过期对于特别热点的数据可以设置永不过期然后通过后台异步更新缓存。 2加互斥锁当缓存失效时不立即去数据库加载而是先使用分布式锁如Redis的setnx保证只有一个线程去查询数据库并更新缓存其他线程等待并重新读取缓存。 缺点如果锁竞争激烈性能会下降。10. 缓存雪崩1概念缓存大面积失效的时候又来了一波请求导致所有的请求都到了数据库上造成数据库连接异常。2原因1缓存服务器宕机。 2大量缓存key设置了相同的过期时间导致在同一时间失效。3处理方法1分散过期时间给缓存的失效时间加上一个随机值避免集体失效。 2缓存高可用使用Redis集群主从复制哨兵机制等保证缓存服务的高可用。 3降级和熔断当数据库压力过大时使用降级返回默认值或熔断直接拒绝请求机制保护数据库。 4提前预热在系统启动或低峰期提前加载热点数据到缓存。11. 布隆过滤器1概念布隆过滤器(Bloom Filter) 是一种空间效率极高的 概率型数据结构用于判断一个元素是否在一个集合中。 核心特点可能存在误判false positive但绝不会有漏判false negative。2核心原理1数据结构 1. 一个长度为 m 的比特数组bit array 2. k 个不同的哈希函数 2操作流程 1. 添加元素 1) 将元素通过 k 个哈希函数映射到数组的 k 个位置 2) 将这些位置的比特位设为 1 2. 查询元素 1) 将元素通过相同的 k 个哈希函数映射到数组的 k 个位置 2) 如果所有位置都为 1 → 元素“可能”存在 3) 如果任一位置为 0 → 元素“一定”不存在3优点1. 空间效率极高相比哈希表节省大量内存。 2. 查询速度快O(k) 时间复杂度常数级。 3. 无漏判如果布隆过滤器说元素不存在那一定不存在。 4. 支持并发只读操作可完全并行。4缺点1. 存在误判可能将不存在的元素判为存在。 2. 基础版本不能删除元素。 3. 不支持元素计数。 4. 需要预先知道数据规模。5应用场景1. 缓存穿透防护 2. 恶意URL检测浏览器检查URL是否在黑名单中 3. 分布式系统 1避免查询不存在的数据到数据库。 2) 路由表快速查询。 4. 推荐系统去重防止重复推荐相同内容。6 变种与优化1. 计数布隆过滤器 特点 1用计数器代替比特位。 2支持删除操作 3空间开销增加。 2. 布谷鸟过滤器 特点 1支持删除。 2空间效率更高。 3查询性能更好。 3. 可扩展布隆过滤器 特点 1动态调整大小。 2适应数据量变化。12. redis类型和编码关系1redis对象的类型可以通过命令TYPE KEY 来查看 redis 对象的类型 redis对象的类型有5种分别是2redis对象的编码redis对象实际的底层数据结构是由编码决定的不同编码代表不同的数据结构。 可以通过命令 OBJECT ENCODING 来查看对应的编码。 redis的编码类型有 8种分别是3redis对象类型和编码的对应关系4String 类型和对应编码1. String类型对应的编码有3种分别是 1int当value值是整数值并且值可以转化为long类型时使用此时对象的类型是字符串编码是 int。 2embstr当value值是字符串并且长度≤44字节(5.0之前为39)时使用此时对象的类型是SDS字符串编码是 embstr。 3raw当value值是字符串并且长度44字节时使用此时对象的类型是SDS字符串编码是 raw。 2. 编码的转换 1int执行操作以后不再是可以转换成long类型的整数并且字节数44那么会转化为raw。 2embstr只要执行修改操作就会变成raw哪怕字节数不够也会变。5list 类型和对应编码1. list 类型对应的编码有2种分别是 1压缩列表ziplist使用ziplist的情况 a. 列表对象中每个元素的长度都小于64字节。 b. 列表的长度(元素数量)小于512。 【注意这2个值可以通过配置进行修改】 2双端链表linkedlist 注意新版本可能使用 quicklist 。 2. 转换 一开始先使用ziplist当不满足ziplist的条件时会自动转化成linkedlist。6hash 类型和对应编码1. hash类型对应的编码有2种分别是 1压缩列表ziplist使用ziplist的情况 a. key和value的字符串长度都小于64字节。 b. 哈希对象保存的键值对的总数量小于512键值是2个。 【注意这2个值可以通过配置进行修改】 2字典(哈希表)hashtable 2. 转换 一开始使用ziplist当不满足ziplist的情况时会自动转化为hashtable。7set 类型和对应编码1. set 类型对应的编码有2种分别是 1整数集合intset使用intset的情况 a. 集合对象保存的所有元素都是整数值。 b. 集合元素数量少于512个(可以进行配置修改) 注意 1intset可以保存类型为 INTSET_ENC_INT16INTSET_ENC_INT32INTSET_ENC_INT64 的整数值具体类型由集合中的编码方式决定。 2从小到大有序排列。 3不会重复。2字典(哈希表)hashtable 2. 转化 当符合intset编码的条件时会使用intstet结构当不符合instset编码的条件时会自动转化为hashtable。8zset 类型和对应编码1. set 类型对应的编码有2种分别是 1压缩列表ziplist使用ziplist的情况 a. 有序集合保存的元素数量小于等于128个 b. 有序集合保存的所有元素的长度都小于64字节 【注意这2个值可以通过配置进行修改】 2跳跃表字典skiplist 2. 转换 一开始使用ziplist当不满足ziplist的情况时会自动转化为 skiplist。13. redis底层数据结构1SDS1. 字符串类型有 1 C语言传统的字符串是一个字节数组末位总是一个空的字符并且以这个空的字符来判断是不是末位位置。 2简单动态字符串simple dynamic String简称SDS。 在redis中C字符串只会作为字符串字面量用在一些不用对字符串进行修改的地方如果需要对字符串的长度进行修改那么redis保存的就不再是C字符串而是SDS redis的key和value在底层都是SDS实现的。 2. SDS字符串的结构 1长度已经使用的字节数。 2剩余长度未使用的字节数。 3字节数组char类型的数组。 注意 a. SDS跟C字符串一样最后一个字符都是空字符这样就方便使用C字符串的一些函数。 b. 保存空字符的1个字节空间不计算在SDS的len属性里并且为空字符分配额外的1字节空间会通过函数自动的将空字符添加到字符串的末尾。3. C字符串和SDS的区别 1获取字符串长度方式不同 C字符串从第一个字符开始遍历到第一个空的字符结束,操作复杂度O(N)。 SDS : 对象中有属性可以直接获取到字符串的长度操作复杂度O(1)。 2缓存区溢出问题和内存泄漏 C字符串不记录自身长度在执行拼接操作时会直接在后面拼接如果在拼接前没有给字符串分配足够的空间就会导致缓存区溢出覆盖后面的数据如果是截取需要在截取后释放字符不再使用的空间如果没有释放就会造成内存泄漏。 SDS : 先判断空间是否满足修改需求如果满足就直接执行修改操作如果不满足会先扩展空间然后才执行修改操作。 3修改字符串时带来的内存重新分配次数不同 C字符串每次字符串修改都需要对内存进行一次重分配操作。 SDS : 字符串修改会判断当前的长度和剩余空间是否满足修改需求如果满足就不重新分配直接修改不满足时才进行重新分配。 4空间预分配 C字符串没有空间于分配每次修改字符串都需要重新分配空间。 SDS: 有一个free属性来预存储一部分空间这部分空间相当于多出来的空间。 预分配的原则 当字符串需要修改(主要是拼接)的时候先去判断预留空间是否满足修改后的长度如果满足就直接修改 如果不满足会判断修改后的字符串长度大小也就是len的值 a. 如果值小于1M那么程序会分配和len属性同样大小的未使用空间即lenfreeSDS的属性buf数组的实际长度为2len1, 1用来保存空字符。 b. 如果len的值大于1M程序会分配1M的未使用空间SDS buf数组的实际长度为len(M)1M1字节。 5惰性空间释放 C字符串截取字符串后需要通过重分配来释放多余的内存空间。 SDS 截取后不立即通过重分配来释放多余的内存空间而是使用free属性将这些字节的数量记录起来等待将来使用(将来字符串拼接时先判断free空间是否足够如果足够就不需要重新分配空间直接拼接只有free不够时才进行重分配扩展空间)。 6二进制安全 C字符串字符必须符合某种编码比如 ASCII 并且除了字符串的末尾之外 字符串里面不能包含空字符 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。 SDS: buf属性中存的不是字符而是一系列二进制数据API操作的时候也是以处理二进制数据的方式来处理buf数组中的数据通过len来判断是否是末位不受空字符的影响可以保存任意格式的二进制数据。 7兼容部分C字符串函数 C字符串字符数组末位是个空的字符。 SDS 末位也是一个空的字符可以使用C字符串的一部分函数。 4. SDS的优势 1容易获取字符串的长度。 2杜绝缓冲区溢出先判断空间是否足够再进行拼接操作。 3减少内存重分配次数不一定需要内存重分配。 4空间预分配策略sds空间默认设置为1M当空间不足1M时设置为空间实际大小。 5惰性空间释放缩短字符串时不立即释放多余内存而是更新 len 字段后续操作可复用空间。 6二进制安全。 7兼容部分C字符串的函数。2embstr1. 简单字符串一次性分配连续内存将 Redis 对象头redisObject和字符串内容存放在同一块连续内存中。 2. 适用于短字符串(长度 ≤ 44 字节Redis 5.0)3raw1. 两次分配内存先分配 redisObject再单独分配字符串内容的内存空间。 2. 适用于长度 44 字节Redis 5.0 3. embstr和raw的比较 相同点 都是使用redisobject和sdshdr结构来表示字符串对象。 不同点 1 raw 调用2次内存分配函数来分别分配redisobject和sdshdrredisobject和sdshdr很可能是不相邻的 embstr: 调用1次内存分配函数直接分配redisobject和sdshdrredisobject和sdshdr是相邻的 2raw释放对象需要2次内存释放函数 embstr: 释放对象只需要1次内存释放函数 3raw编码的字符串对象的所有数据很可能保存在两块不相邻的内存里 embstr: 编码的字符串对象的所有数据保存在1块连续的内存里能够更好的利用缓存带来的优势。4ziplist1. 压缩列表是redis为了节约内存而开发的特点 1是一系列 特殊编码的 连续内存块 组成的 顺序型数据结构。 2一个压缩列表可以包含任意多个节点。 3每个节点可以是字节数组也可以是整数值。 2. 压缩列表的结构为1zlbytes压缩列表占用的内存字节数 2zitail 记录表尾节点(开始index) 距离压缩列表的起始位置的字节数 3zllen 压缩列表包含的节点数量。 4entryX节点 5zlend特殊值0.用于标示也锁列表的末端。 3. 压缩列表的节点 每个压缩列表的节点都由previous_entry_length encoding content 3部分组成。 1previous_entry_length 含义前一个字节的长度---单位是字节可以是1或者5(字节)。 作用根据当前节点的起始索引和前一个节点的长度就可以计算出上一个节点的起始索引使用这种方法可以实现从表尾向表头进行遍历的过程。 2encoding 含义记录了content属性所保存数据的类型和长度所保存的类型有字节数组或者是整数值。 3content 含义节点的具体值可以是1个字节数组或者是一个整数值值的类型和长度都是由encoding决定的。5linkedlist双向链表的结构为6hashtable1. 每个字典中都有一个长度为2的哈希表数组数组中的2个哈希表的结构一样。 2. 使用2个哈希表的目的是为了实现 渐进式 RehashIncremental Rehashing。这种设计解决了传统哈希表在扩容或缩容时一次性迁移数据导致的性能抖动和服务阻塞问题。 3. 哈希表节点dicEntry结构 1key键值对的键 2value 键值对的value可以是一个指针或者是uint64_t 整数或者是int64_t 整数。 3next 指向另一个哈希表节点的指针 这个指针可以将多个哈希值相同的键值对连接在一次 以此来解决键冲突collision的问题。4. 哈希表结构 1table哈希表数组数组中的每个元素都是一个指向节点的指针。 2size哈希表的大小也就是table数组的大小。 3sizemask 哈希表大小掩码和哈希值一起决定一个键应该放到哈希表数组的哪个索引上面对应的值总是 size-1 4used 哈希表目前已有节点(键值对)的数量。5. 字典结构 字典是在哈希表的基础上进行了优化具体结构为 1 type 一个指向 dictType 结构的指针 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数 Redis 会为用途不同的字典设置不同类型的特定函数。 2privdata: 私有数据保存需要传给 类型特定函数的可选参数。 3) ht[ ]: 长度为2的哈希表数组一般只使用ht[0],只有在对ht[0]哈希表进行rehash的时候才会使用ht[1]。 4) rehashidx : 记录rehash的进度没有rehash时值为 -1。6. 普通状态下的字典示例7. 哈希算法 1根据key使用字典设置的哈希函数计算key对应的哈希值。 2根据哈希表的sizemark和哈希值计算对应的索引值。 3将新的键值对放到指定的索引下。 注意 Redis 使用 MurmurHash2 算法来计算键的哈希值。MurmurHash2 算法最新的版本是MurmurHash3 。 8. 键冲突 1定义 哈希表数组的长度是有限的通过键值对的key可以计算对应的哈希值再通过哈希值和哈希表的sizemark可以计算出哈希表索引的值索引的值难免会重复。哈希表数组的长度是有限的通过键值对的key可以计算对应的哈希值再通过哈希值和哈希表的sizemark可以计算出哈希表索引的值索引的值难免会重复。 当两个或者两个以上的键被分配到了哈希表的同一个索引上时就发生了键冲突。 2解决键冲突 链地址法 每个哈希表节点都有一个next指针当多个key的索引相同时多个节点可以通过next指针连接起来形成一个单向链表越早产生的数据在链表的最后面最新产生的节点在链表的最前端。 9. rehash 1原因 随着对键值对的不断操作哈希表保存的键值对数量会不断增多或者减少。为了让哈希表的负载因子保存在一个合理的范围内当哈希表的键值对的数量太多或者太少时就需要对哈希表进行rehash(重新散列)的操作。 2步骤 1. 判断是需要扩展还是收缩 2. 计算所需要的空间大小 a. 如果是扩展计算出ht[0] 哈希表中第一个大于等于ht[0].used*2 的2的n次方的值。【ht[0].used指的是ht[0]哈希表已有节点的数量比如ht[0].used 是6那么最后计算出的结果是第一个大于等于6*2的2的n次方2的3次方是84次方是1616是第一个大于等于12的2的n次方结果就是16】 b. 如果是收缩计算出ht[0]哈希表中第一个大于等于ht[0].used的2的n次方。 3. 为字典ht[1]分配空间空间的大小就是刚才计算出的空间大小。 4. 将保存在ht[0]上的所有的键值对rehash到ht[1]上面具体操作根据key重新计算哈希值然后根据哈希值和ht[1]的sizemaskht[1]的size-1计算对应的索引值并将键值对放置到对应的索引下。 5. 当把ht[0]上的所有的键值对都rehash到ht[1]上面之后ht[0]就变成了空表这时释放ht[0],并将ht[1]改为ht[0]。 6. 在ht[1]新创建一个空的哈希表为下次rehash做准备。 10. 哈希表扩展的条件 满足下面条件中的任意一个就进行扩展 1服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令 并且哈希表的负载因子大于等于 1。 2服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令 并且哈希表的负载因子大于等于 5 。 注意根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行 服务器执行扩展操作所需的负载因子并不相同 这是因为在执行 BGSAVE 命令或BGREWRITEAOF 命令的过程中 Redis 需要创建当前服务器进程的子进程 而大多数操作系统都采用写时复制copy-on-write技术来优化子进程的使用效率 所以在子进程存在期间 服务器会提高执行扩展操作所需的负载因子 从而尽可能地避免在子进程存在期间进行哈希表扩展操作 这可以避免不必要的内存写入操作 最大限度地节约内存。 11. 哈希表收缩的条件 哈希表的负载因子值小于0.1。 12. 负载因子值的计算也就是说节点数量跟哈希表的大小一样时负载因子是1开始进行扩展操作。 13. 渐进式rehash rehash不是一下子完成的而是一步步慢慢完成的因为当哈希表的key非常多时如果一下子都需要rehash可能会导致服务器停止工作。 渐进式rehash步骤 1判断是扩展还是收缩计算需要的空间大小 2为ht[1]分配空间让字典同时持有并使用ht[0]和ht[1]两个哈希表 3字典中有个属性是rehashidx用来判断是否处于rehash状态当不处于rehash状态时rehashidx的值是-1当开始进行rehash时先将rehashidx的值设置为0 4当对字典执行增删改查操作时先执行对应的操作然后再把ht[0]哈希表上索引为rehashidx的所有的键值对rehash到ht[1]哈希表上 5) 将ht[0]对应索引下的所有的键值对rehash到ht[1]后将rehashidx的值加1 6下次进行增删改查操作时再把ht[0]对应index为rehashixd的索引下的键值对都rehash到ht[1]上 7当ht[0]上所有索引下键值对都被rehash到ht[1]以后将rehashidx的重置为 -1rehash结束。 渐进式rehash执行期间的哈希表操作 1如果是增那么新的键值对直接保存到ht[1]哈希表 2如果是删改查那么会先去ht[0]哈希表查找对应的key是否存在如果存在就直接操作如果不存在就再去ht[1]找。7skiplist1. 跳跃表是一种可以对有序链表进行近似二分查找的数据结构它通过在每个节点中维持多个指向其他节点的指针从而达到快速访问节点的目的。 2. reids在两个地方用到了跳跃表分别是 1实现有序集合 如果一个有序集合包含的元素数量比较多‘或者有序集合中元素的成员是比较长的字符串时redis就会使用跳跃表来作为有序集合键的底层实现。 2在集群节点中用作内部数据结构 3. 跳跃表的实现由zskiplist和zskiplistNode两个结构组成。 1zskiplist 用于保存跳跃表的信息如表头节点表尾节点长度最大层数。 2zskiplistNode保存跳跃表节点如层后退指针分值成员对象 。 4. 每个跳跃表节点的层高都是1到32之间的随机数。 5. 在同一个跳跃表中多个节点可以保存相同的分值但是节点的成员对象是唯一的。 6. 在同一个跳跃表中多个节点可以保存相同的分值但是节点的成员对象是唯一的。 7. 跳跃表的结构为介绍8. 跳跃表节点介绍 1层 节点中使用L1,L2,L3等来标记节点的各个层。每个层有两个属性前进指针和跨度。 前进指针用于访问表尾方向的其他节点。 跨度记录前进指针所指向的节点和当前节点的距离。 2后退指针 节点中使用BW标记节点的后退指针它指向当前节点的前一个节点在程序从表尾向表头遍历时使用。 3分值 节点中的1.02.03.0字样是节点保存的分值节点按照分值从小到大的顺序进行排列。 4成员对象 各个节点中的o1,o2,o3等是节点保存的成员对象。 5跳跃表节点具体结构