526互联

Redis（八）底层数据类型原理

发布时间 2023-08-13 00:04:51作者: Tod4

Redis（八）底层数据类型原理

1 SDS 动态字符串

  • Redis中保存的key是字符串，value往往是字符串或者字符串的集合，字符串是redis里面最常用的数据结构

  • Redis虽然是用C语言写的，没有直接使用C语言的字符串，原因有：

    • 获取字符串长度需要位运算（因为结束符\0的存在，需要数据长度-1的运算）
    • 非二进制安全（如果中间出现结束符\0则会出现错误）
    • 不可修改

  • 因此Redis构建了一种新的字符串数据结构，称为SDS（Simple Dynamic String）简单动态字符串

    • 因此对于key、value两个字符串，Redis底层都会去创建SDS

  • SDS的结构是用C语言定义的一个结构体，它主要包含两部分，一部分是记录SDS信息的头部，另一部分是字符串本身

    image-20230811102137537

    • len：存储已经保存的字符串的字节数，不包含C语言的结束标识\0，根据flags有五种类型，如类型为uint0_t则表示字符串len最大为8位即255的长度
    • alloc：存储已经申请到的总的字节数，不包含C语言的结束标识\0
    • flags：记录不同的SDS的类型，SDS有5种类型，分别是5、8、16、32、64字节大小的字符串
    • buf：实际的字符串

  • SDS的扩容：

    • 当给SDS添加字符串的时候，首先会申请新的内存空间：

      • 如果新字符串大小小于1M，则新空间为扩展后字符串的长度*2+1
      • 如果大于1M，则新空间为扩展后字符串的长度+1M+1，称为内存预分配

      为什么采用预分配而不是每次申请都去分配？

      因为操作系统中只有在核心态下才能进行内存的分配，因此每次内存分配都需要从用户态切换到核心态，造成性能的消耗

  • SDS的优点：

    • 获取字符串长度的时间复杂度为O(1)（直接返回len，不需要计算了）
    • 支持动态扩容，减少了内存分配次数
    • 二进制安全（使用len而不需要使用\0判断字符串的结束，因此中间可以出现\0）

2 IntSet 整数集合

  • IntSet是Redis中Set集合的一种实现方式，基于整数数组实现，并且具备长度可变、元素唯一、有序等特性

  • 具备类型升级机制，可以节省内存空间

  • 底层采用二分查找的方式来查询

  • 结构包含头部和集合数据实体两部分：

    image-20230811105911273

    • encoding：编码方式，决定整数数据的大小范围，支持存放16位、32位、64位整数。

      存储在contents整数数组的元素都必须按照encoding的编码存放对应的类型整数，这样能够方便通过偏移量*类型大小找到元素

    • length：元素的个数

    • contents：整数数组，保存一个指向起始元素的指针

IntSet 升级
  • 在为IntSet添加的数字超出原有encoding 编码方式规定类型的时候，IntSet就会自动升级编码方式到合适的大小
  • 首先按照新的编码方式及元素个数扩容数组
  • 按照倒序的方式将数组中的元素拷贝到扩容后正确的位置，使用倒序是因为扩容后元素大小发生变化，这样如果先插入前面的会导致后面的地址空间被破坏
  • 将待添加的元素放入数组末尾
  • 最后修改IntSet的编码类型和数组长度

3 Dict 字典

  • Redis是一个键值型数据库（Key-Value Pair），可以根据键实现快速的增删改查，Dict主要就是用来实现键与值的映射关系，主要是使用一个数组+单向链表来实现解决哈希冲突的

  • Dict包括两个哈希表，一个用来实际存储数据，另一个用来rehash

  • Dict通过伸缩和扩容机制来保证空间的充分利用

