专栏首页服务端思维Redis中字符串的表示

Redis中字符串的表示

c语言中字符串的表示

上节课我们已经说了 Redis 是由 c 语言开发的,但是 Redis 使用字符串的类型却没有采用 c 语言的字符串类型,接下来我们看看为什么要采用这样的设计

c 语言表示字符串用字符数组,用'\0'这样的字符结尾

Redis 字符串的表示——SDS

Redis 自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将 SDS 作为 Redis 的默认字符串表示。

struct sdshdr{
     //len 保存了SDS保存字符串的长度
     int len;
     //free 记录了buf数组中未使用的字节数量
     int free;
     //buf[] 数组用来保存字符串的每个元素
     char buf[];
}

1. 二进制安全

因为 C 字符串以空字符作为字符串结束的标识,而对于一些二进制文件(如图片等),内容可能包括空字符串,因此 C 字符串无法正确存取;而所有 SDS 的 API 都是以处理二进制的方式来处理 buf 里面的元素,并且 SDS 不是以空字符串来判断是否结束,而是以len 属性表示的长度来判断字符串是否结束

2. 减少修改字符串的内存重新分配次数

C 语言中如果要修改字符串,必须要重新分配内存(先释放再申请),因为如果没有重新分配,字符串长度增大时会造成内存缓冲区溢出,字符串长度减小时会造成内存泄露

而对于 SDS,由于 len 属性和 free 属性的存在,对于修改字符串 SDS 实现了空间预分配和惰性空间释放两种策略:

1、空间预分配:对字符串进行空间扩展的时候,扩展的内存比实际需要的多,这样可以减少连续执行字符串增长操作所需的内存重分配次数。

2、惰性空间释放:对字符串进行缩短操作时,程序不立即使用内存重新分配来回收缩短后多余的字节,而是使用 free 属性将这些字节的数量记录下来,等待后续使用。(当然 SDS 也提供了相应的 API,当我们有需要时,也可以手动释放这些未使用的空间。)

3.兼容部分 C 字符串函数

虽然 SDS 是二进制安全的,但是一样遵从每个字符串都是以空字符串结尾的惯例,这样可以重用 C 语言库<string.h> 中的一部分函数

4.杜绝缓冲区溢出

我们知道在 C 语言中使用 strcat 函数来进行两个字符串的拼接,一旦没有分配足够长度的内存空间,就会造成缓冲区溢出。而对于 SDS 数据类型,在进行字符修改的时候,会首先根据记录的 len 属性检查内存空间是否满足需求,如果不满足,会进行相应的空间扩展,然后在进行修改操作,所以不会出现缓冲区溢出

5.字符串长度 O(1)

由于 len 属性的存在,我们获取 SDS 字符串的长度只需要读取 len 属性,时间复杂度为 O(1)。而对于 C 语言,获取字符串的长度通常是经过遍历计数来实现的,时间复杂度为 O(n)。通过strlen key命令可以获取 key 的字符串长度。

Redis3.2版本前后SDS结构变化

在 redis3.2 分支出现之前字符串只用 sdshdr 一个类型(上文说到的 SDS),这种结构存在一个弊端,比如每次创建一个字符串,由于 len(int 类型,一般操作系统占 4 个字节)+free,最少占用 8 个字节,所以是不管字符串有多长,都要最少占用 8 个字节,比较浪费。

3.2 分支引入了五种 sdshdr 类型,每次在创建一个 sds 时根据 sds 的实际长度判断应该选择什么类型的 sdshdr,不同类型的 sdshdr 占用的内存空间不同。这种细分可以极大的节省空间,下面是 3.2 版本的 sdshdr 定义:

struct __attribute__ ((__packed__)) sdshdr5 {
  //实际上这个类型redis不会被使用,因为没有剩余空间的字段,不方便扩容。他的内部结构也与其他sdshdr不同,直接看sdshdr8就好。
  unsigned char flags; //一共8位,低3位用来存放真实的flags(类型),高5位用来存放len(长度)。
  char buf[];//sds实际存放的位置
};
struct __attribute__ ((__packed__)) sdshdr8 {
  uint8_t len;//表示当前sds的长度(单位是字节)
  uint8_t alloc; //表示已为sds分配的内存大小(单位是字节)
  //用一个字节表示当前sdshdr的类型,因为有sdshdr有五种类型,所以至少需要3位来表示
  //000:sdshdr5,001:sdshdr8,010:sdshdr16,011:sdshdr32,100:sdshdr64。高5位用不到所以都为0。
  unsigned char flags;
  char buf[];//sds实际存放的位置
};
struct __attribute__ ((__packed__)) sdshdr16 {
  uint16_t len; /* used */
  uint16_t alloc; /* excluding the header and null terminator */
  unsigned char flags; /* 3 lsb of type, 5 unused bits */
  char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
  uint32_t len; /* used */
  uint32_t alloc; /* excluding the header and null terminator */
  unsigned char flags; /* 3 lsb of type, 5 unused bits */
  char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
  uint64_t len; /* used */
  uint64_t alloc; /* excluding the header and null terminator */
  unsigned char flags; /* 3 lsb of type, 5 unused bits */
  char buf[];
};

下图是几种类型的结构原理图,sdshdr8 类型作为最常用的,重点看一下中间的sdshdr8结构

sdshdr

sdshdr8 各属性含义

  • len:表示当前 sds 的长度,不包括'/0'终止符,可直接获取获取长度,注意单位是字节
  • alloc:当前以分配的大小(3.2 以前的版本用的 free 是表示还剩 free 字节可用空间),不包括'/0'终止符,注意单位是字节
  • flags 表示当前 sdshdr 的类型,声明为 char ,则表示一共有 1 个字节(8 位),仅用低三位就可以表示所有 5 种 sdshdr 类型(参考上图表示)

000:sdshdr5,001:sdshdr8,010:sdshdr16,011:sdshdr32,100:sdshdr64。高5位用不到所以都为0。

“老师,用什么类型的 sdshdr 来存放它的信息呢?”

“这就得根据要存储的 sds 的长度决定了!”

redis 在创建一个 sds 之前,会调用 「sdsReqType(size_t string_size)来判断用哪个 sdshdr」。该函数传递一个 sds 的长度作为参数,返回应该选用的 sdshdr 类型。

#define SDS_TYPE_5  0 //00000000
#define SDS_TYPE_8  1 //00000001
#define SDS_TYPE_16 2 //00000010
#define SDS_TYPE_32 3 //00000011
#define SDS_TYPE_64 4 //00000100

#define SDS_TYPE_MASK 7 //00000111,作为取flags低3位的掩码
  
static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5) //小于2^5,flags成员的高5位即可表示
        return SDS_TYPE_5;
    if (string_size < 1<<8) //小于2^8,8位整数(sdshdr8里的uint8_t)即可表示string_size
        return SDS_TYPE_8;
    if (string_size < 1<<16) //小于2^16,16位整数(sdshdr16里的uint16_t)即可表示string_size
        return SDS_TYPE_16;
    //小于2^32,32位整数(sdshrd32里的uint32_t)即可表示string_size,
    //1ll是指1long long(至少64位)的意思,如果没有ll,1就是一个int,假设int为4字节32位,
    //1<<32就会导致undefined behavior.
    if (string_size < 1ll<<32) 
        return SDS_TYPE_32;
    return SDS_TYPE_64; //若sds的长度超过2^64,则所有类型都不法表示这个sds的len
}

注意这里面其实我们判断使用sdshrd用那个类型,只需要flags&SDS_TYPE_MASK 和 SDS_TYPE_n 比较即可(之所以需要 SDS_TYPE_MASK 是因为有 sdshdr5 这个特例,它的高 5 位不一定为 0)

所以涉及到一些关于字符串相关的函数,都存放在sds.h 文件中,比如求字符串长度的函数,只需要将sds作为参数,通过比较 flags&SDS_TYPE_MASK 和 SDS_TYPE_n 来判断该 sds 属于哪种类型 sdshdr,再按照指定的 sdshdr 类型取出 sds 的相关信息。例如 sdslen 函数(获取字符串长度):

