DEDUPLICATION OF OBJECTS BY FUNDAMENTAL DATA IDENTIFICATION

• US 20180364917A1
• Filed: 10/20/2017
• Published: 12/20/2018
• Est. Priority Date: 06/20/2017
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Ki, Yang Seok, Martineau, Jason
• Granted Patent: US 10,691,340 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• 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/065 Replication mechanisms
• CPC Class Codes: G06F 3/0661 Format or protocol conversion 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/068 Hybrid storage device

Abstract

A method for writing data to a storage device including a processor, a volatile memory, and a non-volatile memory, the storage device being in communication with a host, the method includes receiving, by the processor, a command to write host data to the non-volatile memory, the host data being associated with a host identification, calculating, by the processor, a hash value associated with the host data, adding, by the processor, an object entry in an object map associated with the hash value, the object entry including the host identification and the hash value, and identifying, by the processor, whether there is a dedup entry in a deduplication map associated with the hash value, and writing, by the processor, stored data to the non-volatile memory based on the identification, the stored data being associated with and different from the host data.

Claims

1. A method for writing data to a storage device comprising a processor, a volatile memory, and a non-volatile memory, the storage device being in communication with a host, the method comprising:

receiving, by the processor, a command to write host data to the non-volatile memory, the host data being associated with a host identification;

calculating, by the processor, a hash value associated with the host data;

adding, by the processor, an object entry in an object map associated with the hash value, the object entry comprising the host identification, the hash value, and a first record indicating how to convert the host data into standard data; and

identifying, by the processor, whether there is a dedup entry in a deduplication map associated with the hash value, the dedup entry comprising the hash value and a second record indicating how to convert the standard data into storable data; and

processing, by the processor, the host data for storage in the non-volatile memory as stored data based on the identification, the stored data being associated with and different from the host data.

2. The method of claim 1, wherein the object map is one of a plurality of object maps, each one of the plurality of object maps being associated with data of a different user of the storage device, and

wherein the dedup map is associated with data of all users of the storage device.

3. The method of claim 1, wherein the calculating the hash value comprises:

determining, by the processor, that the host data is compressed;

in response to the determining, decompressing, by the processor, the host data into decompressed host data according to a compression type of the host data; and

calculating, by the processor, the hash value of the decompressed host data,

wherein the object map further comprises the compression type.

4. The method of claim 1, wherein the processing the host data comprises:

in response to identifying the dedup entry in the deduplication map associated with the hash value, updating the object map and incrementing a count number in the dedup entry without storing any further information in the non-volatile memory.

5. The method of claim 1, wherein the processing the host data comprises:

in response to identifying the dedup entry in the deduplication map associated with the hash value and identifying a previously-stored data associated with the hash value that is compressed,

replacing the previously-stored data with a more efficiently compressed stored data.

6. The method of claim 1, wherein the processing the host data comprises:

in response to identifying the dedup entry in the deduplication map associated with the hash value and identifying a previously-stored data associated with the hash value that is encrypted,

replacing the previously-stored data with a more efficiently encrypted stored data.

7. The method of claim 1, wherein the processing the host data comprises:

in response to identifying the dedup entry in the deduplication map associated with the hash value;

identifying, by the processor, the stored data associated with the hash value based on a first physical address in the dedup entry;

identifying, by the processor, whether the stored data is encrypted based on the dedup entry;

identifying, by the processor, whether the stored data is compressed based on the dedup entry;

reformatting, by the processor, the stored data based on an encryption type and a compression type of the stored data; and

identifying, by the processor, the standard data as the reformatted stored data;

in response to identifying no dedup entry in the deduplication map associated with the hash value;

identifying, by the processor, the standard data as the host data;

processing, by the processor, the standard data into storable data for storage in a second physical address in the non-volatile memory; and

updating, by the processor, the deduplication map.

8. The method of claim 7, wherein the reformatting the stored data comprises:

in response to identifying the stored data as being encrypted;

identifying, by the processor, the encryption type of the stored data in the dedup entry;

identifying, by the processor, an encryption key of the stored data in the dedup entry as an off-drive key or a storage key;

in response to identifying the encryption key as the off-drive key;

not decrypting the stored data;

