Redis设计与实现——数据结构与对象

2022/6/29 2:20:21

编程Tag： 对象数据结构链表 Redis 节点字节 sds 给定

本文主要是介绍Redis设计与实现——数据结构与对象，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数据结构

由于C语言内置的数据结构匮乏，Redis实现了一些自己的数据结构。

我们需要分清数据结构和Redis数据类型的区别：

数据结构就只是按照某种结构组织起来的数据，Redis会在很多地方复用它
Redis数据类型指的是面向Redis用户提供的类型，即：string、hash、zset、list、set
Redis使用不同的数据结构来实现Redis的五种数据类型，甚至对于某些数据类型，它的底层并不一定只有一种数据结构来支撑它
Redis服务器中的很多功能也使用到了它定义好的数据结构进行工作，也就是说这些定义好的数据结构并非只用于构建Redis的五种数据类型

你可能看的一头雾水，没关系，在数据结构一节之后你就会明白上面这些话的意思。你现在只需要知道，这一节要说的数据结构并不是我们所熟知的Redis五种数据类型，而是实现它们的基础。

简单动态字符串（Simple Dynamic String, SDS）

由于C语言中的字符串比较底层，很多字符串函数效率不高，而且C原始的字符串对象不方便复用。

SDS是Redis对C语言字符串的包装，提供了一些更强大的特性。

快速获取长度，SDS通过一个成员变量len来记录字符串的长度，这让函数sdslen可以在O(1)的时间复杂度下实现。
SDS不会出现缓冲区溢出，sdscat函数在连接两个字符串时，如果检测到目标字符串长度不够，会创建一个足够大小的新字符串来实现连接
SDS提供空间预分配技术，在对SDS进行空间扩展时，如果要扩展成的空间大小小于1M，SDS实际会分配出两倍于它的空间。这样能够避免每次对SDS进行修改（拼接）都要内存重分配。（若大于1M则只额外分配1M的空间）
SDS提供惰性空间释放，它提供free成员变量，记录当前SDS对象中没有被用到的空间，当你修剪一个字符串时，它只调节free变量而已。这让修剪操作不需要内存重分配，并且让后续的连接操作提供直接复用这些空闲空间的可能性。
支持存储二进制：SDS可以直接把底层的char数组当成字节数组来用，SDSAPI在读取时没有任何限制，如果你存的是二进制值，你取出来也是二进制值。
兼容部分C函数：由于底层仍然使用char数组，所以能够直接兼容部分C的字符串操作函数

API

函数	作用	时间复杂度
sdsnew	创建一个包含指定字符串的SDS	O(N)
sdsempty	创建一个空SDS	O(1)
sdsfree	释放给定的SDS	O(N)
sdslen	获取SDS长度	O(1)
sdsavail	返回SDS空闲空间长度	O(1)
sdsdup	创建SDS副本	O(N)
sdsclear	清空SDS中的内容	O(1)
sdscat	拼接字符串到SDS	O(N)
sdscatsds	拼接两个SDS	O(N)
sdscpy	将给定的C字符串复制到SDS中	O(N)
sdsgrowzero	用空字符串将SDS扩展到指定长度	O(N)
sdsrange	保留SDS给定区间内的数据	O(N)
sdstrim	在SDS中移除所有在给定C字符串中出现过的字符	O(N^2)
sdscmp	比较两个SDS是否相同	O(N)

链表

链表作为Redis数据结构中list的实现之一，在Redis数据结构里非常重要。

Redis的链表特性：

双端，有head和tail节点的引用
无环
带和SDS一样的长度计数器
多态，可以存任意类型数据，链表有三个成员属性来支持多态性
1. dup属性是一个函数，用于复制链表节点所保存的值
2. free属性是一个函数，用于释放链表节点所保存的值
3. match属性是一个函数，用于对比链表节点所保存的值和另一个输入值是否相等

API

