redis 为什么把简单的字符串设计成 SDS?

范蠡 2021-04-08 11:18:30
简单 设计 redis 字符 字符串


2021开工第一天,就有小伙伴私信我,还给我分享了一道他面阿里的redis题(这家伙绝比已经拿到年终奖了),我看了以后觉得挺有意思,题目很简单,是那种典型的似懂非懂,常常容易被大家忽略的问题。这里整理出来分享一下,顺便自己巩固一下基础,希望对正在面试和想要面试的兄弟有点帮助。

题目大致是这样的

面试官:了解redisString数据结构底层实现嘛?

铁子:当然知道,是基于SDS实现的

面试官:redis是用C语言开发的,那为啥不直接用C的字符串,还单独设计SDS这样的结构呢?

铁子:·····

“其实看得出面试官是想看看,铁子是只停留在redis的使用层面,还是对底层数据结构有过更深入的研究,面试嘛都爱这样问大家都懂得。

我们知道redis是用C写的,但它却没有完全直接使用C的字符串,而是自己又重新构建了一个叫简单动态字符串SDS(simple dynamic string)的抽象类型。

redis也支持使用C语言的传统字符串,只不过会用在一些不需要对字符串修改的地方,比如静态的字符输出。

而我们开发中使用redis,往往会经常性的修改字符串的值,这个时候就会用SDS来表示字符串的值了。有一点值得注意:在redis数据库中,key-value键值对含有字符串值的,都是由SDS来实现的。

比如:在redis执行一个最简单的set命令,这时redis会新建一个键值对。

127.0.0.1:6379> set xiaofu "程序员内点事"

此时键值对的keyvalue都是一个字符串对象,而对象的底层实现分别是两个保存着字符串xiaofu程序员内点事SDS结构。

再比如:我向一个列表中压入数据,redis 又会新建一个键值对。

127.0.0.1:6379> lpush xiaofu "程序员内点事" "程序员小富"

这时候键值对的键和上边一样,还是一个由SDS实现的字符串对象,键值对的值是一个包含两个字符串对象的列表对象了,而这两个对象的底层也是由SDS实现。

SDS结构

一个SDS值的数据结构,主要由lenfreebuf[]这三个属性组成。

struct sdshdr{
int free; // buf[]数组未使用字节的数量
int len; // buf[]数组所保存的字符串的长度
char buf[]; // 保存字符串的数组
}

其中buf[]为实际保存字符串的char类型数组;free表示buf[]数组未使用字节的数量;len表示buf[]数组所保存的字符串的长度。

例如上图表示的是buf[]保存长度为6个字节的字符串,未使用的字节数free为0,但是眼尖的同学会发现这明明是7个字符,还有一个"\0"啊?

上边提到过SDS没有完全直接使用C的字符串,还是沿用了一些C特性的,比如遵循C的字符串以空格符结尾的规则,这样还可以使用一部分C字符串的函数。而对于SDS来说,空字符串占用的一字节是不计算在len属性里的,会为他分配额外的空间。

简单了解SDS结构后,下边我们来看看SDS相比于C字符串有哪些优点。

效率高

举个例子:工作中使用redis,经常会通过STRLEN命令得到一个字符串的长度,在SDS结构中len属性记录了字符串的长度,所以我们获取一个字符串长度直接取len的值,复杂度是O(1)。

而如果用C字符串,在获取一个字符串长度时,需对整个字符串进行遍历,直至遍历到空格符结束(C中遇到空格符代表一个完整字符串),此时的复杂度是O(N)。

在高并发场景下频繁遍历字符串,获取字符串的长度很有可能成为redis的性能瓶颈,所以SDS性能更好一些。

数据溢出

上边提到C字符串是不记录自身长度的,相邻的两个字符串存储的方式可能如下图,为字符串分配了合适的内存空间。

如果此时我想把“程序员内点事”改成“程序员内点事123”,可之前分配的内存只有6个字节,修改后的字符串需要9个字节才能放下啊,怎么搞?

没办法只能侵占相邻字符串的空间,自身数据溢出导致其他字符串的内容被修改。

而SDS很好的规避了这点,当我们需要修改数据时,首先会检查当前SDS空间len是否满足,不满足则自动扩容空间至修改所需的大小,然后再执行修改,如下图所示。

不过有个特殊的地方,在把“程序员内点事”的6个字节扩容到“程序员内点事123”9个字节后,发现free属性的值变成了扩容后字符串的总长度,这就涉及到下边要说的内存重分配策略了。

内存重分配策略

C字符串长度是一定的,所以每次在增长或者缩短字符串时,都要做内存的重分配,而内存重分配算法通常又是一个比较耗时的操作,如果程序不经常修改字符串还是可以接受的。

但很不幸,redis作为一个数据库,数据肯定会被频繁修改,如果每次修改都要执行一次内存重分配,那么就会严重影响性能。

SDS通过两种内存重分配策略,很好的解决了字符串在增长和缩短时的内存分配问题。

1.空间预分配

空间预分配策略用于优化SDS字符串增长操作,当修改字符串并需对SDS的空间进行扩展时,不仅会为SDS分配修改所必要的空间,还会为SDS分配额外的未使用空间free,下次再修改就先检查未使用空间free是否满足,满足则不用在扩展空间。

通过空间预分配策略,redis可以有效的减少字符串连续增长操作,所产生的内存重分配次数。

