最小化备份系统故障后重新同步时间的系统与方法

摘要

提供了在基于设备的业务保持体系结构中用于最小化停机时间的系统。该系统包括至少一个主数据存储器和至少一台主机。该系统包括拦截代理，其拦截主机数据请求并收集与所拦截数据请求关联的信息。而且，还提供了至少一个与主机通信并与远程备份站点通信的业务保持设备。该设备从拦截代理接收与所拦截数据请求关联的信息。此外，本地高速缓存包括在业务保持设备中。本地高速缓存根据所接收的信息维护主数据存储器的拷贝。此外，还通过业务保持设备向远程站点提供所拦截的数据请求，其中远程站点维护主数据存储器的备份。

说明书

技术领域

本公开内容描述了这样一种发明，它使用小的固定大小的存储器和/或磁盘空间来在业务保持体系结构中一个或多个备份系统组件故障后最小化重新同步时间。

背景技术

在信息时代，保持数据始终在线变得极为重要。业务保持(BC)和快速数据恢复的需求是急迫的和公认的。对这种问题的一种解决方案是远程数据复制(或远程镜像)。远程镜像可避免或降低站点级灾难中的数据丢失。它还有可能通过在远程站点提供热备用主机和应用并且在主站点遇到故障时将客户导向该远程站点来保证出现站点级灾难时的连续数据访问。远程数据复制有两种方式：同步和异步。由于只有数据成功写入本地站点和远程站点后调用应用的写才认为完成，因此只有同步远程镜像才能避免站点级灾难中的数据丢失。但是，这对应用有性能损害。在异步远程镜像中，写到本地站点后写就认为完成了。随后，更新也发送到远程站点。因此，在站点级灾难中，如果有些数据要发送到远程站点但还未发出去，则将会有数据丢失。但是，基于设备的远程镜像体系结构正在流行，因为它具有异步镜像的性能和差不多同步镜像的保护。

在这种体系结构中，数据被运行在主站点的应用存储并访问。主机定义成在站点中共同为应用的所有I/O请求服务的主机的集合。这些主机的每一个上面都安装了拦截代理。如图1所示，这些拦截代理收集并向运行在设备中的中间代理报告所有更新。设备可以连接到本地网络(如LAN)，或者甚至可以到几英里以外(如WAN)。中间代理的责任是从主站点中的所有拦截代理接收所有更新、将它们暂时保存为本地永久日志，然后周期性地发送到备份代理。备份代理运行在远程站点上。它通过在由中间代理发送更新时并按照中间代理发送的更新保持其最新来维护主站点数据的拷贝。这种体系结构中的备份系统组件指设备和远程备份主机。

由于设备靠近主站点，因此主站点与设备之间的复制可以同步进行，而不会向应用增加显著的性能损害。设备与远程站点之间的复制可以异步进行。中间代理首先将从拦截代理收到的请求记入永久日志。只要请求在主站点上成功进行并记入中间代理的永久日志中，应用请求就可以返回。在后台，中间代理处理永久日志，并在将它们发送到远程站点的备份代理之前将多条更新批处理成大消息。这显著提高了网络利用率，并因而降低了总的复制成本。总的体系结构结合了同步和异步镜像的优点，而没有增加显著的缺陷。几个制造商已经建立了具有这种体系结构的系统[5，3]。在这种体系结构下，中间代理的永久日志和远程备份站点的二级数据拷贝构成了主站点数据拷贝的完整复制。

应当指出，如果主站点的灾难不影响设备，则这种复制解决方案不丢失数据。如果设备在几英里远的MAN上，则这是最可能的情况。但是，如果主站点和设备同时面临灾难，则由于远程站点只是异步更新而且有可能遗漏某些更新，因此有些数据会丢失。在最坏的情况下，所遗漏的更新量等于设备永久日志中的更新量。这使得该体系结构的可信度比传统同步镜像的可信度要弱。但是，这种体系结构覆盖了故障错误情况，比同步镜像具有更多显著的成本和性能优势。最近的领域研究显示只有3％导致数据损失和系统停机的故障情况是由站点级灾难造成的[2]。因此，基于设备的体系结构对97％的故障情况都工作得很好，甚至包括一部分不涉及给定设备的站点灾难。因而，它是支持有效远程镜像有吸引力的选择。

给出这种体系结构，主机站点的故障恢复是直接的。每个人都可以简单地切换到远程站点。远程站点在为任何新请求服务之前必须等待所有未处理完的日志请求在设备中被处理。但是，面对设备故障，永久日志可能不再可用，因而有一部分二级数据拷贝丢失了。除非使用某些专门技术，否则从设备故障恢复是极其昂贵的。在最坏的情况下，存储在主站点的全部数据都必须拷贝到远程站点。在特定情况下，比较主站点和数据与远程站点的数据而且只重新同步两者之间不同的数据而不进行完全的数据拷贝可能成本较小。但是，比较本身就需要读出两站点的整个数据集。如果数据块的校验和用于识别差异，则两站点都必须计算校验和。很清楚，这不仅在数据重新同步中在网络带宽方面有显著的成本，而且它可能会降低主机应用的性能很长一段时间。此外，如果主站点没有离线，则它有可能将整个系统置入无保护模式很长一段时间。类似地，如果远程备份站点遇到故障，并且从三级备份(可能是磁带库)恢复，那么最坏的情况将是比较全部的主站点数据与备份站点数据并重新同步该差异。假定即使在备份系统组件故障后也总有可能过时的备份拷贝可用。这对设备故障来说确实如此，因为备份站点的数据拷贝是过时的备份拷贝。对于远程备份站点故障，假定总是有可用于将备份站点恢复到特定时间点的磁带备份。为了使这种二级数据拷贝，也称为备份数据拷贝，进入等同于主数据的状态，从备份时间点开始在主站点进行的所有更新都要重新同步。所需要的是解决设备和/或远程备份站点故障后最小化该重新同步时间问题的解决方案。

