Redis系列-3.Redis底层数据结构原理(上)

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: Redis系列-3.Redis底层数据结构原理

动态字符串SDS


SDS 简介


无论是 Redis 的 Key 还是 Value,其基础数据类型都是字符串。例如,Hash 型 Value 的field 与 value 的类型、List 型、Set 型、ZSet 型 Value 的元素的类型等都是字符串。虽然 Redis是使用标准 C 语言开发的,但并没有直接使用 C 语言中传统的字符串表示,而是自定义了一种字符串。这种字符串本身的结构比较简单,但功能却非常强大,称为简单动态字符串,Simple Dynamic String,简称 SDS。


注意,Redis 中的所有字符串并不都是 SDS,也会出现 C 字符串。C 字符串只会出现在字符串“字面常量”中,并且该字符串不可能发生变更。


SDS 结构


SDS 不同于 C 字符串。C 字符串本身是一个以双引号括起来,以空字符’\0’结尾的字符序列。但 SDS 是一个结构体,定义在 Redis 安装目录下的 src/sds.h 中:

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

例如执行 SET country “China”命令时,键 country 与值”China”都是 SDS 类型的,只不过一个是 SDS 的变量,一个是 SDS 的字面常量。”China”在内存中的结构如下:

通过以上结构可以看出,SDS 的 buf 值实际是一个 C 字符串,包含空字符’\0’共占 6 个字节。但 SDS 的 len 是不包含空字符’\0’的。

该结构与前面不同的是,这里有 3 字节未使用空间。


SDS 的优势


C 字符串使用 Len+1 长度的字符数组来表示实际长度为 Len 的字符串,字符数组最后以空字符’\0’结尾,表示字符串结束。这种结构简单,但不能满足 Redis 对字符串功能性、安全性及高效性等的要求。


防止”字符串长度获取”性能瓶颈


对于 C 字符串,若要获取其长度,则必须要通过遍历整个字符串才可获取到的。对于超长字符串的遍历,会成为系统的性能瓶颈。


但,由于 SDS 结构体中直接就存放着字符串的长度数据,所以对于获取字符串长度需要消耗的系统性能,与字符串本身长度是无关的,不会成为 Redis 的性能瓶颈。


保障二进制安全


C 字符串中只能包含符合某种编码格式的字符,例如 ASCII、UTF-8 等,并且除了字符串末尾外,其它位置是不能包含空字符’\0’的,否则该字符串就会被程序误解为提前结束。而在图片、音频、视频、压缩文件、office 文件等二进制数据中以空字符’\0’作为分隔符的情况是很常见的。故而在 C 字符串中是不能保存像图片、音频、视频、压缩文件、office 文件等二进制数据的。


但 SDS 不是以空字符’\0’作为字符串结束标志的,其是通过 len 属性来判断字符串是否结束的。所以,对于程序处理 SDS 中的字符串数据,无需对数据做任何限制、过滤、假设,只需读取即可。数据写入的是什么,读到的就是什么。


减少内存再分配次数


SDS 采用了空间预分配策略与惰性空间释放策略来避免内存再分配问题。


空间预分配策略是指,每次 SDS 进行空间扩展时,程序不但为其分配所需的空间,还会为其分配额外的未使用空间,以减少内存再分配次数。而额外分配的未使用空间大小取决于空间扩展后 SDS 的 len 属性值。


  • 如果 len 属性值小于 1M,那么分配的未使用空间 free 的大小与 len 属性值相同。
  • 如果 len 属性值大于等于 1M ,那么分配的未使用空间 free 的大小固定是 1M。


SDS 对于空间释放采用的是惰性空间释放策略。该策略是指,SDS 字符串长度如果缩短,那么多出的未使用空间将暂时不释放,而是增加到 free 中。以使后期扩展 SDS 时减少内存再分配次数。


兼容 C 函数


Redis 中提供了很多的 SDS 的 API,以方便用户对 Redis 进行二次开发。为了能够兼容 C函数,SDS 的底层数组 buf[]中的字符串仍以空字符’\0’结尾。


