Snapshot Isolation(SI)

MVCC天生是属于SI隔离级别的。SI表示每个事务开始的时候看到的是一个独立的snapshot,在提交的时候如果write未冲突即成功。在SI下会有write skew的异常情况。

write skew可以用白球黑球的例子来说明。比如说现在有一堆球,一半是黑的,一半是白的。现在执行两个事务txn1,txn2。

  • txn1把黑球变成白球
  • txn2把白球变成黑球

如果是SERIALIZABLE隔离级别的,那就相当于事务顺序执行, 最后的结果肯定是全黑或者全白。但如果是SI,两个事务都看到相同的snapshot,并在这基础上修改,就很有可能出现还是一半黑一半白的情况。

只要在range scan的情况下会出现write skew, point update不会有这种情况。

Multi-version Concurrency Control (MVCC)

MVCC是目前最流行事务并发管理的方式。根据字面含义,DBMS会创建多个物理的tuple版本,根据事务版本选择对应的tuple版本返回给当前的事务。MVCC有很多优势,如下。

  • writer do not block reader.

    需要注意的是,MVCC并不意味只不上锁。比如一个事务t1在写某一个tuple A1,会先对A1上锁,然后生成A2。这个时候假如事务t2要读A1是不行的,只能读A1之前的版本,因为此时t1还没有提交。所以这里的读写互不阻塞指的是事务级别的,写事务不阻塞读事务,不必像2PL那样等到别的事务提交之后才能拿到锁继续执行。

  • Read-only transactions can read a consistent snapshot without acquiring locks.

    consistent指的是所有已提交的事务所做的修改。

  • Easily support time-travel queries.

    很容易追溯过去的版本

一般MVCC的单个tuple含有txn-id(tid), begin-ts, end-ts, pointer这几个字段,不同算法会略有不同。

MVCC涉及到很多数据库设计方式。比如MVCC需要和别的Concurrency Control ptotocol搭配使用,例如T/O, OCC, 2PL等 。主要有四个关键的设计决策。

  • Concurrency Control ptotocol
  • Version Storage
  • Garbage Collection
  • Index Management

另外这篇文章不考虑range scan,没有phantoms,所以下面描述的算法都是serializable isolation。该文主要讨论的是in-memory database, 和disk-based DBMS有很多区别,比如write-lock 是直接内嵌在tuple上的,当有事务修改tuple时,会将该tuple的txn-id设置为事务的tid,相当于上了锁,事务提交后将txn-id设为0。

下面是一张论文对现有数据库设计的调研结果。


Concurrency Control ptotocol

  1. Timestamp Ordering(MVTO)

    MVTO使用tid来预先定义事务执行的顺序。tuple中额外增加一个read-ts字段,用来保存最后事务读取该tuple的tid。

    • read需要检查当前事务的tid是否落在begin-ts和end-ts之间,并且该tuple没有被别的事务锁定,即txn-id=0或等于tid。如果可以读的话,将read-ts设置为tid。
    • write需要检查该tuple没有被其他事务锁定,并且tid大于当前tuple的read-ts。如果满足条件则创建新的tuple。
  2. Optimistic Concurrency Control(MVOCC)

    OCC在事务执行时不做检查。在事务提交的时候,进入Validation Phase之后,会分配一个timestamp,根据这个时间戳判断事务的先后顺序,如不符合则abort。OCC是假设事务冲突的次数会比较少。MVOCC和原始的OCC不同的是,不再维护私有的工作空间,而是生成真正的物理上tuple。具体OCC的算法可以看上一篇博客occ

    对长事务最后又abort的这种情况不友好。

  3. Two-phase Locking(MV2PL)

    事务需要在对tuple执行操作之前获取锁。write-lock就还是之前txn-id,read-lock额外增加一个字段read-cnt,代表当前读取该tuple的数量。

    • read也是需要根据tid找到一个落在begin-ts和end-ts直接的tuple版本,如果该tuple的txn-id为0的话(其他事务没有获取这个tuple的互斥锁), 则递增read-cnt
    • write只有在read-cnt和txn-id都为0的情况下,才能创建新的tuple版本。

    和常规2PL一样,关键在于如何处理死锁。

Version Storage

MVCC利用pointer将所有版本的tuple串成一个链表管理。索引总是指向链表表头。

  1. Append-only Storage

    所有版本的tuple存在同一个表上。每次write的时候,往同一个表的empty slot中添加。这种方式的区别在于链表链接的顺序。

    • Oldest-to-Newest(O2N)

      head指向oldest tuple,每次查找都需要从旧往新搜索一遍整个链表。

    • Newest-to-Oldest(N2O)

      head指向newest tuple。插入tuple的时候,需要更新index的指向,但是不需要搜索整个链表。可以让index指向一个逻辑的间接节点,避免频繁更新index。

    更适合分析性查询和大块的遍历,因为大部分tuple都连在一起。

  2. Time-Travel Storage

    和Append-only的区别就是将older tuple存到不同的表上。

    • 每次更新的时候,copy当前版本的tuple到time-travel table上
    • 然后修改main table中的master version为最新的内容,并更新指针指向旧的tuple
  3. Delta Storage

    这种方式和TIme-Travel的不同在于,每次copy的时候,仅仅copy被修改了的字段。如果需要旧的版本,DBMS需要遍历链表重建tuple。适合write-intensive的workloads,对read-intensive的事务不友好。

Garbage Collection

DBMS需要定期清理无用的tuple来提高查询效率和节省空间。满足以下两个条件,则这个版本的tuple可以被清理。

  1. 当前所有在运行的事务都看不到这个版本的tuple。
  2. 这个tuple是由被abort的事务创造的

GC可以分成两种力度

  1. Tuple Level

    • Background Vacuuming(VAC)

      开一个额外的线程,搜索所有tuple,找出无效的tuple。这种方式最常见,比较容易。也可以用bitmap来优化,追踪那些dirty block,所以vacuum线程就不需要查找所有的block。

    • Cooperative Cleaning(COOP)

      不开额外的线程。在正常事务执行过程中,遍历tuple链表的时候,同时也判断tuple是否过期,只对O2N有效。这种方式可能会带来额外消耗和漏网之鱼,一般还是会再定期开个线程遍历全表检查一下。

  2. Transaction Level

    用这种方式事务需要自己管理它们旧版本的tuple,由DBMS来决定已经结束的事务所产生的tuple是无效的(no longer visible to other txns)。

Index Management

主键索引当然永远指向version chain的head。关键在于secondary index的设计。secondary index的叶子节点的value可以指向一个间接的逻辑节点,也可以直接指向tuple的地址。

  1. Logical Pointer

    这种方式不需要经常修改index,因为它的指向永远是固定。比如说指向主键,但是需要再用主键通过primary index找到对应的tuple,这是额外的消耗。或者指向tupleid,另外维护一个数据结构将tupleid对应到物理的tuple地址。适合write-intensive。

  2. Physical Pointer

    直接指向物理的tuple地址。不需要再搜索一次,但需要频繁变更index。适合read-intensive。

Conclusion

最后论文里测出来的结果Version Storage的格式对数据库性能有很大的影响,而不是传统认为的concurrency control protocols。而concurrency control protocols中,MVTO的效果最均衡,但是生产环境中居然没有数据库用这种算法。GC算法表现最好的是transaction-level GC。索引管理方面,logical pointer总是表现的更好。具体的workloads和测试方法可以看论文。

Reference

[1] An Empirical Evaluation of In-Memory Multi-Version Concurrency Control. VLDB ‘17