最近CSDN头条有一篇介绍Google Megastore的文章，讲得挺好，本文主要针对Google Megastore的事务实现做一个更详细的探讨。Google Megastore的底层是GFS + Bigtable系统，GFS + Bigtable解决可扩展性问题，但提供的用户接口简单：读接口只提供Get随机读取和Scan连续扫描，写接口也只能够支持单行事务。Google Megastore构建在Bigtable系统之上，通过客户端封装复杂的特性，包括事务支持，基于Entity Group的数据模型，多机房同步等。Megastore的适用场景比较广泛，如社交类，邮箱，Google日历等。
Entity Group模型
互联网应用往往可以根据用户来进行拆分，比如Email系统，相册系统，广告投放效果报表系统，购物网站商品存储系统等，同一个用户内部的操作需要保证强一致性，如要求事务，多个用户之间的操作往往可以要求弱一致性，比如用户之间发Email不要求立即收到。因此，可以根据用户将数据拆分为不同的子集分布到不同的机器上。Google进一步从互联网应用特性中抽取Entity Group概念，从而实现可扩展性和数据库语义之间的一种权衡，同时获得NOSQL和RDBMS的优点。
CREATE TABLE User { required int64 user_id; required string name; } PRIMARY KEY(user_id), ENTITY GROUP ROOT;
CREATE TABLE Photo { required int64 user_id; required int32 photo_id; required int64 time; required string full_url; optional string thumbnail_url; repeated string tag; } PRIMARY KEY(user_id, photo_id), IN TABLE User, ENTITY GROUP KEY(user_id) REFERENCES User;
在上例中，用户定义User和Photo两张表，主键分别为
操作日志
如上图，总体上看，数据拆分成不同的Entity Group，每个Entity Group内的操作日志采用基于Paxos的方式同步到多个机房，保证强一致性。Entity Group之间通过Queue的方式保证最终一致性或者Two-Phase Commit的方式实现分布式事务。我们先看单个集群的情况，暂时忽略基于Paxos的Replication机制。
单集群Entity Group内部：同一个Entity Group内部支持满足ACID特性的事务。数据库系统事务实现时总是会提到REDO Log和UNDO Log，在Megastore系统中使用REDO Log的方式实现事务。同一个Entity Group的REDO Log都写到这个Entity Group的Root Entity中，对应Bigtable系统中的一行，从而保证REDO Log操作的原子性。客户端写完REDO Log后，事务操作成功，接下来的事情只是回放REDO Log(也可称为应用REDO Log)。如果回放REDO Log失败，比如某些行所在的Tablet Server宕机，事务操作也可成功返回客户端。后续的读操作如果要求读取最新的数据，需要先回放REDO Log。
单集群Entity Group之间：Entity Group之间一般采用Queue的方式提供最终一致性，Tablet Server上有定时扫描线程，发送跨Entity Group的操作到目的Entity Group。如果需要保证多个Entity Group之间的强一致性，即实现分布式事务，只能通过Two-phase Commit协议加锁协调。
对于多个集群之间的操作日志同步，Megastore系统采用的是基于Paxos的Replication机制，对于普通的Master-Slave强同步机制，Master宕机后，Slave如果需要切换为Master继续提供服务需要首先确认Master宕机，检测Master宕机这段时间是需要停写服务的，否则将造成数据不一致。基于Paxos的Replication机制主要用来解决机器宕机时停写服务的问题，Paxos协议允许在只是怀疑Master宕机的情况下由Slave发起更新操作，虽然可能出现多点同时更新的情况，但Paxos协议将采用投票的机制保证只有一个节点的更新操作成功，从而在不停写服务的情况下实现强一致的Replication。Paxos机制本身是比较复杂的，Lamport的论文不容易看懂，建议入门的同学可以先看看Viewstamped replication，结合Paxos论文反复阅读并思考如何利用Paxos协议在工程上实现一个可靠的系统。另外一个学习Paxos协议的捷径就是加入淘宝核心系统部门的存储组，这边有架构，协议以及系统方面的牛人以及良好的技术氛围。当然，不要盲目迷恋Paxos，无论是采用什么方法实现，只要是跨越多个机房的保证强一致性的Replication，写操作的延时都是很长的，一般是百毫秒级别。
并发控制
互联网应用是一个读多写少的应用，设计并发控制时一般不允许阻塞读操作，常见的copy-on-write机制，MVCC并发控制等都是为了这个目的。Megastore实现的事务隔离级别为Serializable(可序列化)，即数据库的事务是可串行化执行的。由于Bigtable对每个Cell保留了不同版本的数据，天然适用MVCC机制。
事务执行：采用乐观锁的方式实现事务，读取时记录数据的版本号，事务提交时检查Entity Group当前的事务版本号与读取时记录的版本号是否相同，如果相同则成功提交事务，否则重试。比如有两个事务T1和T2，其中：
T1：Read a; Read b; Set c = a + b;
T2：Read a; Read d; Set c = a + d;
假设事务T1和T2对同一个Entity Group并发执行，T1执行时读取a和b，同时记录版本号为1，这时T1执行中断，T2开始执行，首先读取a和d，记录的版本号也为1，接着T2提交，这时操作的Entity Group版本号为1，因此，没有其它事务发生更新操作，T2成功提交，并更新该Entity Group的版本号为2。当T1恢复并继续执行时，发现此时操作的Entity Group版本号被修改为2，T1回滚重试。对同一个Entity Group的多个事务被串行化，Megastore之所以能提供Serializable级别的并发控制，得益于定义的Entity Group数据模型，由于同一个Entity Group同时进行的更新往往很少，事务冲突导致重试的概率很低。
MVCC：MVCC机制的主要目的是读操作不需要加锁。Megastore提供了三种读取模式：current, snapshot和incosistent。其中，current和snapshot模式读取已经成功提交的事务，且current需要读取最新的成功提交的事务，而incosistent直接读取本地数据，不用关心是否出现事务进行到一半导致数据不完整的情况。由于底层的Bigtable保留了历史版本数据，snapshot模式实现时选取已经成功应用(回放REDO Log完成)的最新事务的版本号，并从Bigtable中读取该版本号对应的数据，可能存在某些事务已经提交(已经记录了REDO Log)但没有应用(回放REDO Log)的情况，这些事务产生的效果在snapshot模式下是读取不到的。而在current模式中，需要首先确保所有已经提交的事务被成功应用。
索引支持
Megastore支持两种索引，一种是local index，另外一种是global index，其中local index和事务机制有关。每个Entity Group有一个local index，用于在Entity Group内部加快数据查询。在某个Entity Group上执行事务操作时先记录REDO Log，回放REDO Log时同时更新该Entity Group的数据和local index。
总体上看，Google Megastore论文，尤其是其中的事务机制，有些复杂，建议结合关系型数据库的并发控制，ACID等特性先思考单个集群的Megastore事务实现，再思考如何通过基于Paxos的Replication机制实现多个集群之间的一致性。