Reordered local data deduplication in storage devices

• US 10,409,518 B1
• Filed: 04/20/2017
• Issued: 09/10/2019
• Est. Priority Date: 04/20/2017
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Xie, Hongmei, Alhussien, AbdelHakim, Sankaranarayanan, Sundararajan, Tang, Alex, Baryudin, Leonid, Haratsch, Erich Franz
• Primary Examiner(s): Mackall, Larry T
• Application Number:
  US15/493,102
• Time in Patent Office: 873 Days
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A device may include a SSD having multiple storage units and a deduplication control circuit configured to determine whether selected data content to be stored is a duplicate of previous data content already in a first buffer of data buffered to be stored in a set of storage units. The deduplication circuit may be further configured to, based on a determination that the selected data content is a duplicate of first previous data content already buffered in the first buffer, instead of buffering another copy of the selected data content, buffer a first header including a first pointer that associates the first header with the first previous data content already buffered in the first buffer. The deduplication circuit may also be configured to reorder the first buffer such that individual data contents in the first buffer are grouped near headers associated with the individual data contents.

Claims

1. A device comprising:

a solid state data storage device (SSD) having multiple storage units, the SSD including;

a deduplication control circuit configured to;

determine whether selected data content to be stored is a duplicate of previous data content already in a first buffer of data buffered to be stored in a set of storage units of the multiple storage units of the SSD;

based at least in part on a determination that the selected data content is a duplicate of first previous data content already buffered in the first buffer, instead of buffering another copy of the selected data content, buffer a first header including a first pointer that associates the first header with the first previous data content already buffered in the first buffer; and

reorder the first buffer such that individual data contents in the first buffer are grouped near headers associated with the individual data contents.

2. The device of claim 1, further comprising the SSD further including:

a hash lookup table including hashes of data content buffered in the first buffer; and

the determining that the selected data content is a duplicate of the first previous data content already buffered in the first buffer being performed at least in part by performing a lookup in the hash lookup table for a first hash value of the selected data content.

3. The device of claim 1, further comprising the deduplication control circuit further configured to:

determine whether a second selected data content to be stored is a duplicate of previous data content already in the first buffer; and

based at least in part on a determination that the second selected data content is not a duplicate of previous data content already buffered in the first buffer, buffer, in the first buffer, the second selected data content and a second header including a second pointer that associates the second header with the second selected data content buffered in the first buffer.

4. The device of claim 3, further comprising:

performing the buffering of the second selected data content and the second header based at least in part on a determination that the second selected data content to be stored is not a duplicate of previous data content already in a second buffer of data buffered to be stored in a global storage space of the SSD and not a duplicate of previous data content already stored in the global storage space of the SSD.

5. The device of claim 1, further comprising the deduplication control circuit further configured to:

determine whether a second selected data content to be stored is a duplicate of previous data content already in the first buffer;

based at least in part on a determination that the second selected data content is not a duplicate of previous data content already buffered in the first buffer, determine whether the second selected data content to be stored is a duplicate of previous data content already in a second buffer of data buffered to be stored in a global storage space of the SSD or a duplicate of previous data already stored in the global storage space of the SSD; and

based at least in part on a determination that the second selected data content is a duplicate of second previous data content already buffered in the second buffer or already stored in the global storage space of the SSD, instead of buffering another copy of the second selected data content, buffer a second header including a second pointer that associates the second header with the second previous data content already buffered in the second buffer or that associates the second header with the second previous data content already stored in the global storage space of the SSD.

6. The device of claim 1 further comprising the deduplication control circuit further configured to:

determine that the first buffer is full;

perform the reordering of the first buffer in response to the determining that the first buffer is full; and

store the data in the first buffer to set of storage units of the SSD in an order based at least in part on the reordering of the first buffer.

7. The device of claim 6, further comprising the deduplication control circuit further configured to:

reset a hash lookup table subsequent to storing the data in the first buffer.

8. The device of claim 1 further comprising the deduplication control circuit further configured to:

store data in the first buffer to the set of storage units of the SSD such that individual data contents in the first buffer are stored in the same storage unit of the set of storage units as the headers associated with the individual data contents.

9. The device of claim 1, further comprising the deduplication control circuit further configured to:

count a number of occurrences of headers associated with a second data content buffered in the first buffer; and

when the number of occurrences is greater than a threshold, buffer the second data content in a second buffer of data buffered to be stored in a global storage space of the SSD and add a hash value of the second data content to a global hash lookup table.

10. A device comprising:

a solid state data storage device (SSD) having multiple storage units, the SSD including;

a first buffer configured to buffer data to be stored in a set of local deduplication storage units of the multiple storage units of the SSD including one or more data contents and one or more headers associated with individual data contents of the one or more data contents, individual headers of the one or more headers associating a logical address with a respective data content;

a deduplication control circuit configured to;

count a number of occurrences of headers in the first buffer associated with a first data content of the one or more data contents buffered in the first buffer; and

