【Redis源码】字符串详解（七）

前言：

学过C的人应该都知道C的字符串是以字节数组存在，然后以\0结尾。计算字符串的长度使用strlen函数，这个标准库函数的复杂程度是O(n)。它需要对字节数组进行扫描遍历计算长度。作为redis单线程的应用是这种形式是比较消耗性能的。

Redis实现了字节的字符串叫sds（Simple Dynamic String），它是一个带着长度的信息的结构体，属于柔性字符串。

Redis的字符串形式如下：

一.Redis字符串内部编码介绍：

redis字符串的内部编码分为三种：int、embstr、raw。

注意事项：

（1） embstr 的44个字节是redis3.2版本之后，之前为39；

（2）说raw大于44个字节这个不能说完全对，利用APPEND命令追加后的字符串为raw类型。

1.1 内部编码int

debug object参数解释：

当设置键值test1为9223372036854775807时，因为long的曲直范围是 -9223372036854775808 ～ 9223372036854775807之间。

所以通过debug object第一次打印test1类型为int，当前的长度为20。由于第二次打印是，设置test1为9223372036854775808，超过了long的最大值。并且长度为20，则现打印类型为embstr。

1.2 内部编码embstr和raw

当设置键值test1为0123456789abcdefghijklmnopqrstuvwxyz12345678时，因为<=44个字节。所以编码类型为embstr。

当设置键值test1为0123456789abcdefghijklmnopqrstuvwxyz123456789时，test1此时为45个字节，则编码类型为raw。

1.3 源码解析

setCommand命令源码

voidsetCommand(client *c) {
   省略...
   c->argv[2] = tryObjectEncoding(c->argv[2]);  //尝试对字符串对象进行编码以节省空间
   setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}


object.c 中tryObjectEncoding函数

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44  //embstr长度限制

robj *tryObjectEncoding(robj *o){
   long value;
   sds s = o->ptr;
   size_t len;
   
   /* 确保这是一个字符串对象 */
   serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);

   /*我们只对RAW或EMBSTR编码的，换句话说，仍然是由实际的字符数组表示。*/
   if (!sdsEncodedObject(o)) return o;

   /*对共享对象进行编码是不安全的：共享对象可以共享
    *在Redis的“对象空间”中的任何地方，并且可能在
    *他们没有被处理。我们只将它们作为键空间中的值来处理。*/
    if (o->refcount > 1) return o;

   /* 检查字符串是否为long类型整数，如果len <=20且在LONG_MIN和LONG_MAX范围内，则是int编码 */
   len = sdslen(s);
   if (len <= 20 && string2l(s,len,&value)) {
      /*此对象可编码为long。尝试使用共享对象。
       *注意，当使用maxmemory时，我们避免使用共享整数
       *因为每个对象都需要有一个用于LRU的私有LRU字段
       *算法运行良好。*/
       if ((server.maxmemory == 0 ||
           !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
           value >= 0 &&
           value < OBJ_SHARED_INTEGERS)
       {
           decrRefCount(o);
           incrRefCount(shared.integers[value]);
           return shared.integers[value];
       } else {
           if (o->encoding == OBJ_ENCODING_RAW) sdsfree(o->ptr);
           o->encoding = OBJ_ENCODING_INT;  //设置为int编码
           o->ptr = (void*) value;
           return o;
       }
   }

   //判断长度小于或等于44，返回一个OBJ_ENCODING_EMBSTR编码
   if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
       robj *emb;

       if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
       emb = createEmbeddedStringObject(s,sdslen(s));
       decrRefCount(o);
       return emb;
   }

   /**我们无法对对象进行编码。。。
    *做最后一次尝试，至少优化SDS字符串。
    *字符串对象需要很少的空间，以防大于SDS字符串末尾可用空间的10%。
    *我们这样做只是为了相对较大的字符串仅当字符串长度大于44。
    */
   if (o->encoding == OBJ_ENCODING_RAW &&
       sdsavail(s) > len/10)
   {
       o->ptr = sdsRemoveFreeSpace(o->ptr);
   }
   
   return o;  //返回原始对象
}



1.4 为什么OBJ_ENCODING_EMBSTR_SIZE_LIMIT是44个字节

redisObject结构体：

typedefstructredisObject {
   unsigned type:4;       //4bit
   unsigned encoding:4;   //4bit
   unsigned lru:LRU_BITS; //24bit
   int refcount;          //4byte
   void *ptr;             //8byte
} robj


redisObject的总大小应该是16字节 = （4bit + 4bit + 24bit) + 4byte + 8byte。32bit = 4byte

sds结构体的最小单位应该是sdshdr8(sdshdr5默认会转化为sdshdr8)，接下来会说到。

struct __attribute__ ((__packed__)) sdshdr8 {
   uint8_t len;          //1byte
   uint8_t alloc;        //1byte
   unsignedchar flags;  //1byte
   char buf[];
};


