用于分布式系统中的应用的实时迁移和自动恢复的系统

摘要

用于在多个服务器之中的应用分布的方法和装置，确保对用于该应用的主设备上的应用数据的改变被异步地复制到用于该应用的多个从设备。服务器可以位于地理上不同的位置中；本发明准许通过高等待时间和有损的网络连接的数据复制以及在硬件和网络故障条件下的故障容许。对应用的访问由分布式协议处理机调解，其允许针对任何应用的任何请求被寻址到任何服务器，并且其当与复制系统合作地工作时，即刻暂停连接以允许应用及其状态在服务器之前的无缝、一致的实时迁移。另外，一种系统，其基于由每个应用所生成的负载的动态测量和每个应用的拓扑偏好而控制上述实时迁移，以便自动将服务器保持在最优利用水平。

说明书

技术领域

本发明涉及在服务器集群上管理多个应用，并且具体地但不排他地涉及用于以分区和容许故障的方式异步地复制与跨高等待时间的联网系统中的多个（虚拟或物理）服务器（集群）的应用集合有关的数据的机制和装置。

背景技术

对于托管（host）网络连接的应用的组织（包括但不限于，托管因特网上的网站的公司）而言，存在两个关键问题：

1．组件、服务器、网络和存储设备可能故障，在这种情况下将需要也许手动地从辅助（secondary）数据存储（诸如在灾难恢复站点处的备份）中恢复应用。我们将称此为冗余问题。

2．由应用所生成的负载可能随时间而显著地变化，例如网站可能经历业务量中的尖峰，因此应用可能需要在服务器之间移动以便维持可接受水平的利用。我们将称此为负载平衡问题。

在冗余问题的情况下，当前解决方案包括：

·例如通过双冗余电源的使用来在物理硬件层级上添加冗余。对于该途径的缺点包括：在单个服务器内完全消除单点故障是极其困难（即，昂贵）的，并且即便这能够实现，系统仍将在操作系统或其它应用软件中具有单点故障（例如web（网络）服务器或内核（kernel）可能崩溃）。

·虚拟化服务器并且将存储器和系统状态中的每个改变通过高速LAN（局域网）复制到第二物理主机，使得如果第一主机故障则第二主机能够接管，例如利用VMware vMotion。对该途径的缺点包括：虚拟化在应用上强加性能开销，其需要几乎两个服务器的资源来运行（实时的那个和复制品），并且复制品在地理上只能够定位在本地。此外该途径仅在共享的存储后端的情况下工作，其可能昂贵得令人望而却步。而且该途径在没有服务器之间的高速连接性的情况下不能被应用在数据中心之间或者商品设置（commodity setup）上。

在负载平衡问题的情况下，当前解决方案包括：

·当负载的尖峰发生时在服务器之间手动地移动应用。该途径的缺点包括：单独的服务器易受其所托管的应用中任何一个的负载中的尖峰伤害，其能够导致服务器上所有托管的应用崩溃，以及对于可能显著延迟恢复时间的手动干预的需要。

·利用操作系统层级约束来隔离在系统上生成大量负载的应用，例如CloudLinux内核扩展。该途径的缺点包括：如果应用经历负载中的尖峰，则实际上使该应用离线（或者使其非常缓慢地运行），直到它被手动移动到另一服务器为止。

·使用负载平衡器装置（硬件或软件），结合无状态或半无状态应用服务器和共享的存储后端（SAN），以便跨多个服务器而分配应用的负载。我们将称该解决方案为“经典集群”。对于该途径的缺点包括：SAN自身充当单点故障，其故障可以是灾难性的，并且这样的集群不能在地理上跨不同区域而进行操作。对于典型集群的另外的缺点包括：需要实现针对“裂脑（split-brain）”问题的复杂解决方案，其中服务器变成从彼此断开但却不从共享的存储介质断开，这能够导致数据毁损，从而需要管理员设置定额（quorum）、围栏（fencing）或STONITH（“将其它节点爆头”），用以如果服务器变得无响应则将其物理断电。

发明内容

一种被配置成将服务递送到被连接到服务器的至少一个客户端的服务器，所述服务器可操作于主角色（master role）或从角色（slave role）的任一个中以用于多个应用中的每一个，所述服务器包括：

用于将服务器连接到类似服务器的集群中的至少一个其它类似服务器的网络接口；

当服务器处于针对应用的主角色中时可操作的服务递送逻辑，以用于托管该应用以将服务递送到客户端；

当服务器处于针对应用的主角色中时可操作的主逻辑，其被配置成将该应用的数据中的改变复制到集群的可配置数量的服务器；

当服务器处于针对托管在集群中另一服务器上的应用的从角色中时可操作的从逻辑，其被配置成从集群的用于该应用的当前主服务器接收经复制的数据改变并且维护用于该应用的实时应用数据的版本；

控制逻辑，其被配置成检测集群中的事件并且响应于该事件而自主地将用于应用中的一个或多个的服务器的角色在从和主之间转变，其中角色由从到主的改变使用所维护的版本来托管该应用。

服务器能够托管一个或多个应用—也就是说它能够是用于一个或多个实时应用的主服务器。该服务器还能够同时充当用于由不同服务器托管的一个或多个实时应用的从设备（slave）。

将显而易见的是，短语“在主和从之间”覆盖角色由主到从或由从到主的改变。

在实施例中，主逻辑可以包括文件系统安装处理机（handler），其可操作于发送模式中以将数据中的改变传输到集群的可配置数量的服务器。

主逻辑可以包括快照复制器，其被配置成拍下服务当前所托管的应用的文件系统的快照。

主逻辑可以包括至少一个每从设备发送器（per slave sender）以用于将由服务器托管的实时应用的数据中的改变复制到集群的相应服务器。

所述至少一个每从设备发送器可以由基于所需数量的从服务器而用于每个从设备的快照复制器所例示。

从逻辑可以包括被配置成接收经复制的数据改变的接收复制器以及被配置在接收模式中以维护实时应用数据的版本的文件系统安装处理机。

控制逻辑可以被配置成发出指示其在集群中的实时存在的周期性心跳信号。

控制逻辑可以被配置成从集群中的其它类似服务器接收心跳信号，并且从而确定服务器在集群中的实时存在状态。

控制逻辑可以被配置成检测选自以下各项的事件：

（i）用于应用的当前主服务器的故障；

（ii）集群的分区；

（iii）集群中服务器的数量的减少；

（iv）集群中服务器的数量的增加；

（v）将用户针对其已表达了对于托管应用的偏好的服务器引入到集群中；

（vi）在集群中服务器之中的应用的负载改变，使得需要负载重新平衡事件。

控制逻辑可以被配置成发送和接收来自集群中其它服务器的消息，所述消息输送数据，由此能够做出关于服务器针对应用的角色的自主决定。

所述消息可以包括指示所述自主决定的二进制数据。

控制逻辑可以被配置成检测来自集群中所有实时存在的服务器的消息，并且在做出关于其针对应用的角色的决定之前从所有这样的服务器接收消息。

网络接口可以可操作以维持到集群中最少一个其它类似服务器的永久连接，由此在服务器之间的消息能够交换。

所述或另一网络接口可以被配置成建立临时会话以用于传输经复制的数据改变。

服务器可以包括协议处理机，其可操作以在该服务器正托管实时应用时将针对服务的请求路由到该服务器。

根据本发明的另一方面，可以提供一种系统，其包括多个根据以上服务器特征中任一项的服务器。

根据本发明的另一方面，提供了一种在服务器处安装持有用于实时应用的数据的文件系统的方法，所述方法包括：

在引起在服务器处安装应用的事件之前，在服务器处从托管该应用的当前主服务器接收实时应用数据中的改变并且维护实时应用数据的版本；

响应于该事件，服务器将其自身识别为新的主服务器并且使用其所维护的实时应用数据的版本来安装用于实时应用的文件系统；

接收针对服务器处应用的请求并且使用实时应用来服务该请求以递送服务。

在实施例中，所述方法可以被用于从当前主设备的故障中恢复，并且故障可以由将形成新的主服务器的从设备自主地检测到。

所述方法可以被用于从当前主服务器的故障中恢复，并且故障可以由服务器集群中的另一服务器自主地检测到，其中所述主服务器与至少一个其它服务器相连接。

所述方法可以被用于从服务器集群中的分区中恢复，其中当前主服务器与至少一个其它服务器相连接，跟随在该分区之后，至少两个服务器可以自主地将自身标识为潜在的新的主服务器，并且在从分区恢复时，潜在的新的主服务器可以与彼此并且与集群的其它服务器协商以确定主服务器的状态是应当维持还是转移。

所述方法可以被用于管理其中连接了主服务器的服务器集群中的负载，所述方法可以包括检测集群中服务器的数量及其当前的应用负载，并且与集群中的其它服务器交换消息以迁移应用来平衡负载。

在与集群中的其它服务器交换消息以确定最高质心度量的文件系统版本之后，服务器可以基于对已被接收的实时应用数据中的改变的快照的分析而将自身标识为新的主服务器。

安装实时应用可以包括例示用于将新安装的文件系统的数据中的改变发送到集群中至少一个从服务器的复制器发送功能。

当前主设备可以在来自服务器集群的集合中选择作为潜在从服务器的服务器的数量。

根据本发明的另一方面，提供了一种管理由服务器集群托管的多个应用的方法，所述服务器各自具有通过网络可连接到至少一个客户端的接口，每个应用在客户端处递送服务，所述方法包括：

