Redis学习笔记——SDS

刘东发布于2019-07-24 14:51 / 511人阅读

摘要：定义了一种数据结构动态字符串来表示字符串值，该数据结构的定义在文件中保存字符串对象的结构中已占用空间的长度中剩余可用空间的长度数据空间变量名已经清晰的记录了变量的作用。是安全的，不会造成缓冲区溢出。修改字符串长度次最多需要执行次内存重分配。

Redis定义了一种数据结构动态字符串来表示字符串值，该数据结构的定义在文件/src／sds.h中

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

变量名已经清晰的记录了变量的作用。初次之外，还定义了这个结构的一些操作接口。

static inline size_t sdsavail(const sds s);        //返回字符串生于的可用空间的长度，也就是free值
sds sdsnewlen(const void *init, size_t initlen);   //根据init指向的字符串常量，和initlen指定的大小来构造字符串
sds sdsnew(const char *init); //根据init指向的字符串常量来构造字符串，不过是通过sdsnewlen来实现的sds sdsempty(void); // 创建长度为0的空字符串size_t sdslen(const sds s); //返回字符串实际占用空间的长度，也就是len值
sds sdsdup(const sds s); //拷贝一个字符串，也是通过sdsnewlen来实现
sds sdsfree(sds s);   //释放字符串占用的空间
sds sdsgrowzero(sds s, size_t len); //将sds扩充至指定长度，末尾未使用的空间以0填充
sds sdscatlen(sds s, const void *t, size_t len); //将字符串t的前len个字节填充到s的末尾
sds sdscat(sds s, const char *t); //将字符串t填充到s的末尾，动下脑子就能猜到，内部通过sdscatlen实现
sds sdscatsds(sds s, const sds t); //同上，因为typedefchar *sds;
sds sdscpylen(sds s, const char *t, size_t len); //将t的前len个字符拷贝到s上，也就是会覆盖s的内容
sds sdscpy(sds s, const char *t); // 将t的内容拷贝到s上
sds sdscatvprintf(sds s, const char *fmt, va_list ap);//通过fmt指定个格式来格式化字符串
sds sdscatfmt(sds s, char const *fmt, ...); //将格式化后的任意数量个字符串追加到s的末尾，通过sdscatvprintf实现
sds sdstrim(sds s, const char *cset); //对s的左右两端进行裁剪，去掉cset指定的字符
void sdsrange(sds s, int start, int end); //通过索引区间[start,end]来截取字符串
void sdsupdatelen(sds s); //根据字符串所占用空间的长度大小来更新len、free
void sdsclear(sds s); //将字符串的第一个字符串置为""，也就是把字符串置为空字符串，但是没有释放空间
int sdscmp(const sds s1, const sds s2); //比较两个sds是否相等
sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count);
//使用分隔符sep对s进程进行分割，返回一个sds数组，同时count设置为数组的个数
//len和seplen分别是s和sep的长度
void sdsfreesplitres(sds *tokens, int count);//释放数组tokens的count个sds
void sdstolower(sds s); // 将sds的所有字符都转换成小写
void sdstoupper(sds s); // 将sds的所有字符都转换成大写 
sds sdsfromlonglong(long long value); //将长整型数据转成字符串
sds sdscatrepr(sds s, const char *p, size_t len);
//将长度为len的字符串p以带引号的格式追加到s的末尾
//如 s = "abc" , p = "gbdf
134"; 那么函数的返回结果为 ret = "abc"gbdf
134""
sds *sdssplitargs(const char *line, int *argc);//将一行文本分割成多个参数，参数的个数存在argc
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
// 将字符串s中，出现存在from中指定的字符，都转换成to中的字符，from与to是有位置关系，
// 假如from = "ckj", to = "345", 那么‘c’就换成‘3’, "k"就换成‘4’, 以此类推
sds sdsjoin(char **argv, int argc, char *sep); //通过分隔符sep把字符数组argv拼接成一个字符串
sds sdsMakeRoomFor(sds s, size_t addlen); //对字符串进行扩充，使之有addlen+1个长度的剩余空间
void sdsIncrLen(sds s, int incr); //在不重新分配空间的基础上，给字符串增加incr长度
sds sdsRemoveFreeSpace(sds s); //回收sds剩余的空间内容，但是不会修改字符串的内容
size_t sdsAllocSize(sds s); //返回给s分配的内存的字节数

代码中操作的对象是sds，并且多次利用sdshr中buf的偏移地址来获取sdshr的地址，如下

struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));

