图解 Redis 六种数据结构

RedisObject

Redis 中的所有数据都是通过 RedisObject 来表示的，它的结构如下：

struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
};

• type 表示数据类型，如 string、hash、list、set、zset、bitmap 等，占用 4bit
  • 这些类型在 Redis 内部有预定义
    • OBJ_STRING 0
    • OBJ_LIST 1
    • OBJ_SET 2
    • OBJ_ZSET 3
    • OBJ_HASH 4
• encoding 表示编码方式，如 int、embstr、raw、ht、ziplist、intset、skiplist、quicklist、stream 等，占用 4bit
  • OBJ_STRING：raw、embstr、int
  • OBJ_LIST：quicklist
  • OBJ_SET：intset、ht
  • OBJ_ZSET：ziplist、skiplist、ht
  • OBJ_HASH：ziplist、ht
• lru 表示该对象最后一次被访问的时间，占用 24bit
• refcount 表示引用计数，被引用一次就加 1，不被引用了就减 1，直到 ，占用 4bit
• ptr 表示指向实际数据的指针，占用 8bit

所以光这一个头部信息占用 16 个字节

简单动态字符串 SDS

redis 中的 key 是个字符串

但是 redis 没有使用 c 中的字符串，而是自己实现了一套字符串，叫做 SDS

SDS 全称 Simple Dynamic String 简单动态字符串，由两部分组成，如图所示：

代码结构如下：

struct __attribute__ ((__packed__)) sdshdr8 {
  uint8_t len;
  uint8_t alloc;
  unsigned char flags;
  char buf[];
};

其中 len、alloc、flags 是头部信息

• len 表示内容使用占用的字节，本身占用 1 个字节
• alloc 表示分配的字节，本身占用 1 个字节
• flags 是个头类型，用来控制头大小，占用 1 个字节：
  • SDS_TYPE_5 0 不常用
  • SDS_TYPE_8 1
  • SDS_TYPE_16 2
  • SDS_TYPE_32 3
  • SDS_TYPE_64 4
• buf 是个柔性数组，保存的是字符串的地址，默认不占用内存

SDS 与 c 字符串的区别

为什么要自己实现一套字符串呢？

因为 c 中的字符串是以

char* str = "hello";
// {'h', 'e', 'l', 'l', 'o', '

这样的话，如果字符串中含有

而 redis 中的 key 是可以包含

在读取字符串的时候，redis 先会读取 len 的值，然后根据 len 的值来读取字符串

比如在存储 name 时对应的 SDS 结构如下：

那这时我修改了 name 变成了 name:uccs，就需要对齐进行扩容了，对应的 SDS 结构如下：

它是怎么扩容的呢？

如果这个字符串小于 1m，那么就会扩容为原来的两倍，如果大于 1m，那么就会扩容为字符串的长度加上 1m

INTSET 整数集合

INTSET 是 redis 用来存储整数的集合，它的结构如下：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

• encoding 表示编码方式
  • INTSET_ENC_INT16，占用 2 个字节
  • INTSET_ENC_INT32，占用 4 个字节
  • INTSET_ENC_INT64，占用 8 个字节
• length 表示集合中元素的个数，占用 4 个字节
• contents 表示集合中的元素，占用 1 个字节
  • contents 保存的是起始元素的地址，对这个数组的增删改查都是自己实现的，不依赖于 c 提供的方法
  • contents 中保存的元素大小是由 encoding 决定的

如下图所示：

上图中 encoding 指定的是 INTSET_ENC_INT16，所以 contents 中的数据类型是 int16_t，每个元素占用 2 个字节

contents 保存的是起始元素的地址，所以第二个元素的地址通过起始元素的地址加上 2 个字节就可以得到，依次类推

所以寻址地址表达式为：

startPtr + (sizeof(int16_t) * index)

动态升级

现在内存中的 INTSET 结构如下：

假如我现在要往 INTSET 中添加一个 int32_t 类型的元素

由于之前的 encoding 是 INTSET_ENC_INT16，所以 contents 中的数据类型是 int16_t，每个元素占用 2 个字节

而现在 int32_t 类型的元素占用 4 个字节，所以需要对 INTSET 进行升级，将原来的 INTSET_ENC_INT16 升级为 INTSET_ENC_INT32

编码升级后，需要做两件事情：

图例说明：

内存扩容

将待添加的元素放到末尾

将 encoding 升级为 INTSET_ENC_INT32，并将 length 改为 4

DICT

dict 由三部分组成：哈希表(DictHashTable)、哈希节点(DictEntry)、字典(Dict)，结构如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

• table 表示哈希表，是一个数组，数组中的每个元素都是一个指向 dictEntry 的指针
• size 表示哈希表的大小，值为 2^n
• sizemask 表示哈希表的掩码，值为 size - 1
• used 表示哈希表中已经使用的 entry 的个数
  • 不同的 key 计算出的 hash 值可能相同，会放在同一个 entry 中，通过链表的方式进行存储，所以 used 的值可能大于 size

typedef struct dictEntry {
  void *key;
  union {
      void *val;
      uint64_t u64;
      int64_t s64;
      double d;
  } v;
  struct dictEntry *next;
} dictEntry;

• key 表示 key 的地址
• v 表示 value 的值，是一个联合体，可以存储 void*、uint64_t、int64_t、double 类型的值
• next 表示下一个 entry 的地址

插入新元素是从头部插入的，所以 table 中保存的是新插入元素的地址，它的 next 指向之前插入元素的地址

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 命令时进行扩容