推选集群中的服务器作为主服务器，所述主服务器托管至少一个实时应用；

当主服务器在托管实时应用时，将实时应用的应用数据中的改变复制到集群中被推选为从服务器的可配置数量的服务器，由此每个所推选的从服务器维护实时应用的应用数据的版本，其中当检测到事件时，响应于集群中的事件，应用的托管从主服务器转移到在没有用户干预的情况下确定的所推选的从服务器之一，所推选的从服务器使用其当前应用数据的版本来安装应用并且成为新的主服务器。

在实施例中，所述事件可以是基于集群中服务器的负载而在集群中检测优选的可替换主服务器。

所述事件可以是基于集群中服务器的地点而检测优选的可替换主服务器。

所述事件可以是基于预定义的用户偏好而在集群中检测优选的可替换主服务器。

将实时应用从其当前主服务器迁移到其从服务器之一的决定可以在当前主设备的负载大于集群中所有服务器的负载平均值以及阻尼因子（Q）时做出。本文中称为“阻尼”因子（或“乏晰（fudge）”因子），Q是防止集群中的服务器不断交换负载的值。

可以通过与集群中的其它服务器交换消息来检测事件。

事件可以是向集群的添加服务器。

在一个服务器的添加之前，集群可以包括在单个服务器中。

事件可以是从集群移除服务器，其中所述移除是预期的并且受控实时迁移被发起。

在向集群添加服务器时，可以确定服务器的新负载，并且可以做出关于由集群托管的应用中的哪些应当被迁移到新添加的服务器的决定。

事件可以是集群中服务器的故障，其中用于由故障的服务器所托管的实时应用的数据可以通过使用集群中正在继续操作的服务器上的当前应用的版本来恢复。

事件可以是集群的分区，并且在从分区恢复之后，可以从多个潜在竞争的主服务器中选择优选的可替换主服务器作为具有更加有价值的当前应用数据的版本的服务器。

在服务器之一上所托管的领导者功能（leader function）可以确定用于应用的新的主服务器，其中所述领导者功能可以在不同于主设备的服务器上。

根据本发明的另一方面，提供了一种从主服务器转移应用的方法，主服务器从客户端接收针对由应用所递送的服务的请求，所述方法包括：

在引起转移的事件之前，将应用状态中的改变复制到集群中的至少一个其它服务器；

响应于该事件，自主地暂停主服务器处进入的请求一段时期，其中未决请求被处理；

以及在该时期届满之后，在其中未决请求被处理的情况下，在用于服务该应用的应用数据的版本已经被维护的至少一个其它服务器处路由所述请求。

在实施例中，当未决请求在该时期内未完成时，所述请求可以不被路由到所述至少一个其它服务器，并且放弃对应用的转移。

在该时期届满之后，主服务器可以通过例示用于接收经复制的应用数据改变的复制器接收功能而自主地采用作为用于其之前托管的应用的从设备的角色。

多个应用可以由主服务器托管，其中主服务器可以将改变复制到为每个应用所选的从服务器的集合。

可以基于负载、用户偏好和地点中的至少一个来选择用于每个应用的从服务器。

服务器可以基于在服务器集群中检测优选的可替换主服务器而自主地放弃其作为主服务器的角色。

根据本发明的另一方面，提供了一种在服务器处托管应用的方法，服务器从客户端接收针对由应用所递送的服务的请求，所述方法包括：

确定在一个时间间隔中对支持该应用的文件系统的修改数量；

在可配置的时间点处拍下文件系统的相继快照，其中所述时间点取决于在该时间间隔中对文件系统的修改数量；以及

将快照发送到复制器以用于从服务器的传输。

根据本发明的另一方面，提供了一种管理文件系统的快照的方法，其中文件系统跨连接在集群中的多个服务器而被复制，所述方法包括：

通过以包括快照标识符、到其中拍下快照的特定服务器上的较早快照的父指针以及其中目前存储了该快照的服务器集合的二进制序列形式的快照节点（snapnode）对象来标识每个快照；

在多个服务器中的每一个上存储文件系统的快照集合的快照节点对象的图，所述服务器之一为文件系统的活动主设备；

活动主设备拍下文件系统的新快照并且创建用于新快照的快照节点对象，从而将活动主设备标识为其中存储了新快照的服务器；

将新快照传输到多个服务器中的其它服务器；并且修改快照节点对象以将所述其它服务器标识为其中存储了新快照的服务器。

在实施例中，所述方法可以被用于在其中活动主设备要确认或修改其状态的事件之后管理文件系统的恢复。

所述事件可以是对其中连接了活动主设备和其它服务器的服务器集群的分区，其中在从分区恢复之后，可以存在至少两个候选主服务器，各自都具有用于文件系统的快照节点对象的图，其中可以遍历每个候选主设备处的图以评估它的值，并且具有指示最高值的图的候选主设备可以采用作为用于文件系统的新的主设备的角色。

在执行比较之前，可以跨服务器而全局同步快照数据，由此可以对着全局同步的快照数据来评估每个候选主设备处的数据的版本的偏离（divergence）。

事件可以是多个服务器中的至少一个其它服务器的丢失，其在充当对于活动主设备的从服务器，其中在替换从设备已经由主设备指定之后，主设备可以指令新的从设备复制文件系统的完整现状，使得复制能够从当前点开始。

所述方法可以包括将来自图中的给定切片点（slice point）的快照保存到本地存储区域的步骤。

所述方法可以包括修剪快照的步骤。

所述方法可以包括基于以下各项来确定采取哪个行动以便解决表示相同文件系统的多个服务器上的图的偏离的步骤：

（1）用于文件系统的当前主设备；

（2）用于该文件系统全局状态的快照节点对象的图；

（3）对用于该文件系统的该主设备的当前从服务器的列表。

快照标识符可以标识拍下快照的时间以及其上拍下快照的服务器。

在以上服务器或方法中任一项的实施例中，可以向用户呈现用户接口以用于准许经由用户对由用户所选的快照的访问。

根据本发明的另一方面，可以提供一种使托管多个应用的服务器的集群中的负载平衡的方法，所述方法包括：

确定每个服务器的当前负载；

确定将集群中的服务器处的负载考虑在内的平均负载；

为服务器确定其负载是小于还是大于平均负载加上阻尼因子（Q）；

当服务器的负载大于平均值加上阻尼因子时做出从该服务器迁移应用的决定。

根据本发明的另一方面，可以提供一种包括其上存储了计算机指令集的计算可读介质的计算机程序产品，所述计算机指令集当由处理装置执行时执行根据上文的服务器或方法特征中任一项的操作。

本发明的实施例提供了用于既调解（mediate）对所托管的应用的访问又控制上述数据复制的机制和装置以使得应用能够响应于改变每个应用的拓扑偏好和负载而在服务器之间无缝地实时迁移。

本发明的实施例提供贮存（stashing）能力。一般而言，贮存发生在文件系统偏离时（其例如可以是由于网络分区，或者在从服务器离线从而使得在故障的和重新引入的从设备上的最近快照不再是对于新复制的有效切片点时发生的修剪）-并且导致接收复制的从设备上的文件系统的部分或全部被贮存到称为“贮存器”的特殊本地存储区域中而不是其中实时文件系统所居于的主存储区域中。

根据本发明的另一方面，提供了一种用于在服务器之间动态迁移应用的系统，所述系统包括多个用于托管应用的服务器，所述多个服务器中的每一个都包括用于接收针对应用的请求的协议处理机，其中所述协议处理机被配置成在应用在服务器之间的迁移期间暂停针对应用的进入的请求。

所述系统此外可以包括用于测量多个服务器之一上的负载的负载平衡器，所述负载由该服务器上托管的一个或多个应用引起，所述负载平衡器被配置成当所测量的服务器的预定负载条件满足时，发起一个或多个应用从所测量的服务器到另一服务器的迁移。

所述多个服务器可以各自都具有控制器，其维护其上当前托管了应用的服务器的记录，并且协议处理机被配置成检查该记录以确定进入的应用请求要被指向的服务器。

协议处理机可以被配置成暂停针对应用的进入的请求并且在预定时间段之后终止针对应用的当前请求。

附加地或可替换地，协议处理机可以被配置成在预定时间段内暂停针对应用的进入的请求并且如果针对应用的当前请求在预定时间段中尚未完成则释放所暂停的请求。

根据本发明的另一方面，提供了一种用于在第一服务器与第二服务器之间的分区之前和之后在第一服务器与第二服务器之间复制文件系统的方法，所述方法包括：在第一服务器处，在文件系统的修改之后的预定时间点处拍下文件系统当前状态的快照，每个快照记录在服务器上文件系统的当前状态与在先前快照的时间点处服务器上文件系统的状态之间的差别；一拍下快照就将第一服务器上所拍下的快照连续复制到第二服务器；在检测到分区时，第一和第二服务器这两者成为用于文件系统的主设备并且接受对文件系统的新修改；在分区的恢复之后，执行更新过程以更新文件系统，所述更新过程包括：标识第一服务器和第二服务器中的哪个含有文件系统最当前的版本；将这样标识的服务器任命为主服务器并且将另一服务器任命为从服务器；标识对主服务器和从服务器二者共同的快照；以及将随后的快照从主服务器复制到从服务器。

标识第一服务器和第二服务器中的哪个含有文件系统最当前的（即最有价值的）版本可以包括为服务器中每一个上的文件系统的版本计算质心度量，所述质心度量表示每个服务器上的文件系统快照的平均年龄以及由每个服务器上的快照所表示的对文件系统的改变的数量。

