什么是可串行化MVCC

此文转载自:https://blog.csdn.net/songguangfan/article/details/109890171

MVCC介绍

?MVCC, 即multi-version concurrency control,多版本并发控制。 它的核心思想是为每一个写操作创建一个新版本,不同的事务根据它的时间戳读取对应的版本。
?与锁机制相比,MVCC不阻塞读操作,也不阻塞写操作。很大程度上提高了事务的并发数,然后,可串行化的MVCC却可能会付出很大的回滚开销。

可串行化MVCC

  1. 假设并行事务的所有操作都是非冲突操作,如果某个事务的操作导致了冲突,则该事务需回滚;
  2. 事务时间戳顺序(从低到高)即是事务冲突可串行化的顺序,如果事务的并行操作产生了冲突,则至少一个事务需要回滚重启;
  3. 每个记录都有多个已提交版本和多个零时版本,每个版本都包含读时间戳RT,写时间戳WT,和一个提交位C,提交位表示最近一次修改是否修改被提交。

?如下图所示;每次合法的写操作都将产生该记录的一个临时版本,读时间戳为创建该版本的事务的时间戳
什么是可串行化MVCC
?时间戳产生的方式主要有以下两种

  1. 采用系统时间作为时间戳,只要确保调度器不会在一个时钟周期内调度两个以上的事务的;
  2. 采用计数器,单调递增,作为事务的逻辑时间戳

导致冲突的两种操作

?在基于时间戳的调度中,同样也需要确保,事务最后的执行顺序必须是事务串行化的顺序。然而基于时间戳还是存在冲突。

  1. 过晚的读
    两个并行事务T,U,T比U先开始
    T:RT(X)
    U:WU(X)
    如果在U在T读之前写,则T的读就导致了一个冲突,使T,U无法通过非冲突交换等价于一个串行调度(T,U)。
    什么是可串行化MVCC
  2. 过晚的写
    ?两个并行事务T,U,T比U先开始
    T:WT(X)
    U:RU(X)
    T,U的串行调度为:WT(X),RU(X)
    ?如图所示,实际调度是:RU(X),WT(X),这个调度不能通过非冲突交换等价与串行调度(T,U),因此T的写操作导致了一个冲突,T该被回滚并重启。
    什么是可串行化MVCC

可串行化多版本时间戳调度规则

?对于事务T的读写请求,按照如下规则进行调度

假设收到事务T的读请求RT(X)

?该读请求会试图读取写时间戳小于或等于TS(T)的最大写时间戳的版本V,即写时间戳小于或等于T的版本中,离TS(T)最近的版本,找到这样的版本后V,直接读取;当成功读取一个版本的时候,如果TS(T)大于该版本的读时间戳,则设置其读时间戳为TS(T),否则不改变该版本读时间戳。这种不阻塞读的策略,会导致级联回滚,即一个事务回滚,会导致语气相关的事务跟着回滚。并且,同一个事务的double-write可能会导致该事务回滚。这里也可以采取读阻塞,直到该版本C位变为真。

假设收到事务T的写请求WT(X)

调度器首先找到写时间戳小于或等于TS(T)的所有版本中写时间戳最大的版本V(该版本可能未提交),如果V的读时间戳满足:RT(X) < TS(T),则创建一个新版本,置该版本写时间戳为TS(T)(此时还没有其他事务来读取该版本,可将该版本的读时间戳设置为T时间戳,因为不会有时间戳比T小的事务来读取该版本,这样做是合理的);如果V的写时间戳等于T的时间戳,即版本V是由T创建的,则直在版本V上修改即可;如果V的读时间戳不满足要求,则回中止T,并重启。

假设收到事务的提交请求

?要求必须按照事务时间戳的顺序创建每个对象的提交版本,因此,如果一个事务提交时,在时间戳排序上,还有在它之前的事务未提交,该事务需要等待。

假设收到事务的中止请求

?当一个事务被中止时,它创建的所有版本都需要被删除,因为读阻塞在这些版本上的事务需要重新开始读操作。如果有其他事务读取了该事务创建的版本,那么这些事务也需要重启。

Read Committed隔离级别

?该隔离级别下,事务的读请求,每次读取的数据都是在该读请求发起时,是已提交的最新版本。
对于事务T的读写请求,按照如下规则进行调度

  1. 假设收到事务T的读请求RT(X)
    该请求会读取在该请求发起的时刻,最近提交的事务创建的版本,即符合条件的版本是在该请求发起时,最新的已提交版本;
  2. 假设收到事务T的写请求WT(X)
    调度器首先找到写时间戳小于或等于TS(T)的所有版本中写时间戳最大的版本V(该版本可能未提交),如果V的读时间戳满足:RT(X) < TS(T),则创建一个新版本,置该版本写时间戳为TS(T)(此时还没有其他事务来读取该版本,可将该版本的读时间戳设置为T时间戳,因为不会有时间戳比T小的事务来读取该版本,这样做是合理的);如果V的写时间戳等于T的时间戳,即版本V是由T创建的,则直在版本V上修改即可;如果V的读时间戳不满足要求,则回中止T,并重启。
  3. 假设收到事务的提交请求
    因为事务创建的版本在未提交之前是不会被其他事务读取的,并且事务只会读取已经提交的数据,因此,事务发出提交请求时,就一定可以提交。
  4. 假设收到事务的中止请求
    当一个事务被中止时,它创建的所有版本都需要被删除,因为读阻塞在这些版本上的事务需要重新开始读操作。

