乐观复制算法

乐观复制算法

在分布式数据共享系统中，复制是能同时提高系统可用性和性能的一项关键技术。本文讨论的乐观复制算法，为了支持并发工作，容忍低质量通信链路中的错误，它允许副本内容在短时间内出现不一致。随着基于广域网和移动网络的协作越来越流行，这项技术也越来越重要。

乐观复制算法采用的技术与传统的悲观算法有很大的不同。与悲观算法依赖于同步副本的协作不同，乐观算法在后台传播更新，在更新发生后发现冲突，逐步在对象的最终内容上达成一致。本文将会讨论乐观复制系统面临的关键问题，比如：一致性达成，保证副本内容质量，副本扩展性。并对解决这些挑战的技术进行全面讨论。

1.介绍

复制管理着在多台电脑上关键数据的多个副本，并允许对其中任一副本的访问。它是实现分布式服务的关键技术，能同时提高服务的性能和可用性。通过允许对数据的访问来提高可用性，即使其中一些副本或网络链路不可用。性能的提升通过两种途径。首先，用户可以就近访问副本，避免远端网络访问的高开销和延迟。其次，服务总的吞吐量提升可以通过多个站点同时提供数据的方式来满足，特别是对于大量读请求的数据访问。复制传统上被用于局域网环境，来保证关键服务的可用性，特别是数据和文件系统。网络和移动计算技术的进步改变了这幅画面。通过DNS，Usenet，CVS，Lotus Notes等服务可以看出，基于广域网的分布式服务成为一种实实在在需要。在延迟和可用性比LAN糟糕数个数量级的环境下，乐观复制系统能实现服务的高可用。它让用户可以在任何时候访问任意节点，从而实现服务的高可用。与之相对的，副本会保存并呈现出不一致的数据，事后不一致数据将被修复。

本文将讨论乐观复制算法。我们将讨论该算法面对三个重要挑战：维护数据一致性，保证内容质量以及支持大规模的副本节点。下面，我们分析之前开发的一些系统，并提出一个易于理解的算法分类。

本章的后面部分将介绍乐观复制的相关概念。1.1小节回顾传统的，悲观复制算法并指出他们的局限性。1.2小节将总述乐观复制系统，并说明它们的优点。1.3小节展现乐观复制系统面对的挑战，1.4小节介绍一个广泛的分类，我们用来回顾该算法以及其解决面临的挑战，同时也是全文的线索。

为了便于阅读，我们汇总了相关概念和名词在表1和表2.详细的定义和示例可以在相关章节找到。

1.1悲观复制算法和他们的局限

复制已经被研究和发展了很长一段时间。传统复制算法旨在支持关键任务的应用，提供单副本的串行化。它们提供给用户一种假象，认为数据的存在是单一的、高可用、可被实时更新。这个目标可以通过多种方式实现，基本的想法是一致的：阻止对副本的访问直到它被更新到最新状态。这就是我们称它们为“悲观”算法的原因。比如，primary-copy算法，在商业数据库系统被广泛使用，选举一个副本作为主节点，该节点负责对特定对象的请求串行化。其它节点作为二级节点仅完成从主节点接收更新。其它系统，比如微软的Cluster Service，DDS，采用two-phase提交，对所有副本加锁并同时提交更新。群多播系统，例如，Isis，Totem，Transis，向所有节点以相同顺序发送消息来串行化更新。在每个节点运行一个未被复制的数据库，并通过它们响应用户请求，理论上可以构建一个复制数据库系统。法定人数算法，需要副本在每次对象读取和更新时进行选举，他们需要多数副本在哪一个内容是最新的问题上达成一致。

悲观复制技术在局域网环境运行的很好。考虑到互联网技术的持续发展，它试图被应用在广域网的数据分布上。下面三个原因，让高性能和可用性无法实现。

1）广域网仍很慢，而且不可靠。广域网上端到端的通信延迟和可用性这些年并没有提升。大量的移动计算服务，存在于防火墙后，间歇性的连接到网络。悲观复制算法在该环境下表现很差。比如，primary-copy算法需要能准确检测站点失效（并与链路失效、节点抖动区分开），以便他能在主节点失效时可靠的选出另一主节点。这在理论上是不可能，只有当提供硬件的端到端直连时在概率上可能。

2）悲观算法需要面临可用性的损失。随着副本节点的增多提高了读可用性，同时降低了写可用性，因为悲观算法以加锁方式协调这些副本对内容进行更新。因此，他们很难应用到需要部署多个节点、频繁更新的服务中。不幸的是，很多互联网和移动服务属于这一类；比如：Usenet,移动文件和数据库系统。

3）一些用户的行为本身需要乐观数据共享。例如，工程或程序开发，用户同时并又相对独立的工作。相比在编辑时加锁，让用户并发更新并在偶然发生冲突时解决它们更好。这样的工作场景中，加上网络延迟与时区不同，乐观复制算法显得更有价值。

1.2乐观复制：总述与优点

乐观复制算法允许用户在任何时间访问任意副本。乐观复制算法基于两点乐观的假设，冲突更新很少出现，副本内容与其它节点上副本的内容是足够一致。区分乐观复制算法与悲观算法的关键点是如何处理对数据的更新。悲观算法同时更新所有的副本，以及当一个更新被应用时，可能阻止来自用户的读请求。乐观算法在大部分时间里每一个副本都是可以直接读、写，在后台传播更新，并在更新冲突发生时解决它们。这样的特性让乐观算法可用性和有效性更高，可以被应用于不可靠的网络介质和并不昂贵的计算机上。乐观复制并不是新的观念（比如，数据备份是一种初级的乐观复制），它只到最近才引起强烈的关注，主要是因为互联网应用和移动设备的激增。乐观复制算法相比悲观算法有如下优点：

A.可用性，乐观算法在低速和不可靠的网络连接和计算机环境中工作的很好，因为它们在后台传播更新并且不阻塞对任何副本地访问。

B.网络灵活性，乐观算法在间歇性网络或不完全网络中可照常工作。例如，很多算法允许更新通过中间站点来传播（称作 epidemic通信）。这样的属性是移动环境的本质，移动设备仅是偶尔的被同步。

C.扩展性，乐观算法能支持大规模副本，因为后台的更新传播需要站点间更少的协作。

（思考：站点间的协作，即站点间需要的通信次数和需要传输的数据量，这个因不同的算法而不同。）

D.站点自治，乐观算法提高站点和用户的自治。例如，一些服务，比如FTP和Usenet镜像，一个副本可以被添加而无需管理员对已存在的站点进行更改。乐观复制也被应用到多用户协作中，比如CVS，Purdy，PerDiS和Lotus Notes,让多个用户在同一个项目上独立工作，稍后合并他们的改变。

E.快速响应，乐观算法让更新立即被应用到它所到达的站点。该特性让用户可以立即看到他所做的更改，提供更好的用户体验。注意，这些更新是不确定的，因为系统可能会取消或者重做他们，当最终应用的顺序确定时。

1.3乐观复制：目标和挑战

伴随着前面提到的优点是需要付出相应的代价。任何分布式信息系统都面对可用性和一致性的权衡。悲观复制算法保证每个副本严格的一致性，常常会阻止对数据的访问，乐观算法保证任意时刻对数据的访问，但有时会出现短暂的数据分歧：悲观算法等待的地方，乐观算法在推测。

（思考：最后这句话说，悲观算法中加锁防止冲突的地方，乐观算法通过推理等方法来解决冲突）

乐观复制系统的目标是提供对“足够新”数据的随时访问，以及最小化用户对分歧数据的困惑。这些目标可以被细化为下面小的目标，并以从基础到高级的顺序介绍。

1.3.1一致性

一致性，也被称作最终一致性，要求无论更新在哪里、在何时发生，以及无论它们以何种顺序被每个站点接收，所有副本的内容将最终获得一致。一致性作为乐观复制系统最重要目标有两个原因。首先，如果没有这个保证，副本内容可能会永远是错的。其次，最终一致性服务通常尽最大努力在站点间快速传播更新，同时这样的努力对大多是应用是足够和实用的。一致性通过结合四个过程来实现，如图1所描述：可靠的更新传播(b)，明确的更新调度（c），冲突检测和解决(d),和更新提交(e).

（思考：调度和冲突解决，让我十分困惑的问题。因为文中所描述的同步步骤是在调度和冲突解决完成后再提交这些更新。可在广域网上，提交更新这一步需要传输大量文件十分耗时，在这段时间内副本极有可能发生了新的变化，这样存在新的冲突在调度和冲突解决阶段是不存在，而当真正提交更新时才会出现。

所以我对调度、冲突解决、提交更新的步骤做了改进，让他们不是一个阶段一个阶段来执行，而是一个文件一个文件来处理。）

更新传播，需要站点积累它独立于其它站点时发生的变化，当与其它站点通信恢复时检测其它站点变化，计算生成让两个副本获得一致变化集，将变化集快速地传播其它节点。

最受欢迎的特性是epidemic传播。任意站点可以和其它站点通信，传播它自己的更新并接收来自其它站点的更新。该协议最终传播每个更新到所有站点，无论何种网络拓扑，包括连接是糟糕、不完善时，例如在Usenet中。当通信链路改变，epidemic传播是鲁棒的，例如，自组网络环境、站点失效的情况。

更新调度，定义了更新顺序的策略。因不同站点可能以不同顺序接收到相同更新，所以需要调度。一个调度算法有两个目标：

A.快速地应用更新，减少延迟，增加并行性

B.尊重用户本身的意图，避免用户混淆。例如，维护因果顺序，避免冲突，以及不丢失更新。

例如，简单地按照更新发生的顺序进行总排序（比如，以物理时钟顺序）能够实现一致性，但可能增加并发率。利用应用语义，例如操作的交换性可以提高并行性，提高用户体验，通过最小化更新冲突或者撤销、重做不确定更新，但这将以一定的算法复杂度为代价。

冲突检测和解决：因为用户进行更新时并不知道其它节点上发生的更新，所以冲突不可避免。此外，当冲突被检测出来时用户可能并不知道。很多系统不提供冲突检查，仍传送错误的结果，因为用户通过愿意强制性地分隔访问数据进而避免冲突。比如，用户很少同时写一个文件。自动冲突检测，尽管是可选的，但它能极大的改善用户体验。考虑一个房间预订系统。如果两人同时预订了一个房间，系统很容易维护一致性，通过简单的接受一个请求，忽略另一个。然而，如果用户被通知有冲突并允许协商时间安排，将会更好。

一旦冲突出现，它必须被解决，通过用没有冲突的更新替换冲突更新。一个通常策略，“last writer wins”，简单地选择最后的更新，丢弃掉较早的更新。更好的策略是试图计算两个更新间的语义信息。例如，一个复制文件系统，当连个用户在同一个目录下创建文件，如果文件名不同系统能同时接收两个更新。同样，当两个用户同时写一个文件，系统能创建以不同名称命名的两个文件，包括用户的两个版本。

冲突检测和解决通常是乐观复制系统最复杂的部分。因此，我们定义了冲突，并对补救办法进行了总的描述，详细的细节在第3章讨论。

更新提交，定义了一种机制让站点在调度和冲突解决后的结果集上达成一致。应用到对象上的更新被提交后，不用担心将来被撤销。所有与更新相关的数据结构可以在提交后删除。

1.3.2内容质量保证

一致性，并不保证临时副本内容的质量，内容最终一致性保证对于用户而言并没有意义。QoC，保证对何时何地传播更新的控制，以及何时何地副本可被用户访问。这个特性并不一定被普遍采用，很多系统向用户提供陈旧的数据；如果严格限制对象访问，系统可用性将会降低。