when the number of occurrences is greater than a threshold, buffer the first data content in a second buffer of data buffered to be stored in a global deduplication storage space of the SSD and add a hash value of the first data content to a global hash lookup table.

11. The device of claim 10, further comprising the deduplication control circuit further configured to:

determine whether first selected data content to be stored is a duplicate of previous data content already in the first buffer of data;

based at least in part on a determination that the first selected data content is a duplicate of first previous data content already buffered in the first buffer, instead of buffering another copy of the first selected data content, buffer a first header including a first pointer that associates the first header with the first previous data content already buffered in the first buffer; and

reorder the first buffer such that individual data contents in the first buffer are grouped near other headers of the one or more headers associated with the individual data contents.

12. The device of claim 11, further comprising:

a hash lookup table including hashes of data content buffered in the first buffer; and

the determining of whether the selected data content is a duplicate of the first previous data content already buffered in the first buffer being performed at least in part by performing a lookup in the hash lookup table for a first hash value of the first selected data content.

13. The device of claim 11 further comprising the deduplication control circuit further configured to:

determine whether a second selected data content to be stored is a duplicate of previous data content already in the first buffer;

based at least in part on a determination that the second selected data content is not a duplicate of previous data content already buffered in the first buffer, determine whether the second selected data content to be stored is the duplicate of previous data content already in a second buffer or a duplicate of previous data already stored in the global deduplication storage space of the SSD; and

based at least in part on a determination that the second selected data content is a duplicate of second previous data content already buffered in the second buffer or already stored in the global deduplication storage space of the SSD, instead of buffering another copy of the second selected data content, buffer a second header including a second pointer that associates the second header with the second previous data content already buffered in the second buffer or that associates the second header with the second previous data content already stored in the global deduplication storage space of the SSD.

14. The device of claim 11 further comprising the deduplication control circuit further configured to:

determine that the first buffer is full;

perform the reordering of the first buffer in response to the determining that the first buffer is full; and

store the data in the first buffer to set of storage units of the SSD in an order based at least in part on the reordering of the first buffer.

15. The device of claim 10, further comprising the deduplication control circuit further configured to:

determine whether a second selected data content to be stored is a duplicate of previous data content already in the first buffer; and

based at least in part on a determination that the second selected data content is not a duplicate of previous data content already buffered in the first buffer, buffer, in the first buffer, the second selected data content and a second header including a second pointer that associates the second header with the second selected data content.

16. The device of claim 15, further comprising:

performing the buffering of the second selected data content and the second header based at least in part on a determination that the second selected data content to be stored is not a duplicate of previous data content already in a second buffer of data buffered to be stored in the global deduplication storage space of the SSD and not a duplicate of previous data content already stored in the global deduplication storage space.

17. A device comprising:

a solid state data storage device (SSD) having multiple storage units, the SSD including;

a deduplication control circuit configured to;

determine whether selected data content to be stored is a duplicate of previous data content already in a first buffer of data buffered to be stored in a set of storage units of the multiple storage units of the SSD;

based at least in part on a determination that the selected data content is a duplicate of first previous data content already buffered in the first buffer, instead of buffering another copy of the selected data content, buffer a first header including a first pointer that associates the first header with the first previous data content already buffered in the first buffer;

reorder the first buffer such that individual data contents in the first buffer are grouped near headers associated with the individual data contents;

a hash lookup table including hashes of data content buffered in the first buffer;

the deduplication control circuit further configured to;

determine that the selected data content is a duplicate of the first previous data content already buffered in the first buffer being performed at least in part by performing a lookup in the hash lookup table for a first hash value of the selected data content;

determine whether a second selected data content to be stored is a duplicate of previous data content already in the first buffer; and

based at least in part on a determination that the second selected data content is not a duplicate of previous data content already buffered in the first buffer, buffer, in the first buffer, the second selected data content and a second header including a second pointer that associates the second header with the second selected data content buffered in the first buffer.

18. The device of claim 17, further comprising the deduplication control circuit further configured to:

count a number of occurrences of headers associated with a second data content buffered in the first buffer; and

when the number of occurrences is greater than a threshold, buffer the second data content in a second buffer of data buffered to be stored in a global storage space of the SSD and add a hash value of the second data content to a global hash lookup table.

19. The device of claim 17, further comprising the deduplication control circuit further configured to:

determine whether a second selected data content to be stored is a duplicate of previous data content already in the first buffer of data buffered to be stored in the set of storage units of the SSD;

based at least in part on a determination that the second selected data content to be stored is not a duplicate of previous data content already in the first buffer, determine whether the second selected data content to be stored is a duplicate of previous data content already in a second buffer of data buffered to be stored in a global storage space of the SSD or a duplicate of previous data already stored in the global storage space of the SSD; and

based at least in part on a determination that the second selected data content is a duplicate of second previous data content already buffered in the second buffer or already stored in the global storage space of the SSD, instead of buffering another copy of the second selected data content, buffer a second header including a second pointer that associates the second header with the second previous data content already buffered in the second buffer or that associates the second header with the second previous data content already stored in the global storage space of the SSD.