Lock-free Transactional Support for Distributed Data Stores

引言

DBMS的本质是事务,缺少事务支持的只能成为data stores,比如hbase,bigtable等。Google的bigtable缺少跨行事务,导致应用开发负担很大,因此percolator系统在bigtable的基础上实现了分布式事务。

目前的大部分系统都以支持SI为最基本的需求,SI需要检测write-write冲突,检测这种冲突需要事务的元数据信息,比如commit time。事务元数据量很大,可能需要分布式存储,同时使用2PC协议协调涉及到的各个datanode,保证提交的原子性。

为了避免专门处理事务元数据信息的开销,percolator讲lock、write、commit信息直接写入数据节点。这种方式加重了data node的开销, percolator为了减缓这种开销,使用了客户端缓存写操作,批量提交的方式,但是这又使事务提交延迟时间达到了秒级别,对于OLTP系统来说,是灾难性的。另一方面,对于一个失败事务,回滚清理锁需要时间,在这个期间,会影响其它事务进行操作。

另外一种方式是lock-free的方式,使用centralized transaction status oracle (SO), SO维护事务的元数据,检查WW冲突,这样就不需要分布式锁,但是受限于SO单点性能:

  1. 事务元数据超过SO的承载量
  2. 序列化的消耗限制了SO的消息发送能力

本论文是解决SO单点瓶颈的问题。

背景

snapshot isolation

通过MVCC方式实现SI,如果两个事务出现了写写冲突,需要回滚一个事务。相对于serialization snapshot isolation (SSI), SI可能出现write skew的问题。

两个事务写写冲突的充分必要条件是:

  1. spatial overlap, 修改同一行
  2. temporal overlap,Ts(txni) < Tc(txnj) and Ts(txnj) < Tc(txni)

检查上面两个条件需要维护的事务元数据包括:

  1. Ts: 事务的开始时间
  2. Tc: 事务的提交时间
  3. Writes: 事务修改的行

实现SI的两种方式:

Distributed Implementations

原生的实现是在client端维护事务元数据,WW冲突检查需要使用2PC协议与所有客户端进行。2PC的性能不会随着client数量增加下降明显。而且客户端需要有容错机制。必须所有的客户端相互通信,整个集群才是可用状态,一旦一个client出问题,或者存在网络分区,则无法进行WW检查。

为了解决这些问题,事务元数据可以不在client端而是在一些专门的nodes中维护,2PC协议通过在datanode中的数据写入达到两截断提交的目的, 参考文章

Percolator就是这么实现的,事务元数据直接存放在datanode。

  1. 未提交事务直接写入datanode,
  2. Ts list直接由写入lock和data的版本号决定
  3. Tc list由write column的版本表示

缺点:

  1. 将事务元数据信息写入data节点,性能较低
  2. 事务回滚时,清理时间较长

Transaction Status Oracle

集中化实现使用单点服务器,SO,接收commit请求。由于SO可以监测之前的commit,故可以维护如下信息:

  1. Tc
  2. writes

SO身兼TO(timestamp oracle)的角色,假设Ts(txni)=txni,故Ts的搜集就是事务号。

uncommited writes类似percolator,存储在data nodes。

算法一:commit request

commit request

W是事务txni的修改的row集合.Tc和lastCommit是SO中的内存数据,表示事务提交的时间戳以及修改行的提交时间戳。

此算法只能串行, 不能并发。

算法二:inSnapshot

inSnapshot

读取数据的时候,需要判断是否可见,可见性需要进行版本号的判断。

OMID设计

这一节介绍SO的瓶颈以及OMID如何解决这些问题的。

为了提升SO的能力,事务元数据量应该都存储在内存中,而非磁盘,但是元数据的增长可能超出SO的承受能力:

  1. 内存不足
  2. 每个事务的请求消息处理能力

Memory Limited Capacity

检测冲突时,需要所有row的lastcommit时间戳,内存很可能不够。

解决方法: 内存中只存最后提交的NR条数据的信息,其它数据只记录一个Tmax。

算法三:Commit request

commit request

由于Tmax是个最大值,可能存在回滚一些不冲突事务的可能性!!所以淘汰算法可以进行改进,根据当前活跃的最小的事务号进行淘汰。

相关链接

percolator解读

本文标题:Lock-free Transactional Support for Distributed Data Stores

文章作者:Louis

发布时间:2017年10月17日 - 14:10

最后更新:2017年10月18日 - 09:10

原始链接:/2017/10/17/omid/

许可协议: Louis-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。