在分布式协定协议中绑定CRUD型协议

通过因特网提供的服务(诸如，所谓的“云”服务)可遭受中断，这些中 断可使用户体验降级。除了使用户体验降级外，这样的中断可在业务成本(诸 如实际的金钱损失以及信誉损失)方面具有较大的组织影响。

概述

提供本概述是为了以简化的形式介绍将在以下具体实施方式中进一步描 述的概念选择。本概述并非旨在标识出所要求保护的主题的关键特征或必要特 征。

各实施例使得冗余服务或副本服务(诸如“云”服务)能够在各地理上分 布的位置处运行。每一副本都能够执行跨所有副本普遍地、相同地执行的操作。 在一个位置处中断的情况下，其他位置处的服务可快速并自动地接管各操作。

在一个或多个实施例中，利用分布式协定协议来绑定CRUD型协议以作为 状态机。绑定通过使用位于分布有该服务的每一位置处的逆向代理来发生。在 至少一些实施例中，分布式协定协议被实现为Paxos协议或其变型，和/或CRUD 型协议包括超文本传输协议(HTTP)。

附图简述

在全部附图中，使用相同的附图标记来指示相同的特征。

图1示出了根据一个或多个实施例的示例操作环境。

图2示出了根据一个或多个实施例的示例操作环境。

图3是描述根据一个或多个实施例的方法中的各步骤的流程图。

图4示出了根据一个或多个实施例的示例系统。

图5示出了根据一个或多个实施例的示例设备。

详细描述

概览

各实施例使得冗余服务或副本服务(诸如“云”服务)能够在各地理上分 布的位置处运行。每一副本都能够执行跨所有副本普遍地、相同地执行的操作。 在一个位置处中断的情况下，其他位置处的服务可快速并自动地接管各操作。

在一个或多个实施例中，利用分布式协定协议来绑定CRUD型协议绑定以 作为状态机。绑定通过使用位于分布有该服务的每一位置处的逆向代理来发 生。在至少一些实施例中，分布式协定协议被实现为Paxos协议或其变型，和/ 或CRUD型协议包括超文本传输协议(HTTP)。然而，将领会和理解，本文 档中描述的技术可结合任何合适的无状态REST(代表性状态转移)协议来采 用。如本领域技术人员将领会的，REST定义了藉此可将web服务设计成聚焦 于系统的资源的体系结构原理集合，该体系结构原理集合包括以不同语言写的 大范围的客户机如何寻址资源状态并通过HTTP传输这些资源状态。如本领域 的技术人员将领会的，REST型体系结构是结合客户机和服务器来利用的。客 户机通常发起对服务器的请求，这些服务器随后处理该请求并返回合适的响 应。请求和响应是围绕资源表示的传输而构建的。资源可包括可寻址到的任何 相干且有意义的概念。资源的表示通常是捕捉资源的当前状态或预期状态的文 档。在客户机准备好作出到新状态的转变时，该客户机通过发送请求来发起通 信。在一个或多个请求未完结时，客户机被认为在转变中。每一状态的表示可 包含下一次客户机选择发起新状态转变时可使用的链接。

在以下讨论中，首先描述可采用本文描述的技术的示例环境。随后描述可 在该示例环境以及其他环境中执行的示例过程。因此，各示例过程的执行不限 于该示例环境，并且该示例环境不限于执行各示例过程。

示例环境

图1概括地在100处示出根据一个或多个实施例的操作环境。环境100包 括本地客户端机器形式的计算设备102，该计算设备102具有一个或多个处理 器104、一个或多个计算机可读存储介质106和驻留在计算机可读存储介质上 并可由处理器104执行的一个或多个应用108。计算设备102还包括web浏览 器110和如以下所描述的那样操作的操作系统111。

计算设备102可被具体化为任何合适的计算设备，诸如作为示例而非限制， 台式计算机、便携式计算机、手持式计算机(诸如个人数字助理(PDA)、移 动电话)、电视机、平板计算机等等。计算设备102的各个不同示例之一在以 下图4和5中示出并描述。

应用108可包括任何合适类型的应用。Web浏览器110被配置成经由网络 112导航。虽然网络112被示为因特网，但是该网络可以采用各种各样的配置。 例如，网络112可以包括广域网(WAN)、局域网(LAN)、无线网络、公共 电话网和内联网等等。此外，虽然只示出了单一网络112，但是，网络112可 以被配置成包括多个网络。

浏览器可被配置成经由网络112导航以与可从一个或多个服务器114(诸 如web服务器)获得的内容交互以及将数据传送给一个或多个服务器114，例 如执行下载和上传。服务器114可被配置成提供一个或多个服务，诸如可经由 网络112访问并可由计算设备102消耗的web服务(也被称为“云服务”)。 这样的服务的示例包括地图服务、电子邮件、网页、照片共享站点、社交网络、 内容共享服务、媒体流式传输服务、数据检索和/或显示服务等等。

应用108中的一个或多个还可被配置成访问网络112，例如它们直接访问 网络和/或通过浏览器访问网络。例如，应用108中的一个或多个可被配置成传 递消息(诸如电子邮件、即时消息等)。在更多示例中，例如应用108可被配 置成访问社交网络、获得天气更新、与由web服务器114中的一个或多个实现 的书店服务交互、支持文字处理、提供电子表格功能、支持演示的创建和输出 等等。

因此，应用108还可被配置用于可涉及直接或间接网络112访问的各种功 能。例如，应用108可包括可由应用108本地地使用并且与在另一计算设备上 执行的应用同步的配置设置和其它数据。以此方式，这些设置可被这些设备共 享。也可构想各种其他实例。因此，计算设备102可按各种方式与来自各个不 同源的内容交互。

在所示和所描述的实施例中，服务器114各自可支持作为冗余web服务的 web服务。即，每一冗余web服务都是其他web服务的复制或副本。这些web 服务可能并且通常在地理上分布的位置处运行或执行。每一副本服务都能够执 行跨所有副本普遍地、相同地执行的操作。在一个位置处中断的情况下，其他 位置处的服务可快速并自动地接管各操作。