//返回一个类型为T包含s字符串的sdshdr的指针
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) 
//用sdshdr5的flags成员变量做参数返回sds的长度,这其实是一个没办法的hack  
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)  
#define SDS_TYPE_BITS 3
static inline size_t sdslen(const sds s) {
    //通过 s[-1]我们可以获得 sds 所属的 sdshdr 的成员变量 flags
    unsigned char flags = s[-1]; 
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;//取出sdshdr的len成员
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;

类似 sdslen 这样利用 sds 找到 sdshdr 类型的还有如下几个函数,就不一一分析了:

static inline size_t sdsavail(const sds s)
static inline void sdssetlen(sds s, size_t newlen)
static inline void sdsinclen(sds s, size_t inc)
static inline size_t sdsalloc(const sds s)
static inline void sdssetalloc(sds s, size_t newlen)

以上就是Redis中字符串的表示原理。

总结

本节内容主要讲解了Redis对字符串的表示方法,之所以不采用c语言中的字符串表示,主要基于安全性、内存的分配及提高字符长度的获取时间复杂度等,而且在3.2之后采用的5中sdshdr结构来表示不同的字符串更加极致的节省了内存的空间,下节课我们将详细介绍Redis的5大数据结构底层原理,也希望大家下来详细了解一下string、list、hash、set、zset这5种类型的API。

本文分享自微信公众号 - 服务端思维(gh_c3775931ac9d)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Apache Dubbo 反序列化漏洞通告及解决方案

    近日检测到Apache Dubbo官方发布了CVE-2019-17564漏洞通告,360灵腾安全实验室判断漏洞等级为高,利用难度低,威胁程度高,影响面大。建议使...

    用户2781897
  • 数据库sql面试需要准备哪些?

    SQL 是用于数据分析和数据处理的最重要的编程语言之一,因此与数据科学相关的工作(例如数据分析师、数据科学家和数据工程师)在面试时总会问到关于 SQL 的问题。...

    用户2781897
  • 我们分析了GitHub上5.46 亿条日志,发现中国开源虽然贡献大但还有这些不足...

    全球最大代码托管平台 GitHub 在 2019 年发布的年度报告中显示, GitHub 上目前已有超过 4000 万开发人员、将近 300 万个组织帐户。其中...

    用户2781897
  • Simple Dynamic Strings(SDS)源码解析和使用说明一

            SDS是Redis源码中一个独立的字符串管理库。它是由Redis作者Antirez设计和维护的。一开始,SDS只是Antirez为日常开发而实现...

    方亮
  • redis设计与实现系列1-SDS

    redis没有直接使用c语言的传统字符串表示(以空字符结尾的字符数组),而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS...

    用户5705150
  • Redis中String数据类型原理实现

    首先Redis是KV数据结构,跟JDK中的Map是一样的,Redis是通过hashtable实现的,我们把这个叫做外层的哈希,那么每一个KY就是一个entry,...

    用户7386338
  • 从进球到生成视频新闻只要20秒,新华社和阿里对世界杯下手了

    一旁的伪球迷、大路的女朋友阿丽举起手中的pad:“咦?APP上推送了一条进球新闻。”

    量子位
  • 超火动态价格面积图:手把手教你!

    近日,公众号推出了一篇名为《超火动态排序图:代码不到40行,手把手教你!》的文章,反向十分强烈。各大公众号进行的了转载,知乎也是有400+的点赞。

    量化投资与机器学习微信公众号
  • 草图秒变风景照,英伟达神笔马良GaoGAN终于开源了

    还记得英伟达在 GTC 2019 披露的令人惊叹的图像生成器 GauGAN 吗?仅凭几根线条,草图秒变风景照,自动生成照片级逼真图像的技术堪比神笔马良。

    代码医生工作室
  • 案例实战|泰坦尼克号船员获救预测(数据预处理部分)

    01 — 背景介绍 已经推送了一些经典的机器学习和深度学习相关的算法,明白了这些算法的原理,对我们之后解决实际问题会打下很好的基础,如何将这些零散的知识综合起来...

    double

扫码关注云+社区

领取腾讯云代金券