带你读《Redis 5设计与源码分析》之二:简单动态字符串-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

带你读《Redis 5设计与源码分析》之二:简单动态字符串

简介: 本书从底层源码的角度,对 Redis的数据结构以及持久化、主从复制、哨兵和集群等特性的实现原理进行了详尽的剖析,图文并茂。
+关注继续查看

点击查看第一章
点击查看第三章
第2章

简单动态字符串

简单动态字符串(Simple Dynamic Strings,SDS)是Redis的基本数据结构之一,用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数,且在此基础上保证了二进制安全。本章将详细讲解SDS的实现,为读者理解Redis的原理和各种命令的实现打下基础。

2.1 数据结构

在学习SDS源码前,我们先思考一个问题:如何实现一个扩容方便且二进制安全的字符串呢?
什么是二进制安全?通俗地讲,C语言中,用“0”表示字符串的结束,如果字符串中本身就有“0”字符,字符串就会被截断,即非二进制安全;若通过某种机制,保证读写字符串时不损害其内容,则是二进制安全。
SDS既然是字符串,那么首先需要一个字符串指针;为了方便上层的接口调用,该结构还需要记录一些统计信息,如当前数据长度和剩余容量等,例如:

struct sds {
    int len;// buf 中已占用字节数
    int free;// buf 中剩余可用字节数
    char buf[];// 数据空间
};

SDS结构示意如图2-1所示,在64位系统下,字段len和字段free各占4个字节,紧接着存放字符串。
Redis 3.2之前的SDS也是这样设计的。这样设计有以下几个优点。

image.png

1)有单独的统计变量len和free(称为头部)。可以很方便地得到字符串长度。
2)内容存放在柔性数组buf中,SDS对上层暴露的指针不是指向结构体SDS的指针,而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容,兼容C语言处理字符串的各种函数。
3)由于有长度统计变量len的存在,读写字符串时不依赖“0”终止符,保证了二进制安全。
上例中的buf[]是一个柔性数组。柔性数组成员(flexible array member),也叫伸缩性数组成员,只能被放在结构体的末尾。包含柔性数组成员的结构体,通过malloc函数为柔性数组动态分配内存。
之所以用柔性数组存放字符串,是因为柔性数组的地址和结构体是连续的,这样查找内存更快(因为不需要额外通过指针找到字符串的位置);可以很方便地通过柔性数组的首地址偏移得到结构体首地址,进而能很方便地获取其余变量。
到这里我们实现了一个最基本的动态字符串,但是该结构是否有改进的空间呢?我们从一个简单的问题开始思考:不同长度的字符串是否有必要占用相同大小的头部?一个int占4字节,在实际应用中,存放于Redis中的字符串往往没有这么长,每个字符串都用4字节存储未免太浪费空间了。我们考虑三种情况:短字符串,len和free的长度为1字节就够了;长字符串,用2字节或4字节;更长的字符串,用8字节。
这样确实更省内存,但依然存在以下问题。
问题1:如何区分这3种情况?
问题2:对于短字符串来说,头部还是太长了。以长度为1字节的字符串为例,len和free本身就占了2个字节,能不能进一步压缩呢?
对于问题1,我们考虑增加一个字段flags来标识类型,用最小的1字节来存储,且把flags加在柔性数组buf之前,这样虽然多了1字节,但通过偏移柔性数组的指针即能快速定位flags,区分类型,也可以接受;对于问题2,由于len已经是最小的1字节了,再压缩只能考虑用位来存储长度了。
结合两个问题,5种类型(长度1字节、2字节、4字节、8字节、小于1字节)的SDS至少要用3位来存储类型(23=8),1个字节8位,剩余的5位存储长度,可以满足长度小于32的短字符串。在Redis 5.0中,我们用如下结构来存储长度小于32的短字符串:

struct __attribute__ ((__packed__))sdshdr5 {
    unsigned char flags; /* 低3位存储类型, 高5位存储长度 */
    char buf[];/*柔性数组,存放实际内容*/
};

