将储存库还原到先前状态的方法

摘要

本发明描述的技术用于将储存库返回到前状态。储存库可以是，例如数据库，并且前状态可以是，例如数据库在过去的特定时间点具有的一致状态。当操作者引起的错误通过由已经提交的事务作出的改变引入到数据库中时，本发明描述的技术可以用于通过将数据库返回到在引入错误的事务被提交的时间之前的时间点来从错误恢复。该技术包括产生“物理撤消”信息，以及物理撤消信息与生理撤消和生理重做的联合使用，以有效地将储存库返回到前状态。

权利要求

1.一种将储存库返回到目标前逻辑状态的方法，所述方法包括：接收将所述储存库返回到所述目标前逻辑状态的请求，其中，所述目标前逻辑状态在目标时间点处是所述储存库的一致状态，并且其中，所述目标前逻辑状态在所述储存库的最近一致逻辑状态之前；

响应于所述请求，执行如下步骤：

对持久存储在所述储存库中的数据应用撤消，其中，所述撤消包括将所述数据返回到先前状态所必需的信息，并且其中，所述撤消的应用使得所述数据反映所述先前状态；以及在应用所述撤消之后，应用生理重做，以将所述数据从所述先前状态移动到所述目标前逻辑状态，其中，所述生理重做包括关于如何对所述数据重新执行改变的信息。

2.根据权利要求1所述的方法，其中，

所述应用所述撤消的步骤包括：为多个过程分配撤消记录；以及所述多个过程相对于彼此并行地应用所述撤消记录。

3.根据权利要求1所述的方法，其中，

所述应用所述撤消的步骤使得在所述储存库中的数据块反映在所述目标时间点之前的时间；以及所述应用生理重做的步骤包括：应用所述生理重做，以将在所述储存库中的所述数据在时间上向前移动到所述目标前逻辑状态。

4.根据权利要求3所述的方法，其中，所述撤消是第一类撤消，其中，所述应用生理重做的步骤包括：在应用所述生理重做之后，应用第二类撤消，以从所述数据的至少一些去除由在所述目标时间点时或在所述目标时间点之前还未提交的事务作出的改变。

5.根据权利要求1所述的方法，其中，所述对所述储存库中的所述数据应用撤消的步骤包括：对所述数据的第一集合应用与对应于为其产生所述撤消的特定时间点的门相关的所述撤消；以及对所述数据的第二集合应用与在所述门之前的预期门相关的所述撤消。

6.根据权利要求5所述的方法，进一步包括：为在所述预期门之后作出的一些但不是所有的预期门后第一次更新产生所述撤消；以及除对在所述预期门之后为其产生所述撤消的数据作出的更新之外，为在对应于所述特定时间点的所述门之后作出的所有门后第一次更新产生所述撤消。

7.根据权利要求6所述的方法，进一步包括：当所述预期门后第一次更新被执行时，根据资源的可用性确定是否为所述预期门后第一次更新产生所述撤消。

8.根据权利要求1所述的方法，进一步包括：根据与特定时间点相关的门产生所述撤消；

将所述撤消作为一系列闪回记录存储在闪回日志中；以及将使所述门与位置相关联的数据存储在所述闪回日志中。

9.根据权利要求8所述的方法，其中，所述将使所述门与位置相关联的数据存储在所述闪回日志中的步骤包括：为所述门的各个门在所述闪回日志中存储门标记。

10.根据权利要求9所述的方法，进一步包括如下步骤：使用与门相关的门标记，来确定处理哪个闪回记录，以将所述储存库返回到与所述门相关的所述先前状态。

11.根据权利要求9所述的方法，其中：

所述门标记包括指示在重做日志中的位置的数据；以及所述方法进一步包括使用在所述重做日志中的所述位置来确定处理哪个重做。

12.根据权利要求9所述的方法，其中：

所述门标记包括指示在所述闪回日志中的位置的数据；以及所述方法进一步包括使用在所述闪回日志中的所述位置来确定处理哪个闪回条目。

13.根据权利要求9所述的方法，进一步包括，在各门标记中存储到在所述闪回日志中的先前门标记的链接。

14.根据权利要求1所述的方法，其中，

多个实体可以使用所述储存库；以及

所述多个实体的各实体保存分离日志，所述分离日志含有对于所述撤消的至少一些所述数据的撤消信息。

15.根据权利要求14所述的方法，进一步包括通过执行以下步骤来建立门：将所述多个实体中的一个指定为协调器；

使所述协调器向各其它所述实体发送开始记录消息；

使各其它实体通过为所有更新产生所述重做来响应所述开始记录消息；

在发送所述开始记录消息之后，使所述协调器向各其它所述实体发送门已建立消息；

以及

使各其它实体通过仅为门后第一次更新建立所述撤消来响应所述门已建立消息。

16.根据权利要求15所述的方法，其中：

各其它实体还通过向所述协调器发送响应来响应所述开始记录消息；以及(1)在向所述多个实体中的各其它实体发送所述开始记录消息之后以及(2)在从所有所述其他实体接收到对所述开始记录消息的响应后，所述协调器发送所述门已建立消息。

17.根据权利要求16所述的方法，其中：

由各其它实体发送的所述响应，指示所述实体在所述分离日志中的位置；以及所述协调器存储使所述门与位置信息相关联的数据，其中，所述位置信息用于识别在从所述各其它实体接收到的所述响应中指示的位置。

18.根据权利要求17所述的方法，其中，所述存储使所述门与位置信息相关联的数据的步骤包括：为所述门在所述协调器的所述分离日志中存储标记，其中，所述标记包括在从所述各其它实体接收到的所述响应中指示的位置的链接。

19.一种用于将储存库还原到先前状态的方法，所述先前状态是在所述储存库的最近一致逻辑状态之前的状态，所述方法包括：建立与第一时间点相关的预期门；