在如设备和备份站点故障的备份系统组件故障后，可能的长重新同步时间是有问题的。长重新同步时间是由于主系统不能跟踪当一个或多个备份系统组件故障时什么数据必须重新同步的事实。最简单、通常也最慢的重新同步方式是无一遗漏地比较主和备份站点的整个数据集并将差异加到备份。如果主站点的数据量很大，则这个过程极慢。如果主机知道故障后什么数据必须重新同步，则只有那些数据集需要从主拷贝恢复到备份拷贝。例如，在设备故障的情况下，需要恢复的数据仅仅是中间代理永久日志中的数据。如果远程站点故障，也是类似。远程主机恢复处理可以首先将远程站点恢复到最后一次的磁带备份。然后，只有从该磁带备份开始后进行的更新必须从主站点恢复。如果这种差异可以容易地识别，则备份系统组件的恢复不会很昂贵。通常，依赖于配置场景，两个数据拷贝版本之间的差异可以从只需几秒的更新到好几小时甚至好几天的更新。

跟踪这种主数据拷贝与远程站点和设备上数据之间差异的一种途径是通过使用主和远程站点上的时间点快照能力。其思想是让主机周期性地拍摄快照。远程站点也保持快照，但滞后于更新。当设备故障时，远程主机可用找出它们接收到全部更新的最近的快照。从该快照开始所进行的全部变化构成当设备死机时其永久日志中变化的超集。只要主机有识别从远程站点所指示快照开始变化的有效方式，它就足以只发送那些变化给复制，以确保在远程站点的完全复制。类似地，如果远程站点故障，则它首先恢复到最后一次的磁带备份。假定最后一次的磁带备份对应于某个快照N，则需要恢复的数据是从快照N开始进行的变化集。主机可以利用快照信息来识别变化的数据，从而只恢复一数据子集，而不是整卷的文件系统。

尽管以上方法显著减少了数据的重新同步时间，但它需要主机具有适当的快照能力，从而造成系统软件依赖性。远程备份也需要知道快照并能够利用该特征。而且，它需要主站点对快照的调度，以方便当备份组件故障时备份站点或设备的快速重新同步。即使有快照，主站点也必须能够很快识别出从给定快照开始进行的变化集，其中该快照是备份最新的。为便于如此，软件应当避免完全的快照元数据扫描，因为这对主机应用来说是非常昂贵的，而且性能降低很多。但是，避免快照元数据扫描的方案常常对主机的数据处理引入性能损害。在有些情况下，依赖于软件的复杂程度，主机应用可能必须停下来等待扫描完成。网络设备文件管理器[8]对此类故障情况利用快照。但是，这种体系结构依赖于用在主和备份站点的软件或设备的一致性。

通过以除快照以外的途径跟踪对主站点某些日志中更新，有几种方法已被用于减轻以上问题。这类日志中的记录指示哪些数据变化了，因此当备份系统组件要恢复时，只有这些数据需要重新同步。但是，即使这些解决方案也有问题，因为它们不能利用受限的资源很好工作。一旦分配给日志的空间满了，这些算法就求助于强迫所有应用停止产生更多更新(从而造成停机)，或者它们停止累积日志从而如果主站点在无一遗漏地比较主和备份版本这又长又痛苦的过程中遇到故障则面临系统数据丢失。

因此，还是需要一种能处理各种备份系统组件故障的有效的重新同步方法。

发明内容

根据本发明，提供了在基于设备的业务保持体系结构中最小化备份系统组件故障后数据重新同步时间的系统。该系统包括至少一个主数据存储器。此外，该系统还包括至少一台主机，其中该主机能访问存储在主数据存储器上的数据。而且，该系统还包括在至少一台主机上用于拦截数据请求并收集关于所拦截数据请求的信息的拦截代理，其中所拦截数据请求包括数据读请求和数据写请求。该系统还包括在至少一台主机上用于维护所收集信息的摘要日志。此外，该系统还包括至少一个业务保持设备，与主机上的拦截代理通信并与远程备份站点通信，其中该业务保持设备从拦截代理接收与所拦截数据请求关联的信息。该系统还包括至少一个业务保持设备，与拦截代理通信并与远程备份站点通信，其中该业务保持设备从拦截代理接收所收集的信息。此外，该系统还包括本地高速缓存，其包括在该业务保持设备中，其中该高速缓存维护所收集的数据。而且该系统还包括远程备份站点，向远程备份站点提供所收集的数据，其中远程备份站点维护位于主数据存储器的数据的二级拷贝。摘要日志用于在业务保持设备和远程备份站点组合故障的情况下最小化重新同步时间。

