准备了解一下hadoop，翻译篇论文先。

摘要

我们提出一种建立可扩展分布式系统的新范式。这种方法不需要处理消息传递协议--已存在的分布式系统中最复杂的部分。代替的，开发者只需要使用我们称之为Sinfonia的服务来设计和操纵数据结构。Sinfonia把数据保存在内存节点集合中供一些应用程序使用，每个内存节点占用线性的地址空间。Sinfonia的核心是minitransaction，能够在高效一致访问数据的情况下，隐藏并发和失败带来的复杂性。使用Sinfo- nia,我们花了数月的时间实现了两个不同且复杂的应用：一个分布式文件系统和一个组通信服务。我们的实现运行良好并扩展到数百台服务器上。

类别和主题描述

C.2.4 [Computer-Communication Networks]: Distributed sys- tems—Distributed applications; E.1 [Data Structures]: Dis- tributed data structures

通用术语

算法，设计，实验，性能，可靠性

关键字

分布式系统，可伸缩的，容错的，分享内存，事务，二阶段提交

Distributed systems, scalability, fault tolerance, shared memory, transactions, two-phase commit 

1介绍

开发人员经常使用消息传递机制来构建分布式系统，并通过传递消息来处理共享数据。这种机制不仅容易出错而且难于使用，因为在处理分布式状态时涉及到设计实现和调试复杂的协议。分布式状态指的是应用主机彼此之间需要操作和分享的数据，如元数据，表，配置和状态信息。处理分布式状态的协议包括复制、文件数据、元数据管理，缓存一致性，组的成员关系。这些协议的开发非常有意义。

我们提出一种建立可扩展分布式系统的新范式，在我们的范式下，开发人员不需要与消息传递协议打交道，代替的，开发人员只需要在我们名为

Sinfonia的服务中涉及和操作数据结构。我们也因此把协议设计问题转变为了简单得多的数据结构设计问题。我们的方法以数据中心应用为目标，如分布式文件系统，锁管理器，组通信服务。这些应用必须是容错和可伸缩的，而且必须提供一致性和合理的性能。

概括的说，Sinfonia是一个能够允许主机以容错的、可伸缩的、一致性的方式分享应用数据的服务。现有可以允许主机分享数据的服务包括数据库和分布式共享内存。数据库在效率至关重要的时候缺乏基础应用所需要的性能。这是因为数据库提供了比所需更多的功能，造成性能开销。在实例中，尝试使用数据库构建文件系统因为过慢的性能导致系统不可用。现有的DSM系统缺乏基础应用需要的可伸缩性和容错性。第八节讨论了一些接近于Sinfonia的DSM系统。

Sinfonia的核心是一个轻量级的minitransaction，应用使用minitransaction在多个内存节点上原子的访问和附有条件的编辑数据。举例来说，考虑一个使用Sinfonia构建的分布式文件系统。使用minitransaction，一个主机可以原子性的存储一个inode于一个内存节点并且将这个inode链接到另外一个内存节点中存储的目录实体，并且这些更新可以取决于inode被释放(避免竞态)。像数据库事务一样，minitransactions隐藏了并发执行和失败处理的复杂性。

在许多情况下，minitransaction也可以提高性能。首先minitransaction允许用户用户批量更新，这样可以消除多次网络往返。第二，因为他们的限定域，minitransaction可以在提交协议执行。实际上，Sinfonia可以在两个网络往返内开始，执行并提交一个minitransaction。对比更加高级强大的数据库的事务，仅提交就需要两个往返，开始和执行还需要额外的往返。第三，minitransaction可以在一个复制模式中并行执行，避免了额外延时的可用性问题。

我们构建了两个非常不同的复杂应用用来演示Sinfonia：一个叫做SinfoniaFS的分布式文件系统和一个叫做SinfoniaGCS的组通信服务。这些应用已知都是难于实现为可伸缩和容错的：系统达到这些目标会非常复杂而且需要数年的努力。使用Sinfonia，我们构建他们分别用了3900和3500行代码，一和两个人月。在SinfoniaFS中，Sinfonia保留文件系统数据，每个分布式的节点都使用minitransaction原子的检索和更新文件数据与属性，分配和销毁空间。在SinfoniaGCS中，Sinfonia保存用户广播的排序消息，用户使用minitransaction向排序中增加新的消息。

经验显示Sinfonia和它的应用易于扩展性能良好。Sinfonia在单节点的情况下可以每秒执行数千个minitransaction，而且吞吐量随着系统大小有着很好的伸缩性。单节点的SinfoniaFS性能与NFS服务器一样好，不同于NFS服务器，SinfoniaFS可以扩展至几百个节点，SinfoniaGCS的扩展性比Spread(一个组通信服务的高吞吐实现)更好。

