关于redis:redis学习-sds字符串

redis学习 – sds字符串

Redis 设计与实现：如果想要晓得redis底层，这本书能够给予不少的帮忙，十分举荐每一位学习redis的同学去翻一翻。

sds字符串倡议多看看源代码的实现，这篇文章根本是集体看了好几篇文章之后的笔记。

源代码文件别离是：sds.c，sds.h

redis的string API应用

首先看下API的简略利用，设置str1变量为helloworld，而后咱们应用debug object +变量名的形式看下，留神编码为embstr。

127.0.0.1:17100> set str1 helloworld
-> Redirected to slot [5416] located at 127.0.0.1:17300
OK
127.0.0.1:17300> debug object str1
Value at:0x7f2821c0e340 refcount:1 encoding:embstr serializedlength:11 lru:14294151 lru_seconds_idle:8

如果咱们将str2设置为helloworldhelloworldhelloworldhelloworldhell，字符长度为44，再应用下debug object+变量名的形式看下，留神编码为embstr。

127.0.0.1:17300> set str2 helloworldhelloworldhelloworldhelloworldhell
-> Redirected to slot [9547] located at 127.0.0.1:17100
OK
127.0.0.1:17100> get str2
"helloworldhelloworldhelloworldhelloworldhell"
127.0.0.1:17100> debug object str2
Value at:0x7fd75e422c80 refcount:1 encoding:embstr serializedlength:21 lru:14294260 lru_seconds_idle:6

然而当咱们把设置为helloworldhelloworldhelloworldhelloworldhello，字符长度为45，再应用debug object+变量名的形式看下，留神编码扭转了，变为raw。

127.0.0.1:17100> set str2 helloworldhelloworldhelloworldhelloworldhello
OK
127.0.0.1:17100> debug object str2
Value at:0x7fd75e430c60 refcount:1 encoding:raw serializedlength:21 lru:14294358 lru_seconds_idle:9

最初咱们将其设置为整数100，再应用debug object+变量名的形式看下，编码的格局变为了int。

127.0.0.1:17100> set str2 11
OK
127.0.0.1:17100> get str2
"11"
127.0.0.1:17100> debug object str2
Value at:0x7fd75e44d370 refcount:2147483647 encoding:int serializedlength:2 lru:14294440 lru_seconds_idle:9

所以Redis的string类型一共有三种存储形式：

当字符串长度小于等于44，底层采纳embstr；
当字符串长度大于44，底层采纳raw；
当设置是整数，底层则采纳int。

至于这三者有什么区别，能够间接看书：

http://redisbook.com/preview/…

为什么redis string 要应用sds字符串？

O(1)获取长度，c语言的字符串自身不记录长度，而是通过开端的\0作为完结标记，而sds自身记录了字符串的长度所以获取间接变为O(1)的工夫复杂度、同时，长度的保护操作由sds的自身api实现
避免缓冲区溢出bufferoverflow：因为c不记录字符串长度，相邻字符串容易产生缓存溢出。sds在进行增加之前会查看长度是否足够，并且不足够会主动依据api扩容
缩小字符串批改的内存调配次数：应用动静扩容的机制，依据字符串的大小抉择适合的header类型存储并且依据理论状况动静扩大。
应用空间预调配和惰性空间开释，其实就是在扩容的时候，依据大小额定扩容2倍或者1M的空间，方面字符串批改的时候进行伸缩
应用二进制爱护，数据的读写不受非凡的限度，写入的时候什么样读取就是什么样
反对兼容局部的c字符串函数，能够缩小局部API的开发

SDS字符串和C语言字符串库有什么区别

摘自黄健巨大神的一张表

C 字符串	SDS
获取字符串长度的复杂度为 O(N) 。	获取字符串长度的复杂度为 O(1) 。
API 是不平安的，可能会造成缓冲区溢出。	API 是平安的，不会造成缓冲区溢出。
批改字符串长度 `N` 次必然须要执行 `N` 次内存重调配。	批改字符串长度 `N` 次最多须要执行 `N` 次内存重调配。
只能保留文本数据。	能够保留文本或者二进制数据。
能够应用所有 `<string.h>` 库中的函数。	能够应用一部分 `<string.h>` 库中的函数。

redis的sds是如何实现的

因为c语言的string是以\0结尾的Redis独自封装了SDS简略动静字符串构造，如果在字符串变量非常多的状况下，会节约非常多的内存空间，同时为了缩小malloc操作，redis封装了本人的sds字符串。

