Redis核心技术笔记01-02

01 KV数据库结构

可以存哪些数据

对于键值数据库来说，基本的数据模型是key-value模型。我们对于KV数据库选项时，一个重要的考虑因素是它支持的value类型：

• Memcached仅支持string

• Redis支持String、哈希表、列表、集合等

  数据操作

• PUT/SET：新写入或更新一个kv对
• GET：根据key获取对应value
• DELETE：根据key删除整个kv对

• SACN：根据一段key范围返回相应value

  数据库内部结构

• 访问框架
• 索引模块：定位键值对位置
• 操作模块

• 存储模块

  访问框架

• 函数库调用

• 网络框架：socket通信+请求解析（Memcached、Redis）

  索引模块

  Memcached 和 Redis 采用哈希表作为 key-value 索引原因：键值数据保存在内存中，内存的高性能随机访问特性可以很好地与哈希表 O(1) 的操作复杂度相匹配。

  操作模块

  不同操作的具体逻辑：

• GET/SCAN：根据 value 的存储位置返回 value
• PUT：为键值对分配内存空间

• DELETE：删除键值对，并释放相应的内存空间，这个过程由分配器完成。

  存储模块

  重启后快速提供服务：

• 内存分配器

• 持久化（AOF/RDB）

  Redis其他特性

• 高可用集群：主从、哨兵

• 高可扩展集群：数据分片

  02 底层数据结构

  底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

• 键和值结构组织：哈希表
• String：简单动态字符串(sds)
• List：双向链表(quicklist)，压缩列表(ziplist)
• hash：压缩列表，hash表
• zset(sortset)：hash表，跳表(skiplist)

• set：hash表，整数数组

  哈希表

  哈希表就是数组，数组的每个元素称为一个哈希桶，保存指向具体值的指针。

• 优点：可以用 O(1) 的时间复杂度来快速查找到键值对。

• 风险：哈希冲突和rehash可能带来的操作阻塞。

  哈希冲突

  两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。解决方法：链式哈希，即同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

  rehash

  增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。原因：哈希冲突链上的元素只能通过指针逐一查找再操作，会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。备注：Redis 默认使用了两个全局哈希表。执行过程：

• 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
• 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中(渐进式rehash)；

• 释放哈希表 1 的空间，哈希表 1留作下一次 rehash 扩容备用。

  渐进式rehash

  Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。

问题1：渐进式 rehash在处理拷贝的时候，还在处理客户端请求，这个时候怎么保证客户端请求的数据不会落在之前已经拷贝过了的索引上？或者说如果落在之前的索引上了怎么再回去拷贝到表2中？答：因为在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找，诸如此类。另外，在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

问题2：一次请求一个entrys，那后续如果再也没有请求来的时候，余下的entrys是怎么处理的呢？是就留在hash1中了还是有定时任务后台更新过去呢答案： 渐进式rehash执行时，除了根据键值对的操作来进行数据迁移，Redis本身还会有一个定时任务在执行rehash，如果没有键值对操作时，这个定时任务会周期性地（例如每100ms一次）搬移一些数据到新的哈希表中，这样可以缩短整个rehash的过程。

集合数据操作效率

一个集合类型的值，第一步是通过全局哈希表找到对应的哈希桶位置，第二步是在集合中再增删改查。

• 与集合的底层数据结构有关: 使用哈希表实现的集合，比使用链表实现的集合访问效率更高。

• 操作本身的执行特点有关：读写一个元素的操作要比读写所有元素的效率高

  底层数据结构

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

  整数数组和双向链表

  顺序读写，通过数组下标/链表指针逐个元素访问，操作复杂度基本是 O(N)，操作效率比较低；

  压缩列表

  压缩列表结构：

• 类似于一个数组，数组中的每一个元素都对应保存一个数据。
• 表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；
• 表尾还有一个 zlend，表示列表结束。查询效率：
• 第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)

• 其他元素只能逐个查找，此时的复杂度就是 O(N)

  跳表

  跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位查询效率：当数据量很大时，跳表的查找复杂度就是 O(logN)。

  不同操作的复杂度

  口诀：

• 单元素操作是基础；
• 范围操作非常耗时；
• 统计操作通常高效；

• 例外情况只有几个。

  单元素操作

  单元素操作，是指每一种集合类型对单个数据实现的增删改查操作。例如，Hash 类型的 HGET、HSET 和 HDEL，Set 类型的 SADD、SREM、SRANDMEMBER 等。这些操作的复杂度由集合采用的数据结构决定:

• HGET、HSET 和 HDEL 是对哈希表做操作，所以它们的复杂度都是 O(1)；
• Set 类型用哈希表作为底层数据结构时，它的 SADD、SREM、SRANDMEMBER 复杂度也是 O(1)

集合类型支持同时对多个元素进行增删改查，这些操作的复杂度，就是由单个元素操作复杂度和元素个数决定的。例如，HMSET 增加 M 个元素时，复杂度就从 O(1) 变成 O(M) 了。

范围操作

范围操作，是指集合类型中的遍历操作，可以返回集合中的所有数据比如 Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS，或者返回一个范围内的部分数据，比如 List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)，比较耗时，我们应该尽量避免。

SCAN 系列操作（包括 HSCAN，SSCAN 和 ZSCAN），这类操作实现了渐进式遍历，每次只返回有限数量的数据。

统计操作

集合类型对集合中所有元素个数的记录，例如 LLEN 和 SCARD。这类操作复杂度只有 O(1)，这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时，这些结构中专门记录了元素的个数统计，因此可以高效地完成相关操作。

例外情况

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

小结

1. 集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是 O(N)。这里，我的建议是：用其他命令来替代，例如可以用 SCAN 来代替，避免在 Redis 内部产生费时的全集合遍历操作。
2. List 类型的两种底层实现结构：双向链表和压缩列表的操作复杂度都是 O(N)。因此，我的建议是：因地制宜地使用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。问题：整数数组和压缩列表在查找时间复杂度方面并没有很大的优势，那为什么 Redis 还会把它们作为底层数据结构呢？答案：1、内存利用率，数组和压缩列表都是非常紧凑的数据结构，它比链表占用的内存要更少。Redis是内存数据库，大量数据存到内存中，此时需要做尽可能的优化，提高内存的利用率。2、数组对CPU高速缓存支持更友好，所以Redis在设计时，集合数据元素较少情况下，默认采用内存紧凑排列的方式存储，同时利用CPU高速缓存不会降低访问速度。当数据元素超过设定阈值后，避免查询时间复杂度太高，转为哈希和跳表数据结构存储，保证查询效率。