枫秀学习日志

枫秀学习日志

0%

redis之字符串存储结构

发表于 分类于 Disqus： Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

字符串在redis中是最为常用的类型，本篇文章主要是针对redis是如何存储字符串的底层结构进行说明，同时在最后说明使用这种结构的优点。

Redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符 数组，以下简称C字符串），而是自己构建了一种名为简单动态字符串 （simple dynamic string，SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。

基本结构

整体结构定义如下

1
2
3
4
5
6
7
8
9
struct sdshdr { 
// 数组中已使用字节的数量 
// 等于SDS 所保存字符串的长度 
int len; 
// 记录buf 数组中未使用字节的数量 
int free; 
// 字节数组，用于保存字符串 
char buf[]; 
};

具体存储实例如下

具体实例

SDS与C字符串的区别

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

通过使用SDS而不是C字符串，Redis将获取字符串长度所需的复杂度从O（N）降低到了O（1），这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。c字符串需要遍历完所有的数组才能得到长度，二SDS直接根据len就可以获取到长度。

杜绝缓冲区溢出

这个主要是在进行组合俩个字符串的时候，SDS可以根据free的长度来判断是否能够有足够的空间拷贝另外的字符串到数组中。但是个人看来，如果要组合字符串的话，也会先检查容量，如果不够会先扩容在拷贝。所以这个不是最根本的原因，只能说一定程度上减少缓冲区溢出。

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

正如前两个小节所说，因为C字符串并不记录自身的长度，所以对于一个包含了N个字符的C字符串来说，这个C字符串的底层实现总是一 个N+1个字符长的数组（额外的一个字符空间用于保存空字符）。因为 C字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个C字符串，程序都总要对保存这个C字符串的数组进行 一次内存重分配操作：

  • 如果程序执行的是增长字符串的操作，比如拼接操作 （append），那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小——如果忘了这一步就会产生缓冲区溢出。
  • 如果程序执行的是缩短字符串的操作，比如截断操作（trim），那 么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使 用的那部分空间——如果忘了这一步就会产生内存泄漏。

因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作： ·在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配是可以接受的。

但是Redis作为数据库，经常被用于速度要求严苛、数据被频繁修 改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的 话，那么光是执行内存重分配的时间就会占去修改字符串所用时间的一 大部分，如果这种修改频繁地发生的话，可能还会对性能造成影响。 为了避免C字符串的这种缺陷，SDS通过未使用空间解除了字符串 长度和底层数组长度之间的关联：在SDS中，buf数组的长度不一定就是 字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。

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

空间预分配
空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个 SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为 SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。

其中，额外分配的未使用空间数量由以下公式决定：

  • 如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。举个例子，如果进行修改之后， SDS的len将变成13字节，那么程序也会分配13字节的未使用空间，SDS 的buf数组的实际长度将变成13+13+1=27字节（额外的一字节用于保存 空字符）。
  • 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序 会分配1MB的未使用空间。举个例子，如果进行修改之后，SDS的len将 变成30MB，那么程序会分配1MB的未使用空间，SDS的buf数组的实际 长度将为30MB+1MB+1byte。 通过空间预分配策略，Redis可以减少连续执行字符串增长操作所 需的内存重分配次数。

惰性空间释放
惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要 缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后 多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待 将来使用。

与此同时，SDS也提供了相应的API，让我们可以在有需要时，真 正地释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内 存浪费。

二进制安全

C字符串中的字符必须符合某种编码（比如ASCII），并且除了字 符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的 空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本 数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

虽然数据库一般用于保存文本数据，但使用数据库来保存二进制数 据的场景也不少见，因此，为了确保Redis可以适用于各种不同的使用 场景，SDS的API都是二进制安全的（binary-safe），所有SDS API都会 以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其 中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它 被读取时就是什么样。 这也是我们将SDS的buf属性称为字节数组的原因——Redis不是用 这个数组来保存字符，而是用它来保存一系列二进制数据。

总结

c字符串 SDS
获取字符串的长度为o(n) 获取字符串的长度为o(1)
API不安全，可能会造成缓冲区溢出 安全，不会造成缓冲区溢出
修改字符串N次必须N次分配 最多N次分配
只保存文本数据 可以保存二进制数据
相关文章推荐