# US 2017/0286005 A1 · Virtual bucket 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/0286005 A1
- Document ID: US20170286005A1
- Status: Published application
- Kind: A1
- Application number: 15/162,517
- Filed: 2016-05-23
- Published: 2017-10-05
- Earliest claimed: 2016-03-31
- 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/US20170286005A1

## CPC

- G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing
- G06F 12/0223: {User address space allocation, e.g. contiguous or non contiguous base addressing}
- G06F 2212/1016: Performance improvement
- G06F 2212/1044: Space efficiency improvement
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method of deduplicating memory in a memory module includes identifying a hash table array including 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 a plurality of virtual buckets each including some of the physical buckets, and each sharing at least one of the physical buckets with another of the virtual buckets, hashing a block of data according to a corresponding one of the hash functions to produce a hash value, determining whether an intended physical bucket has available space for the block of data according to the hash value, and determining whether a near-location physical bucket has available space for the block of data when the intended physical bucket does not have available space, the near-location physical bucket being in a same one of the virtual buckets as the intended physical bucket.

## Claims

### Claim 1

A method of deduplicating memory in a memory module, the method comprising:
identifying a hash table array comprising a plurality of hash tables each corresponding to a hash function, and each comprising physical buckets, each physical bucket comprising ways, and each being configured to store data;
identifying a plurality of virtual buckets each comprising some of the physical buckets, and each sharing at least one of the physical buckets with another of the virtual buckets;
hashing a block of data according to a corresponding one of the hash functions to produce a hash value;
determining whether an intended physical bucket of the physical buckets has available space for the block of data according to the hash value; and
determining whether one of near-location physical buckets of the physical buckets has available space for the block of data when the intended physical bucket does not have available space, the near-location physical buckets being in a same one of the virtual buckets as the intended physical bucket.

### Claim 2 (depends on 1)

The method of claim 1, further comprising storing the block of data in the intended physical bucket when the intended physical bucket has available space.

### Claim 3 (depends on 1)

The method of claim 1, further comprising storing the block of data in the one of the near-location physical buckets when one of the near-location physical buckets has available space and when the intended physical bucket does not have available space.

### Claim 4 (depends on 1)

The method of claim 1, further comprising hashing the block of data according to another one of the hash functions corresponding to another one of the hash tables of the hash table array when all of the physical buckets of the hash table associated with the corresponding one of the hash functions are full; and
storing the block of data in the another one of the hash tables.

### Claim 5 (depends on 1)

The method of claim 1, further comprising storing the block of data in a buffer memory when all of the physical buckets of all of the hash tables of the hash table array are full.

### Claim 6 (depends on 1)

The method of claim 1, further comprising associating each of the virtual buckets with a corresponding group of the physical buckets using a physical line ID (PLID) comprising a virtual bucket index.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
receiving a write request corresponding to the block of data;
discarding the write request when the block of data is stored in one of the virtual buckets having the intended physical bucket therein; and
updating a reference count line of the hash table.

### Claim 8

A memory module for deduplicating memory, the memory module comprising:
multiple hash tables in a hash table array, each of the hash tables comprising:
physical buckets each comprising ways for storing data; and
a plurality of virtual buckets each comprising some of the physical buckets;
a processor; and
wherein the memory module is configured to interface with a memory interface to retrieve the stored data, and to deliver the retrieved data to the memory interface.

### Claim 9 (depends on 8)

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

### Claim 10 (depends on 8)

The memory module of claim 8, wherein the memory module is configured to:
receive a write request from the memory interface to store a block of data in the hash table array;
perform a hash function on the block of data to determine an intended physical bucket of the physical buckets;
determine whether the block of data is previously stored in either the intended physical bucket, or in one of near-location physical buckets of the physical buckets located in any of the virtual buckets to which the intended physical bucket belongs; and
store the block of data in either the intended physical bucket or the one of the near-location physical buckets when the block of data is not previously stored therein, and when either the intended physical bucket or the one of the near-location physical buckets has available space.

### Claim 11 (depends on 10)

The memory module of claim 10, wherein the memory module further comprises a buffer memory for storing data when all of near-location physical buckets and the intended physical bucket are full.

### Claim 12 (depends on 10)

The memory module of claim 10, wherein the memory module is further configured to:
determine whether the near-location physical buckets and the intended physical bucket are full; and
perform another hash function on the block of data to determine another intended physical bucket in a different one of the hash tables than the intended physical bucket when all of the near-location physical buckets and the intended physical bucket are full.

### Claim 13 (depends on 12)

The memory module of claim 12, wherein the memory module further comprises a buffer memory for storing data when all of the physical buckets of all of the hash tables of the hash table array are full.

### Claim 14

A method of deduplicating memory in a memory module, the method comprising:
receiving a write request corresponding to a block of data to store the block of data in a hash table array comprising a plurality of hash tables, each hash table comprising physical buckets, each physical bucket comprising ways, and each physical bucket being associated with a virtual bucket comprising some of the physical buckets;
hashing the block of data according to a corresponding hash function to produce a hash value;
determining an intended physical bucket of the physical buckets based on the hash value;
determining whether an identical block of data is stored in the intended physical bucket; and
determining whether the identical block of data is stored in one of other physical buckets in a same one of the virtual buckets as the intended physical bucket when the identical block of data is not stored in the intended physical bucket.

### Claim 15 (depends on 14)

The method of claim 14, the method further comprising:
determining whether the intended physical bucket is full when the identical block of data is not stored in any of the other physical buckets in the same one of the virtual buckets as the intended physical bucket; and
storing the block of data in the intended physical bucket when the intended physical bucket is not full.

### Claim 16 (depends on 15)

The method of claim 15, the method further comprising:
determining whether all of the other physical buckets in the same one of the virtual buckets as the intended physical bucket are full when the intended physical bucket is full; and
storing the block of data in one of the physical buckets when one of the other physical buckets is not full.

### Claim 17 (depends on 16)

The method of claim 16, the method further comprising storing the block of data in a buffer memory when all of the other physical buckets in the same one of the virtual buckets as the intended physical bucket.

### Claim 18 (depends on 16)

The method of claim 16, the method further comprising:
determining whether all of the other physical buckets in a same one of the hash tables as the intended physical bucket are full when all of the other physical buckets are full;
determining whether another one of the hash tables of the hash table array has available space when all of the physical buckets in the same one of the hash tables are full;
hashing the block of data according to another hash function corresponding to the another one of the hash tables when the another one of the hash tables has available space; and
storing the block of data in the another one of the hash tables.

### Claim 19 (depends on 18)

The method of claim 18, the method further comprising storing the block of data in a buffer memory when no other one of the hash tables of the hash table array has available space.

### Claim 20 (depends on 14)

The method of claim 14, the method further comprising:
storing the block of data in one of the physical buckets of one of the virtual buckets including the intended physical bucket when the identical block of data is not stored therein;
generating a physical line ID (PLID) corresponding to the one of the physical buckets in which the block of data is stored; and
storing the PLID in an address lookup table.