在一个或多个实施例中，利用分布式协定协议来绑定CRUD型协议绑定以 作为状态机。绑定通过对位于分布有该服务的每一位置处的逆向代理的使用来 发生。在至少一些实施例中，分布式协定协议被实现为Paxos协议或其变型， 和/或CRUD型协议包括HTTP协议，如以下将变得更明显的。

一般而言，此处描述的任何功能可使用软件、固件、硬件(例如，固定逻 辑电路)、或这些实现的组合来实现。本文使用的术语“模块”、“功能”和 “逻辑”一般表示软件、固件、硬件或其组合。在软件实现的情况下，模块、 功能或逻辑表示当在处理器(例如，一个或多个CPU)上执行时执行指定任务 的程序代码。程序代码可被储存在一个或多个计算机可读存储器设备中。下面 所描述的技术的特征是平台无关的，意味着所述技术可以在具有各种处理器的 各种商用计算平台上实现。

例如，计算设备102还可包括使得计算设备102的硬件或虚拟机(例如处 理器、功能块等等)执行各操作的实体(例如软件)。例如，计算设备102可 包括计算机可读介质，该计算机可读介质被配置成维护使得计算设备尤其是计 算设备102的操作系统和相关联的硬件执行各操作的指令。因此，这些指令用 于配置操作系统和相关联的硬件来执行这些操作，并以此方式致使操作系统和 相关联的硬件变换以执行各功能。这些指令可由计算机可读介质通过各种不同 配置提供给计算设备102。

一种这样的计算机可读介质配置是信号承载介质，并因此被配置来诸如经 由网络将这些指令(例如，作为载波)传送到计算设备。计算机可读介质还可 被配置为计算机可读存储介质，因此不是信号承载介质。计算机可读存储介质 的示例包括：随机存取存储器(RAM)、只读存储器(ROM)、光盘、闪存、 硬盘存储器，和可使用磁、光以及用于存储指令和其他数据的其他技术的其他 存储设备。

在描述了示例环境后，现在考虑对分布式协定协议(DAP)的讨论以及这 样的DAP可如何与CRUD型协议(诸如，HTTP协议)一起利用以绑定CRUD 型协议以作为状态机。

分布式协定协议

随着信息系统由于如从分布式系统的本质暗示的可缩放性、自主性和容错 性等益处而日益被转换成分布式架构，在这样的分布式系统内维护组织和同步 的挑战变得越来越具挑战性。分布式系统的一个目标是使得用作对等体的每一 处理器或节点高效并灵活地就满足特定协定条件的一个共同值达成协定。

可利用分布式协定协议，以便使得分布式系统内的各节点能够以高效的方 式就这样的共同值达成协定。一个这样的分布式协定协议是以下描述的Paxos 协议。Paxos协议可被利用在本文档中描述的各个实施例中。然而，将领会和 理解，可以利用其它分布式协定协议而不背离所要求保护的主题的精神和范 围。例如，一个这样的分布式协定协议是查询/更新(Q/U)协议，如本领域的 技术人员将领会的。

Paxos协议

以下讨论描述了Paxos协议，该Paxos协议一般仅作为可被利用来绑定 CRUD型协议(例如HTTP)以作为Paxos协议内的状态机的分布式协定协议 的一个示例。

Paxos协议用于实现容错式分布式系统。随后的讨论将应用所获得的Paxos 算法或协议解释为与用于构建分布式系统的状态机方法一致。首先考虑问题的 上下文中的一致性算法。假设可提议值的过程的集合。一致性算法确保所提议 值之间的单个值被选择。如果没有值被提议，则没有值应被选择。如果选择了 值，则各过程应当能够获悉所选择的值。针对一致性的安全性考虑是：(1) 仅已提议的值可被选择，(2)仅单个值被选择，以及(3)除非值实际上已被 选择，否则过程永远不会获悉该值已被选择。目标是确保所提议的一些值最后 被选择，并且如果值已被选择，则过程最后可获悉该值。

一致性算法中的三个角色由以下三个代理类来执行：提议器、接受器和获 悉器。在一实现中，单个过程可充当一个以上的代理。还假设各代理可通过发 送消息彼此通信。在该讨论的上下文中，利用定制的异步、非拜占庭模型，其 中(1)各代理以任意速度操作，可由于停止而失效，并可重启；由于所有代 理都可在值被选择后失效并可随后重启，因此除非已经失效并重启的代理可想 起一些信息，否则解决方案是不可能；以及(2)消息可花费任意长的时间来 递送，可被复制，并且可被丢失，但这些消息不会被破坏。

现在考虑选择值的概念。选择值的最容易的方式是具有单个接受器代理。 提议器向接受器发送提议，接受器选择它接收到的第一个所提议的值。虽然简 单，但该解决方案并不令人满意，因为接受器的失效使得任何进一步进展变得 不可能。取代单个接受器，可使用多个接受器代理。提议器向接受器集合发送 所提议的值。接受器可接受所提议的值。当足够大的接受器集合接受值时，该 值被选择。多大为足够大呢？为了确保仅单个值被选择，可令足够大的集合由 这些代理中的任何多数代理组成。由于任何两个多数代理具有至少一个共有的 接受器，因此这在接受器可接受最多一个值的情况下起作用。在没有失效或消 息丢失的情况下，希望即使在仅一个值被单个提议器提议的情况下仍选择值。 这提出以下要求：

P1.接受器必须接受它接收的第一提议。

然而，这要求提出了问题。若干值可由不同的提议器在大约相同的时间提 议，从而导致其中每一个接受器接受了一个值但是没有单个值被这些接受器中 的大多数接受的情况。即使仅具有两个所提议的值，如果每一值被大约一半这 些接受器接受，则单个接受器的失效可使得无法获悉这两个值中的哪个值被选 择。

