RAMP事务

最近刚发现Cassandra计划在未来支持“RAMP事务”。这是SIGMOD2014的论文《Scalable Atomic Visibility with RAMP Transactions》引入的概念。本文算是读论文的笔记吧。

RAMP的全称是“Read Atomic MultiPartition”，就是分布式的“读原子性”。文章定义出一种新的隔离性——Read Atomic Isolation。简单说就是在分布式数据库中一个对多行同时写入的事务，需要保证其他客户端在读取事务发生时要么可以见到其修改的所有行，要么都见不到。相对来说，ACID中的A是描述的是“写原子性”，写入多行的事务要么都成功要么都不成功。而Cassandra已经通过logged batch来实现了写原子性。读原子性只保证了单个写入事务在其他读取事务面前的原子性，但是多个事务同时写的话不保证隔离性。所以RA隔离性的事务可以满足诸如“不能在某个时刻同时读到A的好友里有B，而B的好友里没A的状态”这样的需求，因为设置好友关系只需要两条写入指令。经典的“银行转账”类跨行事务的需求因为涉及到并发写需要隔离出一个snapshot来判断用户是否有余额，也就是写之前还得读并且要保证另一个事务读的时候必须是当前事务更新完结果之后也就是要对读加锁，RA隔离性是搞不定的了。用隔离性的术语来说，RAMP是保证了Read Committed级别，但做不到Repeatable reads。这就意味着RAMP事务只满足了一部分需求，当然性能也会比满足大部分需求的要好。

在介绍算法前，论文对场景也做了一些限制，如不同client的事务不会互相阻塞对方、每个节点挂了都只影响其保存的数据的读写而不应该影响其他节点上数据的读写。文章称其为“scalability criteria”，后面提供的算法在保证scalability criteria的情况下保证了读原子性。

文章提出了实现RAMP的算法。总体来说思路是读事务通过读取对应数据的metadata来判断是否遇到了进行一半的写事务；而写事务使用二阶段提交来保证读事务要么都读要么都不读。文章提供了三种具体的算法，来在需要的metadata的数量和额外的读取次数之间做tradeoff。分别叫RAMP-Fast、RAMP-Small、RAMP-Hybrid。

RAMP-Fast

算法中读事务需要1-2轮通信，写事务需要2轮通信。

服务端需要存每个key的每个版本的value及对应的时间戳(ts)和metadata(md)，并且每个key存一个最近一次commit的时间戳。服务端在写入的时候有prepare和commit两个操作，prepare将key、value、ts、md存入，而commit时将对应key的latestCommit更新为max(latestCommit, ts)，prepare和commit的时间戳由客户端提供。客户端在写入的时候首先生成一个时间戳，并针对每个key找到所需要存储该key的节点去执行prepare操作，其中md为除了这个key之外该事务所要写的其他所有key的集合。每个节点都执行完prepare后再在每个节点执行commit操作，二阶段提交完成。

服务端在读的时候可以指定一个时间戳来读，也可以设0读取lastestCommit对应的时间戳的值，时间戳和metadata也一并返回。客户端在读的时候写在每个key对应节点上以ts=0来读，拿到的一坨东西挨个解析，每个key会返回该key在该节点最近一次事务提交的时间戳和当时提交的其余n-1个key，二维循环挨个比对每个key在所有读回来的事务里最大的时间戳，如果发现某个key读回来的value对应的时间戳不如在其他key所带回的md中该key的时间戳大，就再去对应节点读指定时间戳的value。因为别的节点commit过必然意味着那条事务的所有key在所有节点prepare过，肯定是能读到对应时间戳的value的，因此某次事务一旦有一个客户端读到了其中一个被commit的key必然可以保证其他key也可以去对应的节点读到，进而整个事务的所有行都是完整读到的，保证了读原子性。

简单粗暴但是需要md里带n-1个key，冗余信息较多，但来回通信的轮数较少，写需要固定两轮，读根据情况需要1轮或两轮。当且仅当某个写入事务没有完全commit完并且要读取的key中有两个key恰好分别在这次写入事务中被commit和还没commit才需要第二轮。

此外，只要保证不同client的时间戳永远不一样，而同client的时间戳也永远不一样（当然要保证单调递增但这个在单机很容易），就一定可以保证对应事务全读出来，哪怕不同节点上的系统时间戳有较大误差也不怕（无非是导致可能后写的反而被先写的覆盖因此读不到，但至少是都读不到）。因此需要在时间戳上加入client id来确保不同节电时间戳永远不会一样。

