前言上一篇Redis闲聊（一）：搭建知识图谱介绍了Redis的基本概念、优缺点，以及它的内存淘汰机制。相信大家对于Redis的了解都有一个初步的了解。Redis在互联网的很多应用场景中都有使用，它能做的事情远超我们的想象。Redis的底层数据结构是什么，为什么能做这么多事情？本文将探讨Redis的底层数据结构和常用命令。本文知识脑图如下：1.Redis的数据模型使用键值对名称：“小明”展示Redis的数据模型如下：dictEntry：在一些编程语言中，数据结构键值对称为字典，在Redis中，每个键值键值对都分配了一个字典实体，即“dicEntry”。dicEntry由三部分组成：key指针，val指针，next指针，next指针指向下一个dicteEntry，构成一个链表。这个next指针可以把多个hash值相同的key-value对链接在一起，通过链地址的方式解决hashcollisionsds的问题：SimpleDynamicString，简单动态字符串，存储字符串数据。redisObject：Redis常用的五种类型都存储在RedisObject中，redisObject中的type字段表示值的数据类型（即五种基本类型）。ptr字段指向对象所在的地址。RedisObject对象非常重要。Redis对象类型、内部编码、内存回收、共享对象等功能都是基于RedisObject对象实现的。这样设计的好处是可以根据不同的使用场景，为常用的五种类型设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。Redis使用jemalloc作为默认的内存分配器来减少内存碎片。在64位系统中，jemalloc将内存空间分为三个范围：small、large、huge；每个范围被分成许多小的内存块单元；Redis存储数据时，会选择大小最合适的内存块进行处理。贮存。2、Redis支持的数据结构有哪些？Redis支持的数据结构有哪些？如果答案是String、List、Hash、Set、Zset，那就错了。这5种是Redis常用的基本数据类型，每种数据类型又包含了多种数据结构。使用编码指令查看值的数据结构。例如：127.0.0.1:6379>setnametomOK127.0.0.1:6379>objectencodingname"embstr这里设置name值为tom，其数据结构为embstr，下面介绍字符串时会详细说明。127.0.0.1:6379>setage18OK127.0.0.1:6379>objectencodingage"int"下表总结了Redis中所有的数据结构类型：补充说明：如果面试官问：Redis的数据类型有哪些？答：String,list,hash,set,zetGeneral情况下，这个答案是正确的。上面说了，Redis的数据类型确实包括这5种，但是细心的同学一定发现了前面说的5种“常用”的数据类型。其实，withRedis的不断发展更新和完善，Redis有超过5种数据类型，登录Redis官网打开官方数据类型介绍（https://redis.io/topics/data-types-intro）：发现Redis支持多数据结构5种类型而不是8种，最后三种类型是：位数组（或简称位图）：可以使用位数组等特殊命令来操作字符串值：可以设置和清除各个位，将所有位设置为1。找到第一个位或一个未设置位等。HyperLogLogs：这是一种用于估计集合基数的概率数据结构。不要害怕，它比看起来更简单。Streams：Append-onlymap-like条目的集合，提供抽象的日志数据类型。本文主要介绍五种常用的数据类型，以上三种以后会一起探讨。1.stringstring类型是Redis中最常用的数据类型。在Redis中，字符串是可以修改的，它以字节数组的形式存在于底层。Redis中的字符串称为简单的动态字符串“SDS”。这种结构很像Java中的ArrayList，其长度是动态可变的。structSDS{Tcapacity;//数组容量tlen;//数组长度byte[]content;//数组内容}content[]存放的是字符串的内容，capacity表示数组分配的长度，len表示长度字符串的实际长度。字符串的编码类型有int、embstr和raw三种。如上表所示，这三种编码类型有什么区别呢？int编码：存储的是可以用long类型表示的整数值。raw编码：保存长度大于44字节的字符串（redis3.2之前为39字节，之后为44字节）。embstr编码：保存一个长度小于44字节的字符串（redis3.2之前39字节，之后44字节）。设置一个值测试一下：127.0.0.1:6379>setnum300127.0.0.1:6379>objectencodingnum“int”127.0.0.1:6379>setkey1wealwaysbyhappyhahahaOK127.0.0.1:6379>objectencodingkey1“embstr”127.0.0.1:6379>setkey2hahahahahahahahaahahahahahahahahahahahahahaOK127。0.0.1:6379>strlenkey2(integer)39127.0.0.1:6379>objectencodingkey2"embstr"127.0.0.1:6379>setkey2hahahahahahahahahahahahahahahahahahahahahahahaOK127.0.0.1:6379>objectencodingkey2"embstr"127.0.79type:比较embstr编码结构：raw编码结构：embstr和raw都是由redisObject和sds组成。不同的是：embstr的redisObject和sds是连续的，只需要用malloc分配一次内存；而raw需要分别为redisObject和sds分配内存，也就是需要分两次分配内存。相比之下，embstr分配一次内存更少，更方便。但是embstr也有明显的缺点：为了增加长度，redisObject和sds都需要重新分配内存。上面介绍了embstr和raw结构的区别。重点来了~为什么选择44作为两种编码的分界点呢？为什么3.2之前是39？这两个值是怎么出来的呢？(1)计算RedisObjectstructRedisObject{int4type;//4bitsint4encoding;//4bitsint24lru;//24bitsint32refcount;//4bytes=32bitsvoid*ptr;//8bytes,64-bitsystem}类型：不同的redis对象会有不同的数据类型（string、list、hash等），typerecords类型，会用到4位。encoding：存储编码后的形式，使用4bits。lru：用24bits记录对象的LRU信息。refcount：引用计数器，使用32bits。*ptr：指向对象具体内容的指针，需要64bits。计算：4+4+24+32+64=128bits=16bytes第一步完成，RedisObject对象头信息会占用16个字节的大小，这个大小通常是固定的。(2)sds占用字节老版size计算：structSDS{unsignedintcapacity;//4byteunsignedintlen;//4bytebyte[]content;//inlinearray,长度为capacity}这里unsignedint为4字节，增加最多8个字节。内存分配器jemalloc如果分配的内存超过64字节，则认为是大字符串，会使用embstr编码。如前所述，SDS结构中的内容字符串是以字节\0结尾的字符串。之所以多出这么一个字节，是为了方便直接使用glibc的字符串处理函数，方便对字符串的处理。调试打印输出。所以我们也减去1个字节64byte-16byte-8byte-1byte=39byte新版本：structSDS{int8capacity;//1byteint8len;//1byteint8flags;//1bytebyte[]content;//内联数组，长度为容量}这里的unsignedint变成了uint8_t、uint16_t.的形式，并且增加了一个charflags标志位，一共只用了3个字节。相当于优化了sds的内存使用，对应的用来存放字符串的内存会变大。然后计算：64byte-16byte-3byte-1byte=44byte。总结：因此Redis3.2版本之后，embstr最大可以容纳的字符串长度为44，之前是39。长度变化的原因是SDS中内存的优化。2、ListRedis中的List对象底层是通过quicklist（快速列表）实现的。快速列表支持从链表的头部和尾部添加元素，可以获取指定位置的元素内容。那么，快捷列表底层是如何实现的呢？为什么能达到这么快的性能呢？罗马不是一天建成的，快速列表也不是一天变现的。起初redis的链表底层是ziplist（压缩链表）或者linkedlist（双端链表）。先分别介绍一下这两个数据结构。(1)ziplist压缩列表当一个列表只包含少量的列表项，并且是小整数值或者长度比较短的字符串时，redis使用ziplist（压缩列表）作为列表键的底层实现。测试：127.0.0.1:6379>rpushdotaherosfqopdoom(integer)3127.0.0.1:6379>objectencodingdotahero"ziplist"这里使用旧版Redis进行测试，在其中加入qopQueenofPain、sfShadowDemon、doomdota英雄列表A英雄，数据结构编码使用ziplist。顾名思义，压缩列表就是压缩的。每个节点之间没有指针，但是多个元素之间是无间隙相邻的。所以ziplist是Redis为了节省内存而开发的，它是由一系列经过特殊编码的连续内存块组成的顺序数据结构。具体结构比较复杂，有兴趣的可以多了解下。structziplist{int32zlbytes;//整个压缩列表占用的字节数int32zltail_offset;//最后一个元素距离压缩列表起始位置的偏移量，用于快速定位最后一个节点int16zllength;//个数elementsT[]entries;//元素内容列表，紧凑地一一存储int8zlend;//标记压缩列表的结尾，值始终为0xFF}(2)双端列表（linkedlist）大家都很熟悉thedouble-endedlist，这里的double-endedlist很像java中的链表。从图中可以看出Redis的linkedlist双端链表具有以下特点：节点有prev、next指针、head指针和tail指针，获取front节点、rear节点、表头节点和表尾节点，并获取长度复杂度为O(1)。压缩列表占用内存较少，但它是一个顺序数据结构。插入和删除元素的操作比较复杂，所以压缩列表适用于数据比较小的情况。数据量大的时候，双端链表的高效插入删除还是比较好的。选择在Redis开发者眼中，数据结构的选择在时间和空间上一定是极端的。因此，他们将压缩列表和双端列表合二为一，创建了一个快速列表（quicklist）。和java中的hashmap一样，结合了数组和链表的优点。(3)快速列表(quicklist)rpush:listAddNodeHead---O(1)lpush:listAddNodeTail---O(1)push:listInsertNode---O(1)index:listIndex---O(N)pop:ListFirst/listLast---O(1)llen:listLength---O(N)structziplist{...}structziplist_compressed{int32size;byte[]compressed_data;}structquicklistNode{quicklistNode*prev;quicklistNode*next;ziplist*zl;//指向压缩列表int32size;//ziplist中的总字节数int16count;//ziplist中的元素个数int2encoding;//存储形式2bit，原生字节数组或LZF压缩存储...}structquicklist{quicklistNode*head;quicklistNode*tail;longcount;//元素总数intnodes;//ziplist节点数intcompressDepth;//LZF算法压缩深度...}quicklist默认压缩深度为0，即，没有压缩。实际压缩深度由配置参数list-compress-depth决定。为了支持快速的push/pop操作，quicklist的前两个ziplist没有压缩，此时深度为1。如果depth为2，表示不压缩quicklist的第一个和最后一个ziplist和第二个ziplist。3、HashHash数据类型的底层实现是ziplist（压缩列表）或字典（也称为哈希表或哈希表）。这里选择压缩列表还是字典也是根据元素个数来决定的。如图所示，hset有3个键值对，当每个值的字节数不超过64时，默认使用的数据结构是ziplist。当我们添加值超过64字节的数据时，默认的数据结构已经变成了hashtable。只有同时满足以下两个条件时，Hash对象才会使用ziplist（压缩列表）：hash中的元素个数小于512；散列中所有键值对的键值串长度均小于64字节。压缩列表刚刚了解，hashtables类似于jdk1.7之前的hashmap。Hashmap使用链地址的方式来解决哈希碰撞问题。想深入了解可以参考我之前写的一篇博客：你真的了解hashmap吗？(https://blog.csdn.net/qq_32519415/article/details/87006982)Redis中的Dictionary：Redis中的dict结构里面包含两个hashtable，通常只有一个hashtable有值。但是在对dict进行扩缩容的时候，需要分配一个新的hashtable，然后进行渐进式搬迁。此时，两个哈希表分别存储旧哈希表和新哈希表。搬迁结束后，旧哈希表将被删除并由新哈希表替换。4、SetSet数据类型的底层可以是intset（整数集）或hashtable（哈希表也叫哈希表）。当数据都是整数且个数不大时，使用intset作为底层数据结构；当存在非整数数据或数据量增加时，使用hashtable作为底层数据结构。127.0.0.1:6379>saddmyset111222333(integer)3127.0.0.1:6379>objectencodingmyset"intset"127.0.0.1:6379>saddmysethahaha(integer)1127.0.0.1:6379>objectencodingmyset"hashtable"inset/intsetinset/intset数据集结构is:Encodingmethoduint32_tencoding;//集合包含的元素个数uint32_tlength;//保存元素的数组int8_tcontents[];}intset;intset的底层实现是一个有序的、不重复的数组。intset的整数类型可以是16位、32位或64位。如果数组中所有整数的长度都是16位的，再加上一个32位的整数，那么整个16位的数组就会升级为32位的数组。升级可以提高intset的灵活性，节省内存，但不可逆。5、ZsetRedis中的zset也称为有序集。它的底层是ziplist（压缩列表）或者skiplist（跳跃列表）。前面介绍过压缩列表，同样的道理在元素个数比较少的时候使用。这里主要介绍跳转列表。跳转列表：跳转列表，顾名思义，可以跳转，跳转查询你要查找的元素。您可能不熟悉这种数据结构。虽然你接触的不多，但确实是一个各方面性能都不错的数据结构。它可以支持快速查询、插入和删除操作。它也比红黑树更难开发。容易多了。为什么跳表有这么高的性能？它是如何“跳跃”的？跳表使用了二分法的思想，二分法可以在数组中快速查找，在链表中也是可以的。例如，链表如下：假设要找到节点10，需要一个一个遍历，判断是否是你要找的节点。那么如何提高效率呢？mysql索引相信大家都不陌生，索引可以提高效率。这里也可以使用索引。取出一个索引层：这样只需要先找9再找10，大大节省了查找时间。可以抽取另一层索引，可以更好的节省时间：这样，基于链表的“二分查找”支持快速插入和删除，时间复杂度为O(logn)。由于跳表的快速查找效率，以及实现的简单性和可读性。所以Redis放弃了红黑树，选择了更简单的跳表。Redis中跳过表：typedefstructzskiplist{//表头节点和表尾节点structzskiplistNode*header,*tail;//表中的节点数unsignedlonglength;//层数最大的节点的层数intlevel在表中；}zskiplist；typedefstructzskiplistNode{//成员对象robj*obj;//Scoredoublescore;//BackpointerstructzskiplistNode*backward;//LayerstructzskiplistLevel{//ForwardpointerstructzskiplistNode*forward;//Span---前向指针指向节点和当前节点距离unsignedintspan;}level[];}zskiplistNode;zadd---zslinsert---平均O(logN)，最差O(N)zrem---zsldelete---平均O(logN)，最差O(N)zrank--zslGetRank---平均O(logN),WorstO(N)总结本文大致介绍了Redis常用的5种数据类型的底层实现。希望大家结合源码和资料，对它有更多的了解。数据结构之美在Redis中体现得淋漓尽致。从String到compressedlist、fastlist、hashtable、jumptable，这些数据结构在不同的地方都适用，各司其职。不仅如此，Redis还对这些数据结构进行了升级和组合，以最大限度地提高内存存储的效率和性能。正因如此，Redis才能成为众多互联网公司不可或缺的高性能、秒级键值内存数据库。【本文为栏目机构易新科技原创文章，微信公众号“易新科技（id：CE_TECH）”点击此处查看作者更多好文
