REDIS简单动态字符串

REDIS简单动态字符串

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

举个例子：

redis> SET msg "hello world"
OK

执行上诉语句之后，redis 将在数据库中创建一个新的键值对，该键值对包括：

  • 键是一个字符串对象，底层实现是一个保存着字符串 "msg" 的 SDS
  • 值也是一个字符串对象，底层实现是一个保存着字符串 "hello world" 的 SDS。

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 {
    //记录buf数组中已使用的字节数量
    uint64_t len;
    //分配的buf数组长度，不包括头和空字符结尾
    uint64_t alloc;
    // 标志位， 最低3位表示类型，另外5个位没有使用
    unsigned char flags;
    char buf[];
};

通过源码可以看出 SDS 有5中 header 类型，主要是为了让不同的字符串使用不同程度的header，从而节省内存。

SDS 结构体的组成：

  1. len 记录 buf 数组中已使用的字节数量
  2. alloc 分配的 buf 数组长度，不包括头和空字符结尾
  3. flags 标志位，最低3为表示 header 类型，另外 5 个位没有使用。类型对应下面5中类型。
#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
  1. buf[] 字符数组，用于存放字符串。

redis 虽然不是使用 c 中的字符串格式，但是遵循了 c 字符串以空字符结尾的惯例，保存空字符的 1 个字节不计算在 SDS 的 len 属性里。这样做的好处是，可以直接重用一部分 c 字符串函数库里面的函数。

SDS相对C字符串的优势

获取字符串的长度复杂度为 O(1)

由于 C 字符串并不记录自身的长度信息，所以为了获取一个 C 字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为 O(N) 。

和C字符串不同，因为SDS在len属性中记录了SDS 身的长度，写代码时只要直接获取len属性值，就可以知道字符串长度，所以获取一个SDS长度的复杂度仅为 O(1) 。

防止缓冲去溢出（buffer overflow）

举个例子，<string.h>/strcat 函数可以将 src 字符串中的内容拼接到 dest 字符串的末尾：

char *strcat(char *dest, const char *src);

因为 C 字符串不记录自身的长度，所以 strcat 假定用户在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢出。

举个例子，假设程序里有两个在内存中紧邻着的 C 字符串 s1 和 s2 ，其中 s1 保存了字符串 "hello" ，而 s2 则保存了字符串 "redis"，如下所示：

此时，如果执行：

strcat(s1,' world')

将 s1 的内容修改为 "hello world" ，但粗心的他却忘了在执行 strcat 之前为 s1 分配足够的空间，那么在 strcat 函数执行之后，s1 的数据将溢出到 s2 所在的空间中，导致 s2 保存的内容被意外地修改。

与 c 字符串不同的是

SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：

当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小（即：sdsMakeRoomFor），然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出问题。

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);
    s[curlen+len] = '\0';
    return s;
}

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

因为 C 字符串的长度和底层数组的长度之间存在着关联性， 所以每次增长或者缩短一个 C 字符串， 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作：

  • 如果程序执行的是增长字符串的操作， 比如拼接操作（append）， 那么在执行这个操作之前， 程序需要先通过内存重分配来扩展底层数组的空间大小 —— 如果忘了这一步就会产生缓冲区溢出。
  • 如果程序执行的是缩短字符串的操作， 比如截断操作（trim）， 那么在执行这个操作之后， 程序需要通过内存重分配来释放字符串不再使用的那部分空间 —— 如果忘了这一步就会产生内存泄漏。

因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作：

  • 在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配是可以接受的。
  • Redis 作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分，如果这种修改频繁地发生的话，可能还会对性能造成影响。

为了避免 C 字符串的这种缺陷， SDS 通过已使用空间解除了字符串长度和底层数组长度之间的关联，在更改字符串的时候可以只更改len属性，而不重新分配内存。

空间预分配

对字符串进行增长操作时，会使用一个sdsMakeRoomFor函数来扩展字符串。

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)
        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;
}

