乐趣区

关于后端:Redis-的字符串是如何实现的

jiezi

东边日出西边雨，道是无晴却有晴。

本篇会讲以下内容：

  • Redis 字符串的实现
  • Redis 字符串的性能劣势

Redis 字符串的实现

Redis 尽管是用 C 语言写的，但却没有间接用 C 语言的字符串，而是本人实现了一套字符串。目标就是为了晋升速度，晋升性能，能够看出 Redis 为了高性能也是殚精竭虑。

Redis 构建了一个叫做简略动静字符串（Simple Dynamic String），简称 SDS

1.SDS 代码构造

struct sdshdr{
    //  记录已应用长度
    int len;
    // 记录闲暇未应用的长度
    int free;
    // 字符数组
    char[] buf;};

SDS？什么鬼？可能对此生疏的敌人对这个名称有纳闷。只是个名词而已不用在意，咱们要重点观赏借鉴 Redis 的设计思路。上面画个图来阐明，高深莫测。

Redis 的字符串也会恪守 C 语言的字符串的实现规定，即最初一个字符为空字符。然而这个空字符不会被计算在 len 外头。

2.SDS 动静扩大特点

SDS 的最厉害最微妙之处在于它的 Dynamic。动态变化长度。举个例子

如上图所示刚开始 s1 只有 5 个闲暇位子，前面须要追加 ’ world’ 6 个字符，很显著是不够的。那咋办？Redis 会做以下三个操作：

  1. 计算出大小是否足够
  2. 开拓空间至满足所需大小
  3. 开拓与已应用大小 len 雷同长度的闲暇 free 空间（如果 len < 1M）开拓 1M 长度的闲暇 free 空间（如果 len >= 1M）

看到这儿为止有没有敌人感觉这个实现跟 Java 的列表 List 实现有点相似呢？看完前面的会感觉更像了。

Redis 字符串的性能劣势

  • 疾速获取字符串长度
  • 防止缓冲区溢出
  • 升高空间调配次数晋升内存应用效率

1. 疾速获取字符串长度

再看下下面的 SDS 构造体：

struct sdshdr{
    //  记录已应用长度
    int len;
    // 记录闲暇未应用的长度
    int free;
    // 字符数组
    char[] buf;};

因为在 SDS 里存了已应用字符长度 len，所以当想获取字符串长度时间接返回 len 即可，工夫复杂度为 O(1)。如果应用 C 语言的字符串的话它的字符串长度获取函数工夫复杂度为 O(n),n 为字符个数，因为他是从头到尾（到空字符 ’\0’）遍历相加。

2. 防止缓冲区溢出

对一个 C 语言字符串进行 strcat 追加字符串的时候须要提前开拓须要的空间，如果不开拓空间的话可能会造成缓冲区溢出，而影响程序其余代码。如下图，有一个字符串 s1=”hello” 和 字符串 s2=”baby”, 当初要执行 strcat(s1,”world”), 并且执行前未给 s1 开拓空间，所以造成了缓冲区溢出。

而对于 Redis 而言因为每次追加字符串时都会查看空间是否够用，所以不会存在缓冲区溢出问题。每次追加操作前都会做如下操作：

  1. 计算出大小是否足够
  2. 开拓空间至满足所需大小

3. 升高空间调配次数晋升内存应用效率

字符串的追加操作会波及到内存调配问题，然而内存调配问题会牵扯内存划分算法以及零碎调用所以如果频繁产生的话影响性能，所以对于性能至上的 Redis 来说这是万万不能忍耐的。所以采取了以下两种优化措施

  • 空间与调配
  • 惰性空间回收

1. 空间预调配

对于追加操作来说，Redis 不仅会开拓空间至够用而且还会预调配未应用的空间 (free) 来用于下一次操作。至于未应用的空间 (free) 的大小则由批改后的字符串长度决定。

当批改后的字符串长度 len < 1M, 则会调配与 len 雷同长度的未应用的空间(free)

当批改后的字符串长度 len >= 1M, 则会调配 1M 长度的未应用的空间(free)

有了这个预调配策略之后会缩小内存调配次数，因为调配之前会查看已有的 free 空间是否够，如果够则不开拓了～

2. 惰性空间回收

与下面状况相同，惰性空间回收实用于字符串缩减操作。比方有个字符串 s1=”hello world”，对 s1 进行 sdstrim(s1,” world”)操作，执行完该操作之后 Redis 不会立刻回收缩小的局部，而是会调配给下一个须要内存的程序。当然，Redis 也提供了回收内存的 api, 能够本人手动调用来回收缩减局部的内存。

到此为止完结了～

退出移动版