REDIS5设计与源码分析

全书主要分为三部分介绍Redis。第壹部分介绍Redis5中使用的数据结构，包括动态字符串、跳跃表、压缩列表、字典、整数集合和快速链表，详细介绍其基本结构及常见操作。第二部分为本书核心篇章，首先介绍了Redis5的启动流程，命令解析流程，之后对Redis5中的命令实现进行了全面的介绍，包括键命令、字符串命令、哈希表命令、列表命令、集合及有序集合命令、地理位置相关的GEO命令、统计相关的HyperLogLog命令。第三部分，主要介绍了Redis5的一些特性及使用，包括事务、持久化、主从复制以及集群等。

，好未来学而思网校增长研发负责人，清华与北京邮电大学硕士，曾在百度、腾讯和滴滴等公司工作，12年后端架构经验。著有《PHP7底层设计与源码实现》。

本书赞誉序前言章  引言11.1  Redis简介11.2  Redis 5.0的新特性21.3  Redis源码概述31.4  Redis安装与调试41.5  本章小结6第2章  简单动态字符串72.1  数据结构72.2  基本操作112.2.1  创建字符串112.2.2  释放字符串122.2.3  拼接字符串122.2.4  其余API152.3  本章小结15第3章  跳跃表173.1  简介173.2  跳跃表节点与结构193.2.1  跳跃表节点193.2.2  跳跃表结构203.3  基本操作203.3.1  创建跳跃表213.3.2  插入节点223.3.3  删除节点283.3.4  删除跳跃表303.4  跳跃表的应用313.5  本章小结32第4章  压缩列表334.1  压缩列表的存储结构334.2  结构体354.3  基本操作374.3.1  创建压缩列表374.3.2  插入元素384.3.3  删除元素424.3.4  遍历压缩列表444.4  连锁更新444.5  本章小结45第5章  字典475.1  基本概念475.1.1  数组485.1.2  Hash函数495.1.3  Hash冲突515.2  Redis字典的实现525.3  基本操作555.3.1  字典初始化555.3.2  添加元素565.3.3  查找元素605.3.4  修改元素615.3.5  删除元素615.4  字典的遍历625.4.1  迭代器遍历625.4.2  间断遍历655.5  API列表705.6  本章小结71第6章  整数集合726.1  数据存储726.2  基本操作756.2.1  查询元素756.2.2  添加元素786.2.3  删除元素826.2.4  常用API836.3  本章小结85第7章  quicklist的实现867.1  quicklist简介867.2  数据存储877.3  数据压缩917.3.1  压缩927.3.2  解压缩937.4  基本操作947.4.1  初始化947.4.2  添加元素957.4.3  删除元素967.4.4  更改元素987.4.5  查找元素997.4.6  常用API1007.5  本章小结101第8章  Stream1028.1  Stream简介1028.1.1  Stream底层结构listpack1038.1.2  Stream底层结构Rax简介1048.1.3  Stream结构1088.2  Stream底层结构listpack的实现1128.2.1  初始化1128.2.2  增删改操作1128.2.3  遍历操作1138.2.4  读取元素1138.3  Stream底层结构Rax的实现1148.3.1  初始化1148.3.2  查找元素1148.3.3  添加元素1168.3.4  删除元素1188.3.5  遍历元素1208.4  Stream结构的实现1238.4.1  初始化1248.4.2  添加元素1248.4.3  删除元素1258.4.4  查找元素1288.4.5  遍历1298.5  本章小结131第9章  命令处理生命周期1329.1  基本知识1329.1.1  对象结构体robj1329.1.2  客户端结构体client1369.1.3  服务端结构体redisServer1389.1.4  命令结构体redisCommand1399.1.5  事件处理1419.2  server启动过程1499.2.1  server初始化1499.2.2  启动监听1529.3  命令处理过程1559.3.1  命令解析1569.3.2  命令调用1599.3.3  返回结果1619.4  本章小结1630章  键相关命令的实现16410.1  对象结构体和数据库结构体回顾16410.1.1  对象结构体redisObject16410.1.2  数据库结构体redisDb16610.2  查看键信息16610.2.1  查看键属性16610.2.2  查看键类型16910.2.3  查看键过期时间17010.3  设置键信息17110.3.1  设置键过期时间17110.3.2  删除键过期时间17210.3.3  重命名键17310.3.4  修改键最后访问17310.4  查找键17410.4.1  判断键是否存在17410.4.2  查找符合模式的键17510.4.3  遍历键17610.4.4  随机取键17710.5  操作键17810.5.1  删除键17810.5.2  序列化／反序列化键18210.5.3  移动键18310.5.4  键排序18510.6  本章小结1871章  字符串相关命令的实现18811.1  相关命令介绍18811.2  设置字符串18911.2.1  set命令18911.2.2  mset命令19511.3  修改字符串19611.3.1  append命令19611.3.2  setrange命令19711.3.3  计数器命令19711.4  字符串获取19911.4.1  get命令19911.4.2  getset命令19911.4.3  getrange命令19911.4.4  strlen命令20011.4.5  mget命令20111.5  字符串位操作20111.5.1  setbit命令20111.5.2  getbit命令20311.5.3  bitpos命令20311.5.4  bitcount命令20511.5.5  bitop命令20811.5.6  bitfield命令20911.6  本章小结2122章  散列表相关命令的实现21312.1  简介21312.1.1  底层存储21312.1.2  底层存储转换21512.1.3  接口说明21512.2  设置命令21612.3  读取命令21712.3.1  hexists命令21812.3.2  hget/hmget命令21812.3.3  hkeys/hvals/hgetall命令21912.3.4  hlen命令22012.3.5  hscan命令22012.4  删除命令22112.5  自增命令22212.6  本章小结2243章  列表相关命令的实现22513.1  相关命令介绍22513.1.1  命令列表22513.1.2  栈和队列命令列表22613.2  push/pop相关命令22813.2.1  push类命令的实现22813.2.2  pop类命令的实现22913.2.3  阻塞push/pop类命令的实现23013.3  获取列表数据23413.3.1  获取单个元素23413.3.2  获取多个元素23513.3.3  获取列表长度23613.4  操作列表23613.4.1  设置元素23713.4.2  插入元素23713.4.3  删除元素23813.4.4  裁剪列表23913.5  本章小结2404章  集合相关命令的实现24114.1  相关命令介绍24114.2  集合运算25414.2.1  交集25414.2.2  并集25814.2.3  差集26014.3  本章小结2635章  有序集合相关命令的实现26415.1  相关命令介绍26415.2  基本操作27215.2.1  添加成员27215.2.2  删除成员27515.2.3  基数统计27615.2.4  数量计算27715.2.5  计数器27915.2.6  获取排名27915.2.7  获取分值27915.2.8  遍历28015.3  批量操作28015.3.1  范围查找28015.3.2  范围删除28315.4  集合运算28415.5  本章小结2846章  GEO相关命令28516.1  基础知识28516.2  命令实现28816.2.1  使用geoadd添加坐标28816.2.2  计算坐标的geohash29116.2.3  使用geopos查询位置经纬度29216.2.4  使用geodist计算两点距离29516.2.5  使用georadius/georadius-bymembe查询范围内元素29516.3  本章小结2977章  HyperLogLog相关命令的实现29817.1  基本原理29817.1.1  算法演进29917.1.2  线性计数算法29917.1.3  对数计数算法30017.1.4  自适应计数算法30217.1.5  超对数计数算法30217.2  HLL Redis实现30217.2.1  HLL头对象30317.2.2  稀疏编码30417.2.3  密集编码30617.2.4  内部编码30817.2.5  编码转换30917.3  命令实现31017.3.1  添加基数31017.3.2  近似基数31117.3.3  合并基数31317.4  本章小结3148章  数据流相关命令的实现31518.1  相关命令介绍31518.2  基本操作命令原理分析32318.2.1  添加消息32318.2.2  删除消息32518.2.3  范围查找32618.2.4  获取队列信息32718.2.5  长度统计32718.2.6  剪切消息32818.3  分组命令原理分析32818.3.1  分组管理32818.3.2  消费消息33018.3.3  响应消息33118.3.4  获取未响应消息列表33118.3.5  修改指定未响应消息归属33118.4  本章小结3329章  其他命令33319.1  事务33319.1.1  事务简介33319.1.2  事务命令实现33419.2  发布-订阅命令实现33919.3  Lua脚本34519.3.1  初始化Lua环境34519.3.2  在Lua中调用Redis命令34719.3.3  Redis和Lua数据类型转换34919.3.4  命令实现35119.4  本章小结356第20章  持久化35720.1  RDB35820.1.1  RDB执行流程35820.1.2  RDB文件结构35920.2  AOF36720.2.1  AOF执行流程36820.2.2  AOF重写36920.3  RDB与AOF相关配置指令37220.4  本章小结374第21章  主从复制37521.1  主从复制功能实现37521.2  主从复制源码基础37821.3  slaver源码分析38221.4  master源码分析38821.5  本章小结391第22章  哨兵和集群39222.1  哨兵39222.1.1  哨兵简介39322.1.2  代码流程39422.1.3  主从切换39622.1.4  常用命令39922.2  集群40022.2.1  集群简介40122.2.2  代码流程40222.2.3  主从切换40422.2.4  副本漂移40622.2.5  分片迁移40722.2.6  通信数据包类型40922.3  本章小结415

