Redis 数据结构之 String - Redis 数据库 | 方家小白 = 和你一起遇见更好的自己

今天来聊聊 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

tip : 命令助记: 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"

ps: 如果原来的存在 key，但是 value 的类型与新设置的类型不一致，会抛出命令错误。

# 设置一个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[];
};

tips: 如果你注意到了这个结构体的命名。那么来看下这篇文章吧。

sds 保留了 C 字符串以空字符结尾的惯例。保留的这个空字符的长度不会保存在 len 字段中。保留这一惯例的好处就是可以使用 C 字符串函数库的一些方法。

假设我们分配了 10 个字节空间，只保存了 redis 这个 C 字符串，那么在 sds 中，是这么表示的：

01-01-sds示意图.png

# 使用 `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 字符串。

# 最后

期望与你一起遇见更好的自己

Redis

# string 简介

# string 相关常用命令

# set 命令

# setnx 命令

# setEx 命令

# psetEx 命令

# get 命令

# getset 命令

# strlen 命令

# APPEND 命令

# setrange 命令

# getrange 命令

# incr 命令

# incrby 命令

# INCRBYFLOAT 命令

# DECR 命令

# DECRBY 命令

# mget 命令

# mset 命令

# msetnx 命令

# Redis 如何实现 String 这一数据结构

# sds

# 使用 sds 比使用 C 字符串有什么好处呢？

# 获取字符长度的时间复杂度为 O(1)