附图说明

图1示出了基于设备的业务保持体系结构。

图2说明了写摘要日志的方法。

图3说明了压缩摘要日志的方法。

图4说明了维护摘要日志的方法。

图5说明了响应摘要日志达到其容量而压缩摘要日志的方法。

具体实施方式

本发明主要作为在基于设备的业务保持体系结构中用于利用摘要日志最小化备份系统故障后重新同步时间的系统与方法来描述。在以下描述中，为了解释，阐明了各种具体细节，以便提供对本发明的彻底理解。但是，对本领域技术人员来说，很显然本发明可以实现为没有这些具体细节。

本领域技术人员应当认识到包括CPU、存储器、I/O、程序存储器、连接总线及其它适当组件的装置，如数据处理系统，可以被编程或设计成方便本发明的实现。这种系统包括用于执行本发明操作的适当程序装置。

如和数据处理系统一起使用的预记录磁盘或其它类似的计算机程序产品的一款产品可以包括：在其上进行记录的存储介质和程序装置，用于引导数据处理系统以方便本发明方法的实现。这类装置和产品也属于本发明的主旨和范围。

图1示出了基于设备的业务保持体系结构10。在这种体系结构中，数据被运行在主站点12上的应用存储并访问。主站点12包括一台或多台主机14，其中主机14为应用进行的所有I/O请求服务。每台主机14都包括拦截代理16。拦截代理16收集与应用所进行所有数据请求(读和写)关联的统计数据和模式。此外，拦截代理16还收集与所有数据请求关联的标识与描述信息。而且，主机14还包括用于维护拦截代理16所收集的统计数据、模式、标识与描述信息的摘要日志15。此外，主机14还包括数据访问代理17。主站点12连接到LAN/MAN18。

体系结构10还包括网络设备20。网络设备20连接到LAN/MAN18。网络设备20包括中间代理22。拦截代理16向中间代理22提供收集到的所有统计数据和访问模式。而且，拦截代理16还向中间代理22提供所有的数据请求和所有的数据更新。此外，网络设备20还包括本地高速缓存23。

体系结构10还包括远程站点24。在一种典型实施方式中，远程站点通过WAN 26附属于网络设备20。远程站点24包括备份代理28。备份代理28负责通过分析与施加通过中间代理22接收到的更新维护主站点数据的二级拷贝。在一种可选实施方式中，备份代理28可以与中间代理在网络设备20共存。

智能拦截代理

在体系结构10中，拦截代理16有两项工作：(1)向中间代理22发送更新；及(2)捕获I/O错误并以对请求应用透明的方式将请求重新引向中间代理22。智能拦截代理100包括拦截代理16的全部功能，而且还有收集关于出现在主机14上I/O的访问模式和统计信息的附加功能。统计信息包括什么数据被访问(可以是文件名或块地址)、谁在读或写数据、隔多久数据被访问或修改、什么时候数据被访问等。所读出数据的内容不转发到智能中间代理102，这类信息不需要为每次读操作发送。相反，多条记录可以与为数据复制发送的更新批处理并绑在一起。在一种典型实施方式中，分配一临时的存储器内缓冲区用于批处理。如果很长一段时间都没有更新请求，则不管什么时候缓冲区满，智能拦截代理100都将所记录的信息传递到智能中间代理102。在任何需要的时候，智能中间代理102还执行一些统计处理，以降低要发送到智能中间代理102的数据量。由于智能中间代理102只是利用这类信息决定哪些数据高速缓存和预取是有用的，因此发送统计数据时小的延迟应当不会引入显著的影响。

在优选实施方式中，关于向智能中间代理102报告什么信息，智能拦截代理100是系统管理员可配置的。而且，智能拦截代理100还可以配置成在自动将请求重新引向智能中间代理102之前等待管理员确定故障的准确性质。这种配置将依赖组织利用体系结构92的需求而变。

智能中间代理

在体系结构10中，中间代理22具有以下任务：(1)从拦截代理16接收更新并将它们加到它维护的更新日志中；(2)将更新异步发送到备份代理28；及(3)为所有由拦截代理16重新引向它的I/O请求服务，其中这种重新引向是作为主站点12数据不可用的结果(例如，主站点12故障)。

为了最小化主站点92数据不可用期间的性能降低，增加了由智能中间代理102维护的“热高速缓存”的概念。在主站点12的主机14没有可用数据的任何时候，使用由智能中间代理102维护的“热数据”，而且联系智能中间代理102以检索最新的数据拷贝。智能中间代理102从智能拦截代理100接收访问模式和统计数据。基于该信息，智能中间代理102就哪些数据集有可能在最近需要作出智能猜想。在优选实施方式中，提供了到智能中间代理102的接口，这种接口可以被系统管理员用于指示智能中间代理102考虑特定数据集为热的。许多不同标准可用于确定一条数据是否是热的。接下来将解释“热数据”的概念。

热数据

