Multi-level buffer pool extensions

• US 9,235,531 B2
• Filed: 11/28/2011
• Issued: 01/12/2016
• Est. Priority Date: 03/04/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Celis, Pedro, Bradshaw, Dexter Paul, Krishnamurthy, Sadashivan, Reynya, Georgiy I., Zhang, Chengliang, Kodavalla, Hanumantha Rao
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Chang, Tian-Pong
• Application Number:
  US13/305,670
• Publication Number:
  US 20120072652A1
• Time in Patent Office: 1,506 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

A buffer manager that manages blocks of memory amongst multiple levels of buffer pools. For instance, there may be a first level buffer pool for blocks in first level memory, and a second level buffer pool for blocks in second level memory. The first level buffer pool evicts blocks to the second level buffer pool if the blocks are not used above a first threshold level. The second level buffer pool evicts blocks to a yet lower level if they have not used above a second threshold level. The first level memory may be dynamic random access memory, whereas the second level memory may be storage class memory, such as a solid state disk. By using such a storage class memory, the working block set of the buffer manager may be increased without resorting to lower efficiency random block access from yet lower level memory such as disk.

Claims

1. A computer program product comprising one or more computer-storage devices, excluding propagation signals, which store computer-executable instructions that, when executed by one or more processors of a computing system, cause the computing system to implement a method for using a buffer pool to manage blocks of memory among a first level memory, a second level memory, and a lower level of external memory, and where the computer-implemented method comprises acts of:

retrieving from an external memory blocks of memory comprised of data pages, and caching at least some of said data pages in a first level memory of a buffer pool, and caching at least some other data pages in a second level memory of the buffer pool, the first level memory providing faster average access speeds for data retrieval than the second level memory, and the second level memory providing faster average access speeds for data retrieval than the external memory;

determining at least first and second threshold values, the first threshold value defining a value which determines when a data page is to be evicted from the first level memory of the buffer pool to the second level memory of the buffer pool, and the second threshold value defining a value which determines when a data page is to be evicted from the second level memory of the buffer pool;

periodically scanning all data pages cached in the first and second levels of memory of the buffer pool and assigning a value to each scanned data page based on usage history of each scanned page as of the time scanned;

periodically comparing the assigned value of each said cached data page to the first and second threshold values;

scheduling for eviction cached data pages from the first level memory of the buffer pool to the second level memory of the buffer pool for those cached data pages not having an assigned value above said first threshold level;

scheduling for eviction cached data pages from the second level memory of the buffer pool to a lower level memory for those cached data pages not having an assigned value above said second threshold level;

determining if a data page scheduled for eviction is dirty because the page has been altered prior to eviction, and if so, scheduling a write operation for writing the dirty data page to external memory prior to unhashing a buffer descriptor and freeing a page frame for the dirty data page so that the dirty page is then evicted;

for each data page scheduled for eviction that is dirty, writing the dirty page to external memory and after the scheduled write operation has been completed, evicting the dirty page from the first or second level of memory of the buffer pool based on the assigned value for the evicted dirty page as compared to the first and second threshold values; and

for each data page scheduled for eviction that is not dirty, unhashing a buffer descriptor and freeing a page frame for each said data page that is not dirty, and evicting each such data page from the first or second level of memory of the buffer pool based on the assigned value of the evicted page that is not dirty, as compared to the first and second threshold values.

2. The computer program product of claim 1 where the computer system is comprised of a plurality of processors with at least one processor having multiple non-uniform memory access (NUMA) nodes, and wherein the computer-implemented method further comprises an act of partitioning the first level memory of the buffer pool among said nodes.

3. The computer program product of claim 1, wherein the first level memory of the buffer pool is dynamic random access memory (DRAM).

4. The computer program product of claim 1, wherein the second level memory of the buffer pool is storage class memory (SCM).

5. The computer program product of claim 1, wherein the second level memory of the buffer is at least one solid state disk.

6. The computer program product of claim 1, wherein the lower level memory is the external memory.

7. The computer program product of claim 1, wherein the lower level memory is a disk.

8. The computer program product of claim 1, wherein in addition to completing the scheduled write operation of the dirty page to external memory, the computer-implemented method further comprises an act of performing a further, parallel write of the dirty page to the second level memory of the buffer pool.

9. A computer-implemented method for using a buffer pool to manage blocks of memory among a first level memory, a second level memory, and a lower level of memory, the computer-implemented method comprising acts of:

retrieving from an external memory blocks of memory comprised of data pages, and caching at least some of said data pages in a first level memory of a buffer pool, and caching at least some other data pages in a second level memory of the buffer pool, the first level memory providing faster average access speeds for data retrieval than the second level memory, and the second level memory providing faster average access speeds for data retrieval than the external memory;

determining at least first and second threshold values, the first threshold value defining a value which determines when a data page is to be evicted from the first level memory of the buffer pool to the second level memory of the buffer pool, and the second threshold value defining a value which determines when a data page is to be evicted from the second level memory of the buffer pool;

periodically scanning all data pages cached in the first and second levels of memory of the buffer pool and assigning a value to each scanned data page based on usage history of each scanned page as of the time scanned;