为对存在于所述储存库中的数据作出的一些但不是全部的预期门后第一次更新产生撤消；

建立与比所述第一时间点晚的第二时间点相关的门；

除在所述预期门时为其产生所述撤消的数据作出的更新之外，为对存在于所述储存库中的数据作出的所有门后第一次更新产生所述撤消；

通过执行以下步骤，将所述储存库还原到至少与所述第二时间点一样早的所述先前状态：使用与所述预期门相关的所述撤消，以将所述储存库的数据的第一集合还原回在所述第二时间点之前的时间；以及使用与所述门相关的所述撤消，以将所述储存库的数据的第二集合还原回所述第二时间点。

20.根据权利要求19所述的方法，进一步包括以下步骤：在所述预期门后第一次更新被执行时，根据资源的可用性确定是否为预期门后第一次更新产生所述撤消。

说明书

将储存库还原到先前状态的方法

[0001] 本申请是申请号为200480010768.1、申请日为2004年3月31日、发明名称为“将储存库还原到先前状态的方法”的发明专利申请的分案申请。

技术领域

[0002] 本发明涉及数据管理系统，并且更特别地，涉及用于将一组数据恢复到先前状态的技术。

背景技术

[0003] 在使用计算机时可能会产生许多问题。两种通常类别的错误包括计算机引起的错误和操作者引起的错误。由于这两种类型的错误的性质不同，被设计用于从计算机引起的错误恢复的技术未必能用于从操作者引起的错误恢复。

[0004] 例如，一项用于在计算机引起的错误(诸如节点或进程故障)之后恢复数据库的技术包括保存操作日志。特别地，保存重做日志(redo log)，使得由在故障之前提交的事务在易失性存储器中作出的改变能够在故障之后持久保存在数据库中。类似地，保存撤消日志(undo log)，使得由不是在故障之前提交的事务作出的持久保存的改变可以在故障之后被从数据库除去。

[0005] 上述的基于日志的恢复技术不能处理操作者引起的错误的问题，因为这些错误可以反映在由所提交的事务作出的改变中。即使当反映人员错误的所提交的事务后面跟有计算机引起的错误时，基于日志的恢复操作仅仅能保证这些错误地执行的改变在从计算机引起的错误恢复后继续反映在数据库中。因此，计算机引起的错误的恢复技术倾向于区别已提交的改变和未提交的改变，而不区别正确的已提交的改变和错误的已提交的改变。

[0006] 与计算机引起的错误的恢复技术相反，操作者引起的错误的恢复技术集中在从数据库除去已提交的改变和未提交的改变。特别地，操作者引起的错误的恢复技术典型地集中在将数据库返回到存在于在过去的特定点(优选地在包括操作者引起的错误的事务的提交时间之前)的一致状态。例如，一项操作者引起的错误的恢复技术包括在特定时间点制作数据库的备份。如果操作者引起的错误在该时间之后引入，可以通过还原到数据库的备份来将操作者引起的错误“除去”。

[0007] 当然，数据库管理员很少提前知道操作员引起的错误将被引入。如果在最后的备份操作与错误的时间之间已经经过了很长时间，则还原回备份的数据库，然后再次应用在备份操作之后但是在错误之前发生的所有改变是非常不切实际和低效的。

[0008] 另一技术包括保存“镜像”数据库(mirror database)，其状态相对于原始数据库被延迟。在用户引起的错误的情况下，可以还原到镜像数据库。然而，如果用于发现错误的时间大于延迟的持续时间，则即使所延迟的镜像也将反映错误。此外，由于长的延迟将提高及时发现错误的概率，其将同样增加与故障转移到镜像相关的低效率。

[0009] 另一延迟的镜像技术包括保存多个延迟的镜像数据库，其中各镜像数据库具有不同的延迟持续时间。带有不同延迟的多个镜像的使用增加了至少一个镜像将表示在错误的时间之前但是不太久前的状态的可能性。然而，同可以用于该目的的资源相比，保存这样的镜像消耗了更多的资源。

[0010] 可选的技术包括在支持“快照(snapshot)”的存储器子系统上存储数据库，然后使用子系统的快照机制将存储器子系统还原回在错误之前的快照时间。例如，存储器子系统可以设定特定的“快照时间”T5。在T5之后，子系统中的块(block)的各个改变通过以下方式处理：(1)确定该块在T5之后是否已经被改变，并且如果没有，那么(2)在对该块作出改变之前，从子系统中读取块的改变之前的版本并将其复制到与T5快照相关联的特殊分离“快照存储器”。使用该技术，通过将块从T5快照存储器复制回其在存储器子系统中的对应块，可以将存取器子系统返回到其在时间T5存在的状态。

[0011] 此外，即使在不将存储器子系统还原回其前状态(prior state)的情况下，当进程或事务想要看特殊的块时，也可以通过执行以下的步骤允许进程或事务看子系统在时间T5的状态：(1)，如果特殊块的拷贝在T5快照存储器中，则从T5快照存储器中提供特殊块的拷贝，以及(2)只有当在T5快照存储器中没有块的拷贝时才从存储器子系统提供特殊块的拷贝。

[0012] 快照技术提供了精确的结果，但是这是通过将潜在地巨大管理量强加于所有的写入操作来实现的。特别地，当在任意快照时间之后对任意块的第一次更新时，块的更新之前的图像必须被读取，然后写出到适当的快照存储器。此外，当数据库管理员必须将存储器子系统返回到先前状态时，管理员仅被限于那些快照时间被明确地设定的状态。

[0013] 操作者引起的错误仅仅是一种不容易通过应用生理撤消(physiological undo)除去的错误。例如，当试图从逻辑数据不纯(data corruption)恢复时可能会产生困难。例如，类似于操作者引起的错误，如果再次应用重做(redo)，这样的不纯可以被简单地“重放(replay)”。

