MVCC和OCC

HBase MVCC

MVCC问题背景

数据库为了保证一致性，在执行读写操作时往往会对数据做一些锁操作，比如两个client同时修改一条数据，我们无法确定最终的数据到底是哪一个client执行的结果，所以需要通过加锁来保证数据的一致性。但是锁操作的代价是比较大的，往往需要对加锁操作进行优化，主流的数据库Mysql，PG等都采用MVCC（多版本并发控制）来尽量避免使用不必要的锁以提高性能。

多版本并发控制（MVCC）是一种用来解决读-写冲突的无锁并发控制，也就是为事务分配单向增长的时间戳，为每个修改保存一个版本，版本与事务时间戳关联，读操作只读该事务开始前(看到)的数据库的快照。 这样在读操作不用阻塞写操作，写操作不用阻塞读操作的同时，避免了脏读和不可重复读

本文主要介绍HBase的MVCC实现机制。
在讲解HBase的MVCC之前，我们先了解一下现有的隔离级别，sql标准定义了4种隔离级别：

1. read uncommitted 读未提交
2. read committed 读已提交
3. repeatable read 可重复读
4. serializable 可串行化

HBase不支持跨行事务，目前只支持单行级别的read uncommitted和read committed隔离级别。下面主要讲解HBase的read committed实现机制。

HBase采用LSM树结构，当client发送数据给regionserver端时，regionserver会将数据写入对应的region中，region是由一个memstore和多个storeFile组成，我们可以将memstore看做是一个skipList（跳表），所有写入的数据首先存放在memstore中，当memstore增大到指定的大小后，memstore中的数据flush到磁盘生成一个新的storeFile。

HBase的写入主要分两步：
1.数据首先写入memstore
2.数据写入WAL
写入WAL的目的是为了持久化，防止memstore中的数据还未落盘时宕机造成的数据丢失，只有数据写入WAL成功之后才会认为该数据写入成功。

下面我们考虑一个问题：
根据前面的讨论可知，假如数据已经写入memstore，但还没有写入WAL，此时认为该条数据还没有写成功，如果按照read committed隔离界别的定义，用户在进行查询操作时（尤其是查询memstore时），是不应该看到这条数据的，那HBase是如何区分正在写入和写入成功的数据呢？
我们可以简单理解HBase在每次put操作时，都会为该操作分配一个id，可以类比mysql里面的事务id，是本次put的唯一标识，该id是region级别递增的，并且每个region还有一个MVCC控制中心，它还同时维护了两个pos：一个readpoint，一个writepoint。readpoint指向目前已经插入完成的id，当put操作完成时会更新readpoint；而writepoint指向目前正在插入的最大id，可以认为writepoint永远和最新申请的put的事务id是一样的。

下面我们画图解释：
1.client插入数据时（这里的client我们可以理解为是regionserver），首先会向MVCC控制中心（MultiVersionConsistencyControl类）申请最新的事务id，其实就是返回write point++，每一个region各自拥有一个独立MVCC控制中心。
2.假设初始状态read和write point都指向2，表明目前没有正在进行的put操作，新的put请求过来时，该region的MVCC控制中心向它自己维护的队列中插入一个新的entry，表示发起了一个新的put事务，并且第一步中将write point++。
3.向client返回本次事务的id为3.
4.client向memstore中插入数据，并且该数据附带本次事务的id号：3
5.将本次的put操作写入WAL，写入成功后代表数据写入成功
6.此时移动read point至3，表示任何MVCC值小于等于3的数据此时都可以被新创建的scan查询检索到。
scan执行查询操作时，首先会向MVCC控制中心拿到目前的read point，然后对memstore和storeFiles进行查询，并过滤掉MVCC值大于本次scan MVCC的数据，保证了scan不会检索到还未提交成功的数据。这也说明HBase默认即为read committed级别，只不过是单行事务。