标识第一服务器和第二服务器中的哪个含有文件系统最当前的（即最有价值的）版本此外可以包括标识文件系统的快照集合，其对于每个服务器，每个快照集合包含仅存在于该服务器上的快照，以及基于该服务器的快照集合来为每个服务器计算质心度量。

更新过程此外可以包括存储在共同快照之后拍下的从服务器的快照。

根据本发明的另一方面，提供了一种用于在第一服务器与第二服务器之间的分区之前和之后在第一服务器与第二服务器之间复制文件系统的系统，所述系统包括：快照装置，其用于在文件系统的修改之后的预定时间点处拍下第一服务器上的文件系统当前状态的快照，每个快照记录在服务器上文件系统的当前状态与在先前快照的时间点处服务器上文件系统的状态之间的差别；复制器装置，其用于一拍下快照就将第一服务器上所拍下的快照连续复制到第二服务器；检测装置，其被配置以使得在检测到分区时，第一和第二服务器这两者成为用于文件系统的主设备并且接受对文件系统的新修改；更新装置，其被配置成在分区的恢复之后执行更新过程以更新文件系统，所述更新过程包括：标识第一服务器和第二服务器中的哪个含有文件系统最当前的版本（即最有价值的）；将这样标识的服务器任命为主服务器并且将另一服务器任命为从服务器；标识对主服务器和从服务器二者共同的快照；以及将随后的快照从主服务器复制到从服务器。

标识第一服务器和第二服务器中的哪个含有文件系统最当前的（即最有价值的）版本可以包括为服务器中每一个上的文件系统的版本计算质心度量，所述质心度量表示每个服务器上的文件系统快照的平均年龄以及由每个服务器上的快照所表示的对文件系统的改变的数量。

标识第一服务器和第二服务器中的哪个含有文件系统最当前的（即最有价值的）版本此外可以包括标识文件系统的快照集合，其对于每个服务器，每个快照集合包含仅存在于该服务器上的快照，以及基于该服务器的快照集合来为每个服务器计算质心度量。

更新过程此外可以包括存储在共同快照之后拍下的从服务器的快照。

所述系统此外可以包括存储装置，其用于存储为文件系统所拍下的快照，使得文件系统的先前快照能够由用户从所存储的快照中选择以将系统还原到其在所选快照的时间处的状态。

文件系统的先前快照借助于被呈现给用户的用户接口可以是可选择的。

根据本发明的另一方面，提供了计算机软件，其当由适当处理装置执行时，使得处理装置实现本方面的第一、第二和第三方面的系统和方法。

附图说明

现在将严格仅作为示例、参照附图来描述本发明的实施例，其中：

图1是将快照2复制到已经具有快照1的第二服务器B的第一服务器A的示意性表示；

图1A是托管多个应用的服务器的集群的示意性框图；

图1B是服务器的示意图；

图2是在网络分区和偏离的情况下图1的复制的示意性表示；

图2A是经分区的集群的示意图；

图3是示例复制系统配置的示意性表示，其中存在三个服务器A、B和C以及两个文件系统F和G；

图4是示出了快照复制器状态的示意图；

图5是示出了每从设备发送复制器状态的示意图；

图6是示出了接收复制器状态的示意图；

图7是示出了控制器状态转换（transition）的示意图；以及

图8是分布式协议处理机的示意性表示。

图9是实时迁移状态机转换的示意性表示。

具体实施方式

术语

图1a图示了其中本文所讨论的本发明的各种方面能够有效地实现的计算机系统的示意性架构。将容易领会到，这仅仅是一个示例，并且可以设想到服务器集群的许多变型（包括1的集群）。

图1A图示了如集群那样操作的服务器1的集合。集群形成在2个子集中，其中服务器被标注为1E的第一集合和其中服务器被标注为1W的第二集合。子集可以在地理上分离，例如服务器1E可以在美国的东海岸上，而标注为1W的服务器可以在美国的西海岸上。子集E的服务器1E通过交换机3E连接。交换机可以以任何形式实现—所有所需要的是该子集中的每个服务器借助于其能够与该子集中的另一服务器进行通信的机制。所述交换机能够是具有连接到服务器的端口的实际物理交换机，或者更可能地可以是局域网或内联网。西部子集的服务器1W类似地通过交换机3W连接。交换机3E和3W自身经由网络互连，所述网络可以是用于跨越地理距离的任何合适的网络。因特网是一种可能性。所述网络在图1A中被指定为8。

每个服务器与能够构成任何合适的存储装置的本地存储设施6相关联，例如碟或其它形式的存储器。存储设施6支持文件系统10。文件系统10支持在服务器1上运行的应用，所述应用例如正将服务经由因特网递送到一个或多个客户端终端7。本发明的实施例在通过因特网递送基于web的应用的领域中特别有利。本发明的实施例对于支持电子邮件服务器同样是有用的，其具有本文中所讨论的益处，其中文件系统支持邮箱。

在每一个都能够取决于所选模式而自主地作为主设备或从设备而操作的意义上，服务器和相关联的文件系统基本上类似或同质（homogenous）。

定义对象：

每个客户端7能够发动（launch）诸如web浏览器之类的软件程序，以用于访问由服务器之一所递送的应用（或数据库）。托管该应用的服务器与客户端通信例如以使用HTTP协议递送网页。在本文中，术语应用旨在覆盖在能够由客户端访问的服务器处的任何活动软件或数据结构，并且具体地但没有限制地覆盖程序、数据库和电子邮件（邮箱）或其它消息发送结构。

在本描述中，我们利用基本数学符号，包括：

A定义

集合：

{1,2,3}对于唯一的元素1,2,3

映射：

[1→A，2→B]对于唯一的键（key）1,2

有序数组：

（1,2,B）其可以是不同类型

复合类型定义（命名数组）：

类型（A,B,C）。

假设

我们假设本发明的实施例所取决于的两个底层系统的存在：

1. 每个服务器本地的文件系统10，其能够包含任意多的子文件系统（每个应用或数据库一个）。注意到，在下文中，文件系统支持应用或数据库并且对每个服务器能够存在多于一个，即，子文件系统在下文被称作“文件系统”。文件系统能够包括任何合适的存储装置，例如碟。每个文件系统能够具有任意多的一致时间点快照，各自以本地唯一的字符串命名，并且此外存在将两个快照之间的差别从一个机器复制到另一个的机制。满足这些需求的文件系统的一个示例是开源ZFS文件系统。如本文更加全面地描述的，本发明的实施例使用文件系统的这种能力来将差别从一个服务器复制到另一个以允许服务器自主地迁移应用/数据库。严格作为示例，服务器A上可能存在具有快照{1,2,3}的文件系统F，并且服务器B上可能存在相同文件系统的快照{1,2}。注意到，快照不必作为文件系统的整个比特图像而被存储和传输-文件系统允许我们复制快照2和3之间的差别（例如，仅盘上的块，其发生了改变）以使服务器B是最新的，使得其包含快照{1,2,3}。然而，在以下实施例中，尽管仅传输差别是便利的，但是可以传输完整图像。

2. 由网络8支持的群组消息发送服务GMS，其允许消息M1、M2….Mn在集群中的服务器之间发送。关键地，群组消息发送服务提供关于被广播给群组的消息的某些保证：甚至在有损、高等待时间的网络链路上，还向群组的所有当前活动成员保证消息递送，并且消息排序跨所有服务器是逻辑上一致的。严格作为示例，如果服务器A向群组发送一条消息，并且同时服务器B发送另一消息，群组的所有成员（包括A和B）将以相同的顺序接收到消息。满足这些需求的群组消息发送系统的一个示例是开源Spread工具包。

图1B为单个服务器1的示意图。服务器包括适合于执行指令以递送如本文中更加清楚讨论的不同功能的处理器。另外，服务器包括用于支持处理器的操作的存储器（未示出）。该存储器不同于支持文件系统10的存储设施6。正如将从以下容易地理解的，服务器1能够在任何给定时间处支持多个应用。这些以图解形式通过标注为app的圆示出。示出为交叉影线的app指明作为稍后讨论的应用迁移过程的结果而最近已被安装在服务器1上的应用。以虚线示出的app图示了刚已从服务器1迁移走的应用。服务器1支持协议处理机5，其与集群中的其它服务器的类似协议处理机协作以提供本文中更加全面地讨论的分布式协议处理机机制。服务器1还支持群组消息协议4。协议处理机5通过网络8从客户端终端7接收请求并且负责将请求路由到该请求所寻址到的应用，并且负责向客户端返回从应用所提供的服务数据以用于将服务递送到客户端7。群组消息发送协议4负责与集群中的其它服务器交换消息m1到m4。注意到，这些消息能够在本地通过本地交换机3E/3W和/或远程地经由网络8来交换。服务器1还支持发送和接收复制器34/38，其负责发送和接收在支持应用的文件系统上的应用数据的快照。注意到，图1B是高度示意性的，特别是在服务器1可以具有通过其提供了所有内部和外部通信路径的单个或多个端口的意义上。因而，尽管可能的是提供专用端口用于向客户端终端递送服务、消息交换、以及快照的接收和递送，但是这不是必需的，并且这可以全部发生在服务器的相同物理端口上。在此时注意到，服务器1和存储设施6之间的关系并未在本文中被进一步讨论，因为可以使用任何合适的文件系统布置。因此，尽管被示出为分离的模块，但是如果期望或必要的话，将文件系统存储设施集成在服务器内是可能的。

