哪里有做网站的素材,手机网站如何做才能兼容性各种手机,佛山做外贸网站如何,边个网站可以接模具做Redis 为什么那么快 redis是一种内存数据库#xff0c;所有的操作都是在内存中进行的#xff0c;还有一种重要原因是#xff1a;它的数据结构的设计对数据进行增删查改操作很高效。 redis的数据结构是什么 redis数据结构是对redis键值对值的数据类型的底层的实现#xff0c… Redis 为什么那么快 redis是一种内存数据库所有的操作都是在内存中进行的还有一种重要原因是它的数据结构的设计对数据进行增删查改操作很高效。 redis的数据结构是什么 redis数据结构是对redis键值对值的数据类型的底层的实现注意不是String、List、Hash、Set、Zset、BitMap、HyperLogLog、GEO、Stream这些数据类型而是对这些类型的底层实现。 redis数据结构与数据类型的关系 从上图我们也知道数据结构主要有SDS、双向链表、压缩列表、哈希表、跳表、整数集合、quicklist、listpack。但是双向链表、压缩列表已经使用quicklist、listpack替代了。 键值对数据库是怎么实现的
在讲数据结构之前我们先了解一下redis的键值对key-value是怎么实现的。
redis键值对的key是一个字符串对象而value可以是redis数据类型中的任何一个对象。那这键值对是怎么保存的呢 Redis 是使用了一个「哈希表」保存所有键值对哈希表的最大好处就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对。哈希表其实就是一个数组数组中的元素叫做哈希桶 那么哈希桶又是怎么保存键值对数据的呢 哈希桶存放的是指向键值对数据的指针dictEntry*这样通过指针就能找到键值对数据然后因为键值对的值可以保存字符串对象和集合数据类型的对象所以键值对的数据结构中并不是直接保存值本身而是保存了 void * key 和 void * value 指针分别指向了实际的键对象和值对象这样一来即使值是集合数据也可以通过 void * value 指针找到。 上图说明 redisDb 结构表示 Redis 数据库的结构结构体里存放了指向了 dict 结构的指针 dict 结构结构体里存放了 2 个哈希表正常情况下都是用「哈希表1」「哈希表2」只有在 rehash 的时候才用具体什么是 rehash我在本文的哈希表数据结构会讲 ditctht 结构表示哈希表的结构结构里存放了哈希表数组数组中的每个元素都是指向一个哈希表节点结构dictEntry的指针 dictEntry 结构表示哈希表节点的结构结构里存放了 void * key 和 void * value 指针 *key 指向的是 String 对象而 *value 则可以指向 String 对象也可以指向集合类型的对象比如 List 对象、Hash 对象、Set 对象和 Zset 对象 注意void * key 和 void * value 指针指向的是 Redis 对象Redis 中的每个对象都由 redisObject 结构表示如下 上图说明 type标识该对象是什么类型的对象String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对象 encoding标识该对象使用了哪种底层的数据结构 ptr指向底层数据结构的指针。 到这里我们大概知道edis的键值对key-value的大体实现那么下面我们就开始聊聊这些底层实现的数据结构。
SDS
字符串在 Redis 中是很常用的键值对中的键是字符串类型值有时也是字符串类型。
Redis 是用 C 语言实现的但是它没有直接使用 C 语言的 char* 字符数组来实现字符串而是自己封装了一个名为简单动态字符串simple dynamic stringSDS 的数据结构来表示字符串也就是 Redis 的 String 数据类型的底层数据结构是 SDS。
SDS 的数据结构 SDS 的数据结构说明 len记录了字符串长度。这样获取字符串长度的时候只需要返回这个成员变量值就行时间复杂度只需要 O1。 alloc分配给字符数组的空间长度。这样在修改字符串的时候可以通过 alloc - len 计算出剩余的空间大小可以用来判断空间是否满足修改需求如果不满足的话就会自动将 SDS 的空间扩展至执行修改所需的大小然后才执行实际的修改操作所以使用 SDS 既不需要手动修改 SDS 的空间大小也不会出现前面所说的缓冲区溢出的问题。 flags用来表示不同类型的 SDS。一共设计了 5 种类型分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64后面在说明区别之处。 buf[]字符数组用来保存实际数据。不仅可以保存字符串也可以保存二进制数据。 SDS与C语言中字符串的区别
1.获取字符串长度
因为C语言字符串本身不记录自身的长度若要获取其长度则需要遍历字符串才能得到时间复杂度为O(N)而SDS在其自身的数据结构中记录了以使用字符串空间也就是len所以获取一个字符串长度的时间复杂度为O(1)
2.防止缓冲区的溢出
C 语言的字符串标准库提供的字符串操作函数大多数比如 strcat 追加字符串函数都是不安全的因为这些函数把缓冲区大小是否满足操作需求的工作交由开发者来保证程序内部并不会判断缓冲区大小是否足够用当发生了缓冲区溢出就有可能造成程序异常结束SDS由于其自身记录了长度在每次修改SDS时1API会检查SDS的空间是否足够2若不足则API会自动将SDS的空间扩展至所需的大小再进行接下来的操作。由此SDS可以避免缓冲区的溢出。
3.二进制安全
C 语言的字符串需要以 “\0” 字符来标识字符串结尾的。而SDS不需要它是有len 成员变量来记录长度所以它存储任意格式的二进制数据就算这个数据中间有“\0” 也不会因为遇到“\0” 结束。但是 SDS 为了兼容部分 C 语言标准库的函数 SDS 字符串结尾还是会加上 “\0” 字符。
4.减少修改字符串时内存重分配的次数
在一般的程序中每次修改字符串都执行一次内存重分配这是可以接受的但是redis作为数据库经常用于速度要求严苛、数据要求频繁修改的场合每次修改字符串所需要内存重分配可能会对性能造成影响。通过使用未使用的空间allocSDS实现了空间预分配与惰性空间释放两种优化策略。
5. 节省内存空间
SDS 结构中有个 flags 成员变量表示的是 SDS 类型。分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
这 5 种类型的主要区别就在于它们数据结构中的 len 和 alloc 成员变量的数据类型不同。
比如 sdshdr16 和 sdshdr32 这两个类型它们的定义分别如下
struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len;uint16_t alloc; unsigned char flags; char buf[];
};struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len;uint32_t alloc; unsigned char flags;char buf[];
};
可以看到 sdshdr16 类型的 len 和 alloc 的数据类型都是 uint16_t表示字符数组长度和分配空间大小不能超过 2 的 16 次方。 sdshdr32 则都是 uint32_t表示表示字符数组长度和分配空间大小不能超过 2 的 32 次方。 之所以 SDS 设计不同类型的结构体是为了能灵活保存不同大小的字符串从而有效节省内存空间。比如在保存小字符串时结构头占用空间也比较少。
除了设计不同类型的结构体Redis 在编程上还使用了专门的编译优化来节省内存空间即在 struct 声明了 __attribute__ ((packed)) 它的作用是告诉编译器取消结构体在编译过程中的优化对齐按照实际占用字节数进行对齐。
比如sdshdr16 类型的 SDS默认情况下编译器会按照 16 字节对齐的方式给变量分配内存这意味着即使一个变量的大小不到 16 个字节编译器也会给它分配 16 个字节。
举个例子假设下面这个结构体它有两个成员变量类型分别是 char 和 int如下所示
#include stdio.hstruct test1 {char a;int b;} test1;int main() {printf(%lu\n, sizeof(test1));return 0;
}
大家猜猜这个结构体大小是多少我先直接说答案这个结构体大小计算出来是 8。
这是因为默认情况下编译器是使用「字节对齐」的方式分配内存虽然 char 类型只占一个字节但是由于成员变量里有 int 类型它占用了 4 个字节所以在成员变量为 char 类型分配内存时会分配 4 个字节其中这多余的 3 个字节是为了字节对齐而分配的相当于有 3 个字节被浪费掉了。
如果不想编译器使用字节对齐的方式进行分配内存可以采用了 __attribute__ ((packed)) 属性定义结构体这样一来结构体实际占用多少内存空间编译器就分配多少空间。
比如我用 __attribute__ ((packed)) 属性定义下面的结构体 同样包含 char 和 int 两个类型的成员变量代码如下所示
#include stdio.hstruct __attribute__((packed)) test2 {char a;int b;} test2;int main() {printf(%lu\n, sizeof(test2));return 0;
}
这时打印的结果是 51 个字节 char 4 字节 int。
可以看得出这是按照实际占用字节数进行分配内存的这样可以节省内存空间。
链表
Redis 的 List 对象的底层实现之一就是链表。链表节点的数据结构如下
typedef struct listNode {//前置节点struct listNode *prev;//后置节点struct listNode *next;//节点的值void *value;
}
从定义可以看出这是一个双向链表 但是Redis 在 listNode 结构体基础上又封装了 list 这个数据结构如下
typedef struct list {//链表头节点listNode *head;//链表尾节点listNode *tail;//节点值复制函数void *(*dup)(void *ptr);//节点值释放函数void (*free)(void *ptr);//节点值比较函数int (*match)(void *ptr, void *key);//链表节点数量unsigned long len;
} list;list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数。
举个例子下面是由 list 结构和 3 个 listNode 结构组成的链表。 链表的优势与缺陷
Redis 的链表实现优点如下 listNode 链表节点的结构里带有 prev 和 next 指针获取某个节点的前置节点或后置节点的时间复杂度只需O(1)而且这两个指针都可以指向 NULL所以链表是无环链表 list 结构因为提供了表头指针 head 和表尾节点 tail所以获取链表的表头节点和表尾节点的时间复杂度只需O(1) list 结构因为提供了链表节点数量 len所以获取链表中的节点数量的时间复杂度只需O(1) listNode 链表节使用 void* 指针保存节点值并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数因此链表节点可以保存各种不同类型的值 链表的缺陷也是有的 链表每个节点之间的内存都是不连续的意味着无法很好利用 CPU 缓存。能很好利用 CPU 缓存的数据结构就是数组因为数组的内存是连续的这样就可以充分利用 CPU 缓存来加速访问。 还有一点保存一个链表节点的值都需要一个链表节点结构头的分配内存开销较大。 然后在Redis 5.0 设计了新的数据结构 listpack来替代List 对象的底层数据结构。
压缩列表
压缩列表的最大特点就是它被设计成一种内存紧凑型的数据结构占用一块连续的内存空间不仅可以利用 CPU 缓存而且会针对不同长度的数据进行相应编码这种方法可以有效地节省内存开销。但是压缩列表的缺陷也是有的 不能保存过多的元素否则查询效率就会降低 新增或修改某个元素时压缩列表占用的内存空间需要重新分配甚至可能引发连锁更新的问题。 因此Redis 对象List 对象、Hash 对象、Zset 对象包含的元素数量较少或者元素值不大的情况才会使用压缩列表作为底层数据结构。
压缩列表结构设计
压缩列表是 Redis 为了节约内存而开发的它是由连续内存块组成的顺序型数据结构有点类似于数组。 压缩列表在表头有三个字段 zlbytes记录整个压缩列表占用对内存字节数 zltail记录压缩列表「尾部」节点距离起始地址由多少字节也就是列表尾的偏移量 zllen记录压缩列表包含的节点数量 zlend标记压缩列表的结束点固定值 0xFF十进制255。 在压缩列表中如果我们要查找定位第一个元素和最后一个元素可以通过表头三个字段的长度直接定位复杂度是 O(1)。而查找其他元素时就没有这么高效了只能逐个查找此时的复杂度就是 O(N) 了因此压缩列表不适合保存过多的元素。
另外压缩列表节点entry的构成如下 压缩列表节点包含三部分内容 prevlen记录了「前一个节点」的长度 encoding记录了当前节点实际数据的类型以及长度 data记录了当前节点的实际数据 当我们往压缩列表中插入数据时压缩列表就会根据数据是字符串还是整数以及数据的大小会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息这种根据数据大小和类型进行不同的空间大小分配的设计思想正是 Redis 为了节省内存而采用的。
分别说下prevlen 和 encoding 是如何根据数据的大小和类型来进行不同的空间大小分配。
压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」而且 prevlen 属性的空间大小跟前一个节点长度值有关比如 如果前一个节点的长度小于 254 字节那么 prevlen 属性需要用 1 字节的空间来保存这个长度值 如果前一个节点的长度大于等于 254 字节那么 prevlen 属性需要用 5 字节的空间来保存这个长度值 encoding 属性的空间大小跟数据是字符串还是整数以及字符串的长度有关 如果当前节点的数据是整数则 encoding 会使用 1 字节的空间进行编码。 如果当前节点的数据是字符串根据字符串的长度大小encoding 会使用 1 字节/2字节/5字节的空间进行编码。 连锁更新
压缩列表除了查找复杂度高的问题还有一个问题。
压缩列表新增某个元素或修改某个元素时如果空间不不够压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时可能会导致后续元素的 prevlen 占用空间都发生变化从而引起「连锁更新」问题导致每个元素的空间都要重新分配造成访问压缩列表性能的下降。
前面提到压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配 如果前一个节点的长度小于 254 字节那么 prevlen 属性需要用 1 字节的空间来保存这个长度值 如果前一个节点的长度大于等于 254 字节那么 prevlen 属性需要用 5 字节的空间来保存这个长度值 现在假设一个压缩列表中有多个连续的、长度在 250253 之间的节点如下图 因为这些节点长度值小于 254 字节所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。
这时如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点即新节点将成为 e1 的前置节点如下图 因为 e1 节点的 prevlen 属性只有 1 个字节大小无法保存新节点的长度此时就需要对压缩列表的空间重分配操作并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。
多米诺牌的效应就此开始。 e1 原本的长度在 250253 之间因为刚才的扩展空间此时 e1 的长度就大于等于 254 了因此原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。
正如扩展 e1 引发了对 e2 扩展一样扩展 e2 也会引发对 e3 的扩展而扩展 e3 又会引发对 e4 的扩展…. 一直持续到结尾。
这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」就像多米诺牌的效应一样第一张牌倒下了推动了第二张牌倒下第二张牌倒下又推动了第三张牌倒下….
压缩列表的缺陷
空间扩展操作也就是重新分配内存因此连锁更新一旦发生就会导致压缩列表占用的内存空间要多次重新分配这就会直接影响到压缩列表的访问性能。
所以说虽然压缩列表紧凑型的内存布局能节省内存开销但是如果保存的元素数量增加了或是元素变大了会导致内存重新分配最糟糕的是会有「连锁更新」的问题。
因此压缩列表只会用于保存的节点数量不多的场景只要节点数量足够小即使发生连锁更新也是能接受的。
虽说如此Redis 针对压缩列表在设计上的不足在后来的版本中新增设计了两种数据结构quicklistRedis 3.2 引入 和 listpackRedis 5.0 引入。这两种数据结构的设计目标就是尽可能地保持压缩列表节省内存的优势同时解决压缩列表的「连锁更新」的问题。
哈希表
redis中哈希键的底层实现之一就是字典实际与C语言中的哈希表一样都是一个键与一个值进行关联并称为键值对。由于redis使用的C语言没有这种数据结构所以redis自己构建了字典实现。在我看来在redis中的字典与哈希表的关系就是字典就是对哈希表的结构的一个封装而已只是为了方便使用。下面会讲到二者的关系。
优缺点 哈希表优点在于它能以 O(1) 的复杂度快速查询数据。怎么做到的呢将 key 通过 Hash 函数的计算就能定位数据在表中的位置因为哈希表实际上是数组所以可以通过索引值快速查询到数据。 但是存在的风险也是有在哈希表大小固定的情况下随着数据不断增多那么哈希冲突的可能性也会越高。Redis 采用了「链式哈希」来解决哈希冲突。 哈希表结构设计
字典的定义
typedef struct dict{//类型特定的函数dictType * type;//私有数据void * private;//哈希表dictht ht[2];//rehash的索引int rehashidx;
} dict;哈希表的数据结构如下
typedef struct dictht {//哈希表数组dictEntry **table;//哈希表大小unsigned long size; //哈希表大小掩码用于计算索引值unsigned long sizemask;//该哈希表已有的节点数量unsigned long used;
} dictht;
其中哈希表节点的数据结构如下
typedef struct dictEntry {//键值对中的键void *key;//键值对中的值union {void *val;uint64_t u64;int64_t s64;double d;} v;//指向下一个哈希表节点形成链表struct dictEntry *next;
} dictEntry;dictEntry 结构里不仅包含指向键和值的指针还包含了指向下一个哈希表节点的指针这个指针可以将多个哈希值相同的键值对链接起来以此来解决哈希冲突的问题这就是链式哈希。
另外这里还跟你提一下dictEntry 结构里键值对中的值是一个「联合体 v」定义的因此键值对中的值可以是一个指向实际值的指针或者是一个无符号的 64 位整数或有符号的 64 位整数或double 类的值。这么做的好处是可以节省内存空间因为当「值」是整数或浮点数时就可以将值的数据内嵌在 dictEntry 结构里无需再用一个指针指向实际的值从而节省了内存空间。
哈希表的结构图 关于什么是哈希冲突和解决方案 可以查看我之前的文章解决哈希冲突的方案不过链式哈希局限性也很明显随着链表长度的增加在查询这一位置上的数据的耗时就会增加毕竟链表的查询的时间复杂度是 O(n)。要想解决这一问题就需要进行 rehash也就是对哈希表的大小进行扩展。
哈希表扩容rehash 1. 为字典的 ht[1] 哈希表分配空间ht[1] 大小为 ht[0] 的 2^n 2. 将 ht[0] 中的键值对reahash到 ht[1] 中 3. 当 ht[0] 中的所有数据拷贝到 ht[1] 后释放 ht[0]; 4. 将 ht[1] 设置为 ht[0]并在 ht[1] 新创建一个空白哈希表为下一次rehash做准备 为了方便你理解我把 rehash 这三个过程画在了下面这张图 这个过程看起来简单但是其实第二步很有问题如果「哈希表 1 」的数据量非常大那么在迁移至「哈希表 2 」的时候因为会涉及大量的数据拷贝此时可能会对 Redis 造成阻塞无法服务其他请求
渐进式rehash
为了避免 rehash 在数据迁移过程中因拷贝数据的耗时影响 Redis 性能的情况所以 Redis 采用了渐进式 rehash也就是将数据的迁移的工作不再是一次性迁移完成而是分多次迁移。
渐进式 rehash 步骤如下 1. 为ht[1]分配空间让字典同时持有 ht[0] 与 ht[1] ; 2. 在字典中维持一个索引计数器变量rehashidx并将其设置为0表示rehash开始 3. rehash期间每次的修改程序除了指定的操作外还会将 ht[0] 在rehashidx上的所有键值rehash到 ht[1]rehash完成后rehashidx加一 4. 当 ht[0] 中所有的数据都rehash到 ht[1] 时rehashidx设置为-1rehash完成 这样就巧妙地把一次性大量数据迁移工作的开销分摊到了多次处理请求的过程中避免了一次性 rehash 的耗时操作。
在进行渐进式 rehash 的过程中会有两个哈希表所以在渐进式 rehash 进行期间哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。
比如查找一个 key 的值的话先会在「哈希表 1」 里面进行查找如果没找到就会继续到哈希表 2 里面进行找到。
另外在渐进式 rehash 进行期间新增一个 key-value 时会被保存到「哈希表 2 」里面而「哈希表 1」 则不再进行任何添加操作这样保证了「哈希表 1 」的 key-value 数量只会减少随着 rehash 操作的完成最终「哈希表 1 」就会变成空表。
触发 rehash 操作的条件 当负载因子大于等于 1 并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令也就是没有执行 RDB 快照或没有进行 AOF 重写的时候就会进行 rehash 操作。 当负载因子大于等于 5 时此时说明哈希冲突非常严重了不管有没有有在执行 RDB 快照或 AOF 重写都会强制进行 rehash 操作。 负载因子就是 由于篇章过于庞大就先写到这里至于整数集合跳表quicklistlistpack在redis 数据结构二再分析