有各种标准用于将数据识别为“热的”。以下是多种可用于确定数据文件“热度”的此类标准：

●  文件用得越多，它就可能越重要。

●  利用一特定文件的用户数越大，那么如果数据不可用则受影响的用户集越大。

●  在有些设置中，文件的访问时间可以决定其重要性。例如，如果一个文件通常在晚上或周末被访问，则称其不如在工作日开始时被访问的文件关键。

●  某些众所周知的可执行文件和系统文件是重要的，因为它们对系统的正确执行是必需的。

●    系统及用户配置文件可能是用户登录他们的系统所必需的。如果它们驻留在所讨论的存储器上，则这些文件可以认为是“热的”。

●  管理员也可以配置某些目录为重要的，因为它们可能属于运行在主站点92上的重要应用。

●  某些用户的文件(如CEO的邮件)可以认为比别人的重要。

●  如果一个人在休假，那么很可能在他/她离开的这段时间内该用户的文件不应当认为是热的。如果需要，这些及其它基于现实世界知识的标准可以由管理员指定。

●  小文件在高速缓存过程中可以给予一些优先考虑。

●  元数据信息保持在本地高速缓存94中通常是非常有用的，而且可以认为是热的。事实上，为了在主站点92数据不可用期间的效率，智能中间代理102可以本地维护元数据的完全拷贝。

●  文件内容也可以指示文件的“热度”。

●  文件名或其扩展可以指示文件有多重要。例如，foo.c可能比foo.o更重要，因为后者可以由前者重建。众所周知的文件名，如系统日志文件，也可以分配合适的“热度”。

数据块的热度可以类似的方式处理。尽管数据块没有名字，但会有一些众所周知的更重要的数据块。与文件类似，由大量用户或一些重要用户以较高频率使用的数据块可以认为是热的。

高速缓存替换

作为本地高速缓存94的部分，智能中间代理102还决定当本地高速缓存94满时替换高速缓存的什么数据。智能中间代理102可以使用基于访问模式的高速缓存替换策略。如LRU及其后续、LFU和ARC的流行方案可以在不同情况下使用。因为体系结构92什么都没有排除，所以没有指定特定算法。高速缓存遗漏信息和高速缓存替换信息可以由智能备份代理104用于执行智能数据重组，使得对远程站点24的数据访问是有效的。例如，智能中间代理102可以跟踪被替换的高速缓存数据集。在更新数据从智能中间代理102复制到远程站点24的任何时候，此类信息都可以绑在一起发送到智能备份代理104。智能备份代理104可以提取此类信息并执行适当的优化。

智能备份代理

类似于体系结构10中的备份代理28，智能备份代理104负责重演更新请求以重建数据的二级拷贝。此外，智能备份代理104还分析由智能中间代理102发送的访问模式和统计数据(例如，高速缓存遗漏比和替换模式)。基于该分析，它可以执行如数据重组的优化，以便提高在任何时候当智能备份代理104被请求检索某些数据时的I/O性能。数据重组的一个例子是复制频繁访问的数据并以某种顺序方式存储它们。如果主站点92故障，则智能备份代理104将所有尚未处理的更新施加到永久存储器，以给予管理员在远程站点24创建最新数据拷贝的能力。

数据访问代理

数据访问代理17充当主站点92数据的客户。它可以向主站点92的存储器读写数据。它用于两个目的。首先，它被智能中间代理102用于从主站点92读取被确定为“热”的数据，并为此决定第二份拷贝应当保留在本地高速缓存94中。其次，在故障后，当主站点92的硬件问题解决以后，智能中间代理102利用数据访问代理17写主站点92在其不可用期间遗漏的数据。尚未处理的数据存储在智能中间代理102日志中并通过由数据访问代理17提供的接口送出。数据访问代理17可位于主站点92上的任何位置，在该位置其具有到主站点92数据的读/写访问。数据访问代理17能够恢复并访问主站点92的所有数据。在一种可选实施方式中，数据访问代理17可以与智能中间代理102在网络设备20上共存。

自动恢复

智能中间代理102帮助将主站点92在故障后带回到最新状态。

任何时候当智能拦截代理100向主站点的存储器的写出现故障时，它就通知智能中间代理102关于该故障和更新请求。智能中间代理102将更新记在其日志中，因此一旦主站点的故障修复，它们就可以向主站点92重演。一般来说，主站点92的存储器将首先从某些备份磁带恢复。然后必须施加所有在该备份时间后发出的更新，以便使主存储器完全处于最新。实现其的一种途径是故障后在远程站点24创建最近的磁带备份，并利用该磁带进行主存储器恢复。一旦恢复，主存储器就只遗漏了位于智能中间代理102日志中的数据子集。当由系统管理员指示时，智能中间代理102可以通过利用数据访问代理17向主站点92重演这些更新。当主站点进入最新状态时，通知拦截代理100并恢复主站点92的正常运行。

本发明便于在体系结构10中从备份系统组件故障更有效的恢复。通过最小化网络设备20和/或远程站点24的重新同步时间，使恢复更加有效。