1 Dict 的数据结构

  • 字典的数据结构主要有哈希表(DictHash Table)和哈希节点(Dict Entry)两部分：

    • 字典(Dict)：包含一个内置多种hash函数的字典类型指针，两个哈希表(DictHash Table)（一个存储当前数据，另一个为空rehash的时候使用），一个rehashidx记录rehash的进度，还有一个pauserhash记录rehash的状态

      image-20230811120118336

    • 哈希表(DictHash Table)：包含一个指向哈希节点(Dict Entry)的指针，哈希表的大小size（size的大小为2的n次方），哈希表大小的掩码（size-1），哈希节点(Dict Entry)的个数used

      image-20230811114313201

    • 哈希节点(Dict Entry)：包含具体的存储的键值对信息和指向下一个哈希节点(Dict Entry)的next指针

      image-20230811114511632

  • 在向Dict添加键值对的时候，Redis首先根据key计算出hash值，然后对hash值和哈希掩码(sizemask)进行与运算（hash & sizemask，sizemask值为entry数组长度-1，由于sizemark的值为2^n-1，因此与运算就相当于取二进制的最后一位也就是取余操作）来计算元素应该存储到哈希节点(Dict Entry)数组的哪个位置

  • 当出现哈希冲突的时候，使用头插法每次将待插入节点插入链表的前端

image-20230811120432572
2 Dict的扩容

​ Dict中的HashTable就是数组结合链表的实现，当集合中元素较多的时候，必然导致哈希冲突增多，链表过长则查询效率会大大降低，因此需要对哈希表进行扩容操作：

  • 首先判断Dict是否已经在进行Rehash，如果是则取消本次扩容

  • 否则哈希表如果为空，则初始化哈希表为默认大小4

  • 不为空，Dict则在每次更新键值对的时候都会检查负载因子（LoadFactor=used/size），满足以下两种情况时就会触发哈希表的扩容：（used：哈希节点(Dict Entry)个数，size：哈希表(DictHash Table)的大小）

    • 哈希表的LoadFactor>=1，并且服务器没有执行BGSAVE或者BGREWRITEBOF等后台进程
    • 哈希表的LoadFactor>=5

  • 底层会对扩容的大小做判断，实际上是找第一个大于used+1的2^n

3 Dict的收缩

​ 为了防止哈希表长度过大，然后删除元素过多，Dict在扩容以外针对每次删除，也会去检查负载因子，当负载因子<0.1的时候就会进行哈希表的收缩：

  • 每次删除成功后，检查是否重置Dict大小，如果大于哈希表初始大小4并且负载因子小于0.1，则调用dictResize进行重置
  • dictResize方法首先判断是否在进行bgrewritebof和rehash，没有则执行收缩，将大小收缩为第一个大于等于2^n的used哈希节点(Dict Entry)个数
4 Dict的Rehash：渐进式哈希
  • Dict的渐进式哈希指的是不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizeMask变化，而key的查询与sizeMask有关，因此必须重新对哈希表中的每一个元素计算索引，插入新的哈希表
  • 重新计算哈希表的realeSize，值取决于当前是要做扩容还是伸缩：
    • 如果是扩容，则新size为第一个大于等于dict[0].used+1的2^n
    • 如果是收缩，则新size为第一个大于等于dict[0].used的2^n（并且不能小于4）
  • 然后按照新的realeSize申请内存空间，创建哈希表并赋值给dict[1]
  • 设置dict.rehashidx = 0，标志开始rehash，防止在此过程出现扩容或者收缩的行为
  • 将dict[0]的每一个dictEntity都rehash到dict[1]中
  • 最后将dict[1]赋值给dict[0]，dict[1]再初始化为空链表，最后释放掉原来dict[0]的内存
5 Dict的缺点

​ 由于EntrySet哈希节点之间是通过指针建立的单链表，因此在数据量较大的情况下指针会消耗很大一部分内存空间，可以使用压缩链表解决这一问题

