分类 "Redis的设计与实现" 下的文章

链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现.

除了链表键之外, 发布与订阅, 慢查询, 监视器等功能也用到了链表, Redis 服务器还使用链表保存多个客户端的状态信息, 以及使用链表来构建客户端输出缓冲区(output buffer).

1. 链表的定义

每个链表节点使用一个 adlist.h/listNode 结构来表示:

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

使用 adlist.h/list 来操作链表会更方便

typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

可见, 它是一个双向链表.

head, taillen 分别是表头表尾指针和节点数量, 而 dup, freematch 则是用于实现多态链表所需的类型特定函数:

  • dup 函数用于复制链表节点所保存的值;
  • free 函数用于释放链表节点所保存的值;
  • match 函数则用于对比链表节点所保存的值和另一个输入值是否相等.

(有点面向对象的味道)

2. 链表的API

函数 作用 时间复杂度
listSetDupMethod 将给定的函数设置为链表的节点值复制函数 O(1)
listGetDupMethod 返回链表当前正在使用的节点值复制函数 复制函数可以通过链表的 dup 属性直接获得, O(1)
listSetFreeMethod 将给定的函数设置为链表的节点值释放函数 O(1)
listGetFree 返回链表当前正在使用的节点值释放函数 释放函数可以通过链表的 free属性直接获得, O(1)
listSetMatchMethod 将给定的函数设置为链表的节点值对比函数 O(1)
listGetMatchMethod 返回链表当前正在使用的节点值对比函数 对比函数可以通过链表的 match 属性直接获得, O(1)
listLength 返回链表的长度(包含了多少个节点) 链表长度可以通过链表的 len 属性直接获得, O(1)
listFirst 返回链表的表头节点 表头节点可以通过链表的 head 属性直接获得, O(1)
listLast 返回链表的表尾节点 表尾节点可以通过链表的 tail 属性直接获得, O(1)
listPrevNode 返回给定节点的前置节点 前置节点可以通过节点的 prev 属性直接获得, O(1)
listNextNode 返回给定节点的后置节点 后置节点可以通过节点的 next 属性直接获得, O(1)
listNodeValue 返回给定节点目前正在保存的值 节点值可以通过节点的 value 属性直接获得, O(1)
listCreate 创建一个不包含任何节点的新链表 O(1)
listAddNodeHead 将一个包含给定值的新节点添加到给定链表的表头 O(1)
listAddNodeTail 将一个包含给定值的新节点添加到给定链表的表尾 O(1)
listInsertNode 将一个包含给定值的新节点添加到给定节点的之前或者之后 O(1)
listSearchKey 查找并返回链表中包含给定值的节点 O(N), N 为链表长度
listIndex 返回链表在给定索引上的节点 O(N), N 为链表长度
listDelNode 从链表中删除给定节点 O(1)
listRotate 将链表的表尾节点弹出, 然后将被弹出的节点插入到链表的表头, 成为新的表头节点 O(1)
listDup 复制一个给定链表的副本 O(N), N 为链表长度
listRelease 释放给定链表, 以及链表中的所有节点 O(N), N 为链表长度

3. 总结

双端: 节点带有 prevnext 指针, 获取其前置和后置节点的复杂度都是 O(1);

无环: 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL, 对链表的访问以 NULL 为终点;

带表头指针和表尾指针: 通过 list 结构的 head 指针和 tail 指针, 获取表头和表尾节点的复杂度为 O(1);

带链表长度计数器: 通过 list 结构的 len 属性, 程序获取链表中节点数量的复杂度为 O(1);

多态: 链表节点使用 void* 指针来保存节点值, 并且可以通过 list 结构的 dup, free, match 三个属性为节点值设置类型特定函数, 可以用于保存各种不同类型的值.

4. 重点回顾

  • 链表被广泛用于实现 Redis 的各种功能, 比如列表键, 发布与订阅, 慢查询, 监视器, 等等;
  • 每个链表节点由一个 listNode 结构来表示, 每个节点都有一个指向前置节点和后置节点的指针, 所以 Redis 的链表实现是双端链表;
  • 每个链表使用一个 list 结构来表示, 这个结构带有表头节点指针, 表尾节点指针, 以及链表长度等信息;
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL , 所以 Redis 的链表实现是无环链表;
  • 通过为链表设置不同的类型特定函数, Redis 的链表可以用于保存各种不同类型的值.