QoC控制包括多种形式。最流行的是时间保证，保证副本内容不能比最新更新内容落后多少秒，比如WWW caching。因果一致性，维护读写请求间的因果序，是另一种QoC保证。例如，一个复制密码数据库。用户在一个站点修改她的密码，可能稍后在另一个站点以新密码登录会失败，因为更新还没有传播到后一个站点。这样的问题可以被避免，通过保证因果序的读，保证读请求可以获得在同一个用户最后的写更新。我们会在第8章讨论QoC相关问题。

1.3.3扩展性

乐观复制系统必须能扩展，支持大量数目的副本和大对象。如果有大量的副本将同时增加传播延迟和冲突比例。通过选择一个合适的副本连接拓扑，以及预先控制更新流，这种情况可以被改善。我们将在第9章讨论这些策略。支持大对象仅是特定系统的一个问题（“state-transfer”系统，见下一章）；我们将会在5.3小节讨论。

1.4路线图

本文后续按如下结构组织。第2章总述几个采用乐观复制技术的流行应用，并讨论它们不同的需求。第3章定义本文的关键概念：对象，冲突和一致性。尤其，我们将定义什么时候的更新是冲突的，并概括各种冲突处理的方法。

文中余下的部分将讨论算法如何解决在1.3小节中提到的三大挑战。第4章到第7章将讨论一致性问题。我们将论述为实现一致性的各种算法—比如，更新传播、调度、冲突处理—采用Figure 2的分类进行描述。

根据更新发生和传播的地点以及对象进行分类。正如我们所见，这些方面决定了算法的类型，算法被应用维护一致性和功能特性，比如，扩展性。

写入节点数目：单主节点vs多主节点：第一个分类标准以更新在哪里发生和如何传播进行区分。单主节点指定一个副本为主节点。所有的更新发生在主节点，然后传播到其它副本，或称从节点。这些系统比较简单但可用性有一定局限。在另一方面，多主节点让更新在多个主节点副本独立发生，然后在后台交互他们。该系统可用性更高，同时也更加复杂。更新调度，冲突检测和解决都仅是属于多主节点的问题。文中，我们用N表示系统中节点的总数，M表示主节点的数目。

更新传播的单元和模式：状态vs操作：第二个分类标准取决于每一次更新传播的内容。一个状态传播系统，在节点间交换新对象的内容。一个操作传播系统，让每个主节点记住或者重建构成一个对象的操作日志，站点间交换操作描述。状态传播相对简单，因为更新只需要向拥有旧副本的节点传播最新副本的内容。操作传播会更加复杂，因为站点间需要对更新的集合和顺序达成一致。从好的方面看，当对象较大时会非常高效，同时允许更加灵活的冲突处理。比如，在书目数据库中，对于同一个作者两本不同作品的更新，在操作传播系统中可以在语义上进行合并。对于每次传播真个数据库文件的状态传播系统则很难做到。这个分类标准可以应用于单主节点和多主节点系统中，但本文主要研究后一种系统的实现。

第4章讨论单主节点系统。第5章讨论对于多主节点的状态传播系统。第6和第7章讨论多主节点的操作传播系统。第6章论述来自分布式更新的算法，第7讨论调度和冲突处理。

第8章讨论保证副本内容质量的技术。将论述三种广泛采用的方法：保证读请求的因果序，明确不一致窗口，概率技术来降低节点的陈旧情况。第9章讨论随着副本节点的增长,乐观复制算法的扩展性问题。第10章总结算法和已有的系统，并讨论从中可以吸取的教训。附录A，对分布式系统中的事件顺序进行简要描述。

2.采用乐观复制技术的应用

乐观复制被应用到许多重要领域，包括广域网的数据管理，移动信息系统，和基于计算机的协作。为后续技术的讨论提供背景，我们将选取这些领域中的一些主要服务，介绍它们的功能和结构。

2.1互联网服务

对于站点间通信缓慢和不可靠的情况，乐观复制特别具有吸引力，对于互联网上的应用这一点十分突出。我们将考察两种互联网应用，一个是广播信息的应用，另一个是具有更多信息交互的应用。

1.1.1DNS：广域网上的缓存和镜像

很多互联网数据传播服务采用乐观复制保证可用性和性能。例如WWW，FTP，NNTP缓存，以及目录服务器，例如Grapevine，Clearinghouse, DNS，活动目录。

这一章讨论DNS，一个分布式，层次化命名服务。对一个特定的DNS域，由一个主节点服务器所管理，它维护着属于该域的核心数据库，可选的从节点从主节点拷贝数据库。主节点和从节点都将回复从远程客户端和服务器发来的请求。为了更新数据库，管理员改变数据库，增加它的时间戳，并在主节点重新加载。一个从节点服务器，周期性的轮询主节点，当时间戳变化时下载数据库。

DNS是一个乐观复制服务，它允许从节点上的内容滞后主节点，客户端可以看到不一致。有三个原因使得乐观复制非常适合DNS和与之类似的服务。第一，乐观复制允许在长距离,不稳定网络上复制数据。第二，它避免了昂贵的硬件组成，这些对于提供高可靠的悲观复制是必须的（比如，远距离的光纤连接）。最后，因为DNS运行客户端和中间服务器缓存数据，使用乐观复制算法以及宽松的一致性，并不会明显地降低端到端的服务质量。DNS是一个单主节点（所有该域的写请求，发生在该域的主节点上），状态传输系统（主节点发送拷贝和注册信息到从节点）。

1.1.2Usenet：广域网信息交换

Usenet是一个广域网的公告板系统，部署于1979年，是最老并仍是最流行的乐观复制服务。Usenet开始运行在UUCP上，一个无交互的存储发送网络。UUCP仅能和固定的邻居通信，网络连接仅支持在直接连接的服务期间，间歇性的文件拷贝。

Usenet是由上千台服务器组成一个强连通图，由一些列人工协商而成。每个服务器复制所有的新闻文章，这样用户能从最近的服务器获取任意文章。Usenet允许任何用户将文章传送到任何服务器。上传到一台服务器的文章周期性的推送到邻近的服务器上。接收服务器，存储并再周期性地发送到它邻近的服务器。这样，每篇文章通过服务期间的连接最终传播到全世界所有的服务器上。无限的传播循环，通过每个节点仅接受自己缺少的文件而避免。文章通过设定强制性的过期时间删除，或者用户发送取消信息删除，该信息会和通常的消息一样在服务器间传播，但会强迫服务器删除特定消息。

Usenet周期性的文章传播策略，造成了延迟时间的不确定，一篇文章从一个服务器传送到另一台服务器可能需要一周之久。虽然这样的变化经常让用户混淆，但它杰出的可用性使得这是一个合理的代价。

Usenet是一个多主节点（写操作能在任意节点发生），操作传输的系统（主节点发送文章创建、取消操作到其它节点），使用一个周期性更新传播协议（任意节点可以发送更新到其它节点）。

2.2移动数据系统

乐观复制特别适合计算机经常离开的网络环境。采用乐观复制的移动存储系统有Lotus Notes，Palm，Coda，以及Bayou。

下面讨论Bayou系统。它允许用户在移动设备上复制数据库（比如，笔记本），在断开连接时修改它，用户重新连接到网络上时合并其它设备上的变化。Bayou将对站点上的修改，记录为一系列高层次的操作，利用时间戳向量来最小化站点间需要交换的操作。更新在它到来时暂时性地被应用，但到达顺序可能和所有站点最后同意的顺序不一样。

（思考：所有站点需要达成一致的到达顺序，可以通过设定某个全局服务器来统一）

因此，临时性的更新会被取消或者重做，当站点逐步了解到最后顺序。冲突的检测和解决，可以通过应用程序定义的脚本，挖掘应用程序语义来控制。

在算法上，Bayou是一个多主节点，使用周期性传送高层次操作的系统。两种时间戳来控制临时执行的操作和最终调度顺序，应用层脚本来解决语义冲突。Bayou是本文中论述到的最为精致和复杂系统，因为移动环境的挑战，比如缓慢和不可靠的网络连接，不可忽视的更新冲突。

2.3 CVS：计算辅助协作

CVS（并发版本系统）为一组文件保存一系列历史更新，允许用户在需要时兼做文件的历史版本。CVS中的通信是通过单个中心节点进行。中心服务器有一个仓库，管理着文件副本的授权，以及过去他们发生的所有变化。更新文件前，用户先创建一个私有的文件拷贝，利用标准工具比如Emacs进行编辑。任意数目的用户可以拥有他自己的副本，并发的修改副本。当工作完成，用户提交他自己的副本到仓库。如果没有其他用户修改同一个文件，提交立即成功。否则，CVS将会逐行比较不同版本的文件。只有这些行的更新集合没有重叠，CVS就会自动的合并它们，让用户提交合并后的版本。

2.4总结

这一节总体介绍了采用乐观复制的常见系统。乐观复制覆盖了广泛并重要的应用，从Usenet的发明开始。注意，这些系统使用多种不同的机制来维持副本一致性。余下的章节将仔细分析这些系统。

3.基本定义

这一节介绍一些重要的词汇。3.1节说明对象，3.2节定义冲突，3.3节对冲突处理技术进行分类。

3.1 对象

任何复制系统都有一个最小更新粒度的概念，有些系统表示为可识别的粒度，有些系统表示为可传播更新的粒度。文中我们称最小的粒度为对象。不同系统的对象可能差距巨大。比如，文件同步中，一个典型的对象是一个目录或者文件。在groupware系统中，相同的文件会被视为一个包括许多对象文档；比如包含：段，行和字符。有些系统将操作不同层次的粒度；比如CVS，同时操作文件和行对象。

在某些系统中，对象的边界和区分是内容相关的。比如，一个协作的文本编辑器，一个对象可能是文件中的一行，并通过一个行号进行区分。因为用户会并发修改文件内容，系统会对相同位置在不同文件内容中给予不同的标记号。这样相对标记方法，给冲突解决增加了很大的难度，这一点在7.3节操作转化的讨论中将会证明。

一个副本是一个对象的拷贝，并存储在站点上，比如，计算机中。一个站点可能存储多个对象副本。文中，会交换的使用副本和站点这两个概念。大部分的乐观复制算法会独立地管理各个对象。

（思考：最后一句话是说每个乐观复制算法的实例，其管理的更新对象是不同的。）

3.2 一致性和冲突

一个乐观复制系统允许副本存在分歧，比如，不同的值。在但Master系统中，分歧往往是良性的，结果仅仅是访问延迟。本文主要论述多Mater系统，分歧将导致错误，或者冲突。本章将给出在多Master系统中，冲突的更准确描述，以及它与并发访问和共享数据语义的关系。

为了不同目的，存在多种冲突的定义，但它们有两个共同点。首先，冲突的定义无法与一致性向分离，因为冲突出现在操作违反了一致性时。其次，一个操作与另一个操作存在“happened-before”关系，则两者间不存在冲突。换句话说，如果一个操作A能观察到另一个操作B的影响，系统认为操作A已经将操作B考虑进来了。这里，分歧可以从两个维度上定义。

Internal vs. External （内部vs外部）一致性：大多数系统支持的对象相互独立，分离，并采用唯一ID标示。对象的相互独立指，当程序修改多个对象时，更新不能原子性的应用到多个对象上（不是一个原子事物）。对每一个对象的更新单独传播，可能会存在不同的冲突解决结果。

大多数乐观复制系统认为对象相互独立，对于分裂数据的操作将不会冲突。（思考：对不存在依赖关系数据的修改将不会出现冲突，依赖关系可以有很多种。比如，目录结构的父子关系、信用卡转账两个账户的依赖等等）他们支持内部一致性，副本间相同的对象。典型的例子是复制文件系统，对不同文件的更新不会冲突。其它系统试图维护跨对象的不变性，external一致性。比如，一个复制数据库使用事务来保证对多个对象更新的原子性。