P1和值仅在它被大多数接受器接受时才被选择的要求暗示必须允许接受 器接受一个以上提议。为了允许这个，通过以下方式来跟踪接受器可接受的不 同提议：向每一提议分配(自然)编号，使得提议由所提议的编号和值组成。 为了防止混淆，要求不同的提议具有不同的编号。这如何达成取决于该实现， 使得出于讨论的目的现在仅对其作出假定。值在具有该值的单个提议已被这些 接受器中的大多数接受时被选择。在那个情况下，表示该提议(以及其值)已 被选择。

可允许多个提议被选择，但必须保证所有所选择的提议具有相同的值。通 过对提议编号的归纳，它足以保证：

P2.如果选择了具有值v的提议，则所选的每一个带更高编号的提议均具有 值v。

由于各编号全部被排序，因此条件P2保证了仅单个值被选择的安全属性。

为了被选择，提议必须被至少一个接受器接受。因此，可通过满足以下来 满足P2：P2^a。

如果选择了具有值v的提议，则任何接受器所接受的每一个带更高编号的 提议均具有值v。

仍维护P1以确保某个提议被选择。由于通信是异步的，因此提议可在某 个特定接受器c从未接收到任何提议的情况下被选择。假设一新提议器“苏醒”， 并且发出具有不同值的带更高编号的提议。P1要求c接受该提议，而违反P2^a。 维护P1和P2^a两者要求将P2^a加强为：P2^b。

如果选择了具有值v的提议，则任何提议器所发出的每一个带更高编号的 提议均具有值v。

由于提议必定由提议器在该提议可被接受器接受之前发出，因此P2^b暗示 了P2_a，P2_a进而暗示了P2。

为了发现如何满足P2^b，考虑将如何证明它有效。将假定具有编号m和值 v的某个提议被选择，并示出所发出的具有编号n>m的任何提议也具有值v。 通过以下将使得该证明更容易：使用对n的归纳，使得在所发出的具有m...(n-1) 中的编号的每一提议具有值v的附加假定下，可以证明提议编号n具有值v， 其中i..j表示从i到j的编号的集合。在带编号m的提议被选择的情况下，必 定存在由大多数接受器组成的某一集合C，使得C中的每一接受器均接受该提 议。将此与归纳假定组合，m被选择的假设暗示：

C中的每一接受器已接受了具有m..(n-1)中的编号的提议，并且被任何接 受器接受的具有m..(n-1)中的编号的每一提议均具有值v。

由于由大多数接受器组成的任何集合S均包含C的至少一个成员，通过确 保以下不变量被维护可推断出带编号n的提议具有值v：P2^c。

对于任何v和n，如果具有值v和编号n的提议被发出，则存在由大多数 接受器组成的集合S，使得要么(a)S中的接受器都不接受带小于n的编号的 任何提议，要么(b)v是被S中的接受器接受的带小于n的编号的所有提议中 带最高编号的提议的值。

可因此通过维护不变量P2^c来满足P2^b。

为了维护不变量P2^c，想要发出带编号n的提议的提议器必须获悉已被或 者将被一些大多数接受器中的每一接受器接受的、具有小于n的编号的带最高 编号的提议(如果存在任何的话)。获悉已经被接受的提议足够容易；从而预 测将来的接受是困难的。取代尝试预测将来，提议器通过提取将不存在任何这 样接受的承诺来对其进行控制。换言之，提议器请求接受器不再接受带小于n 的编号的提议。这导致用于发出提议的以下算法。

1.提议器选择新提议编号n，并向某一接受器集合中的每一成员发送请求， 以请求它用以下来作出响应：

(a)永远都不会再接受带少于n的编号的提议的承诺，以及

(b)它已经接受的、具有小于n的最高编号的提议(如果有的话)。

这样的请求被称为具有编号n的“准备请求”。

2.如果提议器从大多数接受器中接收了所请求的响应，则该提议器可发出 具有编号n和值v的提议，其中v是这些响应中带最高编号的提议的值，或者 在响应器没有报告提议的情况下是提议器所选择的任何值。

提议器通过向某一接受器集合发送提议被接受的请求来发出该提议。(该 接受器集合不需要是对初始请求作出响应的相同的接受器集合。)该请求将被 称为接受请求。

接受器可从提议器接收两种类型的请求：准备请求和接受请求。接受器可 忽略任何请求，而不危及安全。因此，需要声明这仅在接受器被允许对请求作 出响应时才行。它可能总对准备请求作出响应。它可对接受请求作出响应，从 而接受该提议(仅在它尚未承诺不接受提议的情况下)。换言之：

P1^a.仅在接受器尚未对具有大于n的编号的准备请求作出响应的情况下， 该接受器可接受带编号n的提议。

观察到P1^a包含P1。现在具有用于选择满足所要求的安全属性(假设唯 一的提议编号)的值的完整算法。最后的算法通过作出一个小优化来获得。假 设接受器接收了带编号n的准备请求，但它已经对带大于n的编号的准备请求 作出了响应，由此承诺不接受任何新的带编号n的提议。因此不存在接受器对 新的准备请求作出响应的任何理由，因为它将不会接受该提议器想要发出的带 编号n的提议。因此使该接受器忽略这样的准备请求。还使该接受器忽略针对 该接受器已经接受的提议的准备请求。

通过该优化，接受器仅需要记住该接受器曾经接受过的带最高编号的提 议，以及该接受器已作出过响应的带最高编号的准备请求的编号。由于P2^c必 须保持不变而不管失效，因此接受器必须记住该信息，即使它失效并随后重启。 注意提议器可能总是放弃提议并完全忘记它——只要该提议器永远不尝试发出 具有相同编号的另一提议。

将提议器和接受器的动作放在一起，可明白该算法在以下两个阶段中操 作。

阶段1

(a)提议器选择提议编号n，并将具有编号n的准备请求发送给大多数接 受器。