主机14的摘要日志15用于维护从某个过去的时间点开始对存储在主机14的数据所进行的改变集。有界存储器和有界磁盘空间用于摘要日志。尽管摘要日志15不包含改变内容本身，但它可以在网络设备20和/或远程站点24故障的情况下用于推断要恢复的数据。

图2说明了写摘要日志15的方法40。在块42，方法40开始。

在块44，拦截代理16识别对主机14进行的数据更新请求，并收集与该数据更新请求相关的信息。

在块46，确定要更新的数据是块还是文件。如果是文件，则在块48文件更新的记录由拦截代理16在摘要日志15中创建。如果是块，则在块50块更新的记录由拦截代理16在摘要日志15中创建。

在块52，拦截代理16向中间代理22提供在块44收集的信息。

在块54，方法40结束。

摘要日志记录包含逻辑更新请求，而不是修改后的数据内容。例如，对于向文件区的写请求，记录可以简单地是所更新文件区的文件名、文件偏移和长度。对于磁盘块更新，它可以是所更新磁盘块的磁盘ID、磁盘地址和个数。

为了避免主机14的显著成本，摘要日志15的大小应当维持在相对小的值，例如，几十兆字节的存储器和几亿字节的磁盘空间。当备份系统组件故障时，摘要日志15可用于确定哪些数据更新了并需要在主机14和远程站点24之间重新同步。摘要日志15总是能提供需要重新同步的数据的正确超集。即使在更新量非常大的情况下，多余重新同步的量也保持在最小。当必须重新同步的改变量显著小于数据全集时，所公开的发明提供最大的益处。实际上，情况几乎总是这样。

图3说明了压缩摘要日志15的方法56。在块58，方法56开始。

在块60，拦截代理16向摘要日志15提供数据更新信息。通常，当摘要日志15中有空余空间时，可以记录准确的改变信息。当这种信息在重新同步过程中使用时，重新同步时间被认为是最优的，因为系统确切知道什么数据需要恢复。

在块62，确定摘要日志15是否达到其容量。如果没有，则在块64在摘要日志15进行更新请求的记录。

返回块62。如果是，则在块66依赖于要复制的数据类型(例如，文件或磁盘块)，数据类型专用的信息用于创建对数据改变的“摘要”，而不是总保持确切的改变信息。在这里，创建摘要的处理称为压缩。关于什么数据进行了改变，这种摘要可能不太精确，但该信息足以重新同步数据。为了确保即使在进行了压缩的情况下重新同步时间也仍然保持接近于最优，包括了一组压缩算法，及关于如何在不同的系统条件下选择适当压缩算法的策略。

在块70，方法56结束。

通常，摘要日志15分配的尺寸越大，在其中存储的改变信息越精确。因此，摘要日志15的大边界将导致比小边界小的重新同步时间。总的来说，本发明在正常系统运行时间和组件故障与恢复模式期间都对主机14强加了非常小的性能和资源开销。它可以适用多种故障情况，而对于给定的系统资源具有非常接近最优的数据重新同步时间。

为了从设备故障中恢复，只要摘要日志包含对应于设备永久日志中所有更新的记录，就可以通过简单地基于摘要日志从主机站点读最新的数据拷贝并将它们发送到新安装的设备来从设备故障中恢复。这意味着摘要日志不需要无限期地保持所有更新记录。为了使重新同步工作良好，只需要保持非常有限的改变历史。此外，由于摘要日志驻留在主机上，因此保持摘要日志小而有界以避免主机资源的过多使用是很重要的。

图4说明了维护摘要日志15的方法72。通过当中间代理22发送远程站点24已接收到更新记录拷贝的确认时除去更新记录，摘要日志15可以保持有界。由于备份代理28已接收到更新记录，因此中间代理永久日志中的对应记录可以除去。在块74，方法72开始。

在块76，识别在主机14接收的更新请求。

在块78，时间戳附加到识别出的更新请求。附加时间戳是为便于识别哪些记录可以从摘要日志15中除去。

在块80，在摘要日志15创建识别出的更新请求的记录。

在块82，拦截代理16向中间代理22提供更新请求的记录。中间代理22将以时间顺序处理所有来自拦截代理16的请求。因而，无论什么时候当一组请求已保存在远程站点24上时，中间代理22就可以通知拦截代理16已保存在远程站点24上的最近更新的时间戳。然后，拦截代理16可以从摘要日志15除去所有具有小于或等于该时间戳的记录，减小摘要日志15的大小。

在块84，中间代理22向备份代理28提供从拦截代理16接收到的识别出的更新请求记录。

在块86，通过与远程站点24的通信，中间代理22通过备份代理28向拦截代理16提供关于保存在远程站点24(例如，发送到磁带、磁盘等)的最近更新请求的时间戳的信息。

在块88，拦截代理16除去所有时间戳在最近更新时间戳之前的记录。

在块90，方法72结束。

