# US 2021/0334024 A1 · Transactional Memory Based Memory Page De-Duplication

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0334024 A1
- Document ID: US20210334024A1
- Status: Published application
- Kind: A1
- Application number: 16/860,132
- Filed: 2020-04-28
- Published: 2021-10-28
- Earliest claimed: 2020-04-28
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Qi Zhang; Gong Su; Arun Kwangil Iyengar
- Web page: https://patentgrep.com/patent/US20210334024A1

## CPC

- G06F 3/0641: {De-duplication techniques}
- G06F 9/467: {Transactional memory (G06F9/528 takes precedence)}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0664: {at device level, e.g. emulation of a storage device or system}
- G06F 3/0683: {Plurality of storage devices}
- G06F 9/526: {Mutual exclusion algorithms}
- G06F 12/1018: involving hashing techniques, e.g. inverted page tables
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system, computer program product, and method are provided to de-duplicate one or more memory pages in parallel. Multiple de-duplication processes operate in parallel, with each de-duplication process operatively coupled to at least two data structures, and further leveraging transactional memory to mitigate access conflicts.

## Claims

### Claim 1

A computer system to de-duplicate one or more memory pages comprising:
a processing unit operating coupled to memory and an operating system;
a de-duplication mechanism operatively coupled to the processing unit, the de-duplication mechanism to support first and second de-duplication processes operatively coupled to first and second elements, respectively, and configured to operate in parallel;
the de-duplication mechanism operatively coupled to the processing unit, via one or more of first and second de-duplication processes, to identify a first memory page and selectively de-duplicate the first memory page, including:
search a first data structure for a first matching entry representing a relatively identical memory page to the first memory page:
in response to identification of the first matching entry relatively identical to the first memory page, represent the first memory page and the first matching entry in the first data structure;
search a second data structure for a second matching entry relatively identical to the first memory page in response to absence of the first matching entry in the first data structure, and:
in response to absence of the first memory page, insert the first memory page in the second data structure; and
in response to presence of the first memory page, remove the first memory page from the second data structure, and represent the first memory page with a corresponding matching entry in the first data structure; and
the de-duplication mechanism to leverage transactional memory to resolve concurrent access of the first and second data structures.

### Claim 2 (depends on 1)

The computer system of claim 1, further comprising the de-duplication mechanism to create a first hash code representation of one or more memory pages local to the first element, and create a second hash code representation of one or more memory pages local to the second element.

### Claim 3 (depends on 1)

The computer system of claim 1, wherein the first and second data structures are disjoint-set data structures, each representing a dynamic collection and supporting operations to create a new set containing a single element, return a representative element, and replace a first element in a first set and a second element in a second set with a union in the dynamic collection.

### Claim 4 (depends on 2)

The computer system of claim 2, wherein the relatively identical memory page includes application of a modulus operation to the first memory page based on a corresponding data structure size, and the de-duplication mechanism to compare a value from the applied modulus operation to one or more entries in the corresponding data structure.

### Claim 5 (depends on 4)

The computer system of claim 4, wherein selective de-duplication of the first memory page includes a two phase comparison wherein the value from the applied modulus operation is a first phase comparison, and further comprising the de-duplication mechanism to apply a second phase comparison responsive to relatively matching the first memory page with a page entry in one of the data structures, the second phase including comparison of content of the first memory page with content of the page entry in one of the data structures.

### Claim 6 (depends on 1)

The computer system of claim 1, wherein the first and second elements collaborate to de-duplicate memory pages, the collaboration including intra-element and inter-element memory page de-duplication.

### Claim 7 (depends on 1)

The computer system of claim 1, wherein the first and second data structures are shared with the de-duplication mechanism.

### Claim 8