(b)如果接受器接收到具有比该接受器已经作出响应的任何准备请求的 编号更大的编号n的准备请求，则该接受器用不再接受任何带少于n的编号的 提议的承诺以及该接受器已经接受的带最高编号的提议(如果有的话)对该请 求作出响应。

阶段2

(a)如果提议器从大多数接受器接收到对其准备请求(带编号n)的响应， 则该提议器向这些接受器中的每一个发送对具有值v的带编号n的提议的接受 请求，其中v是这些响应中带最高编号的提议的值，或者在这些响应没有报告 提议的情况下是任何值。

(b)如果接受器接收到了对带编号n的提议的接受请求，则该接受器接 受该提议，除非该接受器已经对具有大于n的编号的准备请求作出了响应。

提议器可作出多个提议，只要该提议器遵循每一个提议的算法。它可在任 何时间放弃处于协议中间的提议。即使对提议的请求和/或响应在该提议被放弃 了很长时间之后才可到达其目的地，正确性仍被维护。如果某一提议器已开始 尝试发出带更高编号的提议，则放弃提议可能是个好注意。因此，如果接受器 忽略了准备请求或接受请求，因为该接受器已经接收到了具有更高编号的准备 请求，则该接受器应可能通知提议器，该提议器随后应放弃其提议。这是不影 响正确性的性能优化。

现在考虑获悉所选择的值的概念。为了获悉值已被选择，则获悉器查明提 议已被大多数接受器接受。实现这个的一种方式是使得每一接受器在无论何时 它接受了一提议时都对所有获悉器作出响应，从而向它们发送该提议。这允许 获悉器一有可能就查明关于所选的值的情况，但这要求每一接受器对每一获悉 器都作出响应——响应的数目等于接受器的数目和获悉器的数目的积。

非拜占庭失效的假定使得一个获悉器可容易地从另一获悉器查明值已被 接受。可使各接受器通过其接受来对区别获悉器作出响应，该区别获悉器转而 向其他获悉器通知已在何时选择了值。该方法要求额外的循环以供所有这些获 悉器发现所选的值。它也较不可靠，因为区别获悉器可能失效。但它要求响应 的数目仅等于接受器的数目和获悉器的数目的和。

更一般地，接受器可用其接受对区别获悉器的某一集合作出响应，这些区 别获悉器中的每一个向所有这些获悉器通知何时选择了值。使用越大的区别获 悉器集合会以越大的通信复杂性为代价提供越大的可靠性。

由于消息丢失，可选择获悉器都不曾查明的值。获悉器可询问接受器它们 已接受了什么提议，但接受器的失效可使得它不可能知道是否大多数都接受了 特定提议。在那个情况下，各获悉器将仅在选择了新提议时查明会选择什么值。 如果获悉器需要知道是否选择了值，它可使用以上描述的算法使提议器发出提 议。

现考虑进展的问题以及如何保证算法的进展以多产的方式继续。考虑其中 两个提议器各自保持以增加的编号(这些编号中没有一个编号曾被选择)发出 提议序列的场景。提议器p对提议编号n₁完成阶段1。另一提议器q随后对提 议编号n₂>n₁完成阶段1。针对带编号n₁的提议的提议器p的阶段2接受请求 被忽略，因为这些接受器全部都已承诺不接受带小于n₂的编号的任何新提议。 因此，提议器p随后开始并完成针对新提议编号n₃>n₂的阶段1，从而导致提议 器q的第二阶段2接受请求将被忽略，并以此类推。

为了保证进展，区别提议器被选作尝试发出提议的唯一提议器。如果该区 别提议器可成功地与大多数接受器进行通信，并且如果它使用具有大于任何已 使用的编号的提议，则它将成功发出被接受的提议。通过在它获悉具有较高提 议编号的某请求的情况下放弃提议并再次尝试，区别提议器将最终选择足够高 的提议编号。

如果该系统的足够部分(提议器、接受器和通信网络)合适地工作，则活 跃度可因此通过选取单个区别提议器来实现。用于选取提议器的可靠算法可随 机使用或例如通过使用超时来实时使用。然而，

安全被确保，而不管该选取是成功还是失败。

现在考虑一些实现问题。Paxos算法假定过程网络。在其一致性算法中， 每一过程扮演提议器、接受器和获悉器的角色。该算法选择领导者，该领导者 扮演区别提议器和区别获悉器的角色。Paxos一致性算法是以上描述的算法， 其中各请求和响应被作为普通消息来发送。响应消息标有相应的提议编号以防 止混淆。在失效期间保存的稳定存储被用于维护接受器将记住的信息。接受器 在实际上发送响应之前将其预期响应记录在稳定存储中。

剩下的所有部分将描述用于保证不曾发出具有相同编号的两个提议的机 制。不同的提议器从不相交的编号集合中选择其编号，使得两个不同的提议器 永远都不会发出具有相同编号的提议。每一提议器在稳定存储中记录它尝试发 出过的带最高编号的提议，并用比它已经使用过的任何编号高的提议编号开始 阶段1。

现在对照Paxos算法的背景考虑状态机的实现。

实现分布式系统的一种方式是作为向中央服务器发出命令的客户机集合。 该服务器可被描述成以某一顺序执行客户机命令的确定性状态机。状态机具有 当前状态；它通过将命令取作输入并产生输出和新状态来执行步骤。例如，分 布式银行系统的客户机可以是提款机，并且该状态机状态可由所有用户的账户 余额组成。取款将通过以下方式来执行：仅在账户余额大于提取的量的情况下， 执行减少该余额的状态机命令，从而产生原来的余额和新的余额作为输出。使 用单个中央服务器的实现在该服务器失效的情况下失效。

因此改为使用服务器集合，每一服务器独立地实现状态机。由于状态机是 确定性的，因此所有服务器都将产生相同的状态序列和输出，如果它们全部执 行相同的命令序列的话。发出命令的客户机随后可使用任何服务器针对其生成 的输出。

