文档章节

Redis压缩列表原理与应用分析

别打我会飞
 别打我会飞
发布于 06/29 21:09
字数 2228
阅读 2671
收藏 38

 

摘要

Redis是一款著名的key-value内存数据库软件,同时也是一款卓越的数据结构服务软件。它支持字符串、列表、哈希表、集合、有序集合五种数据结构类型,同时每种数据结构类型针对不同的应用场景又支持不同的编码方式。这篇文章主要介绍压缩列表编码,在理解压缩列表编码原理的基础上介绍Redis对压缩列表的应用,最后再对Redis压缩列表应用进行分析。

Redis压缩列表原理与应用

压缩列表是一种数据结构,这种数据结构的功能是将一系列数据与其编码信息存储在一块连续的内存区域,这块内存物理上是连续的,逻辑上被分为多个组成部分,其目的是在一定可控的时间复杂读条件下尽可能的减少不必要的内存开销,从而达到节省内存的效果,这么介绍有点玄乎,我们先一起看看它的实现原理吧,Redis3.2版本中,作者对压缩列表的实现在ziplist.h和ziplist.c中。

压缩列表原理

我认为将数据按照一定规则存储在内存中可以用“编码”这个词描述,因此下面会常用“编码”这个词。

总体编码

上面说到压缩列表是一块连续的内存区域,这块内存区域布编码示意图大致如下:

Redis压缩列表内存编码示意图

常态的压缩列表内存编码如上图所示,整个内存块区域内分为五个部分,下面分别介绍着五个部分:

zlbytes:存储一个无符号整数,固定四个字节长度,用于存储压缩列表所占用的字节,当重新分配内存的时候使用,不需要遍历整个列表来计算内存大小。

zltail:存储一个无符号整数,固定四个字节长度,代表指向列表尾部的偏移量,偏移量是指压缩列表的起始位置到指定列表节点的起始位置的距离。

zllen:压缩列表包含的节点个数,固定两个字节长度,源码中指出当节点个数大于2^16-2个数的时候,该值将无效,此时需要遍历列表来计算列表节点的个数。

entryX:列表节点区域,长度不定,由列表节点紧挨着组成。

zlend:一字节长度固定值为255,用于表示列表结束。

列表元素编码

上面介绍了压缩列表的总体内存布局,对于初entryX区域以外的四个区域的长度都是固定的,下面再看看entryX区域的编码情况。

每个列表节点由三部分组成:

压缩列表节点编码示意图

每个压缩列表节点区域头部包含两部分,一部分叫做previous length,另一部分叫encoding,最后是主体内容,叫做content,下面分别介绍他们:

previous length

用于存储上一个节点的长度,因此压缩列表可以从尾部向头部遍历,即当前节点位置减去上一个节点的长度即得到上一个节点的起始位置。previous length的长度可能是1个字节或者是5个字节,如果上一个节点的长度小于254,则该节点只需要一个字节就可以表示前一个节点的长度了,如果前一个节点的长度大于等于254,则previous length的第一个字节为254,后面用四个字节表示当前节点前一个节点的长度。这么做很有效地减少了内存的浪费。

encoding

节点的encoding保存的是节点的content的内容类型以及长度,encoding类型一共有两种,一种字节数组一种是整数,encoding区域长度为1字节、2字节或者5字节长。Redis作者巧妙的利用了前两个字节来表示content存储的内容类型和encoding区域的长度,我们先看看字节数组类型的encoding内容:

content为字节数组的encoding内容

再看看整数编码类型的encoding内容:

content为整数的encoding内容

content

content区域用于保存节点的内容,节点内容类型和长度由encoding决定,上面可以看出目前content的内容类型有整数类型和字节数组类型,且某些条件下content的长度可能为0。

相信到这里,我们都明白了压缩列表的原理,压缩列表并不是对数据利用某种算法进行压缩,而是将数据按照一定规则编码在一块连续的内存区域,目的是节省内存。下面我们看看压缩列表在Redis中的应用领域。

Java架构/分布式:705127209(大牛交流群)没有开发经验勿加!

Redis中压缩列表的应用

Redis中,不同的数据类型广泛地应用了压缩列表编码,整理如下表:

Redis中数据结构类型与压缩列表的应用

上表总结了压缩列表编码在Redis不同的数据类型中的应用,Redis一共支持五种数据结构类型,其中有三种数据结构在一定条件下会应用压缩列表,至于什么条件后面会分析,值得一提的是Redis当前支持的GEO(地理位置)对压缩列表也有应用,具体此处不做讨论。

Redis压缩列表应用分析

上面部分介绍了Redis压缩列表的原理与应用,下面简单分析一下,主要从通过试图回答一些问题来分析:Redis为什么使用压缩列表?使用压缩列表的好处是什么?使用压缩列表的好处还有什么?压缩列表的应用对与我们使用内存有没有什么启发?

Redis对于每种数据结构、无论是列表、哈希表还是有序集合,在决定是否应用压缩列表作为当前数据结构类型的底层编码的时候都会依赖一个开关和一个阈值,开关用来决定我们是否要启用压缩列表编码,阈值总的来说通常指当前结构存储的key数量有没有达到一个数值(条件),或者是value值长度有没有达到一定的长度(条件)。任何策略都有其应用场景,不同场景应用不同策略。为什么当前结构存储的数据条目达到一定数值使用压缩列表就不好?压缩列表的新增、删除的操作平均时间复杂度为O(N),随着N的增大,时间必然会增加,他不像哈希表可以以O(1)的时间复杂度找到存取位置,然而在一定N内的时间复杂度我们可以容忍。然而压缩列表利用巧妙的编码技术除了存储内容尽可能的减少不必要的内存开销,将数据存储于连续的内存区域,这对于Redis本身来说是有意义的,因为Redis是一款内存数据库软件,想办法尽可能减少内存的开销是Redis设计者一定要考虑的事情。

另外,经过仔细琢磨,我认为使用压缩列表的好处除了节约内存之外,还有减少内存碎片的作用,我把这种行为叫做"合并存储",也就是将很多小的数据块存储在一个比较大的内存区域,试想想,如果我们将要存储的数据都是很小的条目,我们为每一个数据条目都单独的申请内存,结果是这些条目将有可能分散在内存的每一个角落,最终导致碎片增加,这是一件令人头疼的事情。

总结

这篇文章在介绍Redis压缩列表原理与应用的基础之上对Redis压缩列表的应用进行分析,分析部分主要掺杂着个人的理解与认知,如果有不同观点或者补充观点,欢迎留言讨论。

© 著作权归作者所有

别打我会飞
粉丝 99
博文 185
码字总数 438876
作品 0
朝阳
架构师
私信 提问
加载中

评论(3)

HL_L
HL_L
如果hash里放入的feild很多,查询时间复杂度还是O1吗
Avior
Avior
图片全都看不到呢。。。
别打我会飞
别打我会飞 博主
你网速问题,刷新就行了
Redis压缩列表原理与应用分析

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

Float_Luuu
2016/07/20
1K
0
比MySQL快60倍 redis从入门到精通视频教程

Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。 学习视频下载地址:https://pan.baidu.com/s/17NO3pG9hRL-RtU0bwa...

自学号
2018/06/02
0
0
Redis为何这么快——数据存储角度

本文内容思维导图如下: 一、简介和应用 Redis是一个由ANSI C语言编写,性能优秀、支持网络、可持久化的K-K内存数据库,并提供多种语言的API。它常用的类型主要是 String、List、Hash、Set、...

Java干货分享
2018/10/09
0
0
Redis详解(五)------ redis的五大数据类型实现原理

  前面两篇博客,第一篇介绍了五大数据类型的基本用法,第二篇介绍了Redis底层的六种数据结构。在Redis中,并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个...

ysocean
2018/06/05
0
0
redis数据结构的底层实现(下)

上两篇我们分享了演示数据,动态字符串和链表的底层实现,现在,我们分享一下字典,跳跃表和压缩列表的具体实现: 4、字典 字典又称为符号表或者关联数组、或映射(map),是一种用于保存键值...

从梦流风
2018/06/04
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 也比较有名,功能方面最大的就是地理视图与照片视图,尤...

在山的那边
昨天
19
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

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部