文档章节

浅谈Redis五种数据结构的底层原理

中关村的老男孩
 中关村的老男孩
发布于 06/18 16:00
字数 2269
阅读 5136
收藏 106

概念

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,意为跳跃表,可以看成平衡树映射的数组,其查找的时间复杂度和平衡树基本没有差别,但是实现更为简单,形如下面这样的结构(图来源跳跃表的原理):

感谢阅读至文末,彩蛋奉上

Java学习、面试;文档、视频资源免费获取

© 著作权归作者所有

中关村的老男孩
粉丝 39
博文 58
码字总数 135493
作品 0
海淀
架构师
私信 提问
加载中

评论(9)

不能告诉你我的名字
不能告诉你我的名字
下次面试,上去就是一顿唬
开源中国首席技术官
开源中国首席技术官
感觉唬不住面试官
x
xytest01
唬人是不对的 :)
开源中国首席技术官
开源中国首席技术官
相互唬 没什么对不对的了
枸杞泡茶
(∂ω∂)
d
dieslrae
想问一个问题,在cluster中定义一个list,是不是该list中的所有值都在一个node里面的?
noday
noday
d
dieslrae
那如果我cluster中有3个node,我想建3个list分别在这3个node中能否实现?
noday
noday
就是按算法找出三个能分配到不同node的key就行了
Redis不同数据类型的的数据结构实现

原文:Redis不同数据类型的的数据结构实现 我们知道Redis支持五种数据类型, 分别是字符串、哈希表(map)、列表(list)、集合(set)和有序集合,和Java的集合框架类似,不同数据类型的数据...

杰克.陈
2017/12/19
0
0
redis 5种基本类型实现原理

Redis主要支持的数据类型有5种:String ,Hash ,List ,Set ,和 Sorted Set。 字符串类型 能存储任何形式的字符串,包括二进制数据 一个字符类型键允许存储的最大容量是512M 内部数据结构 ...

Java搬砖工程师
03/15
0
0
Redis压缩列表原理与应用分析

摘要 Redis是一款著名的key-value内存数据库软件,同时也是一款卓越的数据结构服务软件。它支持字符串、列表、哈希表、集合、有序集合五种数据结构类型,同时每种数据结构类型针对不同的应用...

Float_Luuu
2016/07/20
1K
0
redis数据结构之一:链表

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度。redis提供五种数据结构:String、hash、list、set、sorted set。这五大数据类型底层...

mypsf
2016/10/24
171
0
Redis详解(三)------ redis的五大数据类型详细用法

  我们说 Redis 相对于 Memcache 等其他的缓存产品,有一个比较明显的优势就是 Redis 不仅仅支持简单的key-value类型的数据,同时还提供list,set,zset,hash等数据结构的存储。本篇博客我...

ysocean
2018/05/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

php 遇到 No input file specified的解决方法

(一)IIS Noinput file specified 方法一:改PHP.ini中的doc_root行,打开ini文件注释掉此行,然后重启IIS 方法二: 请修改php.ini 找到 ; cgi.force_redirect = 1 去掉前面分号,把后面的1...

chenhongjiang
今天
5
0
MySQL 基础

一、常用命令 在命令行中,配置好环境变量后,通过cmd可以直接进入mysql命令行模式,同时列举几种常用命令 # 进入mysql数据库,密码可以先不写,打完-p后再输入,防止被别人看到mysql -u账...

华山猛男
今天
6
0
简单的博客系统(四)Django请求HTML页面视图信息--基于函数的视图

1. 编写用于查询数据的功能函数 应用目录 下的 views.py 文件通常用于保存响应各种请求的函数或类 from django.shortcuts import renderfrom .models import BlogArticles# Create your ...

ZeroBit
今天
5
0
用脚本将本地照片库批量导入到Day One中

因为目前iCloud 空间已经不足,其中95%都是照片,之前入手了DayOne,且空间没有限制,订阅费一年也不少,再加上DayOne作为一款日记App 也比较有名,功能方面最大的就是地理视图与照片视图,尤...

在山的那边
昨天
21
0
jupyter部署安装

python373 -m ipykernel install --name python373 ipython kernelspec list sc create myjupyterservice binpath="D:\apply\Python373\Scripts\jupyter-notebook --config=V:/my_work/jupyt......

mbzhong
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部