真正业务场景下是会有很多个client同时写入的，此时不管向MVCC申请事务id还是更新read point都会涉及到多用户竞争的情况。如图client A B C分别写入了数据de/fg/hi，有可能A C已经写入成功了，而B还未执行完，下面我们看一下MVCC控制中心是如何协调并发请求的。

MVCC控制中心

先介绍一下MVCC控制中心–MultiVersionConsistencyControl类.
它包含了三个重要的成员：
1.memstoreRead：即我们提到的read point，记录可以已执行完毕的事务id
2.memstoreWrite：即我们提到的write point，记录当前正在执行的最大事务id
3.writeQueue：一个LinkedList，每一个元素是一个WriteEntry对象。
WriteEntry类包含两个属性：
1.writeNumber：事务id
2.completed： True/False，数据写入成功后，写入线程会将其设置为True

下面详细解释MVCC控制中心针对多用户请求是如何做到同步的：

1. 当一个client写入数据时，首先lock住MVCC控制中心的写入队列LinkedList，并向其插入一个新的entry，并将之前的write point+1赋予entry的num（write point+1也是同步操作），表示发起了一个新的写入事务。Flag值此时为False，表明目前事务还未完成，数据还在写入过程中。
2. 第二步client将数据写入memstore和WAL，此时认为数据已经持久化，可以结束该事务。
3. client调用MVCC控制中心的 complete(WriteEntry writeEntry)方法，该方法采用synchronized关键字，可以理解就是同步方法，将该 writeEntry 的Flag设置为True，表示该entry对应的事务完成。但是单单将Flag设置为True是不够的，我们的最终目的是要让scan能够看到最新写入完成的数据，也就是说还需要更新read point。
4. 更新read point：同样在 complete(WriteEntry writeEntry) 方法中完成，每一个client将其对应的entry的Flag设置为True后，都会去按照队列顺序，从read point开始遍历，假如遍历到的entry的Flag为True，则将read point更新至此位置，直到遇到Flag为False的位置时停止。也就是说每个client写入之后，都会尽力去将read point更新到目前最大连续的已经完成的事务的点（因为是有可能后开始的事务先于之前的事务完成）。

看到这里，可能大家会想了，那假如事务A先于事务C，事务A还未完成，但事务C已经完成，事务C也只能将read point更新到事务A之前的位置，如果此时事务C返回写入成功，那按道理来说scan是应该能够查到事务C的数据，但是由于read point没有更新到C，就会造成一个现象就是：事务C明明提示执行成功，但是查询的时候却看不到。

所以上面说的第4步其实还并没有完，client在执行completeMemstoreInsert后，还会执行一个waitForRead(entry)方法，参数的entry就是该事务对应的entry，该方法会一直等待read point大于等于该entry的num时才会返回，这样保证了事务有序完成。

以上就是HBase写入时MVCC的工作流程，scan就比较好理解了，每一个scan请求都会申请一个readpoint，保证了该read point之后的事务不会被检索到。

备注：
HBase也同样支持read uncommitted级别，也就是我们在查询的时候将scan的mvcc值设置为一个超大的值，大于目前所有申请的MVCC值，那么查询时同样会返回正在写入的数据。

乐观并行控制协议（OCC）

如果从概念的分类来讲是另外一个角度，本文不讲分类，我们在此讨论的是单版本的occ(Optimistic Concurrency Control)，只从原理和在hudi的具体实现两个角度进行分析。

乐观并发是一个应用于事务系统的并发控制方法。OCC假设大多数的事务可以在不互相干扰的情况下完成。

1. 当事务运行时，事务不需要申请资源的锁，便可以使用这些资源。
2. 在提交之前，每一个事务都会验证没有其他的事务修改了它所读取的数据。如果检测显式存在冲突修改，提交事务将被回滚并重新开始执行。
3. OCC通常用于低数据争夺的环境下。当冲突较少时，事务的完成将会没有管理锁的消耗，并且不需要令事务等待其他的事务锁释放，其结果导致比其他的并发控制方法有着更高的吞吐量。

OCC 具体逻辑

读取阶段：