将领会到，在以下定义的结构和功能能够以硬件、固件或软件的任何合适的组合来实现。特别地，功能能够通过运行在服务器的处理器上的合适代码来实现。因而，当在本文中使用时，术语模块不一定意味着分离的物理模块，而是还能够暗示提供特定功能的指令集的架构描述。

概述

在正常操作期间，系统将为每个应用推选一个主服务器，使得每个应用被托管在集群中的恰好一个服务器上。在主设备上对该应用所发生的改变被异步地复制到用于该文件系统的n个从服务器，为了文件系统的总计n+1个拷贝。这使得系统n冗余，因为它能够容忍n个服务器的故障。对应用的改变是在应用或数据库状态（数据）中的改变，如当其为实时的时候在用于该应用的文件系统中记录的那样。

复制系统

SnapshotGraphForest（快照图森林）数据结构

在本示例中通过SnapshotGraphForest（快照图森林）来提供集群的在任意故障和分区条件下执行服务器之间的数据复制的能力。该数据结构表示给定文件系统跨集群中的所有服务器的全局状态。

我们以具有一个文件系统F的集群的简单情况开始。

图1表示服务器A将第二快照2复制到已经具有快照1的服务器B。服务器A是托管文件系统F的应用的主服务器，并且正在将状态中的改变复制到至少一个所推选的从服务器B。

快照图森林是快照图G的集合。快照图是快照节点的有向非循环图（DAG）。快照节点是文件系统的特定、全局唯一的版本，包括父边缘（parent edge）的集合，其标识该快照节点在图中的位置。

图为DAG，因为快照节点能够具有多个父级（parent）以及多个子级（child）。它是非循环的，因为父快照总是老于子快照，因此在该图中永远不能够形成循环。

每个快照节点由对象类型SnapNode（id,[id_p→(srvs,count,imm)]）限定，其中id为全局唯一的快照标识符，id_p为父指针，其指代其上持有该快照的特定服务器上的较早快照的id（如果它是第一快照，则这可以是空值（NULL），在这种情况下其说成是基于原点），srvs是其上目前存储了快照的服务器集合，count表示由快照所捕获的相对于其父快照的文件系统修改的数量，并且imm表示给定快照在给定服务器上是否不可变（其是否可以被删除）。我们将忽略imm，直到我们稍后讨论修剪为止。快照标识符标识在何处（主机服务器）以及在何时（时间戳）拍下快照。

观察到，SnapNode（快照节点）对象能够表示文件系统同时在多个服务器上的状态，并且捕获到以下事实：在不同服务器上，每个快照的父快照可以不同，即便快照捕获的数据是完全相同的。

快照图被定义为SnapGraph（快照节点的集合），其中，图中所有的快照节点经由那些节点的父和子指针可到达。

在图1中的示例中，在由箭头R标示的复制之前，在森林中存在图G：

               

快照1是初始快照，其在两次改变被记录在原点与该快照之间的情况下存储在A和B 二者上，并且快照2是基于快照1的（具有为快照1的父级）并且仅在服务器A上具有拷贝。作为在服务器A处执行的实时应用的结果，所述改变被记录在文件系统F中。

针对该配置的完整快照图森林是SnapForest({G})。也就是说，在该森林中仅存在一个图G（不存在完全断开的快照节点集合，或者所有节点都连接到所有其它节点）。

在快照2复制到B上之后，图G'具有新状态：

注意到，B现在具有快照2的拷贝，上文以粗体指示。

偏离的图

图2a图示了经分区的服务器集群。

考虑到集群可以从服务器集合的服务器群组{a_1, .. a_m, a_m+1, .., a_n}（其中n>m）变成被分区成两个服务器群组L: {a_1, .. a_m}，R: {a_m+1, .. a_n}。事实上，故障可能导致任意多的分区，但是我们描述两个分区的情况，其归纳到任意多的分区。

事实上观察到，该所有故障可以被归纳至分区，例如单个服务器a_i的故障能够被视为分区成群组{a_j | j != i}和{a_i}。网络交换机的故障能够被视为分区成num-ports许多个群组，其各自都含有单个服务器。

在分区期间，分区的所有侧推选用于所有可用文件系统的新的主设备。现在，分区的两侧上的数据可以随着对分区的两侧上的文件系统做出的改变而开始偏离。

图2示出了如之前那样但是在网络分区情况下的相同集群。现在服务器A和B不能够与彼此对话，并且因此它们二者都推选自身作为用于所讨论的文件系统F的新的主设备。然后这两个服务器可能都观察到对它们的文件系统F的修改（改变）并且服务器A可能拍下快照3，其捕获1次修改，并且服务器B可能拍下快照3'，其捕获4次修改。

针对该系统的SnapshotGraphForest（快照图森林）的全局状态现在为：

也就是说，现在存在四个SnapNode对象，由系统捕获的每个不同的文件系统状态各一个。由于快照3和3'二者都具有快照2作为父级，因此文件系统状态被说成已偏离。注意到，仅仅在网络分区被恢复并且A和B能够再次进行通信之后，它们才能够通过发送包括它们的文件系统状态的消息来发现该完整图。

我们现在将考虑一个最终示例，其论证了为何可能必需要能够表达完全断开的图的森林。假定服务器A和B保持断开并且分区两侧上的用户碰巧在分区的两侧上添加具有相同名称的文件系统G。然后假定系统拍下初始快照：

  在分区的A'侧上

  在分区的B'侧上

现在，作为结果的快照图将不相连接，并且因此森林包含两个断开的图：

多个图还可能由一个服务器A离线了足够久以至于另一服务器B在A回到在线的时候之前已经删除了文件系统的所有共同快照所引起。

有时提及仅包含关于特定服务器上的文件系统的信息的局部森林是有用的。观察到，局部森林总是包含不带有偏离的单个线性图的森林，因为单个服务器上的文件系统必须总是具有从最早的到最晚的快照的线性结构。

最后，关于快照标识符（id）的注释。这些被定义为数组SnapId（timestamp, server）（快照Id（时间戳，服务器）），其中timestamp是自UNIX新纪元以来的毫秒数目，并且server是拍下快照的服务器的全局唯一主IP地址。注意在描述快照最初被拍下的地方的SnapId的server字段与指示快照的拷贝目前存储在哪里的SnapNode的srvs字段之间的差别。

探索SnapshotGraphForest（快照图森林）：计算偏离、头、质心、候选主设备，以及寻找更新

给出表示集群上的文件系统的目前全局状态的全局快照图森林，所述系统的目的是在系统中每个服务器上的本地文件系统上执行操作，以便返回到其中从主设备到从设备的改变的复制可以继续的全局一致状态。

我们在文件系统上能够执行的操作（称作操纵器（manipulator）操作）为：

1. 快照：拍下新的快照。

2. 发送：从一个服务器向另一个发送（多个）增量式快照或完整文件系统。

3. 接收：接收从主服务器发送到从服务器上的快照（增量式更新或完整的复制流）。

4. 贮存：将来自给定“切片点”的快照贮存（保存）到本地贮存区域。

5. 修剪：修剪（删除）快照。

此处我们描述其能够被用于检测偏离并且决定执行哪些行动的过程。重要的行动是响应于诸如故障或分区之类的破坏性事件，确定如何推选用于实时应用的新的主服务器，使得其继续而没有显著中断。

首先我们定义遍历函数（traversal function），其在给定开始节点（快照标识符）的情况下经由其父指针和（推演的）子指针而访问其连接的图中的每个快照节点（SnapshotNode）。其构造子指针和父指针的映射并且然后执行从开始节点可访问的图的搜索，记住其已经看过哪些快照以避免环路。

自此我们能够定义图函数（graphs function），其在给定SnapNode（快照节点）对象集合的情况下从该集合移除SnapNode（快照节点）并且将其完整的图添加到图的集合，直到没有SnapNode（快照节点）对象剩余为止，从而通过确立哪些节点互连来将非结构化的快照节点集合带至到快照图的集合。

现在我们能够定义头函数（heads function），以计算在给定图中哪些快照是每个文件系统的竞争的最新近版本，偏离的“头”。给定如通过graphs（图）所计算的图，该图的头恰好是在图中具有零子级的图元素。

我们能够将关于服务器的受限图（restricted graph）定义为受限于在给定服务器上具有拷贝的快照的快照节点集合。因此在图解2中，完整的图为{1, 2, 3, 3'}，但是受限于服务器A的图为{1, 2, 3}，并且受限于B的图为{1, 2, 3'}。注意到，在受限图中的快照节点仅仅总是具有一个父边缘。

现在我们能够在受限图上定义centreOfMass（质心）函数，其计算加权和：作为受限图中的所有快照的平均时间戳的类时值，其由在该节点的单个父边缘中的修改数量所加权。直观地，具有较新近的质心的图比具有较老旧质心的图更有价值，因为较新近的质心对应于更新近且更显著的改变。

这是能够被用于计算受限于服务器A的图G的centreOfMass（质心）的公式：

首先我们将受限图的尾简单地定义为在该图中不是第一快照的所有快照。这是因为每个快照节点g与其父级的中点仅在parent（g）（父级（g））不是原点时被定义。然后我们能够将受限图的centreOfMass（质心）定义为在该快照与其父级的时间的中点的图尾中的快照上的和，其由每个快照的权重（该快照与其紧靠的父级之间的改变的数量）加权，除以图尾的总权重。

