Google-MegaStore的解读

八月 14th, 2013 by klose | Posted under 互联网应用, 海量数据存储与处理.

MegaStore是Google在BigTable之上实现了一个跨机房高可用的数据库。
它提供了类似DB的数据分布、索引的功能,实现了在EntityGroup内部以及EntityGroup之间的事务性,并且通过Paxos协议实现在DC之间多备份的一致性。

MegaStore的目标:在跨机房PB级的数据规模上,支持交互式在线服务。我们知道在Google内部的访问情况是,每天几百亿次的访问请求的应用,读写比例大概在7:1。在这样的规模上,需要达到的特性:
1)高扩展性,无论在机器扩展性还是数据规模上
2)快速的开发迭代速度,
3)低延迟
4)数据一致性
5)高可用

MegaStore的实现原理:
1)从数据库的扩展性的角度上,把大数据切分成更小粒度的数据集(EG),每个数据库保持一个独立的log,保存在BigTable当中。//这也就意味着在每个DC上有一个独立的BigTable数据库。
2)从可用性角度上讲,在跨机房之间,实现了同步、可容错的log-replicator,实现不同DC之间数据的一致性。(Synchronous Paxos)
3) 从数据库事务性的角度上,在EG内部是通过Write-Ahead-Log实现ACID,而在EG与EG之间,Megastore提供两类方式,一是二阶段提交协议,二是异步消息队列。显然,效率上讲异步消息队列更胜一筹。

MegaStore的数据模型:
1)支持基本的数据类型,以及ProtoBuf结构体
2)支持Required、Optional、Repeated语义

EG的数据被放置在BigTable连续行,处于如下的原因:
1)低延迟
2)高吞吐
3)Cache的效率
其中每一个Entity会被映射成BigTable中的一行,并且以该Row为部分Primary Key的其它表格,也会被记录在这个EG当中,这样做的一个最大的好处在于,比方Google通过Megastore提供的Gmail应用中,以userid为主键的其它信息会被快速检索出来。当然,MegaStore支持inline Indexing,会直接把索引信息存在主Row对应的Column当中,尽快加速存储。

MegaStore的Schema与具体存储之间的映射关系:
以下是Schema定义格式:
megastore-schema
Schema定义的要求:
1)支持两种类型的表格:Entity Group Root Table以及Child Tables,其中Child Tables必须reference到Root Table
2)支持Local Indexing、Global Indexing、Inline Indexing,需要注意的是LocalIndexing存储在EntityGroup内部,遵循单阶段ACID语义的一致性,而GlobalIndexing仅仅支持最终一致性,换句话说,通过GlobalIndexing查询到的数据可能不是最新的。针对Inline Indexing它属于Local Index的一种,因为这种Table的Row由两部分组成,一部分是Root Table的Primary Key,另外一部分是Indexing的Property,因此,IndexingTable的做法就是不在BigTable当中写入新的一行,在原有的RootTable中增加新的列,列名采用新表的表名+property。
3)每一个EG对应一个WAL,这样多WAL的情况,要比单WAL的情况要好很多,使得异常局部化,保证整个系统吞吐的稳定性。

注意:MegaStore的Table只是逻辑上的概念,比方说BigTable的Column Name是MegaStore Table Name和Property的组合,例如,创建的INLINE INDEX,在存储上和Parent Table放置在BigTable的同一行中。
megastore-inline-index
同时,在Root Table的BigTable单行中,还存储了transaction,replication元数据以及Transaction Log。下图是整个MegaTable Table在BigTable之上的布局图。

megastore-table-overview

OperationAccess
Entity Group内的读写操作,借助BigTable MVCC(Multi-Version Concurrent Control多版本并发控制)。例如在Hbase当中,采用了MemStoreTS控制读写数据数据的时间版本的可见性,保证读到的数据是被Commited之后的数据,保证不会读到处于uncommited的写数据。与Hbase类似,MegaStore也会有一个WAL来记录写数据的edit log,不同的是,每个EG都对应一个WAL,甚至说在每个RootTable内对应Column分别记录WAL和元数据。

read_write_op_EG
Write操作:
1)获取当前log中的可用位置。current read保证之前的commit的事务全部被applied到data。
2)数据的更新操作组合成一次commit事件,然后获得最大的时间戳,append到WAL log中。
3)在Append到WAL log之后,该事件就处于Commited状态了,写操作就可以返回客户端了。后续就是异步地实现数据的更新。

transactionForEG_write

串行化的Transaction,可以从上图的此刻的状态,如果假定此时发生了一次故障,那么
1)Transaction1是安全的,数据已经被完全提交到Data;
2)Transaction2已经提交成功,此时只需恢复从WAL到Data即可,该状态没有数据丢失。
3)Transaction3 失败,此时返回客户端提交请求失败。

Read操作:
支持三种方式的读操作:
1)Current Read: 从WAL中获取最新Committed的版本,事务系统会确保所有的Committed状态的数据都已经写入数据区,因此,该读操作方式应用在一致性要求较高的场合。
2) Snapshot Read:获取最新的、且已经被完全写入的事务的版本的数据。
3) In-Consistent Read:可以读取还没有被完全Applied状态的数据。

一个事务完整的生命周期:
1)从元数据中获取最新的版本(Committed)的数据
2)应用逻辑:Read+Modify+write
3)聚集多个Mutation到一个Log Entry(Transactions编号),分配一个最新higher的TimeStamp,然后Paxos-Replicator会负责把这部分WAL同步到其它DC,完成之后返回给客户端即可。

4)Write Mutations更新Data和Index表
5)清理不需要的WAL
ps:4)5)两步属于异步操作。

MegaStore架构图:
megastore-arch

1)MegaStore的部署包括两部分内容:客户端库、以及附属Server。

2)每一个AppServer指定一个Replica为本地的,会把Transaction直接写入本地的BigTable,然后通过Paxos算法,同步给其它的Replication Server,由其写入BigTable。

3)Client、network、以及BigTable的错误,可能会导致写操作处于中间状态。ReplicationServer会周期性检查处于中间状态的写操作,重新提交该请求。

4)Coord使用Paxos语义在跨DC之间,实现Transaction的Log提交顺序的一致性。不同的DC的ReplicationServer在并发接收EG的commit时,需要通过Coord保证全局的WAL提交顺序的一致性。

思考:
1)Google-MegaStore的架构图,Coord的作用是帮助AppServer了解整个环境中的状态,提供相关的元数据,比如,另外Replica下的一个Server之类的。
2)有些Replica不保存Data,可以理解为它只负责备份使用,待需要时做数据还原。

3) Google的这个模型,个人感觉是以应用为中心的,不是以服务为中心的架构。例如,MegaStore服务的GMail应用,会以这个应用构建一套ReplicationServer、Coord,以及对应BigTable,而不是通过这个架构对外提供统一的服务。

参考文献:

[1]ppt: http://www.slideshare.net/schubertzhang/learning-from-google-megastore-part1-12149098

[2]paper: http://research.google.com/pubs/pub36971.html

本系列文章属于Binos_ICTBinospace个人技术博客原创,原文链接为http://www.binospace.com/index.php/google-megastore-interpretation/,未经允许,不得转载。

From Binospace, post Google-MegaStore的解读

文章的脚注信息由WordPress的wp-posturl插件自动生成





Tags: , , ,

Comments

2 Responses to “Google-MegaStore的解读”
  1. 说道:

    不好意思兄弟,发现你的是胡戈戈香港机房的机,所以想测试一下评论有没有问题。

Do you have any comments on Google-MegaStore的解读 ?