sdshdr5结构(图2-2)中,flags占1个字节,其低3位(bit)表示type,高5位(bit)表示长度,能表示的长度区间为0~31(25-1),flags后面就是字符串的内容。
image.png
而长度大于31的字符串,1个字节依然存不下。我们按之前的思路,将len和free单独存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的结构相同,sdshdr16结构如图2-3所示。
image.png
其中“表头”共占用了S[2(len)+2(alloc)+1(flags)]个字节。flags的内容与sdshdr5类似,依然采用3位存储类型,但剩余5位不存储长度。
在Redis的源代码中,对类型的宏定义如下:

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

在Redis 5.0中,sdshdr8、sdshdr16、sdshdr32和sdshdr64的数据结构如下:

struct __attribute__((__packed__))sdshdr8 {
    uint8_t len; /* 已使用长度,用1字节存储 */
    uint8_t alloc; /* 总长度,用1字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组,存放实际内容*/
};
struct __attribute__((__packed__))sdshdr16 {
    uint16_t len; /*已使用长度,用2字节存储*/
    uint16_t alloc; /* 总长度,用2字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组,存放实际内容*/
};
struct __attribute__((__packed__))sdshdr32 {
    uint32_t len; /*已使用长度,用4字节存储*/
    uint32_t alloc; /* 总长度,用4字节存储*/
    unsigned char flags;/* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组,存放实际内容*/
};
struct __attribute__((__packed__))sdshdr64 {
    uint64_t len; /*已使用长度,用8字节存储*/
    uint64_t alloc; /* 总长度,用8字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组,存放实际内容*/
};

可以看到,这4种结构的成员变量类似,唯一的区别是len和alloc的类型不同。结构体中4个字段的具体含义分别如下。
1)len:表示buf中已占用字节数。
2)alloc:表示buf中已分配字节数,不同于free,记录的是为buf分配的总长度。
3)flags:标识当前结构体的类型,低3位用作标识位,高5位预留。
4)buf:柔性数组,真正存储字符串的数据空间。
结构最后的buf依然是柔性数组,通过对数组指针作“减一”操作,能方便地定位到flags。在2.2节中,我们能更直观地了解该用法。
源码中的__attribute__((__packed__))需要重点关注。一般情况下,结构体会按其所有变量大小的最小公倍数做字节对齐,而用packed修饰后,结构体则变为按1字节对齐。以sdshdr32为例,修饰前按4字节对齐大小为12(4×3)字节;修饰后按1字节对齐,注意buf是个char类型的柔性数组,地址连续,始终在flags之后。packed修饰前后示意如图2-4所示。
这样做有以下两个好处。

  • 节省内存,例如sdshdr32可节省3个字节(12-9)。
  • SDS返回给上层的,不是结构体首地址,而是指向内容的buf指针。因为此时按1字节对齐,故SDS创建成功后,无论是sdshdr8、sdshdr16还是sdshdr32,都能通过(char*)sh+hdrlen得到buf指针地址(其中hdrlen是结构体长度,通过sizeof计算得到)。修饰后,无论是sdshdr8、sdshdr16还是sdshdr32,都能通过buf[-1]找到flags,因为此时按1字节对齐。若没有packed的修饰,还需要对不同结构进行处理,实现更复杂。

image.png

2.2 基本操作

数据结构的基本操作不外乎增、删、改、查,SDS也不例外。由于Redis 3.2后的SDS涉及多种类型,修改字符串内容带来的长度变化可能会影响SDS的类型而引发扩容。本节着重介绍创建、释放、拼接字符串的相关API,帮助大家更好地理解SDS结构。在2.2.4节列出了SDS相关API的函数名和功能介绍,有兴趣的读者可自行查阅源代码。

2.2.1 创建字符串