作为示例，考虑图解2中的受限图中的哪个具有最高的质心：受限于A的图具有centreOfMass（质心）(3*(2+1)*0.5 + 1*(3+2)*0.5)/(3+1) = 1.75而受限于B的图具有centreOfMass（质心）(3*(2+1)*0.5 + 4*(3+2)*0.5)/(3+4) = 2.071。直观地，受限于B的图获胜，并且B应当被推选为新的主设备（因为它的数据捕获较大权重的新近改变）。注意到，我们不对快照1与原点之间的权重进行计数，但是这无关紧要，因为它在两种情况中相等。

为了正式化该直观，我们定义了chooseCandidateMasters（选择候选主设备）函数，其允许系统处理其中由于网络分区而引起两个或更多个服务器已经变成用于文件系统的竞争的主设备的情况。当网络分区恢复时，服务器通过交换每个服务器认为对于哪些文件系统其是主设备而对于哪些其不是的列表（称作当前主设备消息）而观察到它们处于竞争中，并且此外它们交换对于构造全局森林所必需的快照数据以决定哪个服务器应当继续作为主设备。

chooseCandidateMasters（选择候选主设备）函数如下操作：给定图，它计算被牵涉在图中的服务器的集合（即，哪些具有图中任何快照节点的拷贝），并且对于每个这样的服务器，为该服务器计算受限图。对于每个受限图，它计算该受限图的质心，并且最后它返回在最大质心处成平局的服务器集合。

当服务器检测到它们二者当前都是主设备时，通过检查它们的当前主设备消息，它们二者都基于全局同步的快照数据而运行chooseCandidateMasters（选择候选主设备）函数；无论哪个服务器发现它是最佳的候选主设备，则断言对站点的所有权并且其它服务器让与新的主设备（它们变成从设备）。如果它们成平局，则由服务器以词典编纂上（lexicographically）最低的IP地址来随机推选一个。

如果主设备观察到从设备已经完全断开（分离图），则它比较断开的分段的权重，并且获胜侧（新的主设备）指令失败侧（新的从设备）完整地贮存该整个文件系统，使得复制能够从擦除开始。也就是说，如果在主设备和从设备之间没有共同快照（图“完全断开”），则从设备必须贮存整个文件系统并且主设备必须复制整个历史，从NULL（空值）快照一直到最近的快照。

现在我们能够定义过程findUpdates（寻找更新），给定如下自变量：1.已经被推选为主设备的服务器，2.针对该文件系统的全局状态的完整SnapshotGraphForest（快照图森林），以及3.从服务器名称列表，所述过程决定采取哪些行动以便解决偏离并且允许正常复制在那些从设备上继续。findUpdates（寻找更新）函数通过使用traverse（遍历）函数而在当前主设备的最新近的快照id（master_head）（id（主设备_头））处开始，向后工作从而访问每个（父，子）对来工作。一旦它找到与任何从设备的共同快照，它就知晓，该父级是针对该从设备的“切片点”，因此它记录更新slave → (snapshot_id,master_head)。因此findUpdates（寻找更新）的输出为复制行动的集合：

{slave → (start_snapshot_id, end_snapshot_id)}

这对应于需要被采取以利用主设备使从设备（具有带有相同名称的文件系统的任何拷贝的机器，并且其可以具有复制基于其上的一些共同快照）最新的行动，可能地导致从设备需要贮存一些数据以防它们的数据偏离，在这种情况下，start_snapshot_id（开始_快照_id）对应于从设备上的非头快照。否则，它是从设备上最新近的（“头”）快照，并且复制事件已知为简单的“快速向前”更新。

开始和结束快照节点能够是在图中远离彼此的多于一个的弧形边缘，因为底层文件系统能够在单个复制事件中发送多于一个的快照。

在不太可能的情况下，其中不存在偏离但是给定的主设备具有比从设备更早的头快照，（即，从设备上直到第一共同快照的快照是主设备上快照的严格超集），主设备受尊重并且从设备被指令贮存文件系统直到在该处主设备能够继续复制的点。这种特殊的情况被表达为其中start_snapshot_id（开始_快照_id）和end_snapshot_id（结束_快照_id）完全相同的更新。这在实际中不应当发生。

主设备运行findUpdates（寻找更新）函数并且发送结果，对于每个从设备，作为对于从设备开始复制的指令（复制消息）。现在我们将覆盖在主设备及其从设备上的参与组件之间的状态转换方面复制如何继续进行的细节。

所贮存的数据可以可选地被提供给用户，以防用户希望从分区的失败侧恢复数据。

复制器

概述

如图3中所示，存在五种类型的对象参与文件系统的安装、卸载（unmount）和快照、到从设备的数据复制以及快照的修剪。这些对象能够被实现为适当编程的处理器中的软件，以硬件、固件、状态机或者以任何其它方式实现。

1. 控制器30，其中对于每个服务器恰好存在一个。控制器30负责跨所有服务器同步全局状态、推选主设备、添加和移除从设备、以及代理状态机与群组消息发送协议之间的通信。它还实现在实时迁移方面的负载平衡。

2. 安装处理机32，其处理安全地安装和卸载文件系统。这些存在于主设备和从设备二者上，每个文件系统一个。

3. 快照复制器34，其存在于主设备上（每个文件系统一个），其接收文件系统已经被修改的通知并且决定何时拍下新的快照。

4. 每从设备发送复制器36，其存在于主设备上（每个文件系统每个从设备一个）并且其通过群组消息发送协议4与接收复制器38（经由控制器[注意图3未图示该通路]）进行通信以便根据来自快照图findUpdates（寻找更新）函数的结果来调解快照数据从主设备到从设备的传输。

5. 接收复制器38，其与每从设备发送复制器通信以调解快照数据从主设备到从设备的接收。

图3示出了一种可能的配置，其中存在三个服务器A、B和C以及两个文件系统F和G。该图解对应于以下的currentMasters（当前主设备）映射：

[F → 服务器 A,

G → 服务器 B]

在该示例中，服务器A是用于文件系统F的主设备，并且服务器B是用于文件系统G的主设备。服务器C是用于这两个文件系统的从设备，并且集群被配置成对每个文件系统将文件系统数据复制到两个从设备。图3中的粗线表示文件系统快照数据流。

控制器和安装处理机

每个控制器30具有用于每个文件系统的文件系统安装处理机32，并且每个文件系统安装处理机处于两种状态（接收或发送）之一中。如果安装处理机32处于接收，则它的文件系统（例如服务器A中的G）被卸载并且它具有接收复制器38。如果安装处理机处于发送，则它的文件系统被安装（例如服务器A中的F）并且它具有发送复制器34。由应用对该文件系统F主动地进行改变，由快照复制器34对其进行快照，并且发送复制器的每从设备复制器（例如36B、36C，每个从设备一个）负责向等待的接收器发送快照。

以下的流程图表示以上提到的对象的操作。

图4、5和6中的粗线对应于平常的成功情况，其它线对应于错误处理或分区恢复状态。

快照复制器状态

见图4。

快照复制器34接收文件系统修改的通知和要拍快照的调度（schedule）。当拍下快照时，其告知其每从设备发送复制器36它们应当检查是否向其从设备发起复制事件，所述从设备具有被设置准备接收的接收复制器38。

其开始于加载（LOADING）状态，这意味着其正询问文件系统当前的快照状态并且将其加载到其森林中。当这完成时，它进入就绪（READY）状态。当它达到就绪状态时，它将新状态告知控制器30，控制器将所述新状态广播给集群中的其它节点。当所调度的快照预定发生时，它在快照发生的持续期间内进入快照（SNAPSHOTTING）。

其维护表示在所有节点上对于该文件系统的快照数据的全局状态的全局森林35（图3）。其通过informGlobalState（告知全局状态）接口而被告知关于其它服务器的状态，当它从集群中的其它服务器接收到关于全局状态的更新时其控制器调用该接口。

快照的调度响应于修改的通知如下工作：

如果文件系统接收到仅一个修改，则它在SNAPSHOT_QUICK（快照_迅速）超时内被快照，其基于前一个在修改之间的时期。

如果文件系统在SNAPSHOT_QUICK（快照_迅速）时间间隔内接收到许多修改，则它SNAPSHOT_INTERVAL（快照_时间间隔）超时处拍下快照，其更长。

这意味着如果文件系统被大量修改，则它每隔SNAPSHOT_INTERVAL（快照_时间间隔）秒就被快照，而如果它仅被修改一次，则它在SNAPSHOT_QUICK（快照_迅速）秒内被快照。这些值的一些样本值分别为30秒和60秒。

当快照完成时，复制器还异步地处理修剪，以便将快照的数量保持于合理的数量（典型地每个文件系统100个左右）。修剪在稍后被详细描述。

快照数据库

快照数据库需要来自数据库的协作以便强迫其通过在快照操作期间持有数据库上的锁来使其盘上状态一致。在一个实施例中，本发明通过向MySQL数据库发出“在读锁定的情况下刷新表（FLUSH TABLES WITH READ LOCK）”查询来实现这一点。其它数据库引擎能够利用等同机制而与本发明集成。这允许数据库以及应用和邮箱被快照、自动恢复和在服务器之间实时迁移。数据库和有关的文件系统快照可以在时间上协调，使得应用在盘上和在数据库中的状态是一致的。

每从设备发送复制器状态

见图5。

