Method and system for data de-duplication

• US 9,229,853 B2
• Filed: 12/20/2011
• Issued: 01/05/2016
• Est. Priority Date: 12/20/2011
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Khan, Jawad B., Xie, Ningde, Ramanujan, Raj K., Puthiyedath, Leena K.
• Primary Examiner(s): Abad, Farley
• Assistant Examiner(s): Franklin, Richard B
• Application Number:
  US13/977,069
• Publication Number:
  US 20130318288A1
• Time in Patent Office: 1,477 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 2212/304 In main memory subsystem
• 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/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

An apparatus may comprise a non-volatile random access memory to store data and a processor coupled to the non-volatile random access memory. The apparatus may further include a data de-duplication module operable on the processor to read a signature of incoming data, compare the signature to first data in the non-volatile random access memory, and flag the incoming data for discard when the signature indicates a match to the first data. Other embodiments are disclosed and claimed.

Claims

1. An apparatus, comprising:

a non-volatile random access memory to store data;

a processor coupled to the non-volatile random access memory; and

a data de-duplication module operable on the processor to;

read a signature of incoming data;

compare the signature to first data in the non-volatile random access memory, the data de-duplication module to also include;

a hash generation module operable to produce a first hash that includes pointers to all portions of the first data stored in the non-volatile random access memory, and a first data key to uniquely identify the first data;

a hash translation table generator operable to generate a first hashed system address corresponding to a first system memory address for the first data, and to map the first hashed system address and first data key to a first physical address containing the first data in the non-volatile random access memory; and

a comparison module operable to compare a second hash and second data key of the incoming data with the first hash and first data key; and

flag the incoming data for discard when the signature indicates a match to the first data based on the comparison of the second hash and second data key with the first hash and first data key.

2. The apparatus of claim 1, comprising a two-level memory that includes the non-volatile random access memory and a memory-side-cache.

3. The apparatus of claim 2, the processor arranged to perform a lookup in the memory-side-cache when performing a read/write access of data stored in the two-level memory, and to access the non-volatile random access memory when the lookup indicates that the memory-side-cache does not contain the stored data.

4. The apparatus of claim 2, comprising a second cache arranged in a data path between the non-volatile random access memory and hash translation table generator to employ the physical address of the first data for indexing.

5. The apparatus of claim 2, the apparatus comprising the memory-side-cache and a second cache to cache de-duplicated data received from the data de-duplication module.

6. The apparatus of claim 1, the comparison module operable to:

forward a first signal to an address indirection table to store a second system memory address corresponding to the incoming data together with the first physical address when the second hash and second data key match the respective first hash and first data key; and

forward a second signal to store the incoming data in a second physical address in the non-volatile random access memory when the second hash and second data key do not match the respective first hash and first data key.

7. The apparatus of claim 1, comprising a digital display to present information from the first data.

8. The apparatus of claim 1, the non-volatile random access memory comprising a phase change memory array.

9. The apparatus of claim 1, the processor comprising a solid state device controller that includes the data de-duplication module.

10. A method, comprising:

reading a signature of incoming data;

comparing the signature to first data stored in a first portion of non-volatile random access memory of a two-level memory, comparing the signature to include

producing a first hash that includes pointers to all portions of the first data stored in the non-volatile random access memory and a first data key to uniquely identify the first data;

generating a first hashed system address corresponding to a first system memory address for the first data;

mapping the first hashed system address and first data key to a first physical address containing the first data in the non-volatile random access memory; and

comparing a second hash and second data key of the incoming data with the first hash and first data key;

flagging the incoming data for discard when the signature indicates a match to the first data; and

forwarding the incoming data for writing to a second portion of non-volatile random access memory when the signature indicates no match to the first data.

11. The method of claim 10, comprising:

performing a lookup in a memory-side-cache of the two-level memory when performing a read/write access of stored data; and

accessing the non-volatile random access memory when the lookup indicates that the memory-side-cache does not contain the stored data.

12. The method of claim 10, comprising:

comparing the second hash and second data key to the respective first hash and first data key;

forwarding a first signal to an address indirection table to store a second system memory address corresponding to the incoming data together with the first physical address when the second hash and second data key match the respective first hash and first data key; and

forwarding a second signal to store the incoming data in a second physical address in the non-volatile random access memory when the second hash and second data key do not match the respective first hash and first data key.

13. The method of claim 10, comprising:

receiving an indication of the first physical address of the first data; and

indexing the first physical data.

14. At least one non-transitory computer-readable storage medium comprising a plurality of instructions that, when executed, cause a system to:

read a signature of incoming data;

compare the signature to first data in the non-volatile random access memory compare the signature to include the system to;

produce a first hash that includes pointers to all portions of the first data stored in the non-volatile random access memory, and a first data key to uniquely identify the first data;

generate a first hashed system address corresponding to a first system memory address for the first data, and to map the first hashed system address and first data key to a first physical address containing the first data in the non-volatile random access memory; and

compare a second hash and second data key of the incoming data with the first hash and first data key; and

flag the incoming data for discard when the signature indicates a match to the first data.

15. The at least one non-transitory computer-readable storage medium of claim 14, comprising instructions that, when executed, cause a system to perform a lookup in a memory-side-cache when performing a read/write access of data stored in a two-level memory, and to access the non-volatile random access memory when the lookup indicates that the memory-side-cache does not contain the stored data.

16. The at least one non-transitory computer-readable storage medium of claim 14, comprising instructions that, when executed, cause a system to:

forward a first signal to an address indirection table to store a second system memory address corresponding to the incoming data together with the first physical address when the second hash and second data key match the respective first hash and first data key; and

forward a second signal to store the incoming data in a second physical address in the non-volatile random access memory when the second hash and second data key do not match the respective first hash and first data key.

17. An apparatus, comprising:

a non-volatile random access memory to store data;

a processor coupled to the non-volatile random access memory; and

a data de-duplication module operable on the processor to;

read a signature of incoming data;

compare the signature to first data in the non-volatile random access memory, the comparison of the signature to include the data de-duplication module operable to;

read an outer code of the first data to determine a first parity; and

compute a second parity of the incoming data; and

flag the incoming data for discarding when the computed second parity matches the first parity.

18. The apparatus of claim 17, the data de-duplication module operable on the controller to:

generate parity P₁′

for user data U₁ of a first inner codeword of the first data, the first inner codeword comprising user data U_i, logical block address (LBA) information L_i corresponding to the user data U₁, and computed parity of the user data U₁ and LBA; and

compare P₁′

to the computed second parity.

19. The apparatus of claim 17, the data de-duplication module operable on the controller to:

form a concatenated codeword for the incoming data by encoding an outer code for the incoming data when inner error correction coding check bits for the incoming data do not match the outer code for the incoming data;

write the concatenated codeword to the memory; and

read the concatenated codeword from the memory.

20. At least one non-transitory computer-readable storage medium comprising a plurality of instructions that, when executed, cause a system to:

read a signature of incoming data;

compare the signature to first data in the non-volatile random access memory, compare the signature to include the system to;

read an outer code of the first data to determine a first parity; and

compute parity of the incoming data; and

flag the incoming data for discarding when the computed parity matches the first parity.

21. The at least one non-transitory computer-readable storage medium of claim 20, comprising instructions that, when executed, cause a system to:

generate parity P₁′

for user data U₁ of a first inner codeword of the first data, the first inner codeword comprising user data U₁, logical block address (LBA) information L_i corresponding to the user data U₁, and computed parity of the user data U₁ and LBA; and

compare P₁′

to the computed second parity.

22. The at least one non-transitory computer-readable storage medium of claim 20, comprising instructions that, when executed, cause a system to:

form a concatenated codeword for the incoming data by encoding an outer code for the incoming data when inner error correction coding check bits for the incoming data do not match the outer code of the incoming data;

write the concatenated codeword to the memory; and

read the concatenated codeword from the memory.