Free-Space Reduction in Cached Database Pages

• US 20100306444A1
• Filed: 05/26/2009
• Published: 12/02/2010
• Est. Priority Date: 05/26/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gossage, Matthew, Shirley, Brett A., Burchall, Laurion
• Granted Patent: US 8,108,587 B2
• Time in Patent Office: Days
• US Class Current: 711/6
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 2212/465 Structured object, e.g. database record
• CPC Class Codes: G06F 2212/466 Metadata, control data

Abstract

A computing system stores a database comprising pages. Each of the pages is the same size. When a page is requested, a block of virtual memory addresses is associated with the page and a set of physical data storage locations is committed to the block of virtual memory addresses. A copy of the page is then stored into the set of physical data storage locations. Physical data storage locations committed to the virtual memory addresses associated with available free space in the copy of the page are deallocated, thereby allowing reuse of these physical data storage locations. A reference to the copy of the page is then returned.

Claims

1. A method of managing a database cache, the method comprising:

storing a database in one or more persistent computer-readable data storage media, the database comprising a set of pages, each page in the set of pages having a fixed size, each of the pages containing substantive data;

receiving, at a computing system, a page read request for a requested page in the set of pages;

reserving, by the computing system, an initial block of virtual memory addresses having the fixed size;

allocating, by the computing system, a set of physical data storage locations committed to the initial block of virtual memory addresses;

reading, by the computing system, the requested page from the persistent computer-readable data storage media;

storing, by the computing system, a copy of the requested page into the set of physical data storage locations, a minimum commit size being a minimum number of bytes that an operating system of the computing system is configured to allocate, the copy of the requested page comprising the substantive data of the requested page and available free space, the size of the available free space being equal to the fixed size minus a smallest multiple of the minimum commit size that is greater than a size of the substantive data, the substantive data being associated with a first set of virtual memory addresses within the initial block of virtual memory addresses, the available free space being associated with a second set of virtual memory addresses within the initial block of virtual memory addresses;

after storing the copy of the requested page, deallocating, by the computing system, an available set of physical data storage locations committed to the second set of virtual memory addresses; and

returning, by the computing system, a reference to the copy of the requested page as a response to the page read request.

2. The method of claim 1, wherein the substantive data comprises a plurality of nodes and metadata, the metadata comprises a tag array, the tag array comprising offset values, the offset values indicating virtual memory addresses of the nodes relative to an initial virtual memory address of the copy of the requested page.

3. The method of claim 2,

wherein the metadata comprises a header;

and

wherein the method further comprises;

prior to deallocating the available set of physical data storage locations;

moving, by the computing system, the nodes within the copy of the requested page such that free space adjacent to one or more of the nodes is reduced; and

updating, by the computing system, the offset values such that the offset values indicate virtual memory addresses of the nodes relative to the initial virtual memory address of the copy of the requested page.

4. The method of claim 3,

wherein the header stores an available free space value indicating the size of the available free space;

and

wherein the method further comprises determining, at the computing system, comparing the available free space value to the minimum commit size; and

wherein deallocating the available set of physical data storage locations comprises deallocating, by the computing system, the available set of physical data storage locations when the computing system determines that the available free space value is greater than the minimum commit size.

5. The method of claim 1 further comprising:

receiving, at the computing system, a database entry read request for a requested database entry in the database; and

in response to the database entry read request for the requested database entry, generating, by the computing system, the page read request.

6. The method of claim 5, wherein the substantive data of the requested page comprises a plurality of nodes, each of the nodes of the requested page containing a key value and a reference to a page in the set of pages.

7. The method of claim 6, further comprising:

after returning the reference to the copy of the requested page, identifying, by the computing system, a target node in the copy of the requested page, the target node being one of the nodes in the copy of the requested page containing a key value associated with a requested value;

generating, at the computing system, a target page read request for a target page, the target page indicated by the target node; and

receiving, at the computing system, a reference to a copy of the target page as a response to the target page read request.

8. The method of claim 7 further comprising:

determining, by the computing system, whether the target page is an interior page or a data page; and

in response to determining that the target page is a data page;

identifying, by the computing system, the requested database entry in the target page; and

returning, by the computing system, a reference to the requested database entry as a response to the database entry read request.

9. The method of claim 7, wherein the requested database entry is an e-mail message.

10. The method of claim 1, further comprising:

in response to receiving the page read request;

determining whether the database cache stores the copy of the requested page; and

returning the reference to the copy of the requested page in response to determining that the database cache stores the copy of the requested page.

11. The method of claim 10, further comprising:

automatically selecting, by the computing system, a copy of a selected page of the database in the database cache; and