[0014] 基于前文所述，显然希望提供一种机制和技术，用于以不存在在该部分中描述的方法中固有的效率或资源消耗问题的方式从可重放错误恢复。

[0015] 在该部分中描述的方法是可执行的方法，但不必是以前已经想到或执行的方法。因此，除非指出，否则不应仅因为在该部分中描述的任何方法包括在该部分中，就认为其为现有技术。

附图说明

[0016] 通过附图中的实例来描述本发明，但是不局限于此，在附图中相同的参考标号表示类似的元件，其中：

[0017] 图1A-1C是示出根据本发明的实施例的具有闪回(flashback)日志的系统的框图；

[0018] 图2是示出根据本发明的实施例的嵌入闪回日志的门标记的框图；以及[0019] 图3是示出可实施本发明实施例的计算机系统的框图。

具体实施方式

[0020] 本发明描述一种用于将储存库(repository)还原到前状态的技术。在下面的描述中，为了解释的目的，描述了多个特定的细节，以对本发明有彻底的了解。然而，很显然，在没有这些特定细节的情况下，本发明也可以被实现。在其它的实例中，以框图形式示出已知的结构和设备，以避免不必要地模糊本发明。

[0021] 功能概述

[0022] 在本文中描述的技术用于将储存库返回到前状态。根据一个实施例，该储存库为数据库，并且前状态是数据库在过去特定时间点具有的一致状态。特别地，前状态是数据库在其中反映由在特定时间点之前提交的事务作出的所有改变，并且不反映由在特定时间点之前未提交的事务作出的改变的状态。在另一实施例中，储存库是磁盘上的一个或多个文件。

[0023] 当操作者引起的错误通过由已经提交的事务作出的改变引入到数据库中时，本文中描述的技术可以用于通过将数据库返回到引入错误的事务被提交时间之前的时间点来从错误恢复。该技术包括产生成“物理撤消(physical undo)”信息，并且结合生理撤消(physiological undo)和生理重做(physiological redo)使用物理撤消信息，以有效地将储存库返回到前状态。

[0024] 物理撤消

[0025] 物理撤消包括将存储器单元返回到先前状态所必需的信息。术语“块(block)”在本文中将用于表示为了维持物理撤消而作为原子单位看待的存储单元。本文中描述的技术不限于任何特定大小或间隔尺寸的块。

[0026] 根据一个实施例，块的物理撤消是块的更新之前的图像。已更新的块的更新之前的图像可以用于仅仅通过用块的更新之前的图像重写已更新的块来将已更新的块返回到更新之前的状态。然而，更新之前的图像仅仅是可以用于将存储单元返回到先前状态的信息的一种形式，并且在本文中描述的技术不限于任何特定形式的物理撤消。

[0027] 使用在本文中描述的技术，将已更新的块写入磁盘的每项操作均不会引起用于获得块的更新之前的图像的磁盘读取操作的额外管理。相反地，当数据库服务器执行更新时，数据库服务器通常已经具有在易失性存储器中的块的拷贝。因此，物理撤消的发生可以仅仅包括在更新第一拷贝之前在易失性存储器中生成块的第二拷贝。如下面更加详细描述的，更新之前的第二拷贝在稍后的时间冲入(flush)磁盘，但是不迟于块的已更新的图像冲入磁盘的时间。

[0028] 生理撤消

[0029] 生理撤消包括将单独的逻辑信息片(piece)恢复到先前状态所必需的信息。例如，在关系型数据库系统中，如果表的一行被更新，则可能会产生生理撤消记录。在这种情况下，生理撤消记录将包括用于将该行返回到其更新之前的状态的信息，但是可能不包括关于可能碰巧同已更新的行存在于相同的数据块中的其他数据项的状态的信息。

[0030] 同生理撤消相比，物理撤消具有优势。物理撤消的应用通常是成功的，这是因为其不需要关于应用之前的图像的任何假设。因此物理撤消总是能取消逻辑数据不纯。另一方面，如果应用之前的图像不是自相一致的，则生理撤消的应用可能会失败。一个块可能由于存储器不纯、软件程序错误等而变得自相不一致。

[0031] 生理重做

[0032] 与生理撤消相类似，生理重做存储关于逻辑数据项的改变的信息。然而，虽然生理撤消存储关于如何撤消逻辑数据项的改变的信息，但是生理重做存储关于如何再次执行逻辑数据项的改变的信息。其中，使用生理重做以再次执行由已提交的事务作出的改变，其中这些改变在计算机引起的错误产生时尚没有存储到永久性存储器中。

[0033] 如上所述，为了从计算机引起的错误恢复，许多数据库系统支持生理撤消和重做。在标题为“Method And Apparatus For ImprovedTransaction Recovery”的美国专利第
5,850,507号中描述了生理重做和撤消机制的实例，其内容结合于此作为参考。然而，本文中所述的技术不限于任何用于支持生理重做和撤消的特定机制。

[0034] 双相恢复

[0035] 根据本发明的一个实施例，储存库在两个相位上被返回到先前状态，本文中指的是“物理恢复相位”和“生理恢复相位”。例如，假设用户想要将储存库还原回在特定时间点(“目标时间”)存在的状态。在物理恢复相位期间，物理撤消用于将所有与储存库相关的磁盘块返回到其在某时间点(“物理恢复时间”)的物理状态。在生理恢复相位期间，生理重做和撤消用于将在储存库中的逻辑信息从其在物理恢复之后的状态移动到与目标时间相关的一致状态。

[0036] 应当注意，即使当物理恢复时间是目标时间时，生理恢复相位对于将块中的逻辑数据返回到一致状态而言可能仍是必需的。例如，在时间T5，给定的块可能(1)包括由到时间T5为止还没有提交的事务作出的改变，并且(2)错过由已经在T5之前提交的事务作出的改变。因此，将块返回到其在时间T5的物理状态，并不必然将在块上的逻辑数据项返回到其在时间T5的一致状态。因此，生理重做被应用于，将由已经在T5之前提交的事务作出的任何错过的改变添加到块的T5图像。类似地，生理撤消被应用于，从块的T5物理图像除去任何由到时间T5为止还没有提交的事务作出的改变。

