SQL引擎中的parser
所谓解析器（Parser），一般是指把某种格式的文本（字符串）转换成某种数据结构的过程。最常见的解析器（Parser），是把程序文本转换成编译器内部的一种叫做抽象语法树（AST）的数据结构，此时也叫做语法分析器（Parser）。
编译器、解释器中的解析器一般包含：
扫描器（scanner，也叫tokenizer或者lexical analyzer，词法分析器）。扫描器的输入一般是文本，经过词法分析，输出是将文本切割为单词（token）的流。
语法分析器（parser，也叫syntax analyzer）。语法分析器的输入是单词的流，经过语法分析，输出是语法树或者精简过的AST。
综合来看，解析器主要作用是进行词法分析和语法分析，提取出句子的结构。其输入一般是程序的源码，输出一般是语法树（syntax tree）或抽象语法树（abstract syntax tree，AST）。
解析器类似于解码器，只不过是把字符串解码成数据结构。
编译器/解释器中的解析器一般要完成词法分析、语法分析的功能。
内存数据库与分布式数据库
柔性事务
刚性事务（如单数据库）完全遵循 ACID 规范，即数据库事务正确执行的四个基本要素：
原子性(Atomicity）
一致性（Consistency）
隔离性（Isolation）
持久性（Durability）
柔性事务（如分布式事务）为了满足可用性、性能与降级服务的需要，降低一致性（Consistency）与隔离性（Isolation）的要求，遵循 BASE 理论：
基本业务可用性（Basic Availability）
柔性状态（Soft state）
最终一致性（Eventual consistency）
同样的，柔性事务也部分遵循 ACID 规范：
原子性：严格遵循
一致性：事务完成后的一致性严格遵循；事务中的一致性可适当放宽
隔离性：并行事务间不可影响；事务中间结果可见性允许安全放宽
持久性：严格遵循
柔性事务的分类
柔性事务分为：两阶段型、补偿型、异步确保型、最大努力通知型。
两阶段型
分布式事务二阶段提交，对应技术上的 XA、JTA/JTS，这是分布式环境下事务处理的典型模式。
补偿型
TCC 型事务（Try-Confirm-Cancel）可以归为补偿型。在 Try 成功的情况下，如果事务要回滚，Cancel 将作为一个补偿机制，回滚 Try 操作；TCC 各操作事务本地化，且尽早提交（没有两阶段约束）；当全局事务要求回滚时，通过另一个本地事务实现“补偿”行为。
TCC 是将资源层的二阶段提交协议转换到业务层，成为业务模型中的一部分。
异步确保型
将一些有同步冲突的事务操作变为异步操作，避免对数据库事务的争用，如消息事务机制。
最大努力通知型
通过通知服务器（消息通知）进行，允许失败，有补充机制。
隔离级别标准
MVCC不是单独可以使用的技术，需要配合其他并发控制技术一起来实现不同的隔离级别，如S2PL。
那我们来看看MVCC+S2PL如何实现不同的隔离级别。
事务号
数据有多个版本由不同的版本号区分，这种版本号就是一个事务号，是一个单调递增的数字。
将事务分成两种类型：只读事务和更新事务。
如果是只读事务：则在事务开始时获取一个事务号，读取数据时，就读取比这个事务号小的版本号的数据。这种读取是不用加锁的。
如果是更新事务：
读操作：获取共享锁，读取最新版本的值
写操作：获取排它锁，为写的数据创建一个新版本，版本号为无穷大(版本号类型的最大值，当然实际数据库很少这样实现的，考虑到崩溃恢复和持久化，实际数据库实现的版本控制和可见性判断远比这复杂，属于工程上的优化，目的是一样的)，这样其他事务根据其版本号就无法读取到这条记录，提交时，重新获取事务号，将此写入的数据的版本号改为此事务的事务号+1。
所以MVCC天然就不会读取到未提交数据。
读已提交
每次读都重新获取一次快照，读取最新已提交数据。
可重复读
第一次执行读操作时生成快照，后面的读都以此快照进行读取，这样每次读取的版本都是一样的。
如果是SELECT … FOR UPDATE或DML语句，需要用排它锁锁住需要读写操作的数据直到数据结束。
可串行化
可串行化用SS2PL来实现。
这样，通过MVCC+S2PL实现了数据库的不同隔离级别。
可串行化
与串行化相比 是允许并发的实现
在保证一致性情况下，允许并发操作执行。
冲突可串行化（conflict serializability）
一个调度，如果通过交换相邻两个无冲突的操作能够转换到某一个串行的调度，称为冲突可串行化的调度。
当下面三种条件都满足时，我们将两个操作视为冲突
两个操作属于不同的事务
两个操作访问和处理的数据集有重叠
至少有一个操作的是写操作
对于S1是conflict serializability，可以交换非冲突操作，但S2都不可交换，不是conflict serializability。
// S1 T1 T2 R(A) W(A) R(A) <--- W(A) R(B) W(B) <------ R(B) W(B)
// S2 T1 T2 R(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)<Wj(A)，所以Ti就要先于Tj执行，所以就可以使用优先图来检测冲突可串行化。而如果优先图(precedence graph)没有环，则说明调度是冲突可串行化的。因为如果Ti需要在Tj前执行，又有Tj需要在Ti前执行，显然这是矛盾的，所以存在环则不是冲突可串行化的。
