专栏首页golang+phpredis源码之SDS

redis源码之SDS

1:SDS介绍

我们在redis中执行命令

set key name

的时候,key和name都是字符串类型,而且字符串(string)在redis中是会经常用到的类型,那redis是如何保存字符串的呢?我们接下来往下看 众所周知,redis是c写的,在c中使用char来保存字符串,并且用\0作为字符串的结尾,但是redis不是这样保存的,redis是使用一种叫SDS的结构来保存字符串的。结构如下(redis3.2以前)

 struct sdshdr{
 
 int len;
 
 int free;
 
 char buf[];
 
} 

那么问题来了,redis为什么 会用SDS的结构,而不直接用c语言的字符串,我们来看看他们的区别

1:计算字符串长度的区别

对于c来说,计算字符串的长度的方式就是遍历,遇到\0就停止,所以复杂对是O(n),而SDS直接保存了字符串的长度,复杂度是O(1)

2:保证二进制的安全

因为SDS并不是以\0为结尾的标志,自然就保证了二进制的安全

3:内存管理策略(预分配内存和惰性空间释放策略)

redis是一个高速的缓存数据库,需要频繁的对字符串进行操作,如果内存分配错误,会导致很严重的后果,就算内存分配没问题,频繁的内存分配也是非常耗费时间的,所以这些都是应该去避免的

惰性空间释放策略

在SDS中首先用到了惰性空间释放策略,惰性空间释放用于优化SDS的字符串缩短操作。当要缩短SDS保存的字符串时,程序并不立即使用内存充分配来回收缩短后多出来的字节,而是使用表头的free成员将这些字节记录起来,并等待将来使用。源码如下

void sdsclear(sds s) { //重置sds的buf空间,懒惰释放
 
 struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
 
    sh->free += sh->len; //表头free成员+已使用空间的长度len = 新的free
 
    sh->len = 0; //已使用空间变为0
 
    sh->buf[0] = '\0'; //字符串置空
 
}
 
预分配内存

扩容策略是字符串在长度小于 1M 之前,扩容空间采用加倍策略,也就是保留 100% 的冗余空间。当长度超过1M 之后,为了避免加倍后的冗余空间过大而导致浪费,每次扩容只会多分配 1M大小的冗余空间。

4:兼容c语言函数库 (字符串后面会自动加上\0)

3.2版本以后的SDS结构

前面的len和free以及char这种结构看起来很好,但是是存在一定的问题的

 struct sdshdr{
 
 int len;
 
 int free;
 
 char buf[];
 
}

len和free都是int类型,都是4byte也就是32bit,能表示42亿左右的范围,大大的造成了空间的浪费,所以在3.2以后对SDS有一定的更改,更改如下

typedef char *sds;
/* 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 of 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[];
 
};
 
.........
 

sdshdr5表示的是用5个bit位来表示数据的长度,sdshdr8就是表示用8个bit位来表示数据的长度,以此类推 sdshdr5的内存分配如图

当需要存储的数据长度超过31,就需要用sdshdr8来表示 sdshdr8的内存分配如图

其余的sdshdr16以上的都是以此类推,判断方式源码如下

static inline char sdsReqType(size_t string_size) {
 
 if (string_size < 1<<5) //2^5-1
 
 return SDS_TYPE_5;
 
 if (string_size < 1<<8) //2^8-1
 
 return SDS_TYPE_8;
 
 if (string_size < 1<<16) //2^16-1
 
 return SDS_TYPE_16;
 
#if (LONG_MAX == LLONG_MAX)
 
 if (string_size < 1ll<<32) //2^32-1
 
 return SDS_TYPE_32;
 
 return SDS_TYPE_64;
 
#else
 
 return SDS_TYPE_32;
 
#endif
 
}

本文分享自微信公众号 - 程序员养成日记(programmer_grow),作者:redis

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • svn常用命令

    de >svn checkout path(path是服务器 上的目录)例如:svn checkout svn://192.168.1.1/pro/domai...

    程序员养成日记
  • php运行生命周期--请求初始化php_request_startup

    重新为output_globals分配内存,初始化与输出处理程序相关的堆栈,并将OG宏的flags设置为激活状态。

    程序员养成日记
  • 绝对能让你彻底明白的Redis的内存淘汰策略

    在 redis 中,对于已经过期的数据,Redis 采用两种策略来处理这些数据,分别是惰性删除和定期删除

    程序员养成日记
  • 多个单词的命名规范有哪些优缺点?

    嘿嘿~我写这篇文章主要还是想向大家请教的,我们今天聊三个最常用的吧:横杠 - 连接、下划线 _ 连接、驼峰。

    benny
  • python实现贪吃蛇双人大战

    本文实例为大家分享了python实现贪吃蛇双人大战的具体代码,供大家参考,具体内容如下

    砸漏
  • 3分钟了解清楚持续集成、持续交付、持续部署

    近些年来,持续集成、持续交付以及持续部署这几个热词总是在大家的眼前晃来晃去!在招聘信息和面试过程中也会经常提及!在这里我就用三分钟时间来带大家了解他们!

    测试开发技术
  • 从零开始学习 PyTorch:多层全连接神经网络

    本文引自博文视点新书《深度学习入门之PyTorch》第3 章——多层全连接神经网络 内容提要:深度学习如今已经成为科技领域最炙手可热的技术,在《深度学习入门之...

    AI科技大本营
  • 服务机器人常用的定位导航技术及优缺点分析

    自主定位导航是机器人实现智能化的前提之一,是赋予机器人感知和行动能力的关键因素。如果说机器人不会自主定位导航,不能对周围环境进行分析、判断和选择,规划路径,那么...

    机器人网
  • 绘制热图

    colormap <- colorRampPalette(rev(brewer.pal(n = 7, name = "RdYlBu")))(100)

    爱学习的小明明
  • 使用jQuery的animate方法制作滑动菜单

    周末看Ziv小威的博客《制作滑动条菜单,如何延时处理滑动效果,避免动画卡顿》,参见地址:http://www.cnblogs.com/zivxiaowei/p/...

    八哥

扫码关注云+社区

领取腾讯云代金券