1. 每个事务维持一个私有空间
2. 在该私有空间上读和写
   1. 对于读，放到Read Set，
   2. 对于写，把写记到临时副本，放到Write Set。因为写是写到临时区的，属于未提交结果，其它事务读不到（这点是和MVCC的重要区别）

验证：

1. 获取一个事务号（递增），获取正在活跃的事务列表
2. 正在验证的事务的读集，不能和在这个事务开始之后才完成提交的事务的写集相交（如果相交，有可能新事务读到了旧的值，而不是完成提交后的值，不符合串行化规则）
3. 正在验证的事务，和其他正在活跃的事务（还未提交）比较。较晚完成读阶段的事务（逻辑上靠后的事务）的读写集，不能和较早完成读阶段的事务（逻辑上靠前的事务）的写集相交。如果读集和写集相交，有可能靠后的事务没有读到新版本的值；如果写集和写集相交，因为靠前的事务还没有写，不能保证写入顺序，因此也有可能不符合串行化规则。

提交/回滚：

1. 如果没有冲突，把临时副本区的数据更新到数据库中，完成事务提交。
2. 如果产生了冲突，解决它，通常是终止事务，回滚，尽管其他解决方法仍然可能。必须注意避免TOCTTOU bug，特别是，如果此阶段与之前的阶段并不是作为单个原子操作执行。

OCC在hudi的具体实现

写操作逻辑： HoodieSparkSqlWriter.write()

1. 先创建一个instant ,可以理解为事务时间戳
2. 创建对应的操作私有空间，其实就是创建一些文件/目录，startCommitWithTime()
3. 开始执行写操作，doWriteOperation，写到临时空间
4. 进行提交和提交之后的一些工作， commitAndPerformPostOperations
   1. 提交操作，commit()
   2. 提交之后的工作，Compaction/clustering 等
5. 重点看commit()
   1. 开启事务，本质是获取了当前的instant和最近一次完成的instant,并且赋值给client的成员变量
   2. preCommit(),主要是为了解决提交前的验证工作，判断是否有冲突，并且解决冲突
   3. commit(), 执行具体的提交动作，主要是将一些meta 信息写入hudi meta 表中
   4. postCommit(), 对一些commit进行清理和归档操作

MVCC和OCC的区别

当多个用户/进程/线程同时对数据库进行操作时，会出现3种冲突情形：

• 读-读，不存在任何问题
• 读-写，有隔离性问题，可能遇到脏读（会读到未提交的数据） ，幻影读等。
• 写-写，可能丢失更新

要解决冲突，一种办法是是锁，即基于锁的并发控制，比如2PL，这种方式开销比较高，而且无法避免死锁。

多版本并发控制（MVCC）是一种用来解决读-写冲突的无锁并发控制，也就是为事务分配单向增长的时间戳，为每个修改保存一个版本，版本与事务时间戳关联，读操作只读该事务开始前(看到)的数据库的快照。 这样在读操作不用阻塞写操作，写操作不用阻塞读操作的同时，避免了脏读和不可重复读

多版本并发控制可以结合基于锁的并发控制来解决写-写冲突，即MVCC+2PL，也可以结合乐观并发控制来解决写-写冲突。

乐观并发控制（OCC）是一种用来解决写-写冲突的无锁并发控制，认为事务间争用没有那么多，所以先进行修改，在提交事务前，检查一下事务开始后，有没有新提交改变，如果没有就提交，如果有就放弃并重试。乐观并发控制类似自选锁。乐观并发控制适用于低数据争用，写冲突比较少的环境。
多版本并发控制可以结合基于锁的并发控制来解决写-写冲突，即MVCC+2PL，也可以结合乐观并发控制来解决写-写冲突

参考：
https://www.jianshu.com/p/86246d8bee24
https://www.cnblogs.com/xuwc/p/13873611.html
https://zhuanlan.zhihu.com/p/143036656
https://www.zhihu.com/question/60278698
https://zhuanlan.zhihu.com/p/41505168