51工具盒子

依楼听风雨
笑看云卷云舒,淡观潮起潮落

Redis数据结构-SDS

Redis数据结构-SDS {#redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-sds}

Redis中的String类型有有三种编码方式:intembstrraw

  • int:保存long型(长整型)的64位(8个字节)有符号整数。范围是[-2^63^,2^63^-1],也就是[-9223372036854775808,9223372036854775807],最多19位。

    注意:只有整数才会使用int,如果是浮点数,Redis内部其实是先将浮点数转化为字符串值之后再保存。

    127.0.0.1:6379> SET k1 1.1111111
    OK
    127.0.0.1:6379> OBJECT ENCODING k1
    "embstr"
    
  • embstr:代表embstr格式的SDSSimple Dynamic String-简单动态字符串 ),保存长度小于44字节的字符串。embstr(embedded string),顾名思义表示嵌入式的String。

  • raw:保存长度大于44字节的字符串。

下面我们测试3个key:

  • k1的长度为9,可以看到编码方式是int
  • k2长度大于19,编码方式则为embstr
  • k3的长度大于44,编码方式则为raw
127.0.0.1:6379> SET k1 123456789
OK
127.0.0.1:6379> OBJECT ENCODING k1
"int"
127.0.0.1:6379> SET k2 123456789123456789123
OK
127.0.0.1:6379> OBJECT ENCODING k2
"embstr"
127.0.0.1:6379> SET k3 123456789123456789123456789123456789123456789123456789123456789123456789123456789
OK
127.0.0.1:6379> OBJECT ENCODING k3
"raw"

SDS(Simple Dynamic String-简单动态字符串) {#sds%EF%BC%88simple-dynamic-string-%E7%AE%80%E5%8D%95%E5%8A%A8%E6%80%81%E5%AD%97%E7%AC%A6%E4%B8%B2%EF%BC%89}

上面我们说到了SDSSimple Dynamic String-简单动态字符串)。那么它是什么呢?

Redis是用C语言实现的,但是它没有直接使用C语言的char*字符数组来实现字符串,而是自己封装了一个名为SDSSimple Dynamic String-简单动态字符串 )的数据结构来表示字符串,也就是 Redis的String数据类型的底层数据结构是SDS

Redis中所有的key以及所有值对象中包含的字符串对象底层都是由SDS实现的。

