虽然一直都在使用Redis数据库，但是从来没有研究过它的内部存储结构，连面试都没有。事物。最近在看一个网课，里面提到了这部分，结合《Redis 设计与实现》这本书，大致梳理了一下Redis的内部存储结构。就是下图。对于Redis数据库，大部分人都知道每个Redis实例有16个数据库，但是大部分人可能不知道内部是怎么逆向的，反正我也不知道。整体流程大致如上图所示。知识有限，难免有漏洞，凑合吧。其实前面的都不太重要，重要的是后面四种数据结构和redisObject。不管多重要，再来一次。redisDbredisDb是一个存储真实数据的数据库实例。每个Redis实例将有16个redisDb。redisDb的结构定义如下：typedefstructredisDb{dict*dict;/*ThekeyspaceforthisDB*/dict*expires;/*Timeoutofkeyswithatimeoutset*/dict*blocking_keys;/*Keyswithclientswaitingfordata(BLPOP)*/dict*ready_keys;/*BlockedkeysthatreceivedaPUSH*/dict*watched_keys;/*WATCHEDkeysforMULTI/EXECCAS*/intid;/*DatabaseID*/longlongavg_ttl;/*AverageTTL,justforstats*/list*defrag_later;/*Listofkeynamestoattempttodefragonebyone,gradually.*/}redisDb;redisDb结构中有8个参数：dict：dict用于存储数据，当前DB下的所有数据都存储在这里。expires：存储key和过期时间的映射关系。blocking_keys：存放阻塞状态的key和client列表。例如，在Redis中执行列表阻塞命令blpop、brpop、brpoplpush时，如果对应的list列表为空，Redis会将对应的client设置为阻塞状态，并将client添加到DB中的阻塞dictblocking_keys中。ready_keys：存放未被封锁的Keys。当其他调用者正在向某个key对应的列表中添加元素时，Redis会检测是否有客户端阻塞在这个key上，即检查blocking_keys中是否包含这个key，如果有，则将这个key添加到read_keys字典中中间。同时，这个key也会保存在服务器中一个名为read_keys的列表中。watched_keys：当client使用watch命令监听key时，key和client会保存在watched_keys字典中。id：数据库ID。Redis中DictDict数据结构非常重要。可以看到在redisDb中，8个字段中有5个是dict，其他地方也有很多应用。dict结构定义如下：typedefstructdict{dictType*type;void*privdata;dictththt[2];longrehashidx;/*rehashingnotinprogressifrehashidx==-1*/unsignedlongiterators;/*numberofiteratorscurrentlyrunning*/}dict;dict本身比较简单，该字段不多，重要的字段有3个，需要了解：type：用于保存hash函数和key/value赋值、比较函数。ht[2]：用于存放数据的数组。默认情况下，使用数组编号0。如果0号哈希表中的元素过多，则分配2号哈希表大小两倍的空间给1号哈希表，然后逐步迁移。rehashidx：用于标识迁移位置。dictht&DictEntrytypedefstructdictht{#哈希表数组dictEntry**table;#哈希表大小unsignedlongsize;#哈希表大小掩码，用于计算索引值unsignedlongsizemask;#哈希表中已有节点数unsignedlongused;}dictht;typedefstrucctictEntry{#keyvoid*key;union{#valuevoid*val;uint64_tu64;int64_ts64;doubled;}v;#指向下一个哈希表节点，形成链表structdictEntry*next;}dictEntry;dicttht数据结构没什么好说的，dictEntry是真正挂载数据的节点，有点像Java中的Map，使用key-value映射。key是一串sds结构，value是一个存储各种数据类型的redisObject结构。RedisObject、sds等几个数据结构是重点，面试的时候可能会出现。作为用户，了解这几个就够了。redisObjectredisObject可以理解为Redis数据的数据头，定义了一些数据信息。redisObject结构定义如下：typedefstructredisObject{unsignedtype:4;unsignedencoding:4;unsignedlru:LRU_BITS;/*LRUtime(relativetogloballru_clock)or*LFUdata(leastsignificant8bitsfrequency*andmostsignificant16bitsaccesstime).*/intrefdis;void*ptr;}Objectrobj;fieldNot很多，只有5个字段，但是这些字段非常重要。我们先看一下这5个字段的含义：typetype表示Redis对象的数据类型，表示这个数据的类型。目前，Redis有7种类型。它们是：OBJ_STRING：字符串对象。OBJ_LIST：列表对象。OBJ_SET：集合对象。OBJ_ZSET:Orderedcollectionobject.OBJ_HASH:hashobject.OBJ_MODULE:moduleobject.OBJ_STREAM:messagequeue/streamobject.encodingencodingistheinternalencodingmethodoftheRedisobject,thatis,whichdatastructurethispieceofdataisultimatelystoredinternally.这个字段的作用还是相当大的，我看了一下源码，目前Redis中有10种编码方式，如下：OBJ_ENCODING_RAWOBJ_ENCODING_INTOBJ_ENCODING_HTOBJ_ENCODING_ZIPLISTOBJ_ENCODING_ZIPMAPOBJ_ENCODING_SKIPLISTOBJ_ENCODING_EMBSTROBJ_ENCODING_QUICKLISTOBJ_ENCODING_STREAMOBJ_ENCODING_INTSETLRULRU存储的是淘汰数据用的LRU时间或LFU频率及时间Thedata.refcountrefcountrecordsthereferencecountoftheRedisobject,whichisusedtoindicatethenumberoftimestheobjectisshared.Whenshared,add1,anddecrement1whenitisnolongerused.Whenthecountis0,itindicatesthattheobjectisnotused,anditwillbereleasedandthememorywillbereclaimed.ptrptrisareferencetotherealdatastore,whichpointstotheobject'sinternaldatastructures.Forexample,astringobjectmayhaveansdsdatastructureinternally,soptrpointstosds.Inaddition,ptrmayalsopointtoziplist,quicklist,andskiplist.RedisObjectisaboutthese.Let’stalkaboutthefourdatastructurescommonlyusedinmemoryinRedis.1.sds(simpledynamicstring)RedisdoesnotdirectlyusethetraditionalstringrepresentationoftheClanguage(acharacterarrayterminatedbyanullcharacter,hereinafterreferredtoasaCstring),butbuildsamethodcalledsimpledynamicstring(simpledynamicstring(SDS),anduseSDSasthedefaultstringrepresentationforRedis.Inordertoreduceoverhead,theimplementerdefines5structuresforsds,namely:sdshdr5,sdshdr8,sdshdr16,sdshdr32,sdshdr64.这样在存储的时候，sds会根据字符串的实际长度选择不同的数据结构，更好的提高内存效率。五个结构体的源码如下：struct__attribute__((__packed__))sdshdr5{unsignedcharflags;/*3lsboftype,and5msbofstringlength*/charbuf[];};struct__attribute__((__packed__))sdshdr8{uint8_tlen;/*used*/uint8_talloc;/*excludingtheheaderandnullterminator*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};struct__attribute__((__packed__))sdshdr16{uint16_tlen;/*used*/uint16_talloc;/*excludingtheheaderandusnullterminator*/unsigned/charlsflags;bits,*5charbuf[];};struct__attribute__((__packed__))sdshdr32{uint32_tlen;/*已使用*/uint32_talloc;/*不包括标头和空终止符*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};struct__attribute__((__packed__64)sd{uint64_tlen;/*used*/uint64_talloc;/*不包括header和nullterminator*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};除了sdshdr5，其他几个数据结构包含4个字段:len:character字符串的长度alloc:为字符串分配的内存大小flags：当前字节数组的属性。buf：存储字符串的实际值和一个终止符\0。redisObject中有一个encodingmethod字段，sds数据结构有三种编码方式，分别是INT、RAW、EMBSTR。INT比较简单，ptr直接指向具体的数据。这里简单说一下RAW和EMBSTR的区别。在Redis源码中，有这么一段代码来判断使用哪种编码方式。当保存的字符串长度小于等于44时，使用embstr编码格式，否则使用RAW编码方式。（具体长度可能每个版本定义不同）#defineOBJ_ENCODING_EMBSTR_SIZE_LIMIT44robj*createStringObject(constchar*ptr,size_tlen){if(len<=OBJ_ENCODING_EMBSTR_SIZE_LIMIT)returncreateEmbeddedStringObject(ptr,len);elsereturncreateRawStringObject(ptr,len);}embstrmain方式的区别在于分配内存的时间。embstr编码是一种专门用于保存短字符串的优化编码方式。raw编码会调用两次内存分配函数，分别创建redisObject结构和sdshdr结构，而embstr编码会调用一次内存分配函数，分配一个连续的block。空间，依次包含redisObject和sdshdr两个结构体。embstrencodingrawencodingrawencodingsds主要作为字符串的内部数据结构，sds也是hyperloglog和bitmap类型的内部数据结构。2.ziplist（压缩列表）ziplist是一种专门为节省内存和减少内存碎片而设计的数据结构。Ziplist是一个连续的内存空间，可以连续存储多个元素，没有多余的空间。它是由连续的存储数据块组成的一种顺序存储结构。ziplist主要包括5个部分：zlbytes：ziplist占用内存的总字节数。Zltail：尾节点到起始位置的字节数。Zllen：包含的节点/内存块总数。entry：ziplist中保存的每个数据节点，这些数据点的长度是任意的。Zlend：一个幻数255，用来标记压缩列表的结束。如图，一个包含4个元素的ziplist一共占用100个字节，ziplist起始元素的指针为p，zltail为80，第四个元素的指针为P+80。ziplist的存储节点是zlentry，zlentry结构体定义如下：typedefstructzlentry{unsignedintprevrawlensize;/*Bytesusedtoencodethepreviousentrylen*/unsignedintprevrawlen;/*Previousentrylen.*/unsignedintlensize;/*Bytesusedtoencodethisentrytype/len.Forexamplestringshavea1,2or5bytesheader.Integersalwaysuseasinglebyte.*/unsignedintlen;/*Bytesusedtorepresenttheactualentry.Forstringsthisisjustthestringlengthwhileforintegersitis1,2,3,4,8or0(for4bitimmediate)dependingonthenumberrange.*/unsignedintheadersize;/*prevrawlensize+lensize.*/unsignedcharencoding;/*SettoZIP_STR_*orZIP_INT_*dependingontheentryencoding.Howeverfor4bitsimmediateintegersthiscanassumearangeofvaluesandmustberange-checked.*/unsignedchar*p;/*pointertheverystartoftheentry，即thispointstopprev-entry-lenfield.*/}zlentry；zlentry结构体中有6个字段：prevRawLen：前一个节点的长度；preRawLenSize：编码preRawLen需要的字节数；len：当前节点的长度；lensize:编码len所需的字节数；encoding：当前节点使用的编码类型；entryData：当前节点的数据；由于ziplist是连续且紧凑的存储，没有多余的空间，所以插入新元素需要realloc来扩充内存，所以如果ziplist占用空间太大，realloc重新分配内存和复制的开销会很大，所以ziplist不适合存储太多元素，也不适合存储大字符串ziplist是hash和sortedset数据类型的内部存储结构之一。对于hash，当元素个数不超过512，值不超过64字节时，会使用ziplist作为内存存储结构。我们可以通过修改hash-max-ziplist-entries、hash-max-ziplist-value参数来控制。对于sortedset，当元素个数不超过128，值不超过64字节时，使用ziplist存储，可以通过调整zset-max-ziplist-entries和zset-max-ziplist-value来控制。3.quicklist（快速列表）quicklist数据结构是Redis在3.2之后引入的，用来替代linkedlist。由于链表的每个节点都有前向和后向指针，占用16个字节，每个节点独立分配内存，容易加剧内存碎片。ziplist由于存储紧凑，需要realloc来添加元素，memorycopy来删除元素。自然不适合元素太多、值太大的存储，于是诞生了quicklist。quicklist相关的结构定义如下：typedefstructquicklist{quicklistNode*head;quicklistNode*tail;unsignedlongcount;/*totalcountofallentriesinallziplists*/unsignedlonglen;/*numberofquicklistNodes*/intfill:16;/*fillfactorforindividualnodes*/unsignedintcompress:16;/*depthtocomofend;nodes=off*/}quicklist;typedefstructquicklistNode{structquicklistNode*prev;structquicklistNode*next;unsignedchar*zl;unsignedintsz;/*ziplistsizeinbytes*/unsignedintcount:16;/*countofitemsinziplist*/unsignedintencoding:2;/*RAW==1orLZF==2*/unsignedintcontainer:2;/*NONE==1orZIPLIST==2*/unsignedintrecompress:1;/*这个节点之前是否压缩过？*/unsignedintattempted_compress:1;/*nodecan'tcompress;toosmall*/unsignedintextra:10;/*morebitstostealforfutureusage*//快速列表节点；quicklist整体结构：quicklist整体结构比较简单，是一个基于ziplist的双向链表。将数据段存储到ziplists中，然后将这些ziplists用双向指针连接起来。quicklist结构说明：head和tail是指向第一个和最后一个ziplist节点的两个指针。count是quicklist中所有元素的数量。len是ziplist节点的数量。compress是LZF算法的压缩深度。quicklistNode结构更简单。quicklistNode主要包括一个prev/next双向指针和一个ziplist节点。单个ziplist节点可以存储多个元素。quicklist是list列表的内部数据结构，quicklist快速从头到尾读写数据，时间复杂度为O(1)。也支持从中间任意位置插入或读写元素，但速度较慢，时间复杂度为O(n)。4.zskiplist(跳表)Java中也有跳表。zskiplist是一个有序的数据结构。它可以通过在每个节点中维护多个指向其他节点的指针来加快访问速度。在大多数场景下，跳表的效率接近于平衡树。跳表支持平均O(logN)和最差O(n)复杂度的节点查找，跳表的实现比平衡树简单。不过zskiplist在Redis中用的并不多，跳表只用在以下两种情况：在sortedset数据类型中，如果元素个数多或者元素长度大，则跳表是用作内部数据结构。如果默认的元素个数超过128个或者最大元素的长度超过64个，则将排序后的set存入zskiplist。用作集群节点中的内部数据结构。在Redis中，skiplist主要包括zskiplistNode和zskiplist的组合，定义如下：*;unsignedlonglength;intlevel;}zskiplist;typedefstructzset{dict*dict;zskiplist*zsl;}zset;skiplistzskiplist结构比较简单，有四个字段：header指向skiplist的头节点。tail指向跳转列表的尾节点。length表示跳跃表的长度，即跳跃表中不包含头节点的节点数。level为当前跳表中除头节点外的所有节点中层数最大的节点的层数。skiplist的节点zskiplistNode比较复杂。但是只有4个字段：ele是节点对应的sds值，在zset有序集合中，是集合中的field元素。分数是节点的分数。通过score，将跳转列表中的节点按照从小到大的顺序排列。backward是指向当前节点的前一个节点的指针。level是节点中的层，每个节点一般有多个层。每一层都有两个属性，一个是前向指针，用来指向表尾方向的节点；另一个是span，指的是forward指向的节点到当前节点的距离。跳表的思路比较简单，用空间换时间，可以实现快速查找。比如我们要查找节点S3，我们从表头节点的L32层开始查找，逐层下降，最终找到想要的元素。最后总结一下8大类Redis使用的内部存储结构。
