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)，能够实现疾速操作。
小结
- 汇合类型的范畴操作，因为要遍历底层数据结构，复杂度通常是 O(N)。这里，我的倡议是：用其余命令来代替，例如能够用 SCAN 来代替，防止在 Redis 外部产生费时的全汇合遍历操作。
- List 类型的两种底层实现构造：双向链表和压缩列表的操作复杂度都是 O(N)。因而，我的倡议是：就地取材地应用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它次要用于 FIFO 队列场景，而不是作为一个能够随机读写的汇合。
问题：整数数组和压缩列表在查找时间复杂度方面并没有很大的劣势，那为什么 Redis 还会把它们作为底层数据结构呢？
答案：
1、内存利用率，数组和压缩列表都是十分紧凑的数据结构，它比链表占用的内存要更少。Redis 是内存数据库，大量数据存到内存中，此时须要做尽可能的优化，进步内存的利用率。
2、数组对 CPU 高速缓存反对更敌对，所以 Redis 在设计时，汇合数据元素较少状况下，默认采纳内存紧凑排列的形式存储，同时利用 CPU 高速缓存不会升高访问速度。当数据元素超过设定阈值后，防止查问工夫复杂度太高，转为哈希和跳表数据结构存储，保障查问效率。