江苏龙网

  1. 主页 > 生活百科 > >

Redis源码剖析之SDS

Redissds

SDS(simple dynamic string)是redis提供的字符串的封装 ， 在redis中也是存在最广泛的数据结构 ， 它也是很多其他数据结构的基础 ， 所以才选择先介绍SDS 。SDS也兼容部分C字符串API(strcmp,strlen) ， 它如何兼容C字符串我觉得也是有个很sao的操作 ， 等看完我这篇博客你就明白了 。在开始正式内容前 ， 我先抛几个问题(有些也是面试高频题) ， 带着问题去学习也是一种非常好的学习方法 。

  1. C语言中也算是支持String了 ， 为什么Redis还要自己封装一个？
  2. SDS中的D(dynamic)到底是什么含义？
  3. SDS的数据结构是啥样的？为什么要那么设计？
  4. SDS是如何兼容C字符串的?
Redis中sds相关的源码都在src/sds.c 和src/sds.h中（链接可以直接跳转到我中文注释版redis源码） ， 其中sds.h中定义了所有SDS的api ， 当然也实现了部分几个api ， 比如sds长度、sds剩余可用空间…… ， 不急着看代码 ， 我们先看下sds的数据结构 ， 看完后为什么代码那么写你就一目了然 。
sdshdr数据结构redis提供了sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64这几种sds的实现 ， 其中除了sdshdr5比较特殊外 ， 其他几种sdshdr差不只在于两个字段的类型差别 。我就拿 sdshdr8和sdshdr16来举例 ， 其struct定义分别如下 。
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* 已使用空间大小 */uint8_t alloc; /* 总共可用的字符空间大小 ， 应该是实际buf的大小减1(因为c字符串末尾必须是,不计算在内) */unsigned char flags; /* 标志位 ， 主要是识别这是sdshdr几 ， 目前只用了3位 ， 还有5位空余 */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[];};sdshdr32 sdshdr64也和上面的结构一致 ， 差别只在于len和alloc的数据类型不一样而已 。相较于c原生的字符串 ， sds多了len、alloc、flag三个字段来存储一些额外的信息 ， redis考虑到了字符串拼接时带来的巨大损耗 ， 所以每次新建sds的时候会预分配一些空间来应对未来的增长 ， sds和C string的关系熟悉JAVA的旁友可能会决定就好比java中String和StringBuffer的关系 。正是因为预留空间的机制 ， 所以redis需要记录下来已分配和总空间大小 ， 当然可用空间可用直接算出来 。
Redis源码剖析之SDS

文章插图
下一个问题 ， 为什么redis费心费力要提供sdshdr5到sdshdr64这五种SDS呢？我觉着这只能说明Redis作者抠内存抠到机制 ， 牺牲了代码的简洁性换取了每个sds省下来的几个字节的内存空间 。从sds初始化方法sdsnew和sdsnewlen中我们就可以看出 ， redis在新建sds时需要传如初始化长度 ， 然后根据初始化的长度确定用哪种sdshdr ， 小于2^8长度的用sdshdr8 ， 这样len和alloc只占用两个字节 ， 比较短字符串可能非常多 ， 所以节省下来的内存还是非常可观的 ， 知道了sds的数据结构和设计原理 ， sdsnewlen的代码就非常好懂了 ， 如下：
sds sdsnewlen(const void *init, size_t initlen) {void *sh;sds s;// 根据初始化的长度确定用哪种sdshdrchar type = sdsReqType(initlen);/* 空字符串大概率之后会Append ， 但sdshdr5不适合用来append ， 所以直接替换成sdshdr8 */if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;int hdrlen = sdsHdrSize(type);unsigned char *fp; /* flags pointer. */sh = s_malloc(hdrlen+initlen+1);if (sh == NULL) return NULL;if (init==SDS_NOINIT)init = NULL;else if (!init)memset(sh, 0, hdrlen+initlen+1);/* 注意：返回的s并不是直接指向sds的指针 ， 而是指向sds中字符串的指针 ， sds的指针还需要* 根据s和hdrlen计算出来 */s = (char*)sh+hdrlen;fp = ((unsigned char*)s)-1;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] = '';return s;}


推荐阅读


上一篇：C++四种强制类型转换介绍

下一篇：Java知识点梳理