# US 2017/0286003 A1 · Optimized hopscotch multiple hash tables for efficient memory in-line deduplication application

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

- Number: US 2017/0286003 A1
- Document ID: US20170286003A1
- Status: Published application
- Kind: A1
- Application number: 15/161,136
- Filed: 2016-05-20
- Published: 2017-10-05
- Earliest claimed: 2016-03-29
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Frederic Sala; Chaohong Hu; Hongzhong Zheng; Dimin Niu; Mu-Tien Chang
- Web page: https://patentgrep.com/patent/US20170286003A1

## CPC

- G06F 12/1018: involving hashing techniques, e.g. inverted page tables
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/0641: {De-duplication techniques}
- G06F 3/065: {Replication mechanisms}
- G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays}
- G06F 12/0223: {User address space allocation, e.g. contiguous or non contiguous base addressing}
- G06F 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F 15/7821: {Tightly coupled to memory, e.g. computational memory, smart memory, processor in memory}
- G06F 16/00: Information retrieval; Database structures therefor; File system structures therefor
- G11C 29/74: {using duplex memories, i.e. using dual copies}
- G06F 12/1027: using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/401: Compressed data
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

A method of memory deduplication includes identifying hash tables each corresponding to a hash function, and each including physical buckets, each physical bucket including ways and being configured to store data, identifying virtual buckets each including some physical buckets, and each sharing a physical bucket with another virtual bucket, identifying each of the physical buckets having data stored thereon as being assigned to a single virtual bucket, hashing a data line according to a hash function to produce a hash value, determining whether a corresponding virtual bucket has available space for a block of data according to the hash value, sequentially moving data from the corresponding virtual bucket to an adjacent virtual bucket when the corresponding virtual bucket does not have available space until the corresponding virtual bucket has space for the block of data, and storing the block of data in the corresponding virtual bucket.

## Claims

### Claim 1

A method of memory deduplication, the method comprising:
identifying a plurality of hash tables each corresponding to a hash function, and each comprising physical hash buckets, each physical hash bucket comprising ways and being configured to store data;
identifying a plurality of virtual buckets each comprising some of the physical hash buckets, and each sharing at least one of the physical hash buckets with another of the virtual buckets;
identifying each of the physical hash buckets having data stored thereon as being assigned to a single corresponding one of the virtual buckets;
hashing a data line according to a corresponding one of the hash functions to produce a hash value;
determining whether a corresponding one of the virtual buckets of a corresponding hash table has available space for a block of data according to the hash value;
sequentially moving data from the corresponding one of the virtual buckets to an adjacent one of the virtual buckets when the corresponding one of the virtual buckets does not have available space until the corresponding one of the virtual buckets has space for the block of data; and
storing the block of data in the corresponding one of the virtual buckets.

### Claim 2 (depends on 1)

The method of claim 1, further comprising updating an address lookup table memory to change one or more lookup addresses corresponding to the moved block of data.

### Claim 3 (depends on 1)

The method of claim 1, wherein each of the hash tables further comprises a reference count line, a signature line, and a hopword line.

### Claim 4 (depends on 3)

The method of claim 3, further comprising generating a hopword vector for indicating which of the physical hash buckets containing data correspond to which of the virtual buckets.

### Claim 5 (depends on 4)

The method of claim 4, wherein generating the hopword vector comprises, for each of the virtual buckets, using a binary indicator to indicate whether each of the physical hash buckets of a respective one of the virtual buckets contains a block of data in association with the respective one of the virtual buckets.

### Claim 6 (depends on 3)

The method of claim 3, further comprising generating a hopword value comprising log 2(H) bits per physical hash bucket for indicating which of the physical hash buckets containing data correspond to which of the virtual buckets.

### Claim 7 (depends on 6)

The method of claim 6, wherein generating the hopword value comprises generating a two-dimensional array comprising quasi-addresses for each of the physical hash buckets containing data at locations representing associated pairs of the physical hash buckets and the virtual buckets.

### Claim 8 (depends on 1)

The method of claim 1, wherein the hash table is stored on a volatile memory.

### Claim 9 (depends on 8)

The method of claim 8, wherein the volatile memory comprises dynamic random-access memory (DRAM).

### Claim 10 (depends on 1)

The method of claim 1, further comprising indexing the hash table with a physical line ID (PLID) comprising a virtual bucket utilization value field of log 2(H) bits, and comprising a value equal to a number of data blocks in a corresponding one of the virtual buckets.

### Claim 11 (depends on 10)

The method of claim 10, further comprising increasing the virtual bucket utilization value field by one, when writing an object to the corresponding one of the virtual buckets.

### Claim 12 (depends on 1)

The method of claim 1, further comprising storing the block of data in a buffer memory when the corresponding hash table is full.

### Claim 13

A deduplication dynamic random-access memory (DRAM) memory module for deduplicating memory by reducing duplicate blocks of data in memory, the deduplication DRAM memory module comprising:
a hash table memory for storing deduplicated blocks of data;
an address lookup table memory (ALUTM) for storing addresses corresponding to the deduplicated blocks of data; and
a processor for receiving read requests to enable the deduplication DRAM memory module to retrieve the blocks of data from the hash table memory and to export the blocks of data, and for receiving write requests to enable the deduplication DRAM memory module to store the blocks of data in the hash table memory.

### Claim 14 (depends on 13)

The deduplication DRAM memory module of claim 13, wherein the hash table memory comprises a three-dimensional array of hash tables stored therein, each of the hash tables comprising physical hash buckets, each physical hash bucket comprising ways and being configured to store the deduplicated blocks of data.

### Claim 15 (depends on 14)

The deduplication DRAM memory module of claim 14, wherein each of the hash tables further comprises a plurality of virtual buckets each comprising two or more of the physical hash buckets.

### Claim 16 (depends on 15)

The deduplication DRAM memory module of claim 15, wherein the deduplication DRAM memory module is configured to move the deduplicated blocks of data between adjacent ones of the virtual buckets within a corresponding one of the hash tables.

### Claim 17 (depends on 13)

The deduplication DRAM memory module of claim 13, wherein the deduplication DRAM memory module is able to perform data deduplication without externally supplied commands.

### Claim 18 (depends on 13)

The deduplication DRAM memory module of claim 13, wherein the deduplication DRAM memory module further comprises a buffer memory for storing data when the hash table memory is full.

### Claim 19

A deduplication DRAM memory module for reducing duplicate blocks of data in memory, the deduplication DRAM memory module comprising:
a three-dimensional array of hash tables stored therein, each of the hash tables comprising physical hash buckets, each physical hash bucket comprising ways and being configured to store the blocks of data;
a processor; and
memory, wherein the memory has stored thereon instructions that, when executed by the processor, causes the deduplication DRAM memory module to move a previously stored deduplicated block of data between adjacent virtual buckets of one of the hash tables, each of the virtual buckets comprising two or more of the physical hash buckets.

### Claim 20 (depends on 19)

The deduplication DRAM memory module of claim 19, wherein the memory has further stored thereon instructions that, when executed by the processor, causes the deduplication DRAM memory module to store incoming data in one of the virtual buckets from which the previously stored deduplicated block of data was moved.