[0037] 门

[0038] 根据一个实施例，用于管理储存库的系统建立特殊时间点，本文中称为“门(gate)”，并为其产生物理撤消。为了解释的目的，假设储存库是数据库。在这样的实施例中，管理储存库并建立门的系统是数据库服务器。

[0039] 为门产生的物理撤消用于将存储储存库的块返回到其在与门相关的时间存在的物理状态。例如，如果门G1为时间T5而建立，则为门G1产生的物理撤消具有用于将块返回到其在时间T5或在时间T5之前存在的物理状态的信息。在一个实施例中，G1的物理撤消包括在T5之后更新的所有块的更新之前的图像。块的更新之前的图像包括块中的所有数据，即使更新可能仅改变存储在块上的多个逻辑数据项的一个。因此，可以仅仅通过用块的相应的更新之前的图像重写块的已更新的版本来将储存库的块返回到其在T5的物理状态。

[0040] 根据一个实施例，当块在与门相关的时间之后被第一次更新时，通过存储块的更新之前的图像来建立门的物理重做(physicalredo)。特别地，响应于(1)在门时间之后(2)为自门以后没有被预先更新的任意块作出的任意更新而产生更新之前的图像。这样的更新在本文中称为“门后第一次更新(first-after-gate update)”。

[0041] 例如，设想门G1与时间T5相关联。假设块在T5之后被更新。如果块在T5之后已经被更新，则该更新不是门后的第一次更新，并且没有物理撤消响应于该更新为G1产生。另一方面，如果块在T5之后被第一次更新，则该更新是门后第一次更新，并且产生块的更新之前的图像作为门G1的物理撤消。

[0042] 多种技术可以用于识别哪些更新具有门后第一次更新的资格。例如，可以将时间戳(timestamp)放在各块的首部中，以指示块被更新的最后时间。如果正被更新的块的块首部中的时间戳高于门的时间戳，则一些处理已经在门后更新了块至少一次，因此当前更新不是门后第一次更新。另一方面，如果正被更新的块的块首部中的时间戳低于门的时间戳，则当前更新是门后第一次更新。可选地，数据可以被存储在易失性存储器中，以指示在最近的门之后哪些块已经被更新。本发明不限于用于识别哪些更新有资格作为门后第一次更新的任何特定技术。

[0043] 闪回日志

[0044] 根据一个实施例，门的物理撤消记录作为条目存储在“闪回日志”中。正如下文中将更详细描述的，单个的闪回日志可用于存储与许多门相关联的更新之前的图像，其中标记用于使闪回日志中的位置与特殊的门相关联。

[0045] 图1a根据本发明的实施例示出系统100，将结合系统解释用于管理物理撤消的技术。参照图1a，系统100包括易失性存储器102和非易失性存储器104。非易失性存储器104包括用于存储数据的储存库112。储存库112可以是，例如，由数据库服务器管理的数据库，并且本文中描述的用于管理、维持、和使用物理撤消的操作可以由数据库服务器中的程序自动执行。然而，本文中描述的技术可以应用于可能需要被返回到先前状态的任意类型的储存库，并因此不限于传统的数据库服务器环境。

[0046] 除了储存库112之外，非易失性存储器104包括闪回日志106。闪回日志106用于存储条目(entry，入口)(例如，条目140、142、144)，该条目(1)对应于储存库112中的块，并且(2)包括用于将相应的块返回到前状态的信息。根据一个实施例，闪回日志106中的各个条目包括储存库112中的相应的块的更新之前的图像。

[0047] 易失性存储器102包括块缓存(block cache)110和闪回日志缓存108。块缓存110保存来自储存库112的块的拷贝。例如，对于从储存库112的块120读取数据项的过程，块120的拷贝122载入到易失性存储器102中的块缓存110中。如果该过程然后更新该数据项，则该更新将最初被反映在块120的缓存的拷贝122中，而不是反映在存在于非易失性存储器104中的块120中。

[0048] 易失性存储器102进一步包括闪回日志缓存108。闪回日志缓存108用于存储闪回日志条目(例如，条目130、132和134)，该条目已经被设立但是还没有冲入非易失性存储器104中。例如，如果块120的拷贝122将被修改，可能有必要生成包括块120的更新之前的图像的闪回日志条目(例如，图1B中的条目136)。闪回日志条目最初将被存储在闪回日志缓存108中，然后冲入位于非易失性存储器104上的闪回日志106中。在图1C中，响应于被冲入非易失性存储器104的条目136，条目146已经被添加到闪回日志106。

[0049] 预期的物理撤消生成

[0050] 在上述的实施例中，响应于(1)在门之后(2)为在该门之后没有被预先更新的块而作的每个更新，产生闪回日志条目。遗憾的是，该技术导致在闪回日志条目(其在任意给定的门之后必须立即被产生)的数量中产生“毛刺(spike)”。特别地，实际上在经过门之后立即发生的所有更新都是门后第一次更新。因此，紧跟在门之后，需要生成闪回日志条目的更新操作的百分率实际上是100％。自初始毛刺之后，由于在门之后已经被更新的块将要更新的百分率增加，因此需要生成闪回日志条目的更新的百分率将下降。

[0051] 根据一个实施例，通过执行预期的物理撤消生成，降低了毛刺的数量。特别地，闪回日志条目为不是门后第一次更新的更新而生成。相反地，闪回日志条目是在恰好在与该门相关的时间之前的门时而生成。这样的闪回日志条目，在本文中称为“预期条目”，减少了当到达门时产生的毛刺，这是因为，不需要为具有预期条目的块的门后第一次更新生成另外的闪回日志条目。

