Redis底层数据结构

image-20240325135146100

简单动态字符串

简单动态字符串，SDS（Simple dynamic string，SDS），SDS是Redis的默认字符串表示

sds的结构包括头部和数据两部分

头部包括

len | alloc | flags | '\0'

len 保存了SDS保存字符串的长度

alloc 分别以uin8，uint16，uint32，uint64表示整个SDS除了头部和末尾的\0，剩余的字节数

flags 始终为1字节，以低三位标示着头部的类型，高5位未使用。

为什么使用SDS

  • 常数复杂度获取字符串长度

    • 得益于len的存在

  • 杜绝缓冲区溢出

    • 得益于len的存在

  • 减少修改字符串的内存重新分配次数

    • 得益于alloc和len的存在，修改字符串SDS实现了空间预分配和惰性空间释放两种策略。

    • 空间预分配：对字符串进行空间扩展时，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重新分配次数。

    • 惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用alloc属性将这些字节数量记录下来，等待后续使用。

  • 二进制安全

    • 对于一些二进制文件，其内容可能包括空字符串，因此C字符串无法正确存取，但是SDS并不是以空字符来判断是否结束，而是以len属性长度来判断字符串是否结束。

  • 兼容部分C字符串函数

    • 仍然以\0结尾

压缩列表

ziplist是为了提高存储效率而设计的一种特殊编码的双向链表。它可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。它能在O(1)的时间复杂度下完成list两端的push和pop操作。但是因为每次操作都需要重新分配ziplist的内存，所以实际复杂度和ziplist的内存使用量相关

zlist在内存中的存储格式如下：

zlbytes | zltail | zllen | entry entry......entry | zlend

4bytes | 4bytes | 2bytes | entry entry......entry | 1byte

  • zlbytes，存储的是整个ziplist所占用的内存的字节数

  • zltail，它指的是最后一个entry的偏移量，用于快速定位最后一个entry，以快速完成pop等操作

  • zllen，它指的是整个ziplist中entry的数量。这个值只有16位，如果entry的数量等于或者大于了65535，那么该字段的值固定为65535，如果想要获得实际数量，那么就需要遍历所有的entry才能得到

  • zlend，是一个终止字节，其值全为F，ziplist保证任何情况下，一个entry的首字节都不会是255

entry的存储结构

一般结构为：

prevlen | encoding | entry-data

  • prevlen 前一个entry的大小，具体格式如下解释

  • encoding：不同的情况下值不同，用于表示当前entry的类型和长度

  • entry-data：真实用于存储entry表示的数据；

当存储的数据为int类型时，encoding和entry-data会合并在encoding中表示，此时没有entry-data字段；

在redis中，在存储数据时，会先尝试将string转换为int存储，节省空间；

此时entry的结构：prevlen | entry-data

prevlen结构

当前一个元素的长度小于254的时候，prevlen长度为1个字节，值即为前一个entry的长度，如果长度大于等于254时，prevlen用5个字节表示，第一个字节设置为254，后面的4个字节存储一个小端的无符号整型，表示前一个entry的长度

encoding编码

encoding的长度和值根据保存的是int还是string，还有数据的长度而定

前两位用来表示类型，当为"11"时，表示entry存储的是int类型，其他表示存储的是string。

为什么ZipList省内存

这里的节省内存是相对于普通的list来说，对于一个普通的数组，它的每一个元素所占用的内存是相同的，且取决于最大的那个元素

  • ziplist增加encoding字段，针对不同的encoding来细化存储大小

  • 遍历元素时如何定位到下一元素？在普通数组中完全不需要考虑，但是ziplist每一个data占据的内存不一致，所以为了解决遍历，需要增加记录上一个元素的length，所以增加了prelen字段

缺点

  • ziplist不预留内存空间，并且在移除节点后，也是立即缩容，这代表每次写操作都会进行内存分配操作

  • 节点如果扩容，导致结点占用的内存增长，并且超过254字节，可能会导致链式反应：其后一个节点的entry.prevlen需要从1字节扩容至5字节。最坏的情况下，第一个节点的扩容会导致整个ziplist表中的后续所有节点的entry.prevlen字段扩容。这种现象被称为连锁更新

快表

快表，quicklist，在Redis 3.0之前List对象的底层结构为双向链表或者压缩列表，但在3.2之后，List对象的底层改为quicklist数据结构实现。

它是一种以ziplist为结点的双端链表结构，宏观上，quicklist是一个链表，微观上，链表中的每一个节点都是ziplist。

快表其实就一个双向链表，但是其中每一节点所存储的值并非一个简单的值，而是一个ziplist，当插入某个位置时，并不会立刻建立新节点，而是检查被插入位置的ziplist是否已经存满，没有存满则插入ziplist中，否则再建立新的节点

