范式

• 第一范式/1NF：确保原子性，存储的数据具备不可再分性。
• 第二范式/2NF：确保唯一性，避免冗余结构，每张表只描述一件业务，表中数据所有列的数据都必须依赖于主键，一张表只存储同一类型的数据，不能有任何一列数据与主键没有关系。
• 第三范式/3NF：确保独立性，方便表维护，表中每一列数据不能与主键之外的字段有直接关系。
• 巴斯-科德范式/BCNF/3.5NF：任何主属性不能对其它主键子集存在依赖，即联合主键中的某列值，不能与联合主键中的其他列存在依赖关系，是对第三范式的补充。
• 第四范式/4NF：消除多值依赖，即消除一个字段的值取决于多个字段才能确定的情况。
• 第五范式/5NF/完美范式：表中字段的数据之间不能存在连接依赖关系，直到表中的连接依赖都是主键所蕴含的。
• 反范式设计：范式级别升高，表的数量随之增多，查询数据需要频繁多次连表查询，性能开销逐渐增大。

语句执行

执行简单 select 语句

架构简单分层

• Server 层：建立连接、分析和执行 SQL。
• 存储引擎层：数据存储和提取。
  • MyISAM 和 innoDB 引擎区别
    • 磁盘文件存储：前者存储产生表结构、行数据、索引数据三个磁盘文件，后者只产生表结构、行数据及索引数据两个磁盘文件。
    • 前者只支持非聚簇索引，因为索引数据和行数据是分开文件存储的，后者支持聚簇和非聚簇索引。
    • 前者不支持事务，后者通过 undo log 实现事务机制。
    • 后者基于 redo log 实现故障恢复，前者只有 bin log，可能丢失数据。
    • 前者仅支持表锁，后者可以基于聚簇索引实现行锁，同时也兼容表锁。
    • 后者由于支持行锁和 MVCC 机制，性能远高于前者。
    • 后者设计了 Buffer Pool，内存利用率远超前者。
    • 前者支持空间索引，需要创建使用空间索引必须选择其为表引擎。
    • 前者可以直接返回全表数据量，但一旦加上条件则和后者没有区别。
    • 前者DELETE过的数据不会立即删除，而是先隐藏，后续定时或手动删除。

连接器

• TCP 三次握手建立连接，如果加密则还要 SSL 握手。
• 校验客户端用户名密码，即 mysql 库 user 表，读取用户权限，用于后续权限逻辑判断。
• 连接默认维护八小时，主动退出连接后 MySQL 将线程绑定会话信息清空，放入连接池以备后用，省去创建线程、分配栈空间等一系列动作，连接池一般默认 32 左右。
• 连接建立后通讯机制：半全工，同一时刻单方要么只能发送数据，要么只能接收数据。
• MySQL 的连接池维护的是工作线程，实现复用线程，客户端连接池维护工作线程，以达到复用数据库连接的目的，每个 SQL 操作都需要经过三次握手四次挥手的过程，消耗资源。

查询缓存

• 查看之前有无执行过同命令，命中则直接返回。
• MySQL8.0 版本已删除，频繁更新的表，每次更新都会清空查询缓存，导致命中率低、维护成本高、占用内存高、增加查询步骤，且该功能主要为 MYISAM 引擎准备，innoDB 缓冲区够用，项目有 Redis 维护业务缓存，因而该功能实则鸡肋。
• 移除的是该查询缓存，而非缓冲区 buffer pool。

解析 SQL

• 词法分析：识别关键字，构造 SQL 语法树。
• 语法分析：根据 SQL 语法树判断输入的 SQL 语句是否满足语法。

执行 SQL

• 预处理：检查表及字段是否存在，将*扩展到所有列。
• 优化器：确定执行计划，explain语句可模拟优化器查看执行计划。
  • 也可以通过FORCE INDEX关键字强制指定使用索引。
• 执行器：执行 SQL，存储引擎逐条返回结果给 SQL 接口，SQL 接口合并结果集并返回。

缓冲区管理

• 缓冲区读取数据：一次磁盘 I/O 读取 16KB 数据放入内存，利用局部性原理。
• 缓冲页分类
  • 空闲页：未被使用的内存缓冲页，由 free list 链表管理。
  • 数据页：被用于存放磁盘表数据、索引数据等内容的缓冲页，由 lru list 链表管理，同时负责在需要时淘汰已使用的内存页。
  • 变更页/标记页/脏页：页中数据发生过变更，但还未后台线程刷盘的缓冲页，由 flush list 链表管理，数据刷盘完成后移至数据页/lru list 链表。
• 淘汰缓冲页
  • young 区域：存放经常访问的热点数据页。
  • old 区域：存放刚从磁盘加载的数据页。
  • 预读数据页加入 old 区域头部，真正被访问并达到停留阈值后插入 young 区头部，一直未访问则被从 old 区移除。
  • 避免大查询扫表操作污染缓冲池，替换掉热点数据页。
• MySQL5.6 版本加入了缓冲池预热，避免了热点数据的重新洗入。

执行 update 语句

• 唯一性判断，是否涉及与满足唯一约束字段。
• 记录相应的 undo log，并写入 buffer pool，此时也会因为 undo log 修改记录 redo log。
• redo log 记录（prepare 状态）。
• 在缓冲区查找要操作的数据是否存在在内存中。
• 更新缓存的数据页，并标记为脏页，然后将记录写入 redo log。
• 更新语句执行完成后记录对应的 binlog。
• 事务提交，redo log 和 binlog 都需要提交，二者逻辑独立，可能出现一个成功一个失败导致日志逻辑不一致的情况，因而需要进行「两阶段提交」。

