子非鱼的技术博客

1. endl将与设备关联的缓冲区（buffer）中的内容刷到设备中。在调试时应保证”一直”刷新流。否则若程序崩溃，输出可能还是缓冲区，导致对于程序崩溃位置的错误推断

2. 读取数量不定的输入数据可用while (std::in >> value)

   当遇到文件结束符（end-of-file），或遇到一个无效输入时，istream对象状态变为无效，使条件为假

   EOF：在Windows中为Ctrl+Z，UNIX为Ctrl+D

C++编译过程

1. 预处理（Preprocessing）

   将所有的#include头文件以及宏定义替换成其真正的内容，预处理之后得到的仍然是文本文件，但文件体积会大很多。gcc的预处理是预处理器cpp来完成的。（include只做文本插入，在include的位置将头文件展开）

2. 编译（Compilation）

   这里的编译不是指程序从源文件到二进制程序的全部过程，而是指将经过预处理之后的程序转换成特定汇编代码（assembly code）的过程。

   一个cpp文件是一个编译单元。

3. 汇编（Assemble）

   汇编过程将上一步的汇编代码转换成机器码（machine code），这一步产生的文件叫做目标文件，是二进制格式。

   这一步会为每一个源文件产生一个目标文件。

4. 链接（Linking）

   链接过程将多个目标文以及所需的库文件（.so等）链接成最终的可执行文件（executable file）

宏

预处理阶段将宏所写内容替换

宏没有类型检查

在宏外加括号防止运算符优先级错误

在宏后不需要加分号（非C++语句）

头文件

视图（view）

概念

在MySQL中，视图是一种虚拟表，它是由一个或多个基本表的行或列组成的。视图并不实际存储数据，而是根据定义的 select 语句动态生成结果集。视图可以简化复杂的查询操作，提高查询效率，同时也可以保护数据的安全性，隐藏敏感数据。

执行过程

执行过程类似于 select 语句，流程如下

1. 视图展开（预处理器）：将视图名转化为 select 语句
2. 查询优化（优化器）：选择使用索引或者连接算法优化查询效率
3. 执行查询（执行器，存储引擎）：生成优化后的执行计划后，数据库的 存储引擎会根据这个计划执行查询。执行过程中，MySQL 会从底层表中读取数据，并按需执行连接、过滤、排序等操作，最终返回查询结果

连接（join）

简单嵌套循环连接

执行流程

对于左表的每一条记录，扫描右表的所有记录，找到匹配的记录

为什么要有缓存机制

MySQL 的数据是存储在磁盘里的，但每次访问磁盘开销过大。为此，Innodb 存储引擎设计了一个缓冲池（Buffer Pool），当数据从磁盘中取出后，缓存到Buffer Pool中，下次查询同样的数据的时候，直接从内存中读取，来提高数据库的读写性能。

除了数据的读取保存在缓存中，对数据的修改也不是立即写入磁盘，而是先写到缓存后择机刷盘。所以 Buffer Pool 中包含脏数据（数据页中）和 undo 页

如何提高缓存命中率

基本实现

使用LRU（Least recently used）算法

该算法的思路是，链表头部的节点是最近使用的，而链表末尾的节点是最久没被使用的。那么，当空间不够了，就淘汰最久没被使用的节点，从而腾出空间。

简单的 LRU 算法的实现思路是这样的：

数据库运行期间会发生哪些故障（问题）

事务故障

事务故障指事务未运行到既定的终点（没有commit或显式的rollback），例如对于支付系统若付款失败则需要回滚支付的操作，确保事务的一致性

系统故障

系统故障指需要即时重启系统而造成的数据库故障，现象是修改内存中的修改未写到磁盘，写入磁盘的数据未必是完成的事务

介质故障

介质故障指磁盘损坏造成的故障，需要全量迁移数据库数据

MySQL日志（解决方案）

undo log

概念

事务并发时遇到的问题

数据完整性方面（不同事务对同一行的读写/写写操作）

问题

不同事务对于同一范围内的数据进行增/删/改时需要锁确保在事务提交前只有一个事务能操作该数据

解决方法

对于要修改的数据加锁（lock）

查询结果方法（幻读现象）

问题

在当前读（区别于使用MVCC中ReadView的快照读）的场景下，在事务内不同时间对同一查询条件得到的查询结果不同

解决方法

事务并发带来的问题

• 丢失修改（lost update）：事务 1 与事务 2 从数据库中读入同一数据并修改，事务 2 的提交结果破坏了事务 1 提交的结果， 导致事务 1 的修改被丢失。(W-W)
• 读 “脏” 数据（dirty read）：事务 1 修改某一数据，并将其写回磁盘，事务 2 读取同一数据后，事务 1 由于某种原因被撤消，这时事务 1 已修改过的数据恢复原值，事务 2 读到的数据就与数据库中的数据不一致，是不正确的数据，又称为 “脏” 数据。（W-R）
• 不可重复读（non-repeatable read）：事务 1 读取数据后，事务 2 执行更新操作，使事务 1 无法再现前一次读取结果。(R-W)

