redis存储类型主要提供5种数据结构：字符串（String）、哈希（hash）、列表（list）、集合（set）、有序集合（shortset）；redis底层实现的8种数据结构SDSsimplesynchronousstring：支持自动动态扩容的字节数组列表：链表dict：使用双哈希表实现的支持平滑扩容的字典zskiplist：附有向后指针的跳转表Intset：Anownstructureziplistforstoringintegervaluesets：实现上类似于TLV的数据结构，但比TLV更复杂，用于存储任意数据的有序序列。quicklist：以ziplist为节点的双链表结构，实现的很好。在小型场合使用的轻量级字典结构中，5种存储类型和8种数据结构之间的桥梁是redisObject；Redis中的Key和Value都是表层的redisObject实例，所以这个结构有所谓的“类型”，也就是ValueType。对于ValueType类型的每个redisObject；它的底层至少支持两种不同的底层数据结构来实现。为了处理Redis在不同应用场景下的运行效率，或者内存占用等底层数据的结构分析1.SDS-simpledynamicstring在src文件夹下可以看到sds.c和sds.h的源码文件安装目录的typedefchar*sds;/*注意：sdshdr5从未使用过，我们只是直接访问theflagsbyte。*然而，它的文档布局outoftype5SDSstrings。*/struct__attribute__((__packed__))sdshdr5{unsignedcharflags;/*3lsboftype,and5msbofstringlength*/charbuf[];};struct__attribute__)((__packed__))sdshdr8{uint8_tlen;/*used*/uint8_talloc;/*excludingtheheaderandnullterminator*/unsignedcharflags;/*5unsignedcharflags;/*5lsboftypesedbits*/charbuf[];};struct__attribute__((__packed__))sdshdr16{uint16_tlen;/*used*/uint16_talloc;/*不包括header和nullterminator*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};struct__attribute____((__packed))sdshdr32{uint32_tlen;/*used*/uint32_talloc;/*不包括标头和nullterminator*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};struct__attribute__((__packed__))sdshdr64{uint64_tlen;/*used*/uint;64_/*excludingtheheaderandnullterminator*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};ssdshdr存储结构sdshdr是header，buf是实际存储用户数据的地方。(buf="data"+"\0");sds有四个不同的标题。没有用sdshdr5，en也不显示。userdata的长度用uint8,uint16,uint32,uint64表示（不包括末尾的\0）alloc用uint8,uint16,uint32,uint64表示整个SDS，除了头部的\0和结束，剩余字节数。标志总是一个字节，低三位表示头部的类型，高五位未使用。为一个SDS实例创建三个接口2.List链表实现，链表节点不直接持有数据，而是通过void*指针间接指向数据。实现位于src/adlist.h和src/adlist.c，内存布局列表在Redis中除了作为一些ValueTypes的底层实现外，在Redis的其他功能实现中也广泛使用as一种数据结构工具。在升在ist的实现中，除了基本的链表定义外，还额外增加了一个：迭代器listIter的定义，以及相关接口的实现。由于链表中的链表节点并不直接持有数据，而是通过值域，以void*指针的形式间接持有，所以数据的生命周期并不完全符合链表及其节点。这为列表的用户提供了相当大的灵活性。例如，多个节点可以持有相同的数据地址。但同时，销毁链表、复制节点和查找匹配项时，链表的使用者需要将相关函数指针赋值给list.dup、list.free、list.match字段。3、dictdict类似于C++标准库中的std::unordered_map。它的实现位于src/dict.h和src/dict.c中。dict中存储的键值对，通过dictEntry结构体间接持有，k通过指针间接持有键，v通过指针间接持有值。注意，如果值为整数值，则直接存储在v字段中，而不是间接持有。同时用next指针指向。当桶索引值发生冲突时，以链式方式解决冲突，指向下一个相同索引的dictEntry结构。dict是一本字典。type字段存储了本字典中使用的各种函数指针，包括hash函数、键值复制函数、Release函数、键比较函数。privdata用于存储用户定义的数据。这样，词典的使用者就可以最大限度地实现自定义词典，通过自定义实现各种功能，并且可以附加私有数据，保证词典有很大的调优空间。为了支持平滑扩展，字典定义了数组字段ht[2]。其用途如下：在正常情况下，字典dict只持有哈希表dicttht的一个实例，即整个字典由一个bucket来实现。随着插入操作的进行，桶中发生冲突的概率会增加。当字典存储的节点数与桶数组长度的比值达到一个阈值（1:1）时，字典为了缓解性能下降，扩容操作需要平滑，即当扩容后，字典会持有dicttht的两个实例，ht[0]指向旧哈希表，ht[1]指向扩容后的新哈希表希腊表。内存布局4.zskiplistZskiplist是Redis实现的一种特殊的跳跃列表。跳表是一种基于线性表的简单搜索结构。它最大的特点是即：实现简单，性能可以接近各种搜索树结构。zskiplist的核心设计要点：头节点不持有任何数据，其level[]的长度为每个节点32，除了持有数据的ele字段外，还有一个字段score，标记了得分节点。节点的顺序由分数决定。跳转列表中的节点按照节点的得分从小到大排列。每个节点都持有一个向后指针，这不在原始跳跃列表中。指针指向紧接在该节点之前的节点。每个节点最多包含32个zskiplistLevel结构。实际数量是在创建节点时根据幂律随机产生的（不超过32个）。每个zskiplistLevel中有两个字段。内存布局5，intset是用来存储有序整数的数据结构，也是底层数据结构中最简单的一种。它的定义和实现在src/intest.h中，src/intset.c中的inset结构中有三个编码值，分别是宏INTSET_ENC_INT16、INTSET_ENC_INT32和INTSET_ENC_INT64。length表示其中存储的整数个数，contents指向存储实际值的连续内存区。内存布局intset中的每个字段，包括contents中存储的值，都是按照hostorder（littleendianbyteorder）存储的。这意味着，如果Redis运行在PPC等大端字节序的机器上，访问的数据会有额外的字节序转换开销。同样，当encoding==INTSET_ENC_INT32时，值以int32_t的形式存储在contents中。每当有一个值元素的值超出了int32_t的取值范围，就必须升级整个intset，即所有的值都需要以int64_t的形式存储。显然，升级的成本非常高。intset中的值是按升序存储的，插入和删除的复杂度是O(n)。查找采用二分法，在复杂度为O(log_2(n))intset的代码实现中，没有保留空间，即每次插入操作都会调用zrealloc接口重新分配内存。每次删除也会调用zrealloc接口来减少占用内存。省了，但是内存操作的时间开销增加了。插图编码方式一旦升级，就不会再降级。总之，intset适合存储如下数据：所有数据都位于一个稳定的取值范围内。比如数据稳定在int16_t或者int32_t的取值范围内，插入删除操作不频繁。可以接受O(lgn)级的搜索开销6.ziplistZiplist是Redis底层数据结构中难度最大的结构。它的设计宗旨是：节省内存，从牙齿上节省内存。设计思路和TLV是一致的，但是为了省内存，还额外做了很多工作。ziplist的内存布局和intset一样：都是连续的内存空间。但区域划分比较复杂。和intset一样，ziplist中的所有值都是小端顺序存储的zlbytes字段的类型是uint32_t，存储的是整个ziplist占用内存的字节数。zltail字段的类型是uint32_t，指的是ziplist中最后一个条目的偏移量。用于快速定位最后一个entry，快速完成pop等操作，zllen字段的类型为uint16_t，指的是整个ziplit的entry个数。这个值只占16位，那么蛋疼来了：如果ziplist中的entry个数小于65535，那么这个字段存储的值就是实际的entry值。如果等于或超过65535，则该字段的值固定为65535，但实际的数字需要逐一遍历得到所有条目。zlend是一个终结符段，它的值全是F，即0xff。ziplist保证条目的第一个字节在任何情况下都不会是255。该条目存储其前一个条目占用的字节数。这个支持ziplist反向遍历。每个entry使用单独的区域存储当前节点的类型：所谓类型，包括当前节点存储的数据是什么（二进制，还是数值），如何编码（如果是数值，数值如何存储，如果是二进制数据，二进制数据的长度），最后才是真正的数据。7.如果说ziplist是整个Redis为了节省内存，而写的最难的数据结构，那么叫quicklist就是在最难的基础上，再加一层。这个结构是Redis在3.2版本之后新加入的，在在3.2版本之前，我们可以说dict是最复杂的底层数据结构，ziplist是最难的底层数据结构。3.2版本之后，这两项记录都被刷新了。这是一种以ziplist为节点的数据结构是的，双端链表结构。宏观上，quicklist是一个链表。微观上，链表中的每个节点都是一个ziplist。它的定义和实现分别在src/quicklist.h和src/quicklist.c中，这里定义了五个结构体：quicklistNode。宏观上，quicklist是一个链表。该结构描述了链表中的节点。它通过zl字段保存底层的ziplist。简单的说，它描述了一个ziplist实例quicklistLZF，Ziplist是一个连续的内存。经过LZ4算法压缩后，可以打包成一个quicklistLZF结构。是否压缩quicklist中的每个ziplist实例是一个可配置项。如果启用该配置项，则quicklistNode.zl字段指向Itisnotaziplistinstance,butacompressedquicklistLZFinstancequicklist。这是双向链表的定义。head和tail分别指向头指针和尾指针。len表示链表中的节点。count指的是整个quicklist中所有ziplists的条目数。fill字段影响ziplist在每个链表节点中占用的最大空间，compress影响是否进一步用LZ4算法压缩每个ziplist以节省内存空间。quicklistIter是一个迭代器quicklistEntry是对ziplist中entry概念的封装。quicklist作为一个封装良好的数据结构，不希望用户感知其内部实现，因此需要重新封装ziplist.entry的概念。quicklist的内存布局如下注：以下是quicklist的更多附加信息：quicklist.fill的值影响ziplist在每个链表节点的长度。当该值为负数时，表示单个ziplist的最大长度受字节数限制。具体来说：-1不超过4kb-2不超过8kb-3不超过16kb-4不超过32kb-5不超过64kb当值为正数时，该表使用条目数来限制单个ziplist的长度。该值是数字。由于该字段只占16位，当ziplist的容量受条目数限制时，最大值为2^15。quicklist.compress的值影响quicklistNode.zl字段指向原始ziplist，或者压缩后的quicklistLZF0表示不压缩，zl字段直接指向ziplist1，表示quicklist链表头尾节点不压缩，以及其他节点的zl字段指向压缩的quicklistLZF2表示quicklist链表的前两个节点，后两个节点不压缩，其余节点的zl字段指向压缩的quicklistLZF等，最大值为2^16quicklistNode.encoding字段，表示该链表的节点持有的ziplist是否压缩过。1表示未压缩，持有原始ziplist，2表示压缩quicklistNode.container字段表示每个链表节点持有的数据类型。默认的实现是ziplist，这个字段对应的值为2。目前Redis没有提供其他的实现。所以实际上这个字段的值一直是2quicklistNode。recompress字段表示当前节点持有的ziplist是否已经解压。如果该字段为1，表示之前已经解压过，下次操作时需要重新解压。quicklist的具体实现代码很长，这里就不贴代码片段了。从内存布局也可以看出，因为每个节点持有的ziplist都有长度上限，所以操作时要考虑的分支很多。想想就心痛。快速列表有其自身的优点和缺点。对于用户来说，它的体验类似于线性数据结构，list是最传统的双链表。节点通过指针来保存数据，而指针字段会消耗大量内存。Ziplist解决了内存消耗的问题。但是引入了一个新的问题：整个ziplist的每次写操作都需要重新分配内存。Quicklist在两者之间取得了平衡。并且用户可以自定义quicklist.fill，根据实际业务情况，凭经验调整参数。8.作为字典结构，zipmapdict有很多优点，扩展性强，支持平滑扩展等，但是对于字典中的key值都是二进制数据，而且长度很小，dict里面放一堆指针会浪费很多内存，所以Redis实现了一个轻量级的字典，就是zipmap。zipmap适合的场合是：key-valuepair量不大，单个key，单个value长度小，key值是二进制数据，不是复合结构，也不是复杂结构。dict支持各种嵌套，字典本身不保存数据，只保存指向数据的指针。但是Zipmap直接保存数据。zipmap的定义和实现在src/zipmap.h和src/zipmap.c这两个文件中。定义和实现都没有定义任何struct结构，因为zipmap的内存布局是一个连续的内存空间。内存布局如下：zipmap的第一个字节存储了zipmap中键值对的个数。如果键值对的个数大于254，那么这个字节的值为固定值254，实际的键值对个数需要遍历得到。zipmap的最后一个字节是固定值0xFF。zipmap中的每一个key-value对称为一个entry，其内存使用情况如上图所示，分为六部分：len_of_key，一个字节或五个字节。它存储密钥的二进制长度。如果长度小于254，则以1字节存储，否则以5字节存储。第一个字节的值固定为0xFE，最后四个A字节以little-endianuint32_t类型存储key的二进制长度。key_data为key数据len_of_val，1字节或5字节，存放value的二进制长度。编码方式同len_of_keylen_of_free，固定值为1字节。存储条目中未使用空间的字节数。图中未使用的空间是空闲的，一般是键值对中的值被替换造成的。比如键值对hello<->word修改为hello<->w后，会有四个字节的空闲空间val_data，也就是值数据free，也就是空闲空间。由于len_of_free的值最多只能是254，所以如果值的变化导致freespace大于254，zipmap会回收内存空间。
