个人中心
gpt4 book ai didi

【Redis】字符串sds

转载 作者：我是一只小鸟 更新时间：2023-07-13 22:31:46 25 4
gpt4 key购买 nike

sds，即 Simple Dynamic Strings，是Redis中存储绝大部分字符串所采用的数据结构.

typedef char *sds,

1、类型

sds的类型包括 SDS_TYPE_5 , SDS_TYPE_8 , SDS_TYPE_16 , SDS_TYPE_32 , SDS_TYPE_64 五种:

                      
                        #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

创建sds时根据初始字符串的长度指定sds类型。源码如下:

                      
                        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
}

标识SDS_TYPE的数字实际上指定了字符串长度能够由长度为几位的二进制数标识.

long long 一般是8字节，只有当 long 也为8字节，且字符串长度用32位不足以表示时，才会将sds指定为 SDS_TYPE_64 类型.

疑问：函数参数 size_t string_size 的类型实际为 unsigned long long ，为什么要考虑 long 型的长度?

由于一共有5种类型，需要二进制数至少三位来标识类型。这可以从下文得到印证.

2、结构

sds大致的结构为头部+字符串值。对于上述五种不同类型，sds结构大同小异.

                      
                        struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

__attribute__ ((__packed__)) 用于指示编译器以紧凑方式打包结构体，即不对成员进行对齐.

可以看到，公共的成员变量包括 buf 与 flags .

  • buf 用于实际存储数据
  • flags 共有的用途是指明sds的类型，具体存储在低3位

struct sdshdr5 相对不复杂，仅在 flags 中记录了字符串的实际长度。由前文可知，当原字符串长度可以用不超过5位表示时，sds采用 SDS_TYPE_5 类型。于是将长度的5位与用于标识类型的3位组合为 flags ，很好地利用了空间.

对于其他类型的sds， flags 中的高五位已不能满足长度记录需要，因此增加了字段.

  • len ：指的是实际字符串的长度，与 SDS_TYPE_5 类型的sds中 flags 高五位的含义一致
  • alloc ：指的是分配的字节数，不包含头部与字符串尾部附加的 '\0'

3、相关操作

(1) 创建

最简单的创建sds的函数定义如下所示，该函数接收一个C语言字符串作为参数（C语言字符串以'\0'为结尾）.

                      
                        sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnew(const char *init) 方法实际调用了 sdsnewlen 方法，将原始字符串和字符串长度作为参数传入。 sdsnewlen 方法定义如下:

                      
                        sds sdsnewlen(const void *init, size_t initlen) {
    return _sdsnewlen(init, initlen, 0);
}

sdsnewlen 仍然是一个壳子，调用了 _sdsnewlen 方法，其定义如下.

                      
                        sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    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. */
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    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 = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

函数内部首先判定待创建的sds类别，存放在变量 type 中，所调用的 sdsReqType 我们在前文已经介绍过了。 有一个细节的处理是，如果字符串长度是0，手动将其设置为 SDS_TYPE_8 类型。原因在源码的注释中已经给出：字符串长度为0的sds一般是被创建用来拼接字符串的，而 SDS_TYPE_5 类型的sds并不擅长做这个.

接下来，调用函数 sdsHdrSize 根据类别获取头部长度，存放在变量 hdrlen 中。函数定义也很简单，就是根据 type 计算对应的头部结构体大小并返回。需要额外解释的是，每个sds头结构体实际用一个柔性数组存放字符串，在 sizeof() 计算时，柔型数组字段对应的 size 为0。以 struct sdshdr8 为例，其大小只有前三个成员的大小决定，为 1+1+1 字节.

                      
                        struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

接下来，为sds分配空间，对应这段代码:

                      
                        sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);

sdsnewlen 调用 _sdsnewlen 时，传参 trymalloc 为0。于是我们查看 s_malloc_usable 方法。调用 s_malloc_usable 传入两个参数，第一个参数值 hdrlen+initlen+1 恰好指定 sds 所需的最小空间，包括头部空间，原始字符串，以及字符串末尾的 \0 。第二个参数用于接收分配的可用空间大小.

s_malloc_usable 实际通过宏定义指向 zmalloc_usable 方法.

                      
                        void *zmalloc_usable(size_t size, size_t *usable) {
    size_t usable_size = 0;
    void *ptr = ztrymalloc_usable_internal(size, &usable_size);
    if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
    ptr = extend_to_usable(ptr, usable_size);
#endif
    if (usable) *usable = usable_size;
    return ptr;
}

这一方法内部又调用了 ztrymalloc_usable_internal 方法:

                      
                        static inline void *ztrymalloc_usable_internal(size_t size, size_t *usable) {
    /* Possible overflow, return NULL, so that the caller can panic or handle a failed allocation. */
    if (size >= SIZE_MAX/2) return NULL;
    void *ptr = malloc(MALLOC_MIN_SIZE(size)+PREFIX_SIZE);

    if (!ptr) return NULL;
#ifdef HAVE_MALLOC_SIZE
    size = zmalloc_size(ptr);
    update_zmalloc_stat_alloc(size);
    if (usable) *usable = size;
    return ptr;
#else
    // 分析这里
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    if (usable) *usable = size;
    return (char*)ptr+PREFIX_SIZE;
#endif
}

malloc 分配处，将宏定义展开则为如下表达式:

void *ptr = malloc((size > 0 ? size : 0)+(sizeof(size_t))) 。

