Dynamic cache partition manager in heterogeneous virtualization cloud cache environment

• US 10,496,541 B2
• Filed: 02/07/2018
• Issued: 12/03/2019
• Est. Priority Date: 11/29/2017
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Yang, Zhengyu, Evans, T. David
• Primary Examiner(s): Dudek, Jr., Edward J
• Assistant Examiner(s): Verderamo, III, Ralph A
• Application Number:
  US15/891,350
• Publication Number:
  US 20190163636A1
• Time in Patent Office: 664 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/0848 Partitioned cache, e.g. separate instruction and operand caches
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 2009/45583 Memory management, e.g. access or allocation
• CPC Class Codes: G06F 2212/151 Emulated environment, e.g. virtual machine
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects

Abstract

A system is disclosed. The system may include a virtual machine server, which may include a processor, a memory, and at least two virtual machines that may be stored in the memory and executed by the processor. The virtual machine server may also include a virtual machine hypervisor to manage the operations of the virtual machine. The virtual machine server may also include a cache that may include at least one storage device. A Dynamic Cache Partition Manager (DCPM) may manage the partition of the cache into a performance guarantee zone, which may be partitioned into regions, and a spike buffer zone. The DCPM may include a reusability statistic calculator to calculate a reusability statistic, a comparator to compare the reusability statistic with a spike threshold, an access statistic calculator to calculate an access statistic, a spike data identifier to identify data in the spike buffer zone that satisfies the access statistic, and a cache partitioner to repartition the cache into a new performance guarantee zone and a second spike buffer zone for a new epoch, the second spike buffer zone is large enough to store the identified data.

Claims

1. A system, comprising:

a virtual machine server, including;

a processor;

a memory;

at least two virtual machines stored in the memory and running on the processor;

a virtual machine hypervisor to manage the operations of the at least two virtual machines; and

a cache including at least one storage device; and

a Dynamic Cache Partition Manager (DCPM) to manage the division of the cache into a performance guarantee zone and a spike buffer zone in each of a plurality of epochs, the performance guarantee zone including regions for each of the at least two virtual machines, the spike buffer zone storing workload spike data for the at least two virtual machines, the DCPM including;

a reusability statistic calculator to calculate a reusability statistic for data stored in the cache during a previous epoch;

a comparator to compare the reusability statistic with a spike threshold;

an access statistic calculator to calculate an access statistic for first data stored in a first performance guarantee zone during the previous epoch;

a spike data identifier to identify second data in a first spike buffer zone during the previous epoch that satisfies the access statistic; and

a cache partitioner to partition the cache into a second performance guarantee zone for a new epoch and a second spike buffer zone for the new epoch so that the second spike buffer zone is large enough to store the second data.

2. A system according to claim 1, wherein the DCPM is included in one of the virtual machine server and a data center server.

3. A system according to claim 2, wherein:

the DCPM further includes a percentage calculator to calculate a first percentage of hits in the performance guarantee zone during the previous epoch and a second percentage of hits in the spike buffer zone during the previous epoch; and

the cache partitioner is operative to partition the cache in the virtual machine server into a third performance guarantee zone and a third spike buffer zone proportional to the first percentage of hits and the second percentage of hits.

4. A system according to claim 2, wherein the reusability statistic calculator is operative to calculate the reusability statistic as a difference between a current number of bins in the cache in the previous epoch and a previous number of bins in the cache in a second previous epoch, divided by the current number of bins in the cache in the previous epoch.

5. A system according to claim 2, wherein:

the DCPM includes;

a selection statistic; and

an identifier to identify a percentage of the first data in the first performance guarantee zone during the previous epoch that satisfy the selection statistic for each virtual machine storing data in the first performance guarantee zone; and

the cache partitioner is operative to allocate a plurality of regions in the second performance guarantee zone for the new epoch in proportion to the percentages for each virtual machine.

6. A system according to claim 5, wherein:

the selection statistic includes a threshold number of bins; and

the identifier is operative to identify a subset of the plurality of bins with corresponding access counts that exceeds the threshold number of bins.

7. A system according to claim 5, wherein the regions for each of the at least two virtual machines in the first performance guarantee zone are initially allocated in proportion to at least two weights correlated to at least two service level agreements for the at least two virtual machines.

8. A system, comprising:

at least two virtual machine servers, each of the at least two virtual machine servers including;

a processor;

a memory;

at least one virtual machine; and

a virtual machine hypervisor to manage the operations of the at least one virtual machine;

at least one cache including at least one storage device; and

a Dynamic Cache Partition Manager (DCPM) Controller to manage the division of the at least one cache into a performance guarantee zone and a spike buffer zone in each of a plurality of epochs, the performance guarantee zone including regions for each of the at least one virtual machine on each of the at least two virtual machine servers, the spike buffer zone storing workload spike data for each of the at least one virtual machine on each of the at least two virtual machine servers, the DCPM Controller including;

a reusability statistic calculator to calculate a reusability statistic for data stored in the at least one cache during a previous epoch;

a comparator to compare the reusability statistic with a spike threshold;

an access statistic calculator to calculate an access statistic for first data stored in a first performance guarantee zone during the previous epoch;

a spike data identifier to identify second data in a first spike buffer zone during the previous epoch that satisfies the access statistic; and

a cache partitioner to partition the at least one cache into a second performance guarantee zone for a new epoch and a second spike buffer zone for the new epoch so that the second spike buffer zone is large enough to store the second data.

9. A system according to claim 8, further comprising a data center server, the data center server including the DCPM Controller.

10. A system according to claim 9, wherein the data center server further includes the at least one cache.