每从设备发送复制器36负责结合远程接收复制器38而发起复制事件。它开始于就绪（READY）状态（没有必要加载，因为它指的是其父快照复制器的森林）。当它已经在其上调用了检查（check）时，要么由于新快照已经创建，要么由于刚已经添加了服务器作为从设备并且为其创建了新的每从设备发送复制器，因此它在其森林上调用findUpdates（寻找更新）。

当findUpdates（寻找更新）指示特定数据流（具有定义的开始和结束快照id）应当从本地服务器被发送到每从设备被设置所用于的远程从设备时，其通过群组消息发送协议向远程接收复制器38发送消息并且进入状态发送_等待（SENDING_WAITING）。如果远程接收复制器38接受复制尝试，则每从设备发送复制器36进入状态发送_运行（SENDING_RUNNING）并且快照数据开始通过网络而流动。当已经发送了所有快照数据时，快照发送复制器34进入WAIT_FOR_ACK（等待应答）状态，这意味着它正等待远程接收复制器应答对所指示的数据的正确接收和存储。当那发生时（再次经由群组消息发送协议），每从设备发送复制器重新进入就绪（READY）状态。

如果在任何点处从远程侧接收到故障消息，或者如果超时引发（如果远程机器故障或者网络变成被分区，则这可能发生），则状态机转换到暂停（PAUSE）并且然后在另外的超时之后转换回到就绪（READY）。这允许复制在没有造成大量消息要被发送的情况下继续，以防远程侧临时不能接收新的复制事件。

接收复制器状态

参见图6。

当服务器是用于文件系统10的从设备时，文件系统安装处理机32处于接收（RECEIVING）模式中并且已经确保文件系统自身被卸载，并且可用于从远程每从设备发送复制器36（其通常将存在恰好一个，因为在任何给定的网络分区内对于每个文件系统仅存在一个主设备—如果在网络分区和随后的恢复之后存在多于一个的主设备，则上文所描述的主设备协商将确保一个主设备在少量时间中让与以使得复制能够继续）接收文件系统更新。

接收复制器38开始于加载（LOADING）状态，其中它正询问文件系统当前的快照数据。当它接收到文件系统数据时，它告知其控制器30当前的快照状态。控制器30将此告知集群中的其它服务器，并且接收复制器38进入就绪（READY）状态。在已经告知其它服务器当前状态后，它们可以基于它们的全局森林计算而判定从设备已经偏离，或者其需要简单的“快速向前”更新。

如果更新是快速向前更新，则复制器直接继续进行到接收（RECEIVING）状态，并且快照数据通过网络而流动。当其完成到加载（LOADING）状态的转换时，检查所预期的数据被正确接收，然后发起异步修剪并且立即为下一个复制事件成为准备就绪。

如果更新不是快速向前更新，则复制器代替地转换成贮存（STASHING）状态，其中它在本地“贮存目录”中存储在“切片点”（由发送复制器所指示的end_snapshot（结束_快照），其是主设备和从设备之间最近的共同快照）与从设备上文件系统的当前头之间的快照的二进制拷贝。一旦该贮存完成，文件系统就立即准备接收改变并且复制照常继续进行。开始快照于是被标记为不可变，使得贮存过程可以被反转。

在一些情形中，从设备上的本地文件系统可以被修改（即便意思是被卸载，管理员可以偶然地例如安装它和修改它）。在这种情况下，复制将失败，然而接收复制器检测到该情况，并且转换成LOCAL_MODS，其使得本地修改被快照并且安全地贮存。接收复制器发出故障消息并且每从设备发送器将转换至暂停（PAUSE），并且当其超时引发（fire）时再次尝试，使得复制能够继续。

修剪算法

过程在上文中描述了创建快照，但是不销毁它们。销毁旧快照以便将快照的数量限制于合理的数量是重要的。当你有多于几百张的快照时文件系统操作变得缓慢。对于用户而言，远离超过一年之前的一分钟前拍下的两个时间点快照之间的差别与来自过去几分钟的两个时间点快照之间的差别相比很可能是不太重要的，因此与较新的那些相比更加进取地修剪较旧的快照是有意义的。修剪是将来自多个相继快照的改变叠并（collapse）成单个快照的过程。

修剪过程的重要属性是其导致集群中所有服务器上的相同快照被选定用于删除。这使得findUpdates（寻找更新）过程将找到新近的共同快照并且避免不必要地发送大量复制数据。

修剪算法通过定义一组区段来工作：典型地前一小时、前一天、前一周和前一个月，并且然后用“路径点（waypoint）”在区段之间“填充缝隙”，例如系统可以被配置使得来自前60分钟的所有快照将被保留，为前一天保留每小时的快照，为前一周保留每天的快照，等等。

通过suggestedDeletions（建议删除）函数来建议删除快照，如果它们不是离路径点最接近的快照的话。

由于路径点相对于时间推移是相当稳定的，因此在所有服务器上采取几乎相同的修剪决定，即便修剪在不同服务器上稍微不同的时间处发生。

非常新近的快照还将被排除在对于删除的考虑之外，并且不可变的快照从不被删除。如果基于该快照已发生了贮存，则该快照被标记为不可变（仅仅在特定服务器上本地地），这是因为为了基于中间快照而恢复快照贮存，中间快照必须仍然存在，并且因此对于将可用于从其恢复数据的贮存而言，必须使得贮存所基于的快照不可变且从不被删除直到贮存被丢弃为止。

快照复制器34和接收复制器38二者都利用该修剪算法来将主设备和从设备上的快照的数量保持在合理界限内。

系统可以可选地暴露接口以用于用户回滚特定快照、从给定点处的快照克隆新的应用和数据库以及手动地将某些快照设成是不可变的。

控制器

本章节解释了总体“控制器”过程，其负责觉察到哪些服务器在当前网络分区（如果有的话）内在线以及因此哪个服务器应当被推选为用于每个站点的主设备。其还负责如果文件系统复制不足（under-replicated）则添加从设备，并且如果文件系统复制过度（over-replicated）则移除从设备。

集群引导与合并过程

参见图7。

在正常操作期间，服务器将通过群组消息发送系统以适当时间间隔广播若干消息：

1. 心跳消息—M2断言每个服务器的活性（liveness）以及每个服务器正在通过其自身的测试（所有系统和过程在该服务器上正确操作）。该数据以称作活性映射的映射而存储在每台机器上。

2. 可用数据消息M2—声明每个服务器具有哪些文件系统的哪些快照，用于确定文件系统状态以及告知复制决定，如所描述的那样。该数据以称作可用数据映射的映射而存储在每台机器上。

3. 当前主设备消息—M3声明哪些服务器当前是用于哪些文件系统的主设备。该数据以称作当前主设备映射的映射而存储在每台机器上。

4. 负载值消息—M4声明当前在每个服务器上由每个应用所生成的负载量，用在负载平衡计算中。

还存在可以以经配置的时间间隔而运行的多个周期性检查：

1. 发出心跳（S4）

2. 发出当前主设备消息（S4）

3. 检查死文件系统（S6）

4. 检查负载平衡（S7）

5. 检查冗余（复制过度/不足）（S8）

当服务器起动时，其通过读取当前文件系统S1和快照状态而开始。如果上一次存在完全（clean）关机，则它可以从本地缓存文件读取该数据，所述本地缓存文件还包括关于先前的当前主设备状态以及刚好在该服务器先前关机之前为实时（live）的服务器的数据（CHECK_TIMEOUT（检查_超时）宽限期被应用于先前为实时的每个服务器以在控制器“解救”其站点之前回到在线）。这是为在必要时促进迅速集群重启，因为过度的重装（其是缓慢的）被避免。

心跳消息

控制器30使用群组消息发送系统来每秒从每个服务器发出心跳。系统记录上次它从每个服务器S2听到音信的时间并且每个服务器能够因此基于CHECK_TIMEOUT（检查_超时）时间间隔来检测哪些服务器是实时的（即在与它相同的分区中），以及哪些服务器是静默的（故障或者被分区）。

避免过早的行动

当服务器在起动时，它可以观察看起来似乎指示它应当执行某个行动的某个状态，诸如解救明显的死文件系统。然而这种行为可能是完全不正确的，因为它可能尚未听到它所需要以便做出正确决定的所有信息。因此，我们定义一种概念，其称作从所有服务器听到音信（heardFromAllServers）S3、S5，其定义了实时服务器的该集合（在过去的CHECK_TIMEOUT（检查_超时）秒内我们已从中听到心跳的服务器）必须是所讨论的映射的键的子集。因此我们通过从所有服务器听到音信（heardFromAllServers）的检查（检查我们已经从所有服务器听到可用数据或者当前主设备消息）来防护将会执行这样的潜在损坏行动的周期性检查。

因此图7描述了服务器当其起动时将经历的状态，以及新服务器加入、发出心跳，但是尚未断言其对文件系统的所有权如何可以引起集群中的其它服务器延迟再次运行它们的循环直到新服务器已经发出数据集消息为止。只有当所有服务器已经听到（S3）所有其它实时服务器发出数据集消息时，任何服务器才将被允许发出当前主设备（S4）消息，并且只有当在当前的当前主设备状态上存在全局共识时，任何服务器才将因此能够运行检查死站点（checkDeadSites）（S6）。这使得集群对于服务器或网络故障是非常稳健的并且被带回在线而没有做出部分告知的决定，所述部分告知的决定可能造成不幸的结果，诸如旧服务器当实际上它有两个星期之久的所有数据的拷贝时上线并且要求作为用于大量文件系统的主设备。

