最近一周没有技能文章产出，紧张是Q4立时结束各种业务都在冲量，笔者一贯都在猖獗工作甚至还有些焦虑到偶尔失落眠，由于没有成块的韶光研究新东西，以是就把之前看过的东西抽韶光总结了下。
操持分三篇来梳理Redis的干系热点问题，本次为开山底层实现篇，通过本文你将理解到以下内容：
温馨提示：内容并不难，就怕你不看。
看不懂可以先收藏先Mark，等到深入研究的韶光再翻出来看看，你就创造真是24K干货呀！
停滞吹嘘，写点不一样的笔墨吧！
Redis是一个利用ANSI C编写的开源、支持网络、基于内存、可选持久化的高性能键值对数据库。Redis的之父是来自意大利的西西里岛的Salvatore Sanfilippo，Github网名antirez，笔者找了作者的一些简要信息并翻译了一下，如图：
从2009年第一个版本起Redis已经走过了10个年头，目前Redis仍旧是最盛行的key-value型内存数据库的之一。
精良的开源项目离不开大公司的支持，在2013年5月之前，其开拓由VMware资助，而2013年5月至2015年6月期间，其开拓由毕威拓资助，从2015年6月开始，Redis的开拓由Redis Labs资助。
笔者也利用过一些其他的NoSQL，有的支持的value类型非常单一，因此很多操作都必须在客户端实现，比如value是一个构造化的数据，须要修正个中某个字段就须要整体读出来修正再整体写入，显得很笨重，但是Redis的value支持多种类型，实现了很多操作在做事端就可以完成了，这个对客户端而言非常方便。
当然Redis由于是内存型的数据库，数据量存储量有限而且分布式集群本钱也会非常高，因此有很多公司开拓了基于SSD的类Redis系统，比如360开拓的SSDB、Pika等数据库，但是笔者认为从0到1的难度是大于从1到2的难度的，毋庸置疑Redis是NoSQL中浓墨重彩的一笔，值得我们去深入研究和利用。
2.Redis的江湖地位Redis供应了Java、C/C++、C#、 PHP 、JavaScript、 Perl 、Object-C、Python、Ruby、Erlang、Golang等多种主流措辞的客户端，因此无论利用者是什么措辞栈总会找到属于自己的那款客户端，受众非常广。
笔者查了datanyze.com网站看了下Redis和MySQL的最新市场份额和排名比拟以及环球Top站点的支配量比拟(网站数据更新到写作当日2019.12.11)：
可以看到Redis总体份额排名第9并且在环球Top100站点中支配数量与MySQL基本持平，以是Redis还是有一定的江湖地位的。
3.聊聊实战
目前Redis发布的稳定版本已经到了5.x，功能也越来越强大，从国内外互联网公司来看Redis险些是标配了。作为开拓职员在日常笔试口试和事情中碰着Redis干系问题的概率非常大，节制Redis的干系知识点都十分有必要。
学习和梳理一个繁芜的东西肯定不能胡子眉毛一把抓，每个人都有自己的认知思路，笔者认为要从充分节制Redis须要从底向上、从外到内去理解Redis。
Redis的实战知识点可以大略分为三个层次：
底层实现：紧张是从Redis的源码中提炼的问题，包括但不限于底层数据构造、做事模型、算法设计等。根本架构：可用概况为Redis整体对外的功能点和表现，包括但不限于单机版主从架构实现、主从数据同步、哨兵机制、集群实现、分布式同等性、故障迁移等。实际运用：实战中Redis可用帮你做什么，包括但不限于单机缓存、分布式缓存、分布式锁、一些运用。深入理解和闇练利用Redis须要韶光熬炼，要做到信手拈来其实不易，想在短韶光内打破只能从热点题目入手，虽然这样觉得有些功利，不过也算无可厚非吧，为了用饭我们还是方向于体谅
4.底层实现热点题目
底层实现篇的题目紧张是与Redis的源码和设计干系，可以说是Redis功能的基石，理解底层实现可以让我们更好地节制功能，由于底层代码很多，在后续的根本架构篇中仍旧会穿插源码来剖析，因此本篇只列举一些热点的问题。
Q1: Redis常用五种数据类型是如何实现的？Redis支持的常用5种数据类型指的是value类型，分别为：字符串String、列表List、哈希Hash、凑集Set、有序凑集Zset，但是Redis后续又丰富了几种数据类型分别是Bitmaps、HyperLogLogs、GEO。
由于Redis是基于标准C写的，只有最根本的数据类型，因此Redis为了知足对外利用的5种数据类型，开拓了属于自己独占的一套根本数据构造，利用这些数据构造来实现5种数据类型。
Redis底层的数据构造包括：大略动态数组SDS、链表、字典、跳跃链表、整数凑集、压缩列表、工具。
Redis为了平衡空间和韶光效率，针对value的详细类型在底层会采取不同的数据构造来实现，个中哈希表和压缩列表是复用比较多的数据构造，如下图展示了对外数据类型和底层数据构造之间的映射关系：
从图中可以看到ziplist压缩列表可以作为Zset、Set、List三种数据类型的底层实现，看来很强大，压缩列表是一种为了节约内存而开拓的且经由分外编码之后的连续内存块顺序型数据构造，底层构造还是比较繁芜的。
Q2: Redis的SDS和C中字符串比较有什么上风？在C措辞中利用N+1长度的字符数组来表示字符串，尾部利用'\0'作为结尾标志，对付此种实现无法知足Redis对付安全性、效率、丰富的功能的哀求，因此Redis单独封装了SDS大略动态字符串构造。
在理解SDS的上风之前须要先看下SDS的实现细节，找了github最新的src/sds.h的定义看下：
typedef char sds;/这个用不到 忽略即可/struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; / 3 lsb of type, and 5 msb of string length / char buf[];};/不同长度的header 8 16 32 64共4种 都给出了四个成员len：当前利用的空间大小；alloc去掉header和结尾空字符的最大空间大小flags:8位的标记 下面关于SDS_TYPE_x的宏定义只有5种 3bit足够了 5bit没有用buf:这个跟C措辞中的字符数组是一样的，从typedef char sds可以知道便是这样的。buf的最大长度是2^n 个中n为sdshdr的类型，如当选择sdshdr16，buf_max=2^16。/struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; / used / uint8_t alloc; / excluding the header and null terminator / unsigned char flags; / 3 lsb of type, 5 unused bits / char buf[];};struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; / used / uint16_t alloc; / excluding the header and null terminator / unsigned char flags; / 3 lsb of type, 5 unused bits / char buf[];};struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; / used / uint32_t alloc; / excluding the header and null terminator / unsigned char flags; / 3 lsb of type, 5 unused bits / char buf[];};struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; / used / uint64_t alloc; / excluding the header and null terminator / unsigned char flags; / 3 lsb of type, 5 unused bits / char buf[];};#define SDS_TYPE_5 0#define SDS_TYPE_8 1#define SDS_TYPE_16 2#define SDS_TYPE_32 3#define SDS_TYPE_64 4#define SDS_TYPE_MASK 7#define SDS_TYPE_BITS 3
看了前面的定义，笔者画了个图：
从图中可以知道sds实质分为三部分：header、buf、null结尾符，个中header可以认为是全体sds的指引部分，给定了利用的空间大小、最大分配大小等信息，再用一张网上的图来清晰看下sdshdr8的实例：
在sds.h/sds.c源码中可清楚地看到sds完全的实现细节，本文就不展开了要不然篇幅就过长了，快速进入主题说下sds的上风：
O(1)获取长度: C字符串须要遍历而sds中有len可以直接得到；防止缓冲区溢出bufferoverflow: 当sds须要对字符串进行修正时，首先借助于len和alloc检讨空间是否知足修正所需的哀求，如果空间不足的话，SDS会自动扩展空间，避免了像C字符串操作中的覆盖情形；有效降落内存分配次数：C字符串在涉及增加或者打消操作时会改变底层数组的大小造成重新分配、sds利用了空间预分配和惰性空间开释机制，说白了便是每次在扩展时是成倍的多分配的，在缩容是也是先留着并不正式归还给OS，这两个机制也是比较好理解的；二进制安全：C措辞字符串只能保存ascii码，对付图片、音频等信息无法保存，sds是二进制安全的，写入什么读取便是什么，不做任何过滤和限定；老规矩上一张黄健伟大神总结好的图：
Q3:Redis的字典是如何实现的？简述渐进式rehash的过程。字典算是Redis5中常用数据类型中的明星成员了，前面说过字典可以基于ziplist和hashtable来实现，我们只谈论基于hashtable实现的事理。
字典是个层次非常明显的数据类型，如图：
有了个大概的观点，我们看下最新的src/dict.h源码定义：
//哈希节点构造typedef struct dictEntry { void key; union { void val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry next;} dictEntry;//封装的是字典的操作函数指针typedef struct dictType { uint64_t (hashFunction)(const void key); void (keyDup)(void privdata, const void key); void (valDup)(void privdata, const void obj); int (keyCompare)(void privdata, const void key1, const void key2); void (keyDestructor)(void privdata, void key); void (valDestructor)(void privdata, void obj);} dictType;/ This is our hash table structure. Every dictionary has two of this as we implement incremental rehashing, for the old to the new table. ///哈希表构造 该部分是理解字典的关键typedef struct dictht { dictEntry table; unsigned long size; unsigned long sizemask; unsigned long used;} dictht;//字典构造typedef struct dict { dictType type; void privdata; dictht ht[2]; long rehashidx; / rehashing not in progress if rehashidx == -1 / unsigned long iterators; / number of iterators currently running /} dict;
C措辞的好处在于定义必须是由最底层向外的，因此我们可以看到一个明显的层次变革，于是笔者又画一图来展现详细的层次观点：
关于dictEntry
dictEntry是哈希表节点，也便是我们存储数据地方，其保护的成员有：key,v,next指针。key保存着键值对中的键，v保存着键值对中的值，值可以是一个指针或者是uint64_t或者是int64_t。next是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来办理哈希冲突的问题。
如图为两个冲突的哈希节点的连接关系：
关于dictht
从源码看哈希表包括的成员有table、size、used、sizemask。table是一个数组，数组中的每个元素都是一个指向dictEntry构造的指针， 每个dictEntry构造保存着一个键值对；size 属性记录了哈希表table的大小，而used属性则记录了哈希表目前已有节点的数量。sizemask即是size-1和哈希值打算一个键在table数组的索引，也便是打算index时用到的。
如上图展示了一个大小为4的table中的哈希节点情形，个中k1和k0在index=2发生了哈希冲突，进行开链表存在，实质上是先存储的k0，k1放置是发生冲突为了担保效率直接放在冲突链表的最前面，由于该链表没有尾指针。
关于dict从源码中看到dict构造体便是字典的定义，包含的成员有type，privdata、ht、rehashidx。个中dictType指针类型的type指向了操作字典的api，理解为函数指针即可，ht是包含2个dictht的数组，也便是字典包含了2个哈希表，rehashidx进行rehash时利用的变量，privdata合营dictType指向的函数作为参数利用，这样就对字典的几个成员有了初步的认识。
字典的哈希算法
//伪码：利用哈希函数，打算键key的哈希值hash = dict->type->hashFunction(key);//伪码：利用哈希表的sizemask和哈希值，打算出在ht[0]或许ht[1]的索引值index = hash & dict->ht[x].sizemask;//源码定义#define dictHashKey(d, key) (d)->type->hashFunction(key)
redis利用MurmurHash算法打算哈希值，该算法最初由Austin Appleby在2008年发明，MurmurHash算法的无论数据输入情形如何都可以给出随机分布性较好的哈希值并且打算速率非常快，目前有MurmurHash2和MurmurHash3等版本。
普通Rehash重新散列哈希表保存的键值对数量是动态变革的，为了让哈希表的负载因子坚持在一个合理的范围之内，就须要对哈希表进行扩缩容。
扩缩容是通过实行rehash重新散列来完成，对字典的哈希表实行普通rehash的基本步骤为分配空间->逐个迁移->交流哈希表，详细过程如下：
为字典的ht[1]哈希表分配空间，分配的空间大小取决于要实行的操作以及ht[0]当前包含的键值对数量：扩展操作时ht[1]的大小为第一个大于即是ht[0].used2的2^n；紧缩操作时ht[1]的大小为第一个大于即是ht[0].used的2^n ；扩展时比如h[0].used=200，那么须要选择大于400的第一个2的幂，也便是2^9=512。将保存在ht[0]中的所有键值对重新打算键的哈希值和索引值rehash到ht[1]上；重复rehash直到ht[0]包含的所有键值对全部迁移到了ht[1]之后开释 ht[0]， 将ht[1]设置为 ht[0]，并在ht[1]新创建一个空缺哈希表， 为下一次rehash做准备。渐进Rehash过程Redis的rehash动作并不是一次性完成的，而是分多次、渐进式地完成的，缘故原由在于当哈希表里保存的键值对数量很大时， 一次性将这些键值对全部rehash到ht[1]可能会导致做事器在一段韶光内停滞做事，这个是无法接管的。
针对这种情形Redis采取了渐进式rehash，过程的详细步骤：
为ht[1]分配空间，这个过程和普通Rehash没有差异；将rehashidx设置为0，表示rehash事情正式开始，同时这个rehashidx是递增的，从0开始表示从数组第一个元素开始rehash。在rehash进行期间，每次对字典实行增编削查操作时，顺带将ht[0]哈希表在rehashidx索引上的键值对rehash到 ht[1]，完成后将rehashidx加1，指向下一个须要rehash的键值对。随着字典操作的不断实行，终极ht[0]的所有键值对都会被rehash至ht[1]，再将rehashidx属性的值设为-1来表示 rehash操作已完成。渐进式 rehash的思想在于将rehash键值对所需的打算事情分散到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的壅塞问题。
看到这里不禁去想这种捎带脚式的rehash会不会导致全体过程非常漫长？如果某个value一贯没有操作那么须要扩容时由于一贯不用以是影响不大，须要缩容时如果一贯不处理可能造成内存摧残浪费蹂躏，详细的还没来得及研究，先埋个问题吧！
Q4:跳跃链表理解吗？Redis的Zset如何利用跳表实现的？ZSet这种数据类型也非常有用，在做排行榜需求时非常有用，笔者就曾经利用这种数据类型来实现某日活2000w的app的排行榜，以是理解下ZSet的底层实现很有必要，之前笔者写过两篇文章先容跳跃链表和ZSet的实现，因此查阅即可。深入理解跳跃链表[一]深入理解跳表在Redis中的运用
Q5:Redis为什么利用单线程？讲讲Redis网络模型以及单线程如何折衷各种事宜运行起来的？Redis在新版本中并不是纯挚的单线程做事，一些赞助事情会有BIO后台线程来完成，并且Redis底层利用epoll来实现了基于事宜驱动的反应堆模式，在全体主线程运行工程中不断折衷韶光事宜和文件事宜来完玉成部系统的运行，笔者之前写过两篇干系的文章，查阅即可得到更深层次的答案。
