看tag知内容 [toc]

参考资料

https://lvsizhe.github.io/course/2020/03/mapreduce.html

https://zhuanlan.zhihu.com/p/34849261

看tag知内容

这里的epoch技术是不是也是bw-tree的那个技术？一招鲜吃遍天？？

流式/增量

1. 支持反馈的有结构循环
2. 有状态的数据流节点，能够在没有全局协调(global coordination)的情况下消费和生产记录（record）
3. 当达到某个循环次数或者遍历完所有数据之后通知所有节点

看tag知内容

https://github.com/couchbase/moss

重写成c++版本

https://github.com/couchbase/moss/blob/master/DESIGN.md

线程安全不等于可重入

lmdb是基于mmap的。还好是嵌入式的小kv，选择mmap可以理解，不过不推荐

boltdb是借鉴lmdb的思想用go重写的，boltdb的资料非常多。

看tag知内容

MVCC 的技术要点，包括：

1. 并发控制协议
2. 多版本存储
3. 垃圾回收
4. 索引管理

并发控制协议

MVTO

通过预先计算顺序的方式来控制并发；事务的读操作返回最新的没有被写锁锁定数据的版本；事务的写操作过程如下：

• 当前没有活跃的事务锁定数据
• 当前事务的事务编号大于最新数据中的读事务的事务编号
• 如果这上述条件成立，那么创建一个新的数据版本

MVOCC

在 MVOCC 中，事务被分成三个阶段，分别是：

1. 读数据阶段，着这个阶段新的版本被创建出来。
2. 验证阶段，在这个阶段一个提交编号被分配给该事务，然后基于这个编号进行验证；
3. 提交阶段，完成提交。

MV2PL

顾名思义，MV2PL 是传统的两阶段锁在多版本并发控制中的应用；事务读写或者创建数据版本都需要获得对应的锁。

SSI

可串行化快照隔离(serializable snapshot isolation或SSI)是在快照隔离级别之上，支持串行化。PosgtreSQL 中实现了这种隔离级别，数据库通过维护一个串行的图移除事务并发造成的危险结构。

多版本存储

数据库通过无锁指针链表维护多个版本，使得事务可以方便的读取特定版本的数据。

仅限追加存储(Append-Only)

• 所有的版本存储在同一个表空间
• 更新的时候追加在版本链表上追加新节点
• 链表可以以最旧到最新的方式组织，
• 链表也可以以最新到最旧的方式组织，表头为最新版本

时序存储(Time-Travel Storage)

• 每次更新的时候将之前的版本放到旧表空间
• 更新主表空间中的版本

仅差异存储(Delta Storage)

• 每次更新近存储修改的部分，将其加入链表，主表空间存储当前版本
• 通过旧的修改部分，可以创建旧版本

垃圾回收

MVCC 在事务过程中不可避免的会产生很多的旧版本，这些旧版本会在下列情况下被回收

1. 对应的数据上没有活跃的事务
2. 某版本数据的创建事务被终止

数据行级别垃圾回收(Tuple Level)

通过检查数据来判断是否需要回收旧版本，有两种做法：

1. 启动一个后台线程进行数据行级的垃圾回收
2. 当事务操作数据行时，顺便做一些垃圾回收的事情

事务级别垃圾回收(Transaction Level)

事务自己追踪旧版本，数据库管理系统不需要通过扫描数据行的方式来判断数据是否需要回收。

索引管理

数据有多个版本，而索引只有一份，更新和维护多个版本的时候如何同步索引？

主键(Primary Key)

主键一般指向多版本链表头

副索引(Secondary Indexes)

有两种做法，逻辑指针和物理地址；前者通过增加一个中间层的方式实现，缩影指向该中间层，中间层指向数据的物理地址，避免应为多版本的物理地址改变引起的索引树的更新；后者索引直接指向数据物理地址。

##

实现

mongo mvcc

https://segmentfault.com/a/1190000023333915

pg mvcc

https://zhuanlan.zhihu.com/p/56108935

Cockroach事务机制中的几个概念：

• 事务ID：每个事务都有一个事务ID，作为事务的唯一标识。
• 事务的状态：pending， aborted， committed。
• 事务的隔离级别：SI、SSI 。
• 事务表(Transaction Table)： 记录整个系统中所有事务的状态，以及处于committed状态事务提交的时间。

事务运行流程中的几个关键状态：

• start 每个事务开始的时候会分配一个initi timestamp和一个优先级别。但是一个事务并不是拥有唯一的 initial timestamp 和优先级别
• restart 事务冲突时，冲突的一个事务需要restart，restart时，把当前事务abort，重新启动一个新的事务，此时事务的initial timestamp与优先级别可能会发生变化。但是对用户看来，就是一个事务
• candidate commit 事务除了在开始会分配一个initial timestamp，还会分配一个 candidate commit timestamp ，初始值为initial timestamp，它在事务执行过程中可以被修改(只能变大)。当事务执行写操作的时候，会在key值中加入intend flag 标签和candidate commit timestamp，表示事务会在candidate commit timestamp 这个时间提交。
• commit 一个事务的是否真正commit 在与此事务是否在transaction table中将事务的状态更新为commited。此时会去掉key值中的intend flag，用于判断是否提交，但是transaction table里面的状态才是真正衡量一个事务是否提交的标志.