[0052] 根据一个实施例，在实际门之前建立预期门(anticipatory gate)。然而，与实际门不同，在预期门之后为块作出的第一次更新不能自动生成闪回条目。相反地，在预期门之后生成闪回条目是可选的。在这些情形下是否生成条目可能取决于多个因素，诸如系统的工作量以及资源的有效性。例如，是否有闪回条目响应于在预期门之后作出的更新而生成，可能取决于在闪回日志缓存108中有多少空间是当前可用的。又例如，系统可以仅仅生成全部预期门后第一次更新(first-after-anticipatory-gate updates)的确定百分率(例如50％)的闪回条目。这些因素仅仅是可用于确定是否为预期门之后的更新生成闪回条目的因素的实例。本文中所描述的技术不限于因素的任何特定集合。

[0053] 当已经为门生成预期闪回条目时，预期闪回条目可能不反映相应的块在与门相关的时间的状态。例如，假设G1与时间T5相关，并且在时间T3发布(publish)G1的预期门。在T3和T5之间生成的所有预期闪回条目将反映块在T3和T5之间的某时间点的状态，但并不必然反映块在时间T5的状态。

[0054] 例如，块B1可以在时间T4被更新，这使得预期闪回条目将被产生。如果与门G1相关的闪回条目随后被用于将数据库还原回时间T5，则B1的预期闪回条目将实际将块B1还原回时间T4。因此，当使用预期门时，储存库在物理恢复相位后将是“模糊的(fuzzy)”。特别地，在物理恢复相位之后，一些块将反映其在时间T5的物理状态，并且其他的块将反映其在时间T3和T5之间的物理状态。

[0055] 预期门的使用仅仅是可能引起这样的“模糊”的技术的一个实例。例如，在下文中描述的用于多服务器系统的双相位广播技术同样可能产生反映在与相应的门相关的时间之前的状态的更新之前的图像。同样，当门与物理撤消的产生“同时”发生时，物理撤消可以被分配在门之前的时间戳。然而，不考虑这些原因，当所有的逻辑数据项从其当前所处的任何状态返回到目标状态时，“模糊”在生理恢复相位期间被消除。

[0056] 门标记

[0057] 如上所述，闪回条目最初存储在闪回缓存108中，并周期性的冲入位于非易失性存储器104上的闪回日志106中。根据一个实施例，单个闪回日志106可用于多个门，其中标记(在本文中称为“门标记”)被插入闪回日志106，以指示与特定门相关的条目的启动。

[0058] 图2是示出根据本发明的实施例的已经放置(populate)的闪回日志200的框图。参照图2，由于闪回条目被从缓存冲入永久性存储器，因此闪回日志200顺序放置(在所述实施例中，从左到右)。

[0059] 根据一个实施例，门标记存储在闪回日志200中，以便于应用与给定的门相关的闪回条目。在所述的实施中，闪回日志200包括与时间T500的门G5相关的门标记202，以及与时间T600的门G6相关的门标记204。

[0060] 门标记链

[0061] 根据一个实施例，闪回日志200中的不同门标记链接在一起，使得它们可以在闪回日志中被快速定位。在示出的实施例中，每个门标记均包括到紧接在前面的门标记的链接，并且控制文件206包括到最新存储的门标记的链接。当以这种方式链接时，通过跟随控制文件206中的链接，任何给定的门标记可以快速地被定位于最新的门标记，然后跟随门标记中的链接回到预期的门标记。例如，为了定位门标记202，使用控制文件206中的链接来定位门标记204，并使用门标记204中的链接来定位门标记202。

[0062] 当新的门标记被添加到闪回日志200中时，门标记链通过如下方式保持：使新门标记指向当前由控制文件指向的门标记，然后使控制文件指向新近插入的门标记。例如，如果新门标记被添加到闪回日志200中，则该新新标记将具有到门204的链接，并且控制文件206中的链接将被更新以指向新门标记。

[0063] 门标记的使用

[0064] 根据一个实施例，用于特定门的门标记可以实现多个目的，包括：(1)标记闪回日志中的位置以及(2)识别生理重做日志中的位置。在一个实施例中，闪回日志中的门标记的位置指示从哪里开始处理闪回条目，以将储存库返回到与相应的门相关的时间。例如，为了将储存库返回到与时间T500相关的物理状态，可通过从条目220开始一直到位于闪回日志末端的条目228来处理闪回日志200。另一方面，为了将储存库返回到与时间T600相关的物理状态，可通过从条目222开始一直到位于闪回日志末端的条目228来处理闪回日志204。

[0065] 在可选实施例中，使用门标记中的指针而不是门标记本身的位置，来识别在相应的门时处理闪回日志的开始位置。通过使用指针来指示闪回日志中的开始位置，门标记本身存储的顺序对于闪回日志而言是无关紧要的。例如，当闪回日志在位置P1时，可以发布与时间T500相关的门G1。如果门标记的位置将被用于识别开始处理的位置，则必须提供一些机制以确保在用于G1的门标记之前没有与G1相关的闪回条目存储在闪回日志中，使得用于G1的门标记存储在位置P1。然而，如果使用指针，则在用于G1的门标记之前在G1时产生的其它闪回条目可以被冲入磁盘。存储在闪回日志的P1之后某处的用于G1的门标记，将仅包括用于指示位置P1的指针。

[0066] 当处理闪回条目时，储存库的对应的块被还原回闪回条目中的图像，除非该闪回条目反映比与被用于还原储存库的门相关的时间更晚的更新。例如，如果闪回条目220和222均对应于相同的块B1，并且储存库被还原回与门G5相关的时间T500，则块B1将基于闪回条目220被还原，但将不会基于闪回条目222被还原，这是因为闪回条目将反映在T500之后对块B1作出的更新。

