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），其中每一个都把控“数据集中自己的分区”。
2.2 分区与本地化
为了扩展我们的复制模式以及使潜在的数据存储之性能最大化，我们给在“其数据的分区和本地化”上的应用以一个精细控制。
2.2.1实体组（Entity Group）
为了扩展吞吐量以及使消耗本地化（localize outages），我们将我们的数据分区到称之为实体组的一个集合（collection）之中【参见：分布式事物处理之外的生活：一个特例独行的观点】，其中每一个都独立的以及同步的在广域方位内进行复制。潜在的数据被存储在各个数据中心内的可扩展NOSQL数据存储（见图1）。
在实体组内的实体随着单独阶段ACID事务而有所改变（are mutated with single phase ACID transactions）（commit一条记录是通过Paxos被复制的）。在实体组上的操作可以依赖于昂贵的二阶段commits， 但典型的提升了Megastore的有效异步消息。发送实体组中的一个事务（transaction），将一个或多个消息放入一队列（queue）；事务受到实体组就自动消耗这些消息并应用确保变异（apply ensuing mutations）。
注意到我们在逻辑远距离的实体组之间异步的使用消息，而不是物理上的远距复制。所有数据中心之间造成的网络拥塞是来自复制操作，这些操作是同步的且一致的。
对一个实体组进行本地索引服从了ACID语法；那些遍布于整个实体组的“索引”（译者加）有更松散的一致性。见图二，在实体组之间的不同操作。
2.2.2选择实体组的边界 （Selecting EntityGroupBoundaries）
实体组定义了一个用于快速操作数据的所谓“优先组”（a priori grouping）。边界也用于精致定义的跨组操作。但是在单一的组内放置了过多的不相关数据，这会使不相关写来序列化（serializes unrelated writes）。
下面这些例子显示了应用以这些约束来运行的方式：
Email 各email帐户天然的形成了一个实体组。在一个帐号内部的操作是事务性的以及一致的（transactional and consistent）：一个发送了或者标记了一条消息的用户，被确保观察到变化，而无论可能的故障切换到另一备份。外部mail路由掌控介于帐户之间的通讯。
博客 一个博客应用会被实体组的许多类所精确的模拟。每一用户有一概貌（profile），自然的属于自己的实体组（naturally its own entity group）。然而，博客是协作的，且没有单一持久所有者（single permanent owner）。我们产生了实体组的第二个类，用于把控每个博客的张贴（posts）和元数据。第三个类切断各个博客声明的唯一命名（keys off the unique name claimed by each blog）。当单独用户的操作影响了博客以及概貌时(a single user operation affects both blogs and profiles)， 该应用依赖于异步消息。就类似“产生一个新的博客并声明其唯一名称”这样的低延迟性操作而言，二阶承诺（two-phase commit）更加普遍并充分的执行。
映射 地理数据就任何一致性或者合适的大小而言，是没有自然的粒度的（has no natural granularity of any consistent or convenient size）。一映射应用可以通过“将整体分割为没有重叠的补丁”生成实体组。就跨越补丁的变异而言（For mutations that span patches），该应用使用了二阶承诺（two-phase commit）使得它们原子化。补丁必须足够的大，从而使二阶事务变得很罕见（two-phase transactions are uncommon），但又必须足够的小，从而每个补丁仅需要一个小的写吞吐量（a small write throughput）。不似前述例子，实体组的数量不会随使用量的增加而增长，所以初始时必须生成足够的补丁，以为后面的扩展作充足的合计之吞度量。几乎所有构建于Megastore上的应用已找到自然的方式去描绘实体组的边界。
2.2.3 物理布局 （Physical Layout）
我们就单一数据中心里面的可扩展容错系统使用谷歌的Bigtable【参见：Bigtable: 就结构化数据的分布式存储系统】，通过将操作遍布于多行，来允许我们支持任意写和读的吞度量。
我们通过让应用去控制数据的放置地点来最小化延迟以及最大化吞吐量：通过选择Bigtable的实例以及一个实例的位置规格（specification of locality）。
为了最小化延迟，应用试着使数据保持在用户附近，并使得备份之间互相接近（replicas near each other）。它们将各个实体组赋予“特定域或最多次获取的内容”（ They assign each entity group to the region or continent from which it is accessed most）。在该域中，它们将某复制的一个三元组或者五元组（a triplet or uintuplet）赋予隔离失效领域的数据中心（with isolated failure domains）。
为了低的延迟性，缓存有效性，以及吞吐量，实体组的数据被把控在“Bigtalbe行的”连续范围内。我们的模式语言让应用控制层级数据的放置位置，将临近行间获得的数据存储在一起（storing data that is accessed together in nearby rows），或者以非规范化的方式（译注：以违反巴斯克范式的形式）存储到同一行中（denormalized into the same row）。
3. 一次MEGASTORE的旅行 （A TOUR OF MEGASTORE）
Megastore 通过将该种架构映射到一谨慎选择的特性集之上，来鼓励快速开发可伸缩的应用。该选择激励了权衡以及描述了其“开发者面需要面对的特性”结果。
3.1 API 设计哲学 （API Design Philosophy）
ACID事物简化了关于正确性的推理，但同样重要的是可以对性能进行推理（be able to reason about performance）。ACID transactions simplify reasoning about correctness,Megastore 强调了与应用开发者直觉相匹配相的“运行时消耗的成本透明API”。
规范化相关模式依赖于：在对用户操作进行服务的查询时之连接。就Megastore 的应用而言，这不是正确的模型，原因如下：
工作量的大容量交互相对于“昂贵的查询语言”，从“可预言性能（predictable performance）”受到更多的益处。
在我们的目标应用中，读相对于写占了主要地位（Reads dominate writes），故而“将工作从读的时间移到到写的时间”是值得的（it pays to move work from read time to write time）。
存储以及查询结构化数据，在诸如Bigtable一类的键值对形式存储中，是很直接的。
先将这点牢记，我们对其它的在物理位域上精致定义的控制（control over physical locality），设计了一个数据模型和模式语言。层级式的布局以及陈述式的反规范化帮助消除大多数的连接需求。查询指定扫描（scans）或者以特定表和索引为背景进行查找。
连接，当需要的时候，在应用代码中实现。我们提供了归并连接算法（merge join algorithm）之归并阶段的实现，在之中用户提供多查询（multiple queries），返回以“相同序列的同一个表的”主键；我们然后对所有提供的查询返回键的交集（the intersection of keys for all the provided queries）。我们也有并行查询的实现外部连接之应用。这典型会关涉到跟随“使用初始的查找之结果的”并行索引查找而来的一个索引查找。我们发现当二级索引查找并行的完成时，来自第一次查找的结果数量相当小（reasonably small）。就SQL形式的连接（join）, 这提供了一个有效的临时替换（stand-in）。
修改模式需要对查询实现代码进行相应的修正，这个系统（译注：指MegaStore）保证了特性是在一个对其性能含义清晰理解之上进行构建的。比如，当用户（他/她可能没有数据库方面的背景知识）自己写了一些类似于嵌入式循环连接算法时，他们很快发现在上述的基于索引的连接方法之后，加上一个索引会更加好。
3.2 数据模型 （Data Model）
Megastore 定义了一个数据模型，该模型是“一关系型数据库管理系统RDBMS的抽象元组”和“NoSQL之具体行列存储”两者的设计权衡。如在一个RDBMS中，数据模型在一个模式中进行声明，并是强类型的（strongly typed）。各模式均有一个关于表的集合，每一个都包含了一个关于条目的集合（a set of entities），这反过来包含了一个关于属性的集合（a set of properties）。属性是命名的且有带类型的值。类型可以是字符串，各种类型的数字，或者是谷歌的协议缓存（Protocol Bu ffers）【参见：谷歌数据交换格式】.它们可以获取，操作，或者重复（允许单独属性中的值之列表[a list of values in a single property] ）。一张表中的所有实体有相同的“可允许属性的”集。 一些列的属性被用于组成实体的主键，在表中该主键必须唯一。图三显示了一个就相片存储应用的示例模式。
CREATE SCHEMA PhotoShop
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;
CREATE LOCAL INDEX PhotosByTime
ON Photo(user_id, time);
CREATE GLOBAL INDEX PhotosByTag
ON Photo(tag) STORING (thumbnail_url);
图三：相片存储应用的示例模式
3.2.1 和键的预连接 （Pre- Joining with Keys）
当传统关系型模型推荐所有的主键取代理值时，Megastore 键选取用于聚集那些一起读取的实体(are chosen to cluster entities that will be read together)。每一个实体被映射到一个单独的Bigtable 行：主键值进行连接以形成Bigtable 的行键（form the Bigtable row key），并且各个剩余的属性占在其所有的Bigtable列上。
我们要注意图三中Photo 和user两个表是如何共享通用user_id前缀的。“IN TABLE User” 直接指导（directive instructs ）Megastore，将这两个表径直放置于同一个Bigtable中，并且键序列确保了Photo 图片实体紧邻相应的User用户进行存储。该功能可以递归的应用，以加速用任意深度的连接进行的查询。当然，用户可以通过对键的序列进行操作，来故意的层级化外观（force hierarchical layout）。
模式声明了键以升序还是降序的形式排列，或者防止全部排序（avert sorting altogether）：SCATTER 属性命令Megastore对每个键预先考虑两字节的哈希（the SCATTER attribute instructs Megastore to prepend a two-byte hash to each key）。以无变化的单调编码这种方式增加键，将防止横跨Bigtable服务器的大数据集上的所谓“热点聚集”（hotspots ）
3.2.2 索引（Indexes）
二级索引可以被声明于任意的实体属性之列表，在协议缓存（protocol buffers）中的域（fields）也是同理。我们在两个高级别的类之索引间进行了区别：本地与全局（见图2）。一个本地索引被当作“就各个实体组而言是隔离的索引”对待。这被用之于：在实体组内找到数据。在图三中，PhotosByTime 是一个本地索引的例子。整个索引被存储于该实体组内，并以原子化的方式进行更新，同时与首要实体数据相一致（consistently with the primary entity data）。
一个全局索引跨越了整个实体组。它用于在无需提前知晓“包含它们的实体组”的情况下，找到实体。图三中的PhotosByTag 索引是全局性的，允许发现由给定tag标记的photos，无需考虑其所有者。全局索引扫描可以读取由许多实体组拥有的数据，但并不保证反映所有的最近更新。
Megastore 还提供了附加的索引特性：
3.2.2.1 存储子句 （Storing Clause) .
通过索引来获取实体数据通常是一个分成二步的形式：首先索引被读出，找到匹配的主键，然后这些键被用于获取实体。我们提供了一种方法，将实体数据的一部分以违反范式的方式注入索引实体。通过把STORING从句加入到索引中， 应用可以从主要表中取得“在读的时候加快获取的”存储附加的特性。比如，PhotosByTag 索引存储了photo 的缩小的URL （thumbnail ），以更快的检索而无需附加的查找。
3.2.2.2 重复索引（Repeated Indexes）
Megastore 提供了这样一种能力：对反复的属性以及协议缓存子字段进行索引（index repeated properties and protocol buffer subfields）。反复索引对于子表而言，是一种新的有效选择。PhotosByTag 就是一个反复索引（a repeated index）：在标记属性中的各个唯一条目（each unique entry in the tag property ）引起一条代表Photo的索引条目之生成。
3.2.2.3 内联索引 （Inline Indexes）
内联索引提供了一种方法来从源实体逆序列化数据到相关的目标实体内：从源条目中而来的索引条目，表现为目标条目中的一个虚拟重复列（as a virtual repeated column in the target entry）。一个内联索引可以在任何“通过把目标实体的第一个主键用作该索引的第一个主键”有外键关联到其他表的这样一张表上创建，并且物理上装载数据到同一个Bigtable作为目标。
内联索引对于从子实体中萃取信息片以及快速存取存在于父实体中的数据，是有帮助的。与重复索引相结合，它们也可以用于较之维护一张多对多的链接表，更有效的实现多对多关系。
PhotosByTime 索引可以已经被实现为一个“内置于父用户表的”内联索引。这将使得数据可以以通常索引的方式来获取（accessible），或者作为User上的一个虚拟重复属性，对每一个包含Photo的“数据”（译者加）拥有时序条目（This would make the data accessible as a normal index or as a virtual repeated property on User, with a time-ordered entry for each contained Photo）。
Bigtable 的列名是Megastore 表名以及属性名的一个拼接（concatenation），允许来自不同的Megastore 表之实体，以无冲突（without collision）方式映射到同一个Bigtable行。图四显示了来自photo例子中的数据应用在Bigtable里是如何的。
就根实体而言，在Bigtable 的一行中，我们为实体组存储了事务以及重复元数据，包含了事务日志。将所有元数据存储于单独的Bigtable行，这将允许我们通过单独Bigtable事务，用原子化的方式更新它（译者注：它指元数据）
各个索引条目被表示为一个单独Bigtable 行；一项（cell ）的行键由“索引属性值与被索引的实体之主键连接”构建。比如，PhotosByTime 索引行键对每个photo来说是一个三元组（user id; time; primary key）。对重复域的索引，对每一个重复元素而言，产生了一个索引条目。比如，photo 的主键如果有三个标记（tags），将会出现在PhotosByTag索引中三次。
3.3 事务和并行控制 （Transactions and Concurrency Control）
各个Megastore 实体组以“提供序列化ACID语法的小数据库”的形式展示功能。一个事务将其变异（mutations）写进实体组的预写（write-ahead）日志，然后该变异（mutations）就被应用到数据了。
Bigtable 提供了一种“存储多个数据到相同的行/列对，而无需时间戳”这样一种能力。我们使用该种特性来实现并行控制的多版本（multiversion concurrency contro，简称 MVCC）：当一个事务中的变异被应用时，它们的交易事务之时间戳就被附带写到该值。读者用该“最近完全应用于事务的（use the timestamp of the last fully applied ）”时间戳来避免部分更新。读和写不会相互阻塞（block），读和写在事务交易期间是相互隔离开的。
Megastore 提供了流的（current），快照的，以及不一致读（inconsistent reads）。流的以及快照的读取，总是在一个单一实体组内完成。当开始一个流读（current read）， 交易系统首先确保所有前一个承诺了的写已经被用到了（committed writes are applied）；然后在最近的承诺事务之时间戳点，进行了应用度。就一个快照读而言，系统首先拣取“最后知晓的完全应用于事务的（last known fully applied transaction ）”时间戳，并从那儿开始读取（译注：是指从拣取的那个数据的位置还是拣取动作的时间？），即便一些承诺事务还没有被应用到。Megastore 同样提供不一致读，这种读会忽略日志的状态，并直接读取最新的值。这对于“有更多潜在的进取需求”的操作（for operations that have more aggressive latency requirements），以及对容忍不新鲜或者部分应用的数据是有用的（can tolerate stale or partially applied data）。
一个写事务总是以一个流读（a current read ）开始，从而决定下一个可以获取的日志位置。承诺操作收集“变异”放到一日志条目（The commit operation gathers mutations into a log entry），赋予其一个较先前那个为高的时间戳，将其附加到使用Paxos的日志。该协议使用了开放式并发（optimistic concurrency）：尽管多个写（multiple writers）可能会试图去写同一个位置，但只有一个会实际的写进去（only one will win）。剩余的将会注意到那个胜出的写， 并终止以及重试其操作（译注：“剩余的”指其余的写么？那在已经指导有写胜出后，为何要重试？）。劝告性的锁（Advisory locking）(译注：似为策略锁的总称，如乐观锁，悲观锁等)对降低争用（contention）的影响是有用的。通过“对特定对前端服务器而言的集中会话（session affinity to a particular front-end server）”的批量写可以避免争用的聚集（can avoid contention altogether）。
完整的事务生命周期如下所示：
读（Read）：获取时间戳以及最新承诺的事务之日志位置（log position of the last committed transaction）。
应用逻辑（Application logic）：从Bigtable 中读取，收集写并放入一日志条目（gather writes into a log entry）。
承诺（Commit）：用Paxos 来达到“为附加那个条目到日志（for appending that entry to the log）”这种一致。
适用（Apply）：将变异写到Bigtable中的该条目以及索引。
清除（Clean up）：删除不再需要的数据。
尽管它尽最大努力去试图等待应用的最近的复制，写操作仍然可以在承诺后的任何点上（at any point after Commit）返回到客户端。
3.3.1 队列（Queues）
队列提供了实体组之间的事务性消息。它们可以用于跨组的（cross-group）操作，可将批量的更新放入单一的事务，或者推迟工作。在一个实体组之上的事务可以在更新实体的同时，以原子化的方式发送或者接受多个消息。每个消息有一个单一的发送以及接受实体组；如果它们不同的话（译注：指那些消息的对象，实体组），那么递送（delivery）就是异步的（见图二）。
队列提供一种方式，可以执行操作影响到许多实体。比如，考虑这样一个日历应用，其中每个日历有一个独立的实体组， 并且我们想要向日历组放松一个邀请。一个单独的事务可以用原子化方式发送邀请队列消息（invitation queue messages）到许多独特的日历。每个受到该消息的日历将在其自己的事务中处理该邀请：更新邀请者的状态并删除消息。
在有全面特性的数据库管理系统RDBMS中，消息队列（message queues）已经有很长时间的历史了。我们的支持主要是在规模上（scale）：声明一个队列自动的会在每个实体组上自动的生成一个收件箱（inbox），带给我们数以百万计的终端。
3.3.2 二阶承诺 （Two Phase Commit）
Megastore 在实体组之上就原子化的更新，支持二阶承诺。由于这些事务有高得多的等待时间（latency），而且增加了争用的风险，我们通常不鼓励来自“使用有利于队列的特性”的这么一种应用。然而，它们在简化用于“实施唯一二级键（for unique secondary key enforcement）”应用编码上是有用的。
3.4 其他特性 （Other Features）
我们已经构建了一个对Bigtable来说是紧密内聚的全文索引（full-text index），在之中“更新”以及“查找”参与进“Megastore的事务以及多版本并行（multiversion concurrency）”之中。一个在Megastore 模式中已声明了的全文索引，可以对一张表的文本进行索引，或者是其它应用生成的属性进行索引。
同步复制（Synchronous replication ）对大多数常见的冲突堕落（corruptions and accidents）是一个足以有效的防护，但是备份可以在程序员的或者是操作的失误情况下变得毫无价值。Megastore的整合备份系统支持周期性的全面快照，同时就事务日志进行增量备份（incremental backup）。恢复进程（The restore process）可以将实体组的状态及时的带回到任意点（to any point in time），随意的省略所选的日志条目（在意外的删除之后）。就终止掉（expiring）删除数据而言的，备份系统遵循律令以及常识原则。
应用关于剩余的加密数据有选择权（Applications have the option of encrypting data at rest），包含了事务日志。加密对各个实体组用到了一个独特的键。我们避免了将相同的操作子赋符赋予加密键的同时，还赋予加密后的数据。
4. 复制 （REPLICATION）
该节将详细讲述我们同步复制模式的核心内容：Paxos的一个低延时的实现。我们讨论操作细节并就我们的产品服务提供了一些测量（measurements ）。
4.1 概览 （Overview）
Megastore的复制系统对“存储于作为基础的复制当中的数据（data stored in its underlying replicas）”提供了一个单一的，一致的视图。读和写可以从任意的复制来初始化，并且在无需考虑“一个客户开始于哪个备份”的情况下，ACID语义（semantics）得以保存。对每个实体组而言，复制均通过“同步复制事务日志到一个法定的备份（by synchronously replicating the group’s transaction log to a quorum of replicas）”而得以完成。“写”典型的要求一轮（one round of）数据中心之间的通信交互，以及本地运行的健康情况下之读（healthy-case reads）。流读（Current reads）有以下的 ：
一个读总是会观察到最后答复的（last-acknowledged）写。
在一个写被观察到以后，所有未来的读会观察那个写。（一个写可能会在“它被应答”之前被观察到。）
4.2 Paxos的简要总结 （Brief Summary of Paxos）
Paxos 的算法是在“单独值上的一组复制”之间达到一致（to reach consensus among a group of replicas on a single value）。这将容忍延迟的或者重新定序的消息以及由于停止而失效的复制件（It tolerates delayed or reordered messages and replicas that fail by stopping）。复制件的大部分（A majority of replicas）必须是活跃的，以及对算法取得进展来说是可达的（这种所谓的进展是指：再2F+1次的复制中，允许最多F次失效‘it allows up to F faults with 2F + 1 replicas’）。一旦通过大部分选择了值， 所有未来试图去对这个值进行的读或写会达到相同的结果（译注：什么结果？）。
由自身决定的单一值之输出的能力，对于数据库来说是没什么用的。数据库典型的使用Paxos来复制一个事务日志， 在该事务日志中，一个独立的Paxos 实例用于该日志的各个位置。新的值被写到日志中，其位置是跟随在最后选择的位置之后（the position following the last chosen position）。
最初的Paxos 算法【参见：兼职的议会】对高延迟性（high-latency）网络链接是不合适的（ill-suited），那是因为该算法需要多轮的交互。写需要在“达到一致”之前，进行至少两轮复制件之间的往返（two inter-replica round trips）：一轮用于准备，这就保留了为接下来的一轮之应答保留了权利（reserves the right for a subsequent round of accepts）。读需要至少一轮准备，以决定最后选择的值。构建于Paxos 之上的真是世界的系统降低了轮询（round trips）次数，使其成为一个可以实践的算法。我们首先回顾基于主程序的（master-based）系统如何使用Paxos，然后解释我们如何使Paxos颇为有效的做法。
4.3基于主程序的方法（Master Based Approaches）
为了最小化延迟，许多系统使用了一个称之为“方言主程序”（dedicated master）的构建，使所有的读和写都被方言化。主程序参与到所有的写之中， 所以其状态总是实时更新。它能在无需任何网络连接的情况下，对写提供当前一致状态（It can serve reads of the current consensus state without any network communication）。写可以通过“在为下一次写的每次应答的当口准备好捎带”用仅仅一轮交互而被降低其“复杂性”（译者加“复杂性” ）【参见：工程师视角的Paxos构造】（Writes are reduced to a single round of communication by piggy backing a prepare for the next write on each accept ）。主程序可以一起以批量写的方式来提高吞吐量。
在主程序之上的复制件（Reliance on a master）限制了读和写的灵活性。事务处理必须在主程序复制件（master replica）附近完成，以避免来自顺序读（sequential reads）的累积延迟性（accumulating latency ）。任何潜在的主程序复制件必须对系统的完全工作量而言，拥有充足的资源：从复制（slave replicas）直至“它们变为主复制”前，都在浪费资源。主程序的故障恢复（failover）可以需要一个复杂的状态机（complicated state machine）(译注：复杂的状态机是指有限状态机，无限状态机，或另有所指？)，以及一系列的定时器必须在服务恢复前消逝（a series of timers must elapse before service is restored ）。很难避免用户可见的运行中断（outages）（译注：宕机－备份－切换是集群系统的常见特点）。
4.4.1 快速读 （Fast Reads）
我们设置了一个前期需求：流读应当经常执行于任意复制件上，而无需复制件之间的PRC（译注：远程过程调用协议 Remote Procedure Call Protoco 简称RPC）介入。由于写经常在所有复制件之后继承，允许本地随处读取就很现实了。这些本地读让我们进行更好的利用，并给了在所有领域内的低延迟性，精确定义的读故障切换， 以及一个更加简单的编程体验。
我们设计了一个称之为协调器（Coordinator）的服务，在每个复制件的数据中心中带有服务器（with servers in each replica’s datacenter）。一协调器服务器追踪一系列的实体组，其复制件已经观察到所有Paxos写（its replica has observed all Paxos writes）（译注：复制件怎么能观察到Paxos 写动作？）。就那个集中的实体组而言，复制件有充分的状态来服务本地读（has suffcient state to serve local reads）。
写算法（write algorithm ）的指责是：保持协调器的状态（keep coordinator state conservative）。如果一个写在复制件的Bigtable上失效了，那么直到“组的键被从复制件的协调器驱逐之前（the group’s key has been evicted from that replica’s coordinator）”，不能被认为是做了承诺了（committed）。
由于协调器是简单的，它们较之Bigtable更加可靠以及迅捷。把控很少见的失效情形或者网络分区将在4.7节中进行描述。
4.4.2 快速写（Fast Writes）
为了达到快速的仅仅一轮（single-round trip）的写，Megastore 采用了“基于主程序的方法所使用的（used by master-based approaches）”前准备优化（pre-preparing optimization）。在一个基于主程序的系统中， 每个成功的写包括了一个含蓄的预备消息（implied prepare message），赋予主程序于下一个日志位置接受消息的权利（granting the master the right to issue accept messages for the next log position）。如果该写成功了话，该准备就兑现了（the prepares are honored）， 且下一个写直接调到接受的阶段。Megastore 并不使用专用主程序（dedicated masters），却以使用引导者来代替（instead uses leaders）。
我们对每个日志位置运行了一个独立的Paxos算法的实例。对每个日志位置而言的特定引导者（The leader ）是一个显著的“挑选于依附之前的日志位置之一致值（chosen alongside the preceding log position’s consensus value）”复制件。
引导者就何值会使用提议值0进行仲裁。第一个写作者（The first writer）提交值到该引导者，将获得“要求所有复制件来接受作为提议值0作为其数值（to ask all replicas to accept that value as proposal number zero）”这种权利作为奖励。所有其余写作者必须有赖于（fall back on ）二阶Paxos。
由于一个写作者必须与引导者在“提交数值到其他复制件”之前通讯，故我们对写作者与引导者之间的延迟性做了最小化。我们设计了“在围绕大多数应用从相同区域反复提交写的观察之情况下，选择下一个写的引导者”策略（for selecting the next write’s leader around the observation that most applications submit writes from the same region repeatedly）。这将导致一个简单的但是有效的启发式的方式：使用最近的复制件。
4.4.3 复制件类型 （Replica Types）
到目前为止所有的复制件都是完全复制的（full replicas），意思是说它们包含了所有的实体以及索引数据，从而可以对流读进行服务（service current reads）。我们还支持所谓“目击者复制件（a witness replica）”的这么一种说法。目击者是在Paxos循回中被选出来的（Witnesses vote in Paxos rounds），并且存储了预写式日志（write ahead log）, 但并不应用该日志，也不存储实体数据或者是索引，故而它们拥有更低的存储消耗（lower storage costs）。它们是有效的连接中断器 （tie breakers），并且当“没有足够的复制件用于形成法定人数”的时候被使用。由于它们没有协调器（coordinator），它们不会在“对一个写的应答失败”时，强迫一个附件的轮询（force an additional round trip）。
只读复制件是对目击者的一个反转（are the inverse of witnesses）：它们是包含了数据的完全快照的所谓非选举复制件（non-voting replicas）。复制件中的读反映了一个就“在近期过去的某个点上（some point in the recent past.）”而言的一致性视图。就那些可以忍受这种不是最新的读而言（tolerate this staleness），只读复制件在无写延迟的影响下，有助于散布数据到大地理范围。
4.5 体系结构 （Architecture）
图五显示了Megastore的核型组件，是一个“有两个完全复制件以及一个目击者复制件”的实例。
Megastore是通过一客户库（a client library）以及一个辅助服务器来应用的。应用连接到客户库，该客户库实现了Paxos以及其他算法：就一个读选择一复制件， 中断一个滞后的复制件（catching up a lagging replica），诸如此类。
每个应用服务器都制定了一个本地复制件。该客户库通过“直接提交事务到本地Bigtable”使Paxos持久的操作于复制件上。为了最小化大范围内的往复次数（minimize wide-area round trips）， 该库将运程Paxos操作递交到与“它们的本地Bigtables”通讯的无状态调解者复制件服务器（stateless intermediary replication servers）。
客户端，网络，或者Bigtable失效可能使写被丢弃到一种不确定的状态（leave a write abandoned in an indeterminate state）。复制服务器周期性的对非完全写（incomplete writes）进行扫描，并通过Paxos提议了一个no-op值，以将它们（译注：它们指“非完全写”）完成（bring them to completion）。
4.6 数据结构与算法 （Data Structures and Algorithms）
该节详细描述了用于“从单一值一致性同意跳跃到功能性的复制日志（make the leap from consensus on a single value to a functioning replicated log）”的数据结构和算法。
4.6.1 复制日志（Replicated Logs）
每个复制件都存储了“对组所知晓的日志条目而言的（for the log entries known to the group）”变异以及元数据。为了保证某复制件可以在“即便它是从前一个运行中断恢复的”情况下，参与进一个法定人数的写（a write quorum）。我们把日志条目存储为Bigtable中一个独立的单元（independent cells）。
当日志复制件包含了一个非完整该日志前缀时， 我们将日志复制件当作是有一个“洞”（refer to a log replica as having “holes"）。图六强调了该场景，就医单一Megastore实体组而言，有一些典型的日志条目。
日志位置0-99是完全清除了的（fully scavenged），且位置100是部分清除了的（partially scavenged），因为每个复制件被通知其余复制件将不会请求一份拷贝。
日志位置101被被所有复制件所接受。日志位置102发现了A和C中有一个赤裸的法定人数（a bare quorum）。位置103很显著的被A和C所接受，丢弃在B位置一个洞“a hole”。 一个冲突写的试图（A conflicting write attempt）在复制件A上占据了位置104，并且在B上阻碍了一致性（A conflicting write attempt has occurred at position 104 on replica A and B preventing consensus）
4.6.2 读（Reads）
在对流读（current read）进行的准备中（如在一个写之前一样），至少一个复制件必须予以更新（be brought up to date）：先前对日志进行承诺的所有变异必须被拷贝以及应用到该复制件（译注：该复制件应指该被承诺的日志之复制件）。我们将该过程称为调味料（catchup）。
省略了一些截止日期管理，流读的算法（见图7）如下：
1.本地查询（Query Local）：对本地复制件的协调器进行查询，以决定实体组是否是本地最新的。
2.发现位置（Find Position）：决定最高的可能承诺位置（the highest possibly-committed log position），并选择一个应用于该位置上的复制件（select a replica that has applied through that log position）。
（a）(本地读) (Local read) 如果步骤一显示了本地复制件是最新的话，那么就从最高接受日志位置以及来自本地复制件的时间戳处读取（read the highest accepted log position and timestamp from the local replica）。
（b）(多数读)（Majority）如果本地复制件不是最新的话（或者步骤1或步骤2a 超时了），
就从多数复制件中读，以找到任何复制件可见的最大日志位置，并捡取一个复制件用于读取。
我们选择有最多应答的，或者是最新的复制件，而不总是本地复制件。
3．调味酱（Catchup）：一旦选取了一个复制件，就将其放置到最大的已知日志为止（catch it up to the maximum known log position），如下：
（a）对每一个日志位置，若其中那些被选了的复制件不知道该一致值（For each log position in which the selected replica does not know the consensus value）， 就从另一个复制件中读取值。对任意的没有可得的已知承诺值的这么一种日志位置（For any log positions without a known-committed value available），会调用Paxos来建议一个no-op写。Paxos会驱使一个大多数复制件（a majority of replicas）在一个单独值上聚集（converge）—可以是no-op，也可以是一个先前的提议写（a previously proposed write）。
（b）顺序的在所有没有应用的日志位置上应用该一致值（Sequentially apply the consensus value of all unapplied log positions）将提高复制件“就分布式一致性状态”之状态（advance the replica’s state to the distributed consensus state）。在失效的事件情况下，在另一个复制件上重试。
4. 确认（Validate）：如果本地复制件被选取并且不是先前的最新的，就给协调器发送一个确认信息，并断言该对（实体组；复制件）对所有承诺了的写作出反馈（reects）。不要等待一个回复—如果请求失败了话，下一个读会重试的。
5. 查询数据（Query Data）：使用选择了的日志位置处的时间戳，来读取选择了的复制件。如果选择了的复制件变得不可用了（becomes unavailable），拣选一个替代的复制件，执行调味酱（perform catchup），代之以从它（译注：它指代替的复制件）读取（read from it instead）。单独的大型查询（a single large query）之结果可能很明显的拼接自多个复制件（may be assembled transparently from multiple1 replicas）。
写算法如下（如图八所示）：
1. 应答引导着 （Accept Leader）：要求引导者接受建议值0作为值。如果成功，跳到步骤3。
2. 预备（Prepare）：在所有复制件上运行Paxos预备阶段，有一个较“日志位置可见的”更高的建议值（with a higher proposal number than any seen so far at this log position）。如果有的话（译注：如果存在这么一个用于更换的最高值的话），用建议发现的最高值去更换该值（Replace the value being written with the highest-numbered proposal discovered），
3. 接受（Accept）：要求其余复制件接受该值。如果“这种要求”（译者加）在复制件大多数上失败了，在随机后退后（after a randomized backoff）返回步骤2。
4. 去效（Invalidate）：使在所有不接受该值的复制件上的协调器失去效用（Invalidate）。
该步骤中的错误处理在4.7节中描述。
5. 应用（Apply）：在尽可能多的复制件上应用该值的变异。如果被选择的值和最初提议的值不同话， 返回一个冲突错误（a conflict error）。
步骤1实施了4.4.2节中所谓“快速读”。写作者使用单一阶段的Paxos，通过“以建议值0发送一个接受命令”跳过预备消息（Writers using single-phase Paxos skip Prepare messages by sending an Accept command at proposal number zero）。下一个“在日志位置n选择的”引导者复制件，将对“在位置n+1处，用于提议0的值”仲裁（arbitrates the value used for proposal zero at n + 1）。由于多个提议者会提交“建议值0”， 在该复制件处序列化就确保了只有一个值与特定日志位置的提议值相一致（corresponds with）。
在传统数据库系统中，承诺点（the commit point）（当变化是持久的时候）与可见点（the visibility point）（当读可以见到一个变化，以及当一个写作者可以就成功被通知时）是同一回事。在我们的写算法里，承诺点是在步骤3后，当写已经在Paxos轮中胜出以后（when the write has won the Paxos round），只有在“所有的完全复制件已近接受了，或者使它们的协调器失效”后，写才能够被答复，且该变化才能被应用。在步骤4之前的确认（Acknowledging）会破坏我们的一致性保证：一个在“其去效被跳过了（whose invalidation was skipped）”的复制件之上的流读可能对观察确认写来说会失效（might fail to observe the acknowledged write）。
4.7 实用的协调器 （Coordinator Availability）
协调器进程运行于各个数据中心之中，并保持它们的本地复制件的状态。在以上的写算法中，每个完全复制件必须获着接受获着使其协调器去效。故而它可能会显现出：任何单独复制件失效（Bigtable和协调器）将会导致无效性（unavailability）。
在实践中这不是一个问题。协调器是一个“简单的没有外部依赖以及持续存储的（no persistent storage）”进程，故而它较之一台Bigtable服务器而言，更趋向稳定。然而，网络以及主机的失效仍然可能使协调器难以利用。
4.7.1错误检测 （Failure Detection）
为解决网络分区， 协调器使用了一个带外（out-of-band）协议来识别当其它协调器起来，健康的以及通用可达的。
我们使用谷歌的Chubby lock服务【参见：Chubby lock服务 — 松耦合分布式系统】：协调器在启动时，从远距数据中心处获取特定的Chubby locks。就处理需要而言，一个协调器必须把控其锁的大多数。如果它曾经“从碰撞获着网络分区而来的”遗失其锁的大多数（If it ever loses a majority of its locks from a crash or network partition），它会回复其状态到一个默认的保留（revert its state to a conservative default），该复制件的随后的写必须从复制件的大多数中（from a majority of replicas）检索出日志位置，直至该锁再次获得，以及它的协调器条目被再次生效（are revalidated）。
写作者通过“测试一个协调器是否失去了其锁”而从协调器失效中隔绝出来了：在那么一种场景中，一个写作者知道协调器其会考虑其本身是否在再次获得它们时无效了（a writer knows that the coordinator will consider itself invalidated upon regaining them）。
该算法冒了一个短小写中断运行风险（数十秒），当一个数据中心包含活跃的协调器突然变得不能利用了时 — 所有的写必须等待协调器的Chubby locks在写可以完成前终止掉（很像等待一个对触发器而言的主线程之故障恢复’ waiting for a master failover to trigger’）。不似主线程故障切换，读和写可以在协调器的状态被重新构建的时候，平滑的进行处理。这种短小罕见的运行中断风险比快速本地读所允许的稳健状态更加合理（This brief and rare outage risk is more than justified by the steady state of fast local reads it allows）。
协调器的活跃性协议对于非对称网络分区来说是脆弱的。如果一个协调器可以在其Chubby locks上保持租赁协定（leases），但是在其他方面却失去了和申请人的约定（but has otherwise lost contact with proposers），其后被影响到的实体组会有经历一个写的运行中断（experience a write outage）。在该场景中，一个操作者执行了一手工的步骤去使“部分分离协调器（partially isolated coordinator）”失效。我们只是在没几次时（only a handful of times）对付过这种情况。
4.7.2 确认竞赛 （Validation Races）
关于可获得性的主题还有一点要说明的是，为了对协调器读和写之协议必须处理一系列竞争条件（race conditions）。去效的消息（Invalidate messages）总是安全的，但是确认消息（validate messages ）必须小心的进行处理。在“为先前写的确认以及为后来写的去效”之间的竞赛被协调器通过“发送相关于行动的日志位置（sending the log position associated with the action）”保护起来。更高的计数去效（Higher numbered invalidates）总是胜出较低的计数确认（ower numbered validates）。相关于“在位置n上的写作者引发的去效（an invalidate by a writer）”与“在某个m<n的位置上的确认（a validate）”之间的冲突同样有一个竞争。我们用一个“为该协调器之各个体现（for each incarnation of the coordinator）”的唯一纪元数侦测到了碰撞（detect crashes using a unique epoch number）：确认（validates ）仅仅在“纪元自从最近的读取协调器后保持未变”情况下可以允许修改协调器的状态。
总结一下，使用协调器去允许从任意数据中心快速本地读，从可用性的影响方面而言，并不是免费的。但实际中大多数运行协调器产生的问题被以下几个因素所减轻下来（are mitigated by）：
协调器相对于Bigtable 服务器而言是更加轻巧的处理程序，有少得多的依赖关系，并因之其自然就更加可用。
协调器是很简单，均匀的工作量使得它们很低廉，且对规定时可预测的（predictable to provision）。
协调器的轻量级网络通信量允许以可信连接方式使用一个高级网络QoS。
操作员可以在维护或者是不健康的时间段上集中的使协调器失效。这对于某些监控信号是自动的。
Chubby locks的法定参与数侦测到大多数网络分区以及节点是不可用的。
4.8 写吞吐量 （Write Throughput）
我们的Paxos 实现在系统的表现行为中有一些有趣的权衡。多个数据中里面的应用服务器中，有对“同时的对同一个实体组和日志位置”的多个初始读（initiate writes）。它们中除了一个，都会失效，并且需要对它们的事务进行重试。由同步复制件加与的（imposed by synchronous replication）的不断增加的延迟性（The increased latency）增加了就一个给定的“每实体组承诺比率（per-entity-group commit rate）”而言的冲突的可能性。
将那个比率限制在“每实体组之每秒的少数写”中，将导致不显著的冲突比率（yields insignificant conflict rates）。就“其实体被小数量的用户一次性的操控（are manipulated by a small number of users at a time）”的应用而言，该限制无关紧要。我们目标客户的大多数“通过对实体组更细微的分片；或者通过确保复制件被放置在相同的区域，降低了延迟性以及冲突比率”来衡量写吞吐量。
带有一些服务器的所谓“粘性”（stickiness）的应用各尽其能的（are well positioned to）将用户之操作批量的放入更少的Megastore 事务中。大块处理Megastore 队列消息（Megastore queue messages）是一种常用的批处理技术（a common batching technique），降低了冲突率，增加了聚合吞吐量（aggregate throughput）。
就那些必须定期的胜出每秒少数写的组而言（For groups that must regularly exceed a few writes per second），应用可以使用精致定义的“由协调器服务器分发的”建议锁（advisory locks）。对事务顺序化成背靠背形式（Sequencing transactions back-to-back ）避免了相关于“重试，以及侦测到冲突时的二阶Paxos 之逆转”的延迟。
4.9 有关操作的一些议题 （Operational Issues）
当某特定完全复制件（full replica ）变得不可信（unreliable）或者失去连接性（connectivity），则Megastore的性能会受到其侵蚀（performance can degrade）。对于这样一些失效，我们有如下所示的一些方法应对：远离疑似有问题的复制件（problematic replica）的路由用户（routing users）会使它的协调器失效，或者使它整个失效。实际中，我们依赖多个技术的组合，其中各个都有其权衡。
首先而且是最重要的对于一个运行中断的反馈就是使Megastore的客户端在受影响的复制件上“通过对临近另一个复制件的应用服务器的重新路由通讯（by rerouting trffic to application servers near other replicas）”使其失效。这些客户端典型的经历了相同的中断运行，都影响到了它们下面的存储栈（storage stack），并可能从外部世界角度而言不太能够达到。
不健康的协调器服务器如果想要持续把控它们的Chubby locks，那么“重新路由通讯单独来说（Rerouting traffic alone ）”就是不充份的。下一个针对复制件的协调器而言的反馈就是，确保问题对写延迟的影响降到最低限度。（见4.7节在更详细的尺度上描述了该问题。）一旦写作者从失效的复制件协调器当中被挽救过来（Once writers are absolved of invalidating the replica’s coordinators），那么不健康的复制件对于写延迟的影响范围就被先制住了。只有初始的“接受引导者（accept leader）”会涉及依赖于复制件的写算法，并且我们维护了一个“在求助于二阶Paxos前，以及在为下一个写去提名一个更健康的引导者前”不宽裕的截止日期（a tight deadline）。
一个更严厉的和少有使用的动作（action）是使该复制件整个的失效：无论是客户端还是复制服务器都不会试图去和它通讯。尽管顺序化复制件看上去似乎很吸引人时，但首要的影响是对可用性的冲击（ a hit to availability）：少于一个的复制件有能力帮助写作者形成一个法定的人数（one less replica is eligible to help writers form a quorum ）。有效的用例是当试图操作可能引发危害时 — 比如，其下运行的Bigtable 严重超负荷工作的时候（ severely overloaded）。
4.10 产品度量 （Production Metrics）
Megastore 已于数年中应用部署于谷歌内部：多于100个产品应用使用了Megastore 作为它们的存储服务。在该节中， 我们就其范围， 可用性， 以及性能给出报告。
图九显示了可用性的分布，就基于各个应用的，在各个操作之上的度量（ measured on a per-application, per-operation basis）。 我们的大多数客户看到了相当高层的可用性（至少五个九），而无需考虑稳固的“有关机器失效的”流（despite a steady stream of machine failures），网络打嗝（Network hiccups）（译注：何意？），数据中心运行中断， 以及其他失效（faults）情况。我们示例的底部（The bottom end of our sample ）包含了一些仍然“处于测试中和带有更高容错的批处理应用的”前产品（pre-productio）应用。
平均读延迟性达到数十个毫秒，取决于数据的量，显示了大多数读取都是本地的。大多数用户看到的平均写延迟性，基于“数据中心之间的物理距离， 需要写的数据的大小， 以及完全复制件的数量”而定，约在100到400毫秒之间。图10显示了读和承诺操作的平均延迟性的分布。
5. 经历 （EXPERIENCE）
在开发该系统的过程中，重点强调了可测性（testability）。代码配备了许多（但是比较廉价的）断言以及日志动作（assertions and logging），并有一个彻底的单元测试覆盖。但最有用的bug查找装置还是我们的网络模拟器：所谓“伪随机测试框架”。它可以探索所有可能的序列空间，并延缓模拟节点或者线程之间的通讯，在给定相同种子的情况下，铁定会给出相同的行为。Bugs通过“找到有问题的事件序列来触发一断言失败（或不正确的结果）”而暴露出来（Bugs were exposed by finding a problematic sequence of events triggering an assertion failure ），通常配以足够的日志以及跟踪信息来诊断（diagnose）该问题，这被加到单元测试的测试套件之中（Added to the suite of unit tests）。当关于排程状态空间（scheduling state space）的一个彻底搜索是不可能的了话，该伪随机模拟较之另外意义上的实践，会进行更多的探索（the pseudo-random simulation explores more than is practical by other means）（译注：何意？）。通过每个晚上的运行模拟出运行数千小时，该测试发现了许多令人惊讶的问题。
在现实世界的部署中，我们观察到了期望的特性：我们的复制件协议优化（replication protocol optimizations）确实在大多数时间提供了在“单轮WAN往复之日常开支（about the overhead of a single WAN roundtrip）”内的本地读，本地写。大多数应用已经发现延迟性是可以忍受的。一些应用被设计成对用户隐藏了写延迟（hide write latency），且少数必须小心翼翼的选择实体组边界，以最大化它们的写吞吐量（write throughput）。这会导致主要的操作上的优势：Megastore的延迟性之尾（latency tail）较之“其底下的层（the underlying layers）”显著的更短了，并且大多数应用经得起“有很少甚或没有人工干预的”计划的与未计划的服务中断。
大多数应用使用Megastore 模式语言来对它们的数据建模。其中一些已经在Megastore 模式语言中实施了它们自己的实体属性值，然后使用了它们自己的应用逻辑来对其数据建模（最著名的有，Google App Engine 【参见：谷歌应用引擎】）。一些使用了这两种方式的混合。让动态模式构建于该静态模式之上，而非以其它方式构建，将使得大多数应用在受益于静态模式带来的“性能，可用性以及完整性福利”的同时，仍然考虑到那些需要动态模式选项的需求。
术语“高可用性（high availability）”常常强调“较之个体系统而言，屏蔽了错误（mask faults）而令系统集更加的可靠（a collection of systems more reliable）”这样一种能力。尽管容错（fault tolerance ）是一个较高级别的目标期望，但其本身仍然有其弱点：它常常隐含了问题背后的持久错误（it often hides persistent underlying problems）。我们组里面有一种说法：“容错就是容忍错误（Fault tolerance is fault masking）”。当我们系统的恢复力（the resilience of our system）配以（coupled with）不充份的警戒（insufficient vigilance）时，在追踪深层的错误（underlying faults）时会导致期望以外的问题出现，这种情况太常见了：小的，暂时的（small transient ）处于持续非正确问题顶端的错误（on top of persistent uncorrected problems ）会引发更大的问题。
另外一个议题就是流控制（flow control）。这是一种算法：该“能容忍有缺陷的参与者的”这么一种算法可以不去注意较慢的那个（ An algorithm that tolerates faulty participants can be heedless of slow ones）。（译注：何意？）理想情况下， 一个分离的机器之间的集合的进展最多只能和“最低效的成员一样快”（ make progress only as fast as the least capable member）。（译注：短板效应）如果缓慢性被解释为一种可以容忍的故障（slowness is interpreted as a faul，and tolerated）， 那么大多数机器中的最快的那个（the fastest majority of machines ）将会以它们自己的步调来处理请求，只有在“被落伍者尽力追赶上”这么一个过程的装载减慢下来，才会达到平衡（equilibrium ）。我们称这种现象为“异常链帮派节流（anomaly chain gang throttling）”，会唤起“一组逃脱中的其进展只能和它们捕获流浪者的速度一样快的罪犯”的一副图像。（evoking the image of a group of escaping convicts making progress only as quickly as they can drag the stragglers）。
Megastore采用的预写式日志所带来的一项福利是：降低整合外部系统的难度（the ease of integrating external systems）。任何幂等的操作（idempotent operation ）（译注：何种幂等操作？）都可以在应用一个日志条目时进行介入（be made a step in）。
为使更复杂的查询取得一个好的效能，那就需要关注Bigtable的物理数据展示（layout）。当查询很慢的时候，开发者需要检查Bigtable 栈，以了解为何他/她们的实际查询性能低于其期望。Megastore 不会对“块大小， 压缩， 表分割， 本地组”强加特定的策略，或者是其它Bigtable提供的调优控制手段。取而代之的，我们需要的是这样的控制，提供给应用开发者一种优化性能的“能力（以及担当 ‘burden’）”。（译注：授之与渔）
6. 相关工作 （RELATEDWORK）
最近，在NoSQL 数据存储领域有不断增长的迎合“有关大型网络应用的需求”的兴趣。代表性的工作包括了Bigtable 【参见：Bigtable: 就结构化数据的分布式存储系统 】，Cassandra 【参见：Apache Cassandra官网】以及Yahoo PNUTS 【参见：PUNTS:雅虎的宿主数据服务平台】。在这些系统中， 可扩展性（scalability ）是通过牺牲传统关系型数据库管理系统RDBMS的一个或者多个属性来达到的，比如，事务，模式支持， 查询能力【参见：Scads: 社会计算应用的独立扩展存储，就大数量的小型应用而言的一个可扩展数据平台】。这些系统常常缩减事务的范围至单独键获取的粒度，从而在构建应用的时候设置了一些显著的障碍【参见：G-store: 一个在云中对事务性多键存取的可扩展数据存储，与 23】。一些系统扩展了事务的范围到单独一张表中的多个行，比如Amazon SimpleDB 【参见：Amazon SimpleDB】运用了“域（domain ）”这么一种观念作为事务性单元（the transactional unit）。但是这种努力仍然有其限制，这是因为事务不可以跨越表或者任意的范围（transactions cannot cross tables or scale arbitrarily）。还有一点要说明，大多数当今的可扩展数据存储系统缺少关涉到RDBMS的富数据模型，这样就“不可避免的”（译者加）增加了开发者的负担。从数据库和可扩展的数据存储两者混合而来的价值（merits），Megastore在一实体组内提供了事务性ACID 保证，并提供了一个灵活的“有用户定义的模式（user-defined schema）， 数据库风格（database-style），全文检索（full-text indexes）以及队列（queues）这些形式的”数据模型。
在远距地理范围域之间的分布的数据中心之间进行数据复制对于“提高最先进的（state-of-the-art）存储系统的可用性”是很昂贵得。大多数流行的数据存储系统使用带有更弱的一致性模型的（a weaker consistency model）异步复制计划（asynchronous replication schemes）。比如，Cassandra 【参见：Apache Cassandra】，HBase 【参见：Apache HBase】， CouchDB 【参见：Apache CouchDB】，以及Dynamo 【参见：Dynamo: amazon的高可用键值存储】使用了一个最终一致性模型（an eventual consistency model）以及PNUTS 使用了所谓“时间线”一致性（"timeline" consistency）【参见：PUNTS:雅虎的宿主数据服务平台】。作为对比，同步复制确保了广域网（wide-area networks）之上的强事务语义（strong transactional semantics）并且“同步复制”（译者加）强化了流读的性能。
同步复制件在传统的关系型数据库系统RDMMS中，表现出了一种性能挑战而且难于扩展【参见：复制的危险以及一个解决方案】。一些建议的变通方法允许经由异步复制而表现出强一致性（allow for strong consistency via asynchronous replication）。一种方式使得“在它们的财物（effects）被复制”之前就进行了完全的更新。将同步延迟传送到（Passing the synchronization delay on to）需要读取该更新状态的事务【参见：针对一个契约的强一致性复制】 。另一种方式路由（approach routes）在“在复制件的一个集合中分布只读事务（distributing read-only transactions among a set of replica）”的同时【参见：Ganymed:就事务性网络应用而言的扩展性复制】，写到一个单一的主程序（master ）。这些更新是异步的传送到（propagated）剩余的复制件的，并且“读”或者被延迟了或者发送到“那些已经被同步化了的（that have already been synchronized）”复制件。一个最近的有关“有效的同步复制（effcient synchronous replication int）”的提议引进了一个所谓“排序处理器（an ordering preprocessor）”，该处理器确定性的对进入之事务进行排产（chedules incoming transactions deterministically），故而它们可以独立的应用于多个“最终结果完全相同的”复制件（applied at multiple replicas with identical results）【参见：数据库系统中的决定论案例】。这些同步化负担被转移到“其本身会被构造成有可扩展性的（which itself would have to be made scalable）”处理器（译注：指排序处理器么？）。
直到现在，很少有使用Paxos来进行实现同步复制的。SCALARIS是一个使用Paxos承诺协议的例子【参见：事务承诺一致性】，从而对一分布式哈希表实现了复制【参见：就DHT上的事物而言之强化的paxos承诺】。Keyspace【参见：Keyspace：一个持续复制的，高可用的键值存储，以及 http://scalien.com/whitepapers/.】同样使用了Paxos来实现在一个通用键值存储上的复制。然而这些系统的可扩展性和性能不为公众所知。Megastore有可能是第一个基于“满足扩展性与满足云中的扩展网络应用性能需求的跨数据中心的（译注：云端还是云中？）”以Paxos复制实现的大规模尺度存储系统。
传统数据库系统提供了成熟的和精致的数据管理特性，但是对大尺度交互为目标的服务就显得有些困难了，如所述文献【参见:就大数量的小应用而言的一个可扩展数据平台】。开源数据库系统，诸如MySQL【参见：2009年时的www.mysql.com】尚不能达到我们所需要的尺度【参见：用YCSB来标记云服务系统】，同时昂贵的商用数据库系统，如Oracle【参见：2007年时的ORACLE】明显提升了大规模部署于云端的拥有总消耗。进一步而言，它们两者（译注：开源数据库MYSQL和ORACLE）都没有提供容错同步复制机制【参见：MySQL集群，11】，而该机制却是构建云中的交互式服务的关键技术（which is a key piece to build interactive services in the cloud）。
7. 总结 （CONCLUSION）
该文献中我们提出了Megastore，一个可扩展的，高可用的数据存储设计，迎合了交互式的英特网服务的存储需求。我们使用Paxos来同步广大范围内的复制，提供了就个体操作而言的轻量级的以及快速的故障恢复（failover）。跨广域范围的分布式同步复制之延迟性惩罚, （is more than offset by）已经被“单独系统图像的便利以及运营商级的可用性之操作收益（the operational benefits of carrier-grade availability）”所抵消了。我们使用Bigtable作为我们的可扩展数据存储，同时增添了更丰富的原语（primitives），诸如ACID, 事物（transactions），索引（indexes），以及队列（indexes）。将数据库分区成实体组子数据库，会对大多数操作提供熟悉的事物特性，与之同时允许存储与吞吐量的可扩展性。
Megastore拥有超过100项的应用产品，面对了谷歌内部与外部用户，并为更高层的产品提供了架构（infrastructure）。这些数量以及应用各异的现象是Megastore易于使用（ease of use），朴拙（generality），以及有力（power）的显证，我们希望Megastore显示了一种可行性，这是一个以中间立场（a middle ground in）而言的特性集，以及与当今的可扩展存储系统相融的复制（replication）。
8. 致谢 （ACKNOWLEDGMENTS）
译者略
9.参考
（译注：原文文献参考号）
【11】Y. Amir, C. Danilov, M. Miskin-Amir, J. Stanton, and
C. Tutu. On the performance of wide-area
synchronous database replication. Technical Report
CNDS-2002-4, Johns Hopkins University, 2002.
【20】J. Furman, J. S. Karlsson, J.-M. Leon, A. Lloyd,
S. Newman, and P. Zeyliger. Megastore: A scalable
data system for user facing applications. In ACM
SIGMOD/PODS Conference, 2008.
【23】S. Gustavsson and S. F. Andler. Self-stabilization and
eventual consistency in replicated real-time databases.
In WOSS ’02: Proceedings of the rst workshop on
Self-healing systems, pages 105{107, New York, NY,
USA, 2002. ACM.
（完）
其他文献：
http://wenku.baidu.com/view/a465cc260722192e4536f671.html# megastore初探
http://cloud.csdn.net/a/20110216/291968.html Google Megastore分布式存储技术全揭秘
http://www.nosqlnotes.net/archives/151 从Megastore看RDBMS和NOSQL系统结合