通过本文，你将了解到：Redis的作者、发展演变、在世界上的地位优势、字典的实现原理、跳表和有序集合的原理、RedisReminder的线程模式和服务模式：内容不难，怕你看不懂。不懂的可以先收藏起来，等到深入研究的时候再去了解。你会发现真的是24K的干货！停止吹牛，写一些不同的东西！一、Redis历史Redis是一个用ANSIC编写的程序一个开源的、支持网络的、基于内存的、具有可选持久性的高性能键值对数据库。Redis之父是来自意大利西西里岛的SalvatoreSanfilippo，Github的名字是antirez。笔者找了一些笔者的简要资料翻译了一下，如图：Redis自2009年第一版以来，已经走过了10个年头，Redis仍然是最流行的key-value内存数据库之一.优秀的开源项目离不开大公司的支持。2013年5月之前，其开发由VMware赞助，2013年5月至2015年6月，其开发由BWT赞助。从2015年6月开始，Redis的开发由RedisLabs赞助。笔者也用过一些其他的NoSQL，有些支持的值类型非常单一，所以很多操作都要在客户端实现。例如，value是一种结构化数据。如果需要修改某个字段，需要将其读出，整体修改。整体写起来比较繁琐，但是Redis的值支持多种类型，很多操作都可以在服务端完成，对于客户端来说非常方便。当然，由于Redis是内存数据库，数据存储容量有限，分布式集群的成本会很高。所以很多公司都开发了类SSD的Redis系统，比如360开发的SSDB和Pika数据库，但是笔者认为0到1的难度要大于1到2的难度。毫无疑问，Redis是NoSQL中的一大亮点，值得我们深入研究和使用。二、Redis在江湖中的地位Redis提供了Java、C/C++、C#、PHP、JavaScript、Perl、Object-C、Python、Ruby、Erlang、Golang等主流语言的客户端，所以不管是什么语言使用Stack的用户总会找到自己的客户端，它的受众非常广泛。笔者查看了http://datanyze.com网站，查看了Redis和MySQL最新的市场份额和排名对比，以及全球排名靠前的网站部署量对比（网站数据更新至2019.12.11）写作当天）：可以看到Redis整体份额排名第9，全球Top100站点部署数量与MySQL基本持平，因此Redis在国际上还是有一定地位的。3、说说实战。目前Redis发布的稳定版已经到了5.x，功能也越来越强大。在国内外互联网公司看来，Redis几乎是标配。作为一名开发人员，在日常的笔试面试和工作中遇到Redis相关问题的概率是非常高的，掌握Redis的相关知识点是非常有必要的。学习和整理一个复杂的东西，绝不能一下子就搞定。每个人都有自己的认知观念。笔者认为，要全面掌握Redis，需要由下而上、由外而内地了解Redis。Redis的实践知识点可以简单分为三个层次：底层实现：主要是从Redis的源代码中提取的问题，包括但不限于底层数据结构、服务模型、算法设计等。基础设施：可用的概述是Redis整体的外部功能和性能，包括但不限于单机主从架构的实现、主从数据同步、sentinel机制、集群实现、分布式一致性、故障迁移等。实用应用：Redis在实战中能为你做什么，包括但不限于单机缓存、分布式缓存、分布式锁，以及一些应用。深入理解和熟练使用Redis需要时间去磨练。轻而易举地做到这一点并不容易。要想在短时间内有所突破，只能从热门话题入手。虽然这感觉有点功利，但也无可厚非。为了吃饭，我们还是倾向于原谅懒惰4.底层实现热点话题底层实现篇的话题主要涉及Redis的源码和设计，可以说是Redis功能的基石.了解底层实现可以帮助我们更好的把握功能，因为底层代码很多，源码还是会穿插在后续的基础架构章节中进行分析，所以本文只罗列一些热点问题。Q1：Redis常用的5种数据类型是如何实现的？Redis支持的五种常用数据类型指的是值类型，分别是：stringString、listList、hashHash、集合Set、有序集合Zset，但Redis随后又丰富了几种数据类型，即Bitmaps、HyperLogLogs、GEO.由于Redis是基于标准C编写的，只有最基本的数据类型，Redis为了满足对外使用的五种数据类型，开发了自己独特的一套基本数据结构，并利用这些数据结构实现五种数据类型.Redis底层数据结构包括：简单动态数组SDS、链表、哈希表、跳转链表、整数集、压缩列表、对象。为了平衡空间和时间效率，Redis针对特定类型的值在底层实现了不同的数据结构。其中哈希表和压缩列表是复用较多的数据结构。下图展示了外部数据类型与底层数据结构之间的映射关系：从图中可以看出，ziplist压缩列表可以作为Zset、Set、List三种数据类型的底层实现。好像很厉害。编码后连续内存块的时序数据结构底层结构比较复杂。Q2：Redis的SDS与C中的strings相比有什么优势？C语言中用N+1长度的字符数组来表示一个字符串，最后用'\0'作为结束标志，不能满足Redis的这种实现方式。Redis出于安全、高效、功能丰富的需求，单独封装了SDS简单的动态字符串结构。在了解SDS的优势之前，需要先了解一下SDS的实现细节。查找src/sds的最新定义。它分为三个部分：header、buf、nullendcharacter。header可以看作是整个sds的引导部分。给定已用空间大小和最大分配大小等信息，然后用网上的一张图清楚的看到sdshdr8例子：在sds.h的源码中可以清楚的看到sds的完整实现细节/sds.c.本文不再展开，否则篇幅过长。赶紧进入正题，说说sds的优点：O(1)获取长度：需要遍历C字符串，直接获取sds中的len；防止缓冲区溢出bufferoverflow：当sds需要修改字符串时，首先借助len和alloc检查空间是否满足修改要求，如果空间不够，SDS会自动扩充空间，避免覆盖就像在C字符串操作中一样；有效减少内存分配次数：C字符串在涉及到添加或清除操作时，会改变底层数组的大小，导致重新分配，而sds采用了空间预分配和惰性空间释放的机制，说白了，就是意味着即每次扩容时乘以，缩容时先保留，不正式返回给OS。这两种机制也比较容易理解；二进制安全：C语言的字符串只能保存ascii码，不能保存图片、音频等信息。SDS是二进制安全的，写入什么都可以读取，没有任何过滤或限制；总结图片：Q3：Redis字典是如何实现的？简述progressiverehash的过程。字典是Redis5常用数据类型中的明星成员。前面说过，字典可以基于ziplist和hashtable来实现。我们只讨论基于hashtable的实现原理。字典是一个很明显的数据类型，如图：有了一个大概的概念，我们来看最新的src/dict.h源码定义：//哈希节点结构typedefstructdictEntry{void*key;union{void*val;uint64_tu64;int64_ts64;doubled;}v;structdictEntry*next;}dictEntry;//封装字典的操作函数指针typedefstructdictType{uint64_t(*hashFunction)(constvoid*key);void*(*keyDup)(void*privdata,constvoid*key);void*(*valDup)(void*privdata,constvoid*obj);int(*keyCompare)(void*privdata,constvoid*key1,constvoid*key2);void(*keyDestructor)(void*privdata,void*key);void(*valDestructor)(void*privdata,void*obj);}dictType;/*Thisisourhashtablestructure.Everydictionaryhastwoofthisaswe*implementincrementalrehashing,fortheoldtothenewtable.*///哈希表结构是理解字典typedefstrucctdict的关键{dictEntry**table;unsignedlongsize;unsignedlongsizemask;unsignedlongused;}dicttht;//字典结构typedefstructdict{dictType*type;void*privdata;dictththt[2];longrehashidx;/*rehashingnotinprogressifrehashidx==-1*/unsignedlongiterators*running*runsc/}dict;C语言的优点是定义必须自下而外，所以我们可以看到明显的电平变化，所以作者再次画一张图来说明具体的层级概念：关于dictEntrydictEntry是一个哈希表节点，就是我们存储数据的地方。它的protected成员是：key，v，next指针key存放的是键值对中的key，v存放的是key键值对中的value，value可以是指针也可以是uint64_t或int64_t。next是指向另一个哈希表节点的指针。该指针可以一次性连接多个具有相同哈希值的键值对，解决哈希冲突问题。图中展示了两个冲突的哈希节点的连接关系：关于dicttht，从源码来看，哈希表包含的成员有table、size、used、sizemask。table是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存一个键值对；size属性记录了哈希表表的大小，used属性记录了哈希表中现有节点的个数。sizemask等于size-1，hash值计算一个key在表数组中的索引，计算索引时用到。上图展示了一个大小为4的表中的hash节点，其中k1和k0在index=2处发生hash冲突，开放链表的存在本质上是k0先存，k1为了冲突而放置。保证效率直接放在冲突链表的最前面，因为链表没有尾指针。关于dict从源码可以看出，dict结构是一个字典的定义，其成员包括type、privdata、ht、rehashidx。其中dictType指针类型的类型指向操作字典的api，可以理解为函数指针。ht是一个包含2个dicttht的数组，即字典包含2个哈希表。rehashidx用于rehash的变量，privdata配合dictType指向的函数作为参数，让我们对字典的几个成员有了初步的了解。字典的哈希算法redis使用MurmurHash算法计算哈希值。该算法最初由AustinAppleby于2008年发明。MurmurHash算法无论数据输入情况如何，都能给出随机分布良好的哈希值，计算速度非常快。速度快，目前有MurmurHash2和MurmurHash3等版本。普通Rehash哈希表中存储的键值对数量是动态变化的。为了使哈希表的负载因子保持在一个合理的范围内，需要对哈希表进行扩缩容。缩放和缩小是通过执行重新散列重新散列来完成的。对字典的哈希表进行普通rehash的基本步骤是分配空间->逐个迁移->交换哈希表。详细过程如下：1、为字典的ht[1]哈希表分配空间，分配空间的大小取决于要执行的操作和ht[0中当前包含的键值对的数量]：扩容时ht[1]的大小是第一个大于等于.used*2的ht[0]2^n；ht[1]的大小是大于或等于ht[0]的第一个2^n。在收缩操作期间使用；比如展开时h[0].used=200，那么需要选择大于400的2的第1次方，即2^9=512。2、重新计算ht[0]到ht[1]中存储的所有键值对的哈希值和索引值；3．重复rehash，直到ht[0]中包含的所有键值对迁移到ht[1]，然后释放ht[0]，将ht[1]设置为ht[0]，在ht[1]中新建一个]用于下一次重新哈希的空白哈希表。ProgressiveRehash过程Redis的rehash动作不是一次性完成的，而是分多次逐步完成的。原因是当哈希表中存储的键值对数量较多时，这些键值对全部rehash到ht[1]可能会导致服务器停止服务一段时间，这是不可接受的.针对这种情况，Redis采用了progressiverehash，过程的详细步骤：为ht[1]分配空间，这个过程和普通的Rehash没有区别；将rehashidx设置为0，表示正式开始rehash工作，并且这个rehashidx是增量的，从0开始表示从数组的第一个元素开始rehash。rehash过程中，每次对字典进行增删改查，将rehashidx索引上ht[0]哈希表的键值对rehash为ht[1]，rehashidx加1指向下一个需要重新散列的键值对。随着字典操作的不断执行，最终ht[0]中的所有键值对都会被rehash到ht[1]，然后将rehashidx属性的值设置为-1表示rehash操作已经完成.progressiverehash的思想是将rehash键值对所需的计算工作分散到每次对字典的增删改查操作中，从而避免集中式rehash带来的阻塞问题。看到这里，不由得想这样的piggy-backrehash会不会导致流程很长？如果某个值没有被操作过，那么影响不大，因为它在需要扩展的时候还没有被使用。如果在需要减少的时候不处理，可能会造成内存浪费，具体还没来得及研究，先埋个问题吧！
