Redis源码阅读一:简单动态字符串SDS

MLXY 2019-12-24

源码阅读基于Redis4.0.9

SDS介绍

redis 127.0.0.1:6379> SET dbname redis
OK
redis 127.0.0.1:6379> GET dbname
"redis"

从上面的例子可以看到,key为dbname的值是一个字符串“redis”
Redis源码是用c写成,但并没有使用c的字符串。c的字符串有以下缺点:

  1. 没有储存字符串长度的变量,获取长度只能靠遍历字符串
  2. 扩容麻烦。没有相应保护,容易造成缓冲区溢出
  3. 更新字符串需要重新分配内存
addrvalue
0x0s
0x1t
0x2r
0x31
0x4‘\0‘
0x5
0x6
0x7
0x8a
0x9b
0xa‘\0‘

解释下2,3点。上图是一段连续的内存,保存了字符串"str1"和“ab”。如果我们用strcat函数,拼接一个“append”在“str1”后面,就会对“ab”产生影响。造成内存的破坏。
同样的道理,想要更新字符串,同时又不造成溢出,只能重新分配一段内存。
普通的应用程序,上面的操作是可以接受的。但是redis作为数据库,经常增删改查,加上对速度有一定需求,所以不能使用C的字符串。
我们可以在src/sds.h中找到sds的声明:

typedef char *sds;

怎么回事?redis中的sds还是char* ,那不是和C字符串一样了吗?
其实这里只是为了兼容,而每个sds字符串前都有一个sds header,保存了该sds字符串的信息
下面是sdsnew函数,用来创建一个sds字符串

/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

/* for example mystring = sdsnewlen("abc",3); */
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);    //根据initlen的值计算出type类型
    /* 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. */

    /*给sds header分配空间*/
    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;
    /*根据type初始化sh的成员*/
    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';    //字符串最后添加'\0'进行兼容,使printf可以打印sds
    return s;
}

SDS header结构体

redis的SDS header结构体如下:

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
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[];
};

除了sdshdr5不被使用,剩下的只是长度的区别,成员是一样的。

  • buf[] 实际存储字符的数组
  • len 字符串长度
  • alloc 最大容量。等于len(buf)-1,因为字符串最后一位固定是‘\0‘
  • flags 低3位是类型,高5位保留

关于该结构体,还需要注意2点:

  1. attribute ((packed))是为了让编译器以紧凑的方式分配内存,否则编译器可能会对结构体的成员进行对齐优化。对这里不太明白的可以看看struct大小的计算
  2. 结构体的最后定义了char buf[]; 这个字段只能作为结构体的最后一个成员。C语言中被称为柔性数组,只是作为一个标记,不占用内存空间。
    如果明白了以上2点,应该能算出sizeof(sdshdr32)=4+4+1=9Byte

SDS优点

常数时间获取字符串长度

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    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 header中保存了字符串长度,所以直接读取sdshdr->len即可,消耗常数时间

相关推荐