Redis中8种数据结构的底层数据结构源码详解

Redis中8种数据结构的底层数据结构源码详解

redis存储类型

主要提供了5种数据结构：字符串(String)、哈希(hash)、列表(list)、集合(set)、有序集合(short set);

redis底层实现的8种数据结构

SDS simple synamic string：支持自动动态扩容的字节数组 list ：链表 dict ：使用双哈希表实现的, 支持平滑扩容的字典 zskiplist ：附加了后向指针的跳跃表 intset ： 用于存储整数数值集合的自有结构 ziplist ：一种实现上类似于TLV, 但比TLV复杂的, 用于存储任意数据的有序序列的数据结构 quicklist：一种以ziplist作为结点的双链表结构, 实现的非常不错 zipmap ： 一种用于在小规模场合使用的轻量级字典结构

其中5种存储类型与8种数据结构的桥梁, 是redisObject;

Redis中的Key与Value在表层都是一个redisObject实例, 所以该结构有所谓的"类型", 即是ValueType. 对于每一种Value Type类型的redisObject;

其底层至少支持两种不同的底层数据结构来实现. 以应对在不同的应用场景中, Redis的运行效率, 或内存占用等

底层数据结构分析

1、SDS - simple dynamic string

可以在安装目录的src文件夹下看到sds.c和sds.h的源码文件

typedef char *sds;   /* Note: sdshdr5 is never used, we just access the flags byte directly.  * However is here to document the layout of type 5 SDS strings. */ struct __attribute__ ((__packed__)) sdshdr5 {  unsigned char flags; /* 3 lsb of type, and 5 msb of string length */  char buf[]; }; 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[]; };s

sdshdr的存储结构

sdshdr是头部, buf是真实存储用户数据的地方.(buf="数据" + "\0" );sds有四种不同的头部. sdshdr5未 使用，未显示

en分别以uint8, uint16, uint32, uint64表示用户数据的长度(不包括末尾的\0)

alloc分别以uint8, uint16, uint32, uint64表示整个SDS, 除过头部与末尾的\0, 剩余的字节数.

flag始终为一字节, 以低三位标示着头部的类型, 高5位未使用.

创建一个SDS实例的三个接口

2、list

链表实现, 链表结点不直接持有数据, 而是通过void *指针来间接的指向数据. 其实现位于 src/adlist.h与src/adlist.c中,

内存布局

list在Redis除了作为一些Value Type的底层实现外, 还广泛用于Redis的其它功能实现中, 作为一种数据结构工具使用.

在list的实现中, 除了基本的链表定义外, 还额外增加了:迭代器listIter的定义, 与相关接口的实现.

由于list中的链表结点本身并不直接持有数据, 而是通过value字段, 以void *指针的形式间接持有, 所以数据的生命周期并不完全与链表及其结点一致. 这给了list的使用者相当大的灵活性. 比如可以多个结点持有同一份数据的地址. 但与此同时, 在对链表进行销毁, 结点复制以及查找匹配时, 就需要list的使用者将相关的函数指针赋值于list.dup, list.free, list.match字段.

3、dict

dict类似于C++标准库中的std::unordered_map, 其实现位于 src/dict.h 与 src/dict.c中

dict中存储的键值对, 是通过dictEntry这个结构间接持有的, k通过指针间接持有键, v通过指针间接持有值. 注意, 若值是整数值的话, 是直接存储在v字段中的, 而不是间接持有. 同时next指针用于指向, 在bucket索引值冲突时, 以链式方式解决冲突, 指向同索引的下一个dictEntry结构.

dict即为字典. 其中type字段中存储的是本字典使用到的各种函数指针, 包括散列函数, 键与值的复制函数, 释放函数, 以及键的比较函数. privdata是用于存储用户自定义数据. 这样, 字典的使用者可以最大化的自定义字典的实现, 通过自定义各种函数实现, 以及可以附带私有数据, 保证了字典有很大的调优空间.

字典为了支持平滑扩容, 定义了ht[2]这个数组字段. 其用意是这样的:

一般情况下, 字典dict仅持有一个哈希表dictht的实例, 即整个字典由一个bucket实现.

