本文共 12211 字，大约阅读时间需要 40 分钟。

基于Redis5.0

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。

SDS定义

//
   
    typedef char *sds;/* 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[];};//flag低3位保存sds类型，sdshdr5的flag高5位保存buf长度#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//过去指向sdshdr的指针，并赋给sh#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));//获取指向sdshdr结构体的指针#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))//获取sdshdr5的字符串长度，即flag字段中高5位存储的值#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
   

SDS_HDR --> | len | alloc | flag | buf（sds） |

• len ：sds的长度，不包括末尾结束符
• alloc ：分配的sds长度，不包括结束符
• flag ：sds类型
• buf ：sds实际存放位置

SDS 遵循 C 字符串以空字符结尾的惯例， 保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面， 并且为空字符分配额外的 1 字节空间，遵循空字符结尾这一惯例的好处是， SDS 可以直接重用一部分 C 字符串函数库里面的函数，末尾空字符的分配在sdsnewlen函数里（sh = s_malloc(hdrlen+initlen+1);），下面有完整函数代码

SDS与C字符串的区别

• 常数复杂度O(1)获取字符串长度

  获取一个 C 字符串的长度， 程序必须遍历整个字符串， 对遇到的每个字符进行计数， 直到遇到代表字符串结尾的空字符为止， 这个操作的复杂度为 O(N)
  SDS 在 len 属性中记录了 SDS 本身的长度， 所以获取一个 SDS 长度的复杂度仅为 O(1)

• 杜绝缓冲区溢出

  SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性： 当 SDS API 需要对 SDS 进行修改时， API 会先检查 SDS 的空间是否满足修改所需的要求， 如果不满足的话， API 会自动将 SDS 的空间扩展至执行修改所需的大小， 然后才执行实际的修改操作， 所以使用 SDS 既不需要手动修改 SDS 的空间大小， 也不会出现缓冲区溢出问题

• 减少修改字符串时带来的内存重分配次数

  C 字符串并不记录自身的长度， 所以对于一个包含了 N 个字符的 C 字符串来说， 这个 C 字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符），每次增长或者缩短一个 C 字符串， 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作，通过未使用空间（alloc - len）， SDS 实现了空间预分配和惰性空间释放两种优化策略
  • 空间预分配

    如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ， 那么程序分配和 len 属性同样大小的未使用空间， 这时 SDS alloc 属性的值将是和len 属性的2倍。 举个例子， 如果进行修改之后， SDS 的 len 将变成 13 字节， 那么程序也会分配 13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。

    如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB 的未使用空间。 举个例子， 如果进行修改之后， SDS 的 len 将变成 30 MB ， 那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。

    通过这种预分配策略， SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。

  • 惰性空间释放

    惰性空间释放用于优化 SDS 的字符串缩短操作： 当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用 free 属性将这些字节的数量记录起来， 并等待将来使用

    通过惰性空间释放策略， SDS 避免了缩短字符串时所需的内存重分配操作， 并为将来可能有的增长操作提供了优化

• 二进制安全

  C 字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据

  使用 SDS 来保存之前提到的特殊数据格式就没有任何问题， 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，通过使用二进制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不仅可以保存文本数据， 还可以保存任意格式的二进制数据

• 兼容部分 C 字符串函数

  SDS 的 API 都是二进制安全的， 但它们一样遵循 C 字符串以空字符结尾的惯例： 这些 API 总会将 SDS 保存的数据的末尾设置为空字符， 并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符， 这是为了让那些保存文本数据的 SDS 可以重用一部分

SDS API

//
   
    //获取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可用的字节数   /* sdsalloc() = sdsavail() + sdslen() */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;}
   

创建一个sds字符串的核心函数：

/* Create a new sds string with the content specified by the 'init' pointer * and 'initlen'. * If NULL is used for 'init' the string is initialized with zero bytes. * If SDS_NOINIT is used, the buffer is left uninitialized; * * The string is always null-termined (all the sds strings are, always) so * even if you create an sds string with: * * mystring = sdsnewlen("abc",3); * * You can print the string with printf() as there is an implicit \0 at the * end of the string. However the string is binary safe and can contain * \0 characters in the middle, as the length is stored in the sds header. */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. */	//为结尾空字符多分配1字节的空间    sh = s_malloc(hdrlen+initlen+1);    if (init==SDS_NOINIT)        init = NULL;    else 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;}