[0067] 在上面给出的实例中，门标记用于指示应用闪回条目的开始位置。在可选的实施例中，闪回条目可以以逆序被应用，从最新的条目开始并继续到适当的门标记(或由在门标记中的指针指示的位置)。在这些情况下，门标记或指针指示在哪里停止处理闪回条目。同样，当闪回日志从最新到最老被处理时，当与条目相关的时间戳比被用于恢复的门的时间更近时，一个闪回条目被跳过。例如，在条目220和222均对应于相同的块B1，并且储存库被还原回与门G5相关的时间T500的情况下，由于条目222将与比时间T500更大的时间戳相关联，其将被跳过。换言之，由于在条目222中反映的块B1的图像包括在时间T500后作出的改变，因此条目222将被跳过。另一方面，由于条目220将与在时间T500之前的时间戳相关联，并将反映块B1在T500之前某时间的物理图像，因此条目220将被应用。

[0068] 如上所述，闪回条目可以以时间顺序或逆时间顺序被应用。事实上，闪回条目可以以任意顺序被处理。如果有用于具有比与被用于还原储存库的门相关的时间更早的时间戳的块的多个闪回条目，则来自任意一个条目的图像同块的在“物理恢复相位”之后的恢复图像一样好。以任意顺序应用闪回条目的能力在能够并行应用闪回条目的系统中尤其有用，从而进一步提高了恢复操作的效率。例如，需要被应用的闪回条目的子集可以被分配给多个过程。这些过程的每个然后可以使其指定的闪回条目具有与其他处理的最小配合。

[0069] 如上所述，在一个实施例中，各门标记还包括指向生理重做日志中的位置的指针(“重做指针”)。特别地，存储在门标记中的重做指针指示生理重做日志250中的在储存库已经被还原回与门标记相关的门之后开始处理重做记录的位置。例如，假设储存库将被返回到时间T550。在物理恢复相位期间，在目标时间T550或在目标时间T550之前的第一门被识别。在当前实例中，门标记链被跟随回到对应于时间T500的标记202。在门标记202之后的闪回条目然后被用于将储存库还原回其在时间T500的物理状态。

[0070] 在物理恢复相位之后，储存库将反映块在时间T500或在T500之前的物理状态。因此，由在T550之前提交的事务作出的改变中的一些，可能不被反映在储存库在时间T500的物理状态中。为了使这些改变被反映，从重做日志250中的由门标记202的重做指针指示的位置开始，使用生理重做记录。重做记录的使用将储存库中的逻辑数据项向前滚动到其在时间T550时的一致状态。同样在生理恢复相位期间，生理撤消被应用于将(1)在物理图像中，但(2)由在时间T550时尚未提交的事务作出的任何更新从逻辑数据项中去除。

[0071] 多服务器系统

[0072] 在一些数据库系统中，多个数据库服务器可能可以进入相同的数据库。根据一个实施例，可以进入数据库的各个数据库服务器保存其自己的用于恢复数据库的日志集合，包括闪回日志和生理重做日志。该多个数据库服务器还可以具有分离的生理撤消日志，或者可以有单个由全部数据库服务器共享的生理撤消日志。为了将数据库还原回先前状态，可能需要来自所有服务器的所有日志的恢复信息。例如，在特定的门G3之后，一个服务器S1可能对块B1执行门后第一次更新，另一服务器S2可能对块B2执行门后第一次更新，并且另一服务器S3可能对块B3执行门后第一次更新。在这些情形下，如果数据库将被还原回门G3，则来自S1的闪回日志的闪回记录将必须被应用到B1，来自S2的闪回日志的闪回记录将必须被应用到B2，并且来自S3的闪回日志的闪回记录将必须被应用到B3。

[0073] 遗憾的是，多个服务器之间的通信不是瞬时的。服务器间通信中的时间延迟能够引起关于门的建立的同步问题。例如，假设服务器S1建立与5pm相关的门G3。如果服务器间通信是瞬时的，则在时间5pm服务器S1可以发布门G3，并且S2和S3将准确地在G3之后开始为所有门后第一次更新生成闪回条目。然而，G3的通知可能直到5pm之后一秒才到达S2，并直到5pm之后三秒才到达S3。因此，G3将错过由S2在5pm和5pm之后一秒之间作出的更新的闪回条目。类似地，G3将错过由S3在5pm和5pm之后三秒之间作出的更新的闪回条目。

[0074] 根据一个实施例，通过使用双相位过程建立门解决了该同步问题。在第一相位期间，被指定为“协调器(coordinator)”的服务器向所有其他服务器发送“开始记录(begin-logging)”消息。响应于该开始记录消息，各其他服务器(1)向协调器发送指示在其闪回日志中的当前插入点的位置的响应消息，并(2)开始为其作出的每个更新生成闪回条目。

[0075] 例如，假设S2接收到来自S1的开始记录消息，并且S2的闪回日志中的当前插入点是S2-POS1。响应于该开始记录消息，S2(1)发送响应到S1，指示其当前位置S2-POS1，并且(2)开始为其作出的每个更新生成闪回条目。类似地，当S3接收到来自S1的开始记录消息时，如果S3的闪回日志中的当前插入点是S3-POS1，则响应于该开始记录消息，S3(1)发送响应到S1，指示其当前位置S3-POS1，并且(2)开始为其作出的每个更新生成闪回条目。

[0076] 当协调器已经接收到来自所有其他服务器的响应时，协调器(1)建立与不比接收到最后的响应的时间早的时间相关的门，并且(2)为该门生成标记。例如，假设S1在5pm接收到最后的响应，并且建立与该时间5pm相关的门G3。在建立该门之后，协调器向其他服务器发送“门已建立(gate-established)”消息。该门已建立消息指示与该新门相关的时间。由于新门的建立时间必定在服务器开始生成闪回条目的时间之后，因此闪回条目将为由服务器作出的所有门后第一次改变而存在，而不考虑它们何时接收到门已建立消息。