两阶段提交

• redo log 影响主库的数据，binlog 影响从库的数据，半成功将导致主从不一致。
• 将 redo log 的持久化分为 prepare 和 commit 两个阶段，中间穿插 binlog 的持久化。

异常分析

• 顺序扫描 redo log，如果遇到 prepare 状态的 redo log，就用该 redo log 的 XID 去 binlog 查询是否存在
  • 如果 binlog 中没有 XID（内部事务），说明 redo log 完成持久化，但 binlog 未完成，回滚事务。
  • 如果 binlog 中有 XID，说明二者都完成了持久化，正常提交事务。
• binlog 写成功作为事务提交成功的标志。

缺陷

• 磁盘 I/O 次数多，每次事务提交都会刷盘两次。
• 锁竞争激烈，多事务的情况下，需要保证两个日志的提交顺序一致。
• 解决方案：组提交，同时每个阶段都有一个队列，锁针对队列，而不锁住提交事务的整个过程，减小粒度，提升效率。
  • flush 阶段组提交 redo log，sync 阶段对 binlog 执行组提交，commit 阶段依次设置 redo log 组状态为 commit。

事务

特性

• 原子性
  • 事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间环节，若执行出错，会回滚至事务开始前的状态。
  • 通过 undo log 保证。
• 一致性
  • 事务操作前后，数据库保持一致性状态，如转账前后总额始终相同。
  • 原子性、隔离性和持久性都是为了确保（内部）一致性。
• 隔离性
  • 每个事务都有完整的隔离空间，并发事务间不会互相干扰。
  • 通过 MVCC 或锁机制保证。
• 持久性
  • 事务结束后，对数据的修改是永久的，不会因为系统故障等丢失。
  • 通过 redo log 保证。

隔离性

• 并发问题
  • 脏读
    • 一个事务读到了另一个未提交事务修改过的数据。
  • 不可重复读
    • 一个事务内多次读取同一个数据，出现前后不一致的情况。
  • 幻读
    • 一个事务内多次查询符合某个查询条件的记录数量，出现前后记录数量不一致的情况。
• 隔离级别
  • 读未提交
    • 事务还没提交时，其它事务能够看到它做的变更。
  • 读已提交
    • 事务提交后，其它事务才能看到它做的变更。
    • 不可能发生脏读。
  • 可重复读
    • InnoDB 引擎默认隔离级别
    • 事务执行的过程中，看到的数据始终是一致的。
    • 不可能发生脏读和不可重复读。
    • 解决幻读问题（只是很大程度上避免了）
      • 快照读（普通 select 语句）：MVCC（多版本并发控制）。
      • 当前读（select…for update、insert、delete、update 等语句）：next-key lock（记录锁+间隙锁）。
  • 可串行化
    • 给记录加上读写锁，遇到读写冲突时候后访问的事务必须等待前一个事务执行完成，相当于强制事务排序，性能很低。
    • 不可能发生脏读、不可重复读和幻读。
  • 具体实现
    • 读未提交直接读取最新数据即可，可串行化则通过加锁的方式避免并行访问冲突。
    • 读已提交和可重复读均根据 Read View 实现，前者在每个语句执行前都会重新生成 Read View，而后者整个事务期间则一直沿用启动事务时生成的 Read View。
    • Read View 主要字段
      • m_ids：创建 Read View 时，「活跃事务」的事务 id 列表。
      • min_trx_id：创建 Read View 时，「活跃事务」中的最小 id。
      • max_trx_id：创建 Read View 时，当前数据库应该给的下一个事务 id 值，即全局事务 id 最大值+1。
      • creator_trx_id：创建该 Read View 事务的 id。
    • 两个隐藏列
      • trx_id：记录修改该条记录的事务 id。
      • roll_pointer：每次改动记录，都会把旧版本记录写入 undo 日志，该列是指针，指向旧版本记录。
    • 事务 id 分配时机：并非 begin 事务时，而是第一次出现增删改时。每次重启后会把全局变量修改为 max_trx_id+256 确保递增。
  • MVCC
    • 通过版本链控制并发事务访问同一个记录。
    • 记录的trx_id < min_trx_id，可见
    • 记录的trx_id >= max_trx_id，不可见
    • min_trx_id <= trx_id < max_trx_id
      • trx_id 在 m_ids 列表，则生成该记录的事务依旧活跃，不可见，否则可见。
    • 同一事务内未提交的修改对自己可见。
  • 未解决的幻读特殊情况
    • A 事务查询不存在的记录，B 事务插入该条记录并立即提交，A 事务 update 该条事务（此时 trx_id 变成了 A 事务 id），A 事务再次查询，查出多一条记录，发生幻读。

日志

WAL 技术

WAL，即 Write-Ahead Logging 技术，MySQL 的写操作并不是立即写到磁盘上，而是先写日志，然后在合适的时间刷新到磁盘。

分类

