De-duplication system using NAND flash based content addressable memory

• US 8,780,633 B2
• Filed: 03/11/2013
• Issued: 07/15/2014
• Est. Priority Date: 11/09/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Sprouse, Steven T., Li, Yan
• Primary Examiner(s): Byrne, Harry W
• Application Number:
  US13/794,428
• Publication Number:
  US 20140136760A1
• Time in Patent Office: 491 Days
• Field of Search: 36518501-18533
• US Class Current: 365/185.17
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• 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]
• CPC Class Codes: G11C 11/5642 Sensing or reading circuits; Data output circuits
• CPC Class Codes: G11C 15/046 using non-volatile storage elements
• CPC Class Codes: G11C 16/0483 comprising cells having several storage transistors connected in series
• CPC Class Codes: G11C 16/3459 Circuits or methods to verify correct programming of nonvolatile memory cells
• CPC Class Codes: G11C 2213/75 Array having a NAND structure comprising, for example, memory cells in series or memory elements in series, a memory element being a memory cell in parallel with an access transistor

Abstract

A NAND Flash based content addressable memory (CAM) is used for a key-value addressed storage drive. The device can use a standard transport protocol such as PCI-E, SAS, SATA, eMMC, SCSI, and so on. A host writes a key-value pair to the drive, where the drive writes the keys along bit lines of a CAM NAND portion of the drive and stores the value in the drive. The drive then maintains a table linking the keys to location of the value. In a read process, the host provides a key to drive, which then broadcasts down the word lines of blocks storing the keys. Based on any matching bit lines, the tables can then be used to retrieve and supply the corresponding data to the host. This arrangement can be applied to de-duplication: for data sets stored in a primary data storage section, corresponding data keys can be generated and store in search NAND. A received key, rather from external to the system or internally generated, can then be compared against the search NAND. The system can be applied to both in-line and off-line de-duplication.

Claims

1. A non-volatile memory system, comprising:

a first non-volatile memory section storing a plurality of data sets;

a search section, including;

a search array storing a corresponding signature for each of the data sets, where for each of the data sets the signature is derived from the corresponding data set and is of a smaller size, wherein the search array is of NAND type architecture and the signatures are stored therein oriented along the search array'"'"'s bit lines;

biasing circuitry connected to the word lines of the search array; and

sensing circuitry connected to the bit lines of the search array, wherein based on a received a first signature, the biasing circuitry biases the word lines of the search array according to the first signature and the sensing circuitry determines whether any of the bit lines of the search array conduct in response to said biasing of the word lines,

wherein the memory system maintains a correspondence between the location at which the data sets are stored in the first non-volatile memory section and the location at which the corresponding signatures are stored in the search array.

2. The non-volatile memory system of claim 1, wherein in response to determining that none of the bit lines of the search array conduct in response to biasing of the word lines, the system writes a first data set to which the first signature corresponds into the first non-volatile memory section.

3. The non-volatile memory system claim 2, wherein further the search section further includes write circuitry connected to the search array and the memory system writes the first signature into search array.

4. The non-volatile memory system of claim 3, wherein the search section further comprises a RAM memory and, prior to writing the first signature into the search array, the search section writes the first signature into RAM memory.

5. The non-volatile memory system of claim 1, wherein in response to determining that a bit line of the search array conducts in response to biasing of the word lines, the memory system does not write a received first data set to which the first signature corresponds into the first non-volatile memory section.

6. The non-volatile memory system of claim 5, wherein the memory system associates the first data set in said correspondence with the signature corresponding to the bit line that conducts in said determining.

7. The non-volatile memory system of claim 1, wherein said biasing includes setting one or more word lines to a “

don'"'"'t care”

value, wherein;

in response to determining that more than one of the bit lines of the search array conduct in response to said biasing of the word lines, the search array subsequently biases the word lines of the search array according to the first signature, but differently than the preceding biasing; and

determines whether any of the bit lines of the search array conduct in response to both of said biasings of the word lines.

8. The non-volatile memory system of claim 1, wherein the memory system further includes signature generation circuitry, where the system generates the first signature from a corresponding first data set.

9. The non-volatile memory system of claim 8, wherein the memory system includes compression circuitry and the data sets are stored in the first memory section in compressed form and the corresponding first data set is decompressed prior to generating the first signature therefrom.

10. The non-volatile memory system of claim 8, wherein the signatures are hash values generated from the corresponding data set.

11. The non-volatile memory system of claim 8, wherein the first data set is received from outside of the memory system.

12. The non-volatile memory system of claim 8, wherein the first data set is read from the first non-volatile memory section.

13. The non-volatile memory system of claim 12, wherein the first data set is read as part of an on-system data maintenance operation.

14. The non-volatile memory system of claim 12, wherein the first data set is read in response to a request from output of the memory system.

15. The non-volatile memory system of claim 1, where the memory system further includes a second memory section and the memory system compares the first signature to one or more signatures stored in the second section.

16. The non-volatile memory system of claim 15, wherein the second section is volatile RAM memory.

17. The non-volatile memory system of claim 16, wherein the memory system searches the RAM memory for the first signature concurrently with said biasing and determining.

18. The non-volatile memory system of claim 15, wherein the second section is a flash memory array in which said one or more signatures are stored oriented along word lines thereof.

19. The non-volatile memory system of claim 1, wherein maintaining of a correspondence includes maintaining a copy of the correspondence as meta-data in non-volatile memory of the memory system.

20. The non-volatile memory system of claim 19, further comprising maintain copies of said signature as part of said meta-data.

21. The non-volatile memory system of claim 20, wherein the copies of said signatures are ECC protected.

22. The non-volatile memory system of claim 1, wherein the first memory section is a solid state drive.

23. The non-volatile memory system of claim 1, wherein search section is part of the solid state drive.

24. The non-volatile memory system of claim 1, wherein search section is separate unit from the solid state drive.

25. The non-volatile memory system of claim 24, wherein the separate units stores the signatures and the correspondence.

26. The non-volatile memory system of claim 1, wherein the memory system includes compression circuitry and compresses the data sets prior to storing in the first memory section.

27. The non-volatile memory system of claim 1, wherein, when writing an updated plurality of signatures into the search array, the memory system updates the correspondence according to the updating of the signatures.

28. The non-volatile memory system of claim 27, wherein when writing the updated plurality of signatures, the memory system marks as obsolete one or more of the non-updated signatures.

29. The non-volatile memory system of claim 28, wherein the search array has a block structure and wherein the blocks include one or more word lines reserved for marking signatures as obsolete.

30. The non-volatile memory system of claim 28, wherein the search array has a block structure, the non-volatile memory system performs garbage collection operations on the signatures in the search array, a garbage collection operation including:

for one or more blocks, copying the signatures not marked as obsolete into volatile memory; and

rewriting said signatures not marked as obsolete into a different block of the search array.

31. The non-volatile memory system of claim 30, wherein the garbage collection operation further includes adding one or more additional signatures to the signature written into said different block.

32. The non-volatile memory system of claim 1, wherein the first data sets are of a fixed size.

33. The non-volatile memory system of claim 1, wherein the first data sets are of a variable size.

34. The non-volatile memory system of claim 1, wherein said biasing is performed using read voltages for the word lines off-set by positive margins relative to standard values.

35. The non-volatile memory system of claim 1, wherein in response to determining that a bit line of the search array conducts in response to biasing of the word lines, determining whether a first data set to which the first signature corresponds is the same as the data set that corresponds to the bit line that conducts.