现在要比较的双方,一个是 SDS,一个是 C 字符串,此时可以通过 C 语言函数strcmp(sds_str->buf,c_str)


新版本的SDS


SDS结构大致上可以分为2大部分:header部分和buff部分,并且header部分和buff部分在内存中是连续的。


header部分


header部分保存的是SDS一些源数据信息。

其中:


  • len表示: 字符串的长度;
  • alloc表示:字符串的长度 + 额外预留空间的长度。alloc代表可用来存储字符空间的总大小,但是不包括null-term,所以是比实际分配出来的buff长度减1;


除了我们上面提到过的len和alloc,这里还多了一个flag字段。flag字段决定len和alloc的变量类型。具体什么意思呢?因为字符串大小不固定有长有短,比如我们要保存"hello"这个字符串,那么对于len和alloc变量来说,最合适的变量类型应该是uint8,用一个字节来存储就够了,如果用uint16、uint32或uint64都显得有点太浪费。基于此SDS根据需要保存的字符串长度设计了如下5种flag类型,flag本身占用1个字节,如下表所示:

flag flag_value 字符串长度(len)字节 (len、alloc) type
SDS_TYPE_5 0 特殊 特殊
SDS_TYPE_8 1 len < (1 << 8) 256 uint8
SDS_TYPE_16 2 len < (1 << 16) 65536 uint16
SDS_TYPE_32 3 len < (1 << 32) uint32
SDS_TYPE_64 4 len >= (1 << 32) uint64

假设我们要保存的字符串长度为len:


  • SDS_TYPE_5:这个比较特殊,注释上说未被使用,但是也不完全准确,无论如何这个类型都不是我们讨论的重点。
  • SDS_TYPE_8: 当len 小于 1 << 8,也就是小于256时,变量len和alloc用uint8类型。
  • SDS_TYPE_16: 当len 小于 1 << 16,也就是小于65536时,变量len和alloc用uint16类型。
  • SDS_TYPE_32: 当len 小于 1 << 32,也就是小于4294967296时,变量len和alloc用uint32类型。
  • SDS_TYPE_64: 当len 大于等于 1 << 32,也就是大于等于4294967296时,变量len和alloc用uint64类型。


我们来举个简单例子,假设我们要用SDS(“hello”)保存"hello"这个字符串。"hello"长度为5个字节,len为5,是小于 1 << 8。因此flag为SDS_TYPE_8,len、alloc变量类型为uint8各自占用一个字节,flag始终占用1个字节,如下图所示:

len值为5:表示hello字符串长度为5个字节;


alloc值为12: 表示一共分配出来可用空间12字节。buff总长度为13字节,由于null-term要额外占用1字节不能计算在内,因此需要减1;


flag值为1: 表示的是SDS_TYPE_8类型;


buff部分


Buff比较简单主要分为2个部分: 第一个部分是原生的C字符串,以null-term结尾,第二个部分是还未使用的额外空间,如下图所示。

前面说过SDS可以在一定程度上兼容C字符串,只要C-String部分是binary-safe,用户可以拿到SDS的buff起始地址(图中return to user),在只读场景当作原生C字符串使用。


还是以前面的"hello"字符串为例:

buff部分索引0~5存储"hello"的C字符串,索引6到索引12是预留空间还未使用。如果后续需要追加字符串并且在8个字节以内,即可直接修改,无需重新分配内存空间。


SDS扩容规则


当我们要往原SDS追加字符串时会触发SDS的扩容,为了阐述方便,我们定义如下变量:


len = 原SDS长度;


avail = 原SDS剩余预留空间长度;


addlen = 追加字符串的长度;


newlen = len + addlen 追加后字符串的总长度;


SDS的扩容规则如下:


  • 如果原SDS预留空间空间avail大于等于追加字符串的长度addlen,不会触发扩容。
  • 如果追加后的字符串总长度newlen小于1MB(1024*1024),将newlen扩容为2倍再加1(null-term),也就是newlen = newlen * 2 + 1。
  • 如果追加后的字符串总长度newlen大于等于1MB(1024*1024),将newlen额外扩容1MB再加1(null-term),也就是newlen = newlen + 1MB + 1。


需要注意的是,如果newlen大于flag所指定的范围,flag的类型也需要随之变大。


我们来举几个例子,依次看一下这2个扩容规则:


规则1:假设有如下图的SDS(“hello”),我们要追加字符串",world"。

变量初始化如下:


len = 5;


avail = alloc - len = 12 - 5 = 7;


addlen = “,world”的长度 = 6;


newlen = 5 + 6 = 11;


按照扩容规则,avail > addlen,不会触发扩容,因此可以原地追加,追加后的SDS如下图所示:


Redis系列-3.Redis底层数据结构原理(下):https://developer.aliyun.com/article/1414380

目录
相关文章
|
1月前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示;根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
184 86
|
19天前
|
存储 消息中间件 NoSQL
Redis数据结构:别小看这5把“瑞士军刀”,用好了性能飙升!
Redis提供5种基础数据结构及多种高级结构,如String、Hash、List、Set、ZSet,底层通过SDS、跳表等实现高效操作。灵活运用可解决缓存、计数、消息队列、排行榜等问题,结合Bitmap、HyperLogLog、GEO更可应对签到、UV统计、地理位置等场景,是高性能应用的核心利器。
|
1月前
|
存储 缓存 NoSQL
Redis基础命令与数据结构概览
Redis是一个功能强大的键值存储系统,提供了丰富的数据结构以及相应的操作命令来满足现代应用程序对于高速读写和灵活数据处理的需求。通过掌握这些基础命令,开发者能够高效地对Redis进行操作,实现数据存储和管理的高性能方案。
69 12
|
1月前
|
存储 消息中间件 NoSQL
【Redis】常用数据结构之List篇:从常用命令到典型使用场景
本文将系统探讨 Redis List 的核心特性、完整命令体系、底层存储实现以及典型实践场景,为读者构建从理论到应用的完整认知框架,助力开发者在实际业务中高效运用这一数据结构解决问题。
|
5月前
|
缓存 NoSQL 关系型数据库
美团面试:MySQL有1000w数据,redis只存20w的数据,如何做 缓存 设计?
美团面试:MySQL有1000w数据,redis只存20w的数据,如何做 缓存 设计?
美团面试:MySQL有1000w数据,redis只存20w的数据,如何做 缓存 设计?
|
26天前
|
存储 缓存 NoSQL
Redis专题-实战篇二-商户查询缓存
本文介绍了缓存的基本概念、应用场景及实现方式,涵盖Redis缓存设计、缓存更新策略、缓存穿透问题及其解决方案。重点讲解了缓存空对象与布隆过滤器的使用,并通过代码示例演示了商铺查询的缓存优化实践。
119 1
Redis专题-实战篇二-商户查询缓存
|
11天前
|
缓存 负载均衡 监控
135_负载均衡:Redis缓存 - 提高缓存命中率的配置与最佳实践
在现代大型语言模型(LLM)部署架构中,缓存系统扮演着至关重要的角色。随着LLM应用规模的不断扩大和用户需求的持续增长,如何构建高效、可靠的缓存架构成为系统性能优化的核心挑战。Redis作为业界领先的内存数据库,因其高性能、丰富的数据结构和灵活的配置选项,已成为LLM部署中首选的缓存解决方案。
|
13天前
|
缓存 运维 监控
Redis 7.0 高性能缓存架构设计与优化
🌟蒋星熠Jaxonic,技术宇宙中的星际旅人。深耕Redis 7.0高性能缓存架构,探索函数化编程、多层缓存、集群优化与分片消息系统,用代码在二进制星河中谱写极客诗篇。
|
5月前
|
缓存 NoSQL Java
Redis+Caffeine构建高性能二级缓存
大家好,我是摘星。今天为大家带来的是Redis+Caffeine构建高性能二级缓存,废话不多说直接开始~
773 0

热门文章

最新文章