Redis的数据结构1 - string

小咪咪 2023-02-16 01:49 9阅读 0赞

### 文章目录 ###

*   *   *  \`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)\`
                 *  可以杜绝缓冲区溢出
                 *  sds 优化了C语言的内存分配策略
                 *   *  空间预分配
                     *  惰性空间释放
             *  二进制安全
             *  兼容部分的\`C\`字符串函数
         *  总结
         *  最后

今天来聊聊 `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`中，是这么表示的：

![在这里插入图片描述][20200607125852843.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`字符串。

### 最后 ###

希望和你成为朋友！我们一起学习~  
最新文章尽在公众号【方家小白】，期待和你相逢在【方家小白】  
![20200607125503248.jpg][]

[20200607125852843.png]: https://img-blog.csdnimg.cn/20200607125852843.png
[20200607125503248.jpg]: https://img-blog.csdnimg.cn/20200607125503248.jpg