• undo log（回滚日志）：innoDB 生成，实现了事务中的原子性，主要用于事务回滚和 MVCC。
• redo log（重做日志）：innoDB 生成，实现了事务中的持久性，主要用于故障恢复。
• bin log（归档日志）：Server 层生成，主要用于数据备份和主从复制。
• error log（错误日志）：记录 MySQL 启动、运行期间的报错、警告信息。
• slow log（慢查询日志）：记录所有执行时长超出long_query_time指定阈值的查询语句。
• relay log（中继日志）：主从集群中，从节点存储主节点 bin log 数据的日志。
• general log（常规日志）：主要记录 MySQL 收到的每一个查询或 SQL 命令。

Undo Log

设计思路

• 插入一条记录时，记录该条记录的主键值，回滚删去该主键值对应记录即可。
• 删除一条记录时，需要记录下该条记录的内容，回滚时再插入到表中。
• 更新一条记录时，需要记录下更新的列的旧值，回滚时再把这些列更新为旧值。

insert 格式

正如 insert 操作思路，记录主键所占用的空间和值，回滚时根据主键值删除记录即可。

delete 格式

删除一条记录的两个阶段

1. delete mask 阶段
   • 将 delete_flag 位设置为 1，但没有将记录移到垃圾链表，在这个删除对应的事务提交前，一直保持着这种中间状态。
   • 由于事务提交后就不需要回滚了，因而只需要针对此阶段考虑 undo log 设计即可。
2. purge 阶段 - 事务提交后，会有专门的线程负责将记录删除，包括从正常记录链表中移除、移至垃圾链表、修改页面相关信息等操作。
   相较于 insert 操作对应格式的 undo 日志，delete 操作对应的 undo 日志还需要记录被包含在索引中的列的相关信息，主要用于后续 2 阶段对记录实现真正删除。

update 格式

不更新主键

• 就地更新：更新前后的列所占用的空间大小相同，就可以直接原地更新。
• 先删除旧记录，再插入新记录：如果有任何一列在更新前后占用空间大小不同，那么就需要先把旧记录删除（此处是用户线程直接删除，而非二段式等待 purge 删除），然后在释放的空间或新申请的空间插入新的记录。
• 针对上述二者，设计了对应格式的 undo 日志，主要记录了更新的列的数量，以及<pos, old_len, old_value>三元组列表。除此之外，如果更新了索引相关列，也要记录下对应的信息。

更新主键

一旦更新主键，由于记录在聚簇索引中按照主键值连成了单向链表，这条记录的位置很可能发生较大改变。因而，针对这种情况，innoDB 的做法和删除类似，首先 delete mask 阶段（防止真正删除导致别的事务无法访问），然后再根据更新的值生成一条新记录，插入聚簇索引。

• 在进行 delete mask 阶段操作时，生成一条 delete 操作对应格式的 undo log。
• 在进行插入阶段操作时，生成一条 insert 操作对应格式的 undo log。
  也即涉及到更新主键操作时，一条语句会生成两条 undo log 与之对应。

更新二级索引

更新二级索引，就意味着也要对旧记录进行 delete mask 操作，然后根据更新后的值插入新的记录到二级索引中。

存储

每个事务都有自己的 undo 页面链表，避免事务间争抢 undo 页面链表指针，使之成为热点资源。一个事务中最多可以分配四个 undo 页面链表：

• 普通表的 insert undo 日志链表。
• 普通表的 update undo 日志链表。
• 临时表的 insert undo 日志链表。
• 临时表的 update undo 日志链表。

Redo Log

定义

• 物理日志，记录对某个数据页做的修改，比如对 XXX 表空间中的 YYY 数据页 ZZZ 偏移量的地方做了 AAA 更新。

配置与写入

• 事务提交时保证将 redo log 持久化到磁盘，无需等待脏页数据从 Buffer Pool 持久化到磁盘。
  • 写入 redo log 的方式是追加（循环），即顺序写，写入数据需要先找到位置再写到磁盘，即随机写，明显 redo log 顺序写的效率更高。
  • flush_log 对应参数为 0 时表示提交事务时将 redo log 留在 redo log buffer，不会触发写入磁盘（MySQL 进程崩溃即丢失上一秒数据），对应参数为 1 则直接持久化到磁盘，对应参数为 2 则持久化到操作系统文件缓存 Page Cache（操作系统崩溃断电则丢失上一秒数据）。
  • 上述参数的选择实则是性能和数据安全性的权衡，能容忍数据库崩溃丢失 1 秒数据的场景下设置参数为 0，可以通过减少 I/O 操作提高性能。
• redo log 采用循环写的方式，数据脏页写入磁盘后对应的 redo log 就可以被擦除，当写入位置指针追上擦除位置指针后，就意味着 redo log 已满，此时 MySQL 阻塞，不执行新的更新操作，而是将 Buffer Pool 中的数据脏页刷新到磁盘，然后擦除对应 redo log，再恢复正常运行。

和 Undo Log 辨析

• redo log 记录此次事务完成后状态，即更新后的值。
  • 事务提交后发生了崩溃，通过 redo log 恢复。
• undo log 记录此次事务开始前状态，即更新前的值。
  • 事务提交前发生了崩溃，通过 undo log 回滚。

BinLog

定义

Server 层负责生成，在 MySQL 完成涉及数据库表结构变更和表数据修改的操作后，会生成一条 binlog，事务提交时统一将 binlog 写入文件。
每次提交事务都会把 binlog 写到 page cache（速度快，不涉及磁盘 I/O），sync_binlog 参数控制是否持久化到磁盘，为 0 时表示交由操作系统决定什么时候持久化（默认，风险大，性能好），为 1 时是每次事务提交都持久化（性能差，但至多丢失一个事务），为 2 时累积指定事务数同步（兼顾，实际开发通常设置为 100~1000）。

