专栏首页服务端思维Redis中string、list的底层数据结构原理

Redis中string、list的底层数据结构原理

Redis 的五大数据结构使用简介

Redis 有一个比较突出的特点就是数据结构更丰富, 「string、hash、list、set、zset、Redis5.0 新数据结构-stream」

这部分的使用相对简单,大家可以参考 Redis 官网系统学习并使用,接下来我们重点来看看 Redis 数据结构的底层设计

Redis 的命令不区分大小写,但是 key 严格区分大小写!!!

“老师,这部分就过了?”

“”我相信你们,最多花一个小时就看完了所有API了,加油!”

Redis-字符串对象(string)

我们还是通过上一节课的那个例子看一下string类型的底层结构是什么,通过object encoding key 命令来查看具体的存储结构

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

“老师,embstr 是什么意思?三种实现方式有什么区别呢?”

“不急,我们接下来就开始详细讲解”

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

 REDIS_ENCODING_INT(long 类型的整数)
 REDIS_ENCODING_EMBSTR embstr (编码的简单动态字符串)
 REDIS_ENCODING_RAW (简单动态字符串)

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

int

我们根据上一节知道每个hashtable中的值作为一个指针会指向redisObject对象,该对象有一个属性是ptr(指针类型),一个指针比如在64位系统中就是用8个字节来存储,这个存储大小正好是一个长整型的存储所以为了节省内存空间,如果一个字符串内容可转为 long,那么该字符串会被转化为 long 类型,对象 ptr 指向该 long,并将 encoding 设置为 int,这样就不需要重新开辟空间,算是长整形的一个优化

raw

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

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 ,编码的字符串对象能够更好地利用缓存带来的优势

Redis-列表对象(list)

3.2 版本前采用ziplist和linkedlist结构

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

3.2版本之前采用两种数据结构作为底层实现:

  • 压缩列表ziplist
  • 双向链表linkedlist

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

ziplist(为节省内存而设计)

下图是ziplist的数据结构

其中黄色区域用来表示列表的特征,绿色区域就是列表中具体的元素了,ziplist是使用连续的内存块存储的

  • zlbytes:表示整个ziplist占用的字节数,一般用于内存重分配或者计算列表尾端
  • zltail:到达列表最后一个节点的偏移量,方便直接找到尾部节点
  • zllen:列表节点的数量

注意zllen用16个比特位存储,也就是说起长度最大表示65535,所以如果长度超过这个值,只能够通过节点遍历来确定列表元素数量

  • entryX:列表中的各节点
  • zlend:作用就是用来标记列表尾端,占用一个字节

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

  typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;    // prevrawlen是前一个节点的长度,prevrawlensize是指prevrawlen的大小,有1字节和5字节两种
    unsigned int lensize, len;  // len为当前节点长度 lensize为编码len所需的字节大小
    unsigned int headersize;    // 当前节点的header大小
    unsigned char encoding; // 节点的编码方式
    unsigned char *p;   // 指向节点的指针
} zlentry;
  
void zipEntry(unsigned char *p, zlentry *e) {   // 根据节点指针返回一个enrty
    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);    // 获取prevlen的值和长度
    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);  // 获取当前节点的编码方式、长度等
    e->headersize = e->prevrawlensize + e->lensize; // 头大小
    e->p = p;
}

完整的zlentry由以下3各部分组成:

  • prevrawlen: 记录前一个节点所占内存的字节数,方便查找上一个元素地址

根据图中可以看到prevrawlen是变长编码的,如果上一个节点长度小于254个字节,则只是用一个字节存储prevrawlen,如果大于等于254,那么第一个字节用254标记,后面四个字节表示上一个节点长度

  • lensize, len:记录当前节点所占内存字节数,以及内容的存储类型,方便解析,其具体对应关系可参考上图文本框中内容
  • content:保存了当前节点的值。