随着插入操作, bucket中出现冲突的概率会越来越大, 当字典中存储的结点数目, 与bucket数组长度的比值达到一个阈值(1:1)时, 字典为了缓解性能下降, 就需要扩容

扩容的操作是平滑的, 即在扩容时, 字典会持有两个dictht的实例, ht[0]指向旧哈希表, ht[1]指向扩容后的新哈希表.

内存布局

4、zskiplist

zskiplist是Redis实现的一种特殊的跳跃表. 跳跃表是一种基于线性表实现简单的搜索结构, 其最大的特点就是: 实现简单, 性能能逼近各种搜索树结构.

zskiplist的核心设计要点:

头结点不持有任何数据, 且其level[]的长度为32

每个结点, 除了持有数据的ele字段, 还有一个字段score, 其标示着结点的得分, 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列.

每个结点持有一个backward指针, 这是原版跳跃表中所没有的. 该指针指向结点的前一个紧邻结点.

每个结点中最多持有32个zskiplistLevel结构. 实际数量在结点创建时, 按幂次定律随机生成(不超过32). 每个zskiplistLevel中有两个字段.

内存布局

5、intset

用于存储在序的整数的数据结构, 也底层数据结构中最简单的一个, 其定义与实现在src/intest.h与src/intset.c中

inset结构中的encoding的取值有三个, 分别是宏INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64. length代表其中存储的整数的个数, contents指向实际存储数值的连续内存区域

内存布局

intset中各字段, 包括contents中存储的数值, 都是以主机序(小端字节序)存储的. 这意味着Redis若运行在PPC这样的大端字节序的机器上时, 存取数据都会有额外的字节序转换开销

当encoding == INTSET_ENC_INT16时, contents中以int16_t的形式存储着数值. 类似的, 当encoding == INTSET_ENC_INT32时, contents中以int32_t的形式存储着数值.

但凡有一个数值元素的值超过了int32_t的取值范围, 整个intset都要进行升级, 即所有的数值都需要以int64_t的形式存储. 显然升级的开销是很大的.

intset中的数值是以升序排列存储的, 插入与删除的复杂度均为O(n). 查找使用二分法, 复杂度为O(log_2(n))

intset的代码实现中, 不预留空间, 即每一次插入操作都会调用zrealloc接口重新分配内存. 每一次删除也会调用zrealloc接口缩减占用的内存. 省是省了, 但内存操作的时间开销上升了.

intset的编码方式一经升级, 不会再降级.

总之, intset适合于如下数据的存储:

所有数据都位于一个稳定的取值范围中. 比如均位于int16_t或int32_t的取值范围中

数据稳定, 插入删除操作不频繁. 能接受O(lgn)级别的查找开销

6、ziplist

ziplist是Redis底层数据结构中, 最苟的一个结构. 它的设计宗旨就是: 省内存, 从牙缝里省内存. 设计思路和TLV一致, 但为了从牙缝里节省内存, 做了很多额外工作.

ziplist的内存布局与intset一样: 就是一块连续的内存空间. 但区域划分比较复杂

和intset一样, ziplist中的所有值都是以小端序存储的

zlbytes字段的类型是uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数

zltail字段的类型是uint32_t, 它指的是ziplist中最后一个entry的偏移量. 用于快速定位最后一个entry, 以快速完成pop等操作

zllen字段的类型是uint16_t, 它指的是整个ziplit中entry的数量. 这个值只占16位, 所以蛋疼的地方就来了: 如果ziplist中entry的数目小于65535, 那么该字段中存储的就是实际entry的值. 若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到.

zlend是一个终止字节, 其值为全F, 即0xff. ziplist保证任何情况下, 一个entry的首字节都不会是255

在画图展示entry的内存布局之前, 先讲一下entry中都存储了哪些信息:

每个entry中存储了它前一个entry所占用的字节数. 这样支持ziplist反向遍历.

每个entry用单独的一块区域, 存储着当前结点的类型: 所谓的类型, 包括当前结点存储的数据是什么(二进制, 还是数值), 如何编码(如果是数值, 数值如何存储, 如果是二进制数据, 二进制数据的长度)最后就是真实的数据了

7、quicklist