sdsMakeRoomFor是sds实现中很重要的一个函数。关于它的实现代码，我们需要注意的是：

  • 如果原来字符串中的空余空间够用（avail >= addlen），那么它什么也不做，直接返回。
  • 如果需要分配空间，它会比实际请求的要多分配一些，以防备接下来继续追加。它在字符串已经比较长（长度将大于等于 1 MB）的情况下要至少多分配 SDS_MAX_PREALLOC 个字节，这个常量在sds.h中定义为(1024*1024)=1MB。
  • 按分配后的空间大小，可能需要更换 header 类型（原来 header 的 alloc 字段太短，表达不了增加后的容量）。
  • 如果需要更换 header，那么整个字符串空间（包括 header ）都需要重新分配（s_malloc），并拷贝原来的数据到新的位置。
  • 如果不需要更换header（原来的 header 够用），那么调用一个比较特殊的 s_realloc，试图在原来的地址上重新分配空间。s_realloc 的具体实现得看Redis编译的时候选用了哪个 allocator（在Linux上默认使用jemalloc）。但不管是哪个 realloc 的实现，它所表达的含义基本是相同的：它尽量在原来分配好的地址位置重新分配，如果原来的地址位置有足够的空余空间完成重新分配，那么它返回的新地址与传入的旧地址相同；否则，它分配新的地址块，并进行数据搬迁。

总结：在扩展SDS空间之前， SDS API 会先检查未使用空间是否足够， 如果足够的话， API 就会直接使用未使用空间， 而无须执行内存重分配。通过这样的空间预分配策略， Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作： 当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是把缩短后的长度记录在len属性中，剩余空间用于未来扩展字符串用。

如 sdstrim 函数：

/* Remove the part of the string from left and from right composed just of
 * contiguous characters found in 'cset', that is a null terminted C string.
 *
 * After the call, the modified sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call.
 *
 * Example:
 *
 * s = sdsnew("AA...AA.a.aa.aHelloWorld     :::");
 * s = sdstrim(s,"Aa. :");
 * printf("%s\n", s);
 *
 * Output will be just "HelloWorld".
 */
sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    if (s != sp) memmove(s, sp, len);
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}

可以看出程序结束时并没有reallocate内存空间，而是修改结构体中len的属性。
当用户真正想free掉空闲空间时，可以使用sdsRemoveFreeSpace函数：

/* Reallocate the sds string so that it has no free space at the end.
 * 重新分配sds字符串，使其末尾没有可用空间。
 * The contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 * 其中包含的字符串保持不变，但进行后续连接操作将需要重新分配。
 *
 * 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字符串不再有效，并且所有引用必须替换为调用返回的新指针。
 */
sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    size_t len = sdslen(s);
    size_t avail = sdsavail(s);
    sh = (char*)s-oldhdrlen;

    /* Return ASAP if there is no space left. */
    if (avail == 0) return s;

    /* Check what would be the minimum SDS header that is just good enough to
     * fit this string. */
    type = sdsReqType(len);
    hdrlen = sdsHdrSize(type);

    /* If the type is the same, or at least a large enough type is still
     * required, we just realloc(), letting the allocator to do the copy
     * only if really needed. Otherwise if the change is huge, we manually
     * reallocate the string to use the different header type. */
    if (oldtype==type || type > SDS_TYPE_8) {
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } else {
        newsh = s_malloc(hdrlen+len+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, len);
    return s;
}

可以存放二进制数据

C 字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
因此， 为了确保 Redis 可以适用于各种不同的使用场景， SDS 的 API 都是二进制安全的（binary-safe）： 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据， 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的， 它被读取时就是什么样。

这也是我们将 SDS 的 buf 属性称为字节数组的原因 —— Redis 不是用这个数组来保存字符， 而是用它来保存一系列二进制数据。

SDS相关 API 总结

参考书籍：Redis 设计与实现

函数 作用 时间复杂度
sdsnew 创建一个包含给定 C 字符串的 SDS 。 O(N) ， N 为给定 C 字符串的长度。
sdsempty 创建一个不包含任何内容的空 SDS 。 O(1)
sdsfree 释放给定的 SDS 。 O(1)
sdslen 返回 SDS 的已使用空间字节数。 这个值可以通过读取 SDS 的 len 属性来直接获得，复杂度为 O(1) 。
sdsavail 返回 SDS 的未使用空间字节数。 这个值可以通过读取 SDS 的 free 属性来直接获得，复杂度为 O(1) 。
sdsdup 创建一个给定 SDS 的副本（copy）。 O(N) ， N 为给定 SDS 的长度。
sdsclear 清空 SDS 保存的字符串内容。 因为惰性空间释放策略，复杂度为 O(1) 。
sdscat 将给定 C 字符串拼接到 SDS字符串的末尾。 O(N) ， N 为被拼接 C 字符串的长度。
sdscatsds 将给定 SDS 字符串拼接到另一个 SDS字符串的末尾。 O(N) ， N 为被拼接 SDS 字符串的长度。
sdscpy 将给定的 C 字符串复制到 SDS 里面，覆盖 SDS 原有的字符串。 O(N) ， N 为被复制 C 字符串的长度。
sdsgrowzero 用空字符将 SDS 扩展至给定长度。 O(N) ， N 为扩展新增的字节数。
sdsrange 保留 SDS 给定区间内的数据，不在区间内的数据会被覆盖或清除。 O(N) ， N 为被保留数据的字节数。
sdstrim 接受一个 SDS 和一个 C 字符串作为参数，从 SDS 左右两端分别移除所有在 C字符串中出现过的字符。 O(M*N) ， M 为 SDS 的长度，N 为给定 C 字符串的长度。
sdscmp 对比两个 SDS 字符串是否相同。 O(N) ， N 为两个 SDS 中较短的那个 SDS的长度。

