• 周五. 9月 30th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

动态字符串 -《Redis设计与实现》读书笔记

admin

11月 28, 2021

SDS(simple dynamic string): 简单动态字符串

SDS使用场景

  1. 包含字符串值的键值对,在底层都是由sds实现
  2. 用作缓冲区:AOF模块中的AOF缓冲区、客户端状态中的输入缓冲区

SDS定义

struct sdshdr {
    // 记录buf数组中已使用字节的数量
    // 等于sds所保存字符串的长度
    unsigned char len;

    // 记录buf分配的长度(除去了sds头和空’’结束符)
    // 计算可用长度 avail = alloc - len
    unsigned char alloc;

    //只有3位有效位,因为类型的表示就是0到4,8位的flags有5位没有被用到
    unsigned char flags;

    // 字节数组,用于保存字符串,实际的字符串存在这里
    // 最后一个字符保存空字符''
    char buf[];
};

空间预分配优化策略

    // 若新的总长度小于1m,则分配新的总长度*2,否则分配新的总长度+1m
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

惰性空间释放优化策略

当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记起来,并等待将来使用

SDS与C字符串的区别

SDS C字符串
获取字符串长度复杂度O(1)
通过len属性实现
获取字符串长度复杂度O(N)
杜绝缓冲区溢出
先检测空间大小再执行修改操作
可能造成缓冲区溢出
增长/缩短N次字符串最多进行N次内存重分配
通过alloc属性实现,实行空间预分配和惰性空间释放优化策略
增长/缩短N次字符串必定进行N次内存重分配
二进制安全
可以保存文本数据和任意格式的二进制数据
二进制不安全
只可以保存文本数据
可以使用部分<string.h>库的函数 可以使用所有<string.h>库的函数

源码阅读

  1. 文件:src/sds.h 、 src/sds.c

索引

redis 系列,要懂redis,首先得看懂sds(全网最细节的sds讲解)
Redis 字符串数据结构(String)底层存储源码分析

只言片语任我说,提笔句句无需忖。落笔不知寄何人,唯有邀友共斟酌。

发表回复

您的电子邮箱地址不会被公开。