sds简介#yyds干货盘点#

PHP小丑

字符串是redis中最为常见的存储数据存储类型，其底层实现是简单的动态字符串sds(simple dynamic string)，可以修改的字符串。

sds 介绍
​​sds​​​本质上是 ​​char *​​，因为有了表头sdshdr结构的存在，所以sds比传统c字符串在某些方面更加优秀，并且能够兼容传统c字符串。​
​​sds​​​采用预分配存储空间的方式来减少内存的频繁分配，惰性空间释放的策略来优化sds的缩短操作，降低内存重新分配的概率。redis 的字符串实现在​​sds.h​​​ ​​sds.c​​ 中。

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[];
};

上述代码来自sds.h

• ​​__attribute__ ((__packed__))​​
  

    redis3.2 之后，针对不同长度的字符串引入了不同的sds数据结构，并且强制内存对齐1，将内存对齐的交给统一的内存分配函数，从而达到节省内存的目的    稍微了解c/c++的人都会了解在结构体建立的是时候，会进行字节对齐操作，所以往往比实际变量占用的字节要多一些，如果我们不想要字节对齐怎么办？    在结构体声明当中​​​​__attribute__ ((__packed__))​​关键字可以让我们的结构体按照紧凑排列的方式，占用内存。
   如下2种数据结构分别sizeof 将得到不同的结果

struct  test{
    unsigned char flags;
    int value;
};
struct __attribute__ ((__packed__)) test_{
    unsigned char flags;
    int value;
};

​​sizeof(struct test) //size is 8​​​
​​sizeof(struct test_) //size is 5​​

• ​​char buf[]​​
  

    ​​char buf[]​​​ 等价与 ​​char buf[0]​​ 在标准C和C++中0长数组如char buf[0]是不允许使用的，因为这从语义逻辑上看，是完全没有意义的。但是，GUN中却允许使用，而且，很多时候，应用在了变长结构体中。对编译器来说，此时长度为0的数组并不占用空间，因为数组名本身不占空间，它只是一个偏移量， 数组名这个符号本身代表了一个不可修改的地址常量。我们可以优雅的将buf称之为柔性数组。    在结构中，buf是一个数组名；但该数组没有元素；该数组的真实地址紧随结构体sdshdr5之后，而这个地址就是结构体后面数据的地址（如果给这个结构体分配的内容大于这个结构体实际大小，后面多余的部分就是这个buf的内容）；这种声明方法可以巧妙的实现C语言里的数组扩展。    对于0长数组的这个特点，很容易构造出变长结构体，如缓冲区，数据包等等

struct Buffer
  {
    int len;
    char cData[0];
  };

假如我们要发送1024个字节，我们如何构造这个数据包呢?
​​char *buffer = (char*)malloc(sizeof(Buffer)+1024)​​
        我们首先申请1024字节的空间，其次做一个类型转换，如下代码

Buffer *p = (Buffer*)buffer
p->len = 1024
memcpy(p.cData,"1024 data............",1024)
send(socket,p,sizeof(Buffer)+1024);//发送数据

sds 数据存储结构
我们摘取其中一个sdshdr32的数据结构来分析redis中sdsh的数据存储结构

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[];
};

​​sdsnew(const char  *init)​​​ 会根据init数据的长度去分配内存，分配内存的大小为​​s_malloc(hdrlen+initlen+1)​​​ 其中 hdrlen 为sdshdr* 的结构体的大小，initlen为传入的​​init​​​ 变量的数据大小或者为​​sdsnewlen(const void *init, size_t initlen)​​​ 传入的​​initlen​​ 的大小。​


​​sdsnewlen​​​ 方法会根据initlen 的数值去通过​​sdsReqType​​​去确定type的类型，然后根据返回的type数值再通过​​sdsHdrSize(type)​​​获得​​hdrlen​​​。 具体代码实现可参见​​sds.c​​​文件。当​​sds s = sdsnew()​​​之后，其中s的位置并不是内存的起始位置, ​​sh = s_malloc(hdrlen+initlen+1)​​​, 而是偏移了sh + hdrlen 后的位置 ​​s = (char*)sh+hdrlen​​。
sds 有一个关键的宏​​SDS_HDR​​ 定义如下

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

其中SDS_HDR 能够将s 的指针位置减去 ​​sdshdr##T​​​的大小，从而将指针位置指向​​sdsnew​​​内存分配的起始位置dh,进而去通过sh去操作​​sdshdr##T​​的成员变量。其中T取值为（5，8，16，32，64）
一个 sds 的内部数据结构

-----------------------------
  | len | alloc | flags | buf |
  -----------------------------

如上，其中buf位置真正存储了字符数据， 前面十三个位置分别存储了buf相关的sds信息。

• ​​len​​记录当前字节数组的长度（不包括\0），使得获取字符串长度的时间复杂度由O(N)变为了O(1)
  
• ​​alloc​​记录了当前字节数组总共分配的内存大小（不包括\0）
  
• ​​flags​​记录了当前字节数组的属性、用来标识到底是sdshdr8还是sdshdr16等
  
• ​​buf​​保存了字符串真正的值以及末尾的一个\0
  

整个sds的内存是连续的，统一开辟的。在大多数操作中，buf内的字符串实体才是操作对象。统一开辟内存能通过buf头指针进行寻址，拿到整个struct的指针，而且通过buf的头指针减1直接就能获取flags的值, ​​flags = s[-1]​​​。更详细的sds的分配可参见​​sds.c​​​中​​sdsnewlen​​的实现部分