函数	作用	时间复杂度
listSetDupMethod	设置dup函数	O(1)
listGetDupMethod	获取dup函数	O(1)
listSetFreeMethod	设置free函数	O(1)
listGetFreeMethod	获取free函数	O(1)
listSetMatchMethod	设置match函数	O(1)
listGetMatchMethod	获取match函数	O(1)
listLength	链表长度获取	O(1)
listFirst	返回链表头节点	O(1)
listLast	返回链表尾节点	O(1)
listPrevNode	返回给定节点的前置节点	O(1)
listNextNode	返回给定节点的后置节点	O(1)
listNodeValue	返回给定节点的值	O(1)
listCreate	创建新链表	O(1)
listAddNodeHead	添加新节点到链表头	O(1)
listAddNodeTail	添加新节点到链表尾	O(1)
listInsertNode	将一个给定节点插入到另一个给定节点的之前或之后	O(1)
listSearchKey	返回链表中包含指定值的节点	O(N)
listIndex	返回链表在给定索引上的节点	O(N)
listDelNode	从链表中删除给定节点	O(N)
listRotate	把链表尾弹出，插入到链表头	O(1)
listDup	复制给定链表的副本	O(N)
listRelease	释放链表占用空间	O(N)

字典

字典就是存储一个东西到另一个东西的映射，在Redis数据结构中，字典就是一个HashMap。

Redis的HashMap使用链表解决冲突
如果负载因子过大，Redis会使用重哈希（rehash）将当前哈希表重映射到另一个更大的哈希表
由于Redis是单线程模型，为了避免重映射大哈希表带来的服务停顿，Redis的重映射机制是惰性的，目的是将rehash的成本均摊到每一次对该哈希表的请求上。每个哈希表在rehash阶段维护一个rehashindex，它代表当前要移动底层数组中那一项的项目链表中的所有节点到新的哈希表中，rehashindex初始是0，hash表每被请求一次，rehashindex+1，同时底层数组中有一个链表中的所有节点被rehash到新哈希表。rehash期间，redis先在原哈希表中查询，如果查询不到，再尝试去新哈希表中查询，当rehash结束，rehashindex=-1，源哈希表被销毁。
负载因子=哈希表中元素数量/底层数组大小
如果服务器没有执行BGSAVE、BGREWRITEAOF，那么负载因子大于等于1时rehash，否则大于等于5时rehash。这是因为rehash操作会产生大量的写内存操作，BGSAVE、BGREWRITEAOF这两个操作都会创建子进程来读取原哈希表，在使用写时复制的系统中，这会产生大量的复制，所以在这两个操作时Redis为了避免复制调高了负载因子。

API

函数	作用	时间复杂度
dictCreate	创建字典	O(1)
dictAdd	向哈希表中添加键值对	O(1)
dictReplace	根据指定的键修改值	O(1)
dictFetchValue	返回指定键的值	O(1)
dictGetRandomKey	返回随机键值对	O(1)
dictDelete	删除一个键值对	O(1)
dictRelease	释放字典	O(N)

跳跃表

跳表就是将链表之上使用链表再建立一层索引，达到几乎和平衡二叉树一样的搜索效率。这有点像数据库系统中的多级非聚集索引。

跳表这种数据结构不经常在教材上出现，但在很多设计中都常用，这里是一篇关于跳表的文章：数据结构与算法——跳表。

Redis中的跳跃表就用来实现有序集合，所以，跳跃表节点中提供一个score字段，用于对跳跃表节点进行排序。

API

函数	作用	时间复杂度
zslCreate	创建一个跳跃表	O(1)
zslFree	释放跳跃表	O(N)
zslInsert	向跳跃表中插入	平均O(logN)，最坏O(N)
zslDelete	删除跳跃表中的一个节点	平均O(logN)，最坏O(N)
zslGetRank	返回包含给定成员和分值的节点在跳跃表中的排位	平均O(logN)，最坏O(N)
zslGetElementByRank	返回跳跃表在给定排位上的节点	平均O(logN)，最坏O(N)
zslIsInRange	返回跳跃表中是否至少有一个元素在给定分值范围内	O(1) 检查跳表头节点和尾节点即可
zslFirstInRange	返回跳表中第一个在给定范围内的元素	平均O(logN)，最坏O(N)
zslLastInRange	返回跳表中最后一个在给定范围内的元素	平均O(logN)，最坏O(N)
zslDeleteRangeByScore	删除分值范围内所有节点	O(N) N是被删除元素个数
zslDeleteRangeByRank	删除指定排位范围的所有节点	O(N) N是被删除元素个数