[0077] 响应于接收门已建立消息，其他服务器停止为所有更新生成闪回条目，并开始仅为门后第一次更新生成闪回条目。返回到当前的实例，S2和S3接收到来自S1的指示G3在5pm被建立的门已建立消息。S2和S3停止为所有更新生成闪回条目，并开始为在5pm之后对任何给定的块作出的第一次更新生成闪回条目。

[0078] 上述的双相位门创建技术避免了与同步相关的问题，这是因为，即使服务器在与门相关的时间之后接收到门已建立消息，该服务器将已经为在与门相关的时间和服务器接收到门已建立消息的时间之间作出的任何改变生成了闪回条目。例如，即使S2在5:01pm接收到G3的门已建立消息，S2将已经为在5:00pm(该时间相关于门G3)之后作出的所有更新生成了闪回信息。

[0079] 如上所述，协调器为其建立的门生成门标记。根据一个实施例，除了在多服务器环境中门标记包括指示在其他服务器的闪回日志中与该门相关的位置的数据外，为在多服务器环境中的门生成的门标记类似于在单服务器环境中生成的门标记。例如，存储在S1的闪回日志中的门G3的闪回标记，包括指示在S2的闪回日志中的S2-POS1和S3的闪回日志中的S3-POS1的数据。因此，当根据G3执行物理恢复时，G3的标记将指示在S1、S2和S3的每个的闪回日志中从哪里开始处理闪回条目。

[0080] 在可选实施例中，特定门的门标记可以放在各个分离的闪回日志中。例如，存储在S1的闪回日志中的门G3的闪回标记，将指示在S1的闪回日志中的与门G3相关的位置。门G3的分离的闪回标记将被存储在S2的闪回日志中，并指示位置S2-POS1。门G3的另一个闪回标记将被存储在S3的闪回日志中，并指示位置S3-POS1。

[0081] 根据其中单个门标记被用于为所有服务器指示门位置的实施例，服务器通过发送其在其各自的闪回日志中的当前位置以及其在其生理重做日志中的当前位置来响应开始记录消息。两份信息均可以存储在门的标记中。因此，当数据库根据门被还原到先前物理状态时，门标记中的信息将不仅指示在多个闪回日志中从哪里开始处理闪回条目，还指示在多个生理重做日志中从哪里开始处理重做条目。

[0082] 时序

[0083] 为了确保储存库的完整性，必须以特定的顺序执行某些操作。由一个实施例使用的可以用于闪回日志维持操作的时序依赖(timing dependency)包括：

[0084] 在块的已更新的拷贝冲入非易失性存储器之时或之前，含有块的更新之前的图像的闪回条目必须被冲入非易失性存储器。例如，参照图1C，闪回条目136必须在块120的修正拷贝124被冲入储存库112之时或之前，被冲入闪回日志106。

[0085] 用于反映在块的前图像(prior image)中的所有改变的重做条目必须在含有前图像的闪回条目被冲入非易失性存储器之时或之前，被冲入非易失性存储器。例如，假设块B1在4:49pm被更新，使得重做记录R1将被生成。进一步假设为块B1的门后第一次更新生成闪回条目F1，其中引起F1生成的门G3与5pm相关。在这些情形下，包含在F1中的B1的前图像将反映在4:49pm作出的改变。因此，R1必须在F1被冲入非易失性存储器的时间之时或之前被冲入非易失性存储器。

[0086] 一项用于确保用于改变的重做在反映改变的前图像被冲入非易失性存储器之前被冲入非易失性存储器的技术包括：在门被建立的时候，将与在门之前作出的改变相关的所有重做冲入非易失性存储器。因此，当G3在5pm被建立时，与在5pm之前作出的改变相关的所有重做被冲入非易失性存储器。因此，G3的闪回条目将不反映重做信息还未在非易失性存储器上反映的任何改变。

[0087] 最优化

[0088] 多种技术可以被用于改善如本文中描述一样执行的恢复操作的执行。例如，假设还没有数据被存储在块B1上。如果B1的第一次更新是门后第一次更新，则将用B1的更新之前的图像生成闪回条目。在这种情况下，然而，B1的更新之前的图像不含有任何有用的信息。因此，当对未存储任何须被保留的信息的块作出门后第一次更新时，产生特殊的闪回条目。该特殊的闪回条目不含有块的完整的更新之前的图像，而是仅仅识别块以及指示该块不含有任何需要的信息。

[0089] 如另一个实例，在一些情形中，诸如在插入(INSERT)操作的情形中，当在块上执行门后第一次更新时，块的前版本可能还没有在易失性存储器中。在这些情况下，块的前图像通常必须被从非易失性存储器中读取，以生成用于更新的闪回条目。然而，如果知道块的前图像不含有必须被记录的任何信息，则可以避免从非易失性存储器读取前图像的必要。根据一个实施例，如果块为已经在随后被取消(drop)的结构(诸如表)预先存储了数据，则确定该结构是否在与该数据库可能被还原到的最老的门相关的时间之前被取消。如果该结构是在与该数据库可能被还原到的最老的门相关的时间之前被丢弃，则不需要从磁盘读取前图像。相反，特殊的闪回条目可被用于识别块，并指示该块不含有任何需要的信息。

[0090] 例如，如果块预先存储在一周前取消表的部分，并且该数据库所需的最老的门是两天以前，则该块属于在与数据库可能被还原到的最老的门相关的时间之前被取消的结构。因此，不含有块的前图像的特殊闪回条目可以被用于该块。

[0091] 另一项可被用于保存资源的技术包括：将物理和生理撤消日志组合成单个的撤消日志，该单个的撤消日志包括将储存库还原回一致状态的足够的信息。使用组合的撤消日志可以避免在分离的物理和生理撤消日志中保存的信息之间的大量冗余。可选地，可以通过仅在生理撤消不具有将块还原回前状态的足够信息的情形下生成闪回条目来避免这样的冗余。生理撤消不具有足够信息的特殊情况将随着执行的变化而变化，并且，例如，由被更新的块的特殊类型而决定。

