深入理解 RDBMS

本文来源于第五届字节跳动青训营活动，已收录到深入理解 RDBMS | 青训营笔记 - 掘金 (juejin.cn) ，主要记录了对 RDBMS 的学习

深入理解 RDBMS

1.经典案例

1.1 红包雨

红包的发送与接收

update account_table set balance = balance - '红包' where name='活动主办方';
update account_table set balance = balance + '红包' where name='活动用户';

1.2 RDBMS 事务 ACID

• 事务（Transaction）：是由一组 SQL 语句组成的一个程序执行单元（Unit），它需要满足 ACID 特性。

  begin;
  update account_table set balance = balance - '红包' where name='活动主办方';
  update account_table set balance = balance + '红包' where name='活动用户';
  commit;

  两条更新操作不再是独立的，而是形成了一个整体，这个整体称为一个事务。

1.3 ACID

• 原子性（Atomicity）：事务是一个不可再分割的工作单元，事务中的操作要么都发生，要么都不发生。
• 一致性（Consistency）：数据库事务不能破坏关系数据的完整性以及业务逻辑上的一致性。
• 隔离性（Isolation）：多个事务并发访问时，事务之间是隔离的，一个事务不应该影响其它事务运行效果。
• 持久性（Durability）：在事务完成以后，该事务对数据库所作的更改便持久的保存在数据库之中，无法被回滚。

1.4 红包雨 与 ACID

• Case 1：活动主办方扣款发送红包，但是服务器挂了，活动用户未能收到红包…

  原子性 Atomicity：两个操作要么同时成功，要么同时失败，不存在中间状态。

• Case 2：活动主办方账户只有 0.5 个亿，但是扣减 1 个亿的操作成功了…

  一致性Consistency：每个操作都必须是合法的，账户信息应该从一个有效的状态变为另一个有效的状态。

• Case 3：用户参加了多个红包活动各自获得了一个亿，两个转账同时进行，假设都是从零开始更新用户的账户余额，最终用户只得到了一个亿…

  隔离性Isolation：两个操作在对同一个账户并发进行操作时，应该是相互不影响的，表现为串行操作。

• Case 4：红包收发成功后，但是还没写到磁盘上，服务器就挂了…

  持久性Durability：操作更新成功之后，更新的结果应该是永久性的保留下来，不会因为宕机等问题而丢失。

1.5 红包雨 与 高并发

• Case 5：假设10亿人同时开始抢红包，每秒处理一个请求，可能需要几十年时间才能完成…

  高并发 Concurrency：如果每秒能够处理1000万个请求，那么只需要几分钟。

1.6 红包雨 与 高可靠

• Case 6：在用户群体最活跃的时间段，服务器挂了，花费了大量时间修复，等修复好了用户都走了，口碑变差…

  高可靠、高可用 High Reliability/Availability

2.发展历史

2.1 前 DBMS 时代 — 人工管理

在现代计算机发明出来以前，通过人工的方式进行数据记录和管理

• 结绳记事、清代钱庄账本、1890年人口普查的霍列瑞斯式打孔机
• 效率太低

2.2 前 DBMS 时代 — 文件系统

1950年，现代计算机的雏形基本出现。1956年 IBM 发布了第一个磁盘驱动器 —— Model 305 RAMAC，从此数据存储进入了磁盘时代。在这个阶段，数据管理直接通过文件系统来实现。

从写到纸上变成了写到文件里，换了个马甲。

2.3 DBMS 时代

1960年，传统的文件系统已经不能满足人们的需要，数据库管理系统（DBMS）应运而生。

DBMS：按照某种数据模型来组织、存储和管理数据的仓库。

通常按照数据模型的特点将传统数据库系统分为网状数据库、层次数据库和关系数据库三类。

传统的文件系统难以应对数据增长的挑战,也无法满足多用户共享数据和快速检索数据的需求。

层次型、网状型和关系型数据库划分的原则是数据之间的联系方式。

层次数据库是按记录来存取数据的；

网状数据库是采用网状原理和方法来存储数据；

关系型数据库是以行和列的形式存储数据。

2.3.1 DBMS 数据模型 — 网状模型

网状数据库所基于的网状数据模型建立的数据之间的联系，能反映现实世界中信息的关系，是许多空间对象的自然表达形式。

1964年，世界上第一个数据库系统——集成数据存储（Integrated Data Storage，IDS）诞生于通用电气公司。IDS是世界上第一个网状数据库，奠定了数据库发展的基础，在当时得到了广泛的应用。

