位置: IT常识 - 正文

【Redis】关于Redis数据结构简单动态字符串(SDS)的一些杂记(redis相关)

编辑:rootadmin
【Redis】关于Redis数据结构简单动态字符串(SDS)的一些杂记 【Redis】关于Redis数据结构“简单动态字符串(SDS)”的一些杂记

推荐整理分享【Redis】关于Redis数据结构简单动态字符串(SDS)的一些杂记(redis相关),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:redis相关知识,redis相关知识,redis的nx,redis相关,redis相关问题,redis相关,redis相关知识,redis相关问题,内容如对您有帮助,希望把文章链接给更多的朋友!

推荐几篇关于SDS数据结构讲解较为详细的文章:

一、简单动态字符串 — Redis 设计与实现 (redisbook.readthedocs.io)

二、深入理解Redis之简单动态字符串 - itbsl - 博客园 (cnblogs.com)

三、Redis内部数据结构详解(2)——sds - 铁蕾的个人博客 (zhangtielei.com)

四、简单动态字符串 — Redis 设计与实现 (redisbook.readthedocs.io)

一、SDS的结构与实现

在前面的内容中, 我们一直将 sds 作为一种抽象数据结构来说明, 实际上, 它的实现由以下两部分组成:

typedef char *sds;struct sdshdr { // buf 已占用长度 int len; // buf 剩余可用长度 int free; // 实际保存字符串数据的地方 char buf[];};

其中,类型 sds 是 char * 的别名(alias),而结构 sdshdr 则保存了 len 、 free 和 buf 三个属性。

作为例子,以下是新创建的,同样保存 hello world 字符串的 sdshdr 结构:

struct sdshdr { len = 11; free = 0; buf = "hello world\0"; // buf 的实际长度为 len + 1};

通过 len 属性, sdshdr 可以实现复杂度为 θ(1)的长度计算操作。

另一方面, 通过对 buf 分配一些额外的空间, 并使用 free 记录未使用空间的大小, sdshdr 可以让执行追加操作所需的内存重分配次数大大减少, 下一节我们就会来详细讨论这一点。

当然, sds 也对操作的正确实现提出了要求 —— 所有处理 sdshdr 的函数,都必须正确地更新 len 和 free 属性,否则就会造成 bug 。

二、字符串对象

Redis 是一个键值对数据库(key-value DB), 数据库的值可以是字符串、集合、列表等多种类型的对象, 而数据库的键则总是字符串对象。对于那些包含字符串值的字符串对象来说, 每个字符串对象都包含一个 sds 值。

【Redis】关于Redis数据结构简单动态字符串(SDS)的一些杂记(redis相关)

注意:

“包含字符串值的字符串对象”,这种说法初听上去可能会有点奇怪, 但是在 Redis 中, 一个字符串对象除了可以保存字符串值之外, 还可以保存 long 类型的值, 所以为了严谨起见, 这里需要强调一下: 当字符串对象保存的是字符串时, 它包含的才是 sds 值, 否则的话, 它就是一个 long 类型的值。

例如,以下命令创建了一个新的键值对,该键值对的键和值都是字符串对象,他们都包含一个sds值:

127.0.0.1:6379> set school "HeFeiUniversity"OK127.0.0.1:6379> get school"HeFeiUniversity"127.0.0.1:6379>

下面的命令也创建了一个键值对,但是它的键是字符串对象,而值则是一个集合对象:

127.0.0.1:6379> sadd nosql "MongoDB" "Redis" "Neo4j"(integer) 3127.0.0.1:6379> smembers nosql1) "Neo4j"2) "Redis"3) "MongoDB"127.0.0.1:6379>三、Redis字符串与C字符串的区别

在 C 语言中,字符串可以用一个 \0 结尾的 char 数组来表示。

比如说, hello world 在 C 语言中就可以表示为 "hello world\0" 。

这种简单的字符串表示,在大多数情况下都能满足要求,但是,它并不能高效地支持长度计算和追加(append)这两种操作:

每次计算字符串长度(strlen(s))的复杂度为 θ(N)。对字符串进行 N 次追加,必定需要对字符串进行 N 次内存重分配(realloc)。

在 Redis 内部, 字符串的追加和长度计算很常见, 而 APPEND 和 STRLEN 更是这两种操作,在 Redis 命令中的直接映射, 这两个简单的操作不应该成为性能的瓶颈。

另外, Redis 除了处理 C 字符串之外, 还需要处理单纯的字节数组, 以及服务器协议等内容, 所以为了方便起见, Redis 的字符串表示还应该是二进制安全的: 程序不应对字符串里面保存的数据做任何假设, 数据可以是以 \0 结尾的 C 字符串, 也可以是单纯的字节数组, 或者其他格式的数据。

考虑到这两个原因, Redis 使用 sds 类型替换了 C 语言的默认字符串表示: sds 既可高效地实现追加和长度计算, 同时是二进制安全的。

和C字符串不,因为SDS在len属性中记录了SDS本身的长度,所以获取一个SDS长度的复杂度为O(1)。

通过使用SDS而不是C字符串,Redis将获取字符串长度所需的复杂度从O(N)降低到了O(1),这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。所以,即使我们对一个非常长的字符串反复执行STRLEN命令,也不会对系统性能造成任何影响,因为STRLEN命令的复杂度仅为O(1)。

SDS相对于传统C字符串的优点☆☆☆:C字符串SDS获取字符串长度的复杂度为 O(N)获取字符串长度的复杂度为 O(1)操作字符串函数不安全,可能造成缓冲区溢出安全的操作字符串API,避免缓冲区溢出修改字符串长度 N 次必然需要执行 N 次内存重分配修改字符串长度 N 次最多需要执行 N 次内存重分配只能保存文本数据可以保存文本以及图片、音频、视频、压缩文件这样的二进制数据。四、SDS对内存的优化策略

SDS采用了空间预分配策略与惰性空间释放策略来避免内存分配问题。

空间预分配策略是指,每次 SDS 进行空间扩展时,程序不但为其分配所需的空间,还会为其分配额外的未使用空间,以减少内存再分配次数。而额外分配的未使用空间大小取决于空间扩展后SDS 的 len 属性值。

如果 len 属性值小于 1M,那么分配的未使用空间 free 的大小与 len 属性值相同。如果 len 属性值大于等于 1M ,那么分配的未使用空间 free 的大小固定是 1M。

SDS 对于空间释放采用的是惰性空间释放策略。该策略是指,SDS 字符串长度如果缩短,那么多出的未使用空间将暂时不释放,而是增加到 free 中。以使后期扩展 SDS 时减少内存 再分配次数。如果要释放 SDS 的未使用空间,则可通过 sdsRemoveFreeSpace()函数来释放。

五、SDS模块的API

sds 模块基于 sds 类型和 sdshdr 结构提供了以下 API :

函数作用算法复杂度sdsnewlen创建一个指定长度的 sds ,接受一个 C 字符串作为初始化值O(N)sdsempty创建一个只包含空白字符串 "" 的 sdsO(1)sdsnew根据给定 C 字符串,创建一个相应的 sdsO(N)sdsdup复制给定 sdsO(N)sdsfree释放给定 sdsO(N)sdsupdatelen更新给定 sds 所对应 sdshdr 结构的 free 和 lenO(N)sdsclear清除给定 sds 的内容,将它初始化为 ""O(1)sdsMakeRoomFor对 sds 所对应 sdshdr 结构的 buf 进行扩展O(N)sdsRemoveFreeSpace在不改动 buf 的情况下,将 buf 内多余的空间释放出去O(N)sdsAllocSize计算给定 sds 的 buf 所占用的内存总数O(1)sdsIncrLen对 sds 的 buf 的右端进行扩展(expand)或修剪(trim)O(1)sdsgrowzero将给定 sds 的 buf 扩展至指定长度,无内容的部分用 \0 来填充O(N)sdscatlen按给定长度对 sds 进行扩展,并将一个 C 字符串追加到 sds 的末尾O(N)sdscat将一个 C 字符串追加到 sds 末尾O(N)sdscatsds将一个 sds 追加到另一个 sds 末尾O(N)sdscpylen将一个 C 字符串的部分内容复制到另一个 sds 中,需要时对 sds 进行扩展O(N)sdscpy将一个 C 字符串复制到 sdsO(N)

