一.Redis中那些你不知道的秘密-五大基本结构String的实现原理

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: Redis已经成为解决高并发的必备利器,你可能已经把它玩的很熟了,但是对于它的底层,你又了解几分呢?本篇文章我们来聊聊Redis中那些你不知道的秘密之Redis五大基本结构的实现原理。你也许知道Redis常用的存储结构有 String,List,Set,ZSet,Hash,但还远远不够,本文章将带你一步一步走进Redis更深处的奥秘。

学习使用,老鸟飞过,欢迎交流

前言

Redis已经成为解决高并发的必备利器,你可能已经把它玩的很熟了,但是对于它的底层,你又了解几分呢?

本篇文章我们来聊聊Redis中那些你不知道的秘密之Redis五大基本结构的实现原理。你也许知道Redis常用的存储结构有 String,List,Set,ZSet,Hash,但还远远不够,本文章将带你一步一步走进Redis更深处的奥秘。

简单动态字符串SDS

SDS(simple dynamic string, SDS)译为简单动态字符串,是Redis自己封装的字符串结构,如下:

struct sdshdr{
   
   
    //字符串长度,即buf已用字节的数量
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组,用于保存字符串
    char buf[];
}

SDS内存分配图
在这里插入图片描述

String是Redis最常用的一种存储结构了,我们都知道Redis是使用C语言开发的高性能Nosql数据库,那为什么Redis没有直接使用C的String结构,而是使用的是自己开发的String结构SDS呢?基于两个原因:①取字符串长度的时间复杂度 ②二进制安全问题

为什么要定义len

这里不得不说一下C语言的String,C语言的字符串和其他语言都差不多,底层使用char[] 实现,但是在C语言中要获取字符串的长度需要遍历整个char[] 来完成,时间复杂度是 O(N) ,性能不是最优不说,它还有一个二进制安全问题。

在 C 中使用 ‘\0’ 来标志一个字符串的结束,比如:['h','e','l','l','o','\0'], 如果有一个特殊数据正好内容中有一个空字符,那么在C中这个数据只能被识别到空字符前面部分的数据导致数据不完整,所以在C中String这种结构也是没法保存除文本数据以外的图片、音频等数据。

而Redis不一样,它的SDS结构定义了len来维护char[]的已有数据的长度,要取数据长度直接取len,复杂度为 O(1); 读取字符串不依赖终止符‘\0’,保证了二进制安全,同时可以存储图片,音频等内容。

为什么要定义free

在C语言中每次字符串增长都需要重新分配一次内存空间,这个是非常耗性能的工作,在Redis中字符串是最常用的存储类型,当然会被频繁的修改,如果每次都重新分配内存对性能的损耗极大。

那么在Redis的SDS中,存储数据的char buf[];的实际大小是 len + free + 1

  • len表示字符串的长度,也表示buf中已经被使用的空间的大小。
  • free表示buf中没有被使用的空间的大小。
  • 其中多余的1个字节是用来存储’\0’的

即:char buf[]分配的内存空间是大于实际存储的字符串的长度的。那它为什么要多分配出 free 这一部分空间呢?①是预分配空间,防止每次修改都重新分配空间 ②防止缓冲区溢出

在C语言中,根据字符串处理特性,对于字符串的拼接、复制等操作,C语言开发者必须确保目标字符串的空间足够大,不然字符串增长时空间不够就会出现每次溢出的情况。

而在Redis中它是怎么处理的呢?每次在拼接字符串的时候,SDS的API内部会先对 free未使用的部分空间做判断看是否装得下最新的内容,如果装得下就不用开辟内存空间了,如果装不下再开辟内存空间,当然新开辟空间也不是开辟刚好放得下的空间大小,而是会额外申请len长度的空间作为 free,以便下一次使用,这是不是又是一次性能的提升呢?

SDS扩容图:
在这里插入图片描述

Redis的SDS如何释放内存

Redis采用的是惰性空间释放,如果Redis的String长度缩减它不会重新分配内存空间,而是通过较少len,增加free的方式来空大free的内存空间,这样的好处是减少内存重新分配,同时free可以用来进行下一次字符串拼接时使用这又是一次优化。当然也可以通过调用SDS提供的API直接释放内存,在需要的时候也能真正的释放掉多余的空间
在这里插入图片描述

Redis的极致优化

到此,Redis的SDS已经做了很好的优化了,但是为了把性能做到极致Redis还针对不同长度的String定制了不同的存储结构sdshdr5,sdshdr8,sdshdr32,sdshdr64。为什么这么做呢?例如:一个int占4个字节,在实际的应用中我们往往不会存储那么长的字符串,每个字符串都4个字节就太浪费空间了。

如果我们这样分配内存:短字符串len+free的长度为1个字节就够了,长字符串使用2个字节或者4个字节,更惨的字符串使用8个字节,这样会不会跟省内存?但是这样的话应该如何来区分这几种类型呢?在Redis 5.0版本中做了这样的改变:

sdshdr5{
   
   
    //flags一个字节8位,低3位存储类型,高5位存储长度
    unsigned char flags;
    //buf存放实际的内容
    char buf[];
}

Redis增加了flags占1字节(8bit),低三位用来表示String的type(短字符串,长字符串...),高5位存储长度len。

sdshdr5结构如下:
在这里插入图片描述
这样的话能够表示的长度区间为 0 到 31(2的5次方-1),那么如果字符串长度大于31呢?1个字节就存储不下了,按照之前的思路,把len和free单独存放,SDS几种存储结构如下:

/* sdshdr5和其他几种结构不一样 */
struct __attribute__ ((__packed__)) sdshdr5 {
   
   
    unsigned char flags; /* 低三位表示类型, 高五位表示字符串长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
   
   
    uint8_t len; /* 字符串已用长度,1个字节存储*/
    uint8_t alloc; /* 分配总长度,1个字节存储 */
    unsigned char flags; /* 低3位表示类型,高5位未使用作为预留空间 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
   
   
    uint16_t len; /* 字符串已用长度,2字节*/
    uint16_t alloc; /* 分配总长度,2字节 */
    unsigned char flags; /* 低3位表示类型,高5位未使用作为预留 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
   
   
    uint32_t len; /* 字符串已用长度,4字节*/
    uint32_t alloc; /* 分配总长度,4字节 */
    unsigned char flags; /* 低3位表示类型,高5位未使用作为预留 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
   
   
    uint64_t len; /* 字符串已用长度,8字节*/
    uint64_t alloc; /* 分配总长度,8字节 */
    unsigned char flags; /* 低3位表示类型,高5位未使用作为预留 */
    char buf[];
};
  • len:表示buf已经占用的字节数
  • alloc:表示buf分配的总数量,和len相减就是free的字节数
  • flags:表示SDS类型,第3位表示类型,高5位预留
  • buf:真正存储字符串数据的空间,是一个char[]数组。

可以看到,sdshdr5和其他几种不一太样。sdshdr5是把len放在flags中,而后面几种是把len和总长度alloc单独提出来,flags前3位表示类型,后5位作为预留。

这样一来那Redis该如何区分字符串长度来使用不同的存储类型呢?简单,做一个字符串长度判断即可,如下:

sds sdsnewlen(const void *init, size_t initlen) {
   
   
    void *sh;
    sds s;
    /* 计算出字符串长度,选择不同的SDS的类型 */
    char type = sdsReqType(initlen);
    /*SDS_TYPE_5  转换成SDS_TYPE_8 */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
   /* 计算不同的头部需要长度 */
    int hdrlen = sdsHdrSize(type);
    /* 指向flags */
    unsigned char *fp; 

    /* 分配内存,+1是用来存储\0,兼容C语言的 */
    sh = s_malloc(hdrlen+initlen+1);
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;

    s = (char*)sh+hdrlen;

    fp = ((unsigned char*)s)-1;

    /* 根据不同的类型,初始化sdsHeader */
    switch(type) {
   
   
        case SDS_TYPE_5: {
   
   
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
   
   
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
   
   
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
   
   
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
   
   
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    /* 字符串赋值 */
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

好了文章就讲到这把,那么Redis对于String到底做了什么样的处理呢,这里总结一下:

  • Redis定义了自己的String结构即:SDS
  • 为了解决二进制安全问题SDS定义了len来表示已有字符串长度
  • 为了防止缓冲区溢出SDS在分配内存的时候做了预留空间即:free部分
  • 内存惰性释放,多余的内存加入free做预留,也是优化了内存频繁分配
  • 针对不同的String长度定制了不同的SDS结构

如果面试官问你:Redis为什么那么快,你怎么答?

  • Redis是单线程,没有锁的竞争,没有线程切换的性能开销
  • Redis基于内存读写并发能力强
  • Redis结构简单key-value存储
  • Redis采用多路IO复用模型
  • Redis对String做了极致优化SDS

是不是可以把Redis底层的优化加上?
Redis源码地址:https://github.com/antirez/sds/blob/master/sds.c

文章结束,希望对你有所帮助

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
4天前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
22 0
|
1天前
|
存储 缓存 NoSQL
由菜鸟到大神,谈谈redis的概念、实战、原理、高级使用方法
【5月更文挑战第18天】Redis是一个开源的内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。它支持多种类型的数据结构,如字符串、哈希、列表、集合、有序集合等。
16 10
|
4天前
|
存储 NoSQL 算法
Redis源码、面试指南(2)内存编码数据结构(下)
Redis源码、面试指南(2)内存编码数据结构
20 4
|
4天前
|
存储 NoSQL API
Redis源码、面试指南(2)内存编码数据结构(上)
Redis源码、面试指南(2)内存编码数据结构
15 0
|
4天前
|
负载均衡 NoSQL 关系型数据库
深入浅出Redis(六):Redis的主从架构与主从复制原理
深入浅出Redis(六):Redis的主从架构与主从复制原理
|
4天前
|
NoSQL Java Unix
Redis基础操作 String List
Redis基础操作 String List
10 0
|
4天前
|
监控 NoSQL 算法
深入剖析Redis哨兵模式的原理和应用
Redis的哨兵模式是实现高可用性和自动故障转移的机制,当主服务器故障时,哨兵能自动检测并进行故障转移,确保服务连续和稳定性。哨兵模式通过监控主从服务器状态、自动故障转移、防止数据不一致,提高容错能力和负载均衡,降低运维成本,实现高可用性。哨兵通过检测主观下线和客观下线状态,以及选举Leader Sentinel来协调故障转移。Raft算法在其中用于领导者选举和状态一致性。哨兵模式通过综合考虑多种因素选举新主服务器并执行故障转移,保障集群稳定运行。
88 0
深入剖析Redis哨兵模式的原理和应用
|
4天前
|
存储 NoSQL 安全
Redis入门到通关之Redis数据结构-String篇
Redis入门到通关之Redis数据结构-String篇
35 1
|
4天前
|
NoSQL Redis
Redis入门到通关之Redis主从数据同步原理
Redis入门到通关之Redis主从数据同步原理
31 0
|
4天前
|
存储 NoSQL Redis
Redis入门到通关之Redission原理
Redis入门到通关之Redission原理
23 0