在1970年，网状数据库系统十分流行，在数据库系统产品中占据主导地位。

网状数据模型是以记录类型为结点的网络结构，即一个结点可以有一个或多个下级结点，也可以有一个或多个上级结点，两个结点之间甚至可以有多种联系，例如“教师”与“课程”两个记录类型，可以有“任课”和“辅导”两种联系，称之为复合链。

两个记录类型之间的值可以是多对多的联系，例如一门课程被多个学生修读，一个学生选修多门课程。

2.3.2 DBMS 数据模型 — 层次模型

1968年，世界上第一个层次数据库——信息管理系统（Information Management System，IMS）诞生于 IBM 公司，这也是世界上第一个大型商用的数据库系统。层次数据模型，即使用树形结构来描述实体及其相互关系的数据模型。

层次数据库就是树结构。每棵树都有且仅有一个根节点，其余的节点都是非根节点。每个节点表示一个记录类型对应与实体的概念，记录类型的各个字段对应实体的各个属性。各个记录类型及其字段都必须记录。

2.3.3 DBMS 数据模型 — 关系模型

1970年，IBM 的研究员 E.F.Codd 博士发表了一篇名为 “A Relational Model of Data for Large Shared Data Banks ” 的论文，提出了关系模型的概念，奠定了关系模型的理论基础。1970年 Oracle 首次将关系型数据库商业化，后续 DB2，SAP Sysbase ASE，and Informix 等知名数据库产品也纷纷面世。

使用表格表示实体和实体之间关系的数据模型称之为关系数据模型。

关系数据模型中，无论是是实体、还是实体之间的联系都被映射成统一的关系，一张二维表。

在关系模型中，操作的对象和结果都是一张二维表，它由行和列组成； 关系型数据库可用于表示实体之间的多对多的关系，只是此时要借助第三个关系—表，来实现多对多的关系。

2.4 DBMS 数据模型

	网状模型	层次模型	关系模型
优势	能直接描述现实世界，存取效率高	结构简单，查询效率高，可以提供较好的完整性支持	实体及实体间的联系都通过二维结构表示，可以很方便地表示 M:N 关系，数据访问路径对用户透明
劣势	结构复杂，用户不易使用，访问程序设计复杂	无法表示 M:N 的关系，插入、删除限制多，遍历子节点必须经过父节点，访问程序设计复杂	关联查询效率不够高，关系必须规范化

1974年ACM牵头组织了一次研讨会，会上开展了一场分别以Codd和Bachman为首的支持和反对关系数据库两派之间的辩论。这次著名的辩论推动了关系数据库的发展，使其最终成为现代数据库产品的主流。

2.5 SQL 语言

1974年 IBM 的 Ray Boyce 和 Don Chamberlin 将 Codd 关系数据库的12条准则的数学定义以简单的关键字语法表现出来，里程碑式地提出了 SQL（Structured Query Language）语言。

• 语法风格接近自然语言
• 高度非过程化
• 面向集合的操作方式
• 语言简洁，易学易用

update account_table set balance = balance - '红包' where name='活动主办方';

上面这条 SQL 语句执行的流程

1. Find account_table
2. Search accunt_tabke and compare name to ‘活动主办方’
3. Calculate balance - ‘红包’
4. Write new balance to account_table

高度非过程化

非关系数据模型的数据操纵语言是面向过程的语言，用其完成用户请求时，必须指定存取路径。而用SQL进行数据操作，用户只需提出“做什么”，而不必指明“怎么做”，因此用户无须了解存取路径，存取路径的选择以及SQL语句的操作过程由系统自动完成。这不但大大减轻了用户负担，而且有利于提高数据独立性。

面向集合的操作方式

SQL采用集合操作方式，不仅查找结果可以是元组的集合，而且一次插入、删除、更新操作的对象也可以是元组的集合。

语言简洁，易学易用

SQL功能极强，但由于设计巧妙，语言十分简洁，完成数据定义、数据操纵、数据控制的核心功能只用了9个动词: CREATE、 ALTER、DROP、 SELECT、 INSERT、 UPDATE、 DELETE、GRANT、 REVOKE。且SQL语言语法简单，接近英语口语，因此容易学习，也容易使用。

3.关键技术

3.1 一条 SQL 的一生