automatically removing, by the computing system, the copy of the selected page from the database cache.

12. The method of claim 1 further comprising after deallocating the available set of physical data storage locations:

receiving, at the computing system, a request to write target data to the copy of the requested page;

allocating, by the computing system, an additional set of physical data storage locations to the second set of virtual memory addresses; and

after allocating the additional set of physical data storage locations, writing, by the computing system, the target data to the copy of the requested page.

13. The method of claim 12,

wherein the substantive data comprises a plurality of nodes and a tag array, the tag array comprising offset values, the offset values indicating virtual memory addresses of the nodes relative to an initial virtual memory address of the copy of the requested page;

and

wherein the method further comprises after allocating the additional set of physical data storage locations to the second contiguous block of virtual memory addresses, moving, by the computing system, the tag array in the copy of the requested page such that a last virtual memory address associated with the tag array is a last virtual memory address associated with the copy of the requested page.

14. The method of claim 13 further comprising:

before allocating the additional set of physical data storage locations to the second set of virtual memory addresses, receiving, at the computing system, a request for a write latch on the initial block of virtual memory addresses;

after receiving the request for the write latch, obtaining, by the computing system, the write latch; and

after writing the target data to the copy of the requested page, releasing, by the computing system, the write latch.

15. The method of claim 1, wherein the computing system comprises an electronic computing device, the electronic computing device comprising a processing unit that executes instructions stored in a data storage system, execution of the instructions causing the electronic computing device to perform the actions of claim 1, the data storage system comprising at least one computer-readable data storage medium.

16. A computing system comprising:

a processing unit comprising at least one integrated circuit; and

a data storage system comprising at least one computer-readable data storage medium, the data storage system storing;

a database in one or more persistent computer-readable data storage media in the data storage system, the database comprising a set of pages, each page in the set of pages having a fixed size, each of the pages containing substantive data;

a buffer manager comprising software instructions that, when executed by the processing unit, cause the computing system to;

receive a page read request for a requested page in the set of pages;

reserve an initial block of virtual memory addresses having the fixed size;

allocate a set of physical data storage locations committed to the initial block of virtual memory addresses;

read the requested page from the persistent computer-readable data storage media;

store a copy of the requested page into the set of physical data storage locations;

determine, after storing the copy of the requested page into the set of physical data storage locations, whether a size of available free space in the copy of the requested page is greater than a minimum commit size, the size of the available free space being equal to the fixed size minus a smallest multiple of the minimum commit size that is greater than a size of the substantive data, the minimum commit size being a minimum number of bytes that an operating system of the computing system is configured to allocate;

reorganize, when the size of the available free space is greater than the minimum commit size, the copy of the requested page such that the substantive data in the copy of the requested page is associated with a first contiguous block of virtual memory addresses within the initial block of virtual memory addresses and the available free space is associated with a second contiguous block of virtual memory addresses within the initial block of virtual memory addresses;

deallocate, after reorganizing the copy of the requested page, an available set of physical data storage locations committed to the second contiguous block of virtual memory addresses; and

return, after deallocating the available set of physical data storage locations, a reference to the copy of the requested page as a response to the page read request.

17. The computing system of claim 16,

wherein the substantive data in the copy of the requested page comprises a plurality of nodes, a header and a tag array, the header storing an available free space value indicating the size of the available free space, the tag array comprising offset values, the offset values indicating virtual memory addresses of the nodes relative to an initial virtual memory address of the copy of the requested page;

wherein the instructions that cause the computing system to reorganize the copy of the requested page cause the computing system to;

move the nodes within the copy of the requested page such that free space adjacent to one or more of the nodes is reduced; and

update the offset values of the tag array such that the offset values indicate virtual memory addresses of the nodes relative to the initial virtual memory address of the copy of the requested page; and

wherein the instructions that cause the computing system to determine whether the size of the available free space is greater than the minimum commit size comprises using the available free space value to determine the size of the free space.

18. The computing system of claim 16,

wherein the substantive data in the copy of the requested page comprises a plurality of nodes, each of the nodes in the requested page containing a key value and a reference to a page in the set of pages;

and

wherein the data storage system further comprises;

a tree manager comprising instructions that, when executed by the processing unit, cause the computing system to;

receive a database entry read request for a requested database entry in the database;

generate, in response to the database entry read request for the requested database entry, the page read request;

identify, after the buffer manager causes the computing system to return the reference to the copy of the requested page, a target node in the copy of the requested page, the target node being one of the nodes in the copy of the requested page specifying a key value associated with a requested value;

generate a target page read request for a target page, the target page indicated by the target node;