为了保证所有服务器都执行相同的状态机命令序列，实现Paxos一致性算 法的各单独实例的序列，由第i个实例选择的值是该序列中的第i个状态机命 令。每一服务器在该算法的每一实例中扮演全部角色(提议器、接受器和获悉 器)。出于该示例的目的，假定该服务器集合是固定的，使得一致性算法的所 有实例使用相同的代理集合。

在常规操作时，单个服务器被选作领导者，其在一致性算法的所有实例中 都充当区别提议器(即，尝试发出提议的唯一提议器)。客户机向领导者发送 命令，该领导者判定在该序列中每一命令应出现在哪里。如果领导者判定某一 客户机命令应该是第135条命令，则它尝试使得那个命令被选作该一致性算法 的第135个实例的值。它通常都将成功。它可能因为失效，或者因为另一服务 器相信它自己也是领导者并且对第135条命令应当是什么具有不同的主意，而 失败。但是该一致性算法确保至多一条命令可被选为第135条命令。

在Paxos一致性算法中，这个方法的效率被增强了，因为要提议的值直到 阶段2才会被选择。回想在完成了提议器的算法的阶段1后，要么要提议的值 被确定，要么提议器自由地提议任何值。

现考虑Paxos状态机实现在常规操作期间如何工作。考虑在先前领导者刚 刚失效且新领导者已被选择时会发生什么。新领导者(在该一致性算法的所有 实例中都是获悉器)应该知道已经被选择的大多数命令。假设该新领导者知道 命令1-134、138和139——即在该一致性算法的实例1-134、138和139中所 选择的值。该新领导者随后执行实例135-137以及大于139的所有实例的阶段 1。假设这些执行的结果确定实例135和140中要提议的值，但使得所提议的 值在所有其他实例中不受约束。该领导者随后针对实例135和140执行阶段2， 由此选择命令135和140。

领导者以及获悉该领导者所知道的所有命令的任何其他服务器现在可执 行命令1-135。然而，该领导者无法执行它也知道的命令138-140，因为命令136 和137尚未被选择。该领导者可取客户机所请求的下两条命令来作为命令136 和137。相反，令它通过提议使得状态保持不变的特殊“noop(空操作)”命 令作为命令136和137来立即填充间隙。它通过执行一致性算法的实例136和 137的阶段2来实现这个。一旦选择了这些“noop”命令，就可执行命令138-140。

命令1-140现在已被选择。领导者也完成了大于该一致性算法的140的所 有实例的阶段1，并且该领导者在那些实例的阶段2中自由地提议任何值。领 导者将命令编号141分配给客户机所请求的下一命令，从而在该一致性算法的 实例141的阶段2中提议该下一命令作为值。领导者提议它所接收的下一客户 机命令作为命令142，并以此类推。

领导者可在它获悉它所提议的命令141已被选择之前提议命令142。领导 者在提议命令141时发送的所有这些消息都被丢失，并且命令142在任何其他 服务器已获悉领导者提议了什么作为命令141之前被选择是可能的。

当领导者没能接收到对其在实例141中的阶段2消息的预期响应时，该领 导者将重新传输那些消息。如果一切顺利，其所提议的命令将被选择。然而， 它可能先失效，从而在所选命令序列中留下间隙。一般来说，假设领导者可提 前获得α条命令——即，在命令1到i被选择后，它可提议命令i+1到i+α。 随后可引起最多α-1条命令的间隙。

新选择的领导者为一致性算法的无限多实例(在以上场景中，为实例 135-137以及大于139的所有实例)执行阶段1。通过对所有实例使用相同的提 议编号，它可通过向其他服务器发送单个相当短的消息来实现这个。在阶段1， 接受器仅在它已经从某一提议器接收到了阶段2消息的情况下才用不止简单 OK的消息来作出响应。在该场景中，仅实例135和140是这种情况。因此， 服务器(充当接受器)可用单个相当短的消息来对所有实例作出响应。执行阶 段1的这些无限多实例因此没有提出问题。

由于领导者的失效以及对新领导者的选取应当是不常发生的事件，因此执 行状态机命令(即实现关于命令/值的一致性)的效率成本是仅执行一致性算法 的阶段2的成本。可示出，Paxos一致性算法的阶段2在用于在出现错误时达 成协定的任何算法中具有最少的可能成本。因此，Paxos算法在本质上是最优 的。

对该系统的常规操作的讨论假定除了在当前领导者的失效以及新领导者 的选取之间的短暂时段以外，总存在单个领导者。在异常环境中，领导者选取 可失败。如果没有服务器充当领导者，则将不提议新命令。如果多个服务器认 为它们是领导者，则它们可在该一致性算法的同一实例中全部都提议值，这可 防止任何值被选择。然而，安全性得到了保持——两个不同的服务器永远都不 会不同意被选为第i个状态机命令的值。对单个领导者的选取仅被需要来确保 进展。

如果服务器集合可改变，则必须存在确定什么服务器实现一致性算法的什 么实例的某种方式。实现这个的最简单的方式是通过状态机本身。服务器的当 前集合可变成该状态的一部分，并可随普通状态机命令而改变。通过在执行了 第i条状态机命令后依据状态来指定执行一致性算法的实例i+α的服务器集 合可允许领导者提前获得α条命令。这准许任意复杂重配置算法的简单实现。

以上讨论构成了对可如何利用Paxos算法来实现容错分布式系统的描述。 Paxos协议包括可结合本文中描述的实施例来利用的其他家族成员或变型。这 些其他家族成员包括(作为示例而非限制)所谓的多Paxos、廉价Paxos、快速 Paxos和拜占庭Paxos。这些其他家族成员可在以下描述的各个实施例中利用。

在讨论了分布式协定协议，并给出了特定协议的示例(即，Paxos协议及 其相关的家族成员)后，现在考虑对CRUD(创建、阅读、更新、删除)协议 并且特别是超文本传输协议(HTTP)的简短讨论。

