zz from：http://blog.sciencenet.cn/home.php?mod=space&uid=449420&do=blog&id=444736
Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson,
Jean Michel L′eon, Yawei Li, Alexander Lloyd, Vadim Yushprakh
Google, Inc.
简述 Megastore是一个存储系统，应对目前的交互在线服务之需求。Megastore以一种全新的方式混合了NoSQL数据存储的可伸缩性以及传统关系型数据库管理系统RDBMS的易用性，并同时提供了强一致性保护以及高可用性。 我们提供了完全序列化的ACID语法以及细致分区了的数据。该分区允许我们在遍布广域网的范围内，同步的复制每个写，以一个合理的延迟进行工作，并支持数据中心的无缝的故障恢复（failover），本文献描述了Megastore的语法以及复制算法。同样描述了我们Megastore构建的在支持广大范围内支持的系列谷歌服务产品时的经验。
分类和主题描述
C.2.4【分布式系统】：分布式数据库；
H.2.4【数据库管理】：系统|并行，分布式数据库
常用字 算法， 设计， 性能， 可靠性
关键字 大型数据库， 分布式事务处理， BigTable, Paxos
1. 介绍
交互式在线服务使得存储社区遇到新需求，就像桌面应用程序迁移到云所需面对的一样。诸如email这样的服务， 协同文档，以及社会网络以指数形式增长，并对现存的架构极限进行测试中。面对这些服务存储是具有挑战性的，这是由于一系列的相互矛盾的需求。 首先，因特网带来了巨大的潜在受众，所以应用就必须是高可扩展的。一个可以用MySQL 进行快速构建的服务可以是一个数据存储【参见：www.mysql.com】，但是将这个服务扩展到百万用户就需要对其存储架构作一个完全的重新设计。其次，服务必须为用户而竞争。这需要快速的开发的特性以及快速的投入市场所需的时间。第三，服务必须是响应的；即是说，存储系统必须有低延迟特性。第四点，服务必须提供给用户以一致的观点看待数据，更新的结果必须立即可视以及持久的保存。看到编辑一个云端电子表格软件消失，无论该表格如何简要，都是很差的用户体验。最后，用户期望英特网服务是24乘7小时的， 故服务必须保持高可靠性。系统对各种故障（faults）还必须对“从个别磁盘，机器失败到从路由起一直影响到整个数据中心的大规模运行中断的出错范围”保持透明（be resilient to）。 这些需求是向矛盾的。关系型数据库就用于构建应用，提供了一个功能的富集，但是关系型数据库却难于扩展到数亿的（hundreds of millions ）用户。诸如谷歌BigTable【参见：Bigtable: 就结构化数据的分布式存储系统】，Apache hadoop的 Hbase【参见：hbase.apache.org】，或Facebook的Cassandra【参见：incubator.apache.org/cassandra】一类的NoSQL 数据存储是高可扩展的，但其受限的API以及松一致性模型（loose consis-tency models ）使得应用开发变得复杂化了。由于为了确保就复制数据的一致性视图，特别是在故障发生期间，故而在远距离数据中心间复制数据的同时提供低延迟性是一个挑战。 Megastore 是一个存储系统，其开发适合了现今交互式在线服务的需求。Megastore 设计方式是全新的，由于其融合了NoSQL 数据存储的可扩展性以及传统RDBMS的易用性。它用同步重复来达到高可用性以及对数据的一致视图。简言之，它对“有足够低下延迟性的远距离复制”提供了一个完全序列化的ACID语法以支持交互应用。 我们通过RDBMS以及NoSQL的折衷，进行设计以达致前述需求：我们对数据存储进行分区并且各自复制了其分区，就分区提供了完全的ACID语法，但在其上仅有受限的一致性保证（limited consistency guarantees）。我们提供了传统的数据库特性，诸如二级索引(译注：参见扩展存储引擎)，但仅仅有那些“可以在用户可以忍受范围内的，并在延迟性限制内的”特性，并且仅支持我们的分区模式可以支持的语法。我们主张从大多数因特网服务而来的数据可以被适当的分区（诸如，用户），从而使该种方法可行，并且一个小的，但是并不简短精炼的特性集可以极大的减缓开发云应用的负担。
与传统智慧形成一个对照的是品【参见：分布式事物处理之外的生活：一个特例独行的观点，垂直 paxos 以及 主要备份复制】，我们可以使用Paxos 【参见：兼职的议会】来构建一高可用性系统，该系统就“地理分布远距离数据中心的同步复制写交互应用”提供了可信的潜在因素。虽然许多系统使用Paxos仅仅用于锁，主线程选择（master election），或者元数据复制以及配置（Congurations），我们相信Megastore 是用Paxos 的最大系统部署，在数据中心之间的每次写时复制主用户数据。Megastore 在谷歌中已近广泛的应用了数年【 参见20 】。它控制了多于30亿写以及200亿的每日读事务以及在全球数据中心上存储了大约拍字节的主数据（primary data）。
该文献的核心贡献是以下三点：
数据模型的设计，以及允许进行快速开发的、“从构建开始就具有高可用性与扩展性的”交互应用的存储系统；
Paxos 复制的实现以及就地理分布的数据中心低延迟性操作之一致算法优化，从而对系统提供高可用性；
就我们在谷歌内大规模部署Megastore 的经验给出的报告。
该文献以下述形式组织。第二节描述了Megastore 如何通过“使用分区和证明我们对许多网络交互应用的设计之充分性”来提供可用性以及扩展性。第三节提供了一个Megastore的数据模型以及特性的全局概览。第四节详细解释了复制算法，并就它们实际执行性能如何给出测量方式。第五节总结了我们开发该系统的经验。在第六节我们将回顾相关的工作。第七节进行总结。
2.面向可用性及扩展性 （TOWARD AVAILABILITY AND SCALE）
和我们需要的存储系统平台的全局性，可靠性以及规模上任意大的特性形成对比的是，我们的硬件构建块缺失地理意义上受限制的，易于出错的，且必然是能力受限的。我们必须将这些组件绑定到一个统一的全体，该全体提供将提供更高的吞吐量以及可靠性。
为了做到这一点，我们采取了双管齐下的方法（two-pronged approach）：
就可用性（availability），我们实现了一同步的，容错的“就远距离连接进行优化了的”日志复制器；
就规模（scale）而言，我们将数据分区到有巨大空间的小数据库集之中（a vast space of small databases），其中每个都有自己的复制日志存储于NoSQL数据存储的每一复制（each with its own replicated log stored in a per-replica NoSQL datastore）。
2.1 复制（Replication）
在单一数据中心的诸多主机上的复制数据通过“克服特定主机失败（host-specic failures）”提升了可用性，但这种提升效果却是递减的（but with diminishing returns）。我们仍旧必须面对外部世界互联的网络以及其驱动，把控网络的基础设施架构（infrastructure）。很节俭的构建出来的站点冒着一定级别的广泛设施中断供应（facility-wide outages ）的危险【参见：数据中心作为计算机： 数据仓库级别的机器之设计介绍】，并在地域性灾难面前是脆弱不堪的。就云存储而言，为了达致可用性要求，服务提供商必须在全球地理范围内复制数据。
2.1.1 策略（Strategies）
我们就大范围复制对通用策略进行了评估：
异步主从（Asynchronous Master/Slave） 主节点复制预写式（write-ahead）日志条目到至少一个从节点（slave）。附加日志在并行传输到从节点的主节点是被确认的。主节点可以支持快速的ACID事务，但却要在从节点的故障切换时（failover）冒时间下降或数据丢失的风险。从而需要一个一致性协议在主机间进行协调（A consensus protocol is required to mediate mastership）。
同步主从（Synchronous Master/Slave）一个主节点将在应答从节点前等待，直至改变被反映到从节点中，从而允许无数据丢失的故障恢复。主节点和从节点失效需要外部系统及时的侦测到。
优化复制（Optimistic Replication）一均匀复制组的任何成员可以接受变异（mutations）【参见：23】，且在组内以异步方式进行传播。可用性和延时性（latency）是极好的。然而，全局突变排序（the global mutation ordering）在commit时的时间是不可知的，故事务（transactions）是不可能的。
我们避免这种“在宕机时会引起数据丢失的”策略，大规模系统通常有该缺陷。我们同样还丢弃了不许可ACID原子事务操作的策略。尽管对最终一致性系统（eventually consistent systems）有操作优势，目前在快速应用开发中放弃“读-修改-写”这种特色，还是太困难。我们同样丢弃了重量级主机（heavyweight master）的操作。故障恢复需要的一系列高延迟性阶段（high-latency stages）,常常会导致用户可见的中断供应（outage），并还常伴随巨大数量的复杂性。如果我们可以在所有主机（masters）间进行区分，那又何必将容错系统构建为仲裁成员以及故障切换工作流呢？
2.1.2 进入Paxos（Enter Paxos）
我们决定使用Paxos， 其是一个经过证明了，并优化了的，容错的，无需区分主机的一致性算法【参见:工程师视角的Paxos构造，兼职的议会】。我们在一组对称的对等节点上复制了预写式日志。任何节点可以初始化读以及写。各日志附加了一个从主要复制（a majority of replicas）而来的应答块，且该复制在少数情况下会被缠住（in the minority catch up），就好象它们能使算法的内在容错性质排除对显著的宕机状态（“failed” state）的需要。一个就Paxos的新特性，将详细在4.4.1节中描述，允许在任何实时复制时进行本地复制。另一个扩展允许允许单程写（single-roundtrip writes ）。
即便Paxos拥有容错能力， 但使用单一日志仍然是有限制的。将备份遍布在广域范围内（With replicas spread over a wide are），通讯延迟性将限制总体上的吞吐量（communication latencies limit overall throughput），而且，当目前没有备份或者对写的应答的主要失效时（majority fail to acknowledge writes），前进的步伐被限制住了。在传统的把控成千上万用户的SQL数据库主机上，使用一个异步的复制日志（a synchronously replicated log）会冒大范围中断影响的风险【参见：大范围同步复制数据库的性能】。所以为了提升可用性以及吞吐量，我们使用多复制日志（multiple replicated logs），其中每一个都把控“数据集中自己的分区”。