Redis 源码分析（一）sds

2022-01-14 4 分钟阅读

SDS

作为Redis最基本的数据类型，SDS又进行了更细致的分类。主要区别在于字符串长度字段，对于长度较短的字符串其长度保存在flags字段中的高5位，flags的低3位保存字符串的类型。所有的flags字段在SDS结构中都使用一个无符号字节类型保存在具体的String前，SDS使用了buf[-1]的方式获取flags字段。

SDS 全称是Simple Dynamic String 动态扩展内存。特点如下：

  1. 内部为当前字符串实际分配的空间，一般要高于实际字符串的长度，当字符串的长度小于1M时，扩容都是扩一倍，如果超过1M，扩容是最多扩1M的空间，字符串的最大长度是512M
  2. 二进制安全（Binary Safe）。sds能存储任意二进制数据，而不仅仅是可打印字符。
  3. 与传统的C语言字符串类型兼容。

内存中的数据看起来是这样的： 

flowchart LR;
  HDR-->FLAGS[1 byte flags];
  FLAGS-->STR;

SDS 的结构定义如下：

 1/* Note: sdshdr5 is never used, we just access the flags byte directly.
 2 * However is here to document the layout of type 5 SDS strings. */
 3struct __attribute__ ((__packed__)) sdshdr5 {
 4    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
 5    char buf[];
 6};
 7struct __attribute__ ((__packed__)) sdshdr8 {
 8    uint8_t len; /* used */
 9    uint8_t alloc; /* excluding the header and null terminator */
10    unsigned char flags; /* 3 lsb of type, 5 unused bits */
11    char buf[];
12};
13struct __attribute__ ((__packed__)) sdshdr16 {
14    uint16_t len; /* used */
15    uint16_t alloc; /* excluding the header and null terminator */
16    unsigned char flags; /* 3 lsb of type, 5 unused bits */
17    char buf[];
18};
19struct __attribute__ ((__packed__)) sdshdr32 {
20    uint32_t len; /* used */
21    uint32_t alloc; /* excluding the header and null terminator */
22    unsigned char flags; /* 3 lsb of type, 5 unused bits */
23    char buf[];
24};
25struct __attribute__ ((__packed__)) sdshdr64 {
26    uint64_t len; /* used */
27    uint64_t alloc; /* excluding the header and null terminator */
28    unsigned char flags; /* 3 lsb of type, 5 unused bits */
29    char buf[];
30};

sds

其中 len 是字符串的长度，alloc 是可以存储的字符串最大长度（已经减掉了HDR和字符串结束符的长度。）

这样的好处是对不同长度的字符串使用不同长度的数据类型可以节省一定数量的字节。作为数据存储的中间件内存对Redis来说是有限的资源，所以Redis对内存的使用是非常谨慎的。在之后的代码中到处都是这种扣内存的地方，到时我会特意标注出来。

获取SDS长度使用了inline 函数

 1static inline size_t sdslen(const sds s) {
 2    unsigned char flags = s[-1];
 3    switch(flags&SDS_TYPE_MASK) {
 4        case SDS_TYPE_5:
 5            return SDS_TYPE_5_LEN(flags);
 6        case SDS_TYPE_8:
 7            return SDS_HDR(8,s)->len;
 8        case SDS_TYPE_16:
 9            return SDS_HDR(16,s)->len;
10        case SDS_TYPE_32:
11            return SDS_HDR(32,s)->len;
12        case SDS_TYPE_64:
13            return SDS_HDR(64,s)->len;
14    }
15    return 0;
16}

SDS_TYPE_5_LEN 是 SDS_TYPE_5专用的计算字符串长度的宏，其他类型使用的是SDS_HDR宏，该宏返回的是HDR指针对象。 需要注意的是，字符串长度返回的是size_t类型，所以32位的Redis实际上无法支持超过2G长度的文本。而在实际使用中一般也不建议字符串属性过长

SDS的所有操作都使用SDS系列函数，而非标准库提供的字符串操作函数。因为两种字符串的含义并不相同。