size_t 实际为 unsigned long long ，额外分配的 PREFIX_SIZE 空间用于存储本次分配空间的大小，不包含 PREFIX_SIZE 空间大小.

调用 update_zmalloc_stat_alloc 的目的是维护记录分配空间大小的变量 user_memory .

                      
                        #define update_zmalloc_stat_alloc(__n) atomicIncr(used_memory,(__n))

                      
                    
                      
                        static redisAtomic size_t used_memory = 0;

ztrymalloc_usable_internal 最终返回的是所分配空间向后偏移 PREFIX_SIZE 的地址.

分配空间的部分我们已经解读完毕，接下来继续阅读 _sdsnewlen 剩余代码.

s = (char*)sh+hdrlen; ，使 s 指向头部柔型数组成员.

fp = ((unsigned char*)s)-1; 使 fp 指向柔型数组前一个成员，即 flags .

switch 语句根据 type 为头部每个成员赋值。其中 SDS_HDR_VAR 宏定义如下:

                      
                        #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

这行代码让根据 type 和柔型数组首地址找到头部首地址，并将 sh 指向这一地址.

两个与长度相关的字段赋值如下:

                      
                        sh->len = initlen;
sh->alloc = usable;

这时， usable 与 initlen 的长度实际上是相等的.

接着复制字符串，并在末尾附加'\0':

                      
                        if (initlen && init)
    memcpy(s, init, initlen);
s[initlen] = '\0';

最后返回的是 s 而非 sh 。也就是说， sds 创建后，并不存在指向其头部首地址的指针， sds 指针指向柔性数组字段.

(2) 空间扩展

sds 扩展空间有两种方式，不同之处在于是否进行空间预分配，即分配额外的空间以避免每次增加字符都要重新分配内存。两个函数的定义如下:

                      
                        /* Enlarge the free space at the end of the sds string more than needed,
 * This is useful to avoid repeated re-allocations when repeatedly appending to the sds. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    return _sdsMakeRoomFor(s, addlen, 1);
}

/* Unlike sdsMakeRoomFor(), this one just grows to the necessary size. */
sds sdsMakeRoomForNonGreedy(sds s, size_t addlen) {
    return _sdsMakeRoomFor(s, addlen, 0);
}

可以看到，两个函数最终调用同一个函数 _sdsMakeRoomFor ，第三个参数指明是否需要进行预分配.

_sdsMakeRoomFor 定义如下:

                      
                        sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
        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. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        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 */
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        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);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}

首先判断已有sds尚未使用的空间是否已达到 addlen ， sdsavail 定义如下.

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

若未使用空间已能够满足要求，则不额外分配，直接返回.

若继续分配，要确定新的空间大小:

                      
                        reqlen = newlen = (len+addlen);
if (greedy == 1) {
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
}

这里就是 sdsMakeRoomForNonGreedy 与 sdsMakeRoomFor 差异的根源.

if (greedy == 1) 内 newlen 相比于自身原值增加的值就是预分配的空间。预分配空间是有上限的:

                      
                        #define SDS_MAX_PREALLOC (1024*1024)

若 newlen 原值达不到预分配空间上限，就分配二倍的 newlen 空间，否则额外分配 SDS_MAX_PREALLOC 大小的空间.

接着指定新sds的类型:

                      
                        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. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;

这里更加明确地避免了 SDS_TYPE_5 的使用。由前面 sdsavail 函数可以看到， SDS_TYPE_5 的未使用空间永远是0，这也是为什么 SDS_TYPE_5 不适合用于字符串拼接：每次拼接都要重新分配空间.

后面的处理根据新旧 type 是否一致而存在差异。若新旧 type 一致，头部长度不变，新的空间数据分布与原空间一致，因此调用 realloc ，当新的空间大小大于原空间大小时，realloc的作用是在堆上开辟一块新的内存空间，将原空间的内容复制到新空间，然后释放新空间。若新旧 type 不一致，则新旧sds中 buf 的位置相对于头部首地址不同，不能直接利用 realloc 拷贝，因此调用 malloc ，并需要手动 s_free 原 sds .

4、特性

(1) 结构特性

redis的sds由头部和实际字符串两部分组成，并在字符串末尾附加一个'\0'，其中字符串作为头部结构体最后一个成员变量存在，且sds实际指向柔型数组的首地址。这样的结构有很多好处:

  1. redis的字符串与头部空间可以同时分配、同时释放，且空间连续
  2. 头部维护元信息，简化了部分操作，计算字符串的长度
  3. 二进制安全：sds以头部的 len 字段标识结尾处，而不在'\0'处结尾
  4. 兼容C字符串
(2) 空间预分配

初始创建sds时不预留空间，这是因为不是所有的sds都会执行拼接操作，预留空间未必有意义。而当对sds执行字符串拼接操作时，就要进行空间的预分配了。当存在预分配空间时，进行字符串拼接时若预分配空间足够，则不需要重新分配空间，提高了效率.

最后此篇关于【Redis】字符串sds的文章就讲到这里了,如果你想了解更多关于【Redis】字符串sds的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： Flask结合gunicorn和nginx反向代理的生产环境部署及踩坑记录
文章推荐： AQS实现原理
文章推荐： 处理.git文件夹过大出现臃肿问题-filter-branch和BFG工具
文章推荐： 基于GPT搭建私有知识库聊天机器人（五）函数调用
我是一只小鸟
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com