[0092] 根据另一技术，含有文件的标题信息的块被同存储构成文件的内容的数据的块区别对待。根据一个实施例，为文件标题块生成的闪回条目不含有标题块的全部前图像。相反地，文件标题块的闪回条目描述文件的元变化，并被逻辑应用于文件，而不是完全的重写相应的文件标题块。例如，这样的闪回条目可以指示文件在特定的时间点被扩展。这样的闪回条目的应用包括将文件退回到其原始边界。类似地，闪回条目可为储存库指示文件的添加。闪回条目的应用包括删除所添加的文件。

[0093] 硬件描述

[0094] 图3是框图，示出了可应用本发明的实施例的计算机系统300。计算机系统300包括用于传递信息的总线302或其它通信装置、以及用于处理信息的、与总线302连接的处理器304。计算机系统300还包括主存储器306，例如随机访问存储器(RAM)或者其它动态存储装置，与总线302连接，用于储存信息及处理器304要执行的指令。主存储器306还可用于在处理器304执行指令过程中，储存临时变量或其他中间信息。计算机系统300还包括只读存储器(ROM)308或者其他静态存储装置，与总线302连接，用于储存静态信息和处理器304要执行的指令。还提供了存储装置310，如磁盘或光盘，与总线302连接，用于储存信息和指令。

[0095] 计算机系统300可以经由总线302连接到显示器312，如阴极射线管(CRT)，用于向计算机用户显示信息。包括字母数字键和其他键的输入装置314与总线302相连，用于传递信息和命令选择到处理器304。另一种用户输入装置是光标控制316，如鼠标、跟踪球、或光标方向键，用于传递方向信息和命令选择到处理器304并用于控制显示器312上的光标移动。这个输入设备通常在两个轴上(第一个轴(例如X轴)和第二个轴(例如Y轴))具有两个自由度，使装置能指定平面上的位置。

[0096] 本发明涉及计算机系统300的使用，用于执行在此描述的技术。根据本发明的一个实施例，由计算机系统300响应于执行包括在主存储器306中的一个或多个指令的一个或多个序列的处理器304，来实现这些技术。这样的指令可以从诸如存储设备310的其它计算机可读介质读入主存储器306。通过执行包括在主存储器306中的指令序列，使处理器304执行此处所述的处理步骤。在可选实施例中，硬连线电路(hard-wired circuitry)可取代软件指令或者与软件指令结合来实施该发明。因此，本发明中的实施例将不限于硬件电路和软件的任何特定组合。

[0097] 这里使用的术语“计算机可读介质”是指参与提供指令至用于执行的处理器304的任何介质。这种介质可以采取很多形式，包括但不限于非易失性介质、易失性介质和传递介质。非易失性介质举例来说包括光盘或磁盘，如存储装置310。易失性介质包括动态存储器，如主存储器306。传输介质包括同轴电缆、铜线、和光纤，包括组成总线302的导线。传输介质还可采取声波或光波形式，例如那些在无线电波和红外线数据通信过程中产生的声波和光波。

[0098] 通常形式的计算机可读介质包括如软盘、软性盘、硬盘、磁带，或者任何其它磁性介质、CD-ROM、任何其它光介质、打孔纸、纸带、或者任何带孔图样的物理介质、RAM、PROM、EPROM、FLASH-EPROM、或者其他任何存储芯片或者盒式磁带，或者以下提到的载波、或者计算机可读的任何其他介质。

[0099] 各种形式的计算机可读介质可参与承载一个或者多个指令的一个或多个序列到处理器304用于执行。例如，指令开始可承载在远程计算机的磁盘中。远程计算机可以将指令加载到其动态存储器中，然后使用调制解调器通过电话线发送信息。计算机系统300本地的调制解调器可接收电话线上的数据，并使用红外发射器将数据转换成红外信号。红外探测器可以接收红外信号携带的数据，合适的电路可以把信息放到总线302上。总线302把数据传递到主存储器306中，处理器304从主存储器取回并执行这些指令。在处理器304执行这些指令之前或之后，主存储器306接收的指令可随意地储存于存储装置310中。

[0100] 计算机系统300还包括连接到总线302的通信接口318。通信接口318提供双向数据通信，连接到与局域网322相连的网络链路320。例如，通信接口318可以是综合业务数字网(ISDN)卡或者调制解调器，用于提供到相应类型电话线的数据通信连接。又如，通信接口318可以是局域网(LAN)卡，用于提供至兼容局域网(LAN)的数据通信连接。也可以使用无线链路。在任何这样的实施中，通信接口318发送和接受承载表示各种信息的数字数据流的电信号、电磁信号和光学信号。

[0101] 网络链路320通常可通过一个或者多个网络提供数据通信给其它数据装置。例如，网络链路320可通过局域网322与主机324连接，或者与互联网服务提供商(ISP)326操作的数据设备连接。ISP326又通过目前通称为“互联网”328的全球分组数据通信网络提供数据通信服务。局域网322和互联网328都使用承载数字数据流的电信号、电磁信号或光学信号。这些信号，如通过各种网络的信号，网络链路320上的信号，通过通信接口318的信号，都传送数字数据给计算机系统300或者传送来自计算机系统300的数字数据，是传输信息的载波的示范性形式。

[0102] 计算机系统300能通过网络、网络链路320和通信接口318发送消息和接收数据(包括程序代码)。例如，在互联网的例子中，服务器330可通过互联网328、ISP 326、局域网322、和通信接口318，传送所请求的用于应用程序的程序代码。

[0103] 当代码被接收和/或储存在存储装置310上或者其它非易失性介质上用于随后执行时，处理器304可执行所接收到的代码。按照这种方式，计算机系统300可以以载波的形式获得应用代码。

[0104] 上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。