如果说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字段指向的就不是一个ziplist实例, 而是一个压缩后的quicklistLZF实例

quicklistIter是一个迭代器

quicklistEntry是对ziplist中的entry概念的封装. quicklist作为一个封装良好的数据结构, 不希望使用者感知到其内部的实现, 所以需要把ziplist.entry的概念重新包装一下.

quicklist的内存布局图如下所示:

下面是有关quicklist的更多额外信息:

quicklist.fill的值影响着每个链表结点中, ziplist的长度.

当数值为负数时, 代表以字节数限制单个ziplist的最大长度. 具体为:

-1 不超过4kb

-2 不超过 8kb

-3 不超过 16kb

-4 不超过 32kb

-5 不超过 64kb

当数值为正数时, 代表以entry数目限制单个ziplist的长度. 值即为数目. 由于该字段仅占16位, 所以以entry数目限制ziplist的容量时, 最大值为2^15个

0 表示不压缩, zl字段直接指向ziplist

1 表示quicklist的链表头尾结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF

2 表示quicklist的链表头两个, 与末两个结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF

以此类推, 最大值为2^16

quicklistNode.encoding字段, 以指示本链表结点所持有的ziplist是否经过了压缩. 1代表未压缩, 持有的是原生的ziplist, 2代表压缩过

quicklistNode.container字段指示的是每个链表结点所持有的数据类型是什么. 默认的实现是ziplist, 对应的该字段的值是2, 目前Redis没有提供其它实现. 所以实际上, 该字段的值恒为2

quicklist的具体实现代码篇幅很长, 这里就不贴代码片断了, 从内存布局上也能看出来, 由于每个结点持有的ziplist是有上限长度的, 所以在与操作时要考虑的分支情况比较多. 想想都蛋疼.

quicklist有自己的优点, 也有缺点, 对于使用者来说, 其使用体验类似于线性数据结构, list作为最传统的双链表, 结点通过指针持有数据, 指针字段会耗费大量内存. ziplist解决了耗费内存这个问题. 但引入了新的问题: 每次写操作整个ziplist的内存都需要重分配. quicklist在两者之间做了一个平衡. 并且使用者可以通过自定义quicklist.fill, 根据实际业务情况, 经验主义调参.

8、zipmap

dict作为字典结构, 优点很多, 扩展性强悍, 支持平滑扩容等等, 但对于字典中的键值均为二进制数据, 且长度都很小时, dict的中的一坨指针会浪费不少内存, 因此Redis又实现了一个轻量级的字典, 即为zipmap.

zipmap适合使用的场合是:

键值对量不大, 单个键, 单个值长度小

键值均是二进制数据, 而不是复合结构或复杂结构. dict支持各种嵌套, 字典本身并不持有数据, 而仅持有数据的指针. 但zipmap是直接持有数据的.

zipmap的定义与实现在src/zipmap.h与src/zipmap.c两个文件中, 其定义与实现均未定义任何struct结构体, 因为zipmap的内存布局就是一块连续的内存空间. 其内存布局如下所示:

zipmap起始的第一个字节存储的是zipmap中键值对的个数. 如果键值对的个数大于254的话, 那么这个字节的值就是固定值254, 真实的键值对个数需要遍历才能获得.

zipmap的最后一个字节是固定值0xFF

zipmap中的每一个键值对, 称为一个entry, 其内存占用如上图, 分别六部分:

len_of_key, 一字节或五字节. 存储的是键的二进制长度. 如果长度小于254, 则用1字节存储, 否则用五个字节存储, 第一个字节的值固定为0xFE, 后四个字节以小端序uint32_t类型存储着键的二进制长度.

key_data为键的数据

len_of_val, 一字节或五字节, 存储的是值的二进制长度. 编码方式同len_of_key

len_of_free, 固定值1字节, 存储的是entry中未使用的空间的字节数. 未使用的空间即为图中的free, 它一般是由于键值对中的值被替换发生的. 比如, 键值对hello <-> word被修改为hello <-> w后, 就空了四个字节的闲置空间

val_data, 为值的数据

free, 为闲置空间. 由于len_of_free的值最大只能是254, 所以如果值的变更导致闲置空间大于254的话, zipmap就会回收内存空间.

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。