方法72没有覆盖当由于大量未保存在远程站点24上的更新而使摘要日志15增长超出期望大小的情况。在这种情况下，中间代理22上的永久日志也会相应地大。这可能发生在多种场景。例如，远程站点24和网络设备20之间的WAN 26可能太慢或断开，或者远程站点的请求处理可能太慢，导致更新累积在网络设备20的永久日志中。如果在主站点14有异常高的更新速率，这也有可能发生。为了处理这种情况，提供了一种算法，以摘要日志15决不会增长越界的方式将多条改变描述压缩成高级改变摘要。这种压缩策略没有丢失关于在故障恢复中必须施加的任何更新的信息，但它可能导致长于最优的重新同步时间。该算法工作在总是试图最小化由于这种压缩造成的额外重新同步时间的方式。可用于维持有界摘要日志大小同时又能优化最小重新同步时间的可用压缩算法的类型将在下面进一步解释。

图5说明了响应摘要日志15达到其容量而压缩摘要日志的方法92。

在块94，方法92开始。

在块96，识别对主机14的数据更新请求。

在块98，确定摘要日志15存储器缓冲区部分是否已达到其容量。如果是，则在块100利用压缩算法，该存储器缓冲区部分中的数据被标识以用于压缩。在块102，在块100标识出的数据被压缩。

在块104，在摘要日志15创建所识别出的更新记录请求。

在块106，拦截代理16向中间代理22提供更新请求的记录。中间代理22将以时间顺序处理所有来自拦截代理16的请求。因而，无论什么时候当一组请求已保存在远程站点24上时，中间代理22就可以通知拦截代理16已保存在远程站点24上的最近更新的时间戳。然后，拦截代理16可以从摘要日志15除去所有具有小于或等于该时间戳的记录，减小摘要日志15的大小。

在块108，中间代理22向备份代理28提供从拦截代理16接收到的识别出的更新请求的记录。

在块110，通过与远程站点24的通信，中间代理22通过备份代理28向拦截代理16提供关于保存在远程站点24(例如，发送到磁带、磁盘等)的最近更新请求的时间戳的信息。

在块112，拦截代理16除去所有时间戳在最近更新时间戳之前的记录。

在块114，方法92结束。

为了处理远程备份站点故障及并发的远程备份和设备故障，可以对以上方法稍作修改。

当远程站点24故障时，假定它可以首先恢复到最后一次的磁带备份。其余必须从主站点14恢复的数据是主数据拷贝与最后一次磁带备份之间的差异。由于通常只有全数据集的一小部分需要在长距离的网络上重新同步，因此在网络资源方面，这应当不是很昂贵。为了方便这种有效的恢复，摘要日志15必须包含从远程站点24该磁带备份开始所发生的全部更新的摘要记录。这可以通过让备份代理28在其开始磁带备份的任何时候向中间代理22发送某种信息来完成。中间代理22又将该信息转发到拦截代理16。该信息指示当磁带备份开始时最后一次保存的更新请求的时间戳。此时，所有具有小或相同时间戳的记录可以从摘要日志15中除去。因而，摘要日志15包含从中间代理22故障恢复所需摘要记录的超集。即使网络设备20和远程站点24同时故障，摘要日志15也可以用于识别需要重新同步的数据集，从而显著降低恢复成本。

中间代理22还可以让拦截代理16不时地知道保存在远程站点24的最近更新的时间戳。如果网络设备20故障，则拦截代理16不必处理所有的摘要日志记录。相反，它只需要重新同步所有具有比中间代理22所发送最近时间戳大的时间戳的记录。以这种方式，同一摘要日志15可以有效地用于恢复网络设备20和远程站点24故障。通常，对于拦截代理16，只要摘要日志15中有空余空间，就有可能无限期地保存比需要多的改变记录，而且对于拦截代理16，有一种容易的途径算出对于给定的故障情况需要使用什么记录。例如，如果有足够的日志空间保存从最后N个磁带备份开始的改变描述，那么即使N-1个磁带备份不可用，系统也能恢复数据，而不需要在主和备份数据拷贝之间进行无一遗漏的扫描和比较。

由于部分摘要日志15是主机14的主存储器，因此如果主机14崩溃，则一部分摘要日志15可能在主机14重启后丢失。由于摘要日志15中的记录通常只保存特定的一段时间而且只有当备份系统组件故障时才使用，因此这可能不是个显著的问题。如果在那段时间内没有这种故障，则不需要旧的摘要日志记录。如果期望即使面临主机14故障时也能保存摘要日志15的信息，则中间代理22可以在自己的永久存储器上镜像摘要日志15。以这种方式，如果主机14崩溃，则可以通过联系中间代理22很快地重新加载摘要日志15。由中间代理22创建摘要日志15的拷贝并不昂贵，因为它可以在写永久日志时进行，或者作为处理永久日志的背景处理进行。

用于有界摘要日志的压缩算法

摘要日志15的压缩是通过将摘要日志15中的大量数据更新记录概括成少量高级摘要记录以降低摘要日志15中的存储空间需求实现的。压缩可能会增加重新同步时间，但它以保持重新同步时间尽可能接近最优的方式工作。压缩只有当摘要日志15达到其容量时才被触发。在正常情况下，只要摘要日志15合理地大，压缩将不会被触发。

在这里，典型压缩算法是基于记录的局部性(时间和空间)与概括的组合开发的。

数据访问一般呈现某种时间和空间局部性。例如，文件系统的公用在文件系统层次中呈现更新的局部性。因而，在任何小的时间段内，从几小时到几天，在其下面进行更新的不同目录数一般小于目录总数。类似地，块设备访问也能看到一定程度的数据局部性，尽管其局部性不象在文件系统中那么明显。