2假定和目标

我们考虑到数据中心之内的分布式系统。数据中心是一个拥有许多连接良好主机的位置。它可以拥有数十至数千的主机来运行数十至数百的应用。网络时延很小而且一般只有很小的变化，不像在一个完全并发的环境。数据中心可能会发生网络分区，但很少见；当只有一个主机，在数据中心不可用的时候可以接受暂停应用。数据中心中得应用和他们的设计者是可信赖的而不是恶意的。注意这些假设不包括广域网络，对等系统或是整个Internet。

数据中心受制于失败情形：有时候一个节点可能当机，或是罕见的情况下，所有的节点都可能当机(比如断电)，而且失败情形可能发生于不可预见的时段。独立的机器是可靠的，但当机是常见的，因为有非常多得机器。我们不考虑拜占庭式失败的情形。磁盘提供稳定的存储，也就是说，磁盘为目标应用提供足够的可靠性。这可能需要小心的选择磁盘，稳定存储有可能崩溃，并需要处理，但这样的崩溃相当罕见。

我们的目标是帮助开发人员构建分布式的基础应用，这些应用可以支持其他的应用。示例包括锁管理器，分布式文件系统，组通信服务，和分布式命名服务。这些应用需要提供可靠性，一致性和可伸缩性。可伸缩性是根据系统大小成比例的增加系统上限的能力。本论文中，上限指的是运行限制，由吞吐量来测定。

3.设计

现在我们描述Sinfonia和它的设计原则

3.1原则

Sinfonia的设计基于两个原则：

原则1.减少操作耦合以获得可伸缩性

耦合指的是操作之间的互相依赖，这样限制了不同主机并行执行，损害了可伸缩性。Sinfonia通过不强加数据结构来避免操作耦合。

原则2.扩展组件之前先使其可靠。我们首先使单独的Sinfonia节点容错，然后才扩展系统增加更多的节点。因此我们避免了使用许多不可靠组件的大系统带来的复杂性

3.2 基本组件

Sinfonia由内存节点结合和应用节点上运行的userlibrary组成(图1)。内存节点依据应用需要保留应用数据在RAM或者磁盘上。userlibrary实现在内存节点上操作数据的机制。可以把内存节点可应用节点放在同一个主机上，但他们是逻辑清晰独立的。

每个内存节点保留一些标准长度的原始串或不可中断的words；在本paper中，word长度为1字节。这些字节在地址空间线性的存放，没有任何结构。每个内存节点有独立的地址空间，这样Sinfonia中得数据可以通过键值对(memory-node-id,address)来引用。我们曾尝试过设计一个全局地址空间透明的映射至内存节点，但是这个设计因为缺乏节点聚合性而不可伸缩。节点聚合指的是将会被一起访问的数据放在同一个节点上。例如我们的分布式文件系统尝试将一个inode，它的链接列表和它的文件数据放在同一个内存节点上(如果空间允许的话)。这在透明映射的全局地址空间中是很难实现的。节点聚合是数据分块的反面，数据分块会把一起访问的数据分布到许多节点上去。数据分块提高了单用户的吞吐量，但我们的经验表名这损害了可伸缩性。

应用节点通过一个userlibrary访问Sinfonia上的数据。这个userlibrary提供了字节范围读写单个内存节点的基本方法。下节与minitransaction一起描述。

3.3 Minitransaction

Minitransaction允许应用在保证原子性，一致性，隔离性，和持久性的情况下对多个内存节点上的数据进行更新。原子性意味着minitransaction要么全部执行，要么都不执行；一致性意味着没有脏数据；隔离性意味着minitransaction是串行化的；持久性意味着提交的minitransaction不会丢失，即使出错也不会。

我们调整minitransaction的能力，这样他们执行的相当有效和快速。为了解释我们是如何做到的，首先描述一下标准的分布式事务是如何执行和提交的。大致来说，一个协调器通过询问参与者来运行一个或多个事务动作，例如检索或编辑数据项。在事务结束的时候，协调器执行两阶段的提交。在第一阶段，协调器询问所有的参与者他们是否准备好提交。如果他们都投票yes，在第二阶段协调器通知他们去提交；不然协调器会告诉他们中断操作。在Sinfonia中，协调器是应用节点，参与者是内存节点。