• SQL引擎
  • 查询解析：SQL 语言接近自然语言，入门容易。但是各种关键字、操作符组合起来，可以表达丰富的语意。因此想要处理SQL命令，首先将文本解析成结构化数据，也就是抽象语法树 （AST）。
  • 查询优化：SQL 是一门表意的语言，只是说『要做什么』，而不说『怎么做』。所以需要一些复杂的逻辑选择『如何拿数据』，也就是选择一个好的查询计划。优化器的作用根据AST优化产生最优执行计划（Plan Tree）。
  • 查询执行：根据查询计划，完成数据读取、处理、写入等操作。
• 事务引擎：处理事务一致性、并发、读写隔离等
• 存储引擎：内存中的数据缓存区、数据文件、日志文件

3.2 SQL 引擎

解析器 Parser

解析器（Parser）一般分为词法分析（Lexical analysis）、语法分析（Syntax analysis）、语义分析（Semantic analyzer）等步骤。

所有的代码在执行之前，都存在一个解析编译的过程，差异点无非在于是静态解析编译还是动态的。

SQL语言也类似，在SQL查询执行前的第一步就是查询解析。

词法分析：将一条SQL语句对应的字符串分割为一个个token，这些token可以简单分类。

语法分析：把词法分析的结果转为语法树。根据tocken序列匹配不同的语法规则，比如这里匹配的是update语法规则，类似的还有insert、delete、select、create、drop等等语法规则。根据语法规则匹配SQL语句中的关键字，最终输出一个结构化的数据结构。

语义分析：对语法树中的信息进行合法性校验。

优化器 Optimizer

基于规则的优化（RBO Rule Optimizer）

比如导航地图哪条路线红绿灯最少就选择哪条。

• 条件化简

  例如

  a=5 and b>a
  a>5 and a < b and b=1

  可分别化简为

  a=5 and b>5
  false

• 表连接优化：总是小表先进行连接

  select * from A,B,C where A.a1 = B.b1 and A.a1 = C.b1

• Scan 优化

  • 唯一索引
  • 普通索引
  • 全表扫描

数据库索引：是数据库中辅助数据结构，以协助快速查询、更新数据库表中数据。目前数据库中最常用的索引是通过 B+树 实现的。

基于代价的优化（CBO Cost Base Optimizer）

一个查询有多种执行方案，CBO 会选择其中代价最低的方案去真正的执行。

什么是代价？

到达一个目的地，有不同的路线，选择不同的路线有不同的代价。这里的代价可能是时间，也可能是路程。比如赶时间的时候，就会选择时间最短的。如果时间没那么赶，那么我们可能选择路程最短的。

对于数据库也是这样，一个查询有不同的执行方案。

那对于数据库而言，什么是一条SQL执行的代价呢？

其实，对于用户只能感知到查询时间这个代价，底层用了多少资源他是不在乎的。但是在并发的情况下，就得考虑资源消耗了，这个用户的查询占用的资源多了，其他用户的资源就少了。所以资源也是必须考虑的一点。

对于 InnoDB 存储引擎来说，全表扫描的意思就是把聚簇索引中的记录都依次和给定的搜索条件做一下比较，把符合搜索条件的记录加入到结果集，所以需要将聚簇索引对应的页面加载到内存中，然后再检测记录是否符合搜索条件。

对于使用二级索引 + 回表方式的查询，涉及 MySQL 的大数计算这种查询的成本依赖两个方面的数据：范围区间数量，需要回表数据量

执行器 Executor

火山模型

• 每个 Operator 调用 Next 操作，访问下层 Operator，获得下层 Operator 返回的一行数据，经过计算之后，将这行数据返回给上层。

• 优点：每个算子之间独立抽象实现，相互之间没有耦合，逻辑结构简单。

• 缺点：每计算一条数据有多次函数调用开销，导致 CPU 效率不高。

• 以 Plan Tree 为基础，调用关系是由根到叶，数据流是从叶到根。

向量化

• 每个 Operator 每次操作计算的不再是一行数据，而是一批数据（Batch N行数据），计算完成后向上层算子返回一个 Batch。
• 优点
  • 函数调用次数降低为 1/N
  • CPU cache 命中率更高
  • 可以利用 CPU 提供的 SIMD（Single Instruction Multi Data）机制
• 向量化执行更适合于大批量数据处理，对于很多单行数据处理并没有优势。而且往往搭配列式存储使用。

编译执行

• 将所以的操作封装到一个函数里面，函数的调用的代价也能大幅度降低。

