Redis数据结构-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（Simple Dynamic String-简单动态字符串）。那么它是什么呢？
Redis是用C语言实现的，但是它没有直接使用C语言的char*字符数组来实现字符串，而是自己封装了一个名为SDS（Simple Dynamic String-简单动态字符串）的数据结构来表示字符串，也就是 Redis的String数据类型的底层数据结构是SDS。
Redis中所有的key以及所有值对象中包含的字符串对象底层都是由SDS实现的。
SDS结构设计
源码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选择自己设计一个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) |
| 内存重新分配 | 分配的内存空间超过之后，会导致数组下标越界或者内存分配溢出 |
|
| 二进制安全 | 二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如\0这样的。上面说到C语言的char*中\0表示结束，这样\0后面的数据就会读取不到了 |
SDS是根据len长度来判断字符串结束的。 |
3个编码方式的源码分析
当我们使用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编码
当字符串键值的内容可以用一个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编码
可以看到上面源码中的第#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编码
当字符串的长度大于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。
编码转变的流程图
结论
在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...")| # +-------------+