Redis
的数据结构1 - string
今天来聊聊 Redis
的string
，这一数据结构。
string
简介
string
是Redis
中最基本，也是最简单的数据结构。一个键(key
) 对应着一个string
类型的值(value
). 我们都知道redis
是使用C
语言来编写的,但是 string
这一个数据结构并非是使用C
语言的 string(char[])
来实现的，后面有数据结构的实现，在文末哟.
现在，先暂且抛开内部实现,我们先看看有怎么使用这一数据结构。
string
相关常用命令
set
命令
SET key value [expiration EX seconds|PX milliseconds] [NX|XX]
使用示例:
# 1.设置一个键值对 f1=>f1
127.0.0.1:6379> set k1 v1
OK
# 根据键查询值
127.0.0.1:6379> get k1
"v1"
# 2.设置一个键值对(f2=>f2),设置超时时间为10s
# EX 表示秒
127.0.0.1:6379> set k2 v2 EX 10
OK
127.0.0.1:6379> get k2
"v2"
# 等待10s之后去查询f2
127.0.0.1:6379> get k2
(nil)
# 3.设置一个键值对(f3=>f3),设置超时时间为 10000毫秒
# PX 表示为毫秒
127.0.0.1:6379> set k3 v3 PX 10000
OK
127.0.0.1:6379> get k3
"v3"
127.0.0.1:6379> get k3
(nil)
# 4.设置键值对k4=>v4,验证"存在相同的key就设置失败"
# setnx 命令也可实现,注意返回值。
127.0.0.1:6379> set k4 v4 NX
OK
# 如果存在相同的key就设置失败(与下面的注意对比)
127.0.0.1:6379> set k4 v4 NX
(nil)
# 5.验证"不存在相同的key就设置失败"
127.0.0.1:6379> set k5 v5 XX
(nil)
# 先设置一个键值对,
127.0.0.1:6379> set k5 v5
OK
# 设置不存在相同的key就设置失败
127.0.0.1:6379> set k5 v5 XX
OK复制
setnx
命令
setnx key value
set if not exists
的缩写。如果已存在key,返回0, 不存在返回1. 常用于分布式锁。
使用实例
# 设置一个不存在的键值对 k6=>v6
127.0.0.1:6379> setnx k6 v6
(integer) 1
# 如果key已经存在,则返回0。
127.0.0.1:6379> setnx k6 v6
(integer) 0复制
setEx
命令
setex key seconds value
给键值对设置生存时间(秒级别)。
# 设置k7=>v7这个键值对的生存时间为5s
127.0.0.1:6379> setex k7 5 v7
OK
127.0.0.1:6379> get k7
"v7"
# 过5s秒钟之后,再查看。
127.0.0.1:6379> get k7
(nil)
127.0.0.1:6379>复制
psetEx
命令
psetex key milliseconds value
tips: 命令助记: psetex , p直接的是毫秒。可以参考set命令的PX选项。
给键值对设置生存时间(毫秒级别)。
# 设置键值对
127.0.0.1:6379> psetex k8 5000 v8
OK
# 获取k8的值
127.0.0.1:6379> get k8
"v8"
# 5s之后，获取k8的值
127.0.0.1:6379> get k8
(nil)复制
get
命令
这个命令不多说了, 获取key
相关联的value
. get key
getset
命令
getset key value
设置键值对, key=>value
, 如果key
已经存在,返回旧值。不存在返回 nil
# 设置键值对
127.0.0.1:6379> getset k9 v9
(nil)
# 获取值
127.0.0.1:6379> get k9
"v9"
# 在设置一次k9,值为vv9,返回旧值 v9
127.0.0.1:6379> getset k9 vv9
"v9"复制
# 设置一个list类型，key为k9_1, Value中只有一个元素v9_1
127.0.0.1:6379> lpush k9_1 v9_1
(integer) 1
# 使用getset命令再设置一次,抛出命令错误。
127.0.0.1:6379> getset k9_1 vv9_1
(error) WRONGTYPE Operation against a key holding the wrong kind of value复制
strlen
命令
strlen key
返回字符串的长度. 如果key不存在的时候,返回0,如果key对应的不是一个字符串时,返回错误.
127.0.0.1:6379> set k10 v10
OK
127.0.0.1:6379> strlen k10
(integer) 3
# 演示报错
127.0.0.1:6379> lpush k10_1 v10
(integer) 1
127.0.0.1:6379> strlen k10_1
(error) WRONGTYPE Operation against a key holding the wrong kind of value复制
APPEND
命令
APPEND key value
命令
根据key，给key对应的值追加字符串。如果key不存在，就设置一对键值对。
# 如果key不存在则设置键值对
127.0.0.1:6379> append k11 v11
(integer) 3
127.0.0.1:6379> get k11
"v11"
# 如果存在，则追加
127.0.0.1:6379> append k11 v11
(integer) 6
127.0.0.1:6379> get k11
"v11v11"复制
setrange
命令
setrange key offset value
从偏移量 offset
开始覆写原来key
的值。如果key
不存的时候当作空字符串处理。返回被设置后Value
的长度。
# 设置不存在的key
127.0.0.1:6379> setrange k12 3 v12
(integer) 6
# 在offset前的空位置会用 \x00 填充
127.0.0.1:6379> get k12
"\x00\x00\x00v12"
# 设置已经存在的key
127.0.0.1:6379> setrange k12 4 v12
(integer) 7
127.0.0.1:6379> get k12
"\x00\x00\x00vv12"复制
getrange
命令
getrange key start end
获取指定区间的值.报错start和end位置。索引位置是从0开始的。
负数偏移量表示从字符串的末位开始计数。
127.0.0.1:6379> set k13 v13v13v13
OK
127.0.0.1:6379> getrange k13 2 5
"3v13"
# 从索引为2处，到倒数第4位。
127.0.0.1:6379> getrange k13 2 -4
"3v13"
# 如果end大于Value的长度，返回目前start到结束的部分
127.0.0.1:6379> getrange k13 3 10
"v13v13"
# 超过Value的长度返回为 ""
127.0.0.1:6379> getrange k13 100 120
""复制
incr
命令
incr key
在key对应的Value上进行自增1. 如果Value可以解释为数据，则自增，反之，返回错误。
返回值为自增后的值。
如果ke不存在，则先初始化 key对应的Value=0， 然后再自增。
相对的是: DECR
命令
127.0.0.1:6379> incr k14
(integer) 1
127.0.0.1:6379> get k14
"1"
127.0.0.1:6379> incr k14
(integer) 2复制
incrby
命令
incrby key increment
带有步长的自增命令。
相对的命令是: DECRBY
命令
127.0.0.1:6379> incrby k15 5
(integer) 5
127.0.0.1:6379> INCRBY k15 5
(integer) 10
127.0.0.1:6379> INCRBY k15 5
(integer) 15复制
INCRBYFLOAT
命令
INCRBYFLOAT key increment
带有步长的浮点数自增
127.0.0.1:6379> INCRBYFLOAT k16 5.0
"5"
127.0.0.1:6379> INCRBYFLOAT k16 5.2
"10.2"
127.0.0.1:6379> INCRBYFLOAT k16 5.4
"15.6"复制
DECR
命令
DECR key
自减1
.
# 如果key，不存在，同样会初始化为0，然后自减1
127.0.0.1:6379> DECR k17
(integer) -1
127.0.0.1:6379> DECR k17
(integer) -2
127.0.0.1:6379> DECR k17
(integer) -3复制
DECRBY
命令
带有步长的自减命令, 与 INCRBY
命令相对。
# 如果key不存在，会初始化为0，再进行自减。
127.0.0.1:6379> DECRBY k18 5
(integer) -5
127.0.0.1:6379> DECRBY k18 5
(integer) -10复制
mget
命令
mget key [key ...]
一次性返回多个key
的值。如果key
不存在，返回 (nil)
127.0.0.1:6379> set k19_0 v19_0
OK
127.0.0.1:6379> set k19_1 v19_1
OK
127.0.0.1:6379> mget k19_0 k19_1
1) "v19_0"
2) "v19_1"
# 如果key不存在的时候，返回 (nil)
127.0.0.1:6379> mget k19_0 k19_1 k10_2
1) "v19_0"
2) "v19_1"
3) (nil)复制
mset
命令
同时为设置多个键值对。如果key已经存在，直接覆盖掉。
注意：这个原子性操作. 所有给定的key都会在同一时间内被设置。tips: 如果希望，已经存在的key不被覆盖，可以参考 msetnx
命令
# 一下设置三对
127.0.0.1:6379> mset k20_0 v20_0 k20_1 v20_1 k20_2 v20_2
OK
127.0.0.1:6379> mget k20_0 k20_1 k20_2
1) "v20_0"
2) "v20_1"
3) "v20_2"
# 演示已有的key对应的值会被覆盖掉。
127.0.0.1:6379> mset k20_2 vv20_2 k20_3 v20_3
OK
127.0.0.1:6379> mget k20_2 k20_3
1) "vv20_2"
2) "v20_3"复制
msetnx
命令
MSETNX key value [key value ...]
当且仅当所有给定的key不存在的时候，才会设置键值对。即使有一个key存在，该命令也不会设置其他的key对应的键值对.
# 演示设置成功
127.0.0.1:6379> MSETNX k21_0 v21_0 k21_1 v21_1
(integer) 1
127.0.0.1:6379> MGET k21_0 k21_1
1) "v21_0"
2) "v21_1"
# 存在其中的一个给定key，就不能设置成功
127.0.0.1:6379> msetnx k21_1 vv21_1 k21_2 v21_2
(integer) 0
127.0.0.1:6379> MGET k21_1 k21_2
1) "v21_1"
2) (nil)复制
Redis
如何实现String
这一数据结构
在 string
的相关命令介绍的时候，我其实使用一个错误的描述。就是将Redis
的String
类型称为字符串。这种说法其实不正确的。
在 redis
中, string
这一数据结构使用sds
来表示的。
sds
sds
是 simple dynamic string
的简称。意思是 简单的动态字符串
。这里面的string
就是实打实的C
语言中的字符串(char[]
). Redis
也并非一点也没有使用 C
语言的字符串，像一些字面量常量，日志都是使用C
语言的字符串。
那 sds
到底是一个什么样的结构呢?
在源码的 src
目录下，我找到了 sds.h
这样一个文件。这里规定了 sds
结构。
struct __attribute__ ((__packed__)) sdshdr64 {
// 表示已使用的长度,即buf[]的长度。
uint64_t len;
// 已分配的长度(包括未使用的长度)
// alloc-len,对应着之前版本的free
uint64_t alloc;
unsigned char flags;
char buf[];
};复制
sds
保留了 C
字符串以空字符结尾的惯例。保留的这个空字符的长度不会保存在 len
字段中。保留这一惯例的好处就是可以使用C
字符串函数库的一些方法。
假设我们分配了10
个字节空间,只保存了 redis
这个C
字符串，那么 在sds
中，是这么表示的：
使用sds
比使用C
字符串有什么好处呢?
获取字符长度的时间复杂度为 O(1)
C
语言获取一个字符串的长度为 O(N)
. 需要遍历字符串并累加，判断字符是否为 '\0'
来获得字符串的长度。
sds
只需要根据 len
字段获取即可。怎么获取的呢?
我们来看下源码。
// 定义char类型的指针类型。
typedef char *sds;
// 获取长度的结构体指针的宏.
// 可根据指向buf的指针返回指向sdshdr结构体首地址的宏
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
// sds 直接指向结构体里的buf
static inline size_t sdslen(const sds s) {
// sds是直接指向结构体里的buf数据, 当获取len等字段的信息,只需要减去结构体长度，回退一下指针就可以了。
// 这里使用的尾指针法。
unsigned char flags = s[-1];
// 判断属于那种 sdshdr,对应减去不同的地址。
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}复制
可以杜绝缓冲区溢出
C
语言是不会判断数组是否越界的。比如 strcat
方法, 如果当前的数据不能容纳拼接之后字符时,必然会发生缓存区溢出。但是 sds
则不会。我们来看下 sds
的字符串拼接的方法 sdscat
。
// s 原来的字符串，t是要拼接的字符串
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sds sdscatlen(sds s, const void *t, size_t len) {
// 获取原来字符串的长度。(见上面的方法)
size_t curlen = sdslen(s);
// 扩大sds字符串末尾的可用空间，
//以便调用者确保在调用此函数后可以覆盖字符串末尾的addlen字节，
//再为null项再加上一个字节。具体实现，参考源码(sds.c:204)。
s = sdsMakeRoomFor(s,len);
// 如果内存分配失败，就会返回null
if (s == NULL) return NULL;
// 调用C语言的分配
memcpy(s+curlen, t, len);
// sds设置 sdshdr的len字段的值。
sdssetlen(s, curlen+len);
// 添加最后一个字符为: '\0'
s[curlen+len] = '\0';
return s;
}复制
sds 优化了C语言的内存分配策略
空间预分配
空间预分配策略遵循下面的公式:
如果 SDS
的长度小于最大的预分配空间(1MB
),那么会分配两倍的新空间,再加上结尾的空字符'\0'
举个例子: 原有的sds
的len
为5
,alloc
为5
, 要拼接的字符串长度为15
, 那么新分配的空间大小是:(5byte+15byte)*2 + 1byte = 41byte
.如果 sds
的长度大于等于默认的预分配空间, 那么就在新分配的空间大小基础上，再分配1MB
的空间。如果修改后的，SDS
的len
是20M
，那么alloc
就是20M + 1M + 1byte
具体分配过程见下面的源码
// SDS 默认最大的预分配空间为1M
#define SDS_MAX_PREALLOC (1024*1024)
// sds 预分配空间
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
/* 如果空间足够，直接返回 */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so sdsMakeRoomFor() must be called
* at every appending operation. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
sdssetalloc(s, newlen);
return s;
}复制
惰性空间释放
当对sds进行缩短操作时，程序并不会立马对内存重分配来回收收缩的空间，而是仅仅改变len
属性，并且在对应的位置上将字符设置为: '\0'
以 函数 sdstrim
为例。
sds sdstrim(sds s, const char *cset) {
char *start, *end, *sp, *ep;
size_t len;
sp = start = s;
ep = end = s+sdslen(s)-1;
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > sp && strchr(cset, *ep)) ep--;
len = (sp > ep) ? 0 : ((ep-sp)+1);
// 进行移位
if (s != sp) memmove(s, sp, len);
// 设置字符串结束符
s[len] = '\0';
// 设置len字段的值
sdssetlen(s,len);
return s;
}复制
上述实现中，并没有进行内存回收。sds
也提供了内存回收的函数sds_free
.具体可以看Redis 5.0.7
版源码. sds.c
第1120
行。这里不再深入学习了。
二进制安全
sds
的API
都是二进制安全的。因为Redis
对 sds
结构中的buf
数组中的数据都是以二进制的方式处理的。
兼容部分的C
字符串函数
Redis
还是遵循了C
字符串以 '\0'
结尾的习惯，所以保存了文本数据的sds
是可以复用 <string.h>
库中的函数。
总结
string
是redis
中最简单的数据结构.string
不是C
字符串，而是对C
字符串进行了封装.学习了
string
类型相关的api
。set
,setnx
,setex
,get
,getset
,incr
,decr
,...sds
这种设计的好处,提高了性能,优化内存分配，二进制安全，兼容C
字符串。
最后
期待你的关注
