Method and system for in-line deduplication in a storage drive based on a non-collision hash

1. A computer-implemented method for facilitating in-line deduplication in a storage device, the method comprising:

receiving, by a controller of the storage device, data to be stored;

generating a key for the data based on a hash associated with the data;

storing the key in a first data structure based on a logical block address of the data;

in response to determining that an entry corresponding to the key exists in a second data structure, wherein the entry indicates a physical block address at which the data is stored, modifying metadata associated with the key and the logical block address; and

in response to determining that an entry corresponding to the key does not exist in the second data structure:

compressing the data;

encrypting the compressed data based on the key;

encoding the encrypted data based on an error correction code; and

writing the encoded data to a physical media of the storage device based on a new physical block address.

2. The method of claim 1 , wherein determining that the entry corresponding to the key exists in the second data structure involves:

performing a search in the second data structure, based on the key as an index, for the entry which indicates the physical block address at which the data is stored.

3. The method of claim 1 , wherein in response to determining that the entry corresponding to the key does not exist in the second data structure, prior to writing the encoded data to the physical media of the storage device, the method further comprises:

assigning the new physical block address to the key; and

storing, in the second data structure, a mapping of the key to the new physical block address.

4. The method of claim 3 , wherein assigning the new physical block address is performed by one or more of:

a flash translation layer module of the storage device; and

a mapping system of the storage device.

5. The method of claim 1 , wherein entries in the first data structure are indexed by logical block addresses,

wherein a respective entry in the first data structure indicates a corresponding key,

wherein entries in the second data structure are indexed by keys, and

wherein a respective entry in the second data structure indicates a corresponding physical block address.

6. The method of claim 1 , further comprising:

receiving, by the controller, a request to read the data;

performing a search in the first data structure, based on the logical block address, for the key;

performing a search in the second data structure, based on the key, for the physical block address associated with the data;

reading the data from the storage device based on the physical block address;

in response to determining that a hash of the read data does not match the key, generating an error report or message; and

in response to determining that the hash of the read data does match the key, returning the read data to a requesting application.

7. The method of claim 6 , wherein subsequent to reading the data from the storage device based on the physical block address, the method further comprises:

processing the data by:

decoding the read data based on an error correction code;

decrypting the decoded data based on the key; and

decompressing the decrypted data.

8. The method of claim 1 , wherein the first data structure is stored in a first non-volatile memory of the storage device, and

wherein the second data structure is stored in a second non-volatile memory of the storage device and loaded into a volatile memory of the storage device.

9. A computer system for facilitating in-line deduplication, the system comprising:

a processor; and

a memory coupled to the processor and storing instructions, which when executed by the processor cause the processor to perform a method, wherein the computer system is a storage device, the method comprising:

receiving, by a controller of the storage device, data to be stored;

generating a key for the data based on a hash associated with the data;

storing the key in a first data structure based on a logical block address of the data;

in response to determining that an entry corresponding to the key exists in a second data structure, wherein the entry indicates a physical block address at which the data is stored, modifying metadata associated with the key and the logical block address; and

in response to determining that an entry corresponding to the key does not exist in the second data structure:

compressing the data;

encrypting the compressed data based on the key;

encoding the encrypted data based on an error correction code; and

writing the encoded data to a physical media of the storage device based on a new physical block address.

10. The computer system of claim 9 , wherein determining that the entry corresponding to the key exists in the second data structure involves:

performing a search in the second data structure, based on the key as an index, for the entry which indicates the physical block address at which the data is stored.

11. The computer system of claim 9 , wherein in response to determining that the entry corresponding to the key does not exist in the second data structure, prior to writing the encoded data to the physical media of the storage device, the method further comprises:

assigning the new physical block address to the key; and

storing, in the second data structure, a mapping of the key to the new physical block address.

12. The computer system of claim 11 , wherein assigning the new physical block address is performed by one or more of:

a flash translation layer module of the storage device; and

a mapping system of the storage device.

13. The computer system of claim 9 , wherein entries in the first data structure are indexed by logical block addresses,

wherein a respective entry in the first data structure indicates a corresponding key,

wherein entries in the second data structure are indexed by keys, and

wherein a respective entry in the second data structure indicates a corresponding physical block address.

14. The computer system of claim 9 , wherein the method further comprises:

receiving, by the controller, a request to read the data;

performing a search in the first data structure, based on the logical block address, for the key;

performing a search in the second data structure, based on the key, for the physical block address associated with the data;

reading the data from the storage device based on the physical block address;

in response to determining that a hash of the read data does not match the key, generating an error report or message; and

in response to determining that the hash of the read data does match the key, returning the read data to a requesting application.

15. The computer system of claim 14 , wherein subsequent to reading the data from the storage device based on the physical block address, the method further comprises:

processing the data by:

decoding the read data based on an error correction code;

decrypting the decoded data based on the key; and

decompressing the decrypted data.

16. The computer system of claim 9 , wherein the first data structure is stored in a first non-volatile memory of the storage device, and

wherein the second data structure is stored in a second non-volatile memory of the storage device and loaded into a volatile memory of the storage device.

17. A storage device for facilitating in-line deduplication, comprising:

a first non-volatile memory which stores a first data structure;

a second non-volatile memory which stores a second data structure which is loaded into a volatile memory; and

a controller configured to:

receive data to be stored;

generate a key for the data based on a hash associated with the data;

store the key in the first data structure based on a logical block address of the data;

in response to determining that an entry corresponding to the key exists in the second data structure, wherein the entry indicates a physical block address at which the data is stored, modify metadata associated with the key and the logical block address; and

in response to determining that an entry corresponding to the key does not exist in the second data structure:

compress the data;

encrypt the compressed data based on the key;

encode the encrypted data based on an error correction code; and

write the encoded data to a physical media of the storage device based on a new physical block address.

18. The storage device of claim 17 , wherein in response to determining that the entry corresponding to the key does not exist in the second data structure, prior to writing the encoded data to the physical media of the storage device, the controller is further configured to:

assign the new physical block address to the key; and

store, in the second data structure, a mapping of the key to the new physical block address.