Redis 设计与实现（第一版）

# Redis 设计与实现（第一版） >[warning] > 你正在阅读的是《Redis 设计与实现》第一版（旧版），请访问 [RedisBook.com](http://RedisBook.com/) ，查看关注 Redis 3.0 、包含更多新内容的新版《Redis 设计与实现》。 本书的目标是以简明易懂的方式讲解 Redis 的内部运行机制，通过阅读本书，你可以了解到 Redis 从数据结构到服务器构造在内的几乎所有知识。 [TOC=2,3] [](#) 为了保证内容的简洁性，本书会尽量以高抽象层次的角度来观察 Redis ，并将代码的细节留给读者自己去考究。 如果读者只是对 Redis 的内部运作机制感兴趣，但并不想深入代码，那么只阅读本书就足够了。 另一方面，对于需要深入研究 Redis 代码的读者，本书附带了一份 [带有详细注释的 Redis 2.6 源代码](https://github.com/huangz1990/annotated_redis_source) ，可以配合本书一并使用。 ## 第一部分：内部数据结构 Redis 和其他很多 key-value 数据库的不同之处在于，Redis 不仅支持简单的字符串键值对，它还提供了一系列数据结构类型值，比如列表、哈希、集合和有序集，并在这些数据结构类型上定义了一套强大的 API 。 通过对不同类型的值进行操作，Redis 可以很轻易地完成其他只支持字符串键值对的 key-value 数据库很难（或者无法）完成的任务。 在 Redis 的内部，数据结构类型值由高效的数据结构和算法进行支持，并且在 Redis 自身的构建当中，也大量用到了这些数据结构。 这一部分将对 Redis 内存所使用的数据结构和算法进行介绍。 - [简单动态字符串](#) - [sds 的用途](#) - [Redis 中的字符串](#) - [优化追加操作](#) - [sds 模块的 API](#) - [小结](#) - [双端链表](#) - [双端链表的应用](#) - [双端链表的实现](#) - [迭代器](#) - [小结](#) - [字典](#) - [字典的应用](#) - [字典的实现](#) - [创建新字典](#) - [添加键值对到字典](#) - [添加新元素到空白字典](#) - [添加新键值对时发生碰撞处理](#) - [添加新键值对时触发了 rehash 操作](#) - [Rehash 执行过程](#) - [渐进式 rehash](#) - [字典的收缩](#) - [字典其他操作](#) - [字典的迭代](#) - [小结](#) - [跳跃表](#) - [跳跃表的实现](#) - [跳跃表的应用](#) - [小结](#) ## 第二部分：内存映射数据结构 虽然内部数据结构非常强大，但是创建一系列完整的数据结构本身也是一件相当耗费内存的工作，当一个对象包含的元素数量并不多，或者元素本身的体积并不大时，使用代价高昂的内部数据结构并不是最好的办法。 为了解决这一问题，Redis 在条件允许的情况下，会使用内存映射数据结构来代替内部数据结构。 内存映射数据结构是一系列经过特殊编码的字节序列，创建它们所消耗的内存通常比作用类似的内部数据结构要少得多，如果使用得当，内存映射数据结构可以为用户节省大量的内存。 不过，因为内存映射数据结构的编码和操作方式要比内部数据结构要复杂得多，所以内存映射数据结构所占用的 CPU 时间会比作用类似的内部数据结构要多。 这一部分将对 Redis 目前正在使用的两种内存映射数据结构进行介绍。 - [整数集合](#) - [整数集合的应用](#) - [数据结构和主要操作](#) - [intset 运行实例](#) - [升级](#) - [关于升级](#) - [关于元素移动](#) - [其他操作](#) - [小结](#) - [压缩列表](#) - [ziplist 的构成](#) - [节点的构成](#) - [创建新 ziplist](#) - [将节点添加到末端](#) - [将节点添加到某个/某些节点的前面](#) - [删除节点](#) - [遍历](#) - [查找元素、根据值定位节点](#) - [小结](#) ## 第三部分：Redis 数据类型 既然 Redis 的键值对可以保存不同类型的值，那么很自然就需要对键值的类型进行检查以及多态处理。 为了让基于类型的操作更加方便地执行，Redis 创建了自己的类型系统。 在这一部分，我们将对 Redis 所使用的对象系统进行了解，并分别观察字符串、哈希表、列表、集合和有序集类型的底层实现。 - [对象处理机制](#) - [redisObject 数据结构，以及 Redis 的数据类型](#) - [命令的类型检查和多态](#) - [对象共享](#) - [引用计数以及对象的销毁](#) - [小结](#) - [字符串](#) - [字符串编码](#) - [编码的选择](#) - [字符串命令的实现](#) - [哈希表](#) - [字典编码的哈希表](#) - [压缩列表编码的哈希表](#) - [编码的选择](#) - [哈希命令的实现](#) - [列表](#) - [编码的选择](#) - [列表命令的实现](#) - [阻塞的条件](#) - [阻塞](#) - [阻塞因 LPUSH 、 RPUSH 、 LINSERT 等添加命令而被取消](#) - [先阻塞先服务（FBFS）策略](#) - [阻塞因超过最大等待时间而被取消](#) - [集合](#) - [编码的选择](#) - [编码的切换](#) - [字典编码的集合](#) - [集合命令的实现](#) - [求交集算法](#) - [求并集算法](#) - [求差集算法](#) - [有序集](#) - [编码的选择](#) - [编码的转换](#) - [ZIPLIST 编码的有序集](#) - [SKIPLIST 编码的有序集](#) ## 第四部分：功能的实现 除了针对单个键值对的操作外，Redis 还提供了一些同时对多个键值对进行处理的功能，比如事务和 Lua 脚本。 另外，一些辅助性的功能，比如慢查询，以及一些和数据库无关的功能，比如订阅与发布，我们也会经常用到。 通过理解这些功能的底层实现，我们可以更有效地使用它们。 这一部分将对这些功能进行介绍。 - [事务](#) - [事务](#) - [开始事务](#) - [命令入队](#) - [执行事务](#) - [在事务和非事务状态下执行命令](#) - [事务状态下的 DISCARD 、 MULTI 和 WATCH 命令](#) - [带 WATCH 的事务](#) - [WATCH 命令的实现](#) - [WATCH 的触发](#) - [事务的 ACID 性质](#) - [小结](#) - [订阅与发布](#) - [频道的订阅与信息发送](#) - [订阅频道](#) - [发送信息到频道](#) - [退订频道](#) - [模式的订阅与信息发送](#) - [订阅模式](#) - [发送信息到模式](#) - [退订模式](#) - [小结](#) - [Lua 脚本](#) - [初始化 Lua 环境](#) - [脚本的安全性](#) - [脚本的执行](#) - [EVAL 命令的实现](#) - [EVALSHA 命令的实现](#) - [小结](#) - [慢查询日志](#) - [相关数据结构](#) - [慢查询日志的记录](#) - [慢查询日志的操作](#) - [小结](#) ## 第五部分：内部运作机制 以下章节将对 Redis 最底层也最隐蔽的模块进行探讨： - Redis 如何表示一个数据库？数据库操作是如何实现的？ - Redis 如何进行持久化？ RDB 模式和 AOF 模式有什么区别？ - Redis 如何处理输入命令？它又是如何将输出返回给客户端的？ - Redis 服务器如何初始化？传入服务器的命令又是以什么方法执行的？ 以上的这些问题，都是这一部分要解答的。 - [数据库](#) - [数据库的结构](#) - [数据库的切换](#) - [数据库键空间](#) - [键空间的操作](#) - [键的过期时间](#) - [过期时间的保存](#) - [设置生存时间](#) - [过期键的判定](#) - [过期键的清除](#) - [过期键的惰性删除策略](#) - [过期键的定期删除策略](#) - [过期键对 AOF 、RDB 和复制的影响](#) - [数据库空间的收缩和扩展](#) - [小结](#) - [RDB](#) - [保存](#) - [SAVE 、 BGSAVE 、 AOF 写入和 BGREWRITEAOF](#) - [载入](#) - [RDB 文件结构](#) - [小结](#) - [AOF](#) - [AOF 命令同步](#) - [命令传播](#) - [缓存追加](#) - [文件写入和保存](#) - [AOF 保存模式](#) - [AOF 保存模式对性能和安全性的影响](#) - [AOF 文件的读取和数据还原](#) - [AOF 重写](#) - [AOF 重写的实现](#) - [AOF 后台重写](#) - [AOF 后台重写的触发条件](#) - [小结](#) - [事件](#) - [文件事件](#) - [时间事件](#) - [时间事件应用实例：服务器常规操作](#) - [事件的执行与调度](#) - [小结](#) - [服务器与客户端](#) - [初始化服务器](#) - [客户端连接到服务器](#) - [命令的请求、处理和结果返回](#) - [命令请求实例： SET 的执行过程](#) - [小结](#) ## 关于 本书由 [huangz](http://huangz.me/) 编写。 我在研究 Redis 源码并创作本书的过程中获得了极大的快乐，希望你在阅读本书时也能有同感。 评论、问题、意见或建议都可以发表在本书自带的 disqus 论坛里，也可以通过 [豆瓣](http://www.douban.com/people/i_m_huangz/) 、 [微博](http://weibo.com/huangz1990) 或 [Twitter](https://twitter.com/huangz1990) 联系我，我会尽可能地回复。 要获得本书的最新动态，请关注 [redisbook](https://github.com/huangz1990/redisbook) 项目。 要了解编写本书时用到的工具（源码管理、文档的生成和托管、图片生成，等等），请阅读 [这篇文章](http://blog.huangz.me/diary/2013/tools-for-writing-redisbook.html) 。 下载本书离线版本： [pdf 格式](https://github.com/huangz1990/redisbook/raw/master/pdf/redisbook.pdf) 或 [html 格式](https://media.readthedocs.org/htmlzip/redisbook/latest/redisbook.zip) 。 ## 通过捐款支持本书 如果你喜欢这本《Redis 设计与实现》的话，可以通过捐款的方式，支持作者继续更新本书：比如为本书修补漏洞、添加更多有趣的章节，或者发行有更多更棒内容的下一版，等等。 你可以通过使用[支付宝钱包](https://mobile.alipay.com/main/download.htm?action=mobileClient) 扫描以下二维码来进行捐款，或者通过向支付宝帐号 [huangz1990@gmail.com](#) 转帐来进行捐款。