上面是网上查找的一个sds字符串实现的数据结构设计图：

s1,s2别离指向实在数据区域的头部，而要确定一个sds字符串的类型，则须要通过 s[-1] 来获取对应的flags，依据flags分别出对应的Header类型，获取到Header类型之后，依据最低三位获取header的类型（这也是应用__attribute__ ((__packed__))关键字的起因下文会阐明）：

因为s1[-1] == 0x01 == SDS_TYPE_8，因而s1的header类型是sdshdr8。
因为s2[-1] == 0x02 == SDS_TYPE_16，因而s2的header类型是sdshdr16。

上面的局部是sds的实现源代码：

sds一共有5种类型的header。之所以有5种，是为了能让不同长度的字符串能够应用不同大小的header。这样，短字符串就能应用较小的header，从而节俭内存。

typedef char *sds;
 
// 这个比拟非凡，基本上用不到
struct __attribute__ ((__packed__)) sdshdr5 {
    usigned 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[];
};
//string_size < 1ll<<32
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};
//string_size < 1ll<<32
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};
// 定义了五种header类型，用于示意不同长度的string 
#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

#define SDS_TYPE_MASK 7 // 类型掩码
#define SDS_TYPE_BITS 3 // 
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); // 获取header头指针
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) // 获取header头指针
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

下面的代码须要留神以下两个点：

__attribute__ ((__packed__)) 这是C语言的一种关键字,这将使这个构造体在内存中不再恪守字符串对齐规定，而是以内存紧凑的形式排列。目标时在指针寻址的时候，能够间接通过sds[-1]找到对应flags，有了flags就能够晓得头部的类型，进而获取到对应的len，alloc信息，而不应用内存对齐，CPU寻址就会变慢，同时如果不对齐会造成CPU进行优化导致空白位不补0使得header和data不间断，最终无奈通过flags获取低3位的header类型。
SDS_HDR_VAR函数则通过构造体类型与字符串开始字节，获取到动静字符串头部的开始地位，并赋值给sh指针。SDS_HDR函数则通过类型与字符串开始字节，返回动静字符串头部的指针。
在各个header的定义中最初有一个char buf[]。咱们留神到这是一个没有指明长度的字符数组，这是C语言中定义字符数组的一种非凡写法，称为柔性数组（flexible array member），只能定义在一个构造体的最初一个字段上。它在这里只是起到一个标记的作用，示意在flags字段前面就是一个字符数组，或者说，它指明了紧跟在flags字段前面的这个字符数组在构造体中的偏移地位。而程序在为header调配的内存的时候，它并不占用内存空间。如果计算sizeof(struct sdshdr16)的值，那么后果是5个字节，其中没有buf字段。

对于柔性数组的介绍：

深入浅出C语言中的柔性数组

sdshdr5与其它几个header构造不同，它不蕴含alloc字段，而长度应用flags的高5位来存储。因而，它不能为字符串调配空余空间。如果字符串须要动静增长，那么它就必然要从新分配内存才行。所以说，这种类型的sds字符串更适宜存储动态的短字符串（长度小于32）。

同时依据下面的构造能够看到，SDS构造分为两个局部：

len、alloc、flags。只是sdshdr5有所不同，
- len: 示意字符串的真正长度（不蕴含NULL结束符在内）。
- alloc: 示意字符串的最大容量（不蕴含最初多余的那个字节）。
- flags: 总是占用一个字节。其中的最低3个bit用来示意header的类型。header的类型共有5种，在sds.h中有常量定义。

#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

buf[]：柔性数组，之前有提到过，其实就是具体的数据存储区域，留神这里理论存储的数据的时候开端存在NULL

小贴士：

\#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

\#号有什么作用？

这个的含意是让”#”前面的变量依照一般字符串来解决

双\#又有什么用途呢？

双“#”号能够了解为，在单“#”号的根底上，减少了连接功能

sds的创立和销毁

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

sds sdsempty(void) {
    return sdsnewlen("",0);
}

