下载掌阅APP，畅读海量书库
立即打开
数据库管理系统（DBMS）是一种复杂的关键任务（Mission Critical）软件系统，与操作系统和中间件并称为基础系统软件三大件。当今的数据库管理系统包含了学术界和工业界数十年的研究以及大量的企业软件开发成果。如前所述，关系数据库在其中占据了绝对的主导地位，应用于金融、电信、交通、能源等诸多的在线信息系统。关系数据库历经数十年发展，在技术架构上逐渐趋同，一般的关系数据库除了公共组件，主要分为四个部分，包含接入管理、查询引擎、事务处理和存储引擎。其中，事务执行可以嵌入存储引擎中，对上层的查询引擎提供具有ACID保证的存储能力，如图1-2所示。这几部分互相合作，完成对SQL请求的处理过程。
图1-2 数据库管理系统架构
DBMS一般会提供符合标准接口协议（ODBC、JDBC……）的客户端驱动程序，用户程序可以通过客户端驱动提供的API与DBMS服务端程序建立数据库连接，并发送SQL请求。DBMS在接收到客户端发送的建立连接请求后，会根据协议要求判断是否建立连接，比如客户端地址是否符合接入要求，判断客户端使用的用户进行安全验证和权限验证。验证通过后，建立相应的数据库连接，并为连接分配相应的资源，并为后续的请求执行创建一个会话（Session）环境（Context）。在这个连接上发送过来的请求都会使用会话环境中的设置，直到会话关闭。
当接收到客户端发送的第一条请求后，DBMS会分配相应的计算资源，这个过程与DBMS实现相关，有的数据库（比如PostgreSQL）采用process-per-connection模型，会创建一个子进程服务这个连接上的所有请求。有的数据库（比如MySQL）采用thread-per-connection模型，会创建一个独立的线程。还有一些更复杂的设计，并不会为每个会话创建独立的服务线程或进程，而是采用线程池或进程池的模型，多个会话共用一组线程或进程，避免连接数过多导致系统资源过载。这套机制由公共组件（Common Component）中的进程管理（Process Management）组件实现。
SQL引擎子系统负责将用户发送过来的SQL请求进行解析、语义检查、生成逻辑计划（Logical Plan），经过一系列重写（Rewrite）与优化（Optimize），生成物理计划（Physical Plan），交由计划执行器（Plan Executor）执行。
SQL语句种类繁多，常见的划归为两大类，一是数据操作语言（Data Manipulation Language，DML），语句包括SELECT、UPDATE、INSERT和DELETE；一类是数据定义语言（Data Definition Language，DDL），用来维护数据字典，例如CRATE TABLE、CREATE INDEX、DROP TABLE和ALTER TABLE等，这些DDL语句通常不经过查询处理器的优化阶段，直接由DBMS静态逻辑调用存储引擎（Storage Engine）和数据字典管理（Catalog Manager）处理。本章主要讨论DML的处理，以一个简单的语句"SELECT a，b FROM tbl WHERE pk＞=1 and pk＜=10 ORDER BY c"为例，展示一般SQL语句的执行过程，如图1-3所示。
图1-3 SQL语句的执行过程
1.查询解析
SQL请求第一步是语法解析，多数DBMS通过类lex和yacc等工具生成词法与文法解析器（Query Parser），检查SQL语句的合法性，将SQL文本转化为抽象语法树（Abstract Syntax Tree，AST）结构。图1-3展示了语句解析后的语法树，结构比较简单，如果from子句或where子句后面还有嵌套子查询，那么还会在这些节点下挂上子查询的子树。
随后在AST上做语义检查（resolve），解决名字和引用的问题，比如结合数据字典检查操作的表和字段是否存在，用户是否有相应的操作权限，并将引用的对象名规范化（normalize），比如每个表名规范化为"database"."schema"."tablename"的形式。检查通过后，生成逻辑查询计划。逻辑查询计划是由一系列逻辑操作符组成的树结构。逻辑查询计划并不具备直接执行的能力，逻辑操作符通常也只是一些标记数据结构，用于携带必要的操作信息，便于构成后续的优化，生成真正的执行计划。
2.查询重写
查询重写是查询优化的预备阶段，主要工作是在保证查询语句语义不变的情况下，对原有的查询结构做等价变换，简化和标准化查询结构。查询重写通常在Logical Plan上进行而不是直接操作文本。查询重写一般有如下工作。
1）视图展开。对from子句中的每个引用的视图，从catalog中读取定义，用这个视图引用的表和谓词条件替换视图，以及任何引用这个视图中的列替换为对视图引用表的列引用。
2）常量折叠。对于可以在编译时间计算结果的表达式，直接计算后重写。比如a＜2*3重写为a＜6。
3）谓词逻辑重写。对where条件中的谓词进行重写，比如短路求值a＜10 and a＞100表达式可以直接转为false，返回空结果集。或者做逻辑等价变换，比如not a＜10转换为a＞=10，还有一种重要的逻辑重写使用谓词传递性引入新的谓词，比如t1.a＜10 and t1.a=t2.x，这种方式隐含了t2.x＜10的条件，可以提前对t2表的数据过滤。
4）子查询展开。嵌套子查询在优化阶段比较难以处理，所以重写阶段一般会将其重写为Join形式。比如"SELECT*FROM t1 WHERE id IN（SELECT id FROM t2）；"可以重写为"SELECT DISTINCT t1.*FROM t1，t2 WHERE t1.id=t2.id；"。
还有一些诸多的重写规则，比如根据Schema定义的约束条件做一些语义优化重写，其目的都是一样的——更好地优化查询的效率，减少不必要的操作，或将查询规范化，便于后续的优化阶段处理。
3.查询优化
查询优化的具体工作就是将之前生成并重写过的Logical Plan转化为一个可执行的Physical Plan。这个转化工作试图找出所有可能的计划中代价最低的计划，实际上，寻找“最优计划”是一个NP完全问题，而且代价估算也不准确，优化器只可能寻找“尽可能低”的计划。
查询优化的技术细节非常复杂，这里不会展开。常见的查询优化器一般结合两种技术——Rule-Based（基于规则）和Cost-Based（基于代价）。像开源数据库MySQL是完全基于启发式（Heuristic）规则：比如尽可能下推所有的Filter、Porject、Limit操作，在多表Join时基于基数估计，优先选择小表，Join算子一般选择Nested-loop Join。而Cost-Based的方法是搜索可能的计划，根据代价模型（Cost Mode）公式计算代价，选取代价最小的计划。显然，搜索所有可能的计划代价太大，是不可行的。有两种典型的搜索方法，一是Selinger在论文 [1] 中提到的，使用自底向上的动态规划，为减少搜索空间，只专注“左深树”查询计划（一个连接操作的右手边的输入必须是一个基表），以及尽可能避免“Cross Join”（保证在数据流中，求笛卡儿积的操作是出现在所有的连接之后）。另一种搜索方法是基于级联式技术（Cascade）、目标导向和自顶而下的搜索方案。在一些情况下，自顶向下搜索虽然可以降低一个优化器需要考虑的计划的数量，但同时产生了负面影响，即增加了优化器内存消耗。
计算代价模型与具体的算子及算子的计算顺序相关，比如选择使用哪种Join算子时，需要根据Join条件估算结果集大小，涉及选择率（Selectivity）的问题，而计算选择率需要有列统计信息支撑，统计信息越准确，估计代价就越准，也就能选择到更好的计划。现代数据库不仅统计列的MIN、MAX、NDV（Number of Distinct Value），还有更精准的直方图统计。但在数据量大的情况下，统计直方图开销过大，往往折中采用采样（Sampling）的方法。
4.查询执行
一般执行器采用的执行模型叫作火山模型（Volcano Model），也叫迭代器模型，最早出现在Goetz Graefe的论文 [2] 中。火山模型是一种“拉（Pull）数据”的模型，其基本思路十分简单：将每一个执行计划中的物理算子实现为一个迭代器。每个迭代器都带有一个get_next_row()方法。每次调用这个方法将会返回算子产生的一行数据（tuple）。程序通过在物理执行计划的Root操作符循环调用get_next_row()方法，直到所有数据拉取完毕。以图1-4的Physical Plan为例，计划执行只需循环调用Sort算子的get_next_row()方法即可取到整个结果集。
而顶层的Sort算子是一个聚集算子，它需要把子算子的所有数据都拉取出来，然后才能排序。
图1-4 火山模型查询思路
Projection算子实现则比较简单，只要简单拉取子算子的一行数据，选取必要的列返回即可。
IndexScan则需要对涉及的表按索引扫描数据，具体实现属于存储引擎（Storage Engine）的内容。
数据库的一个最重要的特性是保证“ACID”语义，ACID的具体含义是指：
· 原子性（Atomicity）：一个事务的所有行为在数据库中必须是“原子”的，即这个事务操作的所有数据要么全部提交，要么全部回滚。
· 一致性（Consistency）：是应用层面的一个保证。SQL语句的完整性约束通常就是用于在数据库系统中保证一致性的。给定一个由约束条件集提供的一致性定义，只有当一个事务在完成时可以使得整个数据库仍保持一致性状态的时候，这个事务才能被提交。
· 隔离性（Isolation）：数据库给每个事务独占整个数据库的假象，任意两个并发执行的事务无法看到对方未提交的数据。
· 持久性（Durability）：一个成功提交的事务对数据库的更新是永久的，即便之后发生软件或硬件故障，除非另一个提交的事务将它重写。
数据库处理系统的ACID保证一般非常复杂，具体包括并发控制、日志与恢复系统模块组成。
1.并发控制
数据库是一个多用户系统，意味着同时会收到大量的并发访问请求，如果这些并发请求里有对同一条数据的访问，并且其中一个操作是写操作，则这种情况叫作“数据冲突”（Data Race）。如果不设定合适的保护机制而放任数据冲突不管，则一定会产生数据读写异常，比如读到别的事务未提交的脏数据，一个事务写入的数据被别的事务写入数据覆盖，一次事务中多个时间点读到的数据不一致等。前面讨论的隔离性就是为了避免这些异常带来的非预期的数据结果，而并发控制便是为了实现隔离性而定义的一套数据读写访问的保护协议。
维护数据一致性的严格程度不同，所付出的代价也是不一样的，一致性越严格，运行时的效率也越低。如今多数数据库为了达到效率和一致性之间的平衡，根据异常不同等级定义了多个隔离级别（Isolation Level）选项，以严格程度依次增加分为：读未提交（Read Uncommitted）、读已提交（Read Committed）、可重复读（Repeatable Read）和可串行化（Serializable），用户可以根据业务特征选择。
最严格的隔离级别是可串行化，其意义比较直观，即多个事务交错并发执行的结果，必须与这组事务的某个串行执行结果相同。对于这组事务中的单个事务来说，看起来就好像它在独占这个数据库一样，看不到其他事务的存在，这也是隔离性的含义所在。主要的并发控制技术有以下几种。
1）两阶段加锁（2 Phase Lock，2PL）。对于事务中的每个读写操作，都要对要读写的数据行加锁，读操作加共享锁（Share Lock，其他读操作可以并行执行，写操作必须等待），写操作加排他锁（Exclusive Lock，其他读写操作都需等待）。而且需要保证加放锁的顺序分为加锁阶段和放锁阶段，加锁阶段只允许加新的锁，而放锁阶段只能依次释放之前加的锁，不能再加新的锁。
2）多版本并发控制（MVCC）。事务不使用锁机制，而是针对修改的数据保存多个版本，事务执行时可以锚定一个时间点，即便这个时间点之后数据被别的事务修改，仍然可以读到之前锚定时间点的历史版本数据。
3）乐观并发控制（OCC）。所有事务的操作都无阻塞地读写数据，但是会把所有读和写的操作历史分别写入读操作集合（Read Set）和写操作集合（Write Set）。在事务提交之前经过一个验证阶段（Validation Phase），检查读写集合是否与这个时间段（事务开始和提交之间）的其他事务发生了冲突，如果冲突，则其中一个事务必须回滚。
严格使用2PL可以保证可串行化的隔离级别，但是对每个操作都加锁的代价过大，尤其是读操作，大部分并发事务操作的数据可能并没有交集，但也不得不付出这个代价。为降低加锁的代价，很多数据库采用MVCC+2PL的混合模式，对写操作的数据加锁，而读操作不加锁，而是访问数据某个时间点的历史版本。这种方法提供的隔离级别称为快照隔离（Snapshot Isolation），不能达到可串行化，会有写偏斜（Write Skew）的异常 [1] 。不过它避免了大部分其他异常，提供了更好的性能，在大部分情况下会是一个更好的选择。
而乐观并发控制虽然避免了锁等待，但是一旦判定事务产生了冲突，将会产生大量的回滚，因此在事务冲突较多（比如秒杀场景中，用户购买同一个商品的减库存操作）的情况下表现会非常差，适用于并发事务数据冲突较少的场景。
2.日志与恢复系统
日志系统是数据库存储引擎中的核心部分，主要功能是保证已提交事务中的持久性（D），使得数据库在崩溃后仍然能将之前已提交的事务恢复过来，并且确保回滚中止执行的事务的原子性（A）。实际上保证DA有诸多技术，比如Jim Gray在System R中使用的影子分页（Shadow Paging）技术 [3] ，每次为修改的页面生成一个新页面，提交时持久化新的页面，并且把当前页表（Page Table）中的页面指向原子修改为新页面，回滚则简单丢弃新生成的页面，使用原来的影子页面（Shadow Page）即可。该方法简单直观，但是不支持页面级事务并发，回收代价也比较大，执行效率不高，没有成为主流。现在流行的数据库的恢复机制基本上都使用了C.Mohan发表的ARIES论文 [4] 中的日志机制。
数据库早期都是为了传统磁盘而设计的，而传统磁盘的顺序访问性能远高于随机读写。用户的更新一般都是比较随机地更新一些页面，如果每更新一个页面提交就要把相应的页面刷到磁盘，则会引发大量的随机I/O，也无法保证页内并发事务的原子性，例如多个事务同时更新页面时，一个事务提交后不能立即刷下页面，因为可能包含其他未提交事务。因此在更新页面时，只会在内存缓存中原地更新页面内容，同时记录事务的操作日志，保证在事务提交时操作日志先于页面内容刷到磁盘，这种技术被称为预写日志（Write Ahead Log，WAL）。
为了保证事务的D和A，需要严格定义日志、提交点以及数据页的落盘顺序。这里有force/no-force、steal/no-steal几种策略。
· 首先日志肯定先于数据页面落到磁盘，要求事务提交后（记录Commit Marker），必须强制把事务所有更新的页面刷到磁盘，然后才能返回事务提交成功，这种策略称为force。如果不强制立即刷入更新页面，则可以放在后面异步进行，这种策略称为no-force。no-force意味着可能有部分已经提交的事务所在的页面并没有落盘，这时日志必须记录重做日志（Redo Log），恢复时可以通过回放回滚保证持久性。
· 是否允许一个含有未提交事务的数据页刷盘，如果steal策略允许，则磁盘上就包含了未提交事务，必须在日志里面记录回滚来保证事务中止时能够回滚，no-steal策略则不用。
ARIES协议采用的是steal/no-force策略，即允许未提交事务先于提交点落盘，也允许事务提交后不强制数据页必须落盘，可以完全自主决定何时将脏页刷新到磁盘，采用最优的I/O模式，从理论上来说，其是效率最高的。付出的代价是必须同时记录重做日志和回滚日志。
对于数据库表的数据存储操作，一般都在存储引擎层完成。它涉及数据存取的TableScan、IndexScan物理算子会调用存储引擎提供的数据存取接口（Access Method）读写指定数据。数据库存储引擎一般包含数据组织与索引管理和缓冲区管理两个主要模块。
1.数据组织与索引管理
数据库的数据存储组织方式是由目标存取效率决定的。不同种类的数据库侧重点也有所不同，早期的数据库都以磁盘作为存储介质，为了达到更快的I/O效率，一般采用定长的页面（Page）管理数据，页面大小通常对齐到磁盘扇区（Sector）大小，例如8KB、16KB，也便于装载到内存缓冲区进行管理。
一张表的数据通常会包含非常多的行，这些行以随机或写入的顺序组织成若干页（这种组织方式称为堆表），如何在查询时定位到需要的页面，减少物理I/O次数，是提升数据库查询性能的关键。这就需要对表数据建立索引，用户可以选择若干类型的索引方式，默认是B树索引，数据库会额外存储索引（同样以页面的形式组织）结构，如果是B树索引，那么叶子节点会索引到实际的表数据页面中的位置。有一种特殊索引是主键索引（Primary Key Index），当用户对表指定了主键后，数据库会按主键对数据排序，以排序的形式聚集在物理页面中，这种索引称为聚簇索引，无须额外存储索引结构。
在内存容量越来越大，价格越来越便宜的趋势下，出现了纯内存数据库。它以内存作为主要存储介质的数据库形态，内存支持高效的随机地址访问，无须再像磁盘一样使用逻辑结构映射到物理地址的间接访问方式，而是直接使用带指针的数据结构，而且索引到行，访问路径更短、更直接。根据使用场景的不同，在页面内的数据组织方式也有所区别，典型类型有以下几种。
· 数据按行存储（Narray Storage Model，NSM），对事务处理比较友好，因为事务数据总是以完整行的形式写进来，多用于在线事务处理（OLTP）场景；
· 按列存储（Decomposition Storage Model，DSM），把元组中相同的列值在物理上存储在一起，这样只需要读取需要的列，在扫描大规模数据时减少大量I/O。另外，列存做压缩的效果更好，适合在线分析处理（OLAP）场景，但是事务处理就不那么方便，需要做行转列操作，所以大部分AP数据库事务处理效率都不太高，某些甚至只支持批量导入。
· 混合存储（Flexible Storage Model，FSM），采用行列混合布局，有把数据先按行分组（Segment，SubPage），组内使用DSM组织，如PAX、RCFile；也有先按列分组（Column Group），组内指定的列按NSM组织，如Peloton的Tile。此种格式试图结合NSM和DSM两者的优点，达到处理混合负载（HTAP）的目的，但同时也继承了按行存储和按列存储的缺点。
当然，数据组织还有更多细节，如何在磁盘或内存中节约存储空间的同时不降低存取效率，有很多的材料例如ASV99 [5] 、BBK98 [6] 可以进一步参考。
2.缓冲区管理
在对数据页面进行读写操作时，一个必要的操作是把页面从磁盘装载到内存中，修改页面的内容也在内存中进行。一般而言，内存的容量都远小于磁盘容量，因此装载到内存中的页面只是整体数据页的一部分。如何根据读写请求决定内存中装载哪些页面，何时将页面同步修改到磁盘，淘汰哪些内存页，都是缓冲区管理的主要工作。
大部分数据库在内存页中使用和磁盘页面完全一样的内容，这样做有两点好处，一是固定大小的页面便于内存管理，使用非常简单的分配回收算法，避免内存碎片；二是格式一致，读写过程中没有编码和解码（serialize/deserialize）操作，减少了CPU的负担。
数据库使用一个页表（散列表）的数据结构管理缓冲区页面，页表是页面编号与页面内容（包括页面内存位置、磁盘位置及页面元数据）的映射关系。元数据记录了页面当前的一些特征，比如脏标记（Dirty Flag）表明页面是否在读入之后被修改过，引用标记（Pin）表明页面是否被某些正在执行的事务引用，这类页面是不能被交换到磁盘的。
缓冲区的大小一般是固定的，与系统配置的物理内存相关。因此，当缓冲区被填满时，如果有新的页面需要加载，则必须使用页面替换算法淘汰一些页面。一些通用的缓冲区替换算法如LRU（Least Recently Used）、LFU（Least Frequently Used）和CLOCK等在数据库复杂的访问模式下未必合适，比如数据库中常见的全表扫描。如果扫描的数据量非常大，若使用LRU算法，这些数据页面会全部进入缓冲区挤占掉原有的数据页，导致短时间内缓冲区的命中率大幅下降。如今，很多数据库采用简单的LRU增强方案解决扫描问题，比如将缓冲区划分为冷区和热区，扫描读入的部分页面先进入冷区，在冷区中命中以后再进入热区，避免缓存污染问题。也有很多的研究寻找更多的有针对性的替换算法，例如LRU-K [7] 和2Q [8] 。
参考文献
[1]GRIFFITHS SELINGER P, ASTRAHAN M, Chamberlin D, et al. Access path selection in a relational database management system.Proceedings of the 1979 ACM-SIGMOD international conference on Management of data, 1979: 23-34.https: //doi.org/10.1145/582095.582099.
[2]GRAEFE G.Volcano, an extensible and parallel query evaluation system.IEEE Transactions on Knowledge and Data Engineering 6.1, 1994:120-135.
[3]GRAY J, MCJONES P, BLASGEN M, et al. The recovery manager of the System R database manager.ACM Computing Surveys (CSUR), 1981, 13(2): 223-242.
[4]MOHAN C, HADERLE D J, LINDSAY B G, et al. Aries: A transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging.ACM Transactions on Database Systems (TODS), 1992, 17: 94-162.
[5]ARGE L, SAMOLADAS V, JEFFREY SCOTT V, et al. On Two-Dimensional Indexability and Optimal Range Search Index.Proceeding of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1999: 346-357.
[6]BERCHTOLD S, BÖHM C, KRIEGEL H-P.The Pyramid-Technique:Towards Breaking the Curse of Dimensionality.ACM-SIGMOD International Conference on Management of Data, 1998:142-153.
[7]O'NEIL E J, O'NEIL P E, WEIKUM G, et al. The LRU-K Page Replacement Algorithm For Database Disk Buffering.ACM SIGMOD International Conference on Management of Data, 1993: 297-306.
[8]JOHNSON T, SHASHA D.2Q:A low overhead high performance buffer management replacement algorithm.International Conference on Very Large Data Bases (VLDB), 1994:297-306.
[1] 写偏斜（Write Skew）异常：是指两个事务（ T 1 与 T 2 ）并发读取一个数据集（例如包含 V 1 与 V 2 ），然后各自修改数据集中不相交的数据项（例如 T 1 修改 V 1 ， T 2 修改 V 2 ），最后并发提交事务。如果事务是串行执行的，这种异常不会发生。而快照隔离允许这种异常发生。例如，设想 V 1 与 V 2 是Phil的个人银行账户。银行允许 V 1 或 V 2 是空头账户，只要两个账户总和非负（即 V 1 + V 2 ≥ 0）。两个户头的初值各是$100，Phil启动两个事务， T 1 从 V 1 取出$200， T 2 从 V 2 取出$200。
解决写偏移异常有两种策略：一是实现写冲突，增加要给专用的冲突表，两个事务都修改它；二是提升，一个事务修改它的只读数据行（替换其值为一个相等的值）从而导致一个写冲突，或者使用等价的提升——SELECT FOR UPDATE语句。