现在在高铁上, 赶着春节回家过年, 无座站票, 电脑只能放行李架上, 面对着行李架撸键盘--看过<Redis的设计与实现>这本书, 突然想起, 便整理下SDS的内容, 相对后面的章节, 算是比较简单的~

大多数情况下, Redis使用SDS(Simple Dynamic String, 简单动态字符串)作为字符串表示, 比起C字符串, SDS具有以下优点:

  1. 常数复杂度获取字符串长度;
  2. 杜绝缓冲区溢出;
  3. 减少修改字符串时带来的内存重分配次数;
  4. 二进制安全;
  5. 兼容部分C字符串函数.

以上列举的优点, 也算是这篇文章的主要内容. 先从定义说起吧:

1. SDS的定义

SDS结构定义如下(sds.h/sdshdr):

struct sdshdr {
    // 记录buf数组中已使用字节的数量, 等于SDS所保存字符串的长度
    int len;
    // 记录buf数组中未使用字节的数量
    int free;
    // 字节数组, 用于保存字符串
    char buf[];
}
  1. len属性记录了已使用的字节数量(字符串长度);
  2. free属性的值为0, 表示这个SDS没有未使用的空间;
  3. free属性的值为5, 表示这个SDS保存了一个5字节长的字符串;
  4. buf属性是一个char类型的数组, 数组的最后一个字节保存了空字符0.

SDS遵循C字符串以空字符串结尾的惯例, 空字符不计入SDS的len属性, 即额外为空字符分配了1字节的空间, 并且添加空字符到字符串末尾均由SDS函数自动完成, 对使用者完全透明. 该特性带来的好处是, SDS可以直接复用C字符串函数库的部分函数.

2. SDS与C字符串的区别

2.1 常数复杂度获取字符串长度

  1. 由于C字符串不记录自身长度, 所以获取长度时需要遍历整个字符串, 直到遇到空字符0为止, 该操作的复杂度为O(N);
  2. 由于SDS在len属性中记录了SDS本身的长度, 所以获取一个SDS的长度的复杂度为O(1).

Redis使用SDS, 将获取字符串长度所需的复杂度从O(N)降低到O(1), 确保获取字符串长度的工作不会成为Redis的性能瓶颈.

2.2 杜绝缓冲区溢出

由于C字符串不记录自身长度, 以函数strcat来说, 当执行该函数时, 都是认为已经为dest分配了足够的内存容纳src字符串, 但如果该假设不成立, 就会产生缓冲区溢出.

然而, SDS的字符串空间分配策略, 从根本上杜绝了缓冲区溢出的可能性: 当SDS-API需要对SDS进行修改时, API会先检查SDS的空间是否满足修改所需的需求, 如果不满足的话, API会自动扩容至所需大小, 再执行修改操作. 所以, SDS无需手工维护SDS的空间大小, 也不会产生缓冲区溢出的问题.

2.3 减少修改字符串时带来的内存重分配次数

由于C字符串不记录自身长度, 所以每次增长或缩减字符串, 需要对保存这个C字符串的数组进行一次内存重分配操作:

1.如果程序执行的是增长字符串的操作, 比如拼接操作append, 需要进行内存重分配操作, 扩展底层数组至合适大小, 否则将会产生缓冲区溢出;
2.如果程序执行的是缩短字符串的操作, 比如截断操作trim, 需要进行内存释放操作, 否则将会产生内存泄露.

Redis作为数据库, 经常用于速度要求严苛, 数据被频繁修改的场合, 减少内存的重分配次数能提高性能. SDS通过未使用空间解除了字符串长度底层数组长度之间的关联: 在SDS中, buf数组的长度不一定就是字符数加一, 数组里面可以包含未使用的字节, 而这些字节的数量就由SDS的free属性记录.

通过未使用空间, SDS实现了空间预分配和惰性空间释放两种优化策略.

1.空间预分配

当SDS-API对SDS进行修改, 并且需要对SDS进行空间扩展的时候, 程序不仅会为SDS分配修改所需的空间, 还会为SDS分配额外的未使用空间.