语法 vs 语义检测：仅通过并发更新的出现来标示冲突的系统，检测的是语法冲突。比如，文件系统对同一文件的任意并发写冲突，适用这种策略。语义冲突检测，利用应用语义从良性并发更新中区分出冲突。比如，采用语义冲突检测的文件系统，允许对同一目录下不同文件的并发更新；创建文件“X”与删除文件“Y”不会冲突。

两两结合的四种组合都是有意义的。内部-语法系统是最流行的，因为非常容易实现。因为内部一致性不会考虑不同对象的关系，用户可能会观察到令人吃惊的结果。考虑一个持久的Hash表，每个文件有一个Hash表以及溢出的桶。一个插入操作会同时更新两个文件；在这两个文件上，并发的插入操作可能会按不同的方式处理，从而导致一个不一致的Hash表。(说明，这句话翻译的不一定对，下面是原文：Consider for instance a persistent hash table where one file contains the table and another the overflow buckets. An insert operation updates both files; concurrent inserts may be resolved differently at the two files, resulting in an incorrect hash table. )

虽然如此，支持外部一致性在乐观复制系统很少见，因为它需要额外的机制来维护和检测内部对象的约束。第8章将会简要的说明。本文主要考虑内部一致性，除非有明确的说明。

（思考：Dropbox等文件同步工具，实现的是文件目录同步。对于目录删除，目录丢失情况的处理就需要处理外部对象的约束关系，即文件和目录之间的约束。）

（思考：我们实现的Robin对于语法上的冲突，采用Thomas规则。对于违反happen-before关系的冲突修改，则是基于语义来处理。）

（思考：我们实现的Robin维护的文件系统语义一致性主要是三点；目录与文件的父子关系；同一目录下不能出现同名文件、同名目录；对同一文件不能多个用户同时修改（只要违反happen-before关系的修改都判定为并发修改）；）

3.3 冲突处理技术的分类

图3，给出了冲突处理方法的分类。分为三个基本阶段：避免，检测，和修复冲突。

冲突避免是最好的方法，尽管通常在乐观环境中不能。悲观算法和单Master系统采用传播更新前串行化更新的方式来避免冲突。尽管阻止冲突是不可能，系统通过快速地传播更新从而可以减小副本之间的差异。另一个可选方法，将对象划分为更小的片段，能减少false-positive冲突；比如，对同一对象不同部分的更新并不冲突（见5.3节）。最后，有些系统能预估不一致的程度，当超过设定阈值时会提醒用户(见8.2节)。

如果冲突不能避免，他们应当可以被检测和修复。语法冲突可以采用自动机制来检测，比如two-timestamps(5.2.2小节)和version vectors（5.2.2小节）。语义机制可以过滤掉一些语法冲突，根据对象语义他们并不冲突。例如包括，检测可交换的更新，采用有利的顺序。当操作并不可直接互换时，操作转化方法修改冲突操作的参数，使他们以其他顺序执行。

冲突更新必须被解决。解决方法不必依赖于冲突的检测；系统可以简单的使所有可能与其它操作冲突的更新无效，比如，采用“last writer wins”策略。一些高级的系统支持应用相关的自动冲突处理。某些情况下，冲突不能被自动解决，最终将询问用户或者管理员来手动解决冲突。

4.单Master系统

本章讨论单Master系统的设计问题。单Master系统设计一个副本作为Master，所有更新发生在该节点。对于单Master节点，更新传播和调度是没有什么价值的，因为数据通路只有一条，从master到slaves。最简单的设计是state transfer，比如DNS的传输，NIS，以及WWW/FTP镜像。当Master更新一个对象时，分配给该对象一个新的时间戳。Slave的时间戳标记它目前拥有对象的版本。Slave节点周期性地拉取master，如果它的时间戳与master的不同，则从master处获得新的内容。另一种方式，每次对象更新，master向slaves推送更新，比如在DNS主动推送，或者NIS。单Master，操作传输同样存在于关系数据库系统，以及最近的DNS实现中。

冲突检测和解决对于单master系统不是问题，因为master节点可以立即检测和延迟并发更新，或者忽略并发更新。当系统需要处理频繁地，针对共享对象的写操作时，这样的特性让单master系统具有较好的扩展性。

不好的方面，master节点存在单点故障和性能瓶颈。但是，当系统开发需要最小化，或者服务基本由读请求组成，单Master复制仍十分有用。

5.多master的state-transfer系统

我们现在开始着手在多master系统中实现一致性。这一章讨论state-transfer系统；对operation-transfer系统的讨论在第6和第7章。

一个state-transfer系统在每个节点包括下面组成部分：对象内容，描述副本如何更新的信息（比如，a timestamp）。副本一致性管理通常通过下面步骤实施：

1）一个站点决定与另一个站点交换更新。许多系统拉取更新；比如，他们依靠周期性的轮询（例如，FTP镜像，DNS区域传输）。另一些系统，比如NIS，推送更新；比如，他们让一个有更新的副本负责将更新发送到其它副本。拉取与推送的选择是正交的，但它影响到系统的扩展性。我们在9.3节对推送机制进行更详细的讨论.

2）两个站点发现那些对象内容不同。（5.1节）

（注意：这里是两个站点，应该是通过两两比较来发现不同）

3）对每一个修改了的对象，站点需要发现它是否被并发修改。如果是，它们需要解决冲突。（5.2节）

4）解决后的状态被复制到各个副本。

我们将讨论Thomas写规则，一个流行的技术即可用来发现不同副本，也可解决冲突。我接着将介绍几个能更精细的发现冲突并解决他们的算法。最后，我们将讨论扩展性问题和空间开销。

5.1使用Thomas写规则的更新传播与冲突处理

State-transfer系统仅需要在哪个副本存储了最新内容上达成一致，因为将内容从最新副本传输到其它节点能让所有的副本获得更新。Thomas写规则是用于这个目的的最流行算法。[Birrell et al. 1982; Mockapetris and Dunlap 1988; Rabinovich et al. 1996; Gwertzman and Seltzer 1996].它名字来源于一篇介绍基于选举的悲观复制算法的文章[Thomas1979]，但现在它被广泛用于乐观环境中。

Thomas写规则如图4所示。采用Thomas写规则管理的内容是短暂的；一个更新能被并发的另一个用户的更新覆盖，没有人能确定一个更新何时被应用到所有的副本。

采用Thomas写规则，删除一个对象需要特殊处理。简单的删除一个副本以及它的时间戳，会造成update/delete的歧义。考虑站点a更新了对象内容（时间戳Ta）,站点b同时删除了这个对象(时间戳Tb).稍后，站点c接收到从b节点的更新，从磁盘上删除掉副本和时间戳。站点c接收与站点a通信。对于站点c如果Ta>Tb那么正确的操作就是创建一个对象，并忽略更新。但站点c没法这样做，因为它不再存储这个时间戳。

（说明：在我们实现的Robin中，这个问题在服务器端也存在。假设服务器就是站点c，服务器采用抢占式方式接受请求，站点a的update与站点b的delete在站点c执行后必将有一个全局序。如果先收到站点b的delete请求并执行，再收到update请求时会返回站点a请求失败，站点a将update请求转化为create请求发送给服务器并执行，服务器记录下操作日志将是，delete-create，这样其它节点需要同步时，执行delete-create操作即可。这个delete-update到delete-create的转化就是语义层的转化。）

图4. 使用Thomas写规则传播更新。每一个对象保存一个时间戳ts,标记对真实副本数据的最后一次修改。更新在本地发生利用IssueUpdate。每一个站点周期调用ReceiveUpdate，如果它的时间戳小于某一个站点的，那么将下载该站点的内容。

（思考：这里的问题是，如何在各个站点提供全局一致的时间）

两种方案来解决udpate/delete的歧义。第一种是采用离线方式，用户干预删除对象，例如在DNS和NIS中。第二种方式保存从磁盘上删除对象的时间戳（但不保存内容），例如在Usenet，Active Directory，和Clearinghouse。这样的时间戳通常被称作“death certificates”或“tombstones”。

5.2在State-transfer系统中检测与解决冲突

Thomas写规则对冲突解决实现了一个“Last writer wins”策略；他通过让节点最终收敛于最新状态来保证一致性（假设通信是完善的，更新最终不再产生）。这个规则不能显示地发现冲突，对于不能容忍更新丢失的交互应用这不具有吸引力。相关研究发展了两种技术来减缓这种情况：two-timestamp算法和version vectors.

5.2.1 Two-Timestamp算法

Two-timstamp算法扩展了Thomas的写规则来检测句法冲突。[Balasubramaniam and Pierce 1998; Gray et al. 1996].它被用在Lotus Notes和Palm Pilot中。在operation transfer中一些系统也采用了同样的技术。

这里，a站点为对象i保存一个时间戳Ti和前一个时间Pi。Ti随每次对象变化而更新。站点a和b通信，比较时间戳，采用下面的动作：

1）如果Ta=Tb & Pa=Pb，那么副本没有被修改。

2）如果 Ta>Tb & Pa = Pb,对象仅在站点a修改。站点b从站点a拷贝副本，并将Tb,Pb以及Pa设置为Ta。对称的，如果Tb>Ta & Pb=Pa，那么从站点b拷贝内容到a。

3）如果上面两种情况都不满足，则更新冲突。

（思考： Ta、Tb、Pa、Pb这四个时间，即站点a和站点b是否需要全局时间？）

这项技术的不足是不准确。当Master节点多余两个时，它可能会报告不准确的冲突，如图Figure 5。这个技术只能适用于Master节点很少，冲突也很少的情况下。

Fig 5. 使用two-timstamp算法发现冲突错误的情况。Tx和Px表示在站点x当前的和前一个时间戳。在第四步，站点a和c同步，算法发现了一个冲突，即使严格的来说站点c的数据比a落后。

5.2.2版本向量

版本向量（附件A.3）是另一种Thomas写规则的扩展，比前一种算法要准确许多。它第一次被用在Locus分布式操作系统。

与Thomas写规则中一个时间戳不同，在站点i上的一个副本拥有一个向量时间戳VVi，含有M个元素(对不同的对象，VV是不同的 [即每一个对象都有一个时间戳向量])VVi[i]表示在站点i对对象发生的最后更新时间，VVi[j]表示站点i接收到在站点j发生的最后更新时间。VV的交换、更新、比较采用常用的时间戳向量算法（附件A.3）。站点a和b检测冲突的步骤如下：

1）如果VVa=VVb,副本并没有被修改。

2）如果VVa主导VVb，对象仅在站点a进行修改。站点b从站点a拷贝内容和VV。对称的，如果VVb主导VVa，内容和VV从站点b拷贝到a。

3）其它情况，存在语法冲突。

与two-timestamp算法不同，VVs是完善和准确的；VV只有当真实的语法冲突存在时就能发现。不好的方面是不能方便地增加和移除Master节点，因为VVs已经将master节点编码到它的内部。

（思考：这个方法确实能准确的检测出冲突，但是节点扩展很麻烦。Master节点越多，当发生冲突时解决起来越麻烦。）

（思考：无论是two-timstamp还是 version-vector都有一个问题，分配给对象的时间戳与对象绑定，不同对象的时间戳是相互独立的。但在文件系统中相互独立这一点不成立，因为目录下文件的修改会改变目录的最后修改时间属性。所以在开发文件同步时会放宽同步要求，对于目录的一些属性不进行同步。）

5.2.3 State-transfer系统的冲突解决

一旦在语法层次上的冲突被发现，无论使用前面那一种算法，它必须被解决。很多系统简单的存储对象的两个版本，并请求用户来解决。

