Using access-frequency hierarchy for selection of eviction destination

• US 9,971,698 B2
• Filed: 02/08/2016
• Issued: 05/15/2018
• Est. Priority Date: 02/26/2015
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Stratoscale Ltd.
• Inventors: Rapoport, Mike, Gordon, Abel, Maislos, Ariel
• Primary Examiner(s): Farrokh, Hashem
• Application Number:
  US15/017,687
• Publication Number:
  US 20160253265A1
• Time in Patent Office: 827 Days
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 2212/604 Details relating to cache allocation
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0649 Lifecycle management
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

A method includes, in a computing system in which one or more workloads access memory pages in a memory, defining multiple memory-page lists, and specifying for each memory-page list a respective different scanning period. Access frequencies, with which the memory pages are accessed, are estimated continually by periodically checking the memory pages on each memory-page list in accordance with the scanning period specified for that memory-page list, and re-assigning the memory pages to the memory-page lists based on the estimated access frequencies. One or more of the memory pages are evicted from the memory based on a history of assignments of the memory pages to the memory-page lists.

Claims

1. A method, comprising:

in a computing system in which one or more workloads access memory pages in a memory, defining multiple memory-page lists, and specifying for each memory-page list a respective different scanning period;

continually estimating access frequencies with which the memory pages are accessed, by periodically checking the memory pages on each memory-page list in accordance with the scanning period specified for that memory-page list, and re-assigning the memory pages to the memory-page lists based on the estimated access frequencies;

selecting one or more memory pages for eviction from the memory to one or more of multiple storage tiers;

selecting for each of the one or more memory pages selected for eviction, a storage tier to which to evict the memory page, from among the multiple storage tiers, based on a history of the assignments of the memory page to the memory page lists; and

evicting the one or more of the memory pages from the memory to the respective selected storage tiers,

wherein selecting for each of the one or more memory pages selected for eviction, a storage tier comprises determining for evicted memory pages an expected time duration before it will be required in the main memory and selecting a storage tier responsively to the expected time duration.

2. The method according to claim 1, wherein checking and re-assigning the memory pages comprise, in response to identifying that a memory page, which is currently assigned to a first memory-page list having a first scanning period, has been accessed since it was previously checked, re-assigning the memory page to a second memory-page list having a second scanning period larger than the first scanning period.

3. The method according to claim 1, wherein checking and re-assigning the memory pages comprise, in response to identifying that a memory page, which is currently assigned to a first memory-page list having a first scanning period, has not been accessed since it was previously checked, re-assigning the memory page to a second memory-page list having a second scanning period smaller than the first scanning period.

4. The method according to claim 3, wherein the second scanning period is a smallest scanning period among the specified scanning periods.

5. The method according to claim 1, wherein evicting the memory pages comprises evicting a memory page in response to identifying that the memory page is assigned to a memory-page list having a smallest scanning period among the specified scanning periods, and was not accessed for more than a predefined time period.

6. The method according to claim 1, wherein selecting the storage tier comprises calculating a weighted average of numbers of times that the memory page was assigned to the respective memory-page lists, and selecting the storage tier based on the weighted average.

7. The method according to claim 1, wherein selecting the storage tier comprises applying a mapping that chooses the storage tier as a function of the history of the assignments, and comprising evaluating a quality of previous selections of the storage tiers, and adapting the mapping based on the evaluated quality.

8. The method according to claim 1, further comprising determining after evicted pages were returned to memory, an actual time duration spent by the evicted page in the selected storage tier, and determining whether the selected storage tier would have been selected for the evicted page if the actual time duration was known.

9. The method according to claim 1, wherein re-assigning the memory pages to the memory-page lists based on the estimated access frequencies comprises assigning rarely-accessed memory pages to lists indicating a more often scanning, while frequently-accessed memory pages are assigned to lists indicating less often scanning.

10. A computing system, comprising:

a memory for storing memory pages; and

a processor, which is configured to run one or more workloads that access the memory pages in the memory, to define multiple memory-page lists and specify for each memory-page list a respective different scanning period, to continually estimate access frequencies with which the memory pages are accessed, by periodically checking the memory pages on each memory-page list in accordance with the scanning period specified for that memory-page list, to re-assign the memory pages to the memory-page lists based on the estimated access frequencies, to select one or more memory pages for eviction from the memory to one or more of multiple storage tiers, and to evict the one or more of the memory pages from the memory based on a history of assignments of the memory pages to the memory-page lists,

wherein the processor is configured to select for each of the one or more memory pages selected for eviction, a storage tier for evicting the memory page, from among the multiple storage tiers, based on the history of the assignments of the memory page to the memory page lists,

wherein selecting for each of the one or more memory pages selected for eviction, a storage tier comprises determining for evicted memory pages an expected time duration before it will be required in the main memory and selecting a storage tier responsively to the expected time duration.

11. The computing system according to claim 10, wherein, in response to identifying that a memory page, which is currently assigned to a first memory-page list having a first scanning period, has been accessed since it was previously checked, the processor is configured to re-assign the memory page to a second memory-page list having a second scanning period larger than the first scanning period.

12. The computing system according to claim 10, wherein, in response to identifying that a memory page, which is currently assigned to a first memory-page list having a first scanning period, has not been accessed since it was previously checked, the processor is configured to re-assign the memory page to a second memory-page list having a second scanning period smaller than the first scanning period.

13. The computing system according to claim 12, wherein the second scanning period is a smallest scanning period among the specified scanning periods.

14. The computing system according to claim 10, wherein the processor is configured to evict a memory page in response to identifying that the memory page is assigned to a memory-page list having a smallest scanning period among the specified scanning periods, and was not accessed for more than a predefined time period.

15. The computing system according to claim 10, wherein the processor is configured to calculate a weighted average of numbers of times that the memory page was assigned to the respective memory-page lists, and to select the storage tier based on the weighted average.

16. The computing system according to claim 10, wherein the processor is configured to select the storage tier by applying a mapping that chooses the storage tier as a function of the history of the assignments, to evaluate a quality of previous selections of the storage tiers, and to adapt the mapping based on the evaluated quality.

17. A computer software product, the product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a processor that runs one or more workloads that access memory pages in a memory, cause the processor to define multiple memory-page lists, to specify for each memory-page list a respective different scanning period, to continually estimate access frequencies with which the memory pages are accessed, by periodically checking the memory pages on each memory-page list in accordance with the scanning period specified for that memory-page list, to re-assign the memory pages to the memory-page lists based on the estimated access frequencies, to select one or more memory pages for eviction from the memory to one or more of multiple storage tiers, to select for each of the one or more memory pages selected for eviction, a storage tier to which to evict the memory page, from among the multiple storage tiers, based on a history of the assignments of the memory page to the memory page lists, and to evict the one or more of the memory pages from the memory to the respective selected storage tiers,

wherein selecting for each of the one or more memory pages selected for eviction, a storage tier comprises determining for evicted memory pages an expected time duration before it will be required in the main memory and selecting a storage tier responsively to the expected time duration.