SDS结构设计 {#sds%E7%BB%93%E6%9E%84%E8%AE%BE%E8%AE%A1}

源码sds.h中是这样写的:

/* 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[];
};
//和上面的不同只有len和alloc,也就是长度不同而已
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[];
};
//和上面的不同只有len和alloc,也就是长度不同而已
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[];
};
//和上面的不同只有len和alloc,也就是长度不同而已
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[];
};
  • len:直接记录字符串的长度,这样在获取字符串长度的时候直接返回这个字段的值即可,时间复杂度是O(1)。

  • alloc:分配给字符数组的空间长度。可以通过alloc-len计算出剩余的空间大小,在修改字符串的时候,可以判断剩余空间是否满足,不满足的话,会自动将SDS扩容至修改所需要的大小。所以使用SDS既不需要手动修改SDS的空间大小,也不会出现前面所说的缓冲区溢出的问题。

  • flags:这个就是用来表示不同类型的SDS。从上面的源码可以看到一共设计了5种类型:sdshdr5sdshdr8sdshdr16sdshdr32sdshdr64

    可以看到不同长度的SDS结构基本一样,只有sdshdr5不一样,但是注释中也说了不会使用到。

  • buf[]:字符数组,用来保存实际数据。不仅可以保存字符串,也可以保存二进制数据。

Redis为什么要自己设计一个SDS {#redis%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E8%87%AA%E5%B7%B1%E8%AE%BE%E8%AE%A1%E4%B8%80%E4%B8%AAsds}

Redis选择自己设计一个SDS结构来表示字符串,那是否说明C语言中char*字符数组存在一些缺陷?

首先C语言的字符串其实就是一个字符数组,即数组中每个元素是字符串中的一个字符。

# +-----+-----+-----+-----+-----+------+
# |  R  |  E  |  D  |  I  |  S  |  \0  |
# +-----+-----+-----+-----+-----+------+
  1. C语言中获取字符串长度的时间复杂度为O(n)。
  2. 还有就是除了字符串的末尾之外,字符串里面不能含有\0字符,否则最先被程序读入的\0字符将被误认为是字符串结尾,这个限制使得C语言的字符串只能保存文本数据,不能保存像图片、音频、视频文化这样的二进制数据。
  3. 字符串操作函数不高效且不安全,比如有缓冲区溢出的风险,有可能会造成程序运行终止。

SDS和C语言中的char*对比:

| | C语言 | SDS | | 对字符串长度的处理 | 需要从头开始遍历,直到遇到\0为止,时间复杂度是O(n) | 直接记录当前字符串的长度,获取的时候直接返回`len`即可,时间复杂度O(1) | | 内存重新分配 | 分配的内存空间超过之后,会导致数组下标越界或者内存分配溢出 | * 空间预分配:比如SDS修改后: * len长度小于1M,那么将会额外分配和len相同长度的未使用空间。 * len长度大于1M,那么将分配1M的空间。 * 惰性空间释放:既然有空间分配那就有空间释放。SDS缩短的时候并不会回收多余的内存空间,而是使用free字段将多出来的空间记录下来。如果后续有变更操作,直接使用free字段中记录的空间,减少了内存的分配。 | | 二进制安全 | 二进制数据并不是规则的字符串格式,可能会包含一些特殊的字符,比如\0这样的。上面说到C语言的char*\0表示结束,这样\0后面的数据就会读取不到了 | SDS是根据len长度来判断字符串结束的。 | |-----------|-------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|

3个编码方式的源码分析 {#3%E4%B8%AA%E7%BC%96%E7%A0%81%E6%96%B9%E5%BC%8F%E7%9A%84%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90}

当我们使用Redis的String类型的命令(比如SET k1 v1)来设置值的时候,Redis底层是怎么处理的呢?

源码t_string.c中有个函数setCommand(client *c)是这样写的:

/* SET key value [NX] [XX] [KEEPTTL] [GET] [EX <seconds>] [PX <milliseconds>]
 *     [EXAT <seconds-timestamp>][PXAT <milliseconds-timestamp>] */
void setCommand(client *c) {
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    int flags = OBJ_NO_FLAGS;
    if (parseExtendedStringArgumentsOrReply(c,&flags,&unit,&expire,COMMAND_SET) != C_OK) {
        return;
    }
    c->argv[2] = tryObjectEncoding(c->argv[2]);
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

可以看到上面代码中第#10行调用了一个名为tryObjectEncoding的函数,也就是尝试对数据编码,这个函数的源码在object.c中,如下:

/*尝试将字符串对象编码以节省空间*/
robj *tryObjectEncoding(robj *o) {
	long value;
	sds s = o->ptr;
	size_t len;
    /* 确保这是一个字符串对象,因为我们只在这个函数中编码字符串对象。
     * 其他类型使用编码内存效率高的表示形式,但由其类型的命令来处理。*/
	serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);
    /* 只为仍由实际字符数组表示的RAW或EMBSTR编码的对象尝试一些专门的编码。*/
	if (!sdsEncodedObject(o)) return o;
    /* 编码共享对象是不安全的:共享对象可以在Redis的"对象空间"中的任何地方共享,并可能出现在未处理的地方。
     * 我们只将它们作为键空间中的值来处理。*/
    if (o->refcount > 1) return o;
    /* 检查是否可以将此字符串表示为长整数。请注意,我们确信长于20个字符的字符串不能表示为32位或64位整数。*/
    len = sdslen(s);
    if (len <= 20 && string2l(s,len,&value)) {
        /* 表示这个对象可以被编码为long并尝试使用共享对象。
		* 请注意,在使用maxmemory时,我们避免使用共享整数,
		* 这是因为每个对象都需要一个私有的LRU字段,以便LRU算法能够正常工作。*/
        if ((server.maxmemory == 0 ||
            !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
            value >= 0 &&
            value < OBJ_SHARED_INTEGERS){
            	decrRefCount(o);
            	return shared.integers[value];
        } else {
            if (o->encoding == OBJ_ENCODING_RAW) {
                sdsfree(o->ptr);
                o->encoding = OBJ_ENCODING_INT;
                o->ptr = (void*) value;
                return o;
            } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
                decrRefCount(o);
                return createStringObjectFromLongLongForValue(value);
            }
        }
    }
    /* 如果字符串很小且仍以RAW编码,则尝试更高效的EMBSTR编码。
     * 在此表示中,对象和SDS字符串在同一块内存中分配,以节省空间和缓存未命中。 */
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;
        if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }
    /* 不能编码这个对象,最后尝试一下,至少优化SDS字符串内部 */
    trimStringObjectIfNeeded(o, 0);
    /* 返回原始对象。 */
    return o;
}

