乐观复制算法
在分布式数据共享系统中，复制是能同时提高系统可用性和性能的一项关键技术。本文讨论的乐观复制算法，为了支持并发工作，容忍低质量通信链路中的错误，它允许副本内容在短时间内出现不一致。随着基于广域网和移动网络的协作越来越流行，这项技术也越来越重要。
乐观复制算法采用的技术与传统的悲观算法有很大的不同。与悲观算法依赖于同步副本的协作不同，乐观算法在后台传播更新，在更新发生后发现冲突，逐步在对象的最终内容上达成一致。本文将会讨论乐观复制系统面临的关键问题，比如：一致性达成，保证副本内容质量，副本扩展性。并对解决这些挑战的技术进行全面讨论。
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，对分布式系统中的事件顺序进行简要描述。