包括HTTP的CRUD协议

CRUD(创建、阅读、更新、删除)协议指的是允许创建、阅读、更新和 删除资源的协议族。CRUD协议的一个类型是超文本传输协议(HTTP)。超文 本传输协议(HTTP)是用于分布式、协作、超媒体信息系统的应用协议，并 且是用于万维网的数据通信基础。

HTTP用作客户机-服务器计算模型中的请求-响应协议。在HTTP中，web 浏览器例如充当客户机，而在托管网站的计算机上运行的应用用作服务器。客 户机将HTTP请求消息提交给服务器。存储内容或提供资源(诸如HTML文件) 或代表客户机进行执行的服务器向客户机返回响应消息。响应包含关于该请求 的完成状态信息并可在其消息主体中包含客户机所请求的任何内容。

web浏览器(或客户机)通常被称为用户代理(UA)。其他用户代理可包 括搜索提供者(已知为web爬行器)所使用的索引软件，或web浏览器的变型， 诸如呈现交互式语音用户界面的语音浏览器。

HTTP是被设计在因特网协议套件的框架内的应用层协议。该协议定义假 定用于主机到主机数据传输的可靠传输层协议。传输控制协议(TCP)是使用 中的用于这个目的的主要协议。然而，HTTP可以与诸如用户数据报协议(UDP) 的其他协议和诸如简单服务发现协议(SSDP)的方法一起使用。

HTTP资源由统一资源标识符(URI)——或者，更具体地，统一资源定 位符(URL)——使用一个或多个http URI模式来标识并被位于网络上。URI 和超文本标记语言(HTML)形成因特网上的相互链接的资源(被称为超文本 文档)的系统。

HTTP会话是网络请求-响应事务的序列。HTTP客户机通过建立到服务器 上的特定端口的传输控制协议(TCP)连接来发起请求。监听那个端口的HTTP 服务器等待客户机的请求消息。在接收到该请求后，服务器发送回状态行(诸 如HTTP/200“OK”)及其自己的消息。该消息的主体通常为所请求的资源， 但是错误消息或其他信息也可被返回。

HTTP定义指示要对所标识的资源执行的期望动作的九种方法(有时被称 为“动词”)。该资源表示什么(是预先存在的数据还是动态生成的数据)取 决于服务器的实现。通常，该资源对应于文件或驻留在服务器上的可执行指令 的输出。

讨论了HTTP协议的各方面后，现在考虑如何利用分布式协定协议来绑定 CRUD型协议作为状态机。

绑定CRUD型协议作为状态机

图2示出了根据一个或多个实施例的可利用分布式协定协议来绑定CRUD 型协议作为状态机的系统(一般在200处)。在随后的讨论中，图1实施例中 的相同的标号用于描绘相同的组件。然而，将领会和理解，本文档中描述的技 术可结合任何合适的无状态REST(代表性状态转移)协议来采用。

在这个示例中，计算设备102经由网络112与一个或多个服务器114通信。 可以利用任何合适的协议来使得计算设备102能与服务器114通信。在所示和 所描述的实施例中，可发生利用CRUD型协议的通信。在特定实施例中，CRUD 型协议包括HTTP。

在这个特定示例中，每一服务器包括逆向代理202。逆向代理实现驻留在 DAP模块204的表中的分布式协定协议(DAP)的实例。此外，每一服务器114 实现一个或多个web服务(本文中由服务206来表示)，诸如web或“云”服 务。由各个服务器实现的每一服务206构成副本或冗余服务。

在操作时，每一服务器114构成分布式系统中提供有服务206的节点。通 常，但并非总是，服务器在地理上分布在不同的地理位置处。例如，各个服务 器可包括位于跨特定国家的各数据中心或分布在整个世界的服务器。替换地， 服务器可构成单个机架中的各个刀片服务器。每一服务器通过其DAP模块204 在分布式协定协议的实例中运行。在至少一些实施例中，分布式协定协议包括 Paxos协议。

使用CRUD型协议(诸如HTTP)，计算设备102使用例如与特定协议相 关联的动词来发出操作。在HTTP上下文中，这样的动词可包括获得、放置、 投递、打补丁、删除等。客户机计算设备102可与分布式系统中的任何节点(即 服务器114)通信。随着服务器114从计算设备102处接收到操作，该服务器 114捕捉这些操作并从而利用DAP模块204来选择这些操作的排序。具体地， 使用分布式协定协议，通信在每一服务器上的各逆向代理202之间发生。通过 各服务器之间的通信，分布式协定协议被利用来达到与要执行的操作的排序的 一致性。

一旦在利用例如以上所述的Paxos协议后协定了操作次序，每一节点(即， 服务器)可以以所协定的次序来执行服务206的上下文中的操作。通过这种方 式，使用分布式协定协议绑定了CRUD型协议(在该实例中是HTTP)来作为 状态机。

实质上，随后分布式协定协议允许接收来自可能广泛分布的各个客户机的 操作。这些操作可以以任意次序到达，并可与任何服务(即，“云服务”)相关 联。通过使用分布式协定协议，服务器可以构造如多个不同的服务器之间的顺 序操作排序，该操作排序确保跨所有服务器或节点的相同顺序排序是相同的。 结果，每一节点将相对于将执行、已执行的各个操作处于相同的状态。

结合使用CRUD型协议实现的web服务来利用分布式协定协议可以在例 如分布式系统内的各个节点或服务器可能变得无法正常工作时促成操作。

作为可使用以上描述的技术来实现的web服务的示例，考虑维护各个用户 的联系人列表的web服务。在这个特定联系人列表服务中，用户可插入新联系 人、查看联系人、更新联系人和删除联系人。还假定联系人列表服务是使用服 务器(诸如以上描述的那些服务器)以分布式形式实现的。还假定用户可使用 多个不同类型的客户机设备与联系人列表服务交互。例如，用户可能想要与个 人计算机、他们的电话、web浏览器或任何类型的客户机交互联系人列表服务。

