引言
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单点性能:
- 事务元数据超过SO的承载量
- 序列化的消耗限制了SO的消息发送能力
本论文是解决SO单点瓶颈的问题。
背景
snapshot isolation
通过MVCC方式实现SI，如果两个事务出现了写写冲突，需要回滚一个事务。相对于serialization snapshot isolation (SSI)， SI可能出现write skew的问题。
两个事务写写冲突的充分必要条件是：
spatial overlap, 修改同一行temporal overlap，Ts(txni) < Tc(txnj) and Ts(txnj) < Tc(txni)
检查上面两个条件需要维护的事务元数据包括：
- Ts: 事务的开始时间
- Tc: 事务的提交时间
- Writes: 事务修改的行
实现SI的两种方式：
Distributed Implementations
原生的实现是在client端维护事务元数据，WW冲突检查需要使用2PC协议与所有客户端进行。2PC的性能不会随着client数量增加下降明显。而且客户端需要有容错机制。必须所有的客户端相互通信，整个集群才是可用状态，一旦一个client出问题，或者存在网络分区，则无法进行WW检查。
为了解决这些问题，事务元数据可以不在client端而是在一些专门的nodes中维护，2PC协议通过在datanode中的数据写入达到两截断提交的目的, 参考文章
Percolator就是这么实现的，事务元数据直接存放在datanode。
- 未提交事务直接写入datanode，
- Ts list直接由写入lock和data的版本号决定
- Tc list由write column的版本表示
缺点：
- 将事务元数据信息写入data节点，性能较低
- 事务回滚时，清理时间较长
Transaction Status Oracle
集中化实现使用单点服务器，SO,接收commit请求。由于SO可以监测之前的commit，故可以维护如下信息：
- Tc
- writes
SO身兼TO(timestamp oracle)的角色，假设Ts(txni)=txni，故Ts的搜集就是事务号。
uncommited writes类似percolator，存储在data nodes。
算法一：commit request
W是事务txni的修改的row集合.Tc和lastCommit是SO中的内存数据，表示事务提交的时间戳以及修改行的提交时间戳。
此算法只能串行, 不能并发。
算法二：inSnapshot
读取数据的时候，需要判断是否可见，可见性需要进行版本号的判断。
OMID设计
这一节介绍SO的瓶颈以及OMID如何解决这些问题的。
为了提升SO的能力，事务元数据量应该都存储在内存中，而非磁盘，但是元数据的增长可能超出SO的承受能力：
- 内存不足
- 每个事务的请求消息处理能力
Memory Limited Capacity
检测冲突时，需要所有row的lastcommit时间戳，内存很可能不够。
解决方法： 内存中只存最后提交的NR条数据的信息，其它数据只记录一个Tmax。
算法三：Commit request
由于Tmax是个最大值，可能存在回滚一些不冲突事务的可能性！！所以淘汰算法可以进行改进，根据当前活跃的最小的事务号进行淘汰。