System and method for locating log records in multiplexed transactional logs

• US 7,689,626 B2
• Filed: 05/31/2002
• Issued: 03/30/2010
• Est. Priority Date: 05/31/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bradshaw, Dexter Paul, Miller, Thomas Jay
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Dwivedi; Mahesh H
• Application Number:
  US10/159,228
• Publication Number:
  US 20030225585A1
• Time in Patent Office: 2,860 Days
• Field of Search: 707 8- 10, 707201-202, 707/1, 714/15, 718/1, 718/101, 709/229, 715/14
• US Class Current: 707/783
• CPC Class Codes: G06F 16/10 File systems; File servers

Abstract

A common logging system (a “virtual logging system”) that presents to one or more log clients the appearance that each log client is interacting with a dedicated logging system. In reality, the virtual logging system is multiplexing virtual log streams, including log records, for each log client into a single transactional log. In particular, the invention is directed at a scheme for mapping virtual identifiers that a client uses in connection with the client'"'"'s own records to physical identifiers that represent the physical location of the client'"'"'s records in the single transactional log

Claims

1. In a transactional logging system, a computer-implemented method for locating a log record in a transactional log, the transactional log having a plurality of regions, the log record being associated with a client, the computer-implemented method comprising:

receiving a virtual identifier from the client, the virtual identifier identifying the log record in the transactional log;

wherein each region of the transactional log includes log records and an owner page that includes information about ownership of each of the log records in the region;

wherein the owner page identifies at least two clients;

wherein each of the at least two clients is associated with a different application and wherein the transactional log includes log records from the at least two clients;

associating a first group of log records with an identity of the client in response to receiving the first group of log records from the client;

associating a second group of log records with an identity of a second client in response to receiving the second group of log records from the second client;

storing a destination owner page within a destination region of the transactional log, the destination owner page comprising a first range of identifiers associated with the identity of the client and a second range of identifiers associated with the identity of the second client;

wherein the owner page further includes an owner page physical identifier identifying the location of the owner page in the transactional log;

determining a correct region in the transactional log from among the plurality of regions by first accessing a presumed region in the transactional log using the virtual identifier and the identity of the client and determining if the presumed region contains the log record by accessing an owner page in the presumed region and determining whether the virtual identifier is within a range of identifiers associated with the identity of the client in the owner page; and

if the presumed region does not contain the log record then determining the correct region that contains the log record by accessing at least one other region in the transactional log and accessing the owner page for the other region;

calculating a log block physical identifier associated with the log block containing the log record, the calculation being based on the owner page physical identifier;

mapping the virtual identifier to the log block physical identifier for the log record in the correct region using the owner page associated with the correct region, the physical identifier corresponding to the location of the log record in the transactional log; and

locating the log block containing the log record in the transactional log using the log block physical identifier.

2. The computer-implemented method of claim 1, wherein the owner page associated with the correct region includes an owner referral that is used to determine the location of the log record.

3. The computer-implemented method of claim 2, wherein the owner referral includes a range of virtual identifiers associated with the client, the range of virtual identifiers including the virtual identifier that identifies the log record.

4. The computer-implemented method of claim 1, wherein the owner page associated with the correct region includes an owner array that identifies an owner of each of the sectors in the owner page'"'"'s region.

5. The computer-implemented method of claim 4, wherein the correct region includes a plurality of log blocks, the owner array identifying the log blocks associated with the client in the correct region, one of the identified log blocks containing the log record.

6. The computer-implemented method of claim 1, wherein the virtual identifier comprises a value having at least a container identification field identifying a container file in which resides at least a portion of the transactional log.

7. The computer-implemented method of claim 6, wherein the virtual identifier further comprises a second value having at least a block-offset field identifying a log block within the container file within which the log record resides.

8. The computer-implemented method of claim 7, wherein the virtual identifier further comprises a third value having at least a record sequence number field identifying where within the log block resides the log record.

9. In a transactional logging system, a computer-implemented method for identifying a current log record in a transactional log, the current log record being associated with a client, the transactional log having a last log record associated with the client, the last log record being appended to the transactional log before the current log record, the computer-implemented method comprising:

assigning a physical identifier to the last log record, the physical identifier identifying a location of the last log record within the transactional log; and

assigning a virtual identifier to the current log record, the virtual identifier corresponding to the physical identifier and associating the current log record with a virtual log, the virtual log being presented to the client by the transactional logging system as a dedicated log;

