US 7,072,912 B1Granted

Identifying a common point in time across multiple logs

AssigneeMicrosoft Corporation

InventorsSurendra Verma, Jonathan M. Cargille

Life of this patent

Estimating the term…

Loading patent…

Abstract

Nodes in a distributed system maintain virtual times according to specified rules. Each node can associate its virtual time with transactional messages that are transferred to other nodes and with log entries that are written to a log. A reference entry, which corresponds to an arbitrary point in time, is selected from a first log associated with a first node. A reference virtual time associated with the reference entry is identified. A matching entry, with an associated virtual time that appropriately corresponds to the reference virtual time, is selected from a second log associated with a second node. The first node is caused to roll-forward to the arbitrary time by processing the first log up to the reference entry. The second node is caused to roll-forward to the arbitrary time by processing the second log up to the matching entry.

Claims42

Dependent claims

In a computer system that includes a plurality of logs, wherein each log contains a plurality of entries indicating transactions that have occurred at an associated resource manager, and wherein each entry in a log is associated with a virtual time value that represents the virtual time a transaction occurred, a method for selecting chronologically consistent entries contained in two or more logs so as to increase the chances of associated resource managers being in transactionally consistent states if the two or more logs are subsequently processed to bring the associated resource managers to a specified time, the method comprising:

an act of arbitrarily selecting a reference entry from a first log that is associated with a first resource manager, wherein the reference entry is written to the first log by the first resource manager upon receiving a transactional message from a transactional manager, and which is associated with an atomic transaction and that includes a virtual time;
an act of the first resource manager maximizing a reference virtual clock value of the first resource manager by updating the reference virtual clock value to be equal to the virtual time that is included in the received transactional message if the virtual time is greater than the reference virtual clock value when the transactional message is received,
using the reference virtual clock value as a reference virtual time value that is associated with the reference entry in the first log;
subsequent to selecting the reference entry from the first log, an act of identifying the reference virtual time value that is associated with the arbitrarily selected reference entry in the log;
and
wherein the reference virtual time value that was found to be associated with the selected reference entry is subsequently used for an act of selecting a matching entry, with an associated virtual time value that appropriately corresponds to the reference virtual time value, from a second log that is associated with a second resource manager.

3 more elements

In a dependent resource manager that maintains a dependent log, wherein the dependent log contains entries identifying transactions that have occurred at the dependent resource manager, a method for causing the dependent resource manager to be in a transactionally consistent state with a reference resource manager, the method comprising:

receiving a transactional message that is associated with an atomic transaction and that includes a virtual time;
making a log entry of the transactional message in a dependent log;
maximizing a virtual clock value of the dependent resource manager by determining whether the virtual time included in the received transactional message is greater than the virtual clock value of the dependent resource manager, and updating the virtual clock value of the dependent resource manager to be equal to the virtual time of the received transactional message if the virtual time of the received transactional message is greater than the virtual clock value of the dependent resource manager;
using the virtual clock value of the dependent resource manager as a virtual time value that is associated with an entry in the dependent log corresponding to the received transactional message;
and
an act of receiving a new virtual time associated with an entry contained in a reference log for which a transactionally consistent state of the dependent reference log is to be identified;
an act of identifying from the dependent log a matching entry that appropriately corresponds to the newly received virtual time;
and
an act of causing the dependent resource manager to roll-forward by processing the dependent log up to the matching entry, thereby moving the dependent log to the transactionally consistent state with the reference log.

6 more elements

Dependencies are inferred from the claim text.