Redis

  • 完全基于内存的数据库
吊打磁盘数据库(多了将IO操作读取到内存里)、所以不会因为磁盘的IO速度限制。
  • 高效的数据结构
常用的5种:String(SDS简单动态字符串)、list(双向链表、压缩列表)、hash(哈希表、压缩列表)、set(哈希表、整数集合)、zset(压缩列表、skiplist跳表)
总体来讲:redis就是一个全局的哈希表来保存所有键值对。而哈希表本质就是一个数组,保存的entry。这个转化的过程通过哈希函数、可能会发生哈希冲突,通过rehash扩容或者链表来解决
  • 单线程模式
  1. redis的单线程指的是redis的网络IO以及键值对指令是由一个线程来执行的
  2. 对于redis的持久化、集群数据同步、异步删除等都是其他线程执行。
  3. 基于内存操作,不涉及从磁盘读取到内存的IO操作,也就是CPU不是redis的瓶颈,而redis的瓶颈最有可能是机器内存大小或者网络带宽。
  4. 使用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[](字符数组):
  • 字符数组,用于保存实际数据;不仅仅可以保存字符串、也可以保存二进制数据;

优点:

  1. 获取字符串长度时间复杂度为O(1)
  2. 二进制安全(SDS使用len变量记录字符串长度,不需要字符“\0”表示字符串结尾;所以可以存储任意格式的二进制数据、char *只能存储文本数据);
  3. 不会发生缓存区溢出;(alloc实现自动扩展SDS所需要的空间大小)
  4. 节省内存空间(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);

与压缩列表的区别:

  1. 压缩列表会造成连锁更新,因为每个元素的内存大小都不是固定的,根据prevlen和encoding决定,当一个节点的encoding改变,后续节点的prevlen也会跟着改变;
  2. 整数集合每个元素内存大小都会固定的encoding(int8_t、int16_t、int32_t、int64_t)、例如:一个int16_t的内存空间包含两个int8_t的内存空间,每个内存空间大小只存储一个元素;并不像压缩列表每个元素内存空间不固定而且还紧挨着。

跳表

为什么使用跳表而不是红黑树?

  • 方便区间查询(可以引申一下B+树);
  • 实现灵活、简单,通过改变索引构造策略,有效平衡执行效率和内存消耗

概念:

  • 采用二分的思想、向上建立冗余层,进而插入、删除、查找的时间复杂度均为O(logn)
插入的时候,如果不更新索引,极端情况下可能退化成链表;

解决:

  • 通过随机函数维护平衡性,也就是插入数据的同时也插入到部分的索引层中;
  • 随机函数生成了值K,将这个节点添加到第一级到第K级这K级索引中。

拓展:

  1. 压缩列表达到默认阈值128会转化为skiplist。这里跟hashmap的链表到达阈值8会转化为红黑树很像。
  2. 如何动态修改阈值:在redis.windows.conf里面修改数值即可。