Repeatable Read 隔离级别

?该隔离级别下,事务的读请求,每次读取的数据都是在该事务开始之前,最近提交的数据。
?对于事务T的读写请求,按照如下规则进行调度

  1. 假设收到事务T的读请求RT(X)
    该请求会读取在该事务开始时,最近提交的事务创建的版本。记事务T的时间戳A(事务T开始的时刻),则版本列表中写时间戳(创建该版本的时间戳)小于等于A的所有已提交版本中写时间戳最大者即为符合条件的版本,即所读取的版本首先必须是已经提交了的,其次,它是离A最近的事务创建的版本;
  2. 假设收到事务T的写请求WT(X)
    调度器首先找到写时间戳小于或等于TS(T)的所有版本中写时间戳最大的版本V(该版本可能未提交),如果V的读时间戳满足:RT(X) < TS(T),则创建一个新版本,置该版本写时间戳为TS(T)(此时还没有其他事务来读取该版本,可将该版本的读时间戳设置为T时间戳,因为不会有时间戳比T小的事务来读取该版本,这样做是合理的);如果V的写时间戳等于T的时间戳,即版本V是由T创建的,则直在版本V上修改即可;如果V的读时间戳不满足要求,则回中止T,并重启。
  3. 假设收到事务的提交请求
    因为事务创建的版本在未提交之前是不会被其他事务读取的,并且,事务读取的数据都是在事务开始时已经提交的数据,因此,事务发出提交请求时,就一定可以提交。
  4. 假设收到事务的中止请求
    当一个事务被中止时,它创建的所有版本都需要被删除,因为读阻塞在这些版本上的事务需要重新开始读操作。

?按照上述规则可能出现一种不是幻读的错误,因此,它不是严格的RR隔离级别,可以参考postgreSQL的RR隔离级别,举例说明如下。
事务T1,T2,表Table1,Table1中有一个整形字段Val。
假设Table1中已经有2条记录,值分别为10,20,如下表所示:

int id int val
1 10
2 20

T1,T2的操作如下:
?T1读取第2行数据,设该行数据为X,则修改第一行数据为X;
?T2读取第1行数据,设该行数据为Y,修改第2行数据为Y;

?T1,T2的操作序列是为了将两行数据设置成相等的值,如果按照串行的执行顺序,最终2行将会是一样的值,但在Repeatable Read隔离级别下,由于读取限制,最后修改完成后,不能得到预期的效果。
?T1,T2的操作序列如下:
什么是可串行化MVCC
?按照上述操作序列,在RR隔离级别下,最后第1行记录值为20,第2行记录值为10,这与串行执行的效果是不一致的。
?上述错误是postgreSQL在第三种隔离级别下的一个Bug,postgreSQL使用predicate lock修复了这个Bug,并将具有predicate lock的Reapeatable Read隔离级别作为第四种隔离级别。

可串行化调度规则举例

  1. 使用多版本时间戳的调度规则,读操作永远不会被拒绝,因为过晚的读操作可以读更早的版本。
  2. 写操作被拒绝举例
    什么是可串行化MVCC
    ?上图有两个写时间戳为T1和T2的提交版本。
    ?操作序列为:
    ?T3 read; T3 write; T5 read; T4 write;
    a) T3请求一个读操作,它在T2版本上设置读时间戳T3。
    b) T3请求一个写操作,生成一个写时间戳为T3的临时版本。
    c) T5请求一个读操作,它访问写时间戳为T3的版本(小于T5的具有最高写时间戳的版本),同时设置该临时版本的读时间戳为T5。
    d) T4请求一个写操作,由于写时间戳为T3的版本的读时间戳T5大于T4,该写操作被拒绝。(如果该写操作不被拒绝,那么新版本的写时间戳将是T4。如果允许创建这个版本,那么这回合T5的读操作冲突,此时,T5的读操作应该使用时间戳为T4的版本。)
  1. 某个事务double-write导致回滚
    事务Ta,Tb,Tia< Tb(即Ta比Tb早开始)
    操作序列为:Ta write;Tb read;Ta write;
    什么是可串行化MVCC
    a) Ta请求一个写操作,生成一个写时间戳为Ta的临时版本;
    b) Tb请求一个读操作,它访问写时间戳为Ta的版本,该临时版本是写时间戳比Tb小的所有版本中写时间戳最大者,同时设置该版本读时间戳为Tb;
    c) Ta再次请求一个写操作,它会访问自己先前创建的版本,但是,该版本的读时间戳Tb > Ta,该写被拒绝,Ta回滚,并以一个更大的时间戳重启。

什么是可串行化MVCC

上一篇:js通用脱敏方法


下一篇:基于gin的golang web开发:docker