我们观察到可以优化某些事务的执行，比如下面的。如果事务的最后一个动作不会影响协调器决定中断还是提交，协调器可以将最后一个动作放在两阶段提交的第一阶段(比如，操作是数据更新)。这个优化不影响事务语义并节省了通信往返。

 

即使事务的最后一个动作影响了协调器中断还是提交的决定，如果参与者知道协调器如何做决定，我们仍然可以把操作附加到提交协议中。比如，如果最后一个动作是读取而且参与者知道如果读取返回0协调器会返回中断(不然就返回提交)，那么协调器可以把这个操作捎带在两阶段提交中，而且参与者可以读取并调整它的投票，读取为0时投中断。

实际上，将整个事务执行捎带在提交协议中是可能的。We designed minitransactions so that this is always the case and found that it is still possible to get fairly powerful transactions. 

更精细的，一个minitransaction(图2)由比较项集合，读取项集合，写入项集合组成。每项指定了一个内存节点和内存节点之内的地址范围；对比和写入项同样包括数据。所有的项在minitransaction开始执行之前就被选择，基于执行，一个minitransaction做以下步骤：（1）对比比较项集合的位置,若有的话，针对比较项集合的数据进行相等比较，（2）如果所有的比较成功，或者没有比较项集合为空，返回读取项集合的位置以及写入这些位置的写入项，（3）如果对比失败，中断。因此，比较项控制minitransaction提交或者中断，读取和写入项集合决定minitransaction返回和更新什么数据。

More precisely, a minitransaction (Figure 2) consists of a set of compare items, a set of read items, and a set of write items. Each item specifies a memory node and an address range within that memory node; compare and write items also include data. Items are chosen before the minitransaction starts executing. Upon exe- 

cution, a minitransaction does the following: (1) compare the loca- tions in the compare items, if any, against the data in the compare items (equality comparison), (2) if all comparisons succeed, or if there are no compare items, return the locations in the read items and write to the locations in the write items, and (3) if some com- parison fails, abort. Thus, the compare items control whether the minitransaction commits or aborts, while the read and write items determine what data the minitransaction returns and updates. 

Minitransactions对于处理分布式数据是强大的基础。minitransactions示例包括以下步骤：

1.交换。一个读取项返回旧值并由写入项替换它。

2.比较并交换。一个比较项比较当前值和一个常量；如果相等，写入项替换它。

3原子性的读取许多数据。由大量读取项来完成。

4获取租约。一个比较项检查位置是否设置为0；如果为0，一个写入项设置此位置为租借人的id(不为0)而且另一个写入项设置租约的时间。

5原子性的获取多个租约。跟上面一样，除了这里有多个比较项和写入项。注意每个租约都可以在不同的内存节点中。

6如果租约实施则改变数据。一个比较项检查一个租约是否开始，如果开始，写入项更新数据。

 

一个频繁的minitransaction习语是使用比较项集合验证数据，如果数据有效，使用写入项集合应用一些改变在相同或不同的数据上。

minitransactions在SinfoniaFS中很常用：文件系统非常积极的在应用节点中缓存文件节点和元数据，而且相关的缓存实体在修改文件系统之前被验证过。

比如，写入文件需要验证一份拷贝了文件节点和链接列表(the list of blocks comprising the file)，如果他们有效，则修改适当的文件块。

这些在minitransaction的比较项和写入项中完成，图7展示了SinfoniaFS使用minitransaction设置一个文件的属性。

 

另一个minitransaction习语是只使用比较项来验证数据，不需要读取和写入项。

这样的minitransaction无论提交还是中断都不会编辑数据。但如果提交成功，应用节点知道所有的比较成功，所以验证也成功。SinfoniaFS使用这种

minitransaction来验证缓存数据中只读的文件系统操作，如stat（NFS's getttr）。

在第四节我们解释minitransaction如何高效的执行和提交。

Another minitransaction idiom is to have only compare items to validate data, without read or write items.

Such a minitransaction modifies no data, regardless of whether it commits or aborts.

But if it commits, the application node knows that all comparisons suc- ceeded and so the validations were successful.

SinfoniaFS uses this type of minitransaction to validate cached data for read-only file system operations, such as stat (NFS’s getattr).

In Section 4 we explain how minitransactions are executed and committed efficiently.

It is worth noting that minitransactions can be extended to include more general read-modify-write items (not just write items)

and generic conditional items (not just compare items) provided that each item can be executed at a single memory node.

For example, there could be an increment item that atomi- cally increments a location;

and a minitransaction could have mul- tiple increment items, possibly at different memory nodes,

to in- crement all of them together. These extensions were not needed for the applications in this paper, but they may be useful for other applications.