Redis数据结构-SDS {#redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-sds}
Redis中的String类型有有三种编码方式:
int
、embstr
、raw
。
-
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
格式的SDS (Simple 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}
上面我们说到了SDS (Simple Dynamic String-简单动态字符串)。那么它是什么呢?
Redis是用C语言实现的,但是它没有直接使用C语言的char*
字符数组来实现字符串,而是自己封装了一个名为SDS (Simple 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种类型:sdshdr5
、sdshdr8
、sdshdr16
、sdshdr32
和sdshdr64
。可以看到不同长度的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 |
# +-----+-----+-----+-----+-----+------+
- C语言中获取字符串长度的时间复杂度为O(n)。
- 还有就是除了字符串的末尾之外,字符串里面不能含有
\0
字符,否则最先被程序读入的\0
字符将被误认为是字符串结尾,这个限制使得C语言的字符串只能保存文本数据,不能保存像图片、音频、视频文化这样的二进制数据。 - 字符串操作函数不高效且不安全,比如有缓冲区溢出的风险,有可能会造成程序运行终止。
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内部实际上会先把浮点数转化成字符串之后再保存。
而embstr
和raw
编码其实都是SDS (Simple Dynamic String-简单动态字符串),这是Redis内部自己定义的一种结构。
这三种编码方式的区别是:
| INT
| EMBSTR
| RAW
|
|---------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------|
| 当为Long类型的整数时,redisObject
中的ptr
指针直接赋值为整数数据,不再额外地指向整数了,节省了指针的空间开销。 | 当保存的是字符串数据且长度小于44字节的时候,embstr
会调用内存分配函数,只分配一块连续的内存空间,空间中一次包含redisObject
和SDS
两个数据结构,使元数据、指针和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...")| # +-------------+