内存数据库解析与主流产品对比（三） —数据库管理系统中的并发控

— 数据库管理系统中的并发控制—
1. 内存数据库并发控制的两种策略
a. 多版本的并发控制
内存数据库中的并发控制主要采用两类策略：1. 多版本的并发控制；2. 分Partition处理。并发控制机制可以分为乐观和悲观两种类型。悲观并发控制则认为进程竞争资源总是存在的，因此访问时先加锁，访问完再释放；乐观并发控制认为大多数情况不需要竞争资源，只在最后提交前检查是否存在冲突，有冲突就回滚，没有就提交。
乐观并发控制大多数不采用基于锁的技术实现，并且通常是多版本的。多版本意味着每次更新都会产生新的版本，读操作根据可见范围选取合适的老版本，读操作不阻塞写操作，所以并发程度比较高。其缺点是会产生额外开销，例如更新要创建新版本，而且随着版本越来越多，还需要额外开销收回老版本。内存数据库多采用乐观的多版本并发控制机制，相比于基于锁的悲观并发控制其优势是开销较小，而且支持并发程度较高的场景；缺点是在有大量写竞争的场景下，事务间冲突概率比较高时，大量事务会失败和回滚。
【内存数据库解析与主流产品对比（三）】b. 分Partition处理
内存数据库并发控制的另外一类策略是把数据库分成多个Partition ，每个Partition采用串行方式处理事务。优势是单Partition业务的执行没有用于并发控制的额外开销，缺点是存在跨Partition事务时系统的吞吐率会直线下降。因此，如果不能保证所有业务都是单Partition进行，将导致性能不可预测。
2. 多版本并发控制之 Hekaton
Hekaton采用乐观的多版本并发控制。 Transaction开始时，系统为事务分配读时间戳，并将Transaction标记为active ，然后开始执行事务，在操作过程中系统记录被读取/扫描/写入的数据。随后，在Pre-commit阶段，先获取一个结束的时间戳，然后验证读和扫描数据的版本是否仍然有效。如果验证通过，就写一个新版本到日志，执行Commit ，然后把所有的新版本设置为可见。 Commit之后， Post-Processing记录版本时间戳，之后Transaction才真正结束。
文章插图
a. Hekaton 的事务验证i) Read Stability：Hekaton系统能够保证数据的读稳定性（Read Stability），比如交易开始时读到的每条记录版本，在Commit时仍然可见，从而实现Read Stability 。 ii) Phantom Avoidances：Phantom指一个事务在开始和结束时执行相同的条件查询，两次结果不一样。出现幻影的原因是该事务执行过程中，其他事务对相同数据集进行了增加/删除/更新操作。应该如何避免幻影现象呢？可通过重复扫描，检查所读取的数据是否有新版本，保证记录在事务开始时的版本和在结束时一致。 Hekaton并发控制的好处在于，不需要对Read-Only事务做验证，因为多版本能够保证事务开始时的记录版本在结束时依然存在。对于执行更新的事务，是否做验证由事务的隔离级别决定。例如如果快照隔离级别，就不需要做任何验证；如果要做可重复读，就要做Read Stability；如果是串行化隔离级别，既要保证Read Stability ，又要保证Phantom Avoidance 。
b. Hekaton的回收策略Hekaton中的回收任务并不由独立的线程处理，而是每个事务自己回收。如下图所示， Transaction ID为250的事务结束时间戳为150且状态为terminated ，此时会有一个Write Set获取所有老版本，并判断当前所有active的Transaction的开始时间戳是否大于ID为250的事务结束时间，即150 。如果都大于150 ，说明不可能再基于时间戳早于150的旧版本进行修改，因而由事务回收旧版本，这部分工作是每个线程在处理Transaction时的额外工作。
文章插图
3. 多版本并发控制之Hyper
Hyper的并发控制和Hekaton的区别主要有以下三点：1. 直接在记录位置进行更新，通过undo buffer来保存对数据的修改，数据和所有修改被链接在一起；2. 验证是根据最近的更新与读的记录进行比较来实现（后续会涉及到）；3. 串行化处理commit ，对提交的事务进行排序，并依次处理。
文章插图
在事务验证方面， Hyper的验证需要在日志中记录Read Predictates ，包括查询或Range Scan ，而且要记录插入、删除和更新的记录。在Hyper模式中，插入/删除/更新通过对应的Undo Buffer获悉被修改过的记录，所以记录改动对于Hyper而言是容易的。