和其他系统的比较

当我们开始思考PNUTS时，G公司和Amazon已经宣布了两个大规模可扩展性数据库系统，微软也将对外宣布。当我们开始设计时，我们仔细研究了这些系统，思考它们的思想是否对我们有用。这些系统的一些想法对我们有影响，但我们还是决定构建一个新的系统，其架构在很多方面和这些系统不同。我们现在先来研究这些系统，并讨论为什么决定不采用它们的设计理念。

G公司的BigTable

BigTable(Chang等2006）是为了支持G公司的很多Web应用而设计的系统。该系统基于水平方式将“大表”(bg table)切分为很多小表(tblet)，并把这些小表分散到不同的服务器上。支持可扩展性的基本方法以及一些其他特性，比如灵活的模式和有序存储，与我们采用的方法很相似。但是，我们的设计和BigTable在某些方面有区别。

首要区别是数据复制方式不同。BigTable是构建在G公司的文件系统GFS上(Gemawat等2003）。GFS通过同步更新三个数据备份到三台不同的服务器上的方式来处理数据备份。这种方法在一个数据中心可以工作良好，因为一个数据中心的服务器间的延迟很短。但是，在三个不同的、分散的数据中心同步更新三台服务器代价很高。Alice可能需要等待很长的时间，然后其状态才能更新，尤其是如果她的好友通过带宽很低的网络来访问数据中心。为了支持跨数据中心的数据复制，我们提出了时间轴一致性模式，以及与主备份性、负载平衡和失效处理相关的机制。

BigTable和GFS在数据库服务器和文件系统间存在分离，而PNUTS不采用该分离。GFS最初是为需要对大文件进行扫描的应用设计和优化的（如MapReduce)。BigTable通过保留每个记录的版本历史和GFS关联，并把文件以SSTables的文件格式压缩来减少存储空间。这意味着对于记录的读和更新操作，数据需要采用这种压缩格式解码和编码。此外，GFS的特征是面向扫描，这有助于BigTable处理面向列的扫描应用（如“返回所有用户的所有地理位置信息”）。与之相反，我们的主要应用是需要读和更新一个小范围记录内的一条记录的一个版本。因此，我们的策略是把数据作为完整的记录，以B树形式组织保存在磁盘上。这种方法对快速定位、就地更新由主键识别的各条记录做了优化。

PNUTS和BigTable在其他方面还有不同。比如，PNUTS对于一个应用支持多个表，而不是一个大表，且对于散列表和有序表都支持。MegaStore是继BigTable之后(Frman等，2008）添加了事务、索引和更丰富的API，但仍然遵循BigTable中的基本架构原则。

Amazon的Dynamo

Dynamo(DeCandia等2007）是Amazon最近构建的应用于大规模数据负荷的系统，是和我们的高可用性、大规模数据存储的目标最相近的一个系统(Dnamo中称记录为对象）。Dynamo通过允许应用向任何副本写数据提供了写操作可用性，它通过Gossip协议（稍后会细述）向其他副本延缓传播(lzily propagate)这些更新操作。

为了解决网速慢和易于失效问题，Dynamo和PNUTS一致，它们都采用了延缓传播更新策略(lzily propagate updates)。但是，PNUTS的复制策略与之有很大区别。在Gossip（闲话）协议中，更新操作会传播到随机选定的副本，该副本又把该操作继续传播到其他随机选定的副本。这种随机性是该协议提供的概率性保证的基础，它保证了绝大多数副本可以相对快速更新。然而，在我们的应用环境中，随机性必然是次优的。比如Alice执行状态更新操作，其数据是在美国西海岸的数据中心。若采用Gossip方式，该操作可能随机传播到新加坡的副本，然后又随机传播到Texas的副本，接着又随机传播到东京的副本。该更新操作在传播地域上跨越了三次太平洋，如果采用一种更确定性方式(dterministic approach)，只需要传播该操作（和其他更新操作）一次，可以节约紧缺的跨太平洋主干带宽。此外，Gossip要求传播数据的副本预先知道在其他哪个数据中心的哪台服务器上有副本，因此很难为了负载均衡或数据恢复，在不同服务器间传送数据。

PNUTS和Dynamo的另一个关键区别是一致性协议。Gossip协议的本质决定了它是最终一致性模型：所有的数据副本最终将保持一致，但是在更新传播期间，副本可能是不一致的。尤其是，副本可能会存在“无效”状态。举个例子，Alice把她的状态从“Sleeping”改为“Busy”，再把地理位置信息从“Home”改为“Work”。由于更新的次序，从Alice的角度出发，唯一有效的记录状态是(Seeping,Home)、(Bsy,Home)和(Bsy,Work)。在最终一致性原则下，如果两个更新是在不同的数据副本上执行的，有些副本可能会首先接收到改为“Work”的更新，这样，这些副本将临时显示(Seeping,Work)状态。如果Alice的老板看到这种状态，Alice可能就有麻烦了。对依赖于在一条记录上以合理的次序执行多次更新的应用，它需要比最终一致性更严格的执行次序保证。虽然时间轴一致性模式允许副本已经过期，但即使是过期的副本也应该是和某个合理的更新次序一致的版本。

PNUTS和Dynamo还有很多其他区别：Dynamo只支持散列表，不支持有序表，PNUTS二者都支持；和Dynamo相比，PNUTS支持更灵活的数据到服务器的映射机制，可以提高负载均衡和数据恢复（尤其是对于有序表，可能存在不可预测的“热点”）。除了DynamO'Amazon还提供其他的存储系统：S3用于存储数据块；SimpleDB用于在结构化、包含索引的数据上执行复杂查询。虽然SimpleDB提供了更丰富的API，但是它需要应用实现某种数据分区策略，使得每个分区都有固定的大小限制。因此，一个分区内的数据增长是受限的。

微软的Azure SDS

作为Azure服务提供的一部分，微软构建了大规模的SQL Server服务器，称为SQL数据服务(SL Data Service或SDS，参见http：//hadoop.apache.org)。SDS的核心是通过水平分区达到系统的可扩展性。SDS的一个良好的特性是它通过扩展数据索引，并以SQL Server作为查询处理引擎，提高了查询能力。然而，SDS通过严格的分区来实现其查询表达能力：如果应用创建自己的分区，则无法简单地进行重分区。因此，虽然可以对一个数据分区发出丰富的查询请求，如果某个数据分区数据量增长或者访问很多，那么系统无法简单或自动地通过划分分区来解决“热点”效应。我们的策略是通过表抽象层，使得为加载和恢复数据而做的数据分区或者改变这些分区对于上层应用是透明的。虽然PNUTS的查询模式表达能力不如SDS(PNUTS不支持跨分区的复杂查询），但是我们还在继续探索增强PNUTS查询功能（如前面描述的通过视图的方式）的策略。

PNUTS和SDS的另一个区别是PNUTS系统把地理复制作为内建的主要特征。至少对于SDS的第一版本，其工作负荷是期望全部在一个数据中心，只有当主副本全部崩溃时，才会使用远程备份。我们希望Alice在新加坡、柏林和里约热内卢（巴西）的好友都能够有他们自己本地的Alice更新的首要备份。

其他相关系统

和我们的系统类似，一些需要扩展性和灵活性的其他公司，也构建了很多其他系统。Facebook构建了Cassandra系统(Lkshman等2008），它是一个P2P(Peer-to-Peer，对等网络）的数据存储，其数据模型类似于BigTable，架构类似于Dynamo，系统只提供最终一致性。

Sharded数据库（如Flickr[Pattishall]和Facebook[Sobel 2008]使用的MySQL的分区(sarding)策略）通过把数据分区到很多服务器上来提供可扩展性。但是，Sharding系统并没有提供我们所期望的扩展灵活性或全球数据复制特征。和SimpleDB类似，Sharded数据库的数据需要预分区。此外，该数据库只有一个副本可以是主备份，执行写操作。在PNUTS中，不同数据中心的所有副本都可以执行写操作（虽然是对不同的记录）。

雅虎的其他系统

PNUTS是雅虎构建的众多云系统中的一个。在数据管理中，还包含云计算的其他两个方面，但是研究的问题和PNUTS不同。Hadoop是MapReduce框架(Dan和Ghemawat2007）的开源实现(htp：//hadoop.apache.org)，它提供了在大数据文件上的大规模并行分析处理。Hadoop的文件系统HDFS，对扫描操作做了优化，因为MapReduce主要是处理面向扫描的操作。与之相反，PNUTS主要是处理单条记录读写操作。另一个系统MObStor是为了存储和服务大数据对象如图片和视频而设计的。MObStor的目标是为静态对象提供低延迟检索和低代价存储。因为很多应用需要结合记录存储、数据分析和对象检索，我们正在探索无缝地集成这三个系统(Coper等2009）。