_posts/2016-01-11-sds-from-redis.md

   1 ---
   2 layout: post
   3 date: 'Mon 2016-01-11 13:06:16 +0800'
   4 slug: "sds-from-redis"
   5 title: "SDS from Redis"
   6 description: ""
   7 category:
   8 tags: [ZT]
   9 ---
  10 {% include JB/setup %}
  11
  12 看上去`struct sdshdr`已经是最简存在了，`len`保存总大小、`free`用来得到数据尾地址用来追加。
  13
  14 https://gist.github.com/jasonlvhit/bdd88571331d7b6dac1e
  15
  16 SDS -> Simple Dynamic String，简单动态字符串，为了性能和实现上的需要，Redis中用SDS取代了标准C中字符串（对不起，一个以'\0'结尾的char*）类型。SDS的实现比较简单，但却是维持Redis高效率的关键组件，SDS的源码在Redis源码文件中的sds.h和sds.c中可以找到。
  17
  18 相对于传统的标准C字符串，SDS主要有下面几个看起来好一点的特性:
  19
  20 * 二进制安全，字符串中允许拥有任意类型的数据，包括'\0'
  21 * 在O(1)时间内获取字符串长度（strlen）
  22 * 高效的字符串追加操作（append）
  23
  24 第一点和第二点的实现其实很简单，为了在O(1)时间内获得长度，我们只有把这个长度存起来，有了长度我们也就能够判断字符串的开始和终止，也就是说，我们不再需要强制要求字符串是'\0'终止的了。
  25
  26 我们可以容易的理解下面这个sds的定义(来自黄建宏的Redis源码注释，sds.h):
  27
  28 ``` c
  29 struct sdshdr {
  30
  31     // buf 已占用长度
  32     int len;
  33
  34     // buf 剩余可用长度
  35     int free;
  36
  37     // 实际保存字符串数据的地方
  38     // 利用c99(C99 specification 6.7.2.1.16)中引入的 flexible array member,通过buf来引用sdshdr后面的地址，
  39     // 详情google "flexible array member"
  40     char buf[];
  41 };
  42 ```
  43
  44 关于第三点，更加高效的字符串追加操作，这里的动态字符串，类似于C++中的vector，或者Python中的list，可以在原字符串的后面追加新的字符或字符串，而不必要“彻底的重新分配内存”。SDS的动态字符串实现策略同C++的vector和Python中的List如出一辙(算法的很多经典的实现策略都是类似的）：
  45
  46 注意sds结构体中有一成员名为free，这里保存了sds一个实例霸占着的，但未被其使用的空间大小，sds拥有着比实际拥有的字符串成员占据内存大小更大的空间，所以在追加新字符串的时候，我们不必要分配空间给这个sds。
  47
  48 那么sds的内存分配策略是怎样的？.....和Cpapa中的vector和python 中的 list是一样的。
  49
  50 这里同样引用建宏兄的redis源码注释中的内容：
  51
  52 ``` c
  53 sds sdsMakeRoomFor(
  54     sds s,
  55     size_t addlen   // 需要增加的空间长度
  56 )
  57 {
  58     struct sdshdr *sh, *newsh;
  59     size_t free = sdsavail(s);
  60     size_t len, newlen;
  61
  62     // 剩余空间可以满足需求，无须扩展
  63     if (free >= addlen) return s;
  64
  65     sh = (void*) (s-(sizeof(struct sdshdr)));
  66
  67     // 目前 buf 长度
  68     len = sdslen(s);
  69     // 新 buf 长度
  70     newlen = (len+addlen);
  71     // 如果新 buf 长度小于 SDS_MAX_PREALLOC 长度
  72     //这里SDS——MAX_PREALLOC的大小为1M
  73     // 那么将 buf 的长度设为新 buf 长度的两倍
  74     if (newlen < SDS_MAX_PREALLOC)
  75         newlen *= 2;
  76     else
  77         newlen += SDS_MAX_PREALLOC;
  78
  79     // 扩展长度
  80     newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
  81
  82     if (newsh == NULL) return NULL;
  83
  84     newsh->free = newlen - len;
  85
  86     return newsh->buf;
  87 }
  88 ```
  89
  90 所以SDS，是一个经典的用空间换取时间效率的实现。
  91
  92 > 深深的分割线...tatata...
  93 --------------
  94
  95 PS.
  96
  97 Redis的代码写的很赞，简洁并且很易读，并且有很多地方看的让人脑洞大开，比如SDS模块中，下面的这个函数，恕我当时年幼无知(现在更无知)，被这个函数深深的折服：
  98
  99 ``` c
 100 static inline size_t sdslen(const sds s) {
 101     struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
 102     return sh->len;
 103 }
 104 ```
 105
 106 最后：
 107 Be Happy!
 108