有时，挖掘对象的语义信息有可能自动解决冲突。例如Locus,Ficus,Roam,Coda，对孰知的文件类型通过resolver程序，结合语义来检测和解决冲突。比如，在邮件目录文件的一个语法冲突，可以通过计算来自多个冲突副本的信息单元来解决。在另一方面，对于编译产生的文件冲突不用解决，因为他们可以从源文件中编译产生。

写一个自动冲突解决器并不是一个轻松地工作。首先，在state-transfer系统中语义解决是否有限，前面的mail resolver，如果消息在一个副本重现将删除该消息。其次，resolver必须遵循严格的规则来保证一致性。这是必须确定的；选取和运行在resolver上规则，对于每一个冲突解决站点是统一的。一个resolver仅能依赖当前状态，不能访问随时间或站点变化的信息，比如当前系统时间或站点名。Resolver之间必须通信；例如，假设存在一个更新冲突集合，解决方法必须能生成一致的结果无论他们到达站点的顺序。

最终，解决器如果因为使用了超出限制的资源而失败，必须确切的失败：所有的站点必须采用统一的限制，在CPU、内存、以及文件资源等，在运行时必须强制执行这些限制。

5.3支持大对象

(说明: state-transfer系统，同步时传输的就是对象的timestamp，只有当发现需要进行更新时才传输数据对象。)

State传输系统的主要扩展瓶颈是更新（传播的开销）将会随着对象大小的增加而增加。这个问题可以通过多种方式解决，并不失state传输的简单性。

一些系统采用混合State和operation的传输；比如，DNS的增量zone传输，CVS，以及Porcupine。这里，每个站点保存对象过去较短时间内的更新，以及更新对应的时间戳，该时间戳记录何时更新被应用到副本上。当更新其它副本时，如果该副本的时间戳落在已保存的更新历史中，将仅发送差异部分，使得副本达到最新状态。否则，将发送整个对象。这个技术比operation-transfer要简化许多，但它需使用单个时间戳来串行化更新。

另一种途径是将对象划分为更小的子对象。关键问题是有效的发现子对象的最新更新，因为要简单地选出相互对立的子对象代价是十分高昂的。一些系统将子对象组织成一棵树（对于复制文件系统这十分自然），让每个参与节点记录下对它孩子最新更新的时间戳。然后基于这个写时间戳来应用Thomas写规则，逐步向下深入树，并缩小对数据内容的修改。其他系统明确地保存对子对象的更新日志，并采用与VesionVector类似的数据结构来检测对子对象的修改。他们非常像operation传输系统，但在很多重要方面存在不同。首先，日志是小的、受限的，因为它们仅记录被修改子对象的名字，以及数目非常有限的子对象。其次，他们仍采用Thomas写规则来串行化对每个子对象的修改。

5.4在空间上的开销

Tombstones是state传输系统空间开销的主要源头（VV-based系统仍需要将VVs保存为tombstones）。尽管tombstone很小，当对象频繁的创建和删除时，它仍会填满磁盘。对于绝大多数系统，tombstones会在一个固定周期后删除。这个周期要足够长，从而保证大部分更新能传播完全，当也要足够小从而保证较低的空间开销；比如，一个月的周期。这项技术不绝对安全，当通常在实际中工作的很好。

一些系统采用一致性算法来安全的删除tombstones。Roam和Ficus采用两段协议来保证每个站点，在移除对应的tombstone前，获得了更新。阶段一，通知一个站点，所有节点接受到了更新。阶段二，确保所有站点接受到了”删除tombstone”请求。相似的协议同样在Porcupine系统中使用。

6.多Master的operation transfer系统

我们转向研究多master的operation-transfer系统。Operation-transfer系统比state-transfer系统要复杂许多，因为副本为了能达到一致必须在操作集以及操作顺序上达成一致。一个operation-transfer系统工作的基本流程：

1）副本从一个公共的初始状态开始

2）每个Master节点维护一个log来记录本地提交的更新操作。除此之外，每个节点（无论是否为Master节点）从所有Master节点收集操作日志，存放在multi-log文件。6.1节将会详细讨论logging算法。

（思考：上面第二点表明每个Master节点将会有一个log文件和一个multi-log文件，非Master节点将只会有multi-log文件）

3）Master从本地用户节点后更新操作，本地应用，并将他们添加到log和multi-log文件。一个副本节点从远端Masters接收操作，应用他们，并添加到multi-log中。6.2节将更加详细地讨论更新传播。

(思考：log和multi-log中记录的操作是否记录修改的内容？这一点很重要。

如果记录修改的内容，那么进行重新执行就可以恢复到文件的任何状态。

如果不记录修改的内容，当根据log进行更新时，会存在operation对应的文件其数据已经变化，不再是这个operation所做的修改。)

4）正确的更新应用顺序，叫做schedule，被副本节点逐渐的了解，通常与更新接收的顺序并不一致。当一个站点添加请求到multi-log，它将重新计算schedule(调整到它所知的最好结果)，执行schedule, 可能会取消或重做已经应用到副本上的操作，从而使得其达到下一个短暂的一致状态，。从第七章开始到7.3节将会讨论调度算法。

（思考：节点接收更新，进行调度，然后执行。这三步是一个整体，一个周期，循环执行，还是说这三个步骤各自独立，可分别独立运行？无论是一个整体，还是各个部分独立，不同的副本节点收集到的更新都会是不同的。所以副本节点所执行的调度仅仅是它所知的最好调度结果。

调度还是有一定意义，比如文件大量的创建后紧跟着这些文件的删除，如果没有调度，所有这些操作的执行是十分的耗时的。）

5）选择性，当发现操作冲突，节点将会解决他们。第七章讨论冲突处理。

（思考： 发现操作冲突？是发现操作之间的冲突。因为前面提到了节点会将本地进行的更新也记录到multi-log中，加上multi-log还会拥有其他收集其他所有节点的更新，这样multi-log将会拥有所有的更新，只用发现这些操作之间的冲突就是全部的冲突了。

说明：我们的Robin记录了操作，但并不去发现这些操作之间的冲突。因为这个冲突发现十分复杂，计算量很大。这里的冲突发现计算，等效于在一个N个元素的集合中，发现任意m个元素是冲突的，m从2取值到N，这个计算是不可行的。）

6）当所有节点对一个操作集合的schedule达成一致，他们将把操作提交到state,从multi-log中移除这些操作的记录，然后重头执行这个算法。7.5节将讨论提交算法。

（思考： 所有的节点对一个操作集合的schedule达成一致，这在一个节点频繁加入离开的网络不能。同时这也是矛盾的，因为每个节点能收集到的operation是不一样的啊，如果operation的集合元素都不一样，又怎么能在这些元素的schedule上获得一致呢？

前文中提到epidemic 传播，Any site communicates with any other and transfers both its own updates and those received from other sites. This protocol eventually broadcasts every update to all sites whatever the network topology, including when connectivity is poor or incomplete.

虽然能让每个节点都获得所有的更新，但这是最终将获得所有的更新，中间状态不是。所以中间状态的调度很难实现所有的节点能达成一致。

“重头执行这个算法”让我认为这里operation-transfer系统是基于这是一个同步系统的假设。这对我们一点也不适用。我们需要处理的是异步的系统。）

（思考：从目前来看这篇文章来看应该讨论的是异步系统，但是operation-transfer的同步过程却十分像同步系统，这一点让我非常困惑。我们思考的角度应该是异步系统，采用基于队列的方法来获取一致性。）

6.1构造一个日志

一个log可以被看做一个过程，将共享对象从初始状态产生出另一个暂时的一致状态。当设计logging算法时从三个方面进行选择：

1)记录日志的抽象层次

2)是否清理冗余的操作

3)是否记录或重建用户操作

第一个选择是日志记录操作的抽象层次。两种极端情况，一种日志仅记录字节区域的读与写，基本不包含语义信息。一种记录高层的用户操作，富于表达并简明清晰，但对于推理却十分复杂。建议记录简单的操作（便于推理），聚合起来表达高层次的意图（表现力）。

日志如果不含冗余操作，被称为clean;没有更短的日志，可以从初始状态产生中间状态。一个clean log不仅是否有效并容易推理。考虑一个写作的锯齿谜题。假设用户A将X放到某个位置。同时用户B将X放到不同的位置，过会儿他改变了想法并移除它。如果B的log是clean的，它将不会包含对X的移动，系统将会很容易判断这些操作是没有冲突的。

最后选择，是否将操作按他们被期望的方式记录，以及是否根据当前状态和初始状态的不同来重建一个可能的操作历史。

（思考：这一点很重要，我们需要这样做，因为操作log不能无限增长啊。长时间未同步的节点必须通过状态比对来构建可能的操作历史）

通过拦截恰当层次的用户行为，可以记录任意层次的操作日志，但它必须在一个独立干净通路上实现。与此相反，diffing可以在对象编辑者之外实现，同时它的日志自然是clean的；但它需要十分清楚编辑者的修改意图。

6.2使用Timestamp向量的更新传播

Operation-transfer系统必须将所有的更新传播到所有的节点，即使在某一时刻并不是所有节点都可达（比如,epidemic更新传播，在第1章中已定义）。一个朴素的解决办法：让每个节点周期性的发送他整个multi-log到其它节点。假设有足够的时间，让站点进行至少间接的通信，这个方法最终将传播所有的更新到所有的节点。它有一个明显的不足，无法控制的磁盘开销和网络带宽消耗，因为它将聚集不断增多的更新。

在Operation-transfer系统中，解决方法时采用timestamp向量。站点i记录M个元素的时间戳向量TVi。TVi[i]保存在站点i发生的操作数，i.e.,即站点i的log数。TVi[j]表示站点i接收到的来自站点j的最新更新。TVs的不同，可以准确的标记出需要进行交换的更新集合，从而使他们一致。

Fig.6. 副本节点一致采用timestamp向量。接收端先调用发送者的“SendUpdate”过程并传入自己的timestamp向量。发送者发送更新给接收者，接收者在“ReceiveUpdates”过程中处理他们。

图6表示采用timestamp向量的更新传播过程。从站点i传播更新到站点j，站点i向接收j的timestamp向量，TVj。站点i一个元素一个元素地比较TVi和TVj。If∃k,TVi[k] > TVj[k],站点i从它的multi-log中抽出发生在站点k的时间戳大于TVj[K]的操作，并发他们发送给j。这种方法保证站点j能收到所有保存在站点i的更新，同时站点j将不会收到它已经拥有的更新。然后交换角色，让站点i接收来自站点j的更新，这样两个站点将会收到相同的更新集合。

7.Operation-transfer系统中的调度和冲突处理

本章讨论operation-transfer系统中的操作调度算法，以及为达成一致的冲突操作解决。调度紧密地依赖可靠的组通信，向所有站点传播顺序定义良好的网络消息。实际上，TSAE(Time-Stamped Anti-Entropy protocol)作为一个组通信服务出现，尽管它很容易被理解为一个乐观复制服务。本书中呈现的语法更新调度，基本上对应全局广播和因果广播。语义更新调度对应与应用相关的因果广播，进而解决并发更新。（这句话翻译不是很确定，附上原文：Syntactic update ordering presented in this paper roughly corresponds to total and causal broadcast, and semantic ordering corresponds to causal broadcast with an application-specific policy to resolve concurrent updates.）然而，实现该策略的机制会非常不一样，因为乐观复制系统的工作方式是异步的，epidemic。

从一个相同的初始状态开始，结合相同的操作集合，当每一个节点计算出一个能获得一致最终状态的调度时，operation-transfer系统将取得一致。更准确地描述，我们需要下面属性：