INT编码 {#int%E7%BC%96%E7%A0%81}

当字符串键值的内容可以用一个64位有符号的整形来表示的时候,Redis会将键值转换为long型来存储,此时对应的就是OBJ_ENCODING_INT编码类型。

在源码server.h中可以看到Redis启动的时候会预先建立10000个分别存储[0,9999]的redisObject作为共享对象,也就是说当我们使用SET命令的时候,如果值在[0,9999]之间的话,则可以直接指向共享对象而不需要建立新对象,此时的键值不占空间。

/* Static server configuration */
#define OBJ_SHARED_INTEGERS 10000

EMBSTR编码 {#embstr%E7%BC%96%E7%A0%81}

可以看到上面源码中的第#40行,对于长度小于OBJ_ENCODING_EMBSTR_SIZE_LIMIT(44),Redis会采用OBJ_ENCODING_EMBSTR的方式,embedded string表示嵌入式String:从内存结构上来讲,就是SDS 结构体和它对应的redisObject对象分配在同一块连续的内存空间,就像字符串SDS 嵌入在redisObject对象之中一样。

然后在上面的第#43调用了一个函数createEmbeddedStringObject来创建一个EmbStr对象,其源码也是在object.c中如下:

/* 如果字符串对象比OBJ_ENCODING_EMBSTR_SIZE_LIMIT小,则使用EMBSTR编码创建字符串对象,否则使用RAW编码。
 * 当前的限制为44,是为了使我们分配的最大字符串对象作为EMBSTR仍适合于jemalloc的64字节arena。*/
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
/* 创建一个字符串对象,其编码为OBJ_ENCODING_EMBSTR,即sds字符串实际上是一个不可修改的字符串,分配在与对象本身相同的块中。*/
robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
    struct sdshdr8 *sh = (void*)(o+1);
    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;
    o->ptr = sh+1;
    o->refcount = 1;
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    sh->len = len;
    sh->alloc = len;
    sh->flags = SDS_TYPE_8;
    if (ptr == SDS_NOINIT)
        sh->buf[len] = '\0';
    else if (ptr) {
        memcpy(sh->buf,ptr,len);
        sh->buf[len] = '\0';
    } else {
        memset(sh->buf,0,len+1);
    }
    return o;
}

RAW编码 {#raw%E7%BC%96%E7%A0%81}

当字符串的长度大于OBJ_ENCODING_EMBSTR_SIZE_LIMIT的时候,Redis则会将编码方式改为OBJ_ENCODING_RAW格式,这和OBJ_ENCODING_EMBSTR编码方式的不同之处在于:此时SDS 的内存和其依赖的redisObject的内存就不再连续了。

注意这里存在一个问题:在没有超过OBJ_ENCODING_EMBSTR_SIZE_LIMIT的时候,还是变成了RAW编码。

127.0.0.1:6379> SET k1 abc
OK
127.0.0.1:6379> OBJECT ENCODING k1
"embstr"
127.0.0.1:6379> APPEND k1 def
(integer) 6
127.0.0.1:6379> get k1
"abcdef"
127.0.0.1:6379> OBJECT ENCODING k1
"raw"

因为embstr的实现是只读的,在对embstr对象进行修改的时候(比如上面操作的APPEND),都会先转化成RAW然后在修改。所以只要是修改embstr编码的数据,修改后无论其长度是多少,其编码方式一定是RAW

编码转变的流程图 {#%E7%BC%96%E7%A0%81%E8%BD%AC%E5%8F%98%E7%9A%84%E6%B5%81%E7%A8%8B%E5%9B%BE}

Y Y Y Y N N N N 开始 是否embstr 或者raw 长度小于20? 且可以转换为long 长度小于44? 使用了maxmemory配置 或者不在[0,9999]内 从共享对象获取 编码为embstr 返回原始对象 根据embstr或者raw分别处理 结束

结论 {#%E7%BB%93%E8%AE%BA}

在Redis的String类型的底层数据结构中只有整数才会使用int编码方式,对于浮点数Redis内部实际上会先把浮点数转化成字符串之后再保存。

embstrraw编码其实都是SDSSimple Dynamic String-简单动态字符串),这是Redis内部自己定义的一种结构。

这三种编码方式的区别是:

| INT | EMBSTR | RAW | |---------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------| | 当为Long类型的整数时,redisObject中的ptr指针直接赋值为整数数据,不再额外地指向整数了,节省了指针的空间开销。 | 当保存的是字符串数据且长度小于44字节的时候,embstr会调用内存分配函数,只分配一块连续的内存空间,空间中一次包含redisObjectSDS两个数据结构,使元数据、指针和SDS是一块连续的内存区域,从而避免内存岁碎片。 | 当保存的是字符串数据且长度大于44字节的时候,redisObject的和SDS不再是连续的内存区域,会重新给SDS分配内存空间并用指针指向它。RAW会调用两次内存分配函数,分配两块内存空间,一块用来包含redisObject,另外一块用来包含SDS。 |

  • INT

    #  redisObject
    # +------------+
    # |    type    |=====>(REDIS_STRING)
    # +------------+
    # |  encoding  |=====>(OBJ_ENCODING_INT)
    # +------------+
    # |    lru     |
    # +------------+
    # |  refcount  |
    # +------------+
    # |  ptr(123)  |
    # +------------+
    
  • EMB

    #  redisObject
    # +------------+
    # |    type    |=====>(REDIS_STRING)
    # +------------+
    # |  encoding  |=====>(OBJ_ENCODING_EMBSTR)
    # +------------+
    # |    lru     |
    # +------------+
    # |  refcount  |
    # +------------+
    # |    ptr     |
    # +------------+
    # |    len     |
    # +------------+
    # |   alloc    |
    # +------------+
    # |   flags    |
    # +------------+
    # | buf("abc") |
    # +------------+
    
  • RAW

    #  redisObject
    # +------------+
    # |    type    |=====>(REDIS_STRING)
    # +------------+
    # |  encoding  |=====>(OBJ_ENCODING_RAW)
    # +------------+
    # |    lru     |
    # +------------+
    # |  refcount  |            SDS
    # +------------+      +-------------+
    # |    ptr     |=====>|     len     |					
    # +------------+      +-------------+
    #                     |    alloc    |
    #                     +-------------+
    #                     |    flags    |
    #                     +-------------+
    #                     |buf("xyz...")|
    #                     +-------------+
    
赞(0)
未经允许不得转载:工具盒子 » Redis数据结构-SDS