sds sdsnew(const char *init) {
    // 如果initlen 为NULL,应用0作为初始化数据
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

下面的源代码须要留神如下几个点：

SDS_TYPE_5因为设计之初依照常量看待，理论状况大多数为append操作扩容，而SDS_TYPE_5扩容会造成内存的调配，所以应用SDS_TYPE_8 进行断定
SDS字符串的长度为：hdrlen+initlen+1 -> sds_header的长度 + 初始化长度 + 1 (开端占位符NULL断定字符串结尾)
s[initlen] = '\0'; 字符串开端会应用\0进行完结标记：代表为NULL
sdsfree开释sds字符串须要计算出Header的起始地位，具体为s_malloc指针所指向的地位

晓得了sds如何创立之后，咱们能够理解一下外面调用的具体函数。比方sdsReqType，sdsReqType办法定义了获取类型的办法，首先依据操作系统的位数依据判断 LLONG_MAX是否等于LONG_MAX，依据机器确定为32位的状况下调配sds32，同时在64位的操作系统上依据判断小于2^32调配sds32，否则调配sds64。

这里值得注意的是：string_size < 1ll<<32这段代码在redis3.2中才进行了bug修复，在晚期版本当中这里存在调配类型的Bug

commit

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
// 在一些略微长远一点的文章下面没有这一串代码 #
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

再来看下sdslen办法，s[-1]用于向低位地址偏移一个字节，和SDS_TYPE_MASK按位与的操作，取得Header类型，

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    // SDS_TYPE_MASK == 7
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

sds的连贯（追加）操作

/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */

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);
    // 留神开端须要设置占位符\0代表完结标记
    s[curlen+len] = '\0';
    return s;
}

sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

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

// sds实现的一个外围代码，用于判断是否能够追加以及是否有足够的空间
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;

    /* Return ASAP if there is enough space left. */
    // 如果原来的空间大于减少后的空间，间接返回
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // 如果小于 1M，则调配他的两倍大小，否则调配 +1M
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    // sdsheader5 会造成内存的重新分配，应用header8代替
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    // 如果不须要重新分配header，那么试着在原来的alloc空间分配内存
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        // 如果须要更换Header，则须要进行数据的搬迁
        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变量，redis少数的数据结构都采纳这种形式解决。

同时咱们能够确认一下几个点：

append操作的实现函数为sdscatlen函数
getrange这种截取一段字符串内容的形式能够间接操作字符数组，对于局部内容操作看起来比拟容易，效率也比拟高。

sds字符串的空间扩容策略：

如果sds字符串批改之后，空间小于1M，扩容和len等长的未调配空间。比方批改之后为13个字节，那么程序也会调配 13 字节的未应用空间
如果批改之后大于等于1M，则调配1M的内存空间，比方批改之后为30M,则buf的理论长度为：30M+1M+1Byte

简略来说就是：

小于1M，扩容批改后长度2倍
大于1M，扩容1M

结尾：

多多翻翻材料，其实很多货色不须要去钻研细节，有很多优良的人为咱们答疑解惑，所以最重要的是了解作者为什么要这样设计，学习任何货色都要学习思维，思维层面的货色才是最有价值的。

sds曾经被许多大佬文章进行过阐明，这篇文章只是简略的演绎了一下本人看的内容，如果有谬误的中央还望斧正，谢谢

参考资料：

上面是集体学习sds的参考资料：

Redis外部数据结构详解(2)——sds

http://zhangtielei.com/posts/…

解析redis的字符串sds数据结构：

https://blog.csdn.net/wuxing2…

SDS 与 C 字符串的区别

http://redisbook.com/preview/…

Redis源码分析–动静字符串SDS

https://zhuanlan.zhihu.com/p/…

C根底带你手写 redis sds

https://www.lagou.com/lgeduar…

redis源码剖析系列文章

http://www.soolco.com/post/73…

Redis SDS (简略动静字符串) 源码浏览

https://chenjiayang.me/2018/0…

关于redis:redis学习-sds字符串

redis学习 – sds字符串

redis的string API应用

为什么redis string 要应用sds字符串？

SDS字符串和C语言字符串库有什么区别

redis的sds是如何实现的

sds的创立和销毁

sds的连贯（追加）操作

sds字符串的空间扩容策略：

结尾：

参考资料：

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于redis:redis学习-sds字符串

redis学习 – sds字符串

redis的string API应用

为什么redis string 要应用sds字符串？

SDS字符串和C语言字符串库有什么区别

redis的sds是如何实现的

sds的创立和销毁

sds的连贯（追加）操作

sds字符串 的空间扩容策略：

结尾：

参考资料：

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

sds字符串的空间扩容策略：

发表回复取消回复