System and method for locating log records in multiplexed transactional logs

• US 20030225585A1
• Filed: 05/31/2002
• Published: 12/04/2003
• 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
• Granted Patent: US 7,689,626 B2
• Time in Patent Office: Days
• US Class Current: 705/1
• 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;

determining a correct region in the transactional log from among the plurality of regions using a set of owner pages, each owner page in the set having an association with a region in the transactional log; and

mapping the virtual identifier to a 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.

2. The computer-implemented method of claim 1, wherein the owner page associated with the correct region includes an owner referral.

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.

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 5, wherein the owner page further includes an owner page physical identifier identifying the location of the owner page in the transactional log.

7. The computer-implemented method of claim 6, further comprising:

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

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

8. 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.

9. The computer-implemented method of claim 8, 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.

10. The computer-implemented method of claim 9, 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.

12. The computer-implemented method of claim 11, 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.

13. The computer-implemented method of claim 12, 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.

14. The computer-implemented method of claim 13, 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.

11. 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.

15. 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, the target log record being indicated by a virtual identifier;

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;

comparing the virtual identifier to a list of physical identifiers that have previously been returned to the client until a matching physical identifier is located, the matching physical identifier corresponding to the virtual identifier.

16. The computer-implemented method of claim 15, 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.

17. The computer-implemented method of claim 16, 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.

18. The computer-implemented method of claim 17, 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.

19. The computer-implemented method of claim 15, 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.

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

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

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

23. In a transactional logging system, a computer-readable medium encoded with a data structure, comprising:

a client data field containing data representing a plurality of clients associated with a transactional log, the transactional log containing a plurality of log blocks, each of the log blocks being identified by a different virtual identifier and being associated with one of the clients;

a range data field containing data representing a plurality of virtual identifier ranges, each virtual identifier range being associated with one of the clients and describing a range of virtual identifiers for log blocks associated with the client.

24. The computer-readable medium of claim 23, wherein the virtual identifier comprises a container identification field identifying a container file in which resides the log block.

25. The computer-readable medium of claim 24, wherein the virtual identifier further comprises a block-offset field identifying a log block within the container file.

26. The computer-readable medium of claim 24, wherein the data structure is an owner referral.

27. In a transactional logging system, a computer-readable medium encoded with a data structure, comprising:

a multiplicity of sector records, each sector record including;

a client data field that identifies particular client that owns the sector record;

a log record offset that locates the sector record within a sequence of sector records of a log block;

wherein each sector record is associated with a physical identifier and wherein a first physical identifier for a first sector record corresponds to a virtual identifier of another sector record in the multiplicity of sector records, the virtual identifier of the other sector record being different from the first physical identifier of the first sector record.

28. The computer-readable medium of claim 27, 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.

29. The computer-readable medium of claim 28, wherein each of the virtual identifier and the physical identifier further comprises a second value having at least a block-offset field.

30. The computer-readable medium of claim 29, wherein each of the virtual identifier and the physical identifier further comprises a third value having at least a record sequence number field.

31. The computer-readable medium of claim 27, wherein the data structure is an owner array.