写在前面

对Google的论文译文进行了一些修改,因为做笔记不需要论文全部的内容。

正文

Megastore是谷歌一个内部的存储系统,它的底层数据存储依赖Bigtable,也就是基于NoSql实现的,但是和传统的NoSql不同的是,它实现了类似RDBMS(Relational Database Management System)的数据模型(便捷性),同时提供数据的强一致性解决方案(同一个datacenter,基于MVCC的事务实现)。

由于Megastore底层依赖于BigTable,所以Megastore数据复制的一致性是通过Paxos算法保证的。

图片加载失败


  • 为了达到高可用性,megastore实现了一个同步的,容错的,适合长距离连接的日志同步器

  • 为了达到高可扩展性,megastore将数据分区成一个个小的数据库,每一个数据库都有它们自己的日志,这些日志存储在NoSql中

  • Megastore将数据分区为一个Entity Groups的集合,这里的Entity Groups相当于一个按id切分的分库,这个Entity Groups里面有多个Entity Group(相当于分库里面的表),而一个Entity Group有多个Entity(相当于表中的记录)

图片加载失败


在同一个Entity Group中(相当于单库)的多个Entity的更新事务采用single-phase ACID事务,而跨Entity Group(相当于跨库)的Entity更新事务采用two-phase ACID事务(2段提交),但更多使用Megastore提供的高效异步消息实现。需要说明的一点是,这些事务都是在同一个机房的,机房之间的数据交互都 是通过数据复制来实现的。

图片加载失败


传统关系型数据库使用join来满足用户的需求,对于Megastore来说,这种模型(也就是完全依赖join的模型)是不合适的。原因包括

  1. 高负载交互性型应用能够从可预期的性能提升得到的好处多于使用一种代价高昂的查询语言所带来的好处。
  2. Megastore目标应用是读远远多于写的,所以更好的方案是将读操作所需要做的工作转移到写操作上面(比如通过具体值代替外键以消除join)
  3. 因为megastore底层存储是采用BigTable,而类似BigTable的key-value存储对于存取级联数据是直接的

所以基于以上几个原因,Megastore设计了一种数据模型和模式语言来提供基于物理地点的细颗粒度控制,级联布局,以及申明式的不正规数据存储来帮助消除大部分joins。查询时只要指定特定表和索引即可。

当然可能有时候不得不使用到join,所以Megastore提供了一种合并连接算法实现.

使用Megastore的应用通过并行查询实现了outer joins。通常先进行一个初始的查询,然后利用这个查询结果进行并行索引查询。

Megastore的数据结构介于传统的RDBMS和NoSql之间的,前者主要体现在他的schema表示上,而后者体现在具体的数据存储上 (BigTable)。

  • 每一个schema有一个表集合,每个表包 含一个实体集合(相当于record)
  • 每个实体有一系列的属性(相当于列属性),属性是命名的,并且指定类型,
  • 属性可以被设置成必需的,可选的,或者可重复的(一个属性上可以具有多个值)
  • 一个或者多个属性可以组成一个主键。

Megastore支持事务和并发控制。

  • 一个事务写操作会首先写入对应Entity Group的日志中,然后才会更新具体数据。
  • BigTable具有一项在相同row/column中存储多个版本带有不同时间戳的数据,所以Megastore实现了多版本并发控制(MVCC,这个包括oracle,innodb都是使用这种方式实现ACID,当然具体方式会有所不同):
  • 当一个事务的多个更新实施时,写入的值会带有这个事务的时间戳。读操作会使用最后一个完全生效事务的时间戳。
  • 读写操作不相互阻塞,并且读操作在写事务进行中会被隔离。
  • Megastore 提供了current,snapshot,和inconsistent读,current和snapshot级别通常是读取单个entity group。
    • current读操作时,事务系统会首先确认所有之前提交的写已经生效了;然后系统从最后一个成功提交的事务时间戳位置读取数据。
    • 对于snapshot读取,系统拿到己经知道的完整提交的事务时间戳并且从那个位置直接读取数据,和current读取不同的是,这个时候可能提交的事务更新数据还没有完全生效(提交和生效是不同的)。
    • 最后一个就是inconsistent读,这种读无视日志状态并且直接读取最后一个值。这种方式的读对于那些对减少延迟有强烈需求,并且能够容忍数据过期或者不完整的读操作是非常有用的。
  • 完整事务生命周期包括以下步骤:
    1. 读:获取时间戳和最后一个提交事务的日志位置
    2. 应用逻辑:从BigTable读取并且聚集写操作到一个日志Entry
    3. 提交:使用Paxos将日志Entry加到日志中
    4. 生效:将数据更新到BigTable的实体和索引中
    5. 清理:删除不再需要的数据
  • 写操作能够在提交之后的任何点返回,但是最好还是等到最近的副本(replica)生效(再返回)。

  • Megastore提供的消息队列提供了在不同Entity Group之间的事务消息。
  • Megastore支持使用二段提交进行跨Entity Group的原子更新操作。因为这些事务有比较高的延迟并且增加了竞争的风险,一般不鼓励使用。

参考文章(不是论文的参考文献)