Redis
- 完全基于内存的数据库。
- 高效的数据结构
总体来讲:redis就是一个全局的哈希表来保存所有键值对。而哈希表本质就是一个数组,保存的entry。这个转化的过程通过哈希函数、可能会发生哈希冲突,通过rehash扩容或者链表来解决。
- 单线程模式
- redis的单线程指的是redis的网络IO以及键值对指令是由一个线程来执行的。
- 对于redis的持久化、集群数据同步、异步删除等都是其他线程执行。
- 基于内存操作,不涉及从磁盘读取到内存的IO操作,也就是CPU不是redis的瓶颈,而redis的瓶颈最有可能是机器内存大小或者网络带宽。
- 使用IO多路复用技术,通过事件分离器。
底层数据结构
SDS
介绍:redis并没有直接使用c语言的char *字符数组存储,而是自己封装一个简单动态字符串;
SDS的数据结构:len、alloc、flags、buf[]
len(字符串长度)- 记录字符串长度,直接返回变量即可获得,时间复杂度为O(1);
- c语言获取字符串长度通过strlen函数,遍历字符数组遇到“\0”停止,时间复杂度为O(n);
alloc(分配的空间长度):
- 分配给字符数组的空间长度;通过alloc-len计算出剩余的空间大小,自动将SDS的空间拓展到执行修改所需的大小;
- c语言需要自己预先分配足够的内存,让其执行;
flags(sds类型):
- 用于表示不同的SDS的类型(sdshdr5,sdshdr8,sdshdr16,sdshdr32,sdshdr64);区别在于存储的len、alloc的数据类型不同;
buf[](字符数组):
- 字符数组,用于保存实际数据;不仅仅可以保存字符串、也可以保存二进制数据;
优点:
- 获取字符串长度时间复杂度为O(1);
- 二进制安全(SDS使用len变量记录字符串长度,不需要字符“\0”表示字符串结尾;所以可以存储任意格式的二进制数据、char *只能存储文本数据);
- 不会发生缓存区溢出;(alloc实现自动扩展SDS所需要的空间大小)
- 节省内存空间(SDS使用flags、保存不同大小的字符串,有效的节省空间;使用专门的编译器取消结构体在编译的过程中的优化对齐,而是按照实际占用字节数进行对齐)
双向链表
链表节点带有prev和next指针、len(节点的数量);
优点:
获取某个节点的前驱、后置节点,获取链表的头节点和尾节点,获取链表中的节点数量的时间复杂度都为O(1);
缺点:
- 每个节点需要保存前驱、后置,内存开销较大
- 链表的每个节点的内存都是不连续的,意味着无法很好的利用CPU缓存;(能很好利用CPU缓存的数据结构就是数组)
压缩列表
压缩列表节点:
- prevlen(记录前一个节点的长度);prevlen属性空间大小跟前一个节点长度值有关;
- encoding(记录当前节点的实际数据的类型以及长度);encoding属性空间大小根据数据是字符串还是证书、以及字符串长度有关;
- data(记录当前节点的实际数据)
适用场景:用于保存节点数量不多的场景;
优点:
- 占用一块连续的内存块组成的顺序型数据结构,可以很好的利用CPU缓存;
- 节省内存:对于不同数据会使用不同空间大小的prevlen和encoding两个元素保存信息;
缺点:
- 查找中间数据节点的时间复杂度为O(n);
- 连锁更新:压缩列表新增某个元素或修改某个元素时,如果空间不够,压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时,可能会导致后续的元素的prevlen占用空间都发生变化,从而引起连锁更新问题,导致每个元素的空间都需要重新分配,造成访问压缩列表性能下降
压缩列表和双向链表总结
少数据使用压缩列表(可以很好的利用CPU缓存、节省内存(prevlen、encoding)同时可以避免连锁更新)、多数据的时候变化为双向链表
哈希表
渐进式rehash(扩容)
在数据迁移的时候不是一次性将大量数据拷贝进入新的hash表,而是在rehash期间,每次哈希表元素进行新增、删除、查找或者更新操作操作时,redis除了会执行对应的操作之外,还会顺序将旧的hash表中的索引位置上所有的key - value迁移到新的哈希表上;会在最终的某个时间完成哈希表的rehash操作;
rehash触发的条件
负载因子 = 哈希表已保存节点数量 / 哈希表大小;
- 当负载因子 >= 1,并且redis没有执行RDB快照或者AOF重写的时候,就会进行rehash操作;
- 当负载因子 >= 5,说明哈希冲突已经非常严重了,不管有没有在执行RDB快照或者AOF重写都会强制进行rehash操作;
整数集合
存储结构:
- encoding(编码方式)
- length(集合包含的元素数量)
- contents[](元素数组):会根据不同的encoding属性的值,保存不同的类型;默认为int8_t
整数集合的升级
如果加入到整数集合(int8_t)的新元素的数据类型是(int16_t),需要对整数集合先进行升级,按照元素类型(int16_t)拓展contents数组空间的大小,使得升级后的数组每个元素的类型都为(int16_t);在原有的数组上进行拓展空间
好处:
- 节省内存资源,需要更大内存空间类型才进行升级,默认使用int8_t类型;
- 不支持降级(整数集合(int8_t)、添加元素int16_t类型后删除,数组类型不会再降级为int8_t);
与压缩列表的区别:
- 压缩列表会造成连锁更新,因为每个元素的内存大小都不是固定的,根据prevlen和encoding决定,当一个节点的encoding改变,后续节点的prevlen也会跟着改变;
- 整数集合每个元素内存大小都会固定的encoding(int8_t、int16_t、int32_t、int64_t)、例如:一个int16_t的内存空间包含两个int8_t的内存空间,每个内存空间大小只存储一个元素;并不像压缩列表每个元素内存空间不固定而且还紧挨着。
跳表
为什么使用跳表而不是红黑树?
- 方便区间查询(可以引申一下B+树);
- 实现灵活、简单,通过改变索引构造策略,有效平衡执行效率和内存消耗。
概念:
- 采用二分的思想、向上建立冗余层,进而插入、删除、查找的时间复杂度均为O(logn);
插入的时候,如果不更新索引,极端情况下可能退化成链表;
解决:
- 通过随机函数维护平衡性,也就是插入数据的同时也插入到部分的索引层中;
- 随机函数生成了值K,将这个节点添加到第一级到第K级这K级索引中。
拓展:
- 压缩列表达到默认阈值128会转化为skiplist。这里跟hashmap的链表到达阈值8会转化为红黑树很像。
- 如何动态修改阈值:在redis.windows.conf里面修改数值即可。