in response to identifying the encryption key as the storage key;

decrypting, by the processor, the stored data with the storage key and according to the encryption type; and

in response to identifying the stored data as not being compressed;

identifying, by the processor, the standard data as the decrypted stored data.

9. The method of claim 8, wherein the reformatting the stored data further comprises:

in response to identifying the stored data as being compressed;

identifying, by the processor, the compression type of the stored data in the dedup entry; and

decompressing, by the processor, according to the compression type, the decrypted stored data or, in response to identifying the stored data as not being encrypted, the stored data to generate the standard data.

10. The method of claim 7, wherein the processing, by the processor, the standard data into storable data for storage comprises:

determining, by the processor, whether the standard data is compressible based on one or more of quality of service (QoS) parameters, work load of the storage device, and user demands;

determining, by the processor, whether the standard data is encryptable based on one or more of quality of service (QoS) parameters, work load of the storage device, and user demands;

in response to determining that the standard data is compressible;

compressing, by the processor, the standard data with an algorithm satisfying the QoS parameters to generate processed data;

in response to determining that the standard data is not compressible;

identifying, by the processor, the processed data as the standard data; and

in response to determining that the standard data is not encryptable;

storing, by the processor, the processed data at the second physical address in the non-volatile memory.

11. The method of claim 10, wherein the processing the standard data further comprises:

in response to determining that the standard data is encryptable;

encrypting, by the processor, the processed data with a key and by an algorithm satisfying the QoS parameters; and

storing, by the processor, the encrypted processed data at the second physical address in the non-volatile memory.

12. The method of claim 11, wherein the key comprises an off-drive key or a storage key.

13. The method of claim 7, wherein the updating the deduplication map comprises:

in response to identifying the dedup entry in the deduplication map associated with the hash value;

updating, by the processor, the dedup entry in the deduplication map with the second physical address and one or more of an encryption key, encryption type, and compression type; and

in response to identifying no dedup entry in the deduplication map associated with the hash value;

adding, by the processor, a dedup entry in the deduplication map, the dedup entry comprising the second physical address and one or more of an encryption key, encryption type, and compression type for transforming the stored data into the standard data.

14. The method of claim 1, wherein the deduplication map and the object map are maintained in the volatile memory or the non-volatile memory of the storage device.

15. A method for reading data from a storage device comprising a processor, a volatile memory, and a non-volatile memory, the storage device being in communication with a host, the method comprising:

receiving, by the processor, a command to read host data from the non-volatile memory, the host data being associated with a host identification;

identifying, by the processor, an object entry in an object map associated with the host identification, the object entry comprising the host identification, a hash value, and a first record indicating how to convert the host data into standard data;

identifying, by the processor, the hash value of the object entry;

identifying, by the processor, a dedup entry in a deduplication map associated with the hash value, the dedup entry comprising the hash value and a second record indicating how to convert the standard data into stored data associated with the host data;

retrieving, by the processor, the stored data from the non-volatile memory based on a physical address in the dedup entry;

identifying, by the processor, whether the stored data is encrypted based on the dedup entry;

identifying, by the processor, whether the stored data is compressed based on the dedup entry;

identifying, by the processor, whether the host data is compressed based on the object entry; and

generating, by the processor, the host data from the stored data based on whether the stored data is encrypted, the stored data is compressed, and the host data is compressed.

16. The method of claim 15, wherein the generating the host data comprises:

in response to identifying the stored data as being encrypted;

identifying, by the processor, an encryption type and an encryption key in the dedup entry;

decrypting, by the processor, the stored data associated with the hash value with a storage key and according to the encryption type; and

in response to identifying the stored data and the host data as not compressed;

identifying, by the processor, the host data as the decrypted stored data.

17. The method of claim 16, wherein the generating the host data further comprises:

in response to identifying the stored data as being compressed;

identifying, by the processor, a first compression type in the dedup entry;

identifying, by the processor, a second compression type in the object entry;

determining, by the processor, whether the first and second compression types are the same;

in response to determining that the first and second compression types are the same;

identifying, by the processor, the host data as the decrypted stored data or, in response to identifying the stored data as not being encrypted, as the stored data; and

in response to determining that the first and second compression types are not the same;