格式

• STATEMENT：默认格式，记录每条修改数据的逻辑操作，但像now()这类函数调用会导致复制数据不一致。
• ROW：记录行数据修改结果，不会出现 STATEMENT 的函数问题，但像批量 update 语句会记录更新的行数对应条数的记录，占用空间明显大于 STATEMENT。
• MIXED：上述两种模式的综合，会根据不同情况选择不同模式。

和 Redo Log 辨析

• redo log 是 innoDB 存储引擎实现，而 BinLog 是 Server 层实现，所有引擎通用。
• redo log 循环写，binlog 追加写，不会清除覆盖以前的日志。
• redo log 用于故障恢复，binlog 用于备份恢复、主从复制。
  • binlog 是全量日志，所以如果遭遇删库跑路，只能用 binlog 恢复数据。
• redo log 是物理日志，记录在数据页做的修改，binlog 有三种类型。

主从复制

• 流程
  • 从库会创建专门的线程连接主库 log dump 线程，接受主库 binlog，写入 relay log。
  • 从库还会创建回放 binlog 的线程，读取 relay log，更新存储引擎中数据，实现主从数据一致性。
  • 然后主库负责写操作，从库负责读操作即可，这样写请求上锁后也不会影响读请求高效执行。
  • 只需要在从库建立查询相关索引即可，这样增删改操作都在主库不需要维护索引，保持高性能。
  • 只有读请求，不存在外部写请求的从库可以改为 MyISAM 引擎，基于 MyISAM 的索引查询数据不需要经过回表查询，速度更快。因为 MyISAM 每个索引独立，直接指向行数据地址，而非聚簇索引的索引键。
• 从库越多，主库也会需要创建更多 log dump 线程，对主库资源和网络带宽资源消耗明显。
• 复制方式
  • 同步复制：基本无法使用，性能很低，且任何一个数据库出现问题，都会影响业务。
  • 异步复制（默认）：一旦主库宕机，数据大概率发生丢失。
  • 半同步复制：MySQL5.7 新增，一部分从库复制成功并响应即返回，即使主库宕机，也能保证至少有一个从库有最新数据。
• 主从同步延迟
  • 二次查询，从库查不到去主库查，实现简单，兜底策略，但如果有故意发送查不到内容的请求，会影响性能浪费资源。
  • 强制将写之后需要立即读的操作都转移到主库，相当于绑定在一起，写死逻辑，较僵硬。
  • 关键业务读写都走主库，其余走从库，从业务角度分析，如用户注册就可以都走主库，避免登录时找不到用户。

索引

数据结构

• 二叉树
  • 存在退化成链表的可能性，会使时间复杂度降低到 O(n)。
  • 插入的元素越多，树的高度也增大，意味着需要磁盘 I/O 操作次数越多，严重影响查询性能。
  • 不能支持范围查询，也无法利用局部性原理。
• 自平衡二叉树（AVL 树）、红黑树
  • 插入的元素越多，树的高度也增大，意味着需要磁盘 I/O 操作次数越多，严重影响查询性能。
  • 树的节点越多，同时分叉数足够大时，N 叉树高度远小于二叉树。
  • 每个节点只存储一个数据，节点之间不连续，无法利用局部性原理。
• B 树
  • 每个节点都包含索引+记录，而记录的数据大小大概率远大于索引，因而读到需要的索引数据需要更多的 I/O 操作次数，如会加载很多非必要记录数据，而其实只需要索引数据，同时还占用了更多的资源。
  • 支持范围查询，但需要使用中序遍历，涉及多节点磁盘 I/O，导致性能下降。
• B+树
  • 与 B 树的差异
    • 叶子节点才存放索引+记录，非叶子节点只存放索引。
    • 所有索引都会在叶子节点出现，叶子节点之间构成有序链表。
  • 性能比较
    • 非叶子节点可以存放更多的索引，因而树高更小，查询底层数据的磁盘 I/O 次数更少。
    • B+树存在冗余节点，插入删除操作不太可能引发树的复杂变形，效率更高。
    • 叶子节点组成的链表对范围查找非常有优势，而数据库如 MySQL 经常存在大量范围检索。
• InnoDB 中的 B+树
  • 叶子节点采用双向链表连接，既能向左查询，也能向右。
  • 节点内容是数据页，每个数据页默认大小 16KB。
    • 假设每个数据页存放页信息及保留空间大小合计 1KB。
    • 假设一行记录数据大小 1k，那么单个叶子节点可以存放 $(16k-1k)/1k=15$ 条记录。
    • 假设主键类型是bigint，长度 8 字节，指针大小在 InnoDB 是 6 字节，所以非叶子节点可以存放 $15KB/(8+6)B=1097$ 指针。
    • 一棵高度为 2 的树，可以存放 $1097\ast 15=16455$ 条记录，一棵高度为 3 的树，可以存放 $1097\ast 1097\ast 15=18051135$ 条记录，也即三层即可满足两千万级别的数据存储。
      • 因此，也不建议单表超过两千万行，可能会导致 B+树层级更高，查询性能显著降低。

最左匹配原则

