Google Megastore系统事务机制

近日,Google 发布了 Megastore论文,Megastore是谷歌内部的一个存储系统,它的底层是Google 的 Bigtable,Megastore 被认为是结合了 NoSQL 与 RDBMS 的一个产品,与大多数NoSQL 产品不同的是,Megastore 提供强一致性的保证,下文推荐的是一篇讲 Megastore 的事务机制的文章,相当不错。

同时推荐另一篇讲述Google 在 Megastore 中如何通过牺牲性能来提供强一致性的文章:Comparing Google Megastore

作者: Chuanhui | 可以转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明
本文链接地址: http://www.nosqlnotes.net/archives/145

最近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两张表,主键分别为<user_id>和<user_id, photo_id>,每一个用户的所有数据构成一个Entity Group。每一个Entity Group有一个特殊的Root Entity,对应Bigtable存储系统中的一行,如User表的一行为一个Root Entity,对Root Entity的原子性操作可利用Bigtable的单行事务实现。由于同一个Entity Group连续存放,因此多数情况下同一个用户的所有数据属于同一个Bigtable子表,分布在同一台Bigtable Tablet Server机器,从而提供较高的扫描性能和事务性能。当然,如果某一个Entity Group过大,比如超过一个子表的大小,这样的Entity Group跨多个子表,从而可能分布到多台机器。

操作日志

如上图,总体上看,数据拆分成不同的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,snapshotincosistent。其中,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机制实现多个集群之间的一致性。

anyShare赠人玫瑰,手有余香,分享知识,德艺双馨!
          

无觅相关文章插件,快速提升流量