Key的格式：

• 未提交事务的数据Key格式

key + intend + candidate commit timestamp

• 已提交数据的Key的内存格式：

key + latest read timestamp

• 持久化后，每个key/values 按照事务提交时间记录了多个版本格式：

• key + version1（ timestamp）* ​ key+ version2（ timestamp） Cockroach 事务实现原理 如果每个事务串行执行，事务的处理就会变的极为简单：加全局锁，执行事务。但是这种的方式效率过于底下，甚至导致不相干的事务都只能串行处理。为了提升性能，需要尽可能提升事务处理的并发度，同时又能满足事务的隔离级别要求。事务并发处理会碰到如下三种场景：

• 读写冲突
• 写写冲突
• 写读冲突

读写冲突 ​读写冲突顾名思义，对某一行或者某几行进行读取时，存在另外一个事务同时对这一行或者这几行执行写操作。 ​在数据读时，内存的Key会记录一个latest read timestamp，这是最后一次读操作对应事务的initial timestamp(事务的开始时间)，该事务每执行一个读操作，都会使用initial timestamp 与Key值中的latest read timestamp 进行比较，把该Key值latest read timestamp 更新为max(initial timestamp， original latest read timestamp)。 在存在读写冲突时，需要关心如下几点：

• 读取数据的Key(内存状态)上是否存在intend标记
• 写事务的暂定提交时间(candidate commit timestamp)和读事务的initial timestamp的先后
• 写事务在事务表(transaction table)是否处于提交状态
• 写事务的隔离级别
• 写事务的优先级别

写写冲突 写写冲突顾名思义，当前事务A对某一行或者某几行执行写操作时，存在另外一个事务B同时对这一行或者这几行执行写操作。 那么在事务运行的过程中，需要关心的几点有：

• 事务A待写入数据的Key(内存状态)上是否存在intend标记
• 事务B的在数据表中的状态是否提交
• 事务A和事务B的优先级别
• 事务A写入数据的Key在存储在磁盘的最新版本(timestamp)

写读冲突 写读冲突顾名思义，当前事务A对某一行或者某几行进行写操作时，存在另外一个事务B同时对这一行或者这几行执行读操作。 相对于读写冲突和写写冲突，写读冲突处理起来要简单很多，那么在事务运行的过程中，需要关心的几点有：

• 事务待写入数据的Key(内存状态)的last read timestamp
• 事务待写入数据的Key(内存状态)的candidate commit timestamp

理论分析 开篇讲到Serial Snapshot Isolation是在事务提交阶段做冲突检测，而Cockroach是在事务执行阶段做冲突检测。我们还需要从理论上分析上面的冲突处理流程是否符合MVCC的基础规则。 再回顾一下MVCC事务机制： Snapshot Isolation 中描述的write snapshot isolation涉及两个规则：

• 规则一： RW-spatial Overlap ： txnj writes into row r and txni
• 规则二：Ts(txni) < Tc(txnj) <Tc(txni)

Similarity to snapshot isolation ，write-snapshot isolation assigns unique start and commit timestamp to transactions and ensures that txni reads the latest version of data with commit timestamp phi < Ts(txni) write snapshot isolation 为每个事务分配一个开始的时间戳，一个事务提交时间戳，保证每一个（读写）事务读到一行版本的提交时间戳要小于事务的开始时间 ​在上面冲突处理流程中可以看到Cockroach写到Transaction Table里面的事务提交时间并不是事务运行的结束的时间，而是把事务的提交时间提前。当 Ts(txni) == Tc(txni)的时候，没有任何一个事务txnj满足Ts(txni) < Tc(txnj) <Tc(txni)，假设一个事务开始时，initial timestamp 与candidate commit timestamp 都是2，如果这个事务正常提交(不发生冲突)，假设这个事务结束的绝对时间为4，Cockroach在Transaction Table写入的事务在timestamp = 2的这个时间点提交的。也就是Cockroach里面记录事务提交时间要比事务真实运行时提交的时间要早。这样就可以满足上面的规则要求。 ​但是什么场景下允许这样做而不影响数据的一致性呢？关键在于数据库运行期间，没有其他事务关心这个事务在什么时间提交。或者说在事务运行的时间区间内，该事务修改的行没有被处在这个时间区间内的snapshot 读到过，如果出现这样的事务，SSI事务要么把自己abort掉，要么把对方的事务abort掉。 ​简单描述就是：一个SSI事务如果提交成功，那么它的Ts与Tc是相等的(Ts相当于它的initial timestamp ，Tc是它的final commit timestamp)。在Cockroach的SSI的事务是不允许自己的candidate commit time 往后推，如果SSI事务能够提交成功，那么它的candidate commit time 是跟initial commit time相等的，write snapshot isolation规则二中就不可能有一个事务txnj 满足 Ts(txni) < Tc(txnj) <Tc(txni)。也就是说一个cockroach的SSI事务提交的时候，不可能有其它事务修改了SSI事务读取的行

参考链接

• https://zhuanlan.zhihu.com/p/45734268
• https://zhuanlan.zhihu.com/p/85996983