periodically comparing the assigned value of each said cached data page to the first and second threshold values;

scheduling for eviction cached data pages from the first level memory of the buffer pool to the second level memory of the buffer pool for those cached data pages not having an assigned value above said first threshold level;

scheduling for eviction cached data pages from the second level memory of the buffer pool to a lower level memory of the buffer for those cached data pages not having an assigned value above said second threshold level;

determining if a data page scheduled for eviction is dirty because it has been altered prior to eviction, and if so, scheduling a write operation for writing the dirty data page to external memory prior to unhashing a buffer descriptor and freeing a page frame for the dirty data page so that the dirty page is then evicted;

for each data page scheduled for eviction that is dirty, after scheduled write operation has been completed, evicting the dirty page from the first or second level of memory of the buffer pool based on the assigned value of that page as compared to the first and second threshold values; and

for each data page scheduled for eviction that is not dirty, unhashing a buffer descriptor and freeing a page frame for each said data page that is not dirty, and evicting each such data page from the first or second level of memory of the buffer pool based on the assigned value of that page as compared to the first and second threshold values.

10. The computer-implemented method of claim 9 further comprising an act of partitioning the first level memory of the buffer pool among multiple non-uniform memory access (NUMA) nodes of at least one processor.

11. The computer-implemented method of claim 9 wherein in addition to completing the scheduled write operation of the dirty page to external memory, the computer-implemented method further comprises an act of performing a further, parallel write of the dirty page to the second level memory of the buffer pool.

12. The computer-implemented method of claim 9 wherein the lower level memory is the external memory.

13. The computer-implemented method of claim 9, wherein the lower level is

a third level memory of the buffer pool, and wherein the computer-implemented method further comprises acts of:

determining a third threshold value defining a value which determines when a data page is to be evicted from the third level memory of the buffer pool to a further lower level memory if a data page is assigned a value that is below the third threshold value; and

scheduling for eviction cached data pages from the third level memory of the buffer pool to the further lower level memory for those cached data pages not having an assigned value above said third threshold value.

14. The computer-implemented method of claim 9, wherein the first level memory of the buffer pool is dynamic random access memory (DRAM).

15. The computer-implemented method of claim 9, wherein the second level memory of the buffer pool is storage class memory (SCM).

16. The computer-implemented method of claim 15, wherein the second level memory of the buffer is at least one solid state disk.

17. A computer system comprising:

one or more processors;

a lower level of external memory for storage of memory blocks comprising one or more data pages;

a buffer pool comprised of a first level memory and a second level memory, the first level memory providing faster average access speeds for data retrieval than the second level memory, and the second level memory providing faster average access speeds for data retrieval than the external memory; and

one or more computer-storage devices which store computer-executable instructions that, when executed by one or more processors of a computing system, cause the computer system to implement a method for using the buffer pool to manage blocks of memory among the first level memory, the second level memory, and the lower level of external memory, and where the computer-implemented method comprises acts of;

retrieving from the external memory blocks of memory comprised of data pages, and caching at least some of said data pages in the first level memory of a buffer pool, and caching at least some other data pages in the second level memory of the buffer pool;

determining at least first and second threshold values, the first threshold value defining a value which determines when a data page is to be evicted from the first level memory of the buffer pool to the second level memory of the buffer pool, and the second threshold value defining a value which determines when a data page is to be evicted from the second level memory of the buffer pool;

periodically scanning all data pages cached in the first and second levels of memory of the buffer pool and assigning a value to each scanned data page based on usage history of each scanned page as of the time scanned;

periodically comparing the assigned value of each said cached data page to the first and second threshold values;

scheduling for eviction cached data pages from the first level memory of the buffer pool to the second level memory of the buffer pool for those cached data pages not having an assigned value above said first threshold level;

scheduling for eviction cached data pages from the second level memory of the buffer pool to a lower level memory of the buffer for those cached data pages not having an assigned value above said second threshold level;

determining if a data page scheduled for eviction is dirty because the pate has been altered prior to eviction, and if so, scheduling a write operation for writing the dirty data page to external memory prior to unhashing a buffer descriptor and freeing a page frame for the dirty data page so that the dirty page is then evicted;

for each data page scheduled for eviction that is dirty, after the scheduled write operation has been completed, evicting the dirty page from the first or second level of memory of the buffer pool based on the assigned value for that page as compared to the first and second threshold values; and

for each data page scheduled for eviction that is not dirty, unhashing a buffer descriptor and freeing a page frame for each said data page that is not dirty, and evicting each such data page from the first or second level of memory of the buffer pool based on the assigned value for that page as compared to the first and second threshold values.

18. The computer system of claim 17, wherein the buffer pool has a third level memory, and wherein the computer-implemented method further comprises acts of:

determining a third threshold value defining a value which determines when a data page is to be evicted from the third level memory of the buffer pool to a the lower level memory if a data page is assigned a value that is below the third threshold value; and

scheduling for eviction cached data pages from the third level memory of the buffer pool to the lower level memory for those cached data pages not having an assigned value above said third threshold value.