额外分配的未使用空间数量, 由以下公式决定:

  1. 如果对SDS进行修改之后, SDS的长度(即len属性)将小于1MB, 那么程序分配和len属性同样大小的未使用空间, 这时SDS的len属性的值将和free属性的值相同: 比如修改之后, SDS的len将变成13字节, 那么程序也会分配13字节的未使用空间, buf长度将变成 13Byte + 13Byte + 1Byte = 27Byte;
  2. 如果对SDS进行修改之后, SDS的长度将大于等于1MB, 那么程序会分配1MB的未使用空间: 比如修改之后, SDS的len将变成30MB, 那么程序会分配1MB的未使用空间, buf长度将变成 30MB + 1MB + 1Byte.

通过空间预分配策略, Redis可以减少连续执行字符串增长操作所需的内存重分配次数.

2.惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作: 当SDS-API需要缩短SDS字符串时, 程序并不会立即回收内存, 而是使用free属性将这些字节的数量记录起来, 并等待将来使用.

当然, SDS也提供了相应的API真正地释放SDS的未使用空间, 无需担心该策略带来的内存浪费问题.

2.4 二进制安全

C字符串除了末尾, 不能包含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾, 所以C字符串只能保存文本数据, 而不能保存像图片, 音频, 视频, 压缩文件这样的二进制数据.

Redis为了可以适用于各种不同的场景, SDS-API都是二进制安全的(binary-safe), 所有SDS-API都会以二进制的方式处理buf数组里面的数据, 不限制, 不过滤, 不假设, 写入什么就读到什么.

2.5 兼容部分C字符串函数

虽然SDS-API是二进制安全的, 但它们一样遵循C字符串以空字符结尾的惯例: 这些API总是将SDS保存的数据末尾数组为空字符, 并且总会在为buf分配空间时多分配一个字节来容纳这个空字符, 以复用<string.h>库定义的函数.

3. SDS的API

函数 作用 复杂度
sdsnew 创建一个包含给定C字符串的SDS O(N), N为给定C字符串的长度
sdsempty 创建一个不包含任何内容的空SDS O(1)
sdsfree 释放给定的SDS O(N), N为被释放SDS的长度
sdslen 返回SDS的已使用空间字节数 这个值可以通过读取SDS的len属性来直接获得, 复杂度为O(1)
sdsavail 返回SDS的未使用空间字节数 这个值可以通过读取SDS的free属性来直接获得, 复杂度为O(1)
sdsdup 创建一个给定SDS的副本(copy) O(N), N为给定C字符串的长度
sdsclear 清空SDS保存的字符串内容 因为惰性空间释放策略, 复杂度为O(1)
sdscat 将给定C字符串拼接到另一个SDS字符串的末尾 O(N), N为被拼接C字符串的长度
sdscatsds 将给定SDS字符串拼接到另一个SDS字符串的末尾 O(N), N为被拼接SDS字符串的长度
sdscpy 将给定的C字符串复制到SDS里面, 覆盖SDS原有的字符串 O(N), N为被复制SDS字符串的长度
sdsgrowzero 用空字符将SDS扩展至给定长度 O(N), N为扩展新增的字节数
sdsrange 保留SDS给定区间内的数据, 不在区间内的数据会被覆盖或清除 O(N), N为被保留数据的字节数
sdstrim 接受一个SDS和一个C字符串作为参数, 从SDS中移除所有在C字符串中出现过的字符 O(N^2), N为给定C字符串的长度
sdscmp 对比两个SDS字符串是否相同 O(N), N为两个SDS钟较短的那个SDS的长度

4. 总结

  • Redis在大多数情况下使用SDS作为字符串的表示;
  • 相比C字符串, SDS具有以下优点:
  1. 常熟复杂度获取字符串长度;
  2. 杜绝缓冲区溢出;
  3. 减少修改字符串长度时所需的内存重分配次数;
  4. 二进制安全;
  5. 兼容部分C字符串函数.
  • C字符串和SDS之间的区别:
C字符串SDS
获取字符串长度的复杂度为O(N)获取字符串长度的复杂度为O(1)
API是不安全的,可能造成缓冲区溢出API是安全的,不会造成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重分配修改字符串长度N次最多需啊哟执行N次内存重分配
可以使用所有<string.h>库中的函数可以使用一部分<string.h>库中的函数

以上笔记都是整理自<Redis的设计与实现>, 真的很感谢作者, 也希望自己能坚持写下去^_^.