Redis通过sdsnewlen函数创建SDS。在函数中会根据字符串长度选择合适的类型,初始化完相应的统计值后,返回指向字符串内容的指针,根据字符串长度选择不同的类型:

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);//根据字符串长度选择不同的类型
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;//SDS_TYPE_5强制转化为SDS_TYPE_8
    int hdrlen = sdsHdrSize(type);//计算不同头部所需的长度
    unsigned char *fp; /* 指向flags的指针 */
    sh = s_malloc(hdrlen+initlen+1);//"+1"是为了结束符'\0'
    ...
    s = (char*)sh+hdrlen;//s是指向buf的指针
    fp = ((unsigned char*)s)-1;//s是柔性数组buf的指针,-1即指向flags
    ...
    s[initlen] = '\0';//添加末尾的结束符
    return s;
}

Redis 3.2后的SDS结构由1种增至5种,且对于sdshdr5类型,在创建空字符串时会强制转换为sdshdr8。原因可能是创建空字符串后,其内容可能会频繁更新而引发扩容,故创建时直接创建为sdshdr8。
创建SDS的大致流程:首先计算好不同类型的头部和初始长度,然后动态分配内存。需要注意以下3点。
1)创建空字符串时,SDS_TYPE_5被强制转换为SDS_TYPE_8。
2)长度计算时有“+1”操作,是为了算上结束符“0”。
3)返回值是指向sds结构buf字段的指针。
返回值sds的类型定义如下:

typedef char *sds;

从源码中我们可以看到,其实s就是一个字符数组的指针,即结构中的buf。这样设计的好处在于直接对上层提供了字符串内容指针,兼容了部分C函数,且通过偏移能迅速定位到SDS结构体的各处成员变量。

2.2.2 释放字符串

SDS提供了直接释放内存的方法—sdsfree,该方法通过对s的偏移,可定位到SDS结构体的首部,然后调用s_free释放内存:

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));//此处直接释放内存
}

为了优化性能(减少申请内存的开销),SDS提供了不直接释放内存,而是通过重置统计值达到清空目的的方法—sdsclear。该方法仅将SDS的len归零,此处已存在的buf并没有真正被清除,新的数据可以覆盖写,而不用重新申请内存。

void sdsclear(sds s) {
    sdssetlen(s, 0); //统计值len归零
    s[0] = '\0';//清空buf
}

2.2.3 拼接字符串

拼接字符串操作本身不复杂,可用sdscatsds来实现,代码如下:

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

sdscatsds是暴露给上层的方法,其最终调用的是sdscatlen。由于其中可能涉及SDS的扩容,sdscatlen中调用sdsMakeRoomFor对带拼接的字符串s容量做检查,若无须扩容则直接返回s;若需要扩容,则返回扩容好的新字符串s。函数中的len、curlen等长度值是不含结束符的,而拼接时用memcpy将两个字符串拼接在一起,指定了相关长度,故该过程保证了二进制安全。最后需要加上结束符。

/* 将指针t的内容和指针s的内容拼接在一起,该操作是二进制安全的*/
sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);//直接拼接,保证了二进制安全
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';//加上结束符
    return s;
}

图2-5描述了sdsMakeRoomFor的实现过程。
Redis的sds中有如下扩容策略。
1)若sds中剩余空闲长度avail大于新增内容的长度addlen,直接在柔性数组buf末尾追加即可,无须扩容。代码如下:

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;//s[-1]即flags
    int hdrlen;
    if (avail >= addlen) return s;//无须扩容,直接返回
    ...
}

2)若sds中剩余空闲长度avail小于或等于新增内容的长度addlen,则分情况讨论:新增后总长度len+addlen<1MB的,按新长度的2倍扩容;新增后总长度len+addlen>1MB的,按新长度加上1MB扩容。代码如下:

sds sdsMakeRoomFor(sds s, size_t addlen) 
{
    ...
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)// SDS_MAX_PREALLOC这个宏的值是1MB
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    ...
}

3)最后根据新长度重新选取存储类型,并分配空间。此处若无须更改类型,通过realloc扩大柔性数组即可;否则需要重新开辟内存,并将原字符串的buf内容移动到新位置。具体代码如下:

image.png

sds sdsMakeRoomFor(sds s, size_t addlen) 
{
    ...
    type = sdsReqType(newlen);
    /* type5的结构不支持扩容,所以这里需要强制转成type8*/
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
    /*无须更改类型,通过realloc扩大柔性数组即可,注意这里指向buf的指针s被更新了*/
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /*扩容后数据类型和头部长度发生了变化,此时不再进行realloc操作,而是直接重新开辟内存,拼接完内容后,释放旧指针*/
        newsh = s_malloc(hdrlen+newlen+1);//按新长度重新开辟内存
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);//将原buf内容移动到新位置
        s_free(sh);//释放旧指针
        s = (char*)newsh+hdrlen;//偏移sds结构的起始地址,得到字符串起始地址
        s[-1] = type;//为falgs赋值
        sdssetlen(s, len);//为len属性赋值
    }
    sdssetalloc(s, newlen);//为alloc属性赋值
    return s;
}

2.2.4 其余API

SDS还为上层提供了许多其他API,篇幅所限,不再赘述。表2-1列出了其他常用的API,读者可自行查阅源码学习,学习时把握以下两点。
1)SDS暴露给上层的是指向柔性数组buf的指针。
2)读操作的复杂度多为O(1),直接读取成员变量;涉及修改的写操作,则可能会触发扩容。
image.png

2.3 本章小结

本章介绍了SDS的数据结构及基本API的实现。在源码分析过程中,我们可以知道SDS的以下特性是如何实现的。
1)SDS如何兼容C语言字符串?如何保证二进制安全?
SDS对象中的buf是一个柔性数组,上层调用时,SDS直接返回了buf。由于buf是直接指向内容的指针,故兼容C语言函数。而当真正读取内容时,SDS会通过len来限制读取长度,而非“0”,保证了二进制安全。
2)sdshdr5的特殊之处是什么?
sdshdr5只负责存储小于32字节的字符串。一般情况下,小字符串的存储更普遍,故Redis进一步压缩了sdshdr5的数据结构,将sdshdr5的类型和长度放入了同一个属性中,用flags的低3位存储类型,高5位存储长度。创建空字符串时,sdshdr5会被sdshdr8替代。
3)SDS是如何扩容的?
SDS在涉及字符串修改处会调用sdsMakeroomFor函数进行检查,根据不同情况动态扩容,该操作对上层透明。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Gear的技术优势
Gear 关键的技术创新在于其新颖的跨合约通信方式。Gear 使用 Actor 通信模型和 WebAssembly VM,支持并行处理,并具有速度快、成本低的优势。 事实证明, WebAssembly VM 比任何其他方案运行速度都要快。使用 WebAssembly 可以让 GEAR 的智能合约直接编译成机器码,运行速度媲美原生。更快的速度意味着更低的交易成本和更高的效率。
9 0
C 语言项目_项目流程|学习笔记
快速学习 C 语言项目_项目流程
6 0
mysql事务隔离级别
mysql事务隔离级别
11 0
MySQL MGR模式介绍
MGR是Mysql Group Replication(组复制)的缩写,Mysql5.7之后是以一个Mysql插件的形式集成在Mysql中,用于创建可伸缩、高可用、可容错的复制架构,是Mysql集群的一种形式
9 0
阿里云飞天加速计划ecs服务器试用体验
关于阿里云飞天加速计划ecs服务器的试用体验
9 0
synchronized 中的 4 个优化,你知道几个?(1)
synchronized 中的 4 个优化,你知道几个?(1)
4 0
JVM深入学习(二十四)-GC日志
GC日志是分析垃圾回收不可缺少的工具,我们通过对GC日志的分析可以看到垃圾回收的详细过程,更好的调优垃圾回收
4 0
图解:为什么非公平锁的性能更高?(3)
图解:为什么非公平锁的性能更高?(3)
8 0
HashMap 中的一个“坑”!(2)
HashMap 中的一个“坑”!(2)
23 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载