Cluster-wide memory management using similarity-preserving signatures

• US 9,747,051 B2
• Filed: 03/30/2015
• Issued: 08/29/2017
• Est. Priority Date: 04/03/2014
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Stratoscale Ltd.
• Inventors: Hudzia, Benoit Guillaume Charles, Freiman, Rom
• Primary Examiner(s): Tsai, Sheng-Jen
• Application Number:
  US14/672,466
• Publication Number:
  US 20150286442A1
• Time in Patent Office: 883 Days
• Field of Search: 711170
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method includes, in a computing system that includes one or more compute nodes that run clients, defining memory chunks, each memory chunk including multiple memory pages accessed by a respective client. Respective similarity-preserving signatures are computed for one or more of the memory chunks. Based on the similarity-preserving signatures, an identification is made that first and second memory chunks differ in content in no more than a predefined number of memory pages with at least a predefined likelihood. Efficiency of access to the identified first and second memory chunks is improved.

Claims

1. A method, comprising:

in a computing system that includes a plurality of compute nodes that run clients, defining memory chunks, each memory chunk comprising multiple memory pages accessed by a respective client;

computing respective similarity-preserving signatures for two or more of the memory chunks;

identifying, based on the similarity-preserving signatures, memory chunks that differ in content in no more than a predefined number of memory pages with at least a predefined likelihood, and noting first and second clients on different computing nodes, accessing the identified memory chunks; and

migrating the first client to the compute node hosting the second client or to a compute node topologically adjacent in the computing system to the compute node hosting the second client, responsively to identifying the memory chunks that differ in content in no more than a predefined number of memory pages with at least a predefined likelihood.

2. The method according to claim 1, wherein computing a similarity-preserving signature for a memory chunk comprises computing a set of page signatures over the respective memory pages of the memory chunk.

3. The method according to claim 2, wherein identifying memory chunks that differ in content in no more than a predefined number of memory pages with at least the predefined likelihood comprises identifying that the similarity-preserving signatures of the memory chunks differ in no more than a given number of page signatures.

4. The method according to claim 1, further comprising finding in the identified memory chunks respective first and second memory pages that have identical content, and deduplicating the first and second memory pages.

5. The method according to claim 4, wherein computing a similarity-preserving signature for a memory chunk comprises computing a set of page signatures over the respective memory pages of the memory chunk, and wherein finding the first and second memory pages that have the identical content comprises comparing respective first and second hash values, different from the page signatures, computed over the first and second memory pages.

6. The method according to claim 1, wherein defining the memory chunks comprises classifying the memory pages into active and inactive memory pages, and including in the memory chunks only the inactive memory pages.

14. The method according to claim 1, wherein migrating the first client comprises migrating the first client to the compute node hosting the second client.

15. The method according to claim 1, wherein migrating the first client comprises migrating the first client to a compute node topologically adjacent to the compute node hosting the second client.

7. A computing system, comprising a plurality of compute nodes that comprise respective memories and respective processors, wherein the processors are configured to run clients that access memory pages stored in the memories, to define memory chunks, each memory chunk comprising multiple memory pages accessed by a respective client, to compute respective similarity-preserving signatures for two or more of the memory chunks, to identify, based on the similarity-preserving signatures, memory chunks that differ in content in no more than a predefined number of memory pages with at least a predefined likelihood, and noting first and second clients on different computing nodes, accessing the identified memory chunks, and to migrate the first client to the compute node hosting the second client or to a compute node topologically adjacent in the computing system to the compute node hosting the second client, responsively to identifying the memory chunks that differ in content in no more than a predefined number of memory pages with at least a predefined likelihood.

8. The system according to claim 7, wherein the processors are configured to compute a similarity-preserving signature for a memory chunk by computing a set of page signatures over the respective memory pages of the memory chunk.

9. The system according to claim 8, wherein the processors are configured to identify that the memory chunks that differ in content in no more than a predefined number of memory pages with at least the predefined likelihood, by identifying that the similarity-preserving signatures of the memory chunks differ in no more than a given number of page signatures.

10. The system according to claim 7, wherein the processors are configured to find in the identified memory chunks respective first and second memory pages that have identical content, and to deduplicate the first and second memory pages.

11. The system according to claim 10, wherein the processors are configured to compute a similarity-preserving signature for a memory chunk by computing a set of page signatures over the respective memory pages of the memory chunk, and to find the first and second memory pages that have the identical content by comparing respective first and second hash values, different from the page signatures, computed over the first and second memory pages.

12. The system according to claim 7, wherein the processors are configured to classify the memory pages into active and inactive memory pages, and to include in the memory chunks only the inactive memory pages.

13. 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 plurality of processors of respective compute nodes, cause the processors to run clients that access memory pages stored in memories of the compute nodes, to define memory chunks, each memory chunk comprising multiple memory pages accessed by a respective client, to compute respective similarity-preserving signatures for two or more of the memory chunks, to identify, based on the similarity-preserving signatures, memory chunks that differ in content in no more than a predefined number of memory pages with at least a predefined likelihood, and noting first and second clients on different computing nodes, accessing the identified memory chunks, and to migrate the first client to the compute node hosting the second client or to a compute node that are topologically adjacent in the computing system to the compute node hosting the second client, responsively to identifying the memory chunks that differ in content in no more than a predefined number of memory pages with at least a predefined likelihood.