当摘要日志15达到其容量时，数据集中任意数量的更新都可以通过将大量改变描述打包成少量记录而不丢失任何改变信息来概括。例如，文件系统层次中的一组更新可以通过挑选覆盖所有更新文件和目录的少量祖先来概括。在重新同步中，只有那些子树需要重新同步。由于该子树显著小于整个文件系统，因此用于重新同步的比较甚至数据拷贝将很快。对块设备访问也类似，更新的块数可以在包括范围内合计。

应当指出，尽管不会由于压缩而丢失改变，但这种压缩会导致改变描述精度的损失。此外，如果选择了合适的压缩策略，则改变描述精度仍然是很高的，因而重新同步时间将不会显著偏离最优时间。

为了方便摘要日志15的有效压缩，设计出了摘要日志15合适的数据结构以跟踪数据更新描述记录，因此压缩可以对主机14数据处理最小影响地有效执行。而且，包括了一组确定如何在不同情况下压缩数据的压缩策略。适当压缩策略的选择是基于系统条件。以下，文件系统数据作为例子用来显示如何解决这些问题。如下面所解释的，这些技术也可以扩展或修改，以支持磁盘块数据。

数据结构

如前所述，摘要日志15包含存储器缓冲区和一些磁盘空间。为方便讨论，假定摘要日志磁盘部分的大小总是存储器缓冲区的倍数。存储器缓冲区包含最近的改变描述。拦截代理16总是首先更新存储器缓冲区。如果存储器中没有剩下任何空间了，则摘要日志15存储器缓冲区送到磁盘。如果存储器缓冲区分配在连续存储器区域之外，则需要大的连续写将其写到磁盘。这些存储器缓冲区中每一个都称为摘要日志15的一块。为了方便文件系统数据的快速压缩，使用可以有效表示节点层次的数据结构。每个节点对应于一个目录或文件。从概念上讲，无论何时报告了更新，如果还不存在在数据结构中代表该路径的节点就创建它，从而将更新记录到文件系统。由于它主要是树的查找与更新，因此存储器中的这种操作并不昂贵。如果现有节点已经覆盖了该更新，则数据结构不变。例如，如果一目录节点已经指示其孩子可能是更新过的而且又收到了与其孩子关联的另一更新，则什么都不做，因为该孩子已经标识为更新过的。

以下数据结构表示用在优选实施方式中：

文件节点—这种节点包含表示其所代表文件的名字或常规表达。可使用标志指示更新是关于文件元数据还是文件内容。对于文件内容，它可以包含在所更新区域文件偏移和长度方面已更新的文件区域，及文件总的大小；

目录节点—这种节点包含表示其所代表目录的名字或常规表达。它有一称为深度的域，指示在以该目录为根的文件系统子树中更新的最大深度。因而，如果文件重命名并放置在该目录，则深度为0，因为只有目录列表更新了。如果文件在目录下创建，则深度为1，因为除目录列表外，低一级的文件也更新了。深度为-1意味着这个节点没有更新，但它是更新节点的祖先。因而，这种节点仅仅是帮助指定到更新节点的路径。另一方面，“无限”深度(在这里使用“-2”)意味着这个目录下的整个子树都可能是更新过的，因而在备份系统组件故障的情况下备份可能需要重新同步整个子树。可使用标志指示目录更新是关于元数据还是目录内容。

为了方便摘要记录15的快速除去，在每一块中所记录的最后一次更新的时间戳都被跟踪，因此无论何时当拦截代理16从中间代理22接收到关于要除去的记录的时间戳信息时，它都可以简单地检查那一块记录的最后时间戳。如果该时间戳小于从中间代理22接收到的时间戳，则那一块的所有记录都可以除去。如果块存储在本地文件中，则文件可以除去。一旦摘要日志15接近其所分配的空间，它就可以通过从最旧的块开始压缩，并通过应用下面所讨论各种压缩策略中的一种或多种压缩最旧的N块。N是可配置参数。一旦压缩了，一些摘要日志15的空间就空出来了。重复相同的处理，直到空余空间的量达到某个预定的阈值。压缩仍然保留时间戳信息，因此即使在合并后，当需要时块也可以除去。最旧的块被首先压缩，因为当数据在远程站点24保存或备份时最旧的记录首先被除去。

压缩策略

为了限定摘要日志15的大小，定义了一组压缩策略。策略对一个或多个给定的块起作用并截断它们，因此在摘要日志15中有些指定量的空间可以空出来。策略包括：

程度压缩—无论何时当文件区域更新时，更新的文件偏移和长度适当地加到文件节点。这些文件区域记录可以合并以释放一些空间。在第一文件区域结束与第二区域开始之间有最少差异的记录合并。所有文件区域也可以除去，暗示整个文件都更新了。

名字压缩—文件和目录的名字可以通过利用某种形式的常规表示来压缩。例如，“foolongname”可以表示为“fo^*”。

兄弟压缩—名字压缩策略还可用于兄弟文件或目录，以减少节点数。因而当多个目录节点合并时，兄弟中的最大深度值用于新节点。

