String 实现

Redis String 类型实现 #

Redis 中的字符串是一种 动态字符串,这意味着使用者可以修改,它的底层实现有点类似于 Java 中的 ArrayList,有一个字符数组,从源码的 sds.h/sdshdr 文件 中可以看到 Redis 底层对于字符串的定义 SDS,即 Simple Dynamic String 结构:

/* 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[];
};

你会发现同样一组结构 Redis 使用泛型定义了好多次,为什么不直接使用 int 类型呢?

因为当字符串比较短的时候,len 和 alloc 可以使用 byte 和 short 来表示,Redis 为了对内存做极致的优化,不同长度的字符串使用不同的结构体来表示。

SDS 与 C 字符串的区别 #

为什么不考虑直接使用 C 语言的字符串呢?

C 字符串太简单 #

因为 C 语言这种简单的字符串表示方式 不符合 Redis 对字符串在安全性、效率以及功能方面的要求。

C 语言使用了一个长度为 N+1 的字符数组来表示长度为 N 的字符串,并且字符数组最后一个元素总是 ‘\0’。

这样简单的数据结构可能会造成以下一些问题:

  • 获取字符串长度为 O (N) 级别的操作 → 因为 C 不保存数组的长度,每次都需要遍历一遍整个数组;
  • 不能很好的杜绝 缓冲区溢出 / 内存泄漏 的问题 → 跟上述问题原因一样,如果执行拼接 or 缩短字符串的操作,如果操作不当就很容易造成上述问题;
  • C 字符串 只能保存文本数据 → 因为 C 语言中的字符串必须符合某种编码(比如 ASCII),例如中间出现的 ‘\0’ 可能会被判定为提前结束的字符串而识别不了;

以追加字符串的操作举例,Redis 源码如下:

/* 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);     // 设置追加后的长度
    s[curlen+len] = '\0';         // 让字符串以 \0 结尾,便于调试打印
    return s;
}

参考 #


本文访问量

本站总访问量

本站总访客数