RAMP-Small

因为RAMP-Fast需要的额外空间取决于每次事务所写的key数，如果每次都写很多个key会很耗费空间。因此又有个不需要metadata的算法，但每次读取都需要两轮通信。

服务端的prepare和commit和RAMP-Fast没区别，但是读取操作要传的并非是一个特定的时间戳而是一个时间戳的集合。如果集合为空返回lastedCommit对应的版本的ts（不需要value），而如果是查询一个时间戳集合，把集合中的时间戳从大到小分别查询，一旦查到该key有某个版本的时间戳与之相等就返回这个版本的value和ts。

客户端的写入也和RAMP-Fast没区别只是不需要metadata了。第一轮读取设时间戳集合为空，把每个key的commit ts都读回来，每个key所返回的时间戳作为第二轮查询的时间戳集合。因为第一轮拿到的所有commit ts在第二轮都传入每个节点查询，会保证每个key都尽量返回这个ts集合中所包含的最大时间戳对应的版本的value。所以也不会出现某次事务有些key能读有些key读不到的情况。

读取的轮数多了，但需要的空间和传输数据的量都小了。

RAMP-Hybrid

前两组基本算法的核心思想极其正确性的证明都很容易理解——写入时每行都成功prepare才可能commit，一旦某行被commit必然可以把这次事务的全部其他行都按时间戳找出来。区别只是是否有metadata因而是否需要第二次读取。

而第三种RAMP-Hybrid算法，写入时是在metadata中记录该次事务其他key集合对应的bloom filter而非Fast中完整的key集合。于是很容易想明白，第一轮读取时把lastedCommit的ts和value和md都返回，然后把这次读取事务需要的其他key在这个bloom filter过一遍。因为bloom filter能判断一个元素是一定不在这个集合还是大概率在这个集合，所以如果返回的commit ts比其他某个key拿回来的commit ts小就不管了，如果大就过一遍bloom filter，一旦返回false就省去第二次，而返回true就去第二轮拿对应ts的value，当然可能是没有的因为bloom filter有false positive的可能。

因而Hybrid算法需要的额外空间是一个bloom filter，几乎是个比较小的常量级的空间（而非正比于每次写入事务中key的数量）并且可以根据集合数量和允许的误差度调整。并且和Fast算法中的需要第二轮读取的概率比只是大了bloom filter发生false positive时的概率。如果false positive率为0，Hybrid相当于是Fast；如果为1，会约等于退化成Small。而false positive的概率很小。

算法的核心说到这已经结束，很多人可能觉得自己写一个出来都不难。

接下来首先讲了一些实现问题，最重要的是垃圾回收，哪些数据可以回收是显而易见的——比lastedCommit小的版本的数据全可以不要了。但是存在一些旧版本的读可能还需要读小一些的数据因为他可能在读第一轮的时候不知道新的commit，这时候强制reader重新读也可以，更好的方式是旧数据留一段时间再删。然后他也说这个算法中写操作被简化成了类似Cassandra的“highest-timestamp-wins policy”，如果不想这样可以把lastedCommit变成一组版本号然后自己去靠一个特定的合并逻辑来解决之类的，但总体上感觉意义不大毕竟人工合并并不能解决真正复杂的问题。

然后又讲了一些优化，比如如果get指定时间戳的时候服务器发现这个时间戳比当前key的lastedCommit大，说明肯定有另一个事务包含这个key并且已经在别的节点commit只是没在这个节点commit，那么server可以直接把这个key也给commit了。这样其他reader再读的时候遇到不一致的概率会低。还比如一旦所有key都commit了其实metadata已经可以不用了那么就异步的清理掉。再有就是如果不着急让其他人读到，writer可以在prepare完成就返回以提高延迟，commit操作异步完成。这些应该都不难想到。

后面是一些实验结果和证明，没细看。

总结来说，这个算法解决了一个跨行事务“要么都可见，要么都不可见”的需求，注意这并不能保证这次事务的所有值都能读到，因为可能有一个新的事务覆盖了其中的若干个key，读写尤其是并发的写是完全不加锁的，思想很像cassandra一直遵循的“时间戳谁大谁赢靠NTP减少错误”。相对应的Google的Percolator是对读写进行加锁，需要一个全局递增的时间戳，因而可以处理诸如转账之类的严格要求顺序的事务，当然性能也会差一些。