为了交互其特定联系人列表，客户机设备发出HTTP动词形式的操作。例 如，如果用户希望通过经合适配置的用户界面查看其联系人中的全部，则该用 户将促使HTTP获得操作被发出。类似地，为了更新联系人，HTTP合并(MERGE) 操作将被发出。删除联系人会通过HTTP删除操作发生，且插入新联系人会通 过投递操作的实例发生。

由于联系人列表服务是以分布式形方式在多个不同的服务器上实现的，因 此当客户机设备发出操作时，由每一服务器或更确切地说由每一服务器上的逆 向代理执行的分布式协定协议确保在每一服务器上发生操作的经协定的次序。 通过这种方式，用户的联系人列表可跨分布式系统中的各节点(即，服务器) 保持同步。

考虑了可如何使用分布式协定协议来绑定CRUE型协议以作为状态机后， 现在考虑根据一个或多个实施例的示例方法。

示例方法

图3是描述根据一个或多个实施例的方法中的各步骤的流程图。该方法可 以结合任何合适的硬件、软件、固件或其组合来实现。在至少一些实施例中， 该方法可以至少部分地由经合适配置的客户机设备和一个或多个经合适配置 的服务器来实现。结果，所示的流程图的一部分被指定为“客户机设备”以描 绘由客户机设备执行的动作。同样，该流程图的另一部分被指定为“逆向代理” 以指定可由逆向代理(诸如以上描述的那些逆向代理)执行或代表逆向代理执 行的那些动作或那些动作中的至少一些。

步骤300发出与web服务相关联的操作。任何合适的操作可结合任何合适 的web服务发出。在至少一些实施例中，该操作与CRUD型操作相关联。在特 定实施例中，该操作与HTTP操作(诸如以上描述的那些操作)相关联。步骤 302将该操作传达给具有REST特性(RESTful)的web服务器——即符合或利 用具有REST特性的协议(诸如CRUD型协议)的web服务器。在所示和所描 述的实施例中，web服务器实现web服务，并包括分布式系统中的一个或多个 其他web服务器实现web服务的冗余或副本的部分。

步骤304截取或接收给具有REST特性的web服务器的通信。如上所述， 该步骤可由经合适配置的逆向代理来执行。在所示和所描述的实施例中，逆向 代理支持或以其他方式被配置成利用分布式协定协议，诸如以上提到的那些分 布式协定协议。在特定实现中，分布式协定协议包括Paxos协议。步骤306发 起与一个或多个节点的分布式协定协议。该步骤可以用任何合适的方式来执 行。在所示和所描述的实施例中，每一节点对应于实现以上提到的冗余web服 务的另一具有REST特性的web服务器。步骤308利用分布式协定协议来达到 相对于该操作的一致性。对分布式协定协议的利用可通过支持或展示冗余web 服务的各个服务器之间的相互通信来发生。前面提供了这样的相互通信的示 例。在使用分布式协定协议达到了一致性后，步骤310执行或启用对相关联的 操作的执行。对该操作的执行按如通过具有REST特性的web服务器或者更确 切地每一web服务器所利用的逆向代理之间的一致性确定的次序发生。在执行 了该操作后，步骤312向客户机设备返回合适的响应。可以返回任何合适的响 应。在至少一些实施例中，被返回的响应以HTTP响应的形式驻留。

步骤314在客户机设备处接收该响应并以惯常的方式处理该响应。

利用以上描述的方法，可维持实现冗余web服务的多个不同服务器之间的 状态。通过结合具有REST特性的类型的协议(例如，CRUD型协议)来使用 分布式协定协议，具有REST特性的web服务器可以在锁定步骤中操作以保留 状态并保持与跨web服务器执行的各操作同步。

在考虑了各个实施例之后，现在考虑可被用于实现以上描述的实施例的示 例系统和设备。

示例系统和设备

图4示出了包括参考图1描述的计算设备102的示例系统400。示例系统 400实现了用于当在个人计算机(PC)、电视机设备和/或移动设备上运行应用 时的无缝用户体验的普遍存在的环境。服务和应用在所有三个环境中基本相似 地运行，以便当使用应用、玩视频游戏、看视频等时在从一个设备转换到下一 设备时得到共同的用户体验。

在示例系统400中，多个设备通过中央计算设备互连。中央计算设备对于 多个设备可以是本地的，或者可以位于多个设备的远程。在一个实施例中，中 央计算设备可以是通过网络、因特网或其他数据通信链路连接到多个设备的一 个或多个服务器计算机的云。在一个实施例中，该互连架构使得功能能够跨多 个设备递送以向多个设备的用户提供共同且无缝的体验。多个设备的每一个可 具有不同的物理要求和能力，且中央计算设备使用一平台来使得为设备定制且 又对所有设备共同的体验能被递送到设备。在一个实施例中，创建目标设备的 类，且使体验适应于设备的通用类。设备类可由设备的物理特征、用途类型、 或其他共同特性来定义。

在各种实现中，计算设备102可采取各种不同的配置，诸如用于计算机402、 移动设备404、和电视机406用途。这些配置中的每一个包括可具有一般不同 的构造和能力的设备，并且因而计算设备102可根据不同的设备类中的一个或 多个来配置。例如，计算设备102可被实现为计算机类402设备，该计算机设 备类包括个人计算机、台式计算机、多屏幕计算机、膝上型计算机、上网本等。 这些不同配置中的每一个可使用此处所描述的技术，如通过包括应用程序108、 Web浏览器110以及操作系统111来示出的。

计算设备102还可被实现为移动类1616设备，该移动类设备包括诸如移 动电话、便携式音乐播放器、便携式游戏设备、平板计算机、多屏幕计算机等 移动设备。计算设备102还可被实现为电视机类406设备，该电视机类设备包 括在休闲观看环境中具有或连接到一般更大的屏幕的设备。这些设备包括电视 机、机顶盒、游戏控制台等。本文所描述的技术可由计算设备102的这些各种 配置来支持，且不限于在本文描述的各具体示例。