1）对于所有节点，调度存在一个相同的前缀，我们称为共同前缀。（调度前缀相等，指他们包含相同的操作，同时他们可以从一个相同的初始状态开始，生成相同的状态。）

2）每一个操作最终会包含进入共同前缀，要么被执行，要么不被执行。

3）一旦进入共同前缀，操作不再被移除、也不再改变状态。

为了进行冲突解决，前面的定义允许调度将一个或多个操作无效化，比如，不执行它们。因此，如果两个操作冲突，一个或者另外一个将被无效化。一个更通俗的定义，允许冲突操作集被转化为不冲突的操作集。

这里有多种方法来产生一个相等的调度。一个充分条件是，调度的结果是完全一致的（假设，悲观操作）。语法调度策略，采用静态规则在全局进行更新调度，产生一个完全相同的调度结果。一个完全相同的调度结果，并不是保证调度相等的必要条件。（相等不等于完全相同。相等指的是不同节点调度后的更新，产生的结果是一样的；完全相同，指不同节点调度后的操作完全一样，包括顺序）语义调度需要深入操作语义，局部调度更新来消除冲突，产生相等的调度。操作转化，在7.3节中描述，修改操作本身，不需要重新排序从而让调度结果相等。7.4节讨论更新冲突解决策略。7.5节讨论更新提交（或者说，稳定化），该机制是让副本统一的调度结果被持久的应用到节点上，不用担心被撤销。

7.1 语法操作调度

操作调度的最低要求是调度结果兼容happens-before偏序关系（附件A.1）。语法调度策略通过静态调度规则实现最低要求。

很多系统为每一个操作记录一个标量时钟（比如，物理时钟、逻辑时钟；见Appendix A.2），使用它们来对操作排序，比如在Bayou，TSAE中。

（思考：注意State-transfer系统中，是为对象记录时钟，而不是为修改操作记录时间戳。）既然一个标量时钟无法检测冲突，这些系统必须采用一个独立的机制来检测冲突语义。

你或许认为可以采用Version Vectors来对操作更新进行排序和冲突检测，但它们却在Operation-transfer系统中并不常用。因为Multi-log通常已经记录了操作的语义关系，而Version Vectors提供很少的额外价值。

7.2 语义操作调度

一个不同的操作调度方法，是视调度为一个优化问题，为了消除冲突，实现一致。因此语义调度比语法调度要复杂许多，但可以消除冲突和重新排序不确定的操作。

7.2.1挖掘交换特性

最简单的语义调度是挖掘操作间的交换特性。两个操作known to commute a priori可以被以任意顺序调度，而不会影响最终结果。这样的特性在数据库系统很早就被使用，查询优化器通常会重新调度可交换的操作来产生更有效的序列。Wuu and Bernstein[1984]挖掘数据的交换特性，从而维护一个多Master，可复制的日志数据结构。在该数据结构中，插入和删除操作是可交换的，幂等的，这样调度就不是一个问题了。In GemStone,一个对象可以通知数据库系统它所含操作的交换特性。数据库检测可能的语法冲突，并忽略有数据类型申明的可以交换的冲突操作。

7.2.2典范操作排序

典范次序排序，根据应用语义对操作顺序给出正式形式化的描述。它被Ramsey and Csirmaz最先提出，他们对文件系统的乐观复制和协调进行了形式化描述。这里，日志和调度采用了一个形式化的代数关系进行描述，能准确地定义操作间的交换特性。举例来说，如果一个操作删除一个目录，另一个操作（在其它日志中）删除该目录的子目录，那么子目录必须比它的父亲先删除。当这里没有自然结构顺序，典范顺序将是随意的。（说明：自然结构顺序，比如说目录的父子关系）来自不同日志的两个操作（语义上）冲突，要么是他们不能互换，要么就是他们的结合破坏了文件系统结构。这很可能发生，比如，如果用户修改了一个文件，另一个用户删除了该文件的父目录。

调度Multi-log使得共享文件系统的各个副本，尽量的一致“as close as possible”。调度器忽略了重复更新。它不激活冲突操作，它们依赖于先前未激活的操作，并将冲突保存下来，由人工解决。

Ramsey和Csirmaz提出的操作很少，很简单：创建、删除、修改。虽然如此，他们整理51条规则。将他们的技术应用到一个更复杂的环境下是一个开放性问题。

7.2.3 IceCube中的语义调度

IceCube是一个与应用无关的复制工具，在基于操作的语义约束上计算最优的调度序列。IceCube支持两种类型的约束：

1）静态约束限制的是两个操作间的关系，不需要访问被更新对象的状态。在静态约束限制中，日志约束说明在一个日志中操作间的关系；即，它表示用户的意图。比如，一个日志约束可能加强两个操作间的执行顺序（前后约束），或者它会声明一个原子的更新单元（包裹约束），或者它可能会申明一些可选操作，供调度器选择（可选约束）。

一个对象约束，关系到对共享对象的修改操作。定义了四种对象约束：覆盖（两个操作更新了同一个对象），互换，互斥，最佳顺序（一个比其他顺序更好的执行顺序）。

2）动态约束，是一个断言，调度在执行时必须去进行判断该断言是否为真。它可被称为Bayou-style“依赖检查”，或经典的前置和后置条件。

举例说明，考虑一个旅行计划应用，采用IceCube运行在非连接网络环境下。用户可能会预订一个航班，为门票付费，以及计划在旅途中开一个会。在同一个session中，用户可能会设置一个不相关会议。当用户重新连接时，冲突可能会出现，原因可能有航班已满，不足够的资金，或者一个冲突的会议时间。

用户可以将三个相关的操作打包到一起，来表达他的意图，即当它们中任何一个失败时就取消所有的操作。这不相关的会议就不被打包到一起。如果另一航班具有相同的作用，则可以作为一个可选操作。共享日历实现它的语义，通过将不相融的会议交给用户手动排除。根据银行账户的语义，向账户中存入，和从账户支出两个操作，最好的顺序是先存入再支出。最后，银行设定一个动态的约束，用于支付门票的账户不能产生负值。

IceCube调度器，循环地选择和尝试满足静态约束的调度。如果一个动态约束不被满足，IceCube将跳过当前调度的执行，处理其他。使用静态启发方法，给予最可能成功的操作较高的优先级，根据静态约束规则以及最近动态约束判断失败的经验来选择最可能成功的操作。IceCube可以在1秒中调度上千操作。

7.3 操作转换

操作转换（OT）目标在于当调度结果不一致时保证最后结果的一致，操作是不能交换的，也不能被重新调度或者回滚。采用操作转换的典型应用是合作式文本编辑器，每一个操作包含字符改变发生的位置。假设，用户编辑共享字符串“abc”。用户1执行insert(“X”,1)产生“Xabc”，然后发送更新给站点2。用户2执行delete(1)产生“bc”，发送更新给站点1。站点2的执行结果是“Xbc”，与预期的一致。但站点1的结果是“abc”与预期的不一致。OT修改操作的参数，保持它最初的意图，尽力让所有节点效果一致，而不是考虑接收的顺序。这个例子中，OT发现insert和delete操作并发，它在站点1将delete操作修改为delete(2)。

OT十分复杂，高度依赖应用语义。转化一对冲突操作是与直觉紧密联系的，当有三个或者更多线程并发，转化的处理会更加复杂。有理由对这个文件进行形式化处理，采用cormack提出的微积分方法。比如，Palmer和Cormack证明了共享spreadsheet操作转换的正确性，支持所有常见的操作包括：更新cell值，添加或删除行或列，以及改变公式。

7.4 解决冲突操作

自然地，冲突解决是高度依赖应用的，很难进行概括。对于operation-transfer系统这一点特别的真实，因为operatio-transfer系统通常都会描述操作的语义。这一节我们讨论Bayou系统，并概括它将应用逻辑和可重用的冲突检测和调度算法分离的意图。

Bayou根据更新发生顺序进行临时的调度。它不进行语法冲突的检测。Bayou系统中的操作包括三个组成部分：一个数据库查询称为依赖性检测，一个数据库更新，和一段代码叫做合并过程。三个部分都由应用提供，运行在Bayou上。依赖条件判断负责处理检查语义冲突。通常，它检测当前的副本状态，对于用户来说是否可以接受当前的更新请求。比如，如果从银行账户划出账目，依赖条件会检查该款项是否超过用户定义的阈值，因为账户的余额可能在更新发起时变化。如果依赖条件判断成功，Bayou将执行更新。如果判断失败，合并过程将执行。合并过程可以执行任意必要的操作。比如，如果用户试图设定一个约会，依赖条件发现没有空余的slot，合并过程可以选择另一个slot。

在Bayou中编写一个合并过程并不容易。加在基于状态解决器上的所有严格限制会被应用。实践表明，即使为最简单的应用编写合并过程也是极其困难的。

7.5 提交操作

本小节讨论更新提交协议，比如当副本对一个等价的调度前缀达成一致是，将允许他们提交。提交有三个方面的作用。首先，系统的调度策略可能会产生非确定的结果，这种情况下，站点需要对最终应用的选择达成一致。其次，提交可以通知用户一个特定的操作最终被应用到所有的节点。第三，提交可以满足空间约束的限制，因为提交后的操作可以被安全地从multi-logs中移除。

7.5.1 Ack Vectors

确认向量与时间戳向量结合使用，从而使站点了解到其它站点的进展。站点i保存确认向量AVi，一个N个元素的时间戳数据组。AVi[i]定义为TVi[j]中最小的值，j属于{1…M}。表示，站点i接收了的更新中，没有哪一个操作的时间戳比AVi[i]更加新，无论更新来自哪个站点。确认向量，向TVs一样在节点间进行交换，通过成对的最大值比较而被更改。因此，AVi[K]表示站点i保守的估计站点K所接收到的最后更新。这样的定义下，所有时间戳早于 minAVi[j]的更新可以确定被所有站点已获取，它们可以被安全的重新排序，提交，和从multi-logs中删除。这个算法需要采用已同步的较宽松的物理时间，作为时间戳使用。否则，一个时间戳很慢的站点将拖延所有其它站点的确认向量。

（说明：原文这一段真没看懂）

这种算法比主提交协议要差（我们下面将介绍主提交协议）。首先，它只能被用于语法、基于时间戳的调用。它容易产生live-locking的情况。一个反应迟钝的节点，会拖延所有站点的确认向量，当站点增多时这种情况会更糟。

7.5.2 Primary Commit Protocol

Bayou实现了一个主提交协议。在这个协议中，所有站点对一个对象，在主站点上的更新取得一致意见（Bayou的一个事务不能访问多于一个对象）。主站点单方面的，从全局的角度对操作排序，并给予每一个它受到的更新，一个单调递增的提交顺序号CSN。这个主节点可以灵活选择任意的调度策略；Bayou使用语法的，基于时间戳的排序。操作与CSNs的对应关系，将通过日常更新传递给其它站点。一个非主站点，接收到CSN后可以按他们的顺序提交操作，并从multi-logs中删除。

需要注意该协议与单master复制的区别。在主提交协议中，所有的节点都是masters。即使在主节点无法到达的情况下，其它节点仍可以发起，交换，和临时地应用更新，因为主节点仅完成CSN的分配。

7.5.3 Quorum Commit Protocal

该协议由Deno提出，是悲观算法提交协议，但同样被应用在乐观环境中，因为它能在并不是全部节点都可用的情况下执行。在复制的每一步中，采用状态机方法，对于未解决的请求执行选举算法来提交每次请求。它给每一个<site,update>对分配一个权重，对于每一次更新总的权重是1.0。每个更新在所有节点周期性循环。当节点收到一个更新时，如果更新与本地其他已完成的更新没有冲突，该节点投票支持该更新。当节点观察到对于一个更新的权重达到一个阈值时，节点在本地提交请求，同时它发送一个确认通知给所有其他节点。