个人感觉这个可以写成一个宏，像offsetof。之所以可以这样用sizeof(struct sdshdr)是因为，buf是变长数组，因为没有指定长度，所以没有占用空间。所以，sizeof(struct sdshdr) == sizeof(int) + sizeof(int)
1.Redis通过空间预分配来减少修改字符串带来的内存重新分配的开销。分配的算法如下：
A. 如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ，那么程序分配和 len 属性同样大小的未使用空间，这时 SDS len 属性的值将和 free 属性的值相同。举个例子，如果进行修改之后， SDS 的 len 将变成 13 字节，那么程序也会分配 13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。
B. 如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ，那么程序会分配 1 MB 的未使用空间。举个例子，如果进行修改之后， SDS 的 len 将变成 30 MB ，那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte

2.Redis缩短字符串时，只把字符串的第一个字符置为"0"，不回收空间。也就是所谓的惰性空间释放

3.Redis字符串是二进制安全的，因为sdshr里的字符串数组 char buf[] 存储字符的二进制数据，通过len来表示大小

最后附上《Redis设计与实现的总结》里指出的C字符串跟SDS的区别
字符串和 SDS 之间的区别
C 字符串 SDS
获取字符串长度的复杂度为 O(N) 。获取字符串长度的复杂度为 O(1) 。
API 是不安全的，可能会造成缓冲区溢出。 API 是安全的，不会造成缓冲区溢出。
修改字符串长度 N 次必然需要执行 N 次内存重分配。修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。可以保存文本或者二进制数据。
可以使用所有库中的函数。可以使用一部分库中的函数。

参考：《Redis设计与实现》

云服务器超融合服务器 linux和redis笔记学习笔记学习笔记一基础学习笔记

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/36315.html

【Redis5源码学习】2019-04-15 简单动态字符串SDS

摘要：关于结构体内存对齐是什么，请参考源码学习内存管理笔记。这说明在当前情况下，字符串结构中的柔性数组的起始位置并不受是否加关键字而影响，是紧跟在结构体后面的，所以节省内存这个说法并不成立。 baiyan 全部视频：https://segmentfault.com/a/11... 今天我们正式进入redis5源码的学习。redis是一个由C语言编写、基于内存、单进程、可持久化的Key-Va...

Vixb 2019-08-06 13:45 评论0 收藏0
Redis 数据结构之String

摘要：目的现在是各个系统几乎都在使用的一种分布式高可用的缓存内存中的数据结构存储系统。但是这些我们经常使用的数据结构的底层是怎么实现的。总结因为作为一个数据库存储来使，而且是一个单线程，一旦一个操作阻塞了之后之后的所有操作都会被影响。目的 Redis现在是各个系统几乎都在使用的一种分布式高可用的缓存内存中的数据结构存储系统。可以作为数据库、缓存消息中间件、订阅发布系统等。我们都知道redi...

TigerChain 2019-07-24 16:16 评论0 收藏0
《Redis设计与实现》读书笔记（一）

摘要：这就避免了缓冲区溢出问题作为数据库，在设计的时候，一定是假设数据会被经常访问和修改。第一部分数据结构与对象 Redis是键值数据库。键通常是字符串对象，值有五种可能的对象：字符串，列表，哈希，集合，有序集合。第一部分是介绍这五种对象，剖析其底层数据结构，以及该数据结构对其功能和性能的影响 Redis是由C语言编写，所以出现的源码皆为C语言，其他语言会另外声明。 1. 简单动态字...

wemall 2019-07-24 16:29 评论0 收藏0
【Redis学习笔记】2018-05-29 redis源码学习之跳跃表

摘要：四跳跃表的插入跳跃表的插入使用的是函数，该函数如下该函数有一个难点，即函数。现在假设由返回的所以这个进不去。新建一个节点循环可以进入一次，循环内部的代码为更新和新节点的值，更新后如图所示。顺风车运营研发团队谭淼跳跃表(skiplist)是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到指向其他节点的目的。在Redis中，有序集合是通过跳跃表和hash实现的...

AlexTuan 2019-07-24 15:33 评论0 收藏0
Redis中SDS简单动态字符串

摘要：而使用结构体实现，结构体中的属性直接记录了该结构体中数组中已使用的长度，因此获取字符串长度时，只需要获取属性的值，这个操作的复杂度为。结构体的实现确保了获取字符串长度的工作不会成为的性能瓶颈。 0x00 SDS：简单动态字符串 SDS是Redis中实现的一种数据结构，用来存储字符串，代码实现如下： // 文件路径：src/sds.h struct sdshdr { // 记录b...

xorpay 2019-07-24 14:34 评论0 收藏0