Probabilistic deduplication-aware workload migration

• US 9,886,301 B2
• Filed: 03/31/2016
• Issued: 02/06/2018
• Est. Priority Date: 05/04/2015
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Stratoscale Ltd.
• Inventors: Hudzia, Benoit Guillaume Charles, Solganik, Alexander
• Primary Examiner(s): Truong, Camquy
• Application Number:
  US15/086,123
• Publication Number:
  US 20160328257A1
• Time in Patent Office: 677 Days
• Field of Search: 718 1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2009/45583 Memory management, e.g. access or allocation
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

A computing method includes running, on a plurality of compute nodes, multiple workloads that access respective sets of memory pages. Respective bitmaps are calculated for at least some of the workloads, wherein (i) a bitmap of a workload is statistically indicative of a cardinality of the set of memory pages used by the workload, (ii) a union of two or more bitmaps is statistically indicative of the cardinality of a union of the sets of memory pages used by the two or more corresponding workloads, and (iii) an intersection of first and second bitmaps is statistically indicative of an overlap between respective first and second sets of memory pages used by the corresponding workloads. A decision is made to migrate a selected workload from a source compute node to a destination compute node, based on one or more of the bitmaps.

Claims

1. A computing method, comprising:

running, on a plurality of compute nodes, multiple workloads that access respective sets of memory pages;

calculating respective bitmaps for at least some of the workloads, wherein;

(i) a bitmap of a workload is statistically indicative of a cardinality of the set of memory pages used by the workload;

(ii) a union of two or more bitmaps is statistically indicative of the cardinality of a union of the sets of memory pages used by the two or more corresponding workloads; and

(iii) an intersection of first and second bitmaps is statistically indicative of an overlap between respective first and second sets of memory pages used by the corresponding workloads; and

deciding to migrate a selected workload from a source compute node to a destination compute node, based on one or more of the bitmaps,

wherein deciding to migrate the selected workload comprises choosing one or both of the selected workload and the destination compute node, based on a selection criterion that is defined over one or more of the bitmaps and aims to maximize the overlap between the memory pages used by the selected workload and the memory pages used by existing workloads on the destination compute node.

2. The method according to claim 1, wherein the selection criterion aims to maximize a number of the memory pages that are used by the selected workload and can be deduplicated on the destination compute node following migration of the selected workload.

3. The method according to claim 1, wherein calculating the bitmaps comprises calculating a node-level bitmap for the destination compute node by calculating the union of the bitmaps of the existing workloads on the destination node, and wherein deciding to migrate the workload comprises evaluating the selection criterion based on the node-level bitmap of the destination compute node.

4. The method according to claim 1, wherein calculating the bitmaps comprises calculating HyperLogLog (HLL) bitmaps.

5. The method according to claim 1, wherein deciding to migrate the selected workload is performed in response to detecting that the source compute node is overloaded.

6. A computing method, comprising:

running, on a plurality of compute nodes, multiple workloads that access respective sets of memory pages;

calculating respective bitmaps for at least some of the workloads, wherein;

(i) a bitmap of a workload is statistically indicative of a cardinality of the set of memory pages used by the workload;

(ii) a union of two or more bitmaps is statistically indicative of the cardinality of a union of the sets of memory pages used by the two or more corresponding workloads; and

(iii) an intersection of first and second bitmaps is statistically indicative of an overlap between respective first and second sets of memory pages used by the corresponding workloads; and

deciding to migrate a selected workload from a source compute node to a destination compute node, based on one or more of the bitmaps,

wherein deciding to migrate the workload comprises choosing one or both of the source compute node and the selected workload, based on a selection criterion that is defined over one or more of the bitmaps and aims to minimize the overlap between the memory pages used by the selected workload and the memory pages used by existing workloads on the source compute node.

7. The method according to claim 6, wherein the selection criterion aims to minimize a number of the memory pages that are used by the existing workloads on the source compute node and can no longer be deduplicated on the source compute node following migration of the selected workload.

8. The method according to claim 6, wherein calculating the bitmaps comprises calculating a node-level bitmap for the source compute node by calculating the union of the bitmaps of the existing workloads on the source node, and wherein deciding to migrate the workload comprises evaluating the selection criterion based on the node-level bitmap of the destination compute node.

9. A computing method, comprising:

running, on a plurality of compute nodes, multiple workloads that access respective sets of memory pages;

calculating respective bitmaps for at least some of the workloads, wherein;

(i) a bitmap of a workload is statistically indicative of a cardinality of the set of memory pages used by the workload;

(ii) a union of two or more bitmaps is statistically indicative of the cardinality of a union of the sets of memory pages used by the two or more corresponding workloads; and

(iii) an intersection of first and second bitmaps is statistically indicative of an overlap between respective first and second sets of memory pages used by the corresponding workloads; and

deciding to migrate a selected workload from a source compute node to a destination compute node, based on one or more of the bitmaps,

wherein calculating a bitmap for a given workload comprises calculating respective hash values over at least some of the memory pages used by the given workload, and calculating the bitmap based on the hash values, and

