Lightweight caching of transaction log for sequential access

• US 8,612,390 B2
• Filed: 05/02/2011
• Issued: 12/17/2013
• Est. Priority Date: 05/02/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Rui, Byrne, Peter
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US13/098,647
• Publication Number:
  US 20120284295A1
• Time in Patent Office: 960 Days
• Field of Search: None
• US Class Current: 707/640
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24552 Database cache management

Abstract

Searching cached log blocks. A method includes performing a first search on cached log blocks for a log block having a first log block ID. The log blocks are cached and organized into sequentially ordered log buffers in memory. Adjacent sequentially ordered log buffers are double linked to each other. Each log buffer includes a complete range of log blocks from a starting log block ID to an ending log block ID. As part of the first search one or more links are followed, forward and/or backward, to one or more other log buffers. The method may further include determining that the first log block is not found by following one or more links forward and/or backward to one or more other log buffers and as a result, follow one or more covering pointers to one or more log buffers to search for the first log block.

Claims

1. In a computing environment a method of searching cached log blocks, the method comprising:

performing a first search on cached log blocks cached in memory, wherein the log blocks are organized into sequentially ordered log buffers in memory, wherein adjacent sequentially ordered log buffers are linked to each other by one or more links between the ordered log buffers, and wherein each log buffer includes a complete range of log blocks from a starting log block identifier (ID) to an ending log block ID;

satisfying the first search by finding a first log block in a first log buffer, wherein the first log block has a first log block ID that falls into a complete range of log block IDs in the first log buffer;

performing a second search on the cached log blocks for a second log block having a second log block ID, the second search beginning at the first log buffer;

as part of the second search determining the second log block is not in the first log buffer and following the one or more links at least one of forward or backward to one or more other log buffers; and

determining that the second log block is not found by following one or more links at least one of forward or backward to one or more other log buffers and as a result following covering pointer from a log buffer to another covering log buffer to search for the second log block in the covering log buffer pointed to by the covering pointer, the covering log buffer covering one or more of the ordered log buffers by including all of the log blocks from the one or more of the ordered log buffers.

2. The method of claim 1, wherein adjacent log buffers are double linked in a double linked list.

3. The method of claim 2, wherein the first search is started at a head of the double linked list.

4. The method of claim 1, wherein the one or more covering pointers includes a pointer from a log buffer to a covering log buffer that has a range of log block IDs that entirely overlap the log buffer which the covering pointer is from.

5. The method of claim 1, wherein following one or more links at least one of forward or backward to one or more other log buffers comprises first traversing forward through log buffers not having the second log block ID, until a log buffer has only log block IDs that are greater than second log block ID or until all possible log buffers have been searched following the forward direction, and then traversing in reverse through log buffers not having the second log block ID, until a log buffer has only log block IDs that are less than the second log block ID or until all possible log buffers have been searched following the reverse direction.

6. The method of claim 1, wherein following one or more links at least one of forward or backward to one or more other log buffers comprises first traversing in reverse through log buffers not having the second log block ID, until a log buffer has only log block IDs that are less than second log block ID or until all possible log buffers have been searched following the reverse direction, and then traversing forward through log buffers not having the second log block ID, until a log buffer has only log block IDs that are greater than the second log block ID or until all possible log buffers have been searched following the forward direction.

7. The method of claim 1, further comprising determining that the second log block is not found by following a covering pointer to search for the second log block, and as a result, reading a log chunk containing the second log block from a log and caching the log chunk as a second log buffer.

8. The method of claim 7, further comprising, determining if the second log buffer covers any other cached log buffers in that the second log buffer includes all log blocks included in another log buffer, and if the second log buffer covers any other cached log buffers, then creating pointers from the covered log buffers to the second log buffer.

9. The method of claim 1, wherein following a covering pointer to search for the second log block comprises following a pointer stored in a list of covering pointers stored with a log buffer.

21. The method of claim 1, wherein the memory comprises the memory of a database management system and wherein the log blocks are written to the memory from a log that is stored in a persistent storage associated with the database management system.

10. One or more computer readable media comprising computer executable instructions that when executed by one or more processors cause one or more processors to perform the following:

performing a first search on cached log blocks for a log block having a first log block ID, wherein the log blocks are cached and organized into sequentially ordered log buffers in memory, wherein adjacent sequentially ordered log buffers are linked to each other by one or more links between the ordered log buffers, and wherein each log buffer includes a complete range of log blocks from a starting log block identifier (ID) to an ending log block ID;

as part of the first search searching a first log buffer and then following the one or more links at least one of forward or backward to one or more other log buffers; and

determining that the first log block is not found by following one or more links at least one of forward or backward to one or more other log buffers and as a result following a covering pointer from a log buffer to a covering log buffer to search for the first log block, the covering log buffer covering one or more of the ordered log buffers by including all of the log blocks from the one or more of the ordered log buffers.

11. The computer readable media of claim 10, wherein adjacent log buffers are double linked in a double linked list.

12. The computer readable media of claim 11, wherein the first search is started at a head of the double linked list.

13. The computer readable media of claim 10, wherein the first search is started at a last access point based on where a previous search ended.

14. The computer readable media of claim 10, wherein the one or more covering pointers are one or more pointers from a log buffer to one or more covering log buffers that have a range of log block IDs that entirely overlap the log buffer which the one or more cover pointers are from.

15. The computer readable media of claim 10, wherein following one or more links at least one of forward or backward to one or more other log buffers comprises first traversing forward through log buffers not having the first log block ID, until a log buffer has only log block IDs that are greater than first log block ID or until all possible log buffers have been searched following the forward direction, and then traversing in reverse through log buffers not having the first log block ID, until a log buffer has only log block IDs that are less than the first log block ID or until all possible log buffers have been searched following the reverse direction.

16. The computer readable media of claim 10, wherein following one or more links at least one of forward or backward to one or more other log buffers comprises first traversing in reverse through log buffers not having the first log block ID, until a log buffer has only log block IDs that are less than first log block ID or until all possible log buffers have been searched following the reverse direction, and then traversing forward through log buffers not having the first log block ID, until a log buffer has only log block IDs that are greater than the first log block ID or until all possible log buffers have been searched following the forward direction.

17. The computer readable media of claim 10, further comprising determining that the first log block is not found by following one or more covering pointers to search for the first log block, and as a result, reading a log chunk containing the first log block from a log and caching the log chunk as an added log buffer.

18. The computer readable media of claim 17, further comprising, determining if the added log buffer covers any other cached log buffers in that the added log buffer includes all log blocks included in another log buffer, and if the added log buffer covers any other cached log buffers, then creating pointers from the covered log buffers to the added log buffer.

19. The computer readable media of claim 10, wherein following one or more covering pointers to search for the first log block comprises following a pointer stored in a list of covering pointers stored with a log buffer.

20. A computing system comprising:

one or more processors;

one or more computer readable media coupled to the one or more processors, wherein the one or more computer readable media comprise computer executable instructions that when executed by one or more of the one or more processors, cause one or more processors implement functionality for performing a first search on cached log blocks for a log block having a first log block identifier (ID), wherein the log blocks are cached and organized into sequentially ordered log buffers in memory, wherein adjacent sequentially ordered log buffers are linked to each other in a linked list, and wherein each log buffer includes a complete range of log blocks from a starting log block ID to an ending log block ID, wherein the one or more computer readable media comprise;

computer executable instructions that when executed by one or more processors cause one or more processors to determine if a last access point exists tracking a last accessed log buffer based on a previous search of cached log buffers, and if a last accessed pointer to a last accessed log buffer exists, starting a search at the last accessed log buffer; and

if a last accessed pointer to a last accessed log buffer does not exist, starting a search at a head or tail of the linked list;

computer executable instructions that when executed by one or more processors cause one or more processors to perform searching functionality following one or more links forward or backward to one or more other log buffers searching for a log block with a log block ID and terminating a search and reporting a log block found if a log buffer is found where the log block ID is greater than or equal to a beginning log block ID for the log buffer and less than or equal to an ending log block ID for the log buffer; and

computer executable instructions that when executed by one or more processors cause one or more processors to perform searching functionality following one or more covering pointers to one or more log buffers to search for a log block, wherein each pointer is a pointer from a log buffer to a covering log buffer, wherein the covering log buffer has a range of log block IDs that overlap the log buffer which the pointer is from.