通常情况下，提交协议每次顺序地处理一个操作。当某个操作与已经提交的操作冲突时，它会被忽略直到他们能相互兼容。Denon允许在应用中声明操作的可交换性。模拟实验表明，该协议表现的与经典primary-copy策略十分相似。

保证内容质量

乐观复制算法不能保证单个副本的一致性。一致性仅能保证副本在静止状态是一致的，或者在过去的某一个虚拟点上是一致的。因为更新请求的到达可能是乱序，以及没有严格的传输延时限制，乐观复制难以向用户提供某一个时间点上副本内容的一致性保证。

一些复制服务在采用弱一致保证时仍工作的很好。Usenet和Porcupine邮件服务就是这样的例子；副本不一致不会比NNTP和SMTP中的潜在问题更糟糕，比如消息的延迟发送和重复发送。很多服务，受益于更加严格的内容质量保证。本节将分析多种用来控制副本内容在瞬时质量的方法。8.1.2小节讨论保证对象读和写请求因果一致性的技术。8.2节讨论明确限定不一致副本数量的算法。8.3节讨论了保证副本内容质量的概率技术。

这些方法并不是灵丹妙药，当副本内容太旧它们会禁止对对象的访问，或者需要进行内部站点的同步通信。换句话说，它们也无法避免在可用性和一致性之间进行权衡。

8.1保证访问请求间的因果关系

按因果关系对请求进行排序是任何乐观复制系统的基本特征。它保证了最终对象的内容是用户期望的结果，虽然它无法保证瞬时内容的质量。例如，密码数据库问题（1.3.2小节）就是因为缺少内容质量的保证。一种解决方法就是让用户来声明哪些更新请求应该在读请求之前发生，然后延迟处理这些读请求直到更新被所有的节点处理。类似的技术包括下面几种：

8.1.1明确的因果依赖

这种方法简单地让用户来明确说明，对于每一次读请求，在副本节点上哪些更新请求应该被执行后才能执行读请求。该方法可以使用版本向量控制，对于状态和操作传输系统都很容易实现。这里，一个副本节点的状态被表示为一个版本向量。请求依赖同样采用VV（Version Vector），这样请求将会被延迟处理，直到该请求所依赖的VV被副本节点状态VV所包含。

8.1.2 Session保证

前一种方法的不足是，对于用户来说声明依赖关系并不是一件轻松的事。Session保证是一种自动化的方法来保证因果依赖特性。用户可以选择预先定义的下面几种因果关系。

(思考：Session Guarantees要考虑同一个用户，前后两次请求，交给不同的replica节点处理。)

“Read your writes”(RYW)保证对于同一个用户，从副本读取的内容包含了该用户之前执行的所有写操作。陈旧密码的问题可以通过强制RYW特性来解决；用户要么等待新密码被传送到副本，或者接收到一个“陈旧副本”错误，这两者相比读取到一个旧密码来说都不容易让人困惑。

“Monotonic reads”(MR)保证同一个用户两次连续的读请求能够获得及时的内容更新。例如，对于采用副本的邮件服务，用户可能会先获取一下邮箱的摘要，随后读取其中一封摘要对应的消息。MR保证用户不会获取到一个“non-existent message”错误。（除非，用户在两次读取操作之间删除掉了该信息）

（思考：这里保证的是，用户前后两次读请求，从不同副本节点能够获取到的内容是向前包含的。即第二次读请求获取的内容肯定要包含第一次读请求的内容，除非用户在这两次读操作之间执行了删除操作。）

“Writes follow reads”(WFR)保证对于同一个用户，在这个副本上，前一个读请求能够看到的更新已经在这个副本上被执行。

（思考：比如从副本上读取一个数A，执行A+1这个操作。如果没有WFR这个保证，当把A+1这个请求发送给另一个副本，该副本可能会出现保存的A值与前一个副本不一致的情况，这样会造成该副本执行A+1后的结果与用户预期的不一致。）

“Monotonic writes”(MW)属性保证对于一个副本节点，写请求只有在该用户之前所有的写请求被应用到该副本上时才执行。例如，一个源代码管理系统。一个库模块在一个节点被修改了，应用程序在另一个节点被修改，但它依赖更新后的库模块。MW保证库的更新在应用程序的更新之前进行。

当用户仅访问一个站点时，这些属性都自动得到保证，这些复制算法来保证更新间的happens-before顺序。在移动环境中，他们采用session的方式来实现。Session，被每个用户所保存，记录两个部分信息：由用户发出的写请求集（write-set），以及用户通过读取操作观察到的写请求集合(read-set)。Table 3总结了Session保证的实现。例如，保证RYW，用户发出的每一个更新请求被追加到该用户的write-set。因此，在返回一个读请求之前，副本确认用户的写请求集合是否是节点已应用写请求集合的子集。如果是，则读取成功；如果不是，用户要么等待，要么接收到一个“陈旧副本”的错误。类似的，对于MR保证，对于每一次读请求，副本要检查用户的read-set是该副本节点已应用写请求集合的子集。在回复请求后，用户将站点请求的更新情况添加到用户的read-set中。

8.2限制不一致

一些系统明确地限制副本不一致状态的数量。对于非副本数据库，为了提高性能会放松两段锁协议，但在这之后仍有大量的工作要做。因此，他们并不适合移动和分布式广域网环境。尽管如此，这里仍有一些系统为乐观复制环境而设计，我们下面将要介绍到。

实时性保证，例如，限制传播延迟在网络服务中就十分流行。类似的系统比如，WWW、NFS、DNS以及quasi-copies。缓存对象，并保证该对象的陈旧状态小于一定秒数。这样的系统大部分是单Master，基于拉取操作的系统，因为他们可以简单地通过轮询方式来实现实时性的保证。

TACT提供了三种类型的一致性保证：实时，数值型，以及秩序边界。在TACT中，实时性保证与WWW服务有相似的语义，但它是通过按需推送的方式实现。

数值边界，在不同副本上设定数值限制。它给每一个master副本设定可接受更新的配额，在达到配额后需要将更新提交给远程副本。例如，一个用户的银行账务存在10个master副本，设定限制如下，当读取请求所含的金额小于$50时可以从任意节点读取，每个master节点有$5的配额。任意master节点接收到的账户修改请求累计超过$5时，它必须将更新发送到其它节点，才能接受后续更新。

其它边界限制要确保副本当前值与已提交的值之间不能超过X次更新，X的选取可由不同副本决定。这种保证相比数值边界可能更弱，因为后者保证副本的瞬时值与其它副本瞬时值间的差异不超过X次更新。当与瞬时值或提交值的差异超过限定时，副本节点通过从其它节点拉取更新来满足边界限制。

8.3用概率技术来降低不一致

本节所讨论的技术依赖对负载情况的了解，在最小的开销下降低副本节点变陈旧的平均概率。

Cho和Garcia-Molina根据web代理的页面更新频率以及顺序，来研究更新策略，他们基于更新间隔符合泊松分布的假设。他们发现为了最小化页面平均陈旧度，副本需要每次按照相同的顺序，在同一的时间间隔来获取更新，即使一些页面要比其它页面更新的更加频繁。

Rowstron，Lawrence,以及Bishop采用真实的数据做了相同的研究。他们提供了一个工具，利用概率模型从过去日志中学习更新模式。这个工具选择一个恰当的周期，每天或者每周。周期被划分为更小的时间槽，该工具绘制每一个槽的更新概率直方图。一个移动新闻服务被选作研究案例。这里，应用运行在一个移动设备上，当需要下载最近更新时连接主数据库。假设用户愿意每天建立固定次数的连接。该应用利用概率模型来选择连接时间点，从而优化更新的程度。通过将固定周期连接与他们提出的自适应策略连接对比，更新度平均提高了14%。

9. 扩展乐观复制系统

本节讨论在乐观复制环境下如何支持大量副本节点。（支持大对象的问题在5.3节已经讨论过了）我们将讨论支持许多副本的挑战以及三条补救路线：一个结构化的通信拓扑，主动式的更新推送，以及高效网络。

9.1 评估冲突比例

支持多副本会产生两个问题：增加更新冲突以及传播延迟。更新冲突问题需要一些说明。Gray，Helland,O’Neil和Shasha指出多master的乐观复制系统无法支持大量的master副本，因为它们会产生O(M²)的更新冲突，然而，单master系统将仅产生O(M)的更新冲突。直观上，在多master系统中并发更新将被调节，然而在单master系统利用类似两段锁技术，它们会被延迟或者丢弃。丢弃需要对更新间因果依赖关系的一次循环，同时丢弃发生的概率远小于冲突发生的比例（Prob(abortion）约等于Prob(conflict)²)。Gray基于两个重要的假设来推导出它的结论：在所有节点上数据会以相同的概率更新，同时节点交换更新会以统一的随机性选择其他节点。这样的假设并不普遍适用。比如，在文件系统中的共享写操作就很少发生；文件被共享的越广泛，则越少被写。因此，实际中冲突问题有多严重仍不清楚。

（思考：上面这段最后的意思是否是说，最终人们还是不清楚实际系统中冲突情况有多严重，因为很难测量和建立模型分析真实的冲突情况。）

两个问题-更新冲突和传播延时-能通过以下方法缓和。1）结构化通信拓扑，这样发送到所有节点的更新将只需要很少的跳数。2）主动推送更新，在它们发生后越快越好。3）使用高效地网络协议来快速传播更新。我们将在下面部分讨论这三种方法。

9.2 通过控制通信拓扑结构来扩展系统

我们所能发觉的冲突可能，可以通过节点间特定的连接方式来减少冲突。Figure7展示了一些例子。当站点采用星型结构连接，冲突的可能性被极大地减少。因为中心节点可以在解决完冲突更新后再将更新发送给边缘节点。

（原文注解：注意星型结构与单master系统的不同。单master串行化所有的写请求；星型结构的多master系统在中心处解决所有的冲突。(我不认为是所有的冲突都可以在中心节点解决)）（思考:当Robin中心节点向客户端节点发送更新时，仍需要在客户端进行更新冲突解决。CVS也存在这个问题。所以我觉得中心节点解决完冲突后，在边缘节点仍会需要对冲突的解决。）星型拓扑能更快的传播更新，因为任意更新传播到任意节点都只需要两跳。CVS是一个大家所熟知的例子。两层复制时星型结构的衍化。这里，站点被划分为强连接的“核心节点”以及弱连接的“移动节点”。核心节点通常采用悲观复制算法在节点间保持一致性，叶子节点采用乐观复制并仅与核心节点连接。注意，星型拓扑和两层拓扑仍需要解决多master乐观复制系统的所有问题--可靠的更新传播，调度，冲突解决--但它们能有更好的扩展性，不过这是以牺牲通信的灵活性为代价。与之相反，每个节点能随机地与任意节点通信的拓扑结构，会有最快的传播速度以及最高的冲突比例。

这些方法并不是灵丹妙药。首先，它们仍会在传播速度，负载均衡，以及可用性上付出代价。星型拓扑给中心节点过度的压力，在实际环境中会减慢更新传播。同时，中心节点会成为单点故障。随机拓扑，好的方面在于具有高可用性，负载可以被最终分解到所有节点。其次，站点无法总是可以选择节点进行通信，特别是在移动自组网络环境中，通信拓扑取决于人们的需求以及连接设备。

其他几种拓扑结构也被用于真实世界的系统中。很多采用树形拓扑，它混合了星型和随机拓扑的属性。Roam将中心节点连接成一个环，放开了其它节点的连接。多master系统，比如Usenet，Active Directory将这个概念进一步发展，将节点采用环型或树型结构连接，同时支持节点间的快捷路径，从而提高可用性和加速更新传播。

