文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

redis内部数据结构之SDS简单动态字符串的示例分析

2024-04-02 19:55

关注

小编给大家分享一下redis内部数据结构之SDS简单动态字符串的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

前言

reids 没有直接使用C语言传统的字符串表示(以空字符结尾的字符数组)而是构建了一种名为简单动态字符串的抽象类型,并为redis的默认字符串表示,因为C字符串不能满足redis对字符串的安全性、效率以及功能方面的需求

1、SDS 定义

在C语言中,字符串是以'\0'字符结尾(NULL结束符)的字符数组来存储的,通常表达为字符指针的形式(char *)。它不允许字节0出现在字符串中间,因此,它不能用来存储任意的二进制数据。

sds的类型定义

typedef char *sds;

 redis内部数据结构之SDS简单动态字符串的示例分析

每个sds.h/sdshdr结构表示一个SDS的值 
struct sdshdr{ 
//记录buf数组中已使用的字节的数量 
//等于sds所保存字符串的长度 
int len; 

//记录buf中未使用的数据 
int free; 

//字符数组,用于保存字符串 
} 


* free 属性的值为0,表示这个SDS没有分配任何未使用的空间 
* len 属性长度为5,表示这个SDS保存一个五字节长的字符串 
* buf 属性是一个char类型的数组,数组的前5个字节分别保存了'R','e','d','i','s'五个字符,而最后一个字节则保存了空字符串'\0'

肯定有人感到困惑了,竟然sds就等同于char *?

sds和传统的C语言字符串保持类型兼容,因此它们的类型定义是一样的,都是char *,在有些情况下,需要传入一个C语言字符串的地方,也确实可以传入一个sds。

但是sds和char *并不等同,sds是Binary Safe的,它可以存储任意二进制数据,不能像C语言字符串那样以字符'\0'来标识字符串的结束,因此它必然有个长度字段,这个字段在header中

sds的header结构


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一共有5种类型的header。目的是节省内存。

一个SDS字符串的完整结构,由在内存地址上前后相邻的两部分组成:

除了sdshdr5之外,其它4个header的结构都包含3个字段:

在各个header的类型定义中,还有几个需要我们注意的地方:

至此,我们非常清楚地看到了:sds字符串的header,其实隐藏在真正的字符串数据的前面(低地址方向)。这样的一个定义,有如下几个好处:

弄清了sds的数据结构,它的具体操作函数就比较好理解了。

sds的一些基础函数

二、SDS 数组动态分配策略

header信息中的定义这么多字段,其中一个很重要的作用就是实现对字符串的灵活操作并且尽量减少内存重新分配和回收操作。

redis的内存分配策略如下

reids的内存回收策略如下

综上所述,redis实现的高性能字符串的结果就把N次字符串操作必会发生N次内存重新分配变为人品最差时最多发生N次重新分配。


sds sdsMakeRoomFor(sds s, size_t addlen) {
 void *sh, *newsh;
 size_t avail = sdsavail(s);
 size_t len, newlen;
 char type, oldtype = s[-1] & SDS_TYPE_MASK;
 int hdrlen;
 
 
 if (avail >= addlen) return s;
 
 len = sdslen(s);
 sh = (char*)s-sdsHdrSize(oldtype);
 newlen = (len+addlen);
 if (newlen < SDS_MAX_PREALLOC)
 newlen *= 2;
 else
 newlen += SDS_MAX_PREALLOC;
 
 type = sdsReqType(newlen);
 
 
 if (type == SDS_TYPE_5) type = SDS_TYPE_8;
 
 hdrlen = sdsHdrSize(type);
 if (oldtype==type) {
 newsh = s_realloc(sh, hdrlen+newlen+1);
 if (newsh == NULL) return NULL;
 s = (char*)newsh+hdrlen;
 } else {
 
 newsh = s_malloc(hdrlen+newlen+1);
 if (newsh == NULL) return NULL;
 memcpy((char*)newsh+hdrlen, s, len+1);
 s_free(sh);
 s = (char*)newsh+hdrlen;
 s[-1] = type;
 sdssetlen(s, len);
 }
 sdssetalloc(s, newlen);
 return s;
}
 

sds sdsRemoveFreeSpace(sds s) {
 void *sh, *newsh;
 char type, oldtype = s[-1] & SDS_TYPE_MASK;
 int hdrlen;
 size_t len = sdslen(s);
 sh = (char*)s-sdsHdrSize(oldtype);
 
 type = sdsReqType(len);
 hdrlen = sdsHdrSize(type);
 if (oldtype==type) {
 newsh = s_realloc(sh, hdrlen+len+1);
 if (newsh == NULL) return NULL;
 s = (char*)newsh+hdrlen;
 } else {
 newsh = s_malloc(hdrlen+len+1);
 if (newsh == NULL) return NULL;
 memcpy((char*)newsh+hdrlen, s, len+1);
 s_free(sh);
 s = (char*)newsh+hdrlen;
 s[-1] = type;
 sdssetlen(s, len);
 }
 sdssetalloc(s, len);
 return s;
}

三、SDS的特点

sds正是在Redis中被广泛使用的字符串结构,它的全称是Simple Dynamic String。与其它语言环境中出现的字符串相比,它具有如下显著的特点:

四、浅谈SDS与string的关系

127.0.0.1:6379> set test test
OK
127.0.0.1:6379> append test " test"
(integer) 9
127.0.0.1:6379> get test
"test test"
127.0.0.1:6379> setbit test 36 1
(integer) 0
127.0.0.1:6379> get test
"test(test"
127.0.0.1:6379> getrange test -5 -1
"(test"

但是,string除了支持这些操作之外,当它存储的值是个数字的时候,它还支持incr、decr等操作。它的内部存储不是SDS,这种情况下,setbit和getrange的实现也会有所不同。

以上是“redis内部数据结构之SDS简单动态字符串的示例分析”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-数据库
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