3 大物理编码方式

RedisObject 内部对应 3 大物理编码

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

• type：对象的类型，包括：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET 等等
• encoding：具体的数据结构
• lru:LRU_BITS：24 位，对象最后一次被命令程序访问的时间，与内存回收有关
• refcount：引用基数。当 refcount 为 0 的时候，表示该对象已经不被任何对象引用，则可以进行垃圾回收
• *ptr：指向真正的底层数据结构的指针

int

• 保存 long 型（长整型）的 64 位（8 个字节）有符号整数

• 9223372036854775807

  • long 数据类型是 64 位、有符号的以二进制补码表示的整数；
  • 最小值是 -9,223,372,036,854,775,808(-2^63)；
  • 最大值是 9,223,372,036,854,775,807(2^63 - 1)；
  • 这种类型主要使用在需要比较大整数的系统上；
  • 默认值是 0L。

• 上面数字最多 19 位

• 补充

  只有整数才会使用 int，如果是浮点数，Redis 内部其实先将浮点数转化为字符串值，然后再保存。

embstr

• 代表 embstr 格式的 SDS（Simple Dynamic String简单动态字符串），保存长度大于 44 字节的字符串
• EMBSTR 顾名思义即：embedded string，表示嵌入式的 String

raw

保存长度大于 44 字节的字符串

3 大物理编码案例

案例测试

# 普通数字
127.0.0.1:6379> set k1 123
OK
127.0.0.1:6379> object encoding k1
"int"
 
# 长度小于 20 的数
127.0.0.1:6379> set k1 123456789123456789
OK
127.0.0.1:6379> object encoding k1
"int"
 
# 长度大于等于 20
127.0.0.1:6379> set k1 12345678912345678911
OK
127.0.0.1:6379> object encoding k1
"embstr"
 
# 普通字符串
127.0.0.1:6379> set k1 abc
OK
127.0.0.1:6379> object encoding k1
"embstr"
 
# 长度小于等于 44 的字
127.0.0.1:6379> set k1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK
127.0.0.1:6379> object encoding k1
"embstr"
 
# 长度大于 44 的字
127.0.0.1:6379> set k1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK
127.0.0.1:6379> object encoding k1
"raw"
127.0.0.1:6379> 

C 语言中字符串的展现

假如现在展现一个字符串：Redis

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
};

Redis 没有直接复用 C 语言的字符串，而是新建了属于自己的结构 —— SDS 在 Redis 数据库里，包含字符串值的键值对都是由 SDS 实现的（Redis 中所有的键都是由字符串对象实现的即底层是由 SDS 实现，Redis 中所有的值对象中包含的字符串对象底层也是由 SDS 实现）。

SDS 简单动态字符串 ⭐️

• sds.h 源码分析

  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[];
  };
  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[];
  };
  struct __attribute__ ((__packed__)) sdshdr64 {
      uint64_t len; /* used */
      uint64_t alloc; /* excluding the header and null terminator */
      unsigned char flags; /* 3 lsb of type, 5 unused bits */
      char buf[];
  };
  • len 字符串长度
  • alloc 分配的空间长度，当前字符串数组总共分配的内存大小
  • flags sds 类型，当前字符数组的属性、用来表示到底是 sdshdr8 还是 sdshdr16 等
  • buf[] 字节数组，字符串真正的值

• 说明

  sds.h

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

  Redis 中字符串的实现，SDS 有多种结构（sds.h）：

  • sdshdr5（$2^{5}{=}32byte$）
  • sdshdr8（$2^{8}{=}256byte$）
  • sdshdr16（$2^{16}{=}65536byte{=}64KB$）
  • sdshdr32（$2^{32}byte{=}4GB$）
  • sdshdr64（$2^{64}byte{=}17179869184G$）用于存储不同的长度的字符串。

  len 表示 SDS 的长度，使我们在获取字符串长度的时候可以在 O(1) 情况下拿到，而不是像 C 那样需要遍历一遍字符串。

  alloc 可以用来计算字符串已经分配但未使用的空间，有了这个值就可以引入预分配空间的算法了，而不用去考虑内存分配的问题。

  buf 表示字符串数组，真正存数据的。

• 官网

  https://github.com/antirez/sds (opens in a new tab)

Redis 为什么重新设计一个 SDS 数据结构？ ⭐️