receive a reference to a copy of the target page as a response to the target page read request;

determine whether the target page is an interior page or a data page; and

in response to determining that the target page is a data page;

identify the requested database entry in the target page; and

return a reference to the requested database entry in response to the database entry read request.

19. The computing system of claim 16, wherein after deallocating the available set of physical data storage locations, the instructions of the buffer manager further cause the computing system to:

receive a request for a write latch on the block of virtual memory addresses associated with the copy of the requested page;

obtain the write latch in response to receiving the request for the write latch;

allocate, after obtaining the write latch, an additional set of physical data storage locations committed to the second contiguous block of virtual memory addresses;

receive, after allocating the additional set of physical data storage locations committed to the second contiguous block of virtual memory addresses, a request to write target data to the copy of the requested page;

write, in response to receiving the request to write the target data to the copy of the requested page, the target data to the copy of the requested page; and

release the write latch after writing the target data to the copy of the requested page.

20. A computer-readable data storage medium storing:

instructions that, when executed by a processing unit of a computing system, cause the computing system to store a database in one or more persistent computer-readable data storage media, the database comprising a set of pages, each page in the set of pages having a fixed size of 32 kilobytes, the set of pages comprising a set of data pages and an interior page, each of the pages containing substantive data comprising a plurality of nodes, free space, and metadata, each of the nodes in the interior page containing a key value and a reference to a page in the set of pages containing a database entry having a field that specifies the key value, each of the nodes in each of the data pages containing a database entry, each of the database entries being e-mail messages, the free space consisting of a block of available free space and a block of unavailable free space;

an application comprising instructions that, when executed by the processing unit, cause the computing system to generate a query specifying criteria to process a web content request received by the computing system;

a database manager comprising instructions that, when executed by the processing unit, cause the computing system to;

process the criteria to identify a requested value of a particular field of the one or more database entries in the database; and

generate a database entry read request specifying the requested value;

a tree manager comprising instructions that, when executed by the processing unit, cause the computing system to;

receive the database entry read request from the database manager; and

generate, in response to the database entry read request, a second read request, the second read request indicating a requested page in the set of pages;

a page manager comprising instructions that, when executed by the processing unit, cause the computing system to;

receive the second read request; and

generate, in response to the second read request, a third read request, the third read request indicating the requested page;

a buffer manager comprising instructions that, when executed by the processing unit, cause the computing system to perform the following in response to receiving the third read request;

reserve an initial block of virtual memory addresses having the fixed size;

allocate a set of physical data storage locations committed to the initial block of virtual memory addresses;

read the requested page from the persistent computer-readable data storage media;

store a copy of the requested page into the set of physical data storage locations;

determine, after storing the copy of the requested page into the set of physical data storage locations, whether a size of the block of available free space in the copy of the requested page is greater than a minimum commit size, the size of the block of available free space being equal to the size of the requested page minus a smallest multiple of the minimum commit size that is greater than a size of the substantive data, the minimum commit size being a minimum number of bytes that an operating system of the computing system is configured to allocate;

reorganize, when the size of the free space is greater than the minimum commit size, the copy of the requested page such that the substantive data is associated with a first contiguous block of virtual memory addresses within the initial block of virtual memory addresses and the block of available free space is associated with a second contiguous block of virtual memory addresses within the initial block of virtual memory addresses;

deallocate, after reorganizing the copy of the requested page, an available set of physical data storage locations committed to the second contiguous block of virtual memory addresses; and

return, after deallocating the available set of physical data storage locations, a reference to the copy of the requested page as a response to the third read request;

wherein the instructions of the page manager, when executed by the processing unit, further cause the computing system to;

receive, in response to the third read request, the reference to the copy of the requested page; and

return the reference to the copy of the requested page as a response to the second read request;

wherein the instructions of the tree manager, when executed by the processing unit, further cause the computing system to;

receive, in response to the second read request, the reference to the copy of the requested page;

determine, after receiving the reference to the copy of the interior page, whether the requested page is the interior page;

identify, when the requested page is the interior page, a target node in the requested page, the target node being one of the nodes in the requested page having a highest-order key value less than the requested value;

generate a fourth read request, the fourth read request indicating a target page indicated by the target node;

receive a reference to a copy of the target page;

identify the requested database entry in the target page; and

return a reference to the requested database entry in response to the database entry read request;

wherein the instructions of the database manager, when executed by the processing unit, further cause the computing system to provide the reference to the requested database entry as a response to the query; and

wherein the instructions of the application, when executed by the processing unit, further cause the computing system to use the requested database entry to process the web content request.