9.3 推送技术

讨论到目前为止，我们假设节点知道何时开始传播更新以及知道将更新传播给谁。在一些应用中这并不是个问题。比如，一些明确依赖手工同步的应用，以及一些仅管理少量对象可以采用周期拉取方式的应用（如，WEB镜像）。在更多的环境中，推送更新会更好—让节点承担推送更新到其它节点的责任—减少更新传播的延迟，消除拉取更新的开销。推送更新的挑战在于，它可能会发送重复更新，增加网络资源的消耗，以及增加更新处理的开销。我们从最简单的推送策略泛洪开始，然后讨论一些降低泛洪开销的技术。

9.3.1 Blind Flooding

泛洪是最简单的推送策略。当节点发生更新时，它将更新盲目地推送给它所连接的所有节点。接收节点使用Thomas`s写规则或者时间戳向量来过滤重复请求。该技术被应用在Usenet,NIS,Porcupine,以及很多关系型数据库中。

最简单的泛洪有一个明显的缺点：当一个节点域多个节点连接时，它会发送重复的更新。可以在发送更新前，猜测远程节点是否拥有本次更新，从而消除更新重复发送的问题。在多master系统中类似的信息无法避免，不管怎样，下面我们将看到用来解决该问题的多种技术。

9.3.2 连接状态监控技术

Rumor mongering和directional gossiping都是采用概率技术来避免重复更新。Rumor mongering从泛洪开始，但每个节点监控它所收到的重复请求。当重复请求的数目达到一个阈值时，节点将停止发送更新。在directional gossiping中，每个节点观察更新所经过不同路径的数目。一个不被多个路径所共享的内部链接会更重要，因为它可能是该节点链接到其它节点的唯一链接。因此，该节点会更加频繁地向这样的链接上发送更新。对于多个路径所共享的连接，节点将会减少更新的发送，因为其它节点可能会从不同路径上发送相同更新。

两种技术都是基于概率论的，因此他们可能会丢失发送给副本的更新。因此，为了实现可靠的更新传播，系统偶尔需要对泛洪方式进行重新排序，将更新发送到某些忽略了该更新的站点。模拟结果显示，在合理参数的设置下，这种方法能够消除重复更新，同时保持更新传播可靠度接近100%。

9.3.3 时间戳矩阵：估计远端节点的状态

另一种消除重复更新的技术，是让每一个节点估计远端节点处理的状态，仅发送远端节点可能缺少的更新。时间戳矩阵，在多master系统中被使用的例子包括Wuu and Bernstein 1984; Agrawal et al. 1997.

站点i保存一个时间戳矩阵TMi，一个N*M的时间戳矩阵（N是所有副本节点的数目，M是master节点的数目）。TMi[i]是节点i的时间戳向量。其它TMi的行，是节点i估计其它节点保存的时间戳向量。因此，TMi[k][j]=c,表示节点i认为节点k收到来自节点j更新的时间戳最少也是c。更新传播的流程如Figure8所示，与Figure6的时间戳向量处理类似。唯一的不同是，当发送更新给节点j，节点i采用TMi[j]作为对节点j时间戳向量的估计，而不是从节点j接收一个向量。

9.4 添加和移除master节点

时间戳向量每一项表示一个master节点。因此，它的空间复杂度随着系统规模而线性增长。通过标示符来区分master节点比数字1…M要方便许多，比如节点的IP地址；时间戳向量的记录是稀疏的，所有节点的标示符对应这些节点上时间戳向量的一行。添加一个新的master是相对容易的。

删除一个永久离开系统的master节点则比较复杂。当Z的时间戳向量中表示master节点Y的项无法访问时，Z必须区分节点Y是加入（Z可能还不知道节点Y的加入）还是离开（Z或许忘记了从时间戳向量中删除Y）。如果无法区分这两种情况，会造成系统重复的拉取已经应用的更新。因此，所有节点必须一致地移除掉TV中的项，当master节点离开时。Ratner1998;Peterson et al.1997;Adya and Liskov 1997提出的一些协议可以做到这点。

支持更多节点的系统将会面对更频繁地节点加入和离开。许多系统确实需要离线操作来添加或删除节点。（比如，NIS，Usenet）这样的设计仅仅在节点集合基本为静止状态可以采用。

添加和删除节点对于单master节点以及基于拉取的状态传输系统比较容易处理。事实上，这就是为什么WEB和FTP镜像乐于采用拉取，状态传输。它们系统在完全不同的管理域中可以轻松地添加新节点。

对于采用TV和ＴＭ的系统，前一节假设站点的数目是准确知道的，同时它们被连续编号。然而，节点的加入和离开是动态的；分配一个密集的编号并不可行。实际中并不可行，为了采用了一个稀疏标示符来从节点的唯一标示（如静态IP地址）映射到目录上。添加一个节点很简单：当收到的消息包含一个未知节点的标示符，则添加到向量或者矩阵中，并给它分配一个值为0的时间戳。

然而节点删除则是一个问题。当Z的时间戳向量中表示master节点Y的项无法访问时，Z必须区分节点Y是加入（Z可能还不知道节点Y的加入）还是离开（Z或许忘记了从时间戳向量中删除Y）。如果无法区分这两种情况，系统将不正确假定之前的时间戳为0，然后再一次地拉取已经获得的更新。

在Bayou中采用的方法如下。考虑节点X添加一个新的节点Y到系统中。Y节点的唯一标示是一个三元组，节点X的唯一标示，X时间戳向量的创建时间，（节点的唯一标示是一个任意分配long型数值）。节点创建事件将被写入日志并传送给其它节点。当其它节点Z收到消息包含Y的唯一标记时，同时节点Z的TV中没有Y，那么它可以区分添加和删除：

--如果Y名字中的时间戳向量小于TVz[X]，那么Z之前并没有收到Y的创建消息。Z将Y添加到TV中，并设定预值为0。

--否则，Z之间得到过Y的创建事件，TV中不存在Y的原因是Y曾被删除过。

10. 总结

本节将会对前面给出的算法和系统做一个总结，并为乐观复制系统的设计者和用户给出一些建议。

10.1 对比乐观复制策略

表4总结了Section1.4中所介绍的乐观复制系统在最高比较层面上的不同。该表说明了这里并没有唯一的赢家；每种策略都有自己的优点和缺点。单master传输对于请求负载主要为读取的应用并仅有一个写入节点的应用是一个好的选择，因为它的实现简单同时没有冲突。多master的状态传输相对简单，较低的空间开销（为每一个对象保存一个时间戳，或者版本向量）。它的不足在于，进行冲突解决时无法利用操作的语义信息，同时也会随之对象数目的增多而增加它的开销。因此，对于同步对象少，冲突概率低，同时冲突可以被简单的“last writer wins”规则解决的应用，多master的state传输策略是一个很好的选择。多master的操作传输，解决了state传输的不足，但需要付出算法复杂性以及空间开销增加的代价。

10.2 算法总结

表5总结了用于解决乐观复制所面临挑战的算法，这些挑战在section1.3中进行了说明。灰色的单元表示该方法与本文不是密切相关，或者不是一个问题。比如，对于单master中的调度和冲突管理可以通过本地并发控制解决，在状态传输系统中tombstones的空间开销则远小于操作传输系统日志所需的空间开销。

10.3乐观复制系统的总结

表6总结了综述中提到的乐观复制系统，以及它们所采用的算法。

10.4 对设计乐观复制系统的建议

通过对我们自己经验的总结以及对前面提到论文的总结，我们这里为设计乐观复制系统的朋友给出一些建议。

乐观，异步的数据处理确实可以提高网络灵活性和扩展性。因此，在低速和不可靠网络上贡献数据，或者在广域网上协同工作，同时存在计算节点连接会断开的情况下，我们不可避免地会采用乐观，异步的数据处理。然后，使用乐观复制确实需要付出一定的代价。为了保证一致性，它包含了最复杂的算法。冲突通常需要应用相关的语义信息来解决，丢失更新的问题无可避免。为此我们给出了一些建议。

1）尽量保持简单。悲观符合，采用大量现成解决方案，对于工作在完全连接并且网络可靠环境中的应用是最好的解决方案。另外，尝试单master复制，它简单，无冲突，并在实际中能扩展良好。Thomas`s写规则对于很多应用有良好的表现。对于版本向量，操作传输等高级技术，只有当你确实需要灵活性以及利用语义信息来解决冲突时再采用。

2）保持对象独立避免负面效应。绝大多数乐观复制算法能够保证一个对象在不同副本的一致性，但很难保证多个对象的一致性。

（思考：这一点也是我认为最大的问题，因为复制的数据对象间并不总是独立的。Order data与unorder data。对于这一点普遍采用state-transfer与operation-transfer相结合的方法解决。对象间关系的维护采用operation-transfer，而具体对象的同步则采用state-transfer。）

3）快速传播更新是避免冲突最好的方法。当节点相互连接时，经常的传播更新，保持节点尽量在一个接近的同步状态。这将最小化节点断开发生后的不一致。

4）尽可能地将对象设计为无冲突的。下面给出了关于这一点的一些建议：

--将大对象划分为小对象避免false positives.

--将操作设计为可交换的。例如，利用单调的数据结构，如只允许追加的日志，或者一个线性增加的计数器，或者一个全局唯一集合。

5）使用简单，结构化的拓扑，比如采用星型或者两层拓扑。相比P2P网络，它们较容易控制和扩展。

附件A.1 Happens-before 关系

对于存在全局时间的系统，请求的先后顺序可以根据请求发生的绝对时间很容易获得。然而对于分布式系统获取系统的全局时间是困难的，为系统中每一个操作确定先后顺序也是异常困难的。分布式系统分为同步系统和异步系统。Lamport在他的论文^[72]中已经阐明，尽管时钟同步是可能的，但它不是绝对必要的。如果两个进程不进行交互，那么它们的时钟也无需同步，这是因为即使没有同步也觉察不出来，并且也不会产生问题。Lamport进一步指出，通常，重要的不是所有的进程在时间上完全一致，而是它们在事件的发生顺序上要达成一致。在异步系统中我们将发送消息和接收消息也视为事件。Lamport定义了一个“先发生”(Happens-before)关系来表达事件间的先后顺序^[50,72]。

表达式a->b读作“a在b之前发生”，意思是所有进程一致认为事件a先发送，然后事件b才发生。这种先发生关系有两种情况：

(1)如果a和b是同一进程中的两个事件，且a在b之前发生，则a->b为真。

(2)如果a是一个进程发送消息的事件，而b为另一个进程接收这个消息的事件，则a->b也为真。消息不可能在发送之前就被接收，也不能在发送的同时被接收，这是因为消息需要一定时间才能到达接收端。

先发生关系是一个传递关系，所以若a->b且 b->c，则a->c。如果事件x和y发生在两个互不交换消息的进程中（也不通过第三方间接交换消息），那么x->y不真，y->x也同样不真。这两个事件称为并发，这意味着无法描述这两个事件什么时候发生，哪一个先发生。

附件B-Version vectors算法介绍和不足

Version vectors算法在分布式操作系统LOCUS中提出【Pope et al.1981】，用于检查分布式系统中，在网络中断期间对数据进行的并发修改是否存在冲突。下面对Version vectors算法进行说明，然后再论述该算法的不足。

Version vectors算法介绍

每一个副本节点对于文件f保存一个版本向量version vectors，（包含多个版本元素的向量）。Version vectors用来记录不同节点对于该文件的修改。向量含有N个元素，N为拥有该文件的节点数。向量中每一个元素，比如( Si : vi )表示，节点Si上对文件f进行了共vi次修改。通过比较不同节点保存的version vectors向量可以发现节点间的更新冲突。