• 一直向右匹配直到遇到范围查询，其后的字段都无法用到联合索引。
• 索引下推
  • 针对select * from table where a > 1 and b = 2，在 MySQL5.6 前只能一个个回表对比 b 字段值。
  • 索引下推优化，可以在联合索引遍历过程中，直接过滤掉不满条件的记录，减少回表次数。
  • Explain 语句中 Extra 字段为Using index condition，说明使用了索引下推。
• 区分度 = $distinct(col)/count(\ast )$
• 索引的有序性
  • 建立联合索引选择适当的列，可以避免文件排序，提高查询效率。
  • 例：select * from order where status = 1 order by create_time asc

场景选择

优劣

• 优点
  • 提高查询速度。
• 缺点
  • 占用物理空间，数量越大，占用越多。
  • 创建和维护索引消耗时间，降低性能，在数据量大时尤为明显。
  • 降低表增删改效率，因为涉及到索引的动态维护。

场景

• 适用索引
  • 有唯一性限制的字段，如商品编码。
  • 常用WHERE查询条件的字段，优化的 B+树索引结构大幅提高范围查询效率。
  • 常用GROUP BY和ORDER BY的字段，借助索引避免排序，提高效率。
  • 需要执行 count 函数时，尽量在数据表上建立二级索引，扫描 key_len 最小的二级索引往往效率比主键索引高一些，COUNT(字段)效率最低，如果一定要统计该字段不为NULL的记录数，建议在这个字段建立二级索引。
  • 频繁连表查询时涉及的主外键字段。
• 不适用索引
  • 经常更新的字段，如余额等，经常修改意味着频繁重建索引，严重影响数据库性能。
  • 存在大量重复数据的字段，如性别等。
  • 经常带函数查询/参与计算的字段。
  • 完全无序的字段，尤其是不推荐建立为主键索引。

前缀索引

定义

使用某个字段中的前几个字符建立索引，减小索引字段大小，增加一个数据页中存储的索引数量，有效提高查询速度。

局限性

• ORDER BY和GROUP BY无法使用前缀索引。
• 无法将前缀索引作为覆盖索引，需要回表查询。

主键索引自增

• 如果使用自增主键，则插入新记录都是追加操作，不涉及数据的重新移动，效率高。
• 如果使用非自增主键，则插入新数据的位置是随机的，很有可能需要移动其它数据来插入新数据，涉及页分裂，性能受到影响。进而还可能造成碎片增多，空间利用率下降，浪费存储空间，同时影响之后查询的效率。

自适应哈希索引

hash 结构是所有数据类型中最快的，所以 innoDB 会对统计出的经常走索引查询的热点数据建立哈希索引，提升查询性能。

MRR 机制

MRR，即 Multi-Range Read，MySQL5.6 版本引入，主要针对辅助索引的回表查询，将查询出的 ID 先放到缓冲区，待全部索引检索完成或缓冲区数据达到阈值，对其中 ID 排序，根据顺序 ID 回表查询数据。减少了离散 I/O，将随机 I/O 转换成顺序 I/O，提高查询效率。

分库分表

分库

• 解决服务器资源受单机限制，无法支持高并发的问题，把请求分配到多台服务器上，降低服务器压力。
• 一般按照业务逻辑划分库，同时像活动库等特殊内容，可能会不定期高并发访问，为避免影响核心业务，即使和现有库有关联也会单独分库。
• 跨库后无法使用 JOIN 关键字等联表查询。
  • 适当冗余字段。
  • 业务层实现关联，但通常逻辑更加复杂，效率也不一定高。
• 事务完整性，涉及分布式事务。

分表

• 解决单张表数据量过大的问题。
• 垂直分表
  • 剥离不常用的大字段，如用户表移除联系地址、个人简介，保留用户名和性别等。
  • 额外增加关联表操作即可。
• 水平分表
  • 表内记录数过多，水平拆分为多张表。
  • 分页、计数和排序操作：业务层实现，计数可以缓存，增删改时更新计数。
  • 路由问题
    • HASH：选择表某一列，进行 Hash 运算并取模，将记录分到不同子表。
      • ✔️ 数据分布均匀。
      • ❌ 增加记录时需要一定计算，增加子表时非常复杂，参考 hashmap 扩容。
    • 范围路由：依照时间、地址等划分即可。
      • ✔️ 容易扩展，增加子表操作容易。
      • ❌ 数据分布不均匀。
    • 路由表：用一张表单独记录每个数据具体存放的子表。
      • ✔️ 灵活，迁移数据时修改路由表即可。
      • ❌ 每次需要多查询一次，损失性能，存缓存占据空间。
• 全局主键：自增步长设置、UUID 或分布式 ID。

Explain 语句

查看 SQL 的执行计划，分析语句和表结构的性能瓶颈，统计估算记录数（比执行 count 函数快很多，如搜索引擎返回的数量即是估测数量）。

字段解析

• id：SQL 执行顺序的标识，id 值越大越优先执行。
• table：显示这行数据对应的表，可能显示的是<derived数字>，即第几步的执行结果，派生表。
• select_type：每个 select 子句的类型。
  • SIMPLE：简单 select，不包括子查询和 union。
  • PRIMARY：当存在子查询时，最外层标记为PRIMARY。
  • SUBQUERY：子查询中的 select。
  • UNION：union 关键字之后的查询。
  • UNION RESULT：union 的结果。
  • DERIVED：FROM 子句中包含的子查询，派生表。