quicklist有自己的优点, 也有缺点, 对于使用者来说, 其使用体验类似于线性数据结构, list作为最传统的双链表, 结点通过指针持有数据, 指针字段会耗费大量内存. ziplist解决了耗费内存这个问题. 但引入了新的问题: 每次写操作整个ziplist的内存都需要重分配. quicklist在两者之间做了一个平衡. 并且使用者可以通过自定义quicklist.fill, 根据实际业务情况, 经验主义调参

Hash表

Redis的hash表和其他实现的hash表类似。主要有以下特点

  • 针对Hash冲突，Redis采用链式hash冲突的方式

  • Hash扩容（rehash）

    • 定义了两个hash表，交替使用，rehash时，为另外一个hash表分配存储（现有hash表大小的两倍左右），然后进行数据迁移，然后释放原有hash表空间。

      如果hash表很大，在数据迁移的过程中会涉及到大量的数据拷贝，此时可能会对redis造成阻塞，无法服务其他请求。

  • 为避免上述rehash过程中，对Redis性能的影响，Redis采用了渐进式rehash，即数据的迁移和copy并不是一次性迁移完成，而是分多次迁移完成。步骤如下：

    • 给hash表2分配空间

    • 在rehash进行期间，每次哈希表袁旭进行新增、删除、查找或者更新操作时，Redis除了会执行对应的操作之外，还会顺序将hash表1中索引位置上所有的key-value迁移到hash表2上

    • 在rehash过程中，哈希表的删除、查找、更新等操作都会在两个hash表进行，比如先去表1查，没查到再去表2查。

    • 在新增时，只会在表2中添加，而不会在表1中添加。

  • rehash的条件触发和Java的hashmap类似，会通过负载因子来进行计算，负载 = 已经存储的节点/哈希表大小

  • 当负载因子大于等于1时，并且没有执行rdb和aof时，会执行rehash

  • 当负载因子大于等于5时，不管有没有在执行rdb 和 aof，都会进行强制的rehash

整数集合

整数集合是集合类型的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

IntSet结构包括三个字段

  • encoding，编码方式，int16，int32，int64

  • length，代表其中存储的整数的个数大小

  • contents[]，这里定义为int8，但是其中并不保存任何int8的值，真正存储的数由encoding决定

整数集合的升级

当在一个int16类型的整数集合中插入int32类型的值时，整个集合的所有元素都会转换为int32类型。主要分为三步：

  • 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

  • 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。

  • 最后改变encoding的值，length + 1

但并不会进行降级操作

跳表

ZSkipList，跳跃表结构在Redis中的运用场景只有一个，那就是作为有序列表（Zset）使用。跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来比较的，而且实现方面比平衡树要优雅，这是跳跃表的长处。跳跃表的缺点就是需要存储空间比较大，属于利用空间来换取时间的数据结构。

跳表是在链表的基础上改进过来的，实现了一种多层有序链表。

下面是跳表节点的结构：

每个跳表节点都有一个后向指针（struct zskiplistNode *backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。

其中的level数组中每一个元素代表跳表的一层，其中的span是指跨度，用来记录两个节点之间的距离。

跨度实际上为了计算这个节点在跳表中的排位。即每次跳了之后都会知道跳了多远，最后得到这个节点在表中的排序。

如下是一个跳表示例。

image-20240325162324493

查询过程

从头节点的level数组的最高层开始查找吗，有以下两个判断条件：

  • 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。

  • 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。

如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

跳表节点的层数设置

建立跳表的过程即是建立索引的过程，那么最理想的比例即为2：1，即下一层的索引节点是上一层索引节点的一倍，这样我们能够在logN的复杂度查找。

那么如何维持这个比例?

Redis采用随机数的方式，在创建一个节点时，随机生成一个节点的层数高度。具体实现来讲：

在0，1内生成随机数，如果这个小于0.25，那么层数就加一，然后继续生成下一个随机数，直到随机数的结果大于0.25结束

如何理解这个0.25的设置？

我们渴望的比例为0.5不是吗？即下一层的节点是上一层节点的二倍。这样思考，对于一个节点，如果它被建立了索引，那么一定有第一层索引，无论他被建立了几层索引。那么即

我们不再设置多次的随机数，而是一次来决定它的高度。那么如果大于0.5这个节点不再被建立索引，小于0.5的节点都要被建立索引（这里对应了2：1）,那么该有多少节点仅被建立一级索引呢？答案是1/4。剩下的1/2要被建立一层以上的索引。

为什么用跳表，而不是平衡树?

  • 内存占用上来看，跳表比平衡树更加灵活一些。

    • 可以指定参数来调整内存占用

  • 在范围查找时，跳表的操作比平衡树更简单

  • 跳表的算法实现更简单

上一页Redis基础下一页Redis持久化

最后更新于

这有帮助吗？