本文仅供学习参考!

本文链接地址:https://www.jiuchutong.com/zhishi/299816.html 转载请保留说明!

上一篇:划水日常(16.5)关于出版图书有偿征集书名 ~(划水划水划水表情包)

下一篇:【Vue】初识Vue,Vue简介及Vue Devtools配置(vue入门)

  • 抖音怎么设置省流量模式(抖音怎么设置省不设置城市)

    抖音怎么设置省流量模式(抖音怎么设置省不设置城市)

  • 苹果手机静音键在哪里(苹果手机静音键自动跳)

    苹果手机静音键在哪里(苹果手机静音键自动跳)

  • 华为荣耀20s是否有指纹锁(华为荣耀20s是否支持nfc)

    华为荣耀20s是否有指纹锁(华为荣耀20s是否支持nfc)

  • 华为手机新品5g怎么截屏(华为手机新品5g多少钱)

    华为手机新品5g怎么截屏(华为手机新品5g多少钱)

  • web服务器访问人数超过上限(服务器web访问日志如何查看)

    web服务器访问人数超过上限(服务器web访问日志如何查看)

  • ipad右上角有个话筒(ipad右上角有个绿色的点)

    ipad右上角有个话筒(ipad右上角有个绿色的点)

  • 文字图层中的文字信息哪些可以进行修改和编辑(文字图层中的文字不可以)

    文字图层中的文字信息哪些可以进行修改和编辑(文字图层中的文字不可以)

  • 小米手机拦截不了骚扰电话(小米手机拦截不了10000)

    小米手机拦截不了骚扰电话(小米手机拦截不了10000)

  • WPS填写身份证号码时变成了E 怎么设置(wps填写身份证号时怎么改成文本格式)

    WPS填写身份证号码时变成了E 怎么设置(wps填写身份证号时怎么改成文本格式)

  • 固态坏了有办法修复吗(固态坏了有什么症状)

    固态坏了有办法修复吗(固态坏了有什么症状)

  • 移动副卡怎么激活(移动副卡怎么激活步骤)

    移动副卡怎么激活(移动副卡怎么激活步骤)

  • 红米note8怎么截屏快捷键(红米note 8怎么截图)

    红米note8怎么截屏快捷键(红米note 8怎么截图)

  • 苹果11最小多少寸(苹果11最小多少g)

    苹果11最小多少寸(苹果11最小多少g)

  • 爱奇艺版权受限怎么下载(爱奇艺版权受限录屏)

    爱奇艺版权受限怎么下载(爱奇艺版权受限录屏)

  • 微信群邀请链接几天过期(微信群邀请链接打不开怎么回事)

    微信群邀请链接几天过期(微信群邀请链接打不开怎么回事)

  • 为什么七天网络未授权(为什么七天网络查不到成绩)

    为什么七天网络未授权(为什么七天网络查不到成绩)

  • word07如何生成目录(word生成目录的简单步骤)

    word07如何生成目录(word生成目录的简单步骤)

  • 快手几个人举报可以封号(快手几个人举报会被永久封号)

    快手几个人举报可以封号(快手几个人举报会被永久封号)

  • 什么是面向对象的操作系统(什么是面向对象设计)

    什么是面向对象的操作系统(什么是面向对象设计)

  • string类可以被继承吗(java中string可以被继承吗)

    string类可以被继承吗(java中string可以被继承吗)

  • 天水公交车怎么扫码(西安到天水大巴车时刻表)

    天水公交车怎么扫码(西安到天水大巴车时刻表)

  • mini5多大运行(mini5几g运行内存)

    mini5多大运行(mini5几g运行内存)

  • 微信运动能看公里数吗(微信运动能看到去过哪里吗)

    微信运动能看公里数吗(微信运动能看到去过哪里吗)

  • 苹果14promax上市时间(苹果14promax价格)

    苹果14promax上市时间(苹果14promax价格)

  • 前端经典面试题 | Computed 和 Watch 的区别(前端面试题必问的题目)

    前端经典面试题 | Computed 和 Watch 的区别(前端面试题必问的题目)

  • 生产企业进项税加计扣除
  • 企业销售商品房需要缴纳什么税费
  • 主营业务收入属于什么类
  • 个税申报数据有误,如何快速更正
  • 收入入账会计分录
  • 编制初始计量有什么要求
  • 哪些纳税人可以申请存量留抵退税
  • 企业库存现金的限额是由( )核定的
  • 工程安装公司暂估人工费如何做会计核算?
  • 个人抬头的通讯费可以做费用吗
  • 营业外收入用不用交企业所得税
  • 土地增值税负数怎么算
  • 维修费增值税怎么开
  • 电子发票可以打多少行
  • 因公出差的人身故怎么办
  • 车间扫帚存放架子
  • 酒店服务行业电费发票怎么开
  • 公司账上的资金与注册资金不一致可以吗?
  • 个体户租房交房怎么交税
  • 公司购买电视
  • 代开专票时城建税一起扣了季报怎么报税
  • 汽车的增值税可以退税吗
  • 财务差旅费报销制度
  • 民宿的房屋租赁合同模板
  • 事业单位收受礼品怎么处理
  • 财政拨款收入是指行政单位从哪里取得的预算资金
  • 在win7系统中将打开窗口拖到屏幕顶端
  • window10自带商店下载位置
  • 汽车修理厂如何做账
  • 增值税发票销货清单哪里领
  • 出租车车票可以出卖吗
  • php system函数的用法
  • 出租固定资产取得的收入属于收入要素吗
  • 低值易耗品报废时有残料价值收回的应冲减当月成本费用
  • vue3中props
  • 会计准则对企业行为的影响分析论文
  • 工程实践指的是
  • PHP 中 DOMDocument保存xml时中文出现乱码问题的解决方案
  • 行政性罚款怎么结转损益
  • c语言printf输出数组
  • 税种分类及其税率
  • SQL(MSSQLSERVER)服务启动错误代码3414的解决方法
  • phpcms v9搬家不同步怎么办
  • 公司签发银行承兑汇票的行为属于什么行为
  • 运输发票抵扣进项税额
  • 融资租入的固定资产视为自有固定资产
  • 固定资产会计上与税法上提折旧时间
  • 其他收益属于什么类科目
  • 一般纳税人应如何报税
  • 公司购买理财产品收益会计分录
  • 出口货物预收账款分录
  • 销售货物时发票多开了金额如何处理?
  • 本年利润每个月需要结转吗
  • 开了假发票什么后果?
  • 银行代发工资业务收费吗
  • 房地产企业预缴增值税
  • 公交充值卡发票能报销吗
  • sql 判断数据是否存在
  • mysql主界面
  • mysql运行代码
  • ubuntu系统常用命令
  • openssl安装教程
  • netsh cmd
  • windows七如何连接网络
  • win10怎么关闭windowsdefender
  • win10预览体验计划不显示
  • win8自带驱动吗
  • js的?
  • 应用框架的设计方法
  • jqueryanimate动画
  • node.js golang
  • JavaScript File API文件上传预览
  • python找出n个数里最小的k个
  • 批量ssh登录
  • jquery 获取父元素的子元素
  • 税务局怎么添加税种
  • 房产税的计税依据与税率分别是什么
  • 煤炭资源税税率选煤税率多少黑龙江
  • 哈尔滨国家税务局客服电话
  • 汉中税务大厅电话是多少
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设