0 本节结构

• redis的基本架构
• redis中的常用数据类型
• redis中的底层数据结构
• 全局hash表
• 总结

1. 基本架构

• 访问框架
• 网络访问框架
• 操作模块
• 索引模块
• 存储模块
• 分配器
• 持久化
• 高可用集群支撑模块
• 高可用扩展集群支撑模块

2. redis中常用的数据类型

• 字符串(String)
• 列表(List)
• 散列(Hash)
• 有序集合(Sorted Set)
• 集合(Set)
• 比特位数组(Bitmaps)
• HperLogLogs

3.redis中的底层数据结构

• 字符串(String) 底层数据结构对应 简单动态字符串
• 列表(List) 底层数据结构 由双向链表,压缩列表数据结构实现
• 散列(Hash)底层数据结构由 压缩列表,哈希表数据结构实现
• 有序集合(Sorted Set)底层数据结构由压缩列表,跳表数据结构实现
• 集合(Set)底层数据结构由 哈希表,整数数组数据结构实现

对应关系如下

集合类型的底层数据结构主要有5种: 整数数组,双向链表,哈希表,压缩列表,跳表

整数数组和双向链表都是顺序读写,通过数组下标或链表指针 逐个元素访问,操作复杂度为O(N),操作效率不高

压缩列表类似于数组 ,数组中每一个元素都对应保存一个数据,压缩列表表头有三个字段zlbytes,zltail,zllen 分别表示列表长度,列表尾的偏移量和列表中的entry个数,压缩列表在表尾还有一个zlend 表示列表结束,所以说,再查找第一个元素和最后一个元素时,复杂度是O(1),其他的操作就是O(n)了

跳表只是在链表的基础上,增加了多级索引,通过索引位置的跳转,实现数据的快速定位

这几种类型的时间复杂度如下:

4. 全局hash表

为了实现从键到值的快速访问,redis使用了一个哈希表来保存所有键值对

知识点

0. redis的全局哈希表由多个哈希表结构构成的,每个哈希表称为一个数据库,默认有16个
1. 每个数据库都使用字典来实现键值对的存储
2. 如果冲突太多,redis会进行 渐进式rehash
3. 渐进式rehash过程:

redis默认有2个全局哈希表: 哈希表1和哈希表2,一开始,当插入数据时,默认使用哈希表1,
  此时哈希表2并没有被分配空间,随着数据增多,rehash过程分为三步

1.给哈希表2分配更大的空间,当前哈希表1大小的两倍

2.把哈希表1中的数据重新映射并拷贝到哈希表2中

3. 释放哈希表1的空间

为了避免一次性把哈希表1中的数据都迁移完,会造成redis线程阻塞,无法提供其他请求,所以采用了 渐进式rehash,简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求 时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的entries,如下图

5.小结:

1. 针对单元素操作,如 Hash 类型的 HGET、HSET 和 HDEL，Set 类型的 SADD、SREM、SRANDMEMBER 等。这些操作的复杂度由集合采用的数据结构决定，例如，HGET、HSET 和 HDEL 是对哈希表做操 作，所以它们的复杂度都是 O(1)；Set 类型用哈希表作为底层数据结构时，它的 SADD、 SREM、SRANDMEMBER 复杂度也是 O(1)。如果对多个元素进行操作的话,如 HMGET和HMSET,和SADD 时,复杂度由O(1)变成O(M)了

2. 针对范围操作,如 Hash类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据，比如 List类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)，比较耗时，我们应该尽量避免。在redis 2.8版本后 可以使用 HSCAN，SSCAN 和ZSCAN 命令来代替范围查询的命令,这些命令是渐进式遍历,每次只返回有限数量的数据,不会导致redis阻塞

3. 针对统计操作 ,如 LLEN 和 SCARD 这类复杂度为O(1)

4. 例外情况 如压缩列表和双向链表都会记录表头和表尾的偏移量。这样一来，对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说，它们是在列表的头尾增删元素，这就可以通过偏移量直接定位，所以它们的复杂度也只有 O(1)，可以实现快速操作。