知道了ziplist原理后,我们来看一下在压缩列表转化成双向链表的条件

  • 如果添加的字符串元素长度超过默认值64
  • zip包含的节点数超过默认值512 这两个条件是可以修改的,在redis.conf中
list-max-ziplist-value 64 
list-max-ziplist-entries 512  
复制代码

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

3.2版本之后升级为 quicklist(双向链表)

quicklist是3.2版本之后引入的。

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

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

quickList

根据图中可以看到每一个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。
list-max0ziplist-size -2

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

我们知道list比较适合于用在热点数据中,一般最容易被访问的是列表两端的数据,中间的访问频率很低,如果符合这个场景,list还有一个配置,可以对中间节点进行压缩

  • 0: 是个特殊值,表示都不压缩。这是Redis的默认值。
  • 1: 表示quicklist两端各有1个节点不压缩,中间的节点压缩。
  • 2: 表示quicklist两端各有2个节点不压缩,中间的节点压缩。
  • 以此类推
list-compress-depth 0

总结

本节内容主要讲解了Redis中string、list对象底层结构,string通过int、raw、embstr三种结构来表示,而list在3.2版本之后采用quicklist的数据结构,我们可以看到在节省内存、提高查询效率方面都体现了优秀的设计,这些都可以作为我们日后设计及开发中的宝贵经验!

本文分享自微信公众号 - 服务端思维(gh_c3775931ac9d)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 我们分析了GitHub上5.46 亿条日志,发现中国开源虽然贡献大但还有这些不足...

    全球最大代码托管平台 GitHub 在 2019 年发布的年度报告中显示, GitHub 上目前已有超过 4000 万开发人员、将近 300 万个组织帐户。其中...

    用户2781897
  • 探究导致 MySQL 慢查询的因素:从硬件、网络到数据库的深度剖析

    不管是开发同学还是DBA,想必大家都遇到慢查询(select,update,insert,delete 语句慢),影响业务稳定性。这里说的慢,有两个含义一是比正...

    用户2781897
  • 微服务中使用 OpenJ9 JVM 内存占用降60%(相对HotSpot)

    微服务化后,应用数量可能高一个数量级。一般企业,以前三五个应用能支撑业务,微服务化之后应用数量可能多达几十个。每个微服务往往独立部署,内存的消耗自然也高居不下,...

    用户2781897
  • 机器学习数据采集入门经验分享

    在新的一年里,很多人都在思考如何利用机器学习(ML)算法来提高产品或服务的质量。 PredictionIO公司与许多公司合作,部署他们的第一个ML系统和大数据基...

    机器学习AI算法工程
  • 电气技术中的文字符号和项目代号

    一个电气系统或一种电气设备通常都是由各种基本件、部件、组件等组成,为了在电气图上或其他技术文件中表示这些基本件、部件、组件,除了采用各种图形符号外,还须标注一些...

    机器人网
  • javascript:二叉搜索树 实现

    二叉搜索树:顾名思义,树上每个节点最多只有二根分叉;而且左分叉节点的值 < 右分叉节点的值 。 特点:插入节点、找最大/最小节点、节点值排序 非常方便 二叉搜索...

    菩提树下的杨过
  • Java基础专题(三):字符串

    从概念上来讲,Java字符串就是Unicode字符序列。例如,"Java\u2122" 由5个Unicode字符J,a,v,a,和 ™。Java没有内置的字符串...

    山禾说
  • SAP CRM中间件BDOC内容搜索工具

    One of my colleague asked me whether there is a standard tool which enables us t...

    Jerry Wang
  • uikiller使用手册(一)

    uikiller是使用名命规则来控制UI节点、组件和触摸事件,减少UI相关的代码与编辑器设置,实现原理是提前对UI树的遍历。

    张晓衡
  • 数据结构图文解析之:二叉堆详解及C++模板实现

    Tencent JCoder

扫码关注云+社区

领取腾讯云代金券