并发不一致性的解决办法（封锁协议）

• 一级封锁协议

  事务 T 在修改数据 W 之前必须先对其加 X 锁，直到事务结束才释放（读不加锁）

  一级封锁协议可防止 丢失修改

• 二级封锁协议

  一级封锁协议基础上，事务 T 在读取数据 R 之前必须先对其加 S 锁，读完后即可释放 S 锁

  **二级封锁协议可以防止 丢失修改 和 读 “脏” 数据 **

• 三级封锁协议

  一级封锁协议基础上，事务 T 在读取数据 R 之前必须先对其加 S 锁，直到事务结束才释放

  三级封锁协议可防止 丢失修改、读脏数据和不可重复读

并行事务正确性的唯一准则（可串行化调度）

可串行性的定义

几个事务的并行执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。 这种并行调度策略称为可串行化（Serializable） 的调度

可串行性是并行事务正确性的唯一准则

什么是冲突操作

冲突操作是指读写操作和写写操作

数据库需要解决的问题（背景）

在转账场景中，A向B转账100元。转账过程需要保证的是要么转账成功，要么转账失败恢复到原始值（原子性 Atomicity）；转账前后A与B账号的存款总数不变（一致性 Consistency）；转账过程中A与B的其他转账操作不影响当前转账（隔离性 Isolation）；转账成功则不可撤回（持久性 Durability）。所以引入事务（Transaction）的概念

事务（解决方案）

特性（ACID）

1. 原子性（Atomicity）：一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节，而且事务在执行过程中发生错误，会被回滚到事务开始前的状态，就像这个事务从来没有执行过一样
2. 一致性（Consistency）：是指事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态
3. 隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致
4. 持久性（Durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失

InnoDB 引擎通过什么技术来保证事务的这四个特性的呢？

• 持久性是通过 redo log （重做日志）来保证的；
• 原子性是通过 undo log（回滚日志） 来保证的；
• 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
• 一致性则是通过持久性+原子性+隔离性来保证；

并行事务的问题与解决方案（读的隔离性）

问题

1. 脏读：如果一个事务「读到」了另一个「未提交事务修改过的数据」，就意味着发生了「脏读」现象

索引存储结构

存储结构

使用B+树作为存储结构，非叶子结点存放索引，叶子节点才会存放实际数据（索引+记录）

为什么使用B+树

B+树与B树的对比如下

• B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少
• B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树在插入、删除的效率都更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化
• B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B 树要实现范围查询，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

使用索引时的查询流程

叶子节点存放的是实际数据时（聚簇索引）

当通过主键指定条件时，通过主键索引遍历到叶子结点，获得主键值和其对应的数据

执行select的过程

连接器

客户端通过TCP三次握手与数据库建立连接

查询缓存

如果 SQL 是查询语句（select 语句），MySQL 就会先去查询缓存（ Query Cache ）里查找缓存数据，看看之前有没有执行过这一条命令，这个查询缓存是以 key-value 形式保存在内存中的，key 为 SQL 查询语句，value 为 SQL 语句查询的结果。

解析SQL

解析器完成词法分析（根据输入的字符串识别出关键字）和语法分析（判断语句语法）

执行SQL

预处理器

概述和传输层服务

可靠的、保序的传输：TCP

• 多路复用，解复用
• 拥塞控制
• 流量控制（防止接收方缓存区满造成的分组丢失）
• 建立连接

不可靠、不保序的传输：UDP

• 多路复用，解复用
• 没有为尽力而为的IP服务添加更多的其他服务

都不提供的服务：

• 延时保证
• 带宽保证

可靠数据传输原理

RDT协议（递进关系）

1. rdt1.0：不提供反馈信息（假设所有数据包都正确从发送端传送到接收端）

2. rdt2.0：停止等待协议，引入差错检验，接收方反馈，重传机制。接收方在检验后向发送方返回ACK（正确）/NCK（错误），这里的重传是对于NCK的重传，没有考虑对于丢失处理的超时重传（假设所有反馈消息都能正确送到发送端，没有消息分组的丢弃）

3. rdt2.1：ACK/NCK对于接受到的消息编号，由于为停止等待协议，发送方若未收到消息的确认则不发下个消息，所以只需要一个位表示序号0/1

4. rdt2.2：通过对于上个消息序号的确认替代对于本次消息的NCK（基于rdt2.1的小升级）

5. rdt3.0：引入超时重传机制，可能在接收端会出现冗余分组，但rdt2.2已可以应对（应对消息分组的丢失，但由于为停止等待，网络利用率很低）