C 语言没有 Java 里面的 String 类型，只能是靠自己的 char[] 来实现，字符串在 C 语言中的存储方式，想要获取 「Redis」的长度，需要从头开始遍历，直到遇到 \0 为止。所以，Redis 没有直接使用 C 语言传统的字符串标识，而是自己构建了一种名为简单动态字符串 SDS（simple dynamic string）的抽象类型，并将 SDS 作为 Redis 的默认字符串。

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[];
};
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[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

源码分析

用户 API

set k1 v1 底层发生了什么？调用关系

/* SET key value [NX] [XX] [KEEPTTL] [GET] [EX <seconds>] [PX <milliseconds>]
 *     [EXAT <seconds-timestamp>][PXAT <milliseconds-timestamp>] */
void setCommand(client *c) {
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    int flags = OBJ_NO_FLAGS;
 
    if (parseExtendedStringArgumentsOrReply(c,&flags,&unit,&expire,COMMAND_SET) != C_OK) {
        return;
    }
 
    c->argv[2] = tryObjectEncoding(c->argv[2]);
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

3 大物理编码方式

• INT 编码格式

  命令实例：set k1 123

  127.0.0.1:6379> set k1 123
  OK
  127.0.0.1:6379> object encoding k1
  "int"

  当字符串键值的内容可以用一个 64 位有符号整形来表示时，Redis 会将键值转化为 long 型来进行存储，此时即对应 OBJ_ENCODING_INT 编码类型。内部的内存结构表示如下：

  

  Redis 启动时会预先建立 10000 个分别存储 09999 的 redisObject 变量作为共享对象，这就意味着如果 set字符串的键值在 010000 之间的话，则可以直接指向共享对象而不需要再建立新对象，此时键值不占空间！

  

  server.h

  #define OBJ_SHARED_INTEGERS 10000
  Redis6 object.c

  /* Check if we can represent this string as a long integer.
       * Note that we are sure that a string larger than 20 chars is not
       * representable as a 32 nor 64 bit integer. */
  len = sdslen(s);
  // 字符串长度小于等于 20 且字符串转 long 类型成功
  if (len <= 20 && string2l(s,len,&value)) {
      /* This object is encodable as a long. Try to use a shared object.
       * Note that we avoid using shared integers when maxmemory is used
       * because every object needs to have a private LRU field for the LRU
       * algorithm to work well. */
      if ((server.maxmemory == 0 ||
          !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
          value >= 0 &&
          value < OBJ_SHARED_INTEGERS)
      {
          // 配置 maxmemory 且值在 10000 以内，直接使用共享对象值
          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;
              o->ptr = (void*) value;
              return o;
          } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
              decrRefCount(o);
              return createStringObjectFromLongLongForValue(value);
          }
      }
  }
  Redis7 object.c

  /* Try to encode a string object in order to save space */
  robj *tryObjectEncoding(robj *o) {
      long value;
      sds s = o->ptr;
      size_t len;
   
      /* Make sure this is a string object, the only type we encode
       * in this function. Other types use encoded memory efficient
       * representations but are handled by the commands implementing
       * the type. */
      serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);
   
      /* We try some specialized encoding only for objects that are
       * RAW or EMBSTR encoded, in other words objects that are still
       * in represented by an actually array of chars. */
      if (!sdsEncodedObject(o)) return o;
   
      /* It's not safe to encode shared objects: shared objects can be shared
       * everywhere in the "object space" of Redis and may end in places where
       * they are not handled. We handle them only as values in the keyspace. */
       if (o->refcount > 1) return o;
   
      /* Check if we can represent this string as a long integer.
       * Note that we are sure that a string larger than 20 chars is not
       * representable as a 32 nor 64 bit integer. */
      len = sdslen(s);
      if (len <= 20 && string2l(s,len,&value)) {
          /* This object is encodable as a long. Try to use a shared object.
           * Note that we avoid using shared integers when maxmemory is used
           * because every object needs to have a private LRU field for the LRU
           * algorithm to work well. */
          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;
                  o->ptr = (void*) value;
                  return o;
              } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
                  decrRefCount(o);
                  return createStringObjectFromLongLongForValue(value);
              }
          }
      }
   

  if (len <= 20 && string2l(s,len,&value)) {
      ...
  }

  decrRefCount(o);
  incrRefCount(shared.integers[value]);
  return shared.integers[value];

  o->encoding = OBJ_ENCODING_INT;
  o->ptr = (void*) value;

