数据库核心体系

数据库核心体系

SQL引擎中的

所谓解析器（），一般是指把某种格式的文本（字符串）转换成某种数据结构的过程。最常见的解析器（），是把程序文本转换成编译器内部的一种叫做抽象语法树（AST）的数据结构，此时也叫做语法分析器（）。

编译器、解释器中的解析器一般包含：

扫描器（，也叫或者 ，词法分析器）。扫描器的输入一般是文本，经过词法分析，输出是将文本切割为单词（token）的流。

语法分析器（，也叫 ）。语法分析器的输入是单词的流，经过语法分析，输出是语法树或者精简过的AST。

综合来看，解析器主要作用是进行词法分析和语法分析，提取出句子的结构。其输入一般是程序的源码，输出一般是语法树（ tree）或抽象语法树（ tree，AST）。

解析器类似于解码器，只不过是把字符串解码成数据结构。

编译器/解释器中的解析器一般要完成词法分析、语法分析的功能。

内存数据库与分布式数据库 内存数据库分布式数据库

单原子数据（访问串行化）

分布一致性

多原子数据 （事务 lock）

分布式事务 （两阶段提交 PC）

柔性事务

刚性事务（如单数据库）完全遵循 ACID 规范，即数据库事务正确执行的四个基本要素：

原子性(）

一致性（）

隔离性（）

持久性（）

柔性事务（如分布式事务）为了满足可用性、性能与降级服务的需要，降低一致性（）与隔离性（）的要求，遵循 BASE 理论：

基本业务可用性（Basic ）

柔性状态（Soft state）

最终一致性（ ）

同样的，柔性事务也部分遵循 ACID 规范：

原子性：严格遵循

一致性：事务完成后的一致性严格遵循；事务中的一致性可适当放宽

隔离性：并行事务间不可影响；事务中间结果可见性允许安全放宽

持久性：严格遵循

柔性事务的分类

柔性事务分为：两阶段型、补偿型、异步确保型、最大努力通知型。

隔离级别标准

MVCC不是单独可以使用的技术，需要配合其他并发控制技术一起来实现不同的隔离级别，如S2PL。

那我们来看看MVCC+S2PL如何实现不同的隔离级别。

事务号

数据有多个版本由不同的版本号区分，这种版本号就是一个事务号，是一个单调递增的数字。

将事务分成两种类型：只读事务和更新事务。

如果是只读事务：则在事务开始时获取一个事务号，读取数据时，就读取比这个事务号小的版本号的数据。这种读取是不用加锁的。

如果是更新事务：

读操作：获取共享锁，读取最新版本的值

写操作：获取排它锁，为写的数据创建一个新版本，版本号为无穷大(版本号类型的最大值，当然实际数据库很少这样实现的，考虑到崩溃恢复和持久化，实际数据库实现的版本控制和可见性判断远比这复杂，属于工程上的优化，目的是一样的)，这样其他事务根据其版本号就无法读取到这条记录，提交时，重新获取事务号，将此写入的数据的版本号改为此事务的事务号+1。

所以MVCC天然就不会读取到未提交数据。

读已提交

每次读都重新获取一次快照，读取最新已提交数据。

可重复读

第一次执行读操作时生成快照，后面的读都以此快照进行读取，这样每次读取的版本都是一样的。

如果是 … FOR 或DML语句，需要用排它锁锁住需要读写操作的数据直到数据结束。

可串行化

可串行化用SS2PL来实现。

这样，通过MVCC+S2PL实现了数据库的不同隔离级别。

可串行化

与串行化相比 是允许并发的实现

在保证一致性情况下，允许并发操作执行。

冲突可串行化（ ）

一个调度，如果通过交换相邻两个无冲突的操作能够转换到某一个串行的调度，称为冲突可串行化的调度。

当下面三种条件都满足时，我们将两个操作视为冲突

两个操作属于不同的事务

两个操作访问和处理的数据集有重叠

至少有一个操作的是写操作

对于S1是 ，可以交换非冲突操作，但S2都不可交换，不是 。

// S1 
T1        T2
R(A)
W(A)R(A)      <---W(A)
R(B)
W(B)                <------R(B)W(B)

// S2 
T1         T2R(A)W(A)
R(A)
W(A)
R(B)
W(B)R(B)W(B)

同一个事务操作不可改顺序，同时t1的操作与相邻的t2操作不可交换。

关系

冲突可串行性 比 可串行性 要严格；

满足冲突可串行性 必 满足 可串行性，反之不然。

可串行化一定是正确的并发调度，反正不一定。

所以引出了优先图检测冲突可串行化。

优先图检测冲突可串行化

如Ti的Ri(A)与Tj的Wj(A)冲突，而Ri(A)