扩容的核心函数：

//#define SDS_MAX_PREALLOC (1024*1024)/* Enlarge the free space at the end of the sds string so that the caller * is sure that after calling this function can overwrite up to addlen * bytes after the end of the string, plus one more byte for nul term. * * Note: this does not change the *length* of the sds string as returned * by sdslen(), but only the free buffer space we have. */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);    if (newlen < SDS_MAX_PREALLOC) //SDS_MAX_PREALLOC (1024*1024) = 1M        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);    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 */        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;}

对给定字符或字符串进行分割：

/* Split 's' with separator in 'sep'. An array * of sds strings is returned. *count will be set * by reference to the number of tokens returned. * * On out of memory, zero length string, zero length * separator, NULL is returned. * * Note that 'sep' is able to split a string using * a multi-character separator. For example * sdssplit("foo_-_bar","_-_"); will return two * elements "foo" and "bar". * * This version of the function is binary-safe but * requires length arguments. sdssplit() is just the * same function but for zero-terminated strings. */sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count) {
       int elements = 0, slots = 5;    long start = 0, j;    sds *tokens;    if (seplen < 1 || len < 0) return NULL;		//tokens相当于是一个二维数组，默认先分配五个指针内存，即可以存5个被分割的字符串    tokens = s_malloc(sizeof(sds)*slots);    if (tokens == NULL) return NULL;    if (len == 0) {
           *count = 0;        return tokens;    }    for (j = 0; j < (len-(seplen-1)); j++) {
           /* make sure there is room for the next element and the final one */        if (slots < elements+2) {
               sds *newtokens;            slots *= 2;            newtokens = s_realloc(tokens,sizeof(sds)*slots);            if (newtokens == NULL) goto cleanup;            tokens = newtokens;        }        /* search the separator */        if ((seplen == 1 && *(s+j) == sep[0]) || (memcmp(s+j,sep,seplen) == 0)) {
               tokens[elements] = sdsnewlen(s+start,j-start);            if (tokens[elements] == NULL) goto cleanup;            elements++;            start = j+seplen;            j = j+seplen-1; /* skip the separator */        }    }    /* Add the final element. We are sure there is room in the tokens array. */    tokens[elements] = sdsnewlen(s+start,len-start);    if (tokens[elements] == NULL) goto cleanup;    elements++;    *count = elements;    return tokens;cleanup:    {
           int i;        for (i = 0; i < elements; i++) sdsfree(tokens[i]);        s_free(tokens);        *count = 0;        return NULL;    }}

返回指定范围内的字符串：

/* Turn the string into a smaller (or equal) string containing only the * substring specified by the 'start' and 'end' indexes. * * start and end can be negative, where -1 means the last character of the * string, -2 the penultimate character, and so forth. * * The interval is inclusive, so the start and end characters will be part * of the resulting string. * * The string is modified in-place. * * Example: * * s = sdsnew("Hello World"); * sdsrange(s,1,-1); => "ello World" */void sdsrange(sds s, ssize_t start, ssize_t end) {
       size_t newlen, len = sdslen(s);    if (len == 0) return;    if (start < 0) {
           start = len+start;        if (start < 0) start = 0;    }    if (end < 0) {
           end = len+end;        if (end < 0) end = 0;    }    newlen = (start > end) ? 0 : (end-start)+1;    if (newlen != 0) {
           if (start >= (ssize_t)len) {
               newlen = 0;        } else if (end >= (ssize_t)len) {
               end = len-1;            newlen = (start > end) ? 0 : (end-start)+1;        }    } else {
           start = 0;    }    if (start && newlen) memmove(s, s+start, newlen);    s[newlen] = 0;    sdssetlen(s,newlen);}

转载地址：http://ouhpi.baihongyu.com/