A computer program product comprising a computer readable storage device having computer readable program code embodied therewith, the program code being executable by a processing unit to de-duplicate one or more memory pages, the computer program product comprising:
a de-duplication mechanism supporting first and second de-duplication processes operatively coupled to first and second elements, respectively, the first and second de-duplication processes configured to operate in parallel;
program code to identify a first memory page and selectively de-duplicate the first memory page, including:
search a first data structure for a first matching entry representing a relatively identical memory page to the first memory page, and in response to identification of the first matching entry relatively identical to the first memory page, representing the first memory page and the first matching entry in the first data structure;
search a second data structure for a second matching entry relatively identical to the first memory page in response to absence of the first matching entry in the first data structure, and:
in response to absence of the first memory page, insert the first memory page in the second data structure; and
in response to presence of the first memory page, remove the first memory page from the second data structure, and represent the first memory page with a corresponding matching entry in the first data structure; and
program code to leverage transactional memory to resolve concurrent access of the first and second data structures.

### Claim 9 (depends on 8)

The computer program product of claim 8, further comprising program code to create a first hash code representation of one or more memory pages local to the first element, and create a second hash code representation of one or more memory pages local to the second element.

### Claim 10 (depends on 8)

The computer program product of claim 8, wherein the first and second data structures are disjoint-set data structures, each representing a dynamic collection and supporting operations to create a new set containing a single element, returning a representative element, and replacing a first element in a first set and a second element in a second set with a union in the dynamic collection.

### Claim 11 (depends on 9)

The computer program product of claim 9, wherein the relatively identical memory page includes program code to apply a modulus operation to the first memory page based on a corresponding data structure size, and program code compare a value from the applied modulus operation to one or more entries in the corresponding data structure.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein the selective de-duplication of the first memory page includes a two phase comparison wherein the value from the applied modulus operation is a first phase comparison, and further comprising program code to apply a second phase comparison responsive to relatively matching the first memory page with a page entry in one of the data structures, the second phase including comparison of content of the first memory page with content of the page entry in one of the data structures.

### Claim 13 (depends on 8)

The computer program product of claim 8, wherein the program code supports collaboration of the first and second elements to de-duplicate memory pages, the collaboration including intra-element and inter-element memory page de-duplication.

### Claim 14

A method comprising:
in a computer system configured with a de-duplication mechanism supporting first and second de-duplication processes operatively coupled to first and second elements, respectively, the two first and second de-duplication processes configured to operate in parallel;
identifying a first memory page and selectively de-duplicating the first memory page, including:
searching the first data structure for a first matching entry representing a relatively identical memory page to the first memory page, the relatively identical memory page operatively coupled to one of the first or second elements, and
in response to identification of the first matching entry relatively identical to the first memory page, representing the first memory page and the first matching entry in the first data structure;
searching the second data structure for a second matching entry relatively identical to the first memory page in response to absence of the first matching entry in the first data structure, and:
in response to absence of the first memory page, inserting the first memory page in the second data structure; and
in response to presence of the first memory page, removing the first memory page from the second data structure, and representing the first memory page with a corresponding matching entry in the first data structure; and
leveraging transactional memory for resolving concurrent access of the first and second data structures.

### Claim 15 (depends on 14)

The method of claim 14, further comprising creating a first hash code representation of one or more memory pages local to the first element, and creating a second hash code representation of one or more memory pages local to the second element.

### Claim 16 (depends on 14)

The method of claim 14, wherein the first and second data structures are disjoint-set data structures, each representing a dynamic collection and supporting operations to create a new set containing a single element, returning a representative element, and replacing a first element in a first set and a second element in a second set with a union in the dynamic collection.

### Claim 17 (depends on 15)

The method of claim 15, wherein the relatively identical memory page includes applying a modulus operation to the first memory page based on a corresponding data structure size, and comparing a value from the applied modulus operation to one or more entries in the corresponding data structure.

### Claim 18 (depends on 17)

The method of claim 17, wherein selectively de-duplicating the first memory page includes a two phase comparison wherein the value from the applied modulus operation is a first phase comparison, and further comprising applying a second phase comparison responsive to relatively matching the first memory page with a page entry in one of the data structures, the second phase including comparing content of the first memory page with content of the page entry in one of the data structures.

### Claim 19 (depends on 14)

The method of claim 14, wherein the first and second elements collaborate to de-duplicate memory pages, the collaboration including intra-element and inter-element memory page de-duplication.

### Claim 20 (depends on 14)

The method of claim 14, wherein the first and second data structures are shared with the de-duplication mechanism.