额外分配未使用空间free的规则:

  • 如果对 SDS 字符串修改后,len 值小于 1M,那么此时额外分配未使用空间 free 的大小与len相等。
  • 如果对 SDS 字符串修改后,len 值大于等于 1M,那么此时额外分配未使用空间 free 的大小为1M

2.惰性空间释放

惰性空间释放策略则用于优化SDS字符串缩短操作,当缩短SDS字符串后,并不会立即执行内存重分配来回收多余的空间,而是用free属性将这些空间记录下来,如果后续有增长操作,则可直接使用。

数据格式多样性

C字符串中的字符必须符合某些特定的编码格式,而且上边我们也提到,C字符串以\0空字符结尾标识一个字符串结束,所以字符串里边是不能包含\0的,不然就会被误认是多个。

由于这种限制,使得C字符串只能保存文本数据,像音视频、图片等二进制格式的数据是无法存储的。

redis 会以处理二进制的方式操作Buf数组中的数据,所以对存入其中的数据未做任何的限制、过滤,只要存进来什么样,取出来还是什么样。

总结

上边只是 redis 数据结构的一点基础知识,没什么难度,但以我的面试经验,如果被问这类问题,不要只含糊其辞的说出底层是SDS,有理有据的把为什么这样实现也说出来。

一来可以显得自己基本功扎实,如果表达的在条理清晰,是个很不错的加分项;在一个主动打消面试官问下去的念头,当然就怕不按套路出牌的人!

本文分享自微信公众号 - 高性能服务器开发(easyserverdev)

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

原始发表时间: 2021-03-31

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

版权声明
本文为[范蠡]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/1810402

  1. Java 学生成绩管理系统课程设计,附源码!
  2. Java arbitrary audio to MP3
  3. DNS of docker
  4. Docker - build log monitoring system
  5. SSM + MySQL + Maven + Shiro WMS
  6. Top 10 reasons to fall in love with java!
  7. 一本关于HTTP的恋爱日记
  8. 【RocketMQ源码分析】深入消息存储(3)
  9. SpringCloud+Nacos实现服务配置中心(Hoxton版本)
  10. SCIP:构造数据抽象--数据结构中队列与树的解释
  11. SCIP:构造过程抽象--面向对象的解释
  12. 使用 docker 进行 ElasticSearch + Kibana 集群搭建
  13. Spring IOC 特性有哪些,不会读不懂源码!
  14. [DB Bao 41] use of PMM -- monitoring mysql, PG, mongodb, proxysql, etc
  15. Spring Cloud 升级之路 - 2020.0.x - 3. Undertow 的 accesslog 配置
  16. [DB Bao 42] MySQL high availability architecture MHA + proxysql realizes read-write separation and load balancing
  17. [DataGuard] recovery of physical DG in case of losing archive files in main database (7)
  18. MyBatis(3)Map和模糊查询拓展
  19. 【TTS】AIX->Linux--基于RMAN(真实环境)
  20. 【TTS】传输表空间AIX->linux基于rman
  21. 【TTS】传输表空间AIX asm -> linux asm
  22. 【TTS】传输表空间Linux asm -> AIX asm
  23. 【DB宝40】MySQL高可用管理工具Orchestrator简介及测试
  24. 【TTS】传输表空间Linux ->AIX 基于rman
  25. 一本关于HTTP的恋爱日记
  26. 【RocketMQ源码分析】深入消息存储(3)
  27. SpringCloud+Nacos实现服务配置中心(Hoxton版本)
  28. SICP:构造过程抽象--面向对象的解释
  29. 3w 字长文爆肝 Java 基础面试题!太顶了!!!
  30. Spring Cloud 升级之路 - 2020.0.x - 3. Undertow 的 accesslog 配置
  31. win10卸载mysql5.7
  32. MySQL 批量插入,如何不插入重复数据?
  33. k8s cronjob应用示例
  34. 非常规方法,轻松应对Oracle数据库危急异常
  35. Oracle hang 之sqlplus -prelim使用方法
  36. 如何全文搜索oracle官方文档
  37. Java student achievement management system course design, with source code!
  38. win10安装mysql8.0
  39. 手把手教你写一个spring IOC容器
  40. JAVA 中的异常(1)- 基本概念
  41. A love diary about http
  42. navicat连接win10 mysql8.0 报错2059
  43. [rocketmq source code analysis] in depth message storage (3)
  44. Implementation of service configuration center with spring cloud + Nacos (Hoxton version)
  45. SCIP: constructing data abstraction -- Explanation of queue and tree in data structure
  46. SCIP: abstraction of construction process -- object oriented explanation
  47. Using docker to build elasticsearch + kibana cluster
  48. What are the spring IOC features? I can't understand the source code!
  49. Spring cloud upgrade road - 2020.0. X - 3. Accesslog configuration of undertow
  50. 导致Oracle性能抖动的参数提醒
  51. 风险提醒之Oracle RAC高可用失效
  52. 小机上运行Oracle需要注意的进程调度bug
  53. Oracle内存过度消耗风险提醒
  54. Oracle SQL monitor
  55. 使用Bifrost实现Mysql的数据同步
  56. 揭秘Oracle数据库truncate原理
  57. 看了此文,Oracle SQL优化文章不必再看!
  58. Mybatis (3) map and fuzzy query expansion
  59. Kafka性能篇:为何这么“快”?
  60. 两个高频设计类面试题:如何设计HashMap和线程池