图解 Redis 六种数据结构

开发运维 2023-10-13 大白菜程序猿 手机阅读

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 简单动态字符串，由两部分组成，如图所示：

1.png

代码结构如下：

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 结构如下：

2.png

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

3.png

它是怎么扩容的呢？

如果这个字符串小于 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 决定的

如下图所示：

4.png

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

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

所以寻址地址表达式为：

startPtr + (sizeof(int16_t) * index)

动态升级

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

5.png

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

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

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

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

  • 以前的元素也要按照新的编码进行升级，并扩容数组
  • 倒序依次将数组中的元素拷贝到扩容后的正确的位置上

    • 图例说明：

  • 内存扩容 6.png
  • 元素升级
    • 正序放置，那么重新编码后的元素 5 会覆盖掉元素 10 7.png
    • 倒序放置，先将元素 20 放到正确的位置上，然后将 10、5 放到正确的位置上 8.png 9.png
  • 将待添加的元素放到末尾 10.png
  • 将 encoding 升级为 INTSET_ENC_INT32，并将 length 改为 4 11.png

    • 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 的地址

    12.png

    插入新元素是从头部插入的，所以 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 命令时进行扩容