• 一个问题：用户编写的 SQL 各式各样，如何对每一条 SQL 语句封装？

  使用 LLVM 动态编译执行技术

  代码生成之后数据库运行时仍然是一个 for 循环，只不过这个循环内部的代码从简单的一个虚函数调用plan.next()展开成了一系列具体的运算逻辑，这样数据就不用在各个 operator 之间进行传递，而且有些数据还可以直接被存放在寄存器中，进一步提升系统性能。整个操作有点像inline 函数，把所有的操作inline到一个函数中去。

  LLVM动态编译执行技术，根据优化器产生的计划，动态的生成执行代码。

3.3 存储引擎

InnoDB

In-Memory

• Buffer Pool
• Change Buffer
• Adaptive Hash Index
• Log Buffer

On-Disk

• System Tablespace(ibdata1)
• General Tablespaces(xxx.ibd)
• Undo Tablespaces(xxx.ibu)
• Temporary Tablespaces(xxx.ibt)
• Redo Log(ib_logfileN)

更多信息参考https://dev.mysql.com/doc/refman/8.0/en/innodb-architecture.html

Buffer Pool

Buffer Pool 中有多个 Instance，而每个 Instance 中有多个 chunk。

• MySQL中每个chunk的大小一般为128M，每个block对应一个page，一个chunk下面有8192个block。这样可以避免内存碎片化。

• 分成多个instance，可以有效避免并发冲突。

• Page id % instance num得到它属于哪个instance。

当buffer pool里的页面都被使用之后，再需要换存其他页面怎么办？淘汰已有的页面。

基于什么规则淘汰？淘汰那个最近一段时间最少被访问过的缓存页，这种思想就是典型的 LRU 算法。

普通的LRU算法存在缺陷，考虑到需要扫描100GB的表，而buffer pool只有1GB，这样就会因为全表扫描的数据量大，需要淘汰的缓存页多，导致在淘汰的过程中，极有可能将需要频繁使用到的缓存页给淘汰了，而放进来的新数据却是使用频率很低的数据。

MySQL 没有直接使用 LRU 算法，而是在 LRU 算法上进行了优化。

MySQL 的优化思路就是：对数据进行冷热分离，将 LRU 链表分成两部分，一部分用来存放冷数据，也就是刚从磁盘读进来的数据，另一部分用来存放热点数据，也就是经常被访问到数据。

当从磁盘读取数据页后，会先将数据页存放到 LRU 链表冷数据区的头部，如果这些缓存页在 1 秒之后被访问，那么就将缓存页移动到热数据区的头部；如果是 1 秒之内被访问，则不会移动，缓存页仍然处于冷数据区中。

淘汰时，首先淘汰冷数据区。

更多信息参考https://dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html

Page

变长字段列表	NULL 值标志位	Header	row_id	trx_id	roll_ptr	Col1	Col2	Col3	…	ColN

Header

• delete_mask：标识此条数据是否被删除。
• next_record：下一条数据的位置。
• record_type：表示当前记录的类型。

Page Header(120B)
User Records
Free Space
Page Directory
FIL Trailer(8B)

其中 User Records 在页面上实际是无序的，通过一个单向链表连接。

B+ Tree

• 页面内

  页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

• 从根到叶：中间节点存储

• 点查

  select * from table where id = 2000;

• 范围查询

  select * from table where id > 2000;

3.4 事务引擎

Atomicity 与 Undo Log

begin;
update account_table set balance = balance - '红包' where name='活动主办方';
update account_table set balance = balance + '红包' where name='活动用户';
commit;

如何将数据库回退到修改之前的状态？

使用 Undo Log。

Undo Log 是逻辑日志，记录的是数据的增量变化。利用 Undo Log 可以进行事务回滚，从而保证事务的原子性。同时也实现了多版本并发控制（MVCC），解决读写冲突和一致性读的问题。

在执行以下 SQL 语句中，Undo 也会生成相反操作的 SQL 语句。

insert into users(id,name)value(1,cat);
delete from users where id = 1; # undo
update users set name = 'dog' where id = 1;
update users set name = 'cat' where id = 1; # undo

原子性：一个事务（transaction）中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被恢复（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。

需要记录数据修改前的状态，一边在事务失败时进行回滚。

undo log是逻辑日志，记录的是数据的增量变化，它的作用是保证事务的原子性和事务并发控制。可以用于事务回滚，以及提供多版本机制（MVCC），解决读写冲突和一致性读的问题。