使用领导者（leader）来决策

系统将用于文件系统的领导者定义为具有最低词典编纂上的IP地址的服务器，其具有该文件系统的拷贝。例如，在图1A中，当前主设备可以是服务器A，但是领导者可以是服务器B。这打破了在另外的同质分布式系统中的对称。

注意到，作为用于文件系统的领导者非常不同于作为用于它的主设备。仅仅使用领导力（leadership）检查以便确立哪个服务器能够做出关于改变哪个服务器为用于该文件系统的当前主设备的决定。这种机制停止了多个服务器同时试图对文件系统的迁移有冲突。当然，在一些情况下领导者服务器将会是当前主设备—领导者角色是对于主设备角色分离地定义的角色，但是可以在相同服务器上。

当前主设备消息发出二进制值来会聚于（converge on）全局状态共识

当前主设备消息M3含有来自每个服务器1的其正托管哪些站点和不托管哪些站点的列表。这允许所有服务器构造全局一致的当前主设备映射并且解析分区恢复之后的竞争主设备。

是在接收到当前主设备消息M3时，其中在新近合并的分区中两个竞争主设备的情况可以被检测和处理。这通过使用在快照图章节中描述的chooseCandidateMasters（选择候选主设备）函数来完成。

系统为每个文件系统广播二进制值真或假。通过查看来自所有服务器的当前主设备消息的总体，并且与系统自身的当前主设备映射相比较，我们通过使用以下逻辑来正确地同步全局状态：

如果服务器要求托管文件系统，但是我们不认为它被托管在那里，或者服务器要求不托管文件系统但是我们认为它被托管在那里

并且我们是用于该文件系统的领导者

则基于候选主设备计算而将其移动到最佳服务器

本地和远程冗余计算（addSlaves（添加从设备））

复制检查循环为服务器1目前作为主设备所用于的每个文件系统10检查两件事情：文件系统是否复制不足，在这种情况下它在快照复制器34上调用addSlaves（添加从设备），其创建一些新的每从设备复制器36以用于所选定的新的从服务器（其然后自动创建新的接收复制器，并且文件系统被拷贝到新的从设备）。

第二检查是文件系统是否复制过度，在这种情况下它发出deleteFilesystem（删除文件系统）消息，其引起远程从设备废弃它们的文件系统的拷贝并且用于那些从设备的每从设备复制器36被关机。

在一个实施例中，集群知道哪些服务器在本地数据中心以及哪些服务器在远程数据中心。这允许它基于集群的配置而对关于每个地点中的多少从设备要复制到的这方面更加智慧。例如，集群管理员能够决定她希望拥有本地冗余（localRedundancy）值为2，这意味着除了主设备之外，在本地数据中心中的两个服务器使每个文件系统被复制到它们（使得集群能够应对2个本地服务器的故障），全局冗余（globalRedundancy）值为1，这意味着两个其它数据中心（地点）必须使每个文件系统被复制到它们，以及每远程地点的从设备（slavesPerRemoteLocality）值为1，其意味着每个远程地点必须具有一个服务器，其获得文件系统的拷贝。

由于文件系统和应用可以从一个数据中心实时迁移到另一个，因此当文件系统到达那里时附加的复制品可能在新的数据中心中自动地被创建，并且在旧的数据中心中的一些复制品可能被移除。

检查死文件系统

如果服务器故障，一些文件系统将停止在任何实时服务器上被托管。在这种情况下，在每个服务器上的检查死文件系统（checkDeadFilesystems）循环计算它能够关于其做任何事的死文件系统的集合，其关注是：对于服务器具有其拷贝的那些文件系统，文件系统的当前主设备（如果有的话）目前并不实时。

对于这些文件系统中的每一个，每个服务器确定其是否是用于该文件系统的当前领导者，并且如果其是，其基于来自chooseCandidateMasters（选择候选主设备）函数的最优服务器中的一个来推选用于该文件系统的新的主设备。

分布式协议处理机

在客户端与系统之间调解所有协议访问（示例协议：HTTP、HTTPS、MySQL客户端协议、SMTP、POP和IMAP）的是图8中描述的分布式协议处理机5。

它们允许针对任何文件系统的任何请求被指引到集群中的任何服务器。这意味着例如，可以设立DNS配置使得网站具有多个' A'记录，各自指向集群中的不同服务器，以利用HTTP中的（有限）内置冗余，其中web浏览器将尝试可替换的' A'记录，如果它所尝试的第一个不可用的话。

在每个服务器1上，协议处理机5“坐在”实际应用服务器的“前方”（示例应用服务器：Apache、MySQL服务器、Exim、Dovecot）。另外，协议处理机连接到上文描述的控制器，并且可以访问其当前主设备映射。协议处理机能够“说出”每个协议的恰好足够的，以确立请求应当被路由向哪个文件系统。示例图8示出两个服务器1的配置，其中针对文件系统F的请求从客户端7经由网络8来到服务器A，并且通过进入代理（incoming proxy）80A而被接收。协议处理机通过检查在服务器A处控制器的当前主设备映射来选择后端服务器，并且发现它需要将请求路由到服务器B，因此它的外出代理（outgoing proxy）82连接到服务器B'的进入代理80B。然后服务器B检查它的当前主设备映射（其通过上文所描述的全局状态共识而与服务器A'的相符）并且将该请求路由到它自身的“后端服务器”。在这点上连接是“无缝接合的”使得客户端7或后端服务器（在该情况下B）两者都不能分辨这不是完全普通的客户端连接。客户端和正确的后端服务器然后照常通信（例如：服务器通过HTTP连接向客户端发送网页），但是同时协议处理机保持对经过它们的连接的追踪。

它们需要保持对连接的追踪，因为它们有能力按需暂停新请求。这是为了实现无缝的实时迁移。如果控制器30已经请求了协议处理机5暂停到给定服务器1的连接，则它将以两种模式中的一个。它将等待超时以用于“飞行中（in-flight）”的连接自然关闭，同时暂停所有新的进入的连接，然后：

1. 如果暂停是迫使的，并且如果当前飞行中的连接没有自然关闭，则它将强行终止它们。

2. 如果暂停不是迫使的，则它将等待超时以用于连接自然死去（die），同时暂停所有新的进入的连接。如果飞行中的连接没有在所分配的时间中完成，则放弃暂停尝试并且新暂停的连接被“解放”。

如果暂停成功，则它等待，直到控制器30请求“解封（unblock）”暂停，在这点上系统通过问控制器来检查哪个后端服务器1应当再次被连接到（至关重要地，后端可能已经在暂停操作期间改变了），并且连接到潜在不同的后端服务器，解放“大批请求”，其在暂停过程期间建立到新服务器上，所述新服务器于是能够如平常一样处理它们。如果延迟充分短，终端用户将仅注意到小延迟。

实时迁移

现在我们拥有拼图的所有片来参照图9描述完整的实时迁移过程。为了扼要重述，我们能够：

确保复制继续进行到从服务器，甚至在故障和分区的条件下，并且在那些条件的恢复之后恢复。

用分布式协议处理机控制入站（in-bound）连接，使得任何请求能够被寻址到系统中的任何服务器，并且使得系统能够即刻暂停入站连接，等待飞行中（未决的）那些完成，并且将请求重定向到不同的服务器。

现在我们能够描述实时迁移状态机转换和协议。控制器可以在用户的指引下或者由于下文描述的两种机制中的一个，选择发起应用从一个服务器到另一个的实时迁移。

“投掷器（thrower）服务器”30（主服务器）的控制器在状态INIT 90中创建投掷器对象，其负责同时控制复制系统和分布式协议处理机。该投掷器对象向目标服务器（捕捉器（catcher））（新的主设备）的远程控制器发送请求移动负载（requestmoveload）消息，其试图92为实时迁移分配间隙（存在被允许并行发生的有限数量的实时迁移）。如果间隙（slot）被分配，则它在状态INIT 94中创建捕捉器对象，并且捕捉器发出接受移动负载（acceptmoveload）消息。然后投掷器指令96它的快照复制器34构造每从设备复制器36以用于目标服务器，以防其尚未是从设备。投掷器然后发送最近快照（latestsnapshot）消息，其指令捕捉器进入预复制状态（PREREPLICATION）98直到已经接收到快照。这可能不是用在复制中的最终快照，但是其至少使捕捉服务器“相当时新”使得其中针对文件系统的入站请求即刻被阻挡的实时迁移的关键路径元素尽可能地短。如果捕捉器观察到它已经具有该快照，则它能够绕过180预复制阶段并且立即发起继续移动负载（continuemoveload）消息。否则，它发出99预复制（prereplication）消息并且然后当捕捉器的复制系统观察到快照到达时，其告知投掷器它可以通过发送继续移动负载（continuemoveload）消息来继续。投掷器然后指令102它的分布式协议处理机开始暂停所有新的进入的请求并且当所有当前飞行中的请求完成时通知它。捕捉器做相同的事100。现在整个实时迁移过程可以处于两种模式之一中，受迫使或非受迫使。如果模式是非受迫使的，并且存在到当前主设备的长期实时（long-lived）的连接（例如，诸如IDLE IMAP连接），则暂停可以被放弃，其引起整个实时迁移被放弃（这可以是有用的，例如如果有必要完全关断服务器以迫使实时迁移来使得它们总是在少量时间中成功，这以可能关闭一些长期运行的连接为代价）。当两侧的分布式协议处理机都成功地关闭所有的当前连接并且暂停/阻挡所有新的进入的连接时，投掷器指令104它的文件系统安装处理机以卸载文件系统，使得不可能能够对其做出进一步改变，在这点上它拍下文件系统的最终快照并且将该最终快照复制106到捕捉器，这都在针对应用的新进入的请求被暂停的时候。当复制108成功时，捕捉器安装110文件系统，并且发出完成移动负载（completemoveload）消息，其导致投掷器和捕捉器二者都解封112它们各自的分布式协议处理机并且因此一大批暂停的请求（用户耐心地等待该过程所花费的数秒）被解放在用于该站点的新的主设备上。

