Redis

完全基于内存的数据库。

吊打磁盘数据库(多了将IO操作读取到内存里)、所以不会因为磁盘的IO速度限制。

高效的数据结构

常用的5种：String(SDS简单动态字符串)、list(双向链表、压缩列表)、hash(哈希表、压缩列表)、set(哈希表、整数集合)、zset（压缩列表、skiplist跳表）

总体来讲：redis就是一个全局的哈希表来保存所有键值对。而哈希表本质就是一个数组，保存的entry。这个转化的过程通过哈希函数、可能会发生哈希冲突，通过rehash扩容或者链表来解决。

单线程模式

redis的单线程指的是redis的网络IO以及键值对指令是由一个线程来执行的。
对于redis的持久化、集群数据同步、异步删除等都是其他线程执行。
基于内存操作，不涉及从磁盘读取到内存的IO操作，也就是CPU不是redis的瓶颈，而redis的瓶颈最有可能是机器内存大小或者网络带宽。
使用IO多路复用技术，通过事件分离器。

IO多路复用参考链接：https://blog.nowcoder.net/n/bb61909292c74781896c4c7cc6256ccd

底层数据结构

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缓存的数据结构就是数组）

CPU缓存参考：https://blog.nowcoder.net/n/f6c3f2facf2b41f6989fd93580db7294

压缩列表

压缩列表节点：

prevlen（记录前一个节点的长度）；prevlen属性空间大小跟前一个节点长度值有关；
encoding（记录当前节点的实际数据的类型以及长度）；encoding属性空间大小根据数据是字符串还是证书、以及字符串长度有关；
data（记录当前节点的实际数据）

适用场景：用于保存节点数量不多的场景；

优点：

占用一块连续的内存块组成的顺序型数据结构，可以很好的利用CPU缓存；
节省内存：对于不同数据会使用不同空间大小的prevlen和encoding两个元素保存信息；

缺点：

查找中间数据节点的时间复杂度为O（n）；
连锁更新：压缩列表新增某个元素或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续的元素的prevlen占用空间都发生变化，从而引起连锁更新问题，导致每个元素的空间都需要重新分配，造成访问压缩列表性能下降

压缩列表和双向链表总结

少数据使用压缩列表（可以很好的利用CPU缓存、节省内存（prevlen、encoding）同时可以避免连锁更新）、多数据的时候变化为双向链表

哈希表

参考hashmap：https://blog.nowcoder.net/n/faeb92831c4d4d02a62edb5d0fb2cf8a

渐进式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里面修改数值即可。

Redis底层数据结构