内存分配器jemalloc/tcmalloc分配内存大小单位为：2、4、8、16、32、64。为了能完整容纳一个embstr对象，最小分配32个字节空间。如果稍微长一点就是64个字节空间。如果超出64个字节，Redis认为它是一个大字符串。形式就变为RAW，不在是一个连续内存。

64 - 16 - 3 - 1 = 44，64减去redisObject结构体的16个字节再减去sds结构体的3个字节和一个\0字符的1个字节。

二.SDS介绍：

2.1 SDS数据结构

sds的5种数据结构，sds.h中

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4



看到以上宏可能不是特别容易理解，接下来我们看一段源码,sds.c中：

staticinlinecharsdsReqType(size_t string_size) {
   if (string_size < 1<<5)  //2的5次方
       return SDS_TYPE_5;
   if (string_size < 1<<8)  //2的8次方
       return SDS_TYPE_8;
   if (string_size < 1<<16) //2的16次方
       return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
   if (string_size < 1ll<<32) //2的32次方
       return SDS_TYPE_32;
#endif
   return SDS_TYPE_64;      
}

/*
根据长度创建一个sds字符串
*/
sds sdsnewlen(constvoid *init, size_t initlen){
   void *sh;
   sds s;
   char type = sdsReqType(initlen); //获取字符串类型
   //空字符串默认type为SDS_TYPE_8
   if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
   int hdrlen = sdsHdrSize(type);
   unsignedchar *fp; /* flags pointer. */

   sh = s_malloc(hdrlen+initlen+1);
   if (!init)
       memset(sh, 0, hdrlen+initlen+1);
   if (sh == NULL) returnNULL;
   s = (char*)sh+hdrlen;
   fp = ((unsignedchar*)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] = '\0';  //字符串结尾添加一个\0
   return s;
}


sds的数据结构取值范围：

2.2 SDS字符串扩容

可以先看一下追加字符串函数，在sds.c中:

sds sdscatlen(sds s, constvoid *t, size_t len){
   size_t curlen = sdslen(s); //获取当前字符串长度

   s = sdsMakeRoomFor(s,len); //按照需要空间调整字符串空间
   if (s == NULL) returnNULL;
   memcpy(s+curlen, t, len);  //追加到目标字符串数组中
   sdssetlen(s, curlen+len);  //设置追加后长度
   s[curlen+len] = '\0';      //追加后
   return s;
}



sds字符串调整空间函数，在sds.c中

sds sdsMakeRoomFor(sds s, size_t addlen){
   void *sh, *newsh;
   size_t avail = sdsavail(s);  //获取当前剩下空间
   size_t len, newlen;
   char type, oldtype = s[-1] & SDS_TYPE_MASK;
   int hdrlen;

   /* 如果空间足够时返回原来的 */
   if (avail >= addlen) return s;

   len = sdslen(s);                   //获取长度
   sh = (char*)s-sdsHdrSize(oldtype); //获取数据
       newlen = (len+addlen);         //计算新的长度
   if (newlen < SDS_MAX_PREALLOC)      // < 1M 2倍扩容,1M = 1024 * 1024
       newlen *= 2;
   else
       newlen += SDS_MAX_PREALLOC;    // > 1M 扩容1M

   type = sdsReqType(newlen);  //获得新长度的sds类型

   if (type == SDS_TYPE_5) type = SDS_TYPE_8;  //type5 默认转成 type8

   hdrlen = sdsHdrSize(type); //获得头长度
   if (oldtype==type) {  //判断结构不变情况说明长度够用
       newsh = s_realloc(sh, hdrlen+newlen+1);
       if (newsh == NULL) returnNULL;
       s = (char*)newsh+hdrlen;
   } else {
       /*重新分配内存*/
       newsh = s_malloc(hdrlen+newlen+1);
       if (newsh == NULL) returnNULL;
       memcpy((char*)newsh+hdrlen, s, len+1);
       s_free(sh);
       s = (char*)newsh+hdrlen;
       s[-1] = type;
       sdssetlen(s, len);
   }
   sdssetalloc(s, newlen);
   return s;
}



扩容时，字符串长度小于1M之前，扩容空间都是成倍增加。当长度大于1M之后，为了避免空间过大浪费。

每次扩容只会多分配1M。

三.总结：

(1) redis的字符串为了节省开销采用sds结构作为字符串结构，sds结构分为：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64 五种，字符串会根据不同的大小通过sdsReqType函数获取对应的类型。

(2) redis字符串的编码分为三种，int，embstr，raw。int的范围为min long到max long的整数之间，embstr为非整数44字节内，raw为大于44字节字符串。通过append命令追加字符串不够字节影响，编码类型直接时raw。

(3)redis字符串扩容，小于1M成倍增加，大于或等于1M每次只增加1M。这种做法是避免资源浪费。

(4)OBJ_ENCODING_EMBSTR_SIZE_LIMIT等于44字节，是因为64字节减去redisObject结构体的16个字节再减去sds结构体的3个字节和一个\0字符的1个字节。

(5)sdshdr5默认为变为sdshdr8。