decompressing, by the processor, according to the first compression type, the decrypted stored data or, in response to identifying the stored data as not being encrypted, the stored data to generate the standard data; and

compressing, by the processor, the standard data according to the second compression type to generate the host data.

18. The method of claim 17,

wherein the second compression type is a non-compression,

wherein the compressing the standard data comprises not compressing the decompressed data, and

wherein the generating the host data comprises identifying the host data as the standard data.

19. A method for deleting data from a storage device comprising a processor, a volatile memory, and a non-volatile memory, the storage device being in communication with a host, the method comprising:

receiving, by the processor, a command to delete host data from the non-volatile memory, the host data being associated with a host identification;

identifying, by the processor, an object entry in an object map associated with the host identification, the object entry comprising the host identification, a hash value, and a first record indicating how to convert the host data into standard data;

identifying, by the processor, the hash value of the object entry;

identifying, by the processor, a dedup entry in a deduplication map associated with the hash value, the dedup entry comprising the hash value and a second record indicating how to convert the standard data into stored data associated with the host data;

decrementing, by the processor, a count in the dedup entry;

determining, by the processor, whether the count equals zero; and

deleting, by the processor, one or more of the object entry and the dedup entry based on the count.

20. The method of claim 19, wherein in response to determining that the count equals zero:

deleting, by the processor, the dedup entry from the deduplication map; and

deleting, by the processor, the object entry from the object map;

identifying, by the processor, the stored data associated with the host data in the non-volatile memory based on a physical address in the dedup entry; and

deleting, by the processor, the stored data, and

wherein in response to determining that the count does not equal zero;

deleting, by the processor, the object entry from the object map.

21. A deduplication system for writing data to a storage device in communication with a host, the deduplication system comprising:

a processor; and

a processor memory local to the processor, wherein the processor memory has stored thereon instructions that, when executed by the processor, cause the processor to perform;

receiving a command to write host data to a non-volatile memory, the host data being associated with a host identification;

calculating a hash value associated with the host data;

adding an object entry in an object map associated with the hash value, the object entry comprising the host identification, the hash value, and a first record indicating how to convert the host data into standard data; and

identifying whether there is a dedup entry in a deduplication map associated with the hash value, the dedup entry comprising the hash value and a second record indicating how to convert the standard data into stored data; and

processing the host data for storage in the non-volatile memory as stored data based on the identification, the stored data being associated with and different from the host data.

22. A deduplication system for reading data from a storage device in communication with a host, the deduplication system comprising:

a processor; and

a processor memory local to the processor, wherein the processor memory has stored thereon instructions that, when executed by the processor, cause the processor to perform;

receiving a command to read host data from a non-volatile memory, the host data being associated with a host identification;

identifying an object entry in an object map associated with the host identification, the object entry comprising the host identification, a hash value, and a first record indicating how to convert the host data into standard data;

identifying the hash value of the object entry;

identifying a dedup entry in a deduplication map associated with the hash value, the dedup entry comprising the hash value and a second record indicating how to convert the standard data into stored data associated with the host data;

retrieving the stored data from the non-volatile memory based on a physical address in the dedup entry;

identifying whether the stored data is encrypted based on the dedup entry;

identifying whether the stored data is compressed based on the dedup entry;

identifying whether the host data is compressed based on the object entry; and

generating the host data from the stored data based on whether the stored data is encrypted, the stored data is compressed, and the host data is compressed, the host data being different from the host data.

23. A deduplication system for deleting data from a storage device in communication with a host, the deduplication system comprising:

a processor; and

a processor memory local to the processor, wherein the processor memory has stored thereon instructions that, when executed by the processor, cause the processor to perform;

receiving a command to delete host data from a non-volatile memory, the host data being associated with a host identification;

identifying an object entry in an object map associated with the host identification, the object entry comprising the host identification, a hash value, and a first record indicating how to convert the host data into standard data;

identifying the hash value of the object entry;

identifying a dedup entry in a deduplication map associated with the hash value, the dedup entry comprising the hash value and a second record indicating how to convert the standard data into stored data associated with the host data;

decrementing a count in the dedup entry;

determining whether the count equals zero; and

deleting one or more of the object entry and the dedup entry based on the count.