11. A system according to claim 9, wherein each of the at least two virtual machine servers includes a DCPM Daemon to monitor workloads for the at least one virtual machine.

12. A system according to claim 8, wherein:

the access statistic calculator is operative to calculate an average access count for the first data stored in the performance guarantee zone during the previous epoch; and

the spike data identifier is operative to identify the second data in the first spike buffer zone during the previous epoch with access counts greater than the average access count.

13. A system according to claim 8, wherein:

the DCPM Controller includes;

a selection statistic; and

an identifier to identify a percentage of the first data in the first performance guarantee zone during the previous epoch that satisfy the selection statistic for each virtual machine storing data in the first performance guarantee zone; and

the cache partitioner is operative to allocate a plurality of regions in the second performance guarantee zone for the new epoch in proportion to the percentages for each virtual machine.

14. A system according to claim 13, wherein:

the selection statistic includes a threshold number of bins; and

the identifier is operative to identify a subset of the plurality of bins with corresponding access counts that exceeds the threshold number of bins.

15. A method, comprising:

dividing a cache into a first performance guarantee zone and a first spike buffer zone;

determining a reusability statistic for data stored in the cache in a previous epoch; and

if the reusability statistic is at least as large as a spike threshold;

determining an access statistic for first data stored in the first performance guarantee zone in a previous epoch;

identifying second data stored in the first spike buffer zone during the previous epoch that satisfies the access statistic; and

redividing the cache into a second performance guarantee zone for a new epoch and a second spike buffer zone for the new epoch so that the second spike buffer zone is large enough to store the second data.

16. A method according to claim 15, wherein the cache is in one of a virtual machine server, a data center server, and a machine in a system including the virtual machine server and the data center server.

17. A method according to claim 15, wherein:

determining an access statistic for first data stored in the first performance guarantee zone in a previous epoch includes determining an average access count for first data stored in the first performance guarantee zone during the previous epoch; and

identifying second data stored in the first spike buffer zone during the previous epoch that satisfies the access statistic includes identifying the second data stored in the first spike buffer zone during the previous epoch with access counts greater than the average access count.

18. A method according to claim 17, wherein:

determining an average access count for first data stored in the performance guarantee zone during the previous epoch includes determining the average access count for first data stored in the performance guarantee zone during a plurality of previous epochs; and

identifying the second data stored in the first spike buffer zone during the previous epoch with access counts greater than the average access count includes identifying the second data stored in the first spike buffer zone during the plurality of previous epochs with access counts greater than the average access count.

19. A method according to claim 15, wherein, if the reusability statistic is less than the spike threshold:

determining a first percentage of hits in the performance guarantee zone during the previous epoch;

determining a second percentage of hits in the spike buffer zone during the previous epoch; and

redividing the cache into a third performance guarantee zone and a third spike buffer zone proportional to the first percentage of hits and the second percentage of hits.

20. A method according to claim 19, wherein:

determining a first percentage of hits in the performance guarantee zone during the previous epoch includes determining the first percentage of hits in the performance guarantee zone during a plurality of previous epochs; and

determining a second percentage of hits in the spike buffer zone during the previous epoch includes determining the second percentage of hits in the spike buffer zone during a plurality of previous epochs.

21. A method according to claim 15, wherein determining a reusability statistic for data stored in the cache in a previous epoch includes:

determining a difference between a current number of bins in the cache in the previous epoch and a previous number of bins in the cache in a second previous epoch; and

determining a ratio of the difference and the current number of bins in the cache in the previous epoch.

22. A method according to claim 21, wherein:

determining a difference between a current number of bins in the cache in the previous epoch and a previous number of bins in the cache in a second previous epoch includes determining a smallest difference between the current number of bins in the cache in the previous epoch and a plurality of previous numbers of bins in the cache in a plurality of previous epochs; and

determining a ratio of the difference and the current number of bins in the cache in the previous epoch includes determining the ratio of the smallest difference and the current number of bins in the cache in the previous epoch.

23. A method according to claim 15, further comprising:

determining a selection statistic for the first data in the first performance guarantee zone;

identifying a percentage of the first data in the first performance guarantee zone during the previous epoch that satisfy the selection statistic for each virtual machine storing data in the first performance guarantee zone; and

allocating a plurality of regions in the second performance guarantee zone for the new epoch in proportion to the percentages for each virtual machine.

24. A method according to claim 23, wherein:

determining a selection statistic for the first data in the first performance guarantee zone during the previous epoch includes determining a threshold number of bins; and

identifying a percentage of the first data in the first performance guarantee zone during the previous epoch that satisfy the selection statistic for each virtual machine storing data in the first performance guarantee zone includes;

sorting a plurality of bins in the first performance guarantee zone across all virtual machines by corresponding access counts; and

selecting a subset of the plurality of bins as sorted by corresponding access counts that exceeds the threshold number of bins.

25. A method according to claim 23, wherein identifying a percentage of the first data in the first performance guarantee zone during the previous epoch that satisfy the selection statistic for each virtual machine storing data in the first performance guarantee zone includes identifying the percentage of the first data in the first performance guarantee zone during a plurality of previous epochs that satisfy the selection statistic for each virtual machine storing data in the first performance guarantee zone.

26. A method according to claim 23, further comprising initially allocating the plurality of regions in proportion to a plurality of weights correlated to a plurality of service level agreements for the plurality of virtual machines.

27. A method according to claim 15, wherein dividing a cache into a first performance guarantee zone and a first spike buffer zone includes initially dividing the cache into equally sized first performance and first spike buffer zones.