每日一博 | 浅谈 Redis 五种数据结构的底层原理
概念
Redis作为一个开源的用C编写的非关系型数据库,基于优秀的CRUD效率,常用于软件系统的缓存,其本身提供了以下五种数据格式:
-
string:字符串
-
list:列表
-
hash:散列表
-
set:无序集合
-
zset:有序集合
接下来我们就要针对这五种数据结构,来分析其底层的结构
这里选用的版本是redis-5.0.4
,所以可能有很多地方和如今网络上的其他博文不太一致,不同的地方我会在文中指出
string
因为redis使用c语言开发,所以自然没有java和c++的那些字符串类库,在redis中,其自己定义了一种字符串格式,叫做SDS(Simple Dynamic String),即简单动态字符串
这个结构定义在sds.h中:
typedef char *sds;
但是这个sds类型仅作为参数和返回值使用,并不是真正用于操作的类型,真正核心的部分是下面的这些类:
struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; uint8_t alloc; unsigned char flags; char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; uint16_t alloc; unsigned char flags; char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; uint32_t alloc; unsigned char flags; char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; uint64_t alloc; unsigned char flags; char buf[]; };
除掉第一个结构体(已经弃用),sds具体类型的结构可以分为以下部分:
-
len:已使用的长度,即字符串的真实长度
-
alloc:除去标头和终止符('\0')后的长度
-
flags:低3位表示字符串类型,其余5位未使用(我暂时没发现redis在哪里使用过这个属性)
-
buf[]:存储字符数据
这里和老版本做一下对比,因为我手头只有4.x和5.x的版本,它们sds的实现是一致的,但是据其他人说sds之前的版本实现方式不同,有时间我会去下载下来看一下,其将字符串分为以下部分:
-
len:buf中已经占有的长度(表示此字符串的实际长度)
-
free:buf中未使用的缓冲区长度
-
buf[]:实际保存字符串数据的地方
redis同时写重写了大量的与sds类型相关的方法,那redis为什么要这么下功夫呢,有以下4个优点:
-
降低获取字符串长度的时间复杂度到O(1)
-
减少了修改字符串时的内存重分配次数
-
兼容c字符串的同时,提高了一些字符串工具方法的效率
-
二进制安全(数据写入的格式和读取的格式一致)
list
我们查看源文件可以看到有两个list,一个是ziplist,字面意是压缩列表,另一个是quicklist,字面意是快速列表,在redis中直接使用的是quicklist,但是我们先来看ziplist
ziplist
ziplist并不是一个类名,其结构是下面这样的: <zlbytes><zltail><entries><entry>...<entry><zlend>
其中各部分代表的含义如下:
-
zlbytes:4个字节(32bits),表示ziplist占用的总字节数
-
zltail:4个字节(32bits),表示ziplist中最后一个节点在ziplist中的偏移字节数
-
entries:2个字节(16bits),表示ziplist中的元素数
-
entry:长度不定,表示ziplist中的数据
-
zlend:1个字节(8bits),表示结束标记,这个值固定为ff(255)
这些数据均为小端存储,所以可能有些人查看数据的二进制流与其含义对应不上,其实是因为读数据的方式错了
ziplist内部采取数据压缩的方式进行存储,压缩方式就不是重点了,我们仅从宏观来看,ziplist类似一个封装的数组,通过zltail可以方便地进行追加和删除尾部数据、使用entries可以方便地计算长度
但是其依然有数组的缺点,就是当插入和删除数据时会频繁地引起数据移动,所以就引出了quicklist数据类型
quicklist
其核心数据结构如下:
typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* ziplist所有节点的个数 */ unsigned long len; /* quicklistNode节点的个数 */ int fill : 16; /* 单个节点的填充因子 */ unsigned int compress : 16; /* 压缩端结点的深度 */ } quicklist;
我们可以明显地看出,quicklist是一个双向链表的结构,但是内部又涉及了ziplist,我们可以这么说,在宏观上,quicklist是一个双向链表,在微观上,每一个quicklist的节点都是一个ziplist
在redis.conf中,可以使用下面两个参数来进行优化:
-
list-max-ziplist-size:表示每个quicklistNode的字节大小。默认为2,表示8KB
-
list-compress-depth:表示quicklistNode节点是否要压缩。默认为0,表示不压缩
这种存储方式的优点和链表的优点一致,就是插入和删除的效率很高,而链表查询的效率又由ziplist来进行弥补,所以quicklist就成为了list数据结构的首选
hash
hash这种结构在redis的使用时最为常见,在redis中,hash这种结构有两种表示:zipmap和dict
zipmap
zipmap其格式形如下面这样: <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
各部分的含义如下:
-
zmlen:1个字节,表示zipmap的总字节数
-
len:1~5个字节,表示接下来存储的字符串长度
-
free:1个字节,是一个无符号的8位数,表示字符串后面的空闲未使用字节数,由于修改与键对应的值而产生
这其中相邻的两个字符串就分别是键和值,比如在上面的例子中,就表示"foo" => "bar", "hello" => "world"
这样的对应关系
这种方式的缺点也很明显,就是查找的时间复杂度为O(n),所以只能当作一个轻量级的hashmap来使用
dict
这种方式就适于存储大规模的数据,其格式如下:
typedef struct dict { dictType *type;/* 指向自定义类型的指针,可以存储各类型数据 */ void *privdata; /* 私有数据的指针 */ dictht ht[2];/* 两个hash表,一般只有h[0]有效,h1[1]只在rehash的时候才有值 */ long rehashidx; /* -1:没有在rehash的过程中,大于等于0:表示执行rehash到第几步 */ unsigned long iterators; /* 正在遍历的迭代器个数 */ } dict;
如果我们不想更深入的话了解到这种程度就可以了,其中真正存储数据的是dictEntry结构,如下:
typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry;
很明显是一个链表,我们知道这是采用链式结构存储就足够了
这种方式会消耗较多的内存,所以一般数据较少时会采用轻量级的zipmap
set
在redis中,我们可以查看intset.h
文件,这是一个存储整数的集合,其结构如下:
typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents[]; } intset;
其中各字段含义如下:
-
encoding:数据编码格式,表示每个数据元素用几个字节存储(可取的值有2、4,和8)
-
length:元素个数
-
contents:柔性数组,这部分内存单独分配,不包含在intset中
具体的操作我们就不详细展开了,了解集合这种数据结构的应该都很清楚,我们这里说一下,intset有一个数据升级的概念,比方说我们有一个16位整数的set,这时候插入了一个32位整数,所以就导致整个集合都升级为32位整数,但是反过来却不行,这也就是柔性数组的由来
如果集合过大,会采用dict的方式来进行存储
zset
zset,有很多地方也叫做sorted set,是一个键值对的结构,其键被称为member,也就是集合元素(zset依然是set,所以member不能相同),其对应的值被称为score,是一个浮点数,可以理解为优先级,用于排列zset的顺序
其也有两种存储方式,一种是ziplist/zipmap的格式,这种方式我们就不过多介绍了,只需要了解这种格式将数据按照score的顺序排列即可
另一种存储格式是采用了skiplist,意为跳跃表,可以看成平衡树映射的数组,其查找的时间复杂度和平衡树基本没有差别,但是实现更为简单,形如下面这样的结构(图来源跳跃表的原理):
感谢阅读至文末,彩蛋奉上
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
VS Code 的 python 扩展发布,绘图功能更强大
Visual Studio Code 的 python扩展已发布,可以从Marketplace下载Python扩展,或直接从 Visual Studio Code 中的扩展库安装。如果已经安装了Python 扩展,还可以通过重新启动 Visual Studio Code 获得最新的更新。 在这个版本中,带来了一些特性,主要包括 Python 交互式窗口的绘图查看器、带有 pytest 的并行测试以及在终端中的运行选择的内容。 Python 交互式窗口的绘图查看器 主要的特点是对生成的图形进行更好的操作,例如缩放、平移和导出图像,例如Matplotlib 绘图,通过双击绘图或单击“展开图像”按钮来操作: 新版本的绘图查看器,可以平移、放大/缩小、浏览当前会话中的绘图,并将绘图导出为 PDF、SVG 或 PNG 格式。 带有 pytest 的并行测试 在运行测试显示的信息结果中,新版提高了可靠性,通过安装 pytest-xdist 包并将 “-n<number of CPUs>”添加到配置文件中,例如,对于 4 个 CPU,可以在项目文件夹中创建一个 pytest.ini 文件...
- 下一篇
我为 Windows 10 修复了一个 bug
本文讲述了一名开发者为 Windows 计算器应用修复bug 的经历。 据这名开发者(下用 Peter 代称)介绍,他某日在 Reddit 闲逛时,一个位于 Windows 10 子版块下的帖子引起了他的注意。帖子内容如下: 和大家一样,在计算两个日期之间的相隔天数时,Peter 也发现了关于周数的描述明显是错误的,如此大的数值看起来应该是上溢或者下溢之类的问题,要不就是差一错误(off-by-one)等常见的逻辑错误。 本着对这个 bug 的好奇心,再加上Windows 10 计算器是开源项目,Peter 认为解决这个问题应该不会太复杂,所以他希望亲自找到 bug 并进行修复。 他先在自己的电脑上测试看是否能复现,按照帖子的示例,在测试 7.31-12.31 的间隔天数时,计算器返回的结果是正确的 —— “5个月”。接着 Peter 稍微改了一下日期,改成7.31-12.30时,bug 复现了,计算器显示的值为:“5 months, 613566756 weeks, 3 days”,这明显是错误的。 确定了 bug 的存在,Peter 决定从Windows 计算器的 GitHub 仓...
相关文章
文章评论
共有0条评论来说两句吧...