整数集合

intset是一种简单的，基于数组的集合实现，它只能保存整数，这个整数的位数并不固定。下面是intset的定义

encoding指定整数集合中，整数占用的位数，比如INTSET_ENC_INT16代表content中保存的实际是int16_t类型的值。
length是元素数

intset将维护底层数组中元素的有序性以及唯一性。

升级

如果在一个encoding==INTSET_ENC_INT16的intset上插入一个32位整数，那么当前intset需要被升级：

将底层数组大小扩展到以32位整数存储时足够的大小
将每个元素转换成32位，并放到正确的位置
将新元素添加到底层数组中

intset不支持降级

整数集合API

函数	作用	时间复杂度
intsetNew	创建一个新的整数集合	O(1)
intsetAdd	添加一个元素到整数集合中	O(N)
intsetRemove	从整数集合中移出一个元素	O(N)
intsetFind	检查给定值是否存在于集合	O(logN) 二分查找
intsetRandom	从整数集合中随机返回一个元素	O(1)
intsetGet	取出在给定索引上的元素	O(1)
intsetLen	获取集合中元素数量	O(1)
intsetBlobLen	获取集合占用字节数	O(1)

压缩列表

压缩列表是比刚才所说的链表更加紧凑的列表结构，它是经过编码的内存区块，你也可以理解为字节数组。下图是它的编码方式：

zlbytes：4字节，记录压缩列表占用的内存字节数
zltail：4字节，记录压缩列表的尾节点距离压缩列表的起始地址的偏移量，这使得压缩列表可以在O(1)的时间复杂度下找到尾节点地址
zllen：2字节，压缩列表节点数量
entryX：具体的列表项，长度不定
zlend：1字节，用于标记压缩列表的尾部。和字符串尾部的\0异曲同工。

节点构成

由于压缩列表的节点可以存储多种多样的数据（整数和字节数组），所以不能像整数集合一样简单，下面是节点的内部结构：

previous_entry_length：前一个节点的长度，用于获得前一个节点的起始地址。当前一个节点的长度小于254字节，该字段可以用1个字节实现，否则就用5个字节实现
encoding：占用1~5字节，记录content的类型和长度。下面是该值于content类型长度的对照表：

对于字节数组类型，encoding开头两位代表类型，后面代表字节数组长度。
content：实际保存节点值

连锁更新

考虑极端情况下，压缩列表中所有节点长度都为254，它们的previous_entry_length字段只需要1字节就可以。现在，想要往压缩列表头部插入一个长度大于254字节的节点，那么压缩列表原先的第一个节点的previous_entry_length就要由原先的1字节变成5字节，节点长度就需要变成258，那么后面的节点也要变，随后的所有节点都要变。

删除也可能引发相同的连锁更新。

连锁更新中的每一步都需要空间重分配，所以最坏情况下需要O(N^2)的时间复杂度完成更新。但这种最坏情况太难发生了。

压缩列表API

函数	作用	时间复杂度
ziplistNew	创建一个新的压缩列表	O(1)
ziplistPush	创建一个包含给定值的新节点，加到表头或表尾	O(N)，最坏O(N^2)
ziplistInsert	将包含新值的节点插入到给定节点后	O(N)，最坏O(N^2)
ziplistIndex	返回给定索引上的节点	O(N)
ziplistFind	查找并返回包含了给定值的节点	由于节点值可能是字节数组，所以最坏情况下O(N^2)
ziplistNext	返回给定节点的下一个节点	O(1)
ziplistPrev	返回给定节点的上一个节点	O(1)
ziplistGet	获取给定节点所保存的值	O(1)
ziplistDelete	从压缩列表中删除指定节点	O(N)，最坏O(N^2)
ziplistDeleteRange	从压缩列表中删除多个连续指定节点	O(N)，最坏O(N^2)
ziplistBlobLen	返回压缩列表占用字节数	O(1)
ziplistLen	返回压缩列表目前包含的节点数量	节点数量小于65535时可以直接使用`zllen`，所以是O(1)，大于等于时就是O(N)，需要手动遍历

对象

这篇关于Redis设计与实现——数据结构与对象的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！