Free-Space Reduction in Cached Database Pages
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19)
-
-
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.
-
Specification