wherein calculating the bitmap comprises evaluating the bitmap over the hash values of only the memory pages that are modified by the given workload less frequently than a predefined modification rate.

10. A computing apparatus, comprising:

an interface for communicating with a plurality of compute nodes, which run multiple workloads that access respective sets of memory pages; and

a processor, which is configured to receive from the compute nodes bitmaps calculated for at least some of the workloads, wherein (i) a bitmap of a workload is statistically indicative of a cardinality of the set of memory pages used by the workload, (ii) a union of two or more bitmaps is statistically indicative of the cardinality of a union of the sets of memory pages used by the two or more corresponding workloads, and (iii) an intersection of first and second bitmaps is statistically indicative of an overlap between respective first and second sets of memory pages used by the corresponding workloads, and to decide to migrate a selected workload from a source compute node to a destination compute node based on one or more of the bitmaps,

wherein the processor is configured to choose one or both of the selected workload and the destination compute node, based on a selection criterion that is defined over one or more of the bitmaps and aims to maximize the overlap between the memory pages used by the selected workload and the memory pages used by existing workloads on the destination compute node.

11. The apparatus according to claim 10, wherein the selection criterion aims to maximize a number of the memory pages that are used by the selected workload and can be deduplicated on the destination compute node following migration of the selected workload.

12. The apparatus according to claim 10, wherein the processor is configured to calculate a node-level bitmap for the destination compute node by calculating the union of the bitmaps of the existing workloads on the destination node, and to evaluate the selection criterion based on the node-level bitmap of the destination compute node.

13. The apparatus according to claim 10, wherein the bitmaps comprise HyperLogLog (HLL) bitmaps.

14. The apparatus according to claim 10, wherein the processor is configured to decide to migrate the selected workload in response to detecting that the source compute node is overloaded.

15. A computing apparatus, comprising:

an interface for communicating with a plurality of compute nodes, which run multiple workloads that access respective sets of memory pages; and

a processor, which is configured to receive from the compute nodes bitmaps calculated for at least some of the workloads, wherein (i) a bitmap of a workload is statistically indicative of a cardinality of the set of memory pages used by the workload, (ii) a union of two or more bitmaps is statistically indicative of the cardinality of a union of the sets of memory pages used by the two or more corresponding workloads, and (iii) an intersection of first and second bitmaps is statistically indicative of an overlap between respective first and second sets of memory pages used by the corresponding workloads, and to decide to migrate a selected workload from a source compute node to a destination compute node based on one or more of the bitmaps,

wherein the processor is configured to choose one or both of the source compute node and the selected workload, based on a selection criterion that is defined over one or more of the bitmaps and aims to minimize the overlap between the memory pages used by the selected workload and the memory pages used by existing workloads on the source compute node.

16. The apparatus according to claim 15, wherein the selection criterion aims to minimize a number of the memory pages that are used by the existing workloads on the source compute node and can no longer be deduplicated on the source compute node following migration of the selected workload.

17. The apparatus according to claim 15, wherein the processor is configured to calculate a node-level bitmap for the source compute node by calculating the union of the bitmaps of the existing workloads on the source node, and to evaluate the selection criterion based on the node-level bitmap of the destination compute node.

18. A computing apparatus, comprising:

an interface for communicating with a plurality of compute nodes, which run multiple workloads that access respective sets of memory pages; and

a processor, which is configured to receive from the compute nodes bitmaps calculated for at least some of the workloads, wherein (i) a bitmap of a workload is statistically indicative of a cardinality of the set of memory pages used by the workload, (ii) a union of two or more bitmaps is statistically indicative of the cardinality of a union of the sets of memory pages used by the two or more corresponding workloads, and (iii) an intersection of first and second bitmaps is statistically indicative of an overlap between respective first and second sets of memory pages used by the corresponding workloads, and to decide to migrate a selected workload from a source compute node to a destination compute node based on one or more of the bitmaps,

wherein the processor is configured to calculate a bitmap for a given workload by calculating respective hash values over at least some of the memory pages used by the given workload, and calculating the bitmap based on the hash values, and

wherein the processor is configured to evaluate the bitmap over the hash values of only the memory pages that are modified by the given workload less frequently than a predefined modification rate.

19. A computing system, comprising:

a plurality of compute nodes, which are configured to run multiple workloads that access respective sets of memory pages, and to calculate respective bitmaps for at least some of the workloads, wherein (i) a bitmap of a workload is statistically indicative of a cardinality of the set of memory pages used by the workload, (ii) a union of two or more bitmaps is statistically indicative of the cardinality of a union of the sets of memory pages used by the two or more corresponding workloads, and (iii) an intersection of first and second bitmaps is statistically indicative of an overlap between respective first and second sets of memory pages used by the corresponding workloads; and

a processor, which is configured to receive the bitmaps from the compute nodes and to decide, based on one or more of the bitmaps, to migrate a selected workload from a source compute node to a destination compute node,

wherein the processor is configured to choose one or both of the selected workload and the destination compute node, based on a selection criterion that is defined over one or more of the bitmaps and aims to maximize the overlap between the memory pages used by the selected workload and the memory pages used by existing workloads on the destination compute node.