Redis教程

Redis设计与实现

本文主要是介绍Redis设计与实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第 2 章 简单动态字符串

Redis 没有直接使用 C 语言的字符串来表示(即以空字符结尾的字符数组),构建一张简单动态字符串 SDS 的抽象类型,作为默认字符串

在 Redis 中,C 字符串作为字符串字面量,使用在没有对字符串修改的地方,如打印日志:

但是需要的不仅仅是字符串字面量时,而是可以被修改的字符串值时,就会使用 SDS 来表示,如包含字符串值的键值对底层都是 SDS 实现

  • 键是字符串对象,也是 SDS
  • 值是字符串对象,也是 SDS

SDS 还被用作缓冲区

  • AOF 模块的 AOF 缓存区
  • 客户端状态的输入缓存区

2.1 SDS 的定义

sdshdr

每个 sds.h/sdshdr 结构表示一个 SDS 值

SDS示例

  • free 为 0 ,表示 SDS 没有分配任何未使用的空间

  • len 为 5,表示 SDS 存储了 5 字节的字符串

  • buf 为 char 类型数组,表示存储的字符,最后一个字符是空字符 '\0'

    • 空字符不在 SDS len 计算内,自动分配 1 字节空间,添加到 字符串末尾等操作为 SDS 函数自动完成

    • 好处:直接重用 C 字符串函数库里面的函数

    • 例子,s 指针指向所示 SDS,于是可以直接使用<stdio.h>/printf函数进行打印

      • printf("%s", s->buf);

    带有未使用空间的 SDS

    与图 1 类似,区别的是 SDS 为 buf 数组分配了 5 字节未使用空间, free 值为 5

2.2 SDS 与 C 字符串的区别

传统 C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串,且字符数组最后一个元素是空字符 '\0'

C字符串

不能满足 Redis对字符串在安全性、效率性以及功能方面的要求

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

C 字符串没有记录自身的长度信息,所以为了得到 C 字符串长度,需要遍历整个字符串,直到代表末尾的空字符串 '\0',时间复杂度 O(N)

计算 C 字符串长度

SDS 则在 len 属性中记录了 SDS 本身的长度,时间复杂度 O(1),设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成

SDS

2.2.2 杜绝缓存区溢出

C 字符串容易造成缓冲区溢出

<string.h>/strcat函数可以将 src 字符串的内容拼接到 dest 字符串末尾,但 dest 字符串没有足够内存时则会溢出

SDS 空间分配策略杜绝了发送缓冲区溢出的可能性:

当 SDS API 对 SDS 进行修改时,会先检查 SDS 的空间是否满足修改所需的要求,不满足则会将 SDS 的空间扩展只执行修改所需的大小,再执行实际的修改,因此不会缓冲区溢出

SDS API 中 sdscat函数可以将 C 字符串拼接到 SDS 保存的字符串后,但会按照上述的方法山西实现

sdscat执行之前的SDS

sdscat执行之后的SDS

已存在的字符串长度 len 与未分配的长度一致

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

内存重分配涉及复杂的算法,且可能需要执行系统调用,比较耗时

  • 在一般程序中修改在字符串长度的情况不太常出现,每次修改执行内存重分配是可接受的
  • Redis 作为数据库,速度要求严苛,数据被频繁修改,每次修改都进行内存重分配,则看内存重分配的时间会占去所用时间的一大部分,甚至对性能造成影响

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

1.空间预分配

用于优化 SDS 的字符串增长操作:

​ 当 SDS 的 API 对 SDS 修改并需要扩展时,不仅会分配修改所必须要的空间,还会分配额外的未使用空间

额外分配的空间数量决定:

  • 对 SDS 修改之后的 len 小于 1 MB,则程序分配和 len 相同的大小的 free 空间,假如修改后 len 为 13 字节,则 free 也为 13 字节,buf 数组的实际长度为 13 + 13 + 1 = 27 字节

  • 大于 1 MB,则会分配 1 MB 未使用空间

在扩展 SDS 空间之前,SDS API 会检查未使用空间是否足够,足够则直接使用未使用空间,无须执行内存分配

通过预分配策略,SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次

2.惰性空间释放

用于优化 SDS 的字符串缩短操作:

​ 当需要缩短时,不立即使用内存重分配来回收缩短后多出来的字节,而是使用 free 属性来记录这些字节的数量记录

同时 SDS 也提供了相应的 API,在有需要时,真正释放 SDS 的未使用空间,不会因为惰性空间释放造成内存浪费

2.2.4 二进制安全

C 字符串字符需要符合某种编码 (如 ASCII ),除了字符串末尾之外,不能包含空字符串,否则会被误认为是字符串结尾

SDS API 都是二进制安全的,会以处理二进制的方式来处理 SDS 存放在 buff 数组里的数据,不会对其中的数据做任何限制、过滤或者假设,即 buff 属性被称字节数组的原因

2.2.5 兼容部分 C 字符串函数

SDS 一样遵循 C 字符串以空字符串结尾的惯例,为了让那些保存文本数据的 SDS 可以重用一部分 <string.h>库定义的函数

2.2.3 总结

C字符串和SDS之间的区别

2.3 SDS API

SDS API

2.4 重点回顾

  • Redis 只会使用 C 字符串作为字面量,大多数情况使用 SDS 作为字符串表示
  • SDS 优点
    • 常数复杂度获取字符串长度
    • 杜绝缓冲区溢出
    • 减少修改字符串长度时所需的内存重分配次数
    • 二进制安全
    • 兼容部分 C 字符串函数
这篇关于Redis设计与实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!