wherein the virtual identifier is used by the client to determine a correct region in the transactional log by first accessing a presumed region in the transactional log using the virtual identifier and an identity associated with the client and determining if the presumed region contains the current log record and if the presumed region does not contain the log record then determining the correct region that contains the log record by accessing at least one other region in the transactional log;

wherein an owner page includes information about ownership of each of the log records in a particular region, the owner page comprising the identity associated with the client in association with a range of virtual identifiers;

wherein the owner page further includes an owner page physical identifier identifying the location of the owner page in the transactional log;

calculating a log block physical identifier associated with the log block containing the log record, the calculation being based on the owner page physical identifier;

locating the log block containing the log record in the transactional log using the log block physical identifier;

mapping the virtual identifier to the log block physical identifier for the log record in the correct region using the owner page associated with the correct region, the physical identifier corresponding to the location of the log record in the transactional log;

wherein the owner page identifies at least two clients;

wherein each of the at least two clients is associated with a different application and wherein the transactional log includes log records from the at least two clients such the owner page identifies a first client associated with a first group of log records that are received from the first client and identifies a second client associated with a second group of log records that are received from the second client;

wherein the groups of log records are generated in response to the identity of the client that generated the record.

10. The computer-implemented method of claim 9, wherein each of the virtual identifier and the physical identifier further comprises a value having at least a container identification field identifying a container file.

11. The computer-implemented method of claim 10, wherein each of the virtual identifier and the physical identifier further comprises a second value having at least a block-offset field identifying a log block within the container file.

12. The computer-implemented method of claim 11, wherein each of the virtual identifier and the physical identifier further comprises a third value having at least a record sequence number field identifying at least one log record within the log block.

13. A computer-implemented method for locating a log record in a transactional log comprising:

receiving from a client a request related to a target log record in the transactional log having regions containing log records, the target log record being indicated by a virtual identifier identifying the log record in the transactional log;

wherein each region of the transactional log comprises an owner page that includes information about ownership of each of the log records in the region wherein the owner page identifies at least two clients;

wherein each of the at least two clients is associated with a different application and wherein the transactional log includes log records from the at least two clients;

wherein a first group of log records is associated with an identity of the client in response to receiving the first group of log records from the client;

wherein a second group of log records is associated with an identity of a second client in response to receiving the second group of log records from the second client;

determining if the target log record is located within a presumed region that is identified by the virtual identifier and the client; and

if the target log record is not located within the presumed region then;

determining, from a plurality of owner pages, which of a plurality of regions in the transactional log is a correct region, each owner page being associated with at least one of the regions and including information identifying a range of log blocks within the associated region corresponding to the client, the correct region having a range that includes the target log record;

wherein each owner page includes information about ownership of each of the log records in each of the at least one regions;

wherein the owner page further includes an owner page physical identifier identifying the location of the owner page in the transactional log;

wherein the owner page identifies at least two clients;

wherein each of the at least two clients is associated with a different application and wherein the transactional log includes log records from the at least two clients such the owner page identifies a first client associated with a first group of log records that are received from the first client and identifies a second client associated with a second group of log records that are received from the second client;

wherein the groups of log records are generated in response to the identity of the client that generated the record;

calculating a log block physical identifier associated with the log block containing the log record, the calculation being based on the owner page physical identifier;

mapping the virtual identifier to the log block physical identifier for the log record in the correct region using the owner page associated with the correct region, the physical identifier corresponding to the location of the log record in the transactional log; and

locating the log block containing the log record in the transactional log using the log block physical identifier.

14. The computer-implemented method of claim 13, wherein each of the virtual identifier and the physical identifier further comprises a value having at least a container identification field identifying a container file in which resides the target log record.

15. The computer-implemented method of claim 14, wherein each of the virtual identifier and the physical identifier further comprises a second value having at least a block-offset field identifying a log block within the container file within which the target log record resides.

16. The computer-implemented method of claim 15, wherein each of the virtual identifier and the physical identifier further comprises a third value having at least a record sequence number field identifying where within the target log block resides the log record.

17. The computer-implemented method of claim 13, wherein each of the virtual identifier and the physical identifier further comprises a log sequence number (LSN), the LSN having at least a container identifier, a sector-aligned block offset and a record sequence number.

18. The computer-implemented method of claim 13, wherein determining a correct region is performed using a backout/binary search.

19. The computer-implemented method of claim 18, wherein the backout/binary search includes a backout step and a binary search step.

20. The computer-implemented method of claim 13, wherein the information identifying a range of log blocks within the associated region corresponding to the client are contained in an owner referral.