Method and apparatus for maximized dedupable memory

• US 10,437,785 B2
• Filed: 11/27/2017
• Issued: 10/08/2019
• Est. Priority Date: 03/29/2016
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jiang, Dongyan, Peng, Qiang, Zheng, Hongzhong
• Primary Examiner(s): Bataille, Pierre Miche
• Application Number:
  US15/823,549
• Publication Number:
  US 20180081897A1
• Time in Patent Office: 680 Days
• Field of Search: 711108
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems

Abstract

A memory system is disclosed. The memory system may include a Big Hash Table and a Little Hash Table. The memory system may also include an Overflow Region and a Translation Table to map a logical address to a Physical Line Identifier (PLID), which may include a region identifier and a physical address.

Claims

1. A memory system, comprising:

memory to store data;

a Big Hash Table stored in the memory, the Big Hash Table including a number of buckets and a first number of ways and including a first portion of the memory that includes a first number of bytes that is a first power of 2;

a Little Hash Table stored in the memory, the Little Hash Table including the number of buckets and a second number of ways and including a second portion of the memory that includes a second number of bytes that is a second power of 2;

an Overflow Region stored in the memory, the Overflow Region including a third portion of the memory; and

a Translation Table to map a logical address to a Physical Line Identifier (PLID), the PLID including a region identifier and a physical address.

2. A memory system according to claim 1, wherein the region identifier includes a first bit indicating that the PLID identifies data in the Big Hash Table.

3. A memory system according to claim 2, wherein the physical address includes a row index and a column index.

4. A memory system according to claim 1, wherein the region identifier includes:

a first bit indicating that the PLID does not identify data in the Big Hash Table; and

a second bit indicating whether the PLID identifies data in the Little Hash Table or the Overflow Region.

5. A memory system according to claim 1, wherein the Little Hash Table may grow dynamically.

6. A memory system according to claim 1, further comprising a signature table stored in the memory, the signature table storing a plurality of signatures of data stored in the Big Hash Table and the Little Hash Table,

wherein the signature table may prevent storing multiple data with a common signature in a row in either the Big Hash Table or the Little Hash Table.

7. A memory system according to claim 1, further comprising a signature table stored in the memory, the signature table storing a plurality of signatures of data stored in the Big Hash Table and the Little Hash Table,

wherein the signature table may prevent storing multiple data with a common signature in a row in either the Big Hash Table or the Little Hash Table.

8. A method operable in a memory controller, comprising:

receiving a logical address from a processor;

mapping the logical address to a Physical Line Identifier (PLID) using a Translation Table, the PLID including a region identifier and a physical address;

determining if the physical address is in a Big Hash Table, a Little Hash Table, or an Overflow Region in a memory using the region identifier; and

accessing data in the memory using the physical address.

9. A method according to claim 8, wherein determining if the physical address is in a Big Hash Table, a Little Hash Table, or an Overflow Region in a memory using the region identifier includes determining that the physical address is in the Big Hash Table if a first bit in the region identifier is not set.

10. A method according to claim 8, wherein determining if the physical address is in a Big Hash Table, a Little Hash Table, or an Overflow Region in a memory using the region identifier includes determining that that the physical address is in the Little Hash Table if a first bit in the region identifier is set and a second bit in the region identifier is not set.

11. A method according to claim 8, wherein determining if the physical address is in a Big Hash Table, a Little Hash Table, or an Overflow Region in a memory using the region identifier includes determining that the physical address is in the Overflow Region if a first bit in the region identifier is set and a second bit in the region identifier is set.

12. A method according to claim 8, wherein accessing data in the memory using the physical address includes:

determining a row index and a column index from the physical address; and

accessing the data in one of the Big Hash Table and the Little Hash Table using the row index and the column index.

13. A method according to claim 12, wherein accessing the data in one of the Big Hash Table and the Little Hash Table using the row index and the column index includes searching nearby entries in the Little Hash Table if the data is not found in the Little Hash Table at the row index and the column index.

14. A method according to claim 8, further comprising:

determining that the Little Hash Table is approaching capacity; and

increasing a size of the Little Hash Table while reducing a size of the Overflow Region.

15. A method according to claim 14, wherein increasing a size of the Little Hash Table includes increasing a number of columns in the Little Hash Table.

16. An embodiment of the inventive concept includes an article, comprising a non-transitory storage medium, the non-transitory storage medium having stored thereon instructions that, when executed by a machine, result in:

receiving a logical address from a processor;

mapping the logical address to a Physical Line Identifier (PLID) using a Translation Table, the PLID including a region identifier and a physical address;

determining if the physical address is in a Big Hash Table, a Little Hash Table, or an Overflow Region in a memory using the region identifier; and

accessing data in the memory using the physical address.

17. An article according to claim 16, wherein determining if the physical address is in a Big Hash Table, a Little Hash Table, or an Overflow Region in a memory using the region identifier includes determining that the physical address is in the Big Hash Table if a first bit in the region identifier is not set.

18. An article according to claim 16, wherein determining if the physical address is in a Big Hash Table, a Little Hash Table, or an Overflow Region in a memory using the region identifier includes determining that that the physical address is in the Little Hash Table if a first bit in the region identifier is set and a second bit in the region identifier is not set.

19. An article according to claim 16, wherein determining if the physical address is in a Big Hash Table, a Little Hash Table, or an Overflow Region in a memory using the region identifier includes determining that the physical address is in the Overflow Region if a first bit in the region identifier is set and a second bit in the region identifier is set.

20. An article according to claim 16, wherein accessing data in the memory using the physical address includes:

determining a row index and a column index from the physical address; and

accessing the data in one of the Big Hash Table and the Little Hash Table using the row index and the column index.