• EMBSTR 编码格式

  命令实例：set k1 abc

  127.0.0.1:6379> set k1 abc
  OK
  127.0.0.1:6379> object encoding k1
  "embstr"
  object.c

  #define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
  ......
  /* If the string is small and is still RAW encoded,
   * try the EMBSTR encoding which is more efficient.
   * In this representation the object and the SDS string are allocated
   * in the same chunk of memory to save space and cache misses. */
  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;
  }

  对于长度小于 44 的字符串，Redis 对键值采用 OBJ_ENCODING_EMBSTR 方式，EMBSTR 顾名思义即：embedded string，表示嵌入式的 String。从内存结构上来讲即字符串 sds 结构体与其对应的 redisObject 对象分配在同一块连续的内存空间，字符串 sds 嵌入在 redisObject 对象之中一样。

  /* Create a string object with EMBSTR encoding if it is smaller than
   * OBJ_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
   * used.
   *
   * The current limit of 44 is chosen so that the biggest string object
   * we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc. */
  #define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
  robj *createStringObject(const char *ptr, size_t len) {
      if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
          return createEmbeddedStringObject(ptr,len);
      else
          return createRawStringObject(ptr,len);
  }

  /* Create a string object with encoding OBJ_ENCODING_EMBSTR, that is
   * an object where the sds string is actually an unmodifiable string
   * allocated in the same chunk as the object itself. */
  robj *createEmbeddedStringObject(const char *ptr, size_t len) {
      robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
      struct sdshdr8 *sh = (void*)(o+1);
   
      o->type = OBJ_STRING;
      o->encoding = OBJ_ENCODING_EMBSTR;
      o->ptr = sh+1;
      o->refcount = 1;
      if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
          o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
      } else {
          o->lru = LRU_CLOCK();
      }
   
      sh->len = len;
      sh->alloc = len;
      sh->flags = SDS_TYPE_8;
      if (ptr == SDS_NOINIT)
          sh->buf[len] = '\0';
      else if (ptr) {
          memcpy(sh->buf,ptr,len);
          sh->buf[len] = '\0';
      } else {
          memset(sh->buf,0,len+1);
      }
      return o;
  }

  

• RAW 编码格式

  命令实例：set k1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

  127.0.0.1:6379> set k1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
  OK
  127.0.0.1:6379> object encoding k1
  "raw"
  object.c

  /* Create a string object with EMBSTR encoding if it is smaller than
     * OBJ_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
     * used.
     *
     * The current limit of 44 is chosen so that the biggest string object
     * we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc. */
  #define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
  robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
  }

  当字符串的键值为长度大于 44 的超长字符串时，Redis 则会将键值的内部编码方式改为 OBJ_ENCODING_RAW 格式，这与 OBJ_ENCODING_EMBSTR 编码方式的不同之处在于，此时动态字符串 sds 的内存与其依赖的 redisObject 的内存不再连续了。

  

• 明明没有超过阈值，为什么变成 raw

  127.0.0.1:6379> set k3 a
  OK
  127.0.0.1:6379> object encoding k3
  "embstr"
  127.0.0.1:6379> APPEND k3 b
  (integer) 2
  127.0.0.1:6379> get k3
  "ab"
  127.0.0.1:6379> object encoding k3
  "raw"
  127.0.0.1:6379> 

  答：对于 embstr，由于其实现是只读的，因此在对 embstr 对象进行修改时，都会先转化位 raw 再进行修改。因此，只要是修改 embstr 对象，修改后的对象一定是 raw 的，无论是否达到了 44 个字节（判断不出来，就取最大 raw）。

转变逻辑图

案例结论

• 只有整数才会使用 int，如果是浮点数， Redis 内部其实先将浮点数转化为字符串值，然后再保存。

• embstr 与 raw 类型底层的数据结构其实都是 SDS（简单动态字符串，Redis 内部定义 sdshdr 一种结构）。

  两者的区别见下图：

  编码格式	详解
  int	Long 类型整数时，RedisObject 中的 ptr 指针直接赋值为整数数据，不再额外的指针再指向整数了，节省了指针的空间开销。
  embstr	当保存的是字符串数据且字符串小于等于 44 字节时，embstr 类型将会调用内存分配函数，只分配一块连续的内存空间，空间中依次包含 redisObject 与 sdshdr 两个数据结构，让元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片
  raw	当字符串大于 44 字节时，SDS的数据量变多变大了，SDS 和 RedisObject 布局分家各自过，会给 SDS 分配多的空间并用指针指向 SDS 结构，raw 类型将会调用两次内存分配函数，分配两块内存空间，一块用于包含 redisObject 结构，而另一块用于包含 sdshdr 结构

  

总结

Redis 内部会根据用户给的不同键值而使用不同的编码格式，自适应地选择较优化的内部编码格式，而这一切对用户完全透明！