云408包括和/或表示内容服务412的平台410。平台410抽象云408的硬 件(如，服务器)和软件资源的底层功能。内容服务412可包括可在计算机处 理在位于计算设备102远程的服务器上执行时使用的应用程序和/或数据。内容 服务412(例如，云服务或web服务)可作为因特网上和/或通过诸如蜂窝或 Wi-Fi网络之类的订户网络的服务来提供。

平台410可抽象资源和功能以将计算设备102与其他计算设备相连接。平 台410还可用于抽象资源的缩放以向经由平台412实现的内容服务412所遇到 的需求提供对应的缩放级别。因此，在互联设备的实施例中，本文描述的功能 的实现可分布在系统400上。例如，该功能可部分地在计算设备102上以及经 由抽象云408的功能的平台410来实现。

图5示出了可被实现为如以上所述的实现本文描述的各技术的各实施例的 任何类型的计算设备的示例设备500的各个组件。设备500包括允许设备数据 504(例如，接收到的数据、正被接收的数据、安排用于广播的数据、数据的 数据包等)的有线和/或无线通信的通信设备502。设备数据504或其他设备内 容可以包括设备的配置设置、存储在设备上的媒体内容、和/或与设备的用户相 关联的信息。存储在设备500上的媒体内容可以包括任何类型的音频、视频和 /或图像数据。设备500包括一个或多个数据输入506，经由数据输入可接收任 何类型的数据、媒体内容、和/或输入，诸如用户可选输入、消息、音乐、电视 媒体内容、记录的视频内容、以及从任何内容源和/或数据源接收的任何其他类 型的音频、视频和/或图像数据。

设备500还包括通信接口508，其可被实现为串行和/或并行接口、无线接 口、任何类型的网络接口、调制解调器、以及任何其他类型的通信接口中的任 一个或多个。通信接口508提供设备500和通信网络之间的连接和/或通信链路， 其他电子、计算和通信设备通过所述连接和/或通信链路来与设备500传递数 据。

设备500包括一个或多个处理器510(如，微处理器、控制器等中的任一 个)，该处理器处理各种计算机可执行指令来控制设备500的操作并实现此处 描述的技术的各实施例。作为补充或替换，设备500可被实现为具有与在512 处概括标识的处理和控制电路有关地实现的硬件、固件、或固定逻辑电路中的 任何一个或组合。虽然未示出，但是设备500可包括耦合设备内的各种组件的 系统总线或数据传输系统。系统总线可包括不同总线结构中的任一个或组合， 诸如存储器总线或存储器控制器、外围总线、通用串行总线、和/或利用各种总 线架构中的任一种的处理器或局部总线。

设备500还包括计算机可读介质514，诸如一个或多个存储器组件，存储 器组件的示例包括随机存取存储器(RAM)、非易失性存储器(例如，只读存 储器(ROM)、闪存、EPROM、EEPROM等中的任一个或多个)、以及盘存 储设备。盘存储设备可被实现为任何类型的磁性或光学存储设备，如硬盘驱动 器、可记录和/或可重写紧致盘(CD)、任何类型的数字多功能盘(DVD)等 等。设备500还可包括大容量存储介质设备516。

计算机可读介质514提供数据存储机制以存储设备数据504，以及各种设 备应用518和与设备500的各操作方面相关的任何其他类型的信息和/或数据。 例如，操作系统520可以用计算机可读介质514作为计算机应用来维护并且在 处理器510上执行。设备应用518可包括设备管理器(例如，控制应用、软件 应用、信号处理和控制模块、特定设备本机的代码、特定设备的硬件抽象层等)。 设备应用518还包括实现本文描述的各技术的各实施例的任何系统组件或模 块。在该示例中，设备应用518包括被示为软件模块和/或计算机应用的接口应 用522和输入/输出模块524。输入/输出模块524表示用于给接口提供被配置成 捕捉输入的诸如触摸屏、跟踪垫、相机、话筒等设备的软件。作为替换或补充， 接口应用522和输入/输出模块524可被实现为硬件、软件、固件、或其任何组 合。此外，输入/输出模块524可被配置成支持多个输入设备，诸如分别捕捉视 觉和音频输入的单独设备。

设备500还包括向音频系统528提供音频数据和/或向显示系统530提供视 频数据的音频和/或视频输入-输出系统526。音频系统528和/或显示系统530 可包括处理、显示、和/或以其他方式呈现音频、视频和图像数据的任何设备。 视频信号和音频信号可以通过RF(射频)链路、S-video(S-视频)链路、复 合视频链路、分量视频链路、DVI(数字视频接口)、模拟音频连接，或其它 类似的通信链路，从设备500传递到音频设备和/或显示设备。在一实施例中， 音频系统528和/或显示系统530被实现为设备500的外部组件。或者，音频系 统528和/或显示系统530被实现为示例设备500的集成组件。

结论

各实施例使得冗余服务或副本服务(诸如“云”服务)能够在地理上分布 式的各位置处运行。每一副本都能够执行跨所有副本普遍地、相同地执行的操 作。在一个位置处中断的情况下，其他位置处的服务可快速并自动地接管各操 作。

在一个或多个实施例中，利用分布式协定协议来绑定CRUD型协议作为状 态机。绑定通过对位于分布有该服务的每一位置处的逆向代理的使用而发生。 在至少一些实施例中，分布式协定协议被实现为Paxos协议或其变型，和/或 CRUD型协议包括HTTP协议。

尽管用结构特征和/或方法动作专用的语言描述了本主题，但可以理解，所 附权利要求书中定义的主题不必限于上述具体特征或动作。相反，上述具体特 征和动作是作为实现权利要求的示例形式公开的。