• type：MySQL 在表中找到所需行的方式，分析性能瓶颈的关键字段。
  • null：MySQL 在优化阶段分解查询语句，在执行阶段不需要访问表和索引，如直接获取建有索引字段的最值，直接从对应叶子节点获取即可。
  • system：const类型特例，在表只有一行记录时成立。
  • const：直接按主键或唯一键读取，只匹配一行数据，如SELECT * FROM student AS S WHERE id = 10
  • eq_ref：联表查询场景，且按主键或唯一键查询（只有一行满足）。
  • ref：满足索引的最左前缀规则，或索引不是主键/唯一索引。
  • ref_or_null：类似ref，额外搜索哪些行包含了 NULL 值。
  • index_merge：用到了多个索引，但性能不一定优于range。
  • range：索引范围查询，有限制的索引扫描。
  • index：全索引扫描，如索引是查询的覆盖索引，或按索引顺序来查找数据行，执行了全表扫描。
  • ALL：全表扫描，性能低谷。
• possible_keys：查询字段中存在且可能被用到的索引，但实际不一定会用于本次查询。
• key：实际用到的索引，如果为 null，则说明未使用到索引。
• key_len：索引使用的字节数，字段允许为 NULL 时大 1 字节，不损失精确性的情况下，越短性能越优。
• ref：查询关联，在 key 中查找值所用的列或常量。
• rows：MySQL 估测的扫描行数，数值越小越好。
• filtered：符合查询条件的数据百分比。
• extra：包含 MySQL 查询的详细信息。
  • using index for skip scan：MySQL8.0.13 版本推出，不满足最左匹配原则时，优化拼接成符合最左匹配原则。
    • 如SELECT f2, f3 FROM F WHERE f3 = 1，建有 f2、f3 的联合索引，按理应该用不上索引，需要全索引扫描（index），但如果 f2 的区分度很低（例如只有 1 和 2 两种值），可能优化为基于索引的范围查询（range），即优化为执行SELECT f2, f3 FROM F WHERE f2 = 1 and f3 = 1和SELECT f2, f3 FROM F WHERE f2 = 2 and f3 = 1。
    • 限制条件很多，如区分度低、必须联合索引、不能跨表等，因而此优化实际意义并不显著。
  • using temporary：创建了临时表来保存结果，以解决该查询。
  • using index condition：索引下推。
  • using index：仅使用索引树中的信息从表中检索列信息。
  • using filesort：无法利用索引完成排序操作时，不得不从内存或磁盘排序。
  • impossible where：WHERE 条件查询导致没有符合条件的行。
• 在 explain 语句后紧跟一条 SHOW WARNING 语句，可查看扩展信息。

局限

• 不考虑各种 cache 的情况。
• 部分信息是估算的，而非精确值。
• 只能解析 select 操作。其它操作要重写为 select 后查看执行计划。
• 不包含触发器、用户自定义函数、执行查询时优化工作等带来的影响。

锁

行级锁

• Record Lock 记录锁：仅锁定一条记录。
• Gap Lock 间隙锁：锁定一个范围，但不包含记录本身。
  • 间隙锁的意义在阻止区间被插入，所以是可以共存的，一个事务获取的间隙锁不会阻止另一个事务获取同一个范围的间隙锁，但包含了记录锁的 next-key 锁之间不能兼容。
• Next-Key Lock 记录锁+间隙锁：锁定一个范围，并锁定记录本身。
  • 唯一索引等值查询
    • 记录存在，退化为记录锁。
    • 记录不存在，退化为间隙锁。
  • 范围查询
    • 对每一个扫描到的索引加 next-key 锁，唯一索引在满足一些条件时退化为记录锁或间隙锁。
  • 全表扫描：对每一个索引加 next-key 锁，相当于锁住了整张表。

存储过程

• 一组完成特定功能的 SQL 语句集合，用一个指定名称存储起来，这个过程经过 MySQL 编译解析、执行优化后存储在数据库中。当以后需要时，只需根据名称调用即可。
• 阿里巴巴手册：禁止使用存储过程，难以调试和扩展，更没有移植性。
• 生成测试数据可以利用存储过程批量插入，比 for 循环更快。

NoSQL

Memcached

和 Redis 区别

• Redis 支持更丰富的数据类型，而 Memcached 只支持最简单的 key-value 类型。
• Redis 支持数据持久化，重启后可以把保存在磁盘的数据加载使用，而 Memcached 没有持久化功能。
• Redis 原生支持集群模式，Memcached 需要依靠客户端来向集群分片写入数据。
• Redis 支持发布订阅模型、Lua 脚本和事务等功能，Memcached 不支持。

Redis

数据结构

String

• 最基本的 key-value 结构，value 最多容纳数据长度 512M。
• 底层数据结构实现：int 和 SDS（简单动态字符串）。
  • SDS 相比 C 原生字符串的特点：
    • SDS 不仅可以保存文本数据，还可以保存二进制数据（图片、音视频、压缩文件等）。因为其使用 len 属性值而非空字符来判断字符串结束，并且所有 API 都会以处理二进制的方式处理存放在 buf[] 数组的数据。
    • SDS 获取字符串长度的时间复杂度是 O(1)，因为直接有 len 属性记录。
    • Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出。在拼接前会检查是否满足要求，如果空间不够会自动扩容。
  • 具体结构选择
    • 如果字符串对象保存的是整数值，且可以用 long 类型表示，会将字符串对象编码设置为 int 。
    • 如果字符串对象保存的是长度小于等于 32 字节的字符串，则使用 SDS 来保存，并将编码设置为专用于保存短字符串的优化编码方式 embstr 。
    • 如果字符串对象保存的是长度大于 32 字节的字符串，则使用 SDS 保存，并将其编码设置为 raw 。
    • redis2.+版本边界是 32 字节，后又扩至 39 字节，redis5.0 是 44 字节。
    • embstr 分配一块连续空间来保存 redisObject 和 SDS，调用分配和释放函数均只需一次（而 raw 需要两次且分配两块空间），且可以利用局部性原理，但该编码下的字符串对象实际上是只读的，执行任何修改时需要先转换为 raw 。
