Google-MegaStore的解读

问题导读
1、什么是MegaStore？
2、MegaStore的数据模型是什么？
3、MegaStore的部署包括哪些部分内容？





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定义格式：


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的同一行中。

同时，在Root Table的BigTable单行中，还存储了transaction,replication元数据以及Transaction Log。下图是整个MegaTable Table在BigTable之上的布局图。









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


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




串行化的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架构图：


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

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

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

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

3) Google的这个模型，个人感觉是以应用为中心的，不是以服务为中心的架构。例如，MegaStore服务的GMail应用，会以这个应用构建一套ReplicationServer、Coord，以及对应BigTable，而不是通过这个架构对外提供统一的服务。
参考文献：
[1]ppt: http://www.slideshare.net/schube ... tore-part1-12149098

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