4 压缩列表 ZipList

  • 压缩列表 ZipListn能够不依靠指针的情况下的正序、逆序遍历，并且能够使用连续的内存地址空间存储不同类型的数据
  • 压缩列表 ZipList可以看做一种特殊的双端链表，它一方面使用连续的内存地址空间，另一方面Ziplist中的Entry不像普通链表那样记录前后节点的指针，因为在C中记录两个指针需要消耗16字节浪费空间，而是采用特殊的结构：
  • 压缩列表 ZipList包括五部分：
    • zlbytes：记录压缩链表占用的字节数
    • ztail：记录尾entry节点的起始地址，方便进行逆序遍历
    • zllen：记录链表长度
    • entry：节点记录真实存储数据
    • zlend：压缩链表的结束标志
  • 压缩链表节点Enrty又包括：
    • pre_entry_length：记录前一个节点的长度，占1个或者5个字节，大小是可变的（会导致连锁更新问题，在下面）（压缩链表的压缩也正是因为此，它实现了对链表指针的压缩）：
      • 如果前一个节点的长度小于245字节，则采用1个字节保存这个长度值
      • 如果前一个节点的长度大于245字节，则采用5个字节保存这个长度值，第一个字节为0xfe，后面4个字节才是真实的数据
    • encoding：编码属性，记录content记录类型（字符串还是整数）以及长度，占用1个、2个或者5个字节
    • contents：负责保存节点的数据，可以是字符串或者整数
  • 这样的话就能够通过上面的结构实现不依靠指针的情况下的正序、逆序遍历，并且能够存储不同类型的数据
    • 正序遍历的时候，只需要计算当前entry的起始地址加上entry记录的前一个节点长度的值占用的字节、编码属性占用占用的字节数、数据大小占用的字节数（根据编码属性推断）即可得到下一个entry的起始地址
    • 逆序遍历只需通过压缩列表 ZipList记录的尾节点起始地址减去节点的前一个节点长度，即可得到前一个节点的起始地址，循环即可实现逆序遍历
ZipList的连锁更新问题
  • ZipList的连锁更新问题指的是当有N个连续的、长度为250~253字节之间的ZipList的Entry节点，因为节点大小没有超过254字节，因此后面的节点在记录pre_entry_length前一个节点的长度的时候，只需要使用1个字节的pre_entry_length字段即可
  • 但是如果在这N个节点之前插入一个超过254字节的数据，则第一个节点就需要使用5个字节的pre_entry_length字段的字段记录，那么这个节点自身的大小也满足大于等于245，进而导致一系列的连锁更新，浪费很大的性能
  • 因为连锁更新的条件是有N个连续的、长度为250~253字节之间的ZipList的Entry节点，比较苛刻所以发生的概率极低，目前redis还没有很好的解决方法

​ 回顾：

  • pre_entry_length：记录前一个节点的长度，占1个或者5个字节，大小是可变的（会导致连锁更新问题，在下面）（压缩链表的压缩也正是因为此，它实现了对链表指针的压缩）：
    • 如果前一个节点的长度小于245字节，则采用1个字节保存这个长度值
    • 如果前一个节点的长度大于245字节，则采用5个字节保存这个长度值，第一个字节为0xfe，后面4个字节才是真实的数据
ZipList的缺点及解决方案

  • ZipList虽然节省内存，但是申请内存的时候需要使用连续的内存空间，如果内存占用较多，就会导致内存效率很低，并且申请容易导致内存碎片

    解决方案：限制ZipList的大小和entry的长度

  • 但是还是想存储大量数据怎么办？

    解决方案：可以创建多个ZipList分片来解决

  • 怎么对这些分片进行管理和查找？

    解决方案：Redis3.2版本后引入了一种新的数据结构QuickList，它是一个双端链表，不过链表中的每一个节点都是ZipList

5 快表 QuickList

image-20230812082255577

  • 快表 QuickList是Redis3.2版本后引入了一种新的数据结构，它是一个双端链表，不过链表中的每一个节点都是ZipList

  • QuickList的数据结构：包括指向头尾节点的两个指针、记录所有ziplist的entry节点的数量的count、ziplist的entry上限、首尾不压缩的节点个数等

    image-20230812081819422

    QuickListNode的数据结构为：包括前一个和下一个节点的指针、当前QuickListNode指向的ZipList的指针、当前节点指向的ZipList的字节大小和entry个数、ZipList采用的编码方式和是否被解压缩记录等

    image-20230812081827278

  • 为了避免QuickList中每个ZipList中的Entry节点过多，Redis提供一个配置项limit-max-ziplist-size来限制（默认-2，即每个ZipList的内存占用不超过8kb）

    • 如果值为正，则代表ZipList的允许的entry个数的最大值
    • 如果值为负，则代表ZipList的最大内存大小，分5种情况
      • -1：每个ZipList的内存占用不超过4kb
      • -2（默认）：每个ZipList的内存占用不超过8kb
      • -3：每个ZipList的内存占用不超过16kb
      • -4：每个ZipList的内存占用不超过32kb
      • -5：每个ZipList的内存占用不超过64kb

    可以通过config get list-max-ziplist-size命令来设置

  • 快表 QuickList还能够对ZipList进行数据压缩，通过配置项list-compress-depth来控制，一般链表都是从首尾进行访问的，所以不对首尾进行压缩：

    • 0：表示不压缩
    • 1：首尾各1个节点不压缩，其他压缩
    • n：首尾n个不压缩，其他压缩