• 常用场景
  • 基本缓存，减轻数据库压力。
  • 计数器，Redis 单线程处理命令，执行命令过程是原子的。
  • 共享 Session 信息（分布式场景下）。

List

• 简单字符串列表，按照插入顺序排序，可以从头部或尾部添加元素。
• 底层数据结构实现：双向链表或压缩列表（元素少且每个元素长度短），Redis3.2 版本后全部改由 QuickList 实现。
  • QuickList 实际上是双向链表和压缩列表的结合，将紧凑存储的多段压缩列表通过双向指针串联起来。
  • QuickList 解决了压缩列表变更的时间复杂度高，且双向链表因为大量链表指针带来的空间消耗。
• 常用场景
  • 消息队列，但 List 不支持多个消费者消费同一个消息，且为实现重复消息判断，需要开发者自行为每个消息生成一个唯一 ID。

Hash

• 相比 String，更加适合存储对象。
• 底层数据结构实现：压缩列表或哈希表，Redis7.0 后改由 Listpack 结构实现。
  • Listpack 改进：压缩列表存在致命的性能瓶颈，即连续更新时，因而不能采用原有的保存前一个元素长度的方式。Listpack 记录了元素本身长度和特殊的结束符，用于支持分别向前后遍历。
• 常用场景
  • 存储对象，尤其是频繁变化的属性可以考虑抽出来用 Hash 存储。
  • 购物车，用户 ID 作为 key，商品 ID 作为 field，商品数量作为 value。

Set

• 无序并唯一的键值集合，存储顺序与插入先后无关。
• 底层数据结构实现：整数集合（元素个数小于阈值，默认 512）和哈希表。
• 潜在风险：Set 在完成差集、交集和并集计算时复杂度较高，数据量较大可能造成阻塞。
• 常用场景
  • 点赞/抽奖，保证用户只能点一个赞/中一次奖。
  • 共同关注，本质上是交集运算。

Zset

• 有序集合，每个元素相当于两个值组成，一个是排序值（可以重复），一个是元素值（不能重复）。
• 底层数据结构实现：压缩列表或跳表，Redis7.0 后将压缩列表实现改为 Listpack 实现。
  • 跳表：通过增加多级索引，实现近似二分查找的效果（空间换时间的典例）。
    • 固定每 n 个节点抽一个作为高一级索引，在多次插入后可能导致个别节点间有大量节点，退化为普通链表查找效率。
      • 解决方案：随机选择 n/2 个元素作为一级索引，n/4 个作为二级索引，依此类推。当元素数量足够大，抽取足够随机，也可以提高查询效率。每次插入新的元素时，先通过概率算法决定它应该插入到的最高索引级数。
    • 范围区间查找优于红黑树，只需要对数时间内找到区间起点，依次向后遍历即可。
• 常用场景
  • 排行榜，尤其是数据更新频繁或需要分页显示的场景。

BitMap

• 位图，String 类型的衍生。String 类型保存为二进制的字节数组，BitMap 就把字节数组的每个 bit 位利用，表示一个元素的二值状态。
• 常用场景
  • 非常适合海量数据二值统计，可以有效节省空间。如签到、打卡、判断登录态等。

HyperLogLog

• 提供非常节省空间的前提下，相对不精确（标准误算率 0.81%）的去重计数（基数统计，即统计一个集合中不重复的元素个数）。
• 需要精确结果建议使用 Set 或 Hash 类型。
• 底层数据结构实现：分桶统计+调和均值，好像有点复杂且不重要，略。
• 常用场景
  • 百万级网页 UV(Unique Visitor)计数。

GEO

• 主要用于存储地理位置信息并操作。
• 底层数据结构实现：直接使用了 Sorted Set(Zset)类型，实现了经纬度到元素权重分数的转换。
• 常用场景
  • 地理相关，打车、附近的人等。

Stream

• 专门为消息队列设计的类型，支持消息持久化、自动生成全局唯一 ID、消费组模式等。
• 底层数据结构实现：Listpack。
• 异常情况
  • AOF 持久化异步，主从复制也是异步，这期间存在丢失消息的可能。
  • 面对消息堆积，内存资源可能会紧张，面临 OOM 或者丢失消息的风险。

线程模型

• 单线程：指【接收客户端请求】→【解析请求】→【进行数据读写等操作】→【发送数据给客户端】这个过程是由主线程（单个线程）完成。
  • CPU 并不是 Redis 性能瓶颈，而往往是内存大小和网络 I/O。
  • 多线程模型引入了程序执行顺序不确定性、并发读写等问题，增加了系统复杂度，带来了可能的线程切换、加解锁的性能开销。
  • Redis6.0 后引入多线程，用于处理网络请求，解决网络 I/O 瓶颈，而命令执行依旧采用单线程。