字符串相关命令及解释

  • SET

如果 key 已经持有其他值，SET 就覆写旧值，无视类型。

当 SET 命令对一个带有生存时间（TTL）的键进行设置之后，该键原有的 TTL 将被清除。

  • SETNX

只在键 key 不存在的情况下，将键 key 的值设置为 value 。

若键 key 已经存在，则 SETNX 命令不做任何动作。

  • SETEX

将键 key 的值设置为 value ，并将键 key 的生存时间设置为 seconds 秒钟。

如果键 key 已经存在，那么 SETEX 命令将覆盖已有的值。

SET key value
EXPIRE key seconds  # 设置生存时间

SETEX 和这两个命令的不同之处在于 SETEX 是一个原子（atomic）操作，它可以在同一时间内完成设置值和设置过期时间这两个操作，因此 SETEX 命令在储存缓存的时候非常实用。

  • PSETEX

这个命令和 SETEX 命令相似，但它以毫秒为单位设置 key 的生存时间，

  • GET

返回与键 key 相关联的字符串值。

  • GETSET

将键 key 的值设为 value ，并返回键 key 在被设置之前的旧值。

  • STRLEN

返回键 key 储存的字符串值的长度。

  • APPEND

如果键 key 已经存在并且它的值是一个字符串，APPEND 命令将把 value 追加到键 key 现有值的末尾。

如果 key 不存在，APPEND 就简单地将键 key 的值设为 value ，就像执行 SET key value 一样。

  • SETRANGE (SETRANGE key offset value)

从偏移量 offset 开始，用 value 参数覆写(overwrite)键 key 储存的字符串值。

不存在的键 key 当作空白字符串处理。

SETRANGE 命令会确保字符串足够长以便将 value 设置到指定的偏移量上，如果键 key 原来储存的字符串长度比偏移量小(比如字符串只有 5 个字符长，但你设置的 offset 是 10 )，那么原字符和偏移量之间的空白将用零字节(zerobytes, "\x00" )进行填充。

  • GETRANGE (GETRANGE key start end)

返回键 key 储存的字符串值的指定部分，字符串的截取范围由 start 和 end 两个偏移量决定(包括 start 和 end 在内)。

  • INCR

为键 key 储存的数字值加上一。

如果键 key 不存在，那么它的值会先被初始化为 0 ，然后再执行 INCR 命令。

如果键 key 储存的值不能被解释为数字，那么 INCR 命令将返回一个错误。

本操作的值限制在 64 位(bit)有符号数字表示之内。

  • INCRBY

为键 key 储存的数字值加上增量 increment 。

如果键 key 不存在，那么键 key 的值会先被初始化为 0 ，然后再执行 INCRBY 命令。

如果键 key 储存的值不能被解释为数字，那么 INCRBY 命令将返回一个错误。

本操作的值限制在 64 位(bit)有符号数字表示之内。

  • INCRBYFLOAT

为键 key 储存的值加上浮点数增量 increment

  • DECR

为键 key 储存的数字值减去一

  • DECRBY

将键 key 储存的整数值减去减量 decrement 。

EG: DECRBY key decrement

  • MSET (MSET key value [key value …])

如果某个给定键已经存在，那么 MSET 将使用新值去覆盖旧值，如果这不是你所希望的效果，请考虑使用 MSETNX 命令，这个命令只会在所有给定键都不存在的情况下进行设置。

MSET 是一个原子性(atomic)操作，所有给定键都会在同一时间内被设置，不会出现某些键被设置了但是另一些键没有被设置的情况。

  • MSETNX

当且仅当所有给定键都不存在时，为所有给定键设置值。

即使只有一个给定键已经存在，MSETNX 命令也会拒绝执行对所有键的设置操作。

MSETNX 是一个原子性(atomic)操作，所有给定键要么就全部都被设置，要么就全部都不设置，不可能出现第三种状态。

  • MGET

返回给定的一个或多个字符串键的值。

如果给定的字符串键里面，有某个键不存在，那么这个键的值将以特殊值 nil 表示。

赞 (0)

相关推荐