6 跳表 SkipList

1 跳表的特点
  • 跳表本质就是一个双向链表，每个节点都包含score和节点实际存储的值element，节点会按照score进行排序，score相同则按照element进行排序
  • 每个节点可以包含多级指针，层数是1到32之间的随机数,不同层指针到下一个节点的跨度不同，层级越高，跨度越大，一级指针是指跨度为1的指针，二级则是跨度为2的...以此类推
  • 跳表存储量是非常大的，增删改查的效率和红黑树基本一致，但是实现更加简单
2 跳表的具体数据结构
image-20230812225651256

  • 跳表SkipList的数据结构包括：指向头尾节点的指针、节点的数量和跳表的最大索引层级

    image-20230812224321450

    ​ 而跳表的每一个节点又包含每个节点存储的值element、用于节点排序、查询的节点分数score、一个指向前一个跳表节点的指针backward和一个多级索引数组level[]，用于记录每级索引的跨度和索引指向的下一个节点

    image-20230812224332797
3 跳表的查找过程
  • 首先从初始跳表节点的最高层索引数组按照最高的索引跨度向前查找
  • 如果下一个跨度节点的score的值大于当前遍历跳表节点，则进入下一级索引数组，直到达一级指针也找不到或者找到为止

在这里插入图片描述

  • 如上，找5则按照蓝线
  • 找3的时候则三级指针的下一个大于3，往下一级找到1，下一个5仍大于3，继续下一级找到3
4 跳表的插入过程
  • 首先找出最后一个小于等于插入值的节点，然后将值插入到该节点的右边
  • 然后通过跳表节点的forward前向指针向前遍历跳表节点，如果遍历的跳表节点的层级索引不为空，则将对应层级索引的backward后向指针指向插入跳表节点的新建层级节点
  • 依次向前执行该过程，就完成了跳表的节点插入
5 跳表的删除过程
  • 查询到该节点，从最底层的索引数组节点开始删除
  • 具体是使得同一索引层级的左边的backward后向指针指向删除跳表节点对应层级节点的后一个
  • 最后删除跳表节点，释放内存即完成了跳表的删除

跳表的插入和删除是自己进行的总结，感觉网上的帖子很多讲的不是很对

7 RedisObject

1 RedisObject的数据结构

  • 上面的SDS、IntSet、Dict、ZipList、QuickList、SkipList都是Redis底层的结构，也就是任意类型的键和值，在Redis中都是经过进行封装为RedisObject后才能够使用的

  • 数据结构主要包括：

    • type对象类型：占4个bit位，分别为string、hash、list、set、zset

    • encoding底层编码方式：占4个比特位，共有11中编码方式

      image-20230812234626432

    • lru：记录该对象的最后一次被访问的时间，占用24个bit位，便于判断key空闲时间的长短

    • refCount：记录对象的引用计数，计数为0则说明对象无人引用可以被回收

    • ptr：指针，指向实际存放的数据的空间地址

    image-20230812233437434

    因此尽量使用list来存储key-value键值对，因此只会使用一个对象头，而如果使用string则每一个键值对都消耗一个造成空间浪费

2 Redis基本数据类型的编码方式
数据类型 编码方式
string int、embstr、raw
list 3.2之前LinkedList和ZipList，3.2之后QuickList
set intSet、HashTable
zset ZipList、HashTable、SkipList
hash ZipList、HashTable

新的三种数据类型呢？

BitMap和HyperLogLog底层仍是string，GEO底层是sortedSet只是功能上的扩展