深度增加—目录的深度值可以增加，以释放所有将被新深度值覆盖的节点。

如名字压缩、深度增加和程度压缩的策略可以应用到单个节点，而兄弟压缩用于一组节点。很明显，在最坏的情况下，压缩的结果是树中一个节点，即表示文件系统根的节点。这意味着没有关于文件系统更新的明确信息可用，因此，重新同步时间可能会相当大。这显示我们的算法实际上是受摘要日志15是否至少有保留根节点所需空间(几个字节)那么大限制的。在实际中给定数据局部性的情况下，这是不太可能的。

选择正确的策略

为了释放摘要日志15中的空间，需要正确的策略集以最少量增加重新同步时间但释放期望空间量的方式应用到正确的节点集。令期望释放的空间量为M，层次中的节点数为N，考虑的不同策略数为S。对于层次中的每个节点及可以应用到该节点的每种策略，计算Δm_i，i，这是对节点i应用策略j所释放的空间量。还可以计算Δt_i，j，这是对节点i应用策略j所增加的重新同步时间量。因而，问题可以如下公式化：

最小化 $>\underset{}{}>>\Delta t>>i>,>j>\; >·>>x>>i>,>j>\; >$>

服从 $>\underset{}{}>>\Delta m>>i>,>j>\; >·>>x>>i>,>j>\; >\ge >M>$>

x_i，j∈{0，1}；i＝1，2，...，N；j＝1，2，...，

以上问题公式表明必须选择一组(节点、策略)元组，使总的重新同步时间增长最小化，而释放的存储器大小等于M。这是0-1Knapsack问题的最小化变量。尽管这种问题已知是NP难解的，但还是有众所周知的技术来解决这种问题，象分支定界技术、动态编程技术、状态空间放宽与预处理。众所周知非常快地产生几乎最优解决方案的多项式时间算法也可以使用。最简单的次优解决方案是将问题映射成连续Knapsack问题并利用贪心算法求解，在大多数情况下都可以得到几乎最优的解决方案。贪心算法对受限空间工作得很好。

依赖于数据结构所使用的存储器分配算法，Δm_i，j不应该很难计算。精确计算Δt_i，j需要比存储在数据结构中是信息更多的信息。在程度压缩的情况下，如果文件总的大小已知且其重新同步N字节文件数据所用的时间估计可用，则Δt_i，j可以估计。当对于一目录节点深度增加时，知道增加多少重新同步时间是有帮助的。这需要估计有多少额外的数据必须重新同步。这常常意味着需要文件和目录大小信息。获得这种信息的一种途径是访问压缩节点下文件和目录的元数据。另一种途径是从远程站点24收集元数据信息，以避免对主机14性能的影响。远程站点24的信息可能不如主机14的信息准确，因为有些请求可能还没有从中间代理22同步到远程站点24。但是，因为只需要估计，所以这种方法是合理的。这种信息收集可以作为连续的背景处理或当需要压缩时进行。如果在需要压缩时进行，则主机14的处理可能有一小会儿会受到影响。但是，由于压缩很少有，因此，这不是显著的缺点。可选地，通过放弃重新同步时间的接近最优性质，还有可能根本不收集元数据信息。而且，一些单凭经验的“猜想”可用于提供对重新同步时间的估计。例如，可以对目录和文件假定合理的平均大小，以估计重新同步时间。

对于磁盘块，压缩可以类似上述程度压缩的方式实现。代替文件区域，对固定大小的磁盘块起作用。在最坏的情况下，压缩将导致单个磁盘分区。用于跟踪此类磁盘块改变记录的数据结构可以是磁盘ID、磁盘块地址及从该磁盘地址开始改变的块数的组合。

备份系统故障后利用摘要日志重新同步

一旦摘要日志15形成，重新同步就是直接的。如果摘要日志15的记录描述了准确的改变信息，则系统可以基于改变描述简单地从主机14读数据并将其应用到过期的备份拷贝。对于压缩的记录，有两种可能：

(1)系统有可能简单地读摘要日志15的记录所指示的改变。这意味着改变的某个超集可以读写到备份拷贝。如果读出的多余数据量并不显著，则这不是问题；及

(2)另一方面，如果概括的信息会引起重新同步数据量的显著增加，则有可能在数据重新同步之前对由摘要日志15中记录描述的数据进行比较。只有不同的数据才需要写到备份拷贝(例如，远程站点24上)。由于这种比较不是对整个数据集进行，因此比较可以相当快地进行。尽管如此，在实际中，这种比较还是要避免。

这可以多种途径实现，如通过同步远程备份拷贝与主数据并以干净的永久日志开始，或者通过读摘要日志15并获得一组可能是实际变化超集的变化在网络设备20重新创建逻辑上等效的永久日志。

因而，描述了在基于设备的业务保持体系结构中用于利用摘要日志最小化备份系统故障后的重新同步时间的系统和方法。尽管本发明参考具体的典型实施方式进行了描述，但很显然，在不背离本发明更广泛主旨与范围的前提下，可以对这些实施方式进行各种修改与变化。因此，该说明书和附图应该认为是说明性的，而不是限定性的。