图解 Redis 六种数据结构

2023年 10月 13日 53.0k 0

RedisObject

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

struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
};
  • type 表示数据类型,如 stringhashlistsetzsetbitmap 等,占用 4bit
    • 这些类型在 Redis 内部有预定义
      • OBJ_STRING 0
      • OBJ_LIST 1
      • OBJ_SET 2
      • OBJ_ZSET 3
      • OBJ_HASH 4
  • encoding 表示编码方式,如 intembstrrawhtziplistintsetskiplistquickliststream 等,占用 4bit
    • OBJ_STRINGrawembstrint
    • OBJ_LISTquicklist
    • OBJ_SETintsetht
    • OBJ_ZSETziplistskiplistht
    • OBJ_HASHziplistht
  • lru 表示该对象最后一次被访问的时间,占用 24bit
  • refcount 表示引用计数,被引用一次就加 1,不被引用了就减 1,直到 0,占用 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[];
};

其中 lenallocflags 是头部信息

  • 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 就要自己实现了一套字符串

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

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

2.png

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

3.png

它是怎么扩容的呢?

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

INTSET 整数集合

INTSETredis 用来存储整数的集合,它的结构如下:

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 类型的元素

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

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

编码升级后,需要做两件事情:

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

  • 内存扩容
    6.png
  • 元素升级
    • 正序放置,那么重新编码后的元素 5 会覆盖掉元素 10
      7.png
    • 倒序放置,先将元素 20 放到正确的位置上,然后将 105 放到正确的位置上
      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_tint64_tdouble 类型的值
    • 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 命令时进行扩容
    
  • loadFactor > 5,不管有没有执行 BGSAVE 或者 BGREWRITEAOF 命令都会进行扩容
  • static int _dictExpandIfNeeded(dict *d)
    {
        // 如果正在 rehash ,则返回 ok
        if (dictIsRehashing(d)) return DICT_OK;
    
        // 如何 hash 表为空,则初始化 hash 表,默认大小为 4
        if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    
        // 当负载因子(used/size)大于1时,并且没有进行 bgrewrite 等操作时,
        // 或者负载因子大于5时,进行扩容
        // dict_can_resize 维护的是当前是否在 bgrewrite 等操作
        if (d->ht[0].used >= d->ht[0].size &&
            (dict_can_resize ||
             d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
            dictTypeExpandAllowed(d))
        {
            // 扩容大小为 used+1,底层会对扩容大小做判断,实际上找的是第一个大于等于 used+1 的 2^n
            return dictExpand(d, d->ht[0].used + 1);
        }
        return DICT_OK;
    }
    

    在删除元素时,DICT 会检查负载因子,如果负载因子小于 0.1,那么会进行缩容

    if (dictDelete((dict*)o->ptr, field) == C_OK) {
        deleted = 1;
    
        // 删除成功后,检查是否需要重置 dict 的大小,如果需要则调用 dictResize 重置
        if (htNeedsResize(o->ptr)) dictResize(o->ptr);
    }
    
    int htNeedsResize(dict *dict) {
        long long size, used;
        // hash  表大小
        size = dictSlots(dict);
        // entry 数量
        used = dictSize(dict);
        // size > 4(hash 初始大小)并且负责因子小于 0.1
        return (size > DICT_HT_INITIAL_SIZE &&
                (used*100/size < HASHTABLE_MIN_FILL));
    }
    
    int dictResize(dict *d) {
        unsigned long minimal;
        // 如果正在做 bgsave 或 bgrewriteof 或 rehash,则返回错误
        if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
        // 获取 used,就是 entry 个数
        minimal = d->ht[0].used;
        // 如果 used 小于 4,则重置为 4
        if (minimal < DICT_HT_INITIAL_SIZE)
            minimal = DICT_HT_INITIAL_SIZE;
        // 重置大小为 minimal,其实是一个大于等于 minimal 的 2^n
        return dictExpand(d, minimal);
    }
    

    rehash

    不管是扩容还是收缩,必定会创建新的 HashTable,创建新的 HashTable 会导致 sizesizemask 发生变化

    sizesizemask 发生变化,会导致每一个 key 的索引会重新计算

    计算出新的索引后,将 entry 插入到新的 HashTable 中,这个过程称为 rehash

    所以过程就是:

  • 计算出新的 HashTablerealSize,值取决于当前要扩容还是缩容
    • 扩容:realSize = (used + 1) * 2^n
    • 缩容:realSize = (used) * 2^n 不得小于 4
  • 按照新的 realSize 申请内存空间,创建 dictht,并赋值给 dict.ht[1]
  • 设置 dict.rehashidx = 0,表示 rehash 开始
  • 每次执行增/删/改/查时,都检查一下 dict.rehashidex 是否大于 -1,如果是将 dict.ht[0] 中的 entry 依次插入到 dict.ht[1] 中,并将 rehashidx++,直到 dict.ht[0] 中所有数据都 rehashdict.ht[1]
  • dict.ht[1] 赋值给 dict.ht[0],给 dict.ht[1] 初始化为空哈希表,释放原来的 dict.ht[0] 的内存
  • rehashidx 置为 -1,表示 rehash 结束
  • rehash 过程中,新增操作,直接写入 ht[1],查/改/删则会在 dict.ht[0]dict.ht[1] 依次查找并执行,可确保 ht[0] 的数据只减不增,随着 rehash 最终为空
  • 过程如下:

  • 插入新的 entry 空间不够,准备扩容
    14.png

  • 计算新的 realSize,旧的 size4,新的 size4+1=5,第一个 2^n8
    15.png

  • 元素迁移

    • rehashidx0,说明 rehash 开始了
    • dict.ht[0] 中的 entry 依次插入到 dict.ht[1]
      16.png
  • 每次执行增/删/改/查时,将 dict.ht[1] 赋值给 dict.ht[0],并将 dict.ht[1] 置为 NULL,并将 rehashidx 置为 -1,表示 rehash 结束
    17.png
    18.png

  • 源码:

    int _dictExpand(dict *d, unsigned long size, int* malloc_failed){
        if (malloc_failed) *malloc_failed = 0;
        // 如果当前 entry 数量超过了要申请的 size 大小,或者正在 rehash,则返回错误
        if (dictIsRehashing(d) || d->ht[0].used > size)
            return DICT_ERR;
        // 声明新的 hash 表
        dictht n;
        // 实际大小,第一个大于等于 size 的 2^n,比如 size=5,那么 realsize=8
        unsigned long realsize = _dictNextPower(size);
    
        // 超出 LONG_MAX,说明内存溢出
        if (realsize < size || realsize * sizeof(dictEntry*) ht[0].size) return DICT_ERR;
    
        // 重置新的 hash 表 size 和 sizemask
        n.size = realsize;
        n.sizemask = realsize-1;
        if (malloc_failed) {
            // 分配内存空间,hash 表大小乘以 entry 的字节大小
            n.table = ztrycalloc(realsize*sizeof(dictEntry*));
            *malloc_failed = n.table == NULL;
            if (*malloc_failed)
                return DICT_ERR;
        } else
            n.table = zcalloc(realsize*sizeof(dictEntry*));
        // 重置 used
        n.used = 0;
    
        // 如果是第一次,则直接把 n 赋值给 ht[0] 即可
        // d->ht[0].table == NULL 说明是在初始化
        if (d->ht[0].table == NULL) {
            d->ht[0] = n;
            return DICT_OK;
        }
    
        // 否则需要 rehash,这里只需要把 rehashidx 设置为 0 即可
        // 每次增/删/改/查都会触发 rehash
        d->ht[1] = n;
        d->rehashidx = 0;
        return DICT_OK;
    }
    
    unsigned long _dictNextPower(unsigned long size){
        // DICT_HT_INITIAL_SIZE = 4
        unsigned long i = DICT_HT_INITIAL_SIZE;
        // 是否超过存储上限
        if (size >= LONG_MAX) return LONG_MAX + 1LU;
        // 循环
        while(1) {
            // 如果 i 大于 size,那么就返回 i,这里 i 永远是 2^n
            if (i >= size)
                return i;
            i *= 2;
        }
    }
    

    ZipList

    ZipList 是一个特殊的“双端列表”,在内存中是连续的,可以在任意一端进行压入/弹出操作

    19.png

    • zlbytes 表示整个 ZipList 占用的字节数,占用 4 个字节
    • zltail 表示尾节点的偏移量,占用 4 个字节
    • zllen 表示节点的个数,占用 2 个字节,最多 65535 个节点,如果超过 65535 个节点,那么就需要使用 LinkedList
    • entry 表示节点,节点的长度由节点保存
    • zlend 表示 ZipList 的结尾,占用 1 个字节,默认值为 0xff

    entry

    20.png

    • previous_entry_length 表示前一个节点的长度,占用 15 个字节
      • 如果前一个节点的长度小于 254,那么就占用 1 个字节
      • 如果前一个节点的长度大于等于 254,那么就占用 5 个字节,第一个字节为 0xfe,后面 4 个字节表示前一个节点的长度
    • encoding 表示编码属性,记录 content 的编码类型及长度 占用 1/2/5 个字节
      • 采用小端存储
    • content 表示节点的内容

    encoding

    encoding 编码有两种:

    • 字符串:
      • 00/01/10 开头,分别占用 1/2/5 个字节
      • 举例 ab / bc
        21.png
        22.png

        • aascii6565 的二进制是 0110 0001,对应的十六进制是 0x61b 就是 0x62
        • 所以对于 ab
          • previous_entry_length0
          • encoding0x020x02 的二进制是 0000 0010,表示 content 占用 2 个字节,因为 a 一个字节,b 一个字节
          • content 表示 ab 对应的十六进制码
        • bc
          • previous_entry_length4,因为保存 abentry 占用 4 个字节
          • encoding0x020x02 的二进制是 0000 0010,表示 content 占用 2 个字节
          • content 表示 bc 对应的十六进制码
        • 一个完整的 ZipList 如下所示:
          23.png
    • 整数:
      • 11 开头,且 encoding 固定占用 1 个字节
        • 11000000 表示 int16_t,占用 2 个字节
        • 11010000 表示 int32_t,占用 4 个字节
        • 11100000 表示 int64_t,占用 8 个字节
        • 11110000 表示 24 位有符号整数,占用 3 个字节
        • 11111110 表示 8 位有符号整数,占用 1 个字节
        • 1111xxxx 直接在 xxxx 的位置保存数值,返回是 0001 ~ 1101,对应的十进制是 1 ~ 13,实际表示的是 0 ~ 12
      • 举例 25
        • 20 ~ 12 之间,要加 1 变成 3,其二进制是 0011,对应的十六进制是 0x03,所以 2encoding0xf3
        • previous_entry_length0,因为 2 是第一个节点
        • 5 也在 0 ~ 12 之间,要加 1 变成 6,其二进制是 0110,对应的十六进制是 0x06,所以 5encoding0xf6
        • previous_entry_length2,因为保存 2entry 占用 2 个字节
      • 一个完整的 ZipList 如下所示:
        24.png

    连锁更新问题

    ZipList 的每个 entry 都包含 previous_entry_length 来记录上一个节点的大小,长度是 1bytes5bytes

    • 如果前一节点的长度小于 254bytes,采用 1 个字节保存这个长度值
    • 如果前一节点的长度大于等于 254bytes,则采用 5 个字节来保存这个长度值,第一个字节为 0xfe,后四个字节才是真实长度数据

    假设我们有 n 个连续的,长度为 250 ~ 253bytes 之间的 entry,因此 entryprevious_entry_length 属性用 1bytes 表示

    25.png

    ZipList 在这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新(Cascade Update)。新增、删除都可能导致连锁更新的发生

    QuickList

    ZipList 存在一个问题:虽然节省内存,但申请内存必须是连续空间,如果内存占用较多,申请内存效率会很低

    为了缓解这个问题,我们必须限制 ZipList 的长度和 entry 大小,如果要存储大量数据,可以创建多个 ZipList 来分片存储数据

    为了建立多个 ZipList 之间的联系,Redis 引入了 QuickList,它是一个双端链表,每个节点都是 ZipList

    26.png

    为了避免 QuickList 中每个 ZipListentry 过多,Redis 提供了一个配置项:list-max-ziplist-size 来限制

    list-max-ziplist-size

    • 如果值为正,则代表 ZipListentry 的个数
    • 如果值为负,则代表 ZipList 的最大内存大小,默认值是 -2
      • -1ZipList 内存占用不能超过 4kb
      • -2ZipList 内存占用不能超过 8kb
      • -3ZipList 内存占用不能超过 16kb
      • -4ZipList 内存占用不能超过 32kb
      • -5ZipList 内存占用不能超过 64kb

    QuickList 还对节点 ZipList 做压缩,通过 list-compress-depth 来控制。因为一般首尾访问较多,所以首尾不压缩,所以这个参数是控制首尾不压缩节点个数

    list-compress-depth:默认值是 0

    • 0:不压缩
    • 1:首尾各 1 个节点不压缩,中间压缩
    • 2:首尾各 2 个节点不压缩,中间压缩
    • 3:首尾各 3 个节点不压缩,中间压缩
    • 以此类推

    QuickList 结构

    typedef struct quicklist {
        // 头节点
        quicklistNode *head;
        // 尾节点
        quicklistNode *tail;
        // 所有 ziplist 的 entry 个数
        unsigned long count;
        // ziplist 的数量
        unsigned long len;
        // ziplist 中 entry 上限,默认是 -2
        int fill : QL_FILL_BITS;
        // 首尾不压缩的节点个数,默认是 0
        unsigned int compress : QL_COMP_BITS;
        // 内存重分配时书签数量及数组,一般用不到
        unsigned int bookmark_count: QL_BM_BITS;
        quicklistBookmark bookmarks[];
    } quicklist;
    

    quicklistNode 结构

    typedef struct quicklistNode {
        // 前一个节点指针
        struct quicklistNode *prev;
        // 后一个节点指针
        struct quicklistNode *next;
        // 当前节点 ziplist 指针
        unsigned char *zl;
        // 当前节点 ziplist 字节大小
        unsigned int sz;
        // 当前节点 ziplist 中 entry 个数
        unsigned int count : 16;
        // 编码方式:1,ziplist;2,lzf 压缩模式
        unsigned int encoding : 2;
        // 数据容器类型(预留):1,其他;2,ZipList
        unsigned int container : 2;
        // 是否被解压缩:1,说明被解压了,将来要重新压缩;0,未解压
        unsigned int recompress : 1;
        // 测试用
        unsigned int attempted_compress : 1;
        // 预留
        unsigned int extra : 10;
    } quicklistNode;
    

    27.png

    SkipList

    SkipList 是一个链表,有几个特点:

    • 元素按照升序排列存储
    • 节点可能包含多个指针,指针跨度不同

    28.png

    SkipList 的结构如下:

    typedef struct zskiplist {
        // 头尾节点指针
        struct zskiplistNode *header, *tail;
        // 节点个数
        unsigned long length;
        // 最大索引层级,默认是 1
        int level;
    } zskiplist;
    
    typedef struct zskiplistNode {
        // 节点存储值
        sds ele;
        // 节点分数,用于排序
        double score;
        // 前一个节点指针
        struct zskiplistNode *backward;
        // 多级索引数组,不同的节点,它保存的层级节点不一样,比如上图中,节点 1 保存这 1、2、3、4 层级的节点,节点 3 保存这 1、2 层级的节点
        struct zskiplistLevel {
            // 下一个节点指针
            struct zskiplistNode *forward;
            // 索引跨度
            unsigned long span;
        } level[];
    } zskiplistNode;
    

    29.png

    相关文章

    JavaScript2024新功能:Object.groupBy、正则表达式v标志
    PHP trim 函数对多字节字符的使用和限制
    新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
    使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
    为React 19做准备:WordPress 6.6用户指南
    如何删除WordPress中的所有评论

    发布评论