先介绍一个概念，向量间的包含关系。对于同一个文件f的两个不同向量V和V’，即两个不同节点各自保存的向量。如果向量V中的每一个元素vi >= vi’，那么就称向量V包含向量V’，V’包含于V。

根据这个关系，可以定义节点更新间的冲突。对于同一个文件f的两个向量V和V’, 如果向量V不包含V’，同时V’也不包含V,则视为节点更新冲突。比如对于文件f，节点A上的向量V=<A:3,B:1,C:2>，节点B上的向量V’=<A:2,B:4,C:2>。

因为3>2, 1<4, 2=2 所以V不包含V’；同时，2<3, 4>1, 2=2，V’也不包含V，故在节点A和节点B上进行的修改是冲突的。

假设文件f，在状态<A:2,B:1,C:2>时，节点A和B是一致的。因网络中断，用户在A上进行了一次修改，在B上对文件进行了2次修改，这样就形成前面提到的两个向量。利用Version Vectors算法可以准确的识别出在A，B上进行的修改是冲突的。

Version vectors算法不足

a.仅对单个文件的并发修改有效，对于多个对象的修改无法识别。

对于单一文件系统，当一个文件被编辑时，如果对其目录进行重命名、删除等操作，是不允许的。必须在文件保存后，才能对目录进行重命名或删除操作。但对于分布式系统，用户可以在两个节点上分别进行目录重命名和文件编辑操作。利用Version vectors算法是无法识别这样的并发修改。

因为Version Vectors是针对每个文件进行信息的保存。上面的情况，目录重命名会影响到多个文件，但修改的仅是该目录的Version Vector向量。当两个节点交换更新时就无法识别冲突。当然我们可以修改对Version Vector向量的更新过程，比如当对目录进行操作时，递归的更新其所含文件、子目录的Version Vectors。这意味着需要将不同应用的语义信息移入答Version Vectors算法的更新过程中。

Version Vectors对于单个文件，简单并发更新可以识别。对于多个对象，且对象间存在一定语义约束的情况，Version Vectors算法无法适用。

b.持有文件副本的节点不能灵活扩展

Version vectors从一开始就规定了该文件持有的副本数。当需要有更多的节点持有该副本时，需要辅助的算法进行。在Dynamo系统中也采用了Version Vectors算法。假设Dynamo中对于每个文件默认提供三个副本，那么就会有三台电脑同时持有该文件。如果对文件的请求增多，需要增加该文件的副本来满足更多的请求。这时就需要扩展已持有该文件副本节点的Version vector向量，让向量支持更多的元素，从而支持新的节点加入。在节点频繁伸缩情况下，Version vector的开销就很大。

附件C-一致性模型

对一致性模型的描述主要从三个出发点进行考虑：

(1)响应前还是响应后，即在完成对所有副本数据集的同步前返回用户，还是完成同步后再给用户反馈。

(2)进行同步对象的多少，是对每次更新进行同步还是在多次更新后再同步。

(3)对更新顺序的维护，维护更新操作间不同的顺序会提供不同的一致性，当完全不考虑更新顺序，甚至更新的类型时，只提供最终数据的相互一致，则是最终一致性。

1.相互一致性

文献^[70]对一致性的定义为，设定在数据上的约束。这种约束在不同应用中是不同的。违反这样的约束就称违反了数据的一致性。对于分布式中，复制技术最重要的约束就是副本节点数据的相互一致。请求对一个副本上的数据进行了修改，如果系统没有及时的将更新传播并应用到其它节点，路由到其它节点的请求就会获取到不一致的数据内容。维护节点间的相互一致性就称为了复制系统的关键。同时一致性模型也是数据同步的重要模型。

Yu和Vahdat 2002^[13]为定义副本间的不一致性判断设计了三个相互独立的坐标轴：副本之间的数值偏差、副本之间新旧程度的偏差以及更新操作顺序的偏差。数据具有数值语义的应用程序可以按数值偏差来度量不一致性。例如，股票市场价格记录的复制。在这种应用中，应用程序可能会指定两个副本的偏差不能超过0.02美元，这就是绝对数值偏差。也可以指定相对数值偏差，表示两个副本之间的差别不能超过多少（0.5%）新旧偏差与副本最近一次更新有关。多某些应用程序来说，只要副本提供的旧数据不是太旧，它是可以容忍的。例如，天气预报通常要滞后一段时间（如几个小时）。在这种情况下，主服务器会定期地接收更新消息，但在一段时间内只给副本传送一次更新信息。在有些应用程序中，只要可以界定副本之间的差异，就允许不同的副本采用不同的更新顺序。

下面我们来谈一谈不同的一致性约束。不同的一致性约束是系统对外提供服务的不同特性，开发人员在使用一个存储系统前，最先应当了解该系统提供的一致性约束。

我们这里对于一致性约束的描述是以客户端-服务器为模型^[52,73]。站在客户端的角度来分析客户端自己所做的更新在不同一致性约束下的不同表现结果。为了后续描述的简单，我们这里做一些约定。C表示客户端，C1,C2,C3个客户端。S表示服务器，S1和S2两个服务器。数据对象的编址为1,2,3,4，即有四个数据对象。对数据的读操作为read(i)括号内i为数据的编址。对数据的写操作为write(i,n)，i为数据的编址，n为写入的数值。为了描述单调写一致性，支持write(i,++)操作，即对编址为i的数据进行自动加1操作。所有编址内数据的初始值为0。

2.强一致性

强一致性为：任意一个客户端做的更新，其它客户端在后续的访问中都能获得

我们从最简单的一致性模型开始，然后一步步增加问题的复杂性。最简单的一致性模型应该就是只有单一服务器，多客户端模型，如上图所示。垂直线表示真实时间。含有箭头的线段表示从一台电脑发送给另一台电脑的消息，线段的倾斜角度表示网络延迟，倾斜角度大，说明该消息从发送节点到达接收节点经过的时间长，故网络延迟大。上图我们忽略掉服务器S1执行操作的时间。C2的read(1)请求在C1的write(1,5)之后进行，所以将获得最新的更新内容（1,5）。同理C1的read(2)在C2的write(2,7)之后进行，将获得最新的更新内容（2,7）。

增加一台服务器，同时每个数据对象存在两个副本，分别放置在两台服务器上。由于更新需要应用在多个副本上，所以更新的执行时间就不能被忽略。从图中我们可以看到，C2多次请求数据对象1的内容。当read（1）请求在副本节点执行同步前进行，会返回（1，0）。当服务器正在执行同步时收到请求，则将不返回内容给C2,或者可以返回提示信息表示数据正在同步。当服务器完成同步后，C2的read(1)请求会得到最新的更新值（1,5）。

在多副本的系统中，系统为了保证对外提供数据的强一致性，必然会在系统的可用性上做出一定的牺牲。上图中，对于数据对象1系统在各个服务进行同步的过程中，数据对象1对外不提供服务。

3.弱一致性

为了提高系统的可用性，在许多应用中会放松对一致性的需求。下面先来看一个例子，从而说明什么是弱一致性。然后将说明不同约束下的弱一致性。

上图中，完成多副本间的同步也需要一定的时间，但在这个时间内，系统对外一直提供服务。不过C2并不能在C1提交完更新后就获得最新的更新内容，C2会获得数据对象1的历史数据。我们称不同副本完成同步需要的时间为系统的不一致窗口。如上图，两条虚线间表示不一致窗口

弱一致性指，系统无法提供在更新完成后，任意节点都会立即获得最新的更新内容。

3.1 Read-your-write

C1在提交完write(1,5)更新请求后，紧接着提交了read(1)请求。Read-your-write一致性的约束，是保证C1将会看到自己所做的更新，即C1将会读取到（1,5）。

然后因为存在多个副本节点，C1首先提交的write(1,5)更新请求由S1执行，但是C1随后提交的read(1)请求不一定会在S1上执行。如上图，两条虚线表示不一致窗口。代箭头的虚线表示read(1)由S2执行，此时S2未完成对数据对象1的同步，那么C1将会访问到数据对象1的旧值（1，0），这就违反了Read-your-write约束。

3.2 Session consistency

Session一致性是read-your-write的一个特例。C1首先提交了write(1,5),随后提交了read(1)，如果这两个请求在同一个session的作用范围内，那么C1将看到自己之前提交的更新。如上图虚线方框内的连续两个请求。如果C1的写、读两个请求并不在同一个session范围内，那么系统将不能保证后面的读请求一定会获取前面写请求的更新值。这里有多种原因为造成这样的结果。比如，两个副本节点完成同步的时间大于Session的有效期，并且C1的read(1)被负载到了未完成同步的节点。如上图，代箭头的虚线就是落在session一致性约束外的请求，获取的返回值可能是（1,0）或者（1,5）。

3.3 单调读一致性Monotonic read consistency

单调一致性指，当一个客户端在read请求时获得了某一个特定的值，该客户端随后的read请求不允许获得该数据对象之前的旧值。上图，客户端C1先后执行write(1,5)和read(1)，得到(1,5)。然后C1再多次发送read(1)请求，如果后续的read(1)请求返回的结果都是(1,5)那么就称系统遵循了Monotonic read consistency。但是如上图，代箭头虚线所示，C1后续的read(1)请求的返回结果为（1，0），这就违反了Monotonic read consistency。

3.4 单调写一致性Monotonic write consistency

单调写一致性，指对于同一个客户端，它连续的写操作是基于前面写操作的结果进行。上图中，C1发起连续的两个写操作，分别是write(1,5),write(1,++)，即先将数据对象1设置为5，然后让数据对象1完成自动加1操作。正确的执行结果应该是（1,6）。

上图中在右侧（1,5）（1,0）表示，当某一副本节点执行完C1请求时，在两个副本节点上数据对象1的值。例如，当C1提交write(1,5)，S1完成操作，S2未完成同步，则此时的数据对象1在S1上为（1,5），在S2上为(1,0)。

如果C1第二个写请求write(1,++)，仍由S1执行，则C1将会看到的正确的执行结果（1,6）。但是如果请求由S2执行，C1将会看到（1,1）这样的结果，这样就违反了单调写一致性。

当然，在S1和S2完成同步后，write(1,++)由S2执行，C1仍可以看到正确的执行结果(1,6)。

3.5 因果一致性Causal consistency

前面描述的弱一致性，一直是对从一个客户端的角度分析。如果两个客户端的操作存在一定的先后顺序，该如何保证一致性。因果一致性就是对来自不同客户端，存在先后的请求提供一致性保证。

因果一致性，指如果不同客户端的请求存在先后顺序，那么多副本系统对请求的返回结果也要符合该请求间的先后顺序。

如上图，C1发送请求write(1,5)，然后C1通知C2它完成更新（点线表示该通知），这时C2发送请求read(1)。如果系统对C2的read(1)返回（1,5），则该系统遵从了因果一致性，如果系统返回(1,0)则该系统并为提供因果一致性。对于无请求先后顺序关系的客户端，如C3节点，同样请求read(1)，系统将不提供任何一致性保证，C3获得的返回值可能是（1,0）,也可能是(1,5)。

4.最终一致性

最终一致性是弱一致性的特例^[73]。弱一致性对更新操作在不同副本节点间的传播顺序，以及执行顺序进行了约束，从而实现不同的弱一致性。最终一致性对于不同副本节点间传播的更新，执行顺序没有任何约束，甚至在节点间传播的更新并不总是用户在客户端直接执行的更新操作。最终一致性，只要求如果对于数据对象不再有任何更新后，那么最终所有的访问都将获得最后更新的值。