SDS 提供了一系列的字符串操作我在此做个罗列并解释其含义：

 1/// 通过init所指的原始字符串及initlen创建一个SDS字符串。由于内存对齐的问题，实际分配的内存会大于initlen。如果内存分配失败则会让Redis直接退出。
 2sds sdsnewlen(const void *init, size_t initlen);
 3/// 通过init所指的原始字符串及initlen创建一个SDS字符串。由于内存对齐的问题，实际分配的内存会大于initlen。如果内存分配失败则返回空指针
 4sds sdstrynewlen(const void *init, size_t initlen);
 5/// 通过init所指的原始字符串创建一个新的SDS字符串，内存分配失败会挂掉。
 6sds sdsnew(const char *init);
 7/// 分配一个空字符串，空字符串也需要分配内存，内存分配失败会挂掉。
 8sds sdsempty(void);
 9/// 复制一个SDS字符串
10sds sdsdup(const sds s);
11/// 释放SDS字符串内存
12void sdsfree(sds s);
13/// 增加字符串可用的空间。代码中的增长策略为
14/// len < SDS_MAX_PREALLOC : 扩展内存至要求的一倍
15/// 否则：扩展内存至要求内存 + SDS_MAX_PREALLOC
16/// 默认 SDS_MAX_PREALLOC 为 1M
17/// 这样做的好处是对于频繁变化长度的字符串，特别是频繁修改变长的字符串可以减少内存分配的频次提高可用性。
18/// 需要注意的是，输入的SDS字符串有可能失效
19sds sdsgrowzero(sds s, size_t len);
20/// 将t所指的字符串的len个字符接到SDS字符串s之后，叫appendlen更合适
21/// 需要注意的是，输入的SDS字符串有可能失效
22sds sdscatlen(sds s, const void *t, size_t len);
23/// 将t所指的字符串全部接到SDS字符串s之后，叫append更合适
24/// 需要注意的是，输入的SDS字符串有可能失效
25sds sdscat(sds s, const char *t);
26/// 字符串连接的SDS版本，实际上与sdscat没区别
27sds sdscatsds(sds s, const sds t);
28/// 字符串复制
29/// 需要注意的是，输入的SDS字符串有可能失效
30sds sdscpylen(sds s, const char *t, size_t len);
31/// 字符串复制
32/// 需要注意的是，输入的SDS字符串有可能失效
33sds sdscpy(sds s, const char *t);
34
35sds sdscatvprintf(sds s, const char *fmt, va_list ap);
36sds sdscatfmt(sds s, char const *fmt, ...);
37sds sdstrim(sds s, const char *cset);
38void sdssubstr(sds s, size_t start, size_t len);
39void sdsrange(sds s, ssize_t start, ssize_t end);
40void sdsupdatelen(sds s);
41void sdsclear(sds s);
42int sdscmp(const sds s1, const sds s2);
43sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
44void sdsfreesplitres(sds *tokens, int count);
45void sdstolower(sds s);
46void sdstoupper(sds s);
47sds sdsfromlonglong(long long value);
48sds sdscatrepr(sds s, const char *p, size_t len);
49sds *sdssplitargs(const char *line, int *argc);
50sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
51sds sdsjoin(char **argv, int argc, char *sep);
52sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);
53/* Callback for sdstemplate. The function gets called by sdstemplate
54 * every time a variable needs to be expanded. The variable name is
55 * provided as variable, and the callback is expected to return a
56 * substitution value. Returning a NULL indicates an error.
57 */
58typedef sds (*sdstemplate_callback_t)(const sds variable, void *arg);
59sds sdstemplate(const char *template, sdstemplate_callback_t cb_func, void *cb_arg);
60
61/* Low level functions exposed to the user API */
62sds sdsMakeRoomFor(sds s, size_t addlen);
63void sdsIncrLen(sds s, ssize_t incr);
64sds sdsRemoveFreeSpace(sds s);
65size_t sdsAllocSize(sds s);
66void *sdsAllocPtr(sds s);
67
68/* Export the allocator used by SDS to the program using SDS.
69 * Sometimes the program SDS is linked to, may use a different set of
70 * allocators, but may want to allocate or free things that SDS will
71 * respectively free or allocate. */
72void *sds_malloc(size_t size);
73void *sds_realloc(void *ptr, size_t size);
74void sds_free(void *ptr);

操作函数有点多，不过基本上是望文生义。感兴趣的可以去看Redis的源码

Redis 源码分析（二）adlist

相关文章

评论