驱动实时迁移

控制器30具有用于自动发起实时迁移事件的两种机制。这些是负载平衡机制和应用地点偏好机制。

负载平衡：负载>av+Q

集群中的所有服务器1不断地交易关于由每个应用所生成的负载的当前水平的信息，例如通过测量在十秒时期内针对该应用的总请求次数的总和。通过在10分钟内使用指数式衰减算法（由UNIX负载平均计算所使用的相同算法）来使这些测量“平滑”。服务器连续地（在检查负载平衡（checkLoadBalancing）循环中）检查它们的总负载（跨所有其应用的负载总和）是否超过集群中的平均负载加上“乏晰因子”Q，其存在以使服务器停止不断地交易负载。如果服务器的负载超过av+Q，则服务器推选接收者服务器，其是出自所有服务器的具有最低负载的服务器，并且从其当前站点中拾取站点，其是将不使得接收者自己认为其过载的最大负载的站点。这已知为“防烫手山芋选择功能”，因为它使服务器停止不断交易负载。所选择的站点被实时迁移到接收者。

来自该简单的规则集的突现行为（emergent behaviour）是服务器将自动地通过在集群中的服务器之间到处迁移整个应用来使自身负载平衡。此外，如果一个特定应用得到业务量中的大尖峰，则该应用自身将不被实时迁移（因为防烫手山芋选择功能禁止这样）；相反地，该服务器上的所有其它应用将被迁移走，留下该服务器成为用于该应用的专用服务器。

应用地点偏好

回想到集群可以在地理上跨不同区域分布。用户可能希望表达偏好以使得如果给定区域可用（如果那里存在在线的服务器）则它们的站点应当首先托管在那里。如果用户指定或改变该偏好（其可以存储在数据库中），则控制器检测到改变并且发起应用和任何相关数据库这两者的实时迁移。这是重要的以使得应用及其数据库总是存储在地理上的本地区域中，因为数据库访问经常被假设成是低等待时间的。对于应用而言还可能重要的是不被托管在或复制到给定地点，以便遵守本地法规。

保护以防用户错误

在保护以防硬件故障的数据保护系统中，诸如RAID或同步复制之类，如果用户意外地删除了数据，则删除被复制到（多个）复制品设备并且所删除的数据将永久丢失。

如以上所解释的，本发明的系统连续地拍下存储在系统上的所有数据的时间点快照，并且这些快照被存储使得它们能够由用户访问，例如经由web接口，其呈现可用快照的图形表示。如果用户意外地删除了来自系统的数据，则先前的数据快照可以使用该接口、通过选择图形表示的快照之一而被选择，并且系统可以被还原或回复到其在所选快照被拍下的时候的状态，例如在删除之前，而无需系统管理员的介入。

本发明的上述实施例递送了如下文所阐述的多个特征和优点：

1. 从服务器或数据中心故障中自动恢复以用于复原

回到图1A，当心跳消息指示服务器或者也许甚至服务器的整个子集或到服务器子集的连接（诸如例如交换机3E或3W）已故障时，附到支持特定应用的该服务器的文件系统现在死了的这一事实可以被识别到并且该情形可以在对接收由针对其的文件系统现在已变成死的应用所支持的服务的终端客户端7的（如果有的话）最小中断的情况下被自动恢复。

这方面由连续文件系统复制的机制所支持，由此主服务器连续地向从服务器的指定集合传输具有用于它们所支持的实时应用的文件系统图像的快照。再次回到图1A，例如东部子集中的主设备可以确保他总是指定东部子集中的至少一个其它服务器以及西部子集中的至少一个其它服务器以用于支持特定应用的递送。

用于应用的当前主设备可以执行本地和远程冗余计算（addSlave（添加从设备）功能）以用于检查并且如果必要的话增加冗余。因而，主设备可以自主地不仅确定它将应用数据所复制到的从设备的数量，而且还确定那些从设备的性质和位置。除其它事项之外，这可以由用户输入或用户偏好来指导。

2. 从网络分区恢复—最有价值的数据被选择。

参照回图2A，在从分区的恢复中，领导者服务器可以自主地决定多个潜在主设备中的哪个应当被推选为新的主设备。将容易显而易见的是，在分区之后，可能存在分区的任一侧的服务器，其各自认为自己是应用的主设备。在该情况下，早前描述的图加权函数可以被实现以确定较大的质心并且因而确定哪个主设备具有最有价值的数据。注意到，通过以下事实已经相当大地帮助了从分区的恢复：即在分区之前存在正在进行的文件系统复制，使得潜在新的主设备中的每一个将已经具有一个版本的文件—这是确定谁具有最佳版本的问题。

3. 迁移准则

除了提供支持从故障的自动恢复和从网络分区的恢复的机制之外，上文所描述的实施例能够出于优化目的而递送实时迁移。因而，集群中的服务器可以通过它们的消息交换来自主确定应用在不同的主设备上将会被更好地服务，甚至在其中尚不存在当前主设备的故障的情况下。这能够以使负载平衡或递送针对应用的地点偏好（诸如可能已经由用户或管理员输入）的方式来完成。将负载与跨集群中服务器的平均负载和因子Q相比较的机制允许应用的垂直缩放（vertical scaling）以按需递送专用服务器。也就是说，在应用正占据显著量的当前服务器资源的地方，可以做出确定以将其它应用从该服务器移开到不同服务器，而不是做出确定以将该应用从该服务器移开，并且从而允许该应用增加其在当前服务器上的资源。

4. 实时迁移

如上所讨论的实时迁移通过一旦实时迁移已经被发起就控制复制，并且通过在由协议处理机的迁移期间处理请求来受到支持。

5. 时间点还原特征的交互式控制—这由用户接口支持，其允许用户选择文件系统可以被还原到的时间点。这对于电子邮件、数据库和文件可以是特别有用的，以支持在不同时候的快照、回滚和浏览。这提供了对用户错误的防护，特别是当用户在应用层级删除了他们并不想要删除的某物时。尽管删除可以是有效的，但是还原所删项的早前快照以用于在接口处呈现给用户将会是可能的。

6. 水平可缩放性

上文所描述的本发明的实施例的显著优点是自集群添加或移除服务器以增大或减小其整个容量的能力。例如，集群可以通过移动一个服务器的所有站点而被管理，以便例如在用于在升级或离线过程之前迁移应用的受管理的复制过程的情况下来将其升级或使其离线。应当期望的是，通过使得用于应用的领导者服务器基于发出二进制值以会聚于关于谁将会是最佳主设备的全局状态共识的当前主设备消息而做出关于新的主设备的决定，这可以由集群基本上自主地管理。因而，如果检测到新服务器或服务器的移除发生，那么领导者服务器可以自主地承担在新形成的集群（其现在可以包括较多或较少的服务器）的上下文中指定新的主设备的任务。是在该上下文中，现有集群可以是一个服务器的集群，在附加的服务器可以被添加到该集群中的意义上。

所描述的机制中支持这点的特别有用的点在于避免过早的行动—对于集群而言为新的服务器仅仅在它们已经接收到关于整个系统的充足信息之后才做任何事，以做出适当的决定。负载平衡机制有助于允许新服务器使负载移动到它们，因为在添加了新服务器（在它们支持任何文件系统之前）时，全局平均负载水平降低，使得将负载中的一些迁移到新服务器的决定可以自主地实现。

上文所描述的本发明的实施例以以下方式解决冗余问题：

·对应用状态的所有改变被异步地复制到系统中的可配置数量的其它服务器。在检测对应用数据的改变的可配置秒数内拍下每个应用的数据的时间点快照，并且这些快照之间的差别被复制在服务器之间。这允许应用在系统检测到组件、服务器、网络设备或甚至整个数据中心的故障的情况下从非常新近的数据拷贝中自动恢复。由于不存在对共享的存储的依赖，因此无需定额、围栏或STONITH设置。

上文所描述的本发明的实施例以以下方式解决负载平衡问题：

·由应用所引起的负载连续地由系统测量并且使用在分布式决策过程中以发起应用在服务器之间的无缝实时迁移。例如，如果服务器A正托管应用{1,2,3}并且服务器B正托管应用{4,5,6}，并且应用1和2二者都经历负载中的尖峰，而其余是静寂（quiescent）的，则系统可以推选实时迁移2到服务器B以用于平衡的配置A → {1, 3}, B → {2, 4, 5, 6}。

在上文所描述的实施例中，“无缝”实时迁移是其中通过对应用的飞行中的请求而发生在旧的主设备上的应用的文件系统上的所有修改都在最终快照被拍下并且复制到新的主设备之前完成的一种迁移，使得当文件系统被安装在新的主设备上时，从来没有应用代码或客户端能够分辨发生了实时迁移，并且没有数据丢失。