为什么要写这本书2年前，我们团队建立了学习圈，团队成员可以自愿参加，每天8∶50～10∶30到公司充电100分钟，深入剖析工作中的技术栈，同时2017～2018年编写出版了《PHP 7底层设计与源码实现》一书，接着我们又深入研读了Redis的源码。2018年年初开始，我们开始了Redis源码一书的编写，起初是研读Redis 4.0版本的源码，2018年下半年5.0版本发布，增加了很多的新特性，下半年我们又在之前的基础上结合Redis 5的源码，编写了此书。Redis是一款高性能的开源key-value型数据库，难能可贵的是代码写得非常优雅，非常适合刚入门C语言的读者阅读。本书前半部分详细介绍了Redis中的各种数据结构，适合读者学习和掌握基本的数据结构；后半部分介绍了Redis命令执行的生命周期，以及各类命令的源码实现，希望使用Redis的读者不止会使用Redis，并且能掌握它的原理和细节，提升对Redis的掌控能力。决定编写Redis源码一书后，学习圈里方波、黄桃、李乐、施洪宝、熊浩含、闫昌、张仕华、周生政和我一起编写了这本书。大家在工作之外，每天写到深夜，周末一起探讨，经过一年的编写和校对，终于完成了这本书。希望能给使用Redis的读者一些启发，帮助更多的人理解Redis的实现。读者对象使用Redis的工程师、架构师对Redis源码感兴趣的读者有一定C语言基础的读者如何阅读本书本书内容逻辑上分为三篇，共计22章内容。篇：章简单介绍了Redis，以及Redis的编译安装和研读的方式；第2～8章重点讲解了SDS、跳跃表、压缩列表、字典、整数集合、quicklist和Stream数据结构的实现。第二篇：第9章讲解了Redis的生命周期，命令执行的过程，需要重点阅读；0～19章，分别讲解了键、字符串、散列表、链表、集合、有序集合、GEO、HyperLog和数据流相关命令的实现。第三篇：第20～22章简单讲解了持久化、主从复制和集群的实现，没有详细展开，希望能带读者入门。如果读者是有一定经验的资深开发人员，本书可能会是一本不错的案头书。当然，如果读者是一名初学者，请在开始本书阅读之前，建议先掌握一些C语言和网络编程等基础理论知识。勘误和支持由于笔者的水平有限，编写时间仓促，书中难免会出现一些错误或者不准确的地方，恳请读者批评指正。如果您有更多的宝贵意见，欢迎访问https://segmentfault.com/u/php7internal进行专题讨论，我们会尽量在线上为读者提供解答。同时，您也可以通过微博@PHP7内核，或者邮箱cltf@163.com联系到我们，期待能够得到您的反馈，在技术之路上互勉共进。致谢感谢张国辉、卢红波两位工作导师的支持，前者是我现在的领导，也是我在技术和管理方面的导师，后者是我在滴滴的领导，在技术和管理上给了我很多的指引与帮助。感谢黑夜路人（谢华亮）兄弟的指导和支持，在技术上给了非常多的指点。感谢黄健宏、黄鹏程、付磊、钱文品、张晋涛和吴建超兄弟的指导与建议，他们都是在Redis方面有很深研究的人。感谢方波、黄桃、李乐、施洪宝、熊浩含、闫昌、张仕华和周生政8位兄弟在学习和研究过程中的陪伴与合作，本书是几位兄弟共同合作的结晶。特别是黄桃，已经跟我一起编写了两本书。特别致谢最后，我要特别感谢我的太太梦云、儿子和女儿，我为写作这本书，牺牲了很多陪伴她们的时间，但也正因为有了她们的付出与支持，我才能坚持写下去。同时，感谢我的父母、岳父岳母，不遗余力地帮助我们照顾儿女，有了你们的帮助和支持，我才有时间和精力去完成写作工作。另外要特别感谢我团队的兄弟们，感谢大家的坚持，为大家的成长点赞！重点感谢一下兄弟们背后的太太团，是她们的大力支持，作者们才有时间来编写本书。最后要重点感谢高婧雅编辑，这是第二次跟她合作，她依然非常负责；她耐心审稿，给出很多宝贵建议，才有了这本书的完成。谨以此书献给我最亲爱的家人和团队的兄弟们，以及众多热爱Redis的朋友们！陈  雷序在开源界，高性能服务的典型代表就是Nginx和Redis。纵观这两个软件的源码，都是非常简洁高效的，也都是基于异步网络I/O机制的，所以对于要学习高性能服务的程序员或者爱好者来说，研究这两个网络服务的源码是非常有必要的。Nginx目前市面上的书籍很多，但是Redis确实寥寥无几。这几年Redis版本发展非常快，从稳定的2.x版本，发展到增加了很多优秀特性的5.0版本，这些特性目前尚无资料进行系统讲解。本书的出版填补了Redis 5.0技术学习方面的重大空缺，是技术同仁深入理解Redis内核实现机制的有效途径。Redis是一个优秀的高性能分布式缓存服务器：在实际应用场景中，每秒QPS 能够达到4.5万～5万，算得上性能“怪兽”；在常规非协程的场景中，Redis基本是C10K高性能服务的经典代表。除性能优势外，Redis的整体代码结构也非常清晰，包括基础数据结构、数据类型实现、数据库实现、服务端实现、集群/主从/队列等，基本模块分布清晰，代码质量非常高：static int aeApiCreate(aeEventLoop *eventLoop) { aeApiState *state = zmalloc(sizeof(aeApiState)); if (!state) return -1; state->events = zmalloc(sizeof(struct epoll_event)*eventLoop->setsize); if (!state->events) { zfree(state); return -1; } state->epfd = epoll_create(1024); /* 1024 is just a hint for the kernel */ if (state->epfd == -1) { zfree(state->events); zfree(state); return -1; } eventLoop->apidata = state; return 0;}上面是创建epoll队列的简单代码，简单明了，完全符合《Unix编程艺术》提到的各种关于简单明确的要求，代码赏心悦目，不花里胡哨。除了代码结构之外，Redis的各种类型数据结构也设计良好：简单稳定不容易溢出的字符串结构（sds），快速排序查找的跳跃表（skiplist），节约内存的压缩列表（ziplist），基于Hash表实现的字典（dict），基于链表（list）和压缩列表（ziplist）实现的快速列表（qucklist），基于listpac和基数树（Rax）实现的消息队列（Stream）等，涵盖多种优质数据结构的实现。另外不得不提的是，各类算法在 Redis 里也都得到了呈现，比如 Hash常用算法 times33、物理位置查找算法geohash、高效率的统计算法 HyperLogLog，等等。读完Redis 5.0.0的9.2万行源码，大概比上一学期的数据结构课更有价值。Redis可谓数据结构和常规算法的饕餮盛宴。深入研究Redis 5，相信对技术的理解会更深入。优质的菜品需要有技艺精湛的厨师来烹饪，本书就像以优质菜品做成的“大菜”。整本书没有太多啰唆的语言，直接抽丝剥茧：从基本的数据结构类型，Redis内部每个操作命令的底层代码运行逻辑和结构，一直到整个 Redis 持久化技术、主从技术、分布式集群技术等，都有深入源码级别的讲解，让你领略从数据结构到整个高性能服务的全部设计之美。学以致用，读者朋友通过领会与实践来提升技术，成为一个高性能网络服务开发高手，继而深入理解缓存服务，设计自己的高性能缓存服务系统或者缓存数据库系统，应用到自己业务中去，岂非快哉！在整本书里，我也看到了一群程序员的认真执着，把每个业务数据流程图、关键代码、数据结构图都规划得详细、清晰，把自己对技术的各种理解融入书中。本书脉络清晰，适合刚入行的后端程序员、高性能服务开发者、系统运维人员、技术架构师等阅读。希望阅读本书的技术同仁都能够得到进步和提高。谢华亮（黑夜路人）2019年4月