Isolation 与 锁

Isolation（隔离性）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。

如果多个并发事务访问同一行记录，就需要锁机制来保证了。

读写是否冲突？读写互不阻塞，MVCC机制。

Isolation 与 MVCC

MVCC 的意义

• 读写互不阻塞
• 降低死锁概率
• 实现一致性读

Undo Log 在 MVCC 中的作用

• 每个事务都有一个单增的事务 ID
• 数据页的行记录中包含了 DB_ROW_ID，DB_TRX_ID，DB_ROLL_PTR
• DB_ROLL_PTR 将数据行的所有快照记录都通过链表的结构串联了起来

脏读：事务还没提交之前，它对数据做的修改，不应该被其他人看到。

Durability 与 Redo Log

如何保证事务结束后，对数据的修改永久的保存？

方案一：事务提交前页面写盘，会导致随机 IO 写放大。

方案二：WAL（Write-ahead logging）

redo log 是物理日志，记录的是页面的变化，它的作用是保证事务持久化。如果数据写入磁盘前发生故障，重启 MySQL 后会根据 redo log 重做。

持久化：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

WAL：修改并不直接写入到数据库文件中，而是写入到另外一个称为 WAL 的文件中；如果事务失败，WAL 中的记录会被忽略，撤销修改；如果事务成功，它将在随后的某个时间被写回到数据库文件中，提交修改。 优点：

• 只记录增量变化，没有写放大

• Append only，没有随机IO

4.企业实践

4.1 红包雨挑战

情景模拟

活动统计

• 共计发放红包20亿元
• 总计发放卡券24亿张
• 节日红包补贴12.9亿

流量统计

• 活动钱包：400w/s
• 发红包：300w/s
• 发奖券：400w/s

流量大、流量突增、稳定性

4.2 大流量 — Sharding

问题背景

• 单节点写容易成为瓶颈
• 单机数据容量上限不够

解决方案

• 业务数据进行水平拆分
• 代理层进行分片路由

实施效果

• 数据库写入性能线性扩展
• 数据库容量线性扩展

当数据库中的数据量越来越大时，不论是读还是写，压力都会变得越来越大。虽然上面的方案可以扩展读节点，但是对于写流量增加，以及数据量的增加却没有办法。

4.3 流量突增 — 扩容

问题背景

• 活动流量上涨
• 集群性能不满足要求

解决方案

• 扩容 DB 物理节点数量
• 利用影子表进行压测

实施效果

• 数据库集群提供更高的吞吐
• 保证集群可以承担预期流量

4.4 流量突增 — 代理连接池

问题背景

• 突增流量导致大量建联
• 大量建联导致负载变大，延时上升

解决方案

• 业务侧预热连接池
• 代理侧预热连接池
• 代理侧支持连接队列

实施效果

• 避免 DB 因突增流量挂掉
• 避免代理和 DB 因大量建联挂掉

4.5 稳定性和可靠性

为什么要高可用？

恶意事故：程序员删库跑路

偶然事故：一个机房断电、断网， 某施工队施工的时候挖掘机把某游戏公司的光纤挖断了，一下午的时间，保守估计损失一个亿。

4.5.1 3AZ 高可用

三机房部署

• 机房级别容灾
• 机房级别流量调度

proxy

• 读写分离，分库分表
• 限流，流量调度

监控报警

• 实时监控集群运行状态
• 提前上报集群风险

HA

• High
• Avaliability
• 实时监控 DB 运行状态
• 宕机快速切换

BinLog：binlog是mysql用来记录数据库表结构变更以及表数据修改的的二进制日志，它只会记录表的变更操作，但不会记录select和show这种查询操作。

数据恢复：误删数据之后可以通过mysqlbinlog工具恢复数据

主从复制：主库将binlog传给从库，从库接收到之后读取内容写入从库，实现主库和从库数据一致性

审计：可以通过二进制日志中的信息进行审计，判断是否对数据库进行注入攻击

4.5.2 HA 管理

问题背景

• DB 所在机器异常宕机
• DB 节点异常宕机

解决方案

• HA 服务监管、切换宕机节点
• 代理支持配置热加载
• 代理自动屏蔽宕机读节点

实施效果

• 读节点宕机秒级恢复
• 写节点宕机 30s 内恢复

参考资料

SQL 优化之火山模型

Innodb 存储引擎 | MySQL 官网