Redis极致设计-五大数据结构的底层结构原理

　　一、字符串对象（string）

　　上一篇文章最后能看到底层的哈希表元素会指向一个redisObject对象，通过object encoding key 命令可以看到具体的存储结构，string 类型查看如下：

　　上图可以看到不同的字符串其内部的结构不一样，一个是embstr、另外一个是raw；

　　Redis为了将内存的使用率做到极致，针对字符串对象，提供了三种数据结构

　　接下来我们看一下具体区别

　　1. int

　　我们根据上一节知道每个hashtable中的值作为一个指针会指向redisObject对象，下图是该对象的数据结构

　　该对象有一个属性是ptr（指针类型），一个指针比如在64位系统中就是用8个字节来存储，这个存储大小正好是一个长整型的存储，所以为了节省内存空间，如果一个字符串内容可转为 long，那么该字符串会被转化为 long 类型，对象 ptr直接存储该值，并将 encoding 设置为 int，这样就不需要重新开辟空间，算是长整形的一个优化。

　　2. raw

　　如果字符串对象保存的是一个字符串值，并且这个字符串的长度大于 32 字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为 raw。

　　3. embstr

　　如果字符串对象保存的是一个字符串值，并且这个字符串的长度小于等于 44 字节，那么字符串对象将使用 embstr 编码的方式来保存这个字符串。 3.2版本之后是44个字节，之前是39个字节，这也是因为sds结构的版本变化所导致的。

　　embstr类型是如何存放字符串的【重点】

　　我们知道一般cpu从内存中读取数据会先读取到 cache line（缓存行）， 一个缓存行基本占64个字节，其中redisObject最少占16个字节（根据属性的类型计算得出），所以如果要读取一个 redisObject，会发现只读取了16个字节，剩下的48个字节的空间相当于浪费，所以为了提高性能（主要减少了内存读取的次数），所以在RedisObject空间后又开辟48个字节的连续空间，将ptr指向的值存入其中，注意此处存入的是字符串类型，48个字节对应的是sdshdr8存储结构。而 sdshdr8 在不存入数据的情况下，最少要 4 个字节（其中一个字节是字符串尾部的'\0'）,那么还剩余 44 个字节，所以如果在 44 个字节以内字符串就可以放在缓存行里面，从而减少了内存I/O次数

　　embstr 编码方式的优点：embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次。raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构，而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间， 空间中依次包含 redisObject 和 sdshdr 两个结构释放 embstr 编码的字符串对象只需要调用一次内存释放函数，而释放 raw 编码的字符串对象需要调用两次内存释放函数。因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起 raw ，编码的字符串对象能够更好地利用缓存带来的优势。

　　二、列表对象（list）

　　1. Redis3.2 版本前采用ziplist和linkedlist结构

　　list 是一个有序（按加入的时序排序）的数据结构，一般有序我们会采用数组或者是双向链表，其中双向链表由于有前后指针实际上会很浪费内存。

　　3.2版本之前采用两种数据结构作为底层实现：压缩列表ziplist双向链表linkedlist

　　压缩列表相对于双向链表更节省内存，所以在创建列表时，会先考虑压缩列表，并在一定条件下才转化为双向链表，在说明转化条件之前，我们先了解一下什么是压缩列表。

　　（1）压缩列表（ziplist）（为节省内存而设计）

　　下图是ziplist的数据结构

　　

　　其中黄色区域用来表示列表的特征，绿色区域就是列表中具体的元素了，ziplist是使用连续的内存块存储的zlbytes：表示整个ziplist占用的字节数，一般用于内存重分配或者计算列表尾端zltail：到达列表最后一个节点的偏移量，方便直接找到尾部节点zllen：列表节点的数量 注意zllen用16个比特位存储，也就是说起长度最大表示65535，所以如果长度超过这个值，只能够通过节点遍历来确定列表元素数量entryX：列表中的各节点zlend：作用就是用来标记列表尾端，占用一个字节

　　接下来重点看一下列表中每个节点是如何存储的

　　完整的zlentry由以下3各部分组成：prevrawlen: 记录前一个节点所占内存的字节数，方便查找上一个元素地址 根据图中可以看到prevrawlen是变长编码的，如果上一个节点长度小于254个字节，则只是用一个字节存储prevrawlen，如果大于等于254，那么第一个字节用254标记，后面四个字节表示上一个节点长度lensize, len：记录当前节点所占内存字节数，以及内容的存储类型，方便解析，其具体对应关系可参考上图文本框中内容content：保存了当前节点的值。

　　知道了ziplist原理后，我们来看一下在压缩列表转化成双向链表的条件：如果添加的字符串元素长度超过默认值64zip包含的节点数超过默认值512 这两个条件是可以修改的，在redis.conf中

　　（2）压缩列表（ziplist） 的缺点

　　ziplist 最大的确定就是连锁更新问题

　　因为在 ziplist 中，每个 zlentry 都存储着前一个节点所占的字节数，而这个数值又是变长编码的。假设存在一个压缩列表，其包含 e1、e2、e3、e4.....，e1 节点的大小为 253 字节，那么 e2.prevrawlen 的大小为 1 字节，如果此时在 e2 与 e1 之间插入了一个新节点 e，e 编码后的整体长度（包含 e1 的长度）为 254 字节，此时 e2.prevrawlen 就需要扩充为 5 字节；如果 e2 的整体长度变化又引起了 e3.prevrawlen 的存储长度变化，那么 e3 也需要扩.......如此递归直到表尾节点或者某一个节点的 prevrawlen 本身长度可以容纳前一个节点的变化。其中每一次扩充都需要进行空间再分配操作。删除节点亦是如此，只要引起了操作节点之后的节点的 prevrawlen 的变化，都可能引起连锁更新，引发内存 realloc。

　　连锁更新在最坏情况下需要进行 N 次空间再分配，而每次空间再分配的最坏时间复杂度为 O(N)，因此连锁更新的总体时间复杂度是 O(N^2)。

　　基于上述来看ziplist的缺点大于优点，所以*3.2版本之后采用了另外一个数据结构为quicklist

　　2. Redis3.2版本之后升级为 quicklist(双向链表)

　　quicklist是3.2版本之后引入的。

　　根据上文谈到，ziplist会引入频繁的内存申请和释放，而linkedlist由于指针也会造成内存的浪费，而且每个节点是单独存在的，会造成很多内存碎片，所以结合两个结构的特点，设计了quickList。

　　quickList 是一个 ziplist 组成的双向链表。每个节点使用 ziplist 来保存数据。本质上来说，quicklist 里面保存着一个一个小的 ziplist。结构如下：

　　根据图中可以看到每一个ziplist都是一个很小的集合，ziplist太短，内存碎片越多，如果太长，则分配大块连续内存空间的难度就越大，这个范围也是可以配置的-5: 每个quicklist节点上的ziplist大小不能超过64 Kb。-4: 每个quicklist节点上的ziplist大小不能超过32 Kb。-3: 每个quicklist节点上的ziplist大小不能超过16 Kb。-2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（默认值）-1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

　　这个设置的值是可以通过配置文件看到，默认8kb最好（-2对应的就是8kb，可以参考下图中的注释）

　　我们知道list比较适合于用在热点数据中，一般最容易被访问的是列表两端的数据，中间的访问频率很低，如果符合这个场景，list还有一个配置，可以对中间节点进行压缩0: 是个特殊值，表示都不压缩。这是Redis的默认值。1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。以此类推

　　三、哈希对象（hash）

　　hash的底层存储有两种数据结构，一种是ziplist，另外一种是hashtable，这两种数据结构我们之前都有讲解，ziplist就是上文提到的结构，hashtable之前讲解的redis结构，hash对象只有同时满足以下条件，才会采用ziplist编码：hash对象保存的键和值字符串长度都小于64字节hash对象保存的键值对数量小于512

　　ziplist存储的结构如下

　　上图中可以看到，当数据量比较小的时候，我们会将所有的key及value都当成一个元素，顺序的存入到ziplist中，构成有序。

　　hashtable存储的结构如下：字符串的set key value 和 hash 的区别是什么1. 过期时间，hash没有过期时间2. set不断的加值有一个问题，dict中有一个属性是dictht ht[2]，主要是> 扩容用的，如果不断的加key，则整体redis内存就需要扩容，扩容就需要基于原有内存增加一倍，内存消耗很大

　　四、集合对象（set）

　　set是一个无序的、自动去重的集合数据类型，Set底层用两种数据结构存储，一个是hashtable，一个是inset。

　　其中hashtable的key为set中元素的值，而value为null

　　inset为可以理解为数组，使用inset数据结构需要满足下述两个条件：元素个数不少于默认值512

　　元素可以用整型表示

　　intset的底层结构

　　

　　查询方式一般采用二分查找法，实际查询复杂度也就在log(n)

　　五、有序集合对象（zset）

　　zset为有序（有限score排序，score相同则元素字典序），自动去重的集合数据类型，其底层实现为 字典（dict） + 跳表（skiplist），当数据比较少的时候用ziplist编码结构存储。

　　同时满足以下两个条件采用ziplist存储：有序集合保存的元素数量小于默认值128个有序集合保存的所有元素的长度小于默认值64字节

　　1. ziplist存储方式

　　当ziplist作为zset的底层存储结构时候，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值

　　2. 字典（dict） + 跳表（skiplist）的存储方式

　　zset底层的存储结构包括ziplist或skiplist，在同时满足上说的两个条件时使用ziplist，其他时候使用skiplist

　　（1）跳表的数据结构

　　首先我们理解一下什么是跳表

　　上图可以看到通过分等级，从最高等级向低等级查询，效率提高，其时间复杂度为logn（类似于二分查找）

　　dict+skiplist的最终的存储结构如下：

　　基于上图我们看一下skiplist几个关键对象的数据结构，方便大家理解

　　（2）skiplist中的关键结构——zset

　　可以看到一个是dict结构，主要key是其集合元素，而value就是对应分值，而zkiplist作为跳跃表，按照分值排序，方便定位成员

　　（3）skiplist中的关键结构——zskiplist

　　（4）skiplist中的关键结构——zskiplistNode

　　zskiplistNode中的robj指针指向具体元素，注意这个指针和dict中key指针指向同一个元素，其中backward后腿指针便于回溯

　　六、总结

　　本节内容主要讲解了Redis中string、list、hash、set、zse对象底层结构，string通过int、raw、embstr三种结构来表示，而list在3.2版本之后采用quicklist的数据结构，hash底层采用两种，分别是ziplist和hashtable，set底层也分别采用两种hashtable和inset，其中inset也可以理解为数组，zset底层分别是ziplist和dict+skiplist。

　　我们可以看到在节省内存、提高查询效率方面都体现了优秀的设计，这些都可以作为我们日后设计及开发中的宝贵经验。