• 后台线程：包括为关闭文件、AOF 刷盘和（异步）释放内存这些任务创建的单独线程，避免因耗时阻塞主线程。

持久化

AOF

• 记录写操作命令，读操作记录无意义，因而不记录读操作。
• 先执行写操作命令，再记录 AOF 日志。
  • 避免额外开销，保证 AOF 日志里的命令都是语法正确且可执行的。
  • 不会阻塞写操作命令的执行，写操作执行成功后再记录日志。
• 潜在风险
  • 在将写操作命令持久化到硬盘前，服务器宕机，数据有丢失风险。
  • 都在主进程完成，如果 I/O 压力过大，日志写回硬盘速度太慢，可能阻塞下一个命令的执行。
  • 共性：AOF 日志写回硬盘的时机，提供三种写回策略，底层实现区别在于直接调用/异步任务/不执行 fsync() 函数。
    • Always，即每次写操作命令执行完后，同步将 AOF 日志写回硬盘。
      • 最大程度保证数据不丢失，但不可避免影响主进程性能。
      • 如果数据量很大，或是 key 相对大，阻塞时间会更久。
    • Everysec，即每次写操作命令执行完后，先将命令写入内核缓冲区，每隔一秒将缓冲区内容写回硬盘。
      • 折中方式，比 Always 性能稍好，比 No 避免数据丢失。
    • No，即不由 Redis 控制写回硬盘时机，转交给操作系统控制缓冲区内容写回硬盘时机。
      • 性能较好，但一旦宕机可能丢失不定量数据。
• AOF 重写机制：核心是用一条命令记录键值对的最新状态，去除无意义的历史命令。
  • 先写到新的 AOF 文件，然后再覆盖现有的，避免重写失败污染现有 AOF 日志。
  • AOF 重写过程是后台子进程完成的，使用子进程而非线程避免因为加锁保证数据安全而降低性能。
  • 重写期间，Redis 执行新的写命令，会同时将这个命令写入 AOF 缓冲区和 AOF 重写缓冲区，重写完成后子进程向主进程发送一条信号，将 AOF 重写缓冲区的所有内容追加到新的 AOF 文件中。

RDB

• 记录某个瞬间的内存数据，恢复数据的效率更高，直接读入内存而不用额外执行操作命令。
• 全量快照，每次将内存中所有数据都记录到磁盘。因而太频繁会对性能产生影响，频率太低又会丢失更多数据。而 AOF 日志一般以秒级方式记录操作命令，丢失数据通常相较 RDB 更少。
• RDB 快照保存的是原本的内存数据，而主线程刚修改的数据（发生了写时复制后），只能交由下一次快照保存。
• 写时复制机制在极端情况下，内存占用是原来的两倍（所有的共享内存都被修改），因而写操作多的场景需要留意内存占用。

混合持久化

• 在 AOF 日志重写过程执行，AOF 文件前半部分是 RDB 格式的全量数据，后半部分是 AOF 格式的增量数据，后半部分记载了子进程重写 AOF 期间，主线程处理的操作数据。
  • 前半部分是 RDB 格式，加载速度更快。后半部分是 AOF 增量数据，可以尽量让数据更少丢失。
  • AOF 日志中加入了 RDB 格式内容，对应文件可读性差。
  • 无法兼容 Redis4.0 之前的版本。

过期策略

• 定时删除：设置 key 的过期时间，同时创建一个定时事件，时间到达由事件处理器自动执行删除 key 的操作。
  • 可以保证过期 key 被尽快删除，内存友好。
  • 过期 key 较多时，可能会占用相当一部分 CPU 时间，CPU 不友好。
• 惰性删除：不主动删除过期键，每次访问 key 时查看是否过期，若过期则删除该 key。
  • 每次访问时才检查 key 是否过期，只使用很少的系统资源，CPU 友好。
  • 过期 key 一直不被访问，它所占用的内存就不会被释放，造成一定的内存空间浪费，内存不友好。
• 定期删除：每隔一段时间随机从数据库中取出一定数量的 key 进行检查，并删除其中的过期 key。
  • 中庸之道，但难点在于确定删除操作执行的时长和频率。
• Redis 采用了惰性删除+定期删除相配合的方式。

哨兵机制

• 实现主从节点故障转移，具体负责监控（主节点是否存活）、选举主节点和通知新主节点相关信息。
• 判断故障
  • 主观下线：主节点或从节点没有在规定时间响应哨兵的 PING 命令。
  • 客观下线：只适用于主节点，主节点可能因为系统压力大或网络拥塞没有及时响应 PING 命令，为减少误判，需要用哨兵集群一起判断，赞成主节点下线的哨兵数达到阈值后就将主节点标记为客观下线。
  • 最先标记主节点客观下线的哨兵成为候选，然后候选者分别向其余哨兵发起投票请求，投票者响应最先收到的投票请求，当满足票数条件后，对应候选者成为 Leader，负责执行主从切换。
• 主从转移
  • 选出新主节点，过滤掉网络连接状态不好的节点，然后根据节点优先级、数据复制进度和节点 ID 选择。
  • 将已下线主节点属下的所有从节点指向新主节点。
  • 通过 Redis 的发布者/订阅者机制通知客户端新主节点的信息。
  • 继续监视旧主节点，当其重新上线后变更为新主节点的从节点。