Redis系列之底层数据结构SDS详解
目录
- 实验的环境
- 什么是SDS?
- 为什么要使用SDS?
- 获取字符串长度
- 避免缓存区溢出
- 减少字符串内存重新分配次数
- 二进制安全
- 兼容部分C字符串函数
- C字符串和SDS对比
- 总结
实验的环境
- Redis 6.0
- VSCode 1.88.1
什么是SDS?
SDS:Simple Dynamic String,翻译为简单动态字符串。
SDS是一种用于存储二进制数据的数据结构,具有动态扩容的特点,代码位于src/sds.h
和src/sds.c
SDS的总体数据结js构大致如图:在源码里sds包括几个部分,len
、alloc
、flags
、buf
,其中 sdshdr
是头部,buf
是真实存储数据android的地方,在存储的数据后面会跟一个\0
,所以数据加上\0
就是所谓的buf
- len:保存了SDS字符串的长度
- buf[]:保存数据的地方
- alloc:分别以uint8, uint16, uint32, uint64表示整个SDS
- flags:始终为一字节, 以低三位标示着头部的类型, 高5位未使用
查看源码sds.h,可以看到SDS里面有几种不同的头部,其中sdshdr5
实际并未使用到,所以实际上有四种不同的头部
/* Note: sdshdr5 is never used, we just Access the flags byte directly. * However is here to document the layout of type 5 SDS strings. */ struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb ophpf type, and 5 msb of string length */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; 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[]; };
为什么要使用SDS?
Redis是用C语言写的,为什么不直接就用C语言里的char
来定义字符串?
获取字符串长度
由于有len
属性,所以获取SDS
字符串的长度只需要读取len
属性,所以时间复杂度为O(1)
。
如果直接使用C
语言中的字符串来实现,获取字符串的长度需要遍历计数,时间复杂度为O(n)
。
避免缓存区js溢出
在C
语言中,如果使用strcat
函数来进行两个字符串的拼接,如果没有分配足够长度的内存空间,就会造成缓存区溢出。
而对于SDS
数据类型,在进行字符串修改的时候,会根据记录的len属性检查内存空间是否满足需求,如果不满足,会进行相应空间的扩展,所以不会出现缓存区溢出
减少字符串内存重新分配次数
在C
语言中字符串,是不会记录字符串的长度的,所以一旦修改了字符串,就需要重新分配内存,因为如果没有重新分配,字符串长度增大时会造成内存溢出区溢出,php长度减小时会造成内存泄漏。
而对于SDS来说,因为有长度熟悉len
和alloc
属性的存在,SDS
实现了空间预分配和惰性空间释放两种策略来减少重新分配内存
- 空间预分配:SDS对空间进行扩展的时候,扩展的内存比实际需要的多,这样可以减少字符串增长操作所需的内存重新分配次数
- 惰性空间释放:SDS对字符串进行缩短操作时,不会立即进行内存重新分配,来回收缩短后多余的内存空间,而是使用
alloc
将这些字节数量记录下来,等待后续使用
二进制安全
在C
语言中,是以空字符串作为字符串结束的标识,但是一些特殊的字符串,可能就包括空字符串的,所以容易丢失数据,不能正确存取。
而SDS是根据len
属性,以处理二进制的方式来处理buf
里的数据,所以保存数据更加安全
兼容部分C字符串函数
SDS可以重用C语言库<string.h>
中的一部分函数
C字符串和SDS对比
C字符串 | SDS |
---|---|
获取字符串长度时间复杂度为O(n) | 获取字符串的长度时间复杂度为O(1) |
不安全,可能会造成缓冲区溢出 | 安全,不会造成缓冲区溢出 |
修改字符串n次就需要进行n次内存分配 | 修改字符串长度n次,最多需要n次内存分配 |
只能保存文本数据 | 可以保存文本数据或者二进制数据 |
可以使用所有<string.h>库中的函数 | 可以使用一部分<string.h>库中的函数 |
总结
以上为个人经验,希望能给大家一个参考,也希望大家多多支持编程客栈(www.devze.com)。
精彩评论