元数据
Redis设计与实现
- 书名： Redis设计与实现
- 作者： 黄健宏
- 简介： 《Redis设计与实现》对Redis的大多数单机功能以及所有多机功能的实现原理进行了介绍，展示了这些功能的核心数据结构以及关键的算法思想。通过阅读本书，读者可以快速、有效地了解Redis的内部构造以及运作机制，这些知识可以帮助读者更好、更高效地使用Redis。本书主要分为四大部分。第一部分“数据结构与对象”介绍了Redis中的各种对象及其数据结构，并说明这些数据结构如何影响对象的功能和性能。第二部分“单机数据库的实现”对Redis实现单机数据库的方法进行了介绍，包括数据库、RDB持久化、AOF持久化、事件等。第三部分“多机数据库的实现”对Redis的Sentinel、复制（replication）、集群（cluster）三个多机功能进行了介绍。第四部分“独立功能的实现”对Redis中各个相对独立的功能模块进行了介绍，涉及发布与订阅、事务、Lua脚本、排序、二进制位数组、慢查询日志、监视器等。
- 出版时间： 2015-01-01 00:00:00
- ISBN： 9787111464747
- 分类： 计算机-编程设计
- 出版社： 机械工业出版社
- PC地址：https://weread.qq.com/web/reader/d35323e0597db0d35bd957b
高亮划线
前言
📌 ，共同关注功能本质上就是计算两个用户关注集合的交集 ⏱ 2024-04-30 10:23:32
1.2 章节编排
📌 数据库键总是一个字符串对象（string object）；❑而数据库键的值则可以是字符串对象、列表对象（list object）、哈希对象（hash object）、集合对象（set object）、有序集合对象（sorted set object）这五种对象中的其中一种。 ⏱ 2023-04-30 12:20:09
2.1 SDS的定义
📌 SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数。 ⏱ 2023-04-30 12:28:29
2.2 SDS与C字符串的区别
📌 获取字符串长度的复杂度高之外，C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）。 ⏱ 2023-04-30 12:30:04
📌 与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题。 ⏱ 2023-04-30 12:30:33
📌 通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。 ⏱ 2023-05-01 09:50:03
📌 1.空间预分配空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。 ⏱ 2023-05-01 09:50:17
📌 惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。 ⏱ 2023-05-01 10:03:08
📌 为了确保Redis可以适用于各种不同的使用场景，SDS的API都是二进制安全的（binary-safe），所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。 ⏱ 2023-05-01 10:03:56
3.1 链表和链表节点的实现
📌 list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是用于实现多态链表所需的类型特定函数 ⏱ 2023-05-01 10:05:43
4.1 字典的实现
📌 next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题。 ⏱ 2023-05-01 15:57:59
4.2 哈希算法
📌 这种算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。 ⏱ 2024-04-30 19:08:32
4.3 解决键冲突
📌 Redis的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。 ⏱ 2024-04-30 22:09:15
4.4 rehash
📌 rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。 ⏱ 2024-04-30 22:11:52
4.5 渐进式rehash
📌 扩展或收缩哈希表需要将ht[0]里面的所有键值对rehash到ht[1]里面，但是，这个rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。 ⏱ 2024-04-30 22:44:42
📌 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。 ⏱ 2024-04-30 22:45:23
📌 渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。 ⏱ 2024-04-30 22:45:37
4.7 重点回顾
📌 Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用。 ⏱ 2024-04-30 22:53:42
5.1 跳跃表的实现
📌 跨度实际上是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。 ⏱ 2024-04-30 23:35:40
📌 跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。 ⏱ 2024-04-30 23:36:24
📌 分值相同的节点将按照成员对象在字典序中的大小来进行排序 ⏱ 2024-04-30 23:37:02
6.4 降级
📌 整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。 ⏱ 2024-05-01 04:41:27
7.2 压缩列表节点的构成
📌 压缩列表的从表尾向表头遍历操作就是使用这一原理实现的，只要我们拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的previous_entry_length属性，程序就 ⏱ 2024-05-01 04:46:43
7.3 连锁更新
📌 Redis将这种在特殊情况下产生的连续多次空间扩展操作称之为“连锁更新”（cascade update） ⏱ 2024-05-01 04:52:28
8.1 对象的类型与编码
📌 Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。 ⏱ 2024-05-01 04:54:11
📌 encoding属性记录了对象所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现，这个属性的值可以是表8-3列出的常量的其中一个。表8-3 对象的编码 ⏱ 2024-05-01 04:55:37
8.2 字符串对象
📌 因为Redis没有为embstr编码的字符串对象编写任何相应的修改程序（只有int编码的字符串对象和raw编码的字符串对象有这些程序），所以embstr编码的字符串对象实际上是只读的。当我们对embstr编码的字符串对象执行任何修改命令时，程序会先将对象的编码从embstr转换成raw，然后再执行修改命令。因为这个原因，embstr编码的字符串对象在执行修改命令之后，总会变成一个raw编码的字符串对象。 ⏱ 2024-05-01 05:07:52
8.8 内存回收
📌 因为C语言并不具备自动内存回收功能，所以Redis在自己的对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。 ⏱ 2024-05-03 10:45:25
8.9 对象共享
📌 除了用于实现引用计数内存回收机制之外，对象的引用计数属性还带有对象共享的作用。举个例子，假设键A创建了一个包含整数值100的字符串对象作为值对象，如图8-20所示。 ⏱ 2024-05-03 10:46:14
📌 目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。 ⏱ 2024-05-03 10:46:27
📌 因此，尽管共享更复杂的对象可以节约更多的内存，但受到CPU时间的限制，Redis只对包含整数值的字符串对象进行共享。 ⏱ 2024-05-03 10:49:40
8.10 对象的空转时长
📌 除了前面介绍过的type、encoding、ptr和refcount四个属性之外，redisObject结构包含的最后一个属性为lru属性，该属性记录了对象最后一次被命令程序访问的时间 ⏱ 2024-05-03 11:09:51
9.2 切换数据库
📌 谨慎处理多数据库程序 ⏱ 2024-05-03 11:26:19
9.4 设置键的生存时间或过期时间
📌 redisDb结构的expires字典保存了数据库中所有键的过期时间，我们称这个字典为过期字典 ⏱ 2024-05-03 14:15:55
9.5 过期键删除策略
📌 ❑定时删除：在设置键的过期时间的同时，创建一个定时器（timer），让定时器在键的过期时间来临时，立即执行对键的删除操作。❑惰性删除：放任键过期不管，但是每次从键空间中获取键时，都检查取得的键是否过期，如果过期的话，就删除该键；如果没有过期，就返回该键。❑定期删除：每隔一段时间，程序就对数据库进行一次检查，删除里面的过期键。至于要删除多少过期键，以及要检查多少个数据库，则由算法决定。 ⏱ 2024-05-03 14:29:28
9.6 Redis的过期键删除策略
📌 它在规定的时间内，分多次遍历服务器中的各个数据库，从数据库的expires字典中随机检查一部分键的过期时间，并删除其中的过期键。 ⏱ 2024-05-03 14:39:14
9.7 AOF、RDB和复制功能对过期键的处理
📌 通过由主服务器来控制从服务器统一地删除过期键，可以保证主从服务器数据的一致性，也正是因为这个原因，当一个过期键仍然存在于主服务器的数据库时，这个过期键在从服务器里的复制品也会继续存在。 ⏱ 2024-05-03 14:43:13
读书笔记
2.2 SDS与C字符串的区别
划线评论
📌 2.2.4 二进制安全 ^15826765-7QPXIcvJz - 💭 和前面的支持 c style string api 的特点相悖了吧 - ⏱ 2024-04-30 13:50:15