《Redis设计与实现》
《Redis设计与实现》
作者 黄健宏
1.1 Redis版本说明
第 2 章【简单动态字符串】、第4-5章【字典、跳表】、第 10 章【RDB持久化】、第 11 章【AOF持久化】、第15章 【复制】、第17章 【集群】
本书是基于Redis 2.9——也即是Redis 3.0的开发版来编写的，因为Redis 3.0的更新主要与Redis的多机功能有关，而Redis 3.0的单机功能则与Redis 2.6、Redis 2.8的单机功能基本相同，所以本书的内容对于使用Redis 2.6至Redis 3.0的读者来说应该都是有用的。 另外，因为Redis通常都是渐进地增加新功能，并且很少会大幅地修改已有的功能，所以本书的大部分内容对于Redis 3.0之后的几个版本来说，应该也是有用的。
4.1 字典的实现
redis中自己实现的dict结构如下：
图4-3展示了一个普通状态下（没有进行rehash）的字典。
4.2 哈希算法
Redis将一个新的键值对添加到字典里面时，需要： 1. 根据dict设置的哈希函数，计算key的hash值：hash = dict->type->hashFunction(key); 2. 使用哈希表的sizemask和哈希值，计算出索引： index = hash & dict->ht[x].sizemask；
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
4.3 解决键冲突
Redis的哈希表dictht使用链地址法解决键冲突； 为了效率考虑，哈希表总是将新节点添加到冲突key对应value的列表头部’； ——问题：采用链地址法前提下，如何根据指定key获取对应hashValue？
因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O（1）），排在其他已有节点的前面。
4.4 rehash
如何将每个dictEntry从ht[0] rehash到 ht[1]？ 1. dict->type->hashFunction：每个dict的两张hashTable使用同一个哈希函数； 2. ht[x]->sizemask : 每张hashTable都不一样
将ht[0]包含的四个键值对都rehash到ht[1]
什么情况下哈希表的负载因子 >= 1? 哈希表的负载因子 = ht[0].used / ht[0].size ——当哈希表存在键hash值冲突时？
当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：1）服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。2）服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
何为BGSAVE？ 何为BGREWRITEAOF？
这是因为在执行BGSAVE命令或BGREWRITEAOF命令的过程中
4.5 渐进式rehash
渐进式rehash： 1. 利用rehashidx顺序地将ht[0]中的键值对 reshah到 ht[1]中； 2. 将每个rehash均摊到对字典的每个增删改查中；
渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。
第5章 跳跃表
Redis中跳跃表的应用： 1. 有序集合键的底层实现； 2. 集群节点中用作内部数据结构；
Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在Redis里面没有其他用途。
5.1 跳跃表的实现
跳跃表节点组成： 1. level数组。数组元素包含一个前进指针和跨度。一般来说，层数越多，访问其他节点的速度越快； 1.1 前进指针。每个层都有一个指向表尾方向的前进指针—level[i].forward； 1.2 跨度。层的跨度（level[i].span）用于记录两个节点之间的距离； 2. 后退指针。每个节点只有一个后退指针，且每次只能后退至前一个节点； 3. 节点的score（double）和成员（字符串对象）；
跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。
为什么不是从表头L1的前进指针移动到第二个节点？
然后从第四层的前进指针移动到表中的第二个节点。
如图5-3，第二个节点L4前进指针指向第4各节点的L4，那么跳跃表是如何判断需要从L2的前进指针移动到第三个节点？ 1. 根据L4的跨度 > 1，判断当前L4的前进指针指向的节点并非后面一个节点； 2. 依次遍历L3、L2直到找到一层的前进指针跨度 == 1；
在第二个节点时，程序沿着第二层的前进指针移动到表中的第三个节点。
如果某一个节点上，层数比较多，但是只有L4层以下指向后续节点，而从上一个节点的前进指针刚好移动到当前节点的L5，此时判断L5的前进指针 == NULL，会不会导致提前结束遍历？ ——除非中间的每个节点上所有的层都保证指向后续节点；
当程序再次沿着第四个节点的前进指针移动时，它碰到一个NULL，程序知道这时已经到达了跳跃表的表尾，于是结束这次遍历。
7.2 压缩列表节点的构成
这里指向当前节点的起始地址 == 当前节点previous_entry_length的起始地址
举个例子，如果我们有一个指向当前节点起始地址的指针c，那么我们只要用指针c减去当前节点previous_entry_length属性的值，就可以得出一个指向前一个节点起始地址的指针p，如图7-7所示。
压缩列表可以从表尾向表头遍历操作的原理： ——每个压缩列表节点由三部分组成：previous_entry_length、encoding、content； ——其中，previouse_entry_length记录了前一个节点的长度； ——故pc - pc.previous_entry_length == 前一个节点的指针
压缩列表的从表尾向表头遍历操作就是使用这一原理实现的，只要我们拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的previous_entry_length属性，程序就
第8章 对象
Redis基于动态字符串(SDS)、双端链表、字典、压缩列表、整数集合创建了一个对象系统： 1. 该系统共包含字符串对象、列表对象、哈希对象、集合对象和有序集合这5种类型对象； 2. Redis可根据对象类型来判断是否可执行命令； 3. Redis对象系统实现了基于引用计数的内存回收机制，另外通过引用计数计数实现了对象共享机制；
Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。
8.1 对象的类型与编码
Redis中键的作用： 1. Redis使用对象来表示数据库中的键和值，每次在redis的数据库中新创建一个键值对时 == 创建一个key对象 + 一个值对象； 2. 通常，称呼一个数据库键为“列表键”时，是指这个数据库键所对应的值为列表对象；
举个例子，假设键A创建了一个包含整数值100的字符串对象作为值对象，如图8-20所示。
Redis数据库中的key和value： 1. Redis数据库中的key和value首先都是一个对象； 2. Redis中每个对象都由一个redisObject结构表示： 2.1 unsigned type:4——类型； 2.2 unsigned encoding:4——编码； 2.3 void ptr——指向底层数据结构的指针；*
Redis中的每个对象都由一个redisObject结构表示，该结构中和保存数据有关的三个属性分别是type属性、encoding属性和ptr属性：
8.2 字符串对象
如果字符串对象保存的是一个字符串值： 1. 如果字符串值长度 > 32 字节，则redisObject.ptr指向一个简单动态字符串（SDS）来保存这个字符串值，对象编码为raw； 1.1 raw编码会调用两次内存分配函数来分别创建redisObject和sdshdr结构； 2. 若字符串值长度 <= 32字节，则会使用embstr编码方式保存该字符串值； 2.1 embstr编码则通过一次内存分配一块连续内存空间，空间中一次包含redisObject和sdshdr结构；
embstr编码的字符串对象在执行命令时，产生的效果和raw编码的字符串对象执行命令时产生的效果是相同的，但使用embstr编码的字符串对象来保存短字符串值有以下好处：
8.3 列表对象
redis五种类型对象： 1. 字符串对象可以被列表、哈希、集合和有序集合对象嵌套包含；
注意，linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象，这种嵌套字符串对象的行为在稍后介绍的哈希对象、集合对象和有序集合对象中都会出现，字符串对象是Redis五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。
8.4 哈希对象
redis哈希对象： 1. 哈希对象可以使用ziplist编码，对应底层使用压缩列表存储键值对； 1.1 当哈希对象使用ziplist编码时，要求： 1.1.1 哈希对象所保存的所有键值对的key和value对应字符串长度 < 64字节； 1.1.2 哈希对象保存的键值对个数 小于 512个； 1.2 否则，哈希对象原本保存在压缩列表里的所有键值对都会被转移并保存到字典里面；编码转变为hashtable； 2. 哈希对象也可以使用hashtable编码，对应底层使用字典存储键值对；
对于使用ziplist编码的列表对象来说，当使用ziplist编码所需的两个条件的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有键值对都会被转移并保存到字典里面，对象的编码也会从ziplist变为hashtable。
8.5 集合对象
Redis集合对象： 1. 集合对象使用intset编码时，底层使用整数集合存储所有元素； 1.1 集合对象所保存的所有元素都是整数值； 1.2 集合对象保存的元素数量不超过512个； 1.3 否则集合对象需要使用hashtable编码； 2. 集合对象使用hashtable编码时，底层使用字典存储，字典的每个键使用字符串对象包含一个集合元素，而字典的值全部设为NULL；
对于使用intset编码的集合对象来说，当使用intset编码所需的两个条件的任意一个不能被满足时，就会执行对象的编码转换操作，原本保存在整数集合中的所有元素都会被转移并保存到字典里面，并且对象的编码也会从intset变为hashtable。
8.6 有序集合对象
Redis有序集合： 1. 有序集合的编码可以是ziplist，底层使用压缩列表存储集合元素： 1.1 每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个保存元素的成员，第二个节点保存元素的分值； 2. 有序集合可以使用skiplist编码，底层使用zset结构： 2.1 zset结构同时包含一个字典和一个跳跃表； 2.2 zset结构中的跳跃表按分值从小到大保存了所有集合元素： 跳跃表节点object属性（元素成员）+score属性保存了元素分值； 2.3 zset结构中的dict为有序集合创建了一个从成员->分值的映射；
skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表：
8.7 类型检查与命令多态
如何确认操作的是列表键？ ——字符串、列表、哈希表、集合、有序集合分别对应不同的创建指令，通过指令即可确认redisObject.type
借用面向对象方面的术语来说，我们可以认为LLEN命令是多态（polymorphism）的，只要执行LLEN命令的是列表键，那么无论值对象使用的是ziplist编码还是linkedlist编码，命令都可以正常执行。
Redis操作键的指令： 1. 针对任何类型的键执行，如DEL、EXPIRE、TYPE等——基于类型的多态； 2. 根据值对象类型和编码方式执行，如LLEN等——基于编码的多态；
DEL、EXPIRE等命令和LLEN等命令的区别在于，前者是基于类型的多态——一个命令可以同时用于处理多种不同类型的键，而后者是基于编码的多态——一个命令可以同时用于处理多种不同编码。
8.9 对象共享
Redis对象特性： 1. redisObject通过refcount属性实现内部对象共享和内存回收机制； 2. Redis会在初始化服务器时，创建一万个字符串对象（从0-9999），用于对象共享； 3. 使用OBJECT REFCOUNT 键指令查看当前键对象的引用计数； 4. 考虑到识别共享对象的时间复杂度，Redis只对包含整数值的字符串对象进行共享；
目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。
目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。
8.10 对象的空转时长
RedisObject属性： 1. type——根据创建对象的指令，识别对象的类型； 2. encoding——动态跟踪对象的元素内容和元素个数，并适时记录对象的底层实现； 3. ptr——指向对象的底层内容； 4. refcount——记录对象的引用个数，用来做内存回收； 5. lru（unsigned:22）——记录对象最后一次被命令程序访问的时间；结合maxmemory设置做内存回收（最近最少未使用）
除了前面介绍过的type、encoding、ptr和refcount四个属性之外，redisObject结构包含的最后一个属性为lru属性，该属性记录了对象最后一次被命令程序访问的时间：
9.2 切换数据库
redis数据库1： 1. 服务器状态：redisServer.db——指向数据库指针（类型redisDb），redisServer.dbnum(默认为16)——数据库数量（由服务器配置的database选项决定）； 2. 客户端状态：redisClient.db——记录客户端当前正在使用的数据库；
redisClient.db指针指向redisServer.db数组的其中一个元素，而被指向的元素就是客户端的目标数据库。比如说，如果某个客户端的目标数据库为1号数据库，那么这个客户端所对应的客户端状态和服务器状态之间的关系如图9-2所示。
9.3 数据库键空间
键空间： 1. Redis是一个键值对数据库服务器，每个数据库都对应一个redisDb结构； 2. redisDb结构的dict字典保存了数据库中的所有键值对，该字典称为 key space；
Redis是一个键值对（key-value pair）数据库服务器，服务器中的每个数据库都由一个redis.h/redisDb结构表示，其中，redisDb结构的dict字典保存了数据库中的所有键值对，我们将这个字典称为键空间（key space）：
标记键为脏（dirty）： 1. 若客户端使用watch命令监视了某个键，则服务器后续对键的修改，都会将键标记为脏(dirty)； 2. 服务器对键每修改一次，都会对脏键计数器值增1，该计数器会触发服务器的持久化和复制操作；
如果有客户端使用WATCH命令监视了某个键，那么服务器在对被监视的键进行修改之后，会将这个键标记为脏（dirty），从而让事务程序注意到这个键已经被修改过，第19章会详细说明这一点。❑服务器每次修改一个键之后，都会对脏（dirty）键计数器的值增1，这个计数器会触发服务器的持久化以及复制操作，第10章、第11章和第15章都会说到这一点。
9.4 设置键的生存时间或过期时间
- 键的生存时间：设置键的一个相对当前时间的生命周期； cmd: EXPIRE <key> <ttl>;ttl单位为秒 cmd: PEXPIRE <key> <ttl>;ttl单位为毫秒 2. 键的过期时间：设置键的生命周期的一个绝对终止时间； cmd: EXPIREAT <key> <timestamp>；时间单位为秒 cmd: PEXPIREAT <key> <timestamp>；时间单位为毫秒
虽然有多种不同单位和不同形式的设置命令，但实际上EXPIRE、PEXPIRE、EXPIREAT三个命令都是使用PEXPIREAT命令来实现的：无论客户端执行的是以上四个命令中的哪一个，经过转换之后，最终的执行效果都和执行PEXPIREAT命令一样。
过期字典： 1. redisDb中使用属性expires保存着键的过期时间：dict expires； 2. redisDb..dict则指向键值对； 3. 可以使用EXPIRE和PEXPIRE设置键对象的生存时间； 4. 可以使用EXPIREAT和PEXPIREAT指令设置键对象的过期时间；*
图9-12展示了一个带有过期字典的数据库例子，在这个例子中，键空间保存了数据库中的所有键值对，而过期字典则保存了数据库键的过期时间。
9.6 Redis的过期键删除策略
Redis过期键的定期删除策略： 1. 由redis.c/activeExpireCycle函数实现； 2. 删除策略过程大致如下： 2.1 在规定的时间内，每一轮分多次遍历服务器中的各个数据库： 2.1.1 设置默认每次检查的redisDb数量，每一轮遍历的数据库个数 = min(set_redisDb_num，server.dbnum); 2.1.2 使用current_db记录上一轮遍历的数据库索引，因此下一轮activeExpireCycle()会接着上一轮的进度处理； 2.2 每一轮遍历redisDb时，从数据库的expires字典中随机抽查一部分键的过期时间，并删除其中的过期键； 2.1.1
过期键的定期删除策略由redis.c/activeExpireCycle函数实现，每当Redis的服务器周期性操作redis.c/serverCron函数执行时，activeExpireCycle函数就会被调用，它在规定的时间内，分多次遍历服务器中的各个数据库，从数据库的expires字典中随机检查一部分键的过期时间，并删除其中的过期键。整个过程可以用伪代码描述如下：
9.7 AOF、RDB和复制功能对过期键的处理
创建RDB文件： CMD：执行SAVE或者BGSAVE； 效果：程序会创建一个新的RDB文件，并对数据库中的键进行检查，已过期的键不会被保存到RDB文件中；
在执行SAVE命令或者BGSAVE命令创建一个新的RDB文件时，程序会对数据库中的键进行检查，已过期的键不会被保存到新创建的RDB文件中。
AOF处理过期键： 1. 当服务器以AOF持久化模式运行时，如果过期键被删除，则程序会向AOF文件追加（append）一条DEL命令，来显式记录该键已被删除；
当过期键被惰性删除或者定期删除之后，程序会向AOF文件追加（append）一条DEL命令，来显式地记录该键已被删除。
当服务器运行在复制模式下时： 1. 从服务器不会主动删除过期键； 2. 主服务器在删除一个过期键后，会显式地向所有从服务器发送一个DEL指令，这样保证了主从服务器数据地一致性；
通过由主服务器来控制从服务器统一地删除过期键，可以保证主从服务器数据的一致性，也正是因为这个原因，当一个过期键仍然存在于主服务器的数据库时，这个过期键在从服务器里的复制品也会继续存在。
9.8 数据库通知
数据库通知： 1. 键空间通知：某个键执行了什么命令； 2. 键事件通知：某个命令被什么键执行了； 3. 服务器可以通过配置notify-keyspace-events选项来决定服务器发送通知的类型： 3.1 所有类型的键空间通知和键事件通知：AKE； 3.2 所有类型的键空间通知：AK； 3.3 所有类型的键事件通知：AE；
服务器配置的notify-keyspace-events选项决定了服务器所发送通知的类型：
使用 小悦记 导出 | 2022年6月10日
