Key-value addressed storage drive using NAND flash based content addressable memory

• US 9,116,796 B2
• Filed: 01/24/2013
• Issued: 08/25/2015
• 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/749,432
• Publication Number:
  US 20140133228A1
• Time in Patent Office: 943 Days
• Field of Search: 36518501-18533
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• 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/02 electrically programmable
• 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 2211/5641 Multilevel memory having cells with different number of storage levels
• CPC Class Codes: G11C 2211/5642 Multilevel memory with buffers, latches, registers at input or output
• CPC Class Codes: G11C 2213/71 Three dimensional array
• 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.

Claims

1. A method of operating a memory system, the memory system including a first array of non-volatile memory cells arranged into a NAND type of architecture, including a plurality NAND strings and a plurality word lines spanning the NAND strings, each of the word lines connected to a corresponding one of the memory cells thereof, wherein the first array is written as pages of data along selected word lines, the method comprising:

receiving a plurality of data patterns from a host device to which the memory system is connected;

storing the received data patterns in a RAM memory of the memory system;

on the memory system, subsequently arranging the data patterns stored in the RAM memory into pages of data so that when written into first array, the data patterns arranged to orientated along NAND strings of the first array; and

writing said pages of data into the first array.

2. The method of claim 1, further comprising:

subsequently performing a pattern search operation, including;

receiving a search pattern from the host device;

biasing the word lines according to the search pattern; and

concurrently determining those of the NAND strings that conduct in response to the word lines biased according the search pattern being applied thereto.

3. The method of claim 2, wherein the search pattern can include one or more “

don'"'"'t care”

values.

4. The method of claim 2, further comprising providing the result of the pattern search operation to the host.

5. The method of claim 1, further comprising:

receiving from the host device an associated data set for each of the data patterns;

storing the associated data sets in a primary memory section of the memory system; and

maintaining on the memory system a correspondence between the data patterns and the associated data sets.

6. The method of claim 5, further comprising:

subsequently performing a pattern search operation, including;

receiving a search pattern from the host device;

biasing the word lines according to the search pattern;

determining any of the NAND strings that conduct in response to the word lines biased according the search pattern being applied thereto; and

providing to the host any data set associated with the data patterns stored on those of the NAND strings determined to conduct in response to the word lines biased according the search pattern being applied thereto.

7. The method of claim 6, wherein the search pattern can include one or more “

don'"'"'t care”

values.

8. The method of claim 5, wherein the memory system maintains the correspondence between the data patterns and the associated data sets in a non-volatile memory section of the memory system other than the first array.

9. The method of claim 5, further comprising:

storing copies of said data patterns with the associated sets; and

prior to providing to the host any of said data sets, checking that the search pattern matches the copy of the associated data pattern stored with the data set.

10. The method of claim 9, wherein said copies are ECC protected.

11. The method of claim 5, wherein the memory system maintains the correspondence between the data patterns and the associated data sets as metadata associated with the location at which the data pattern is written in the first array.

12. The method of claim 11, wherein the correspondence is based upon equation relating the data pattern location and the associated data set'"'"'s location.

13. The method of claim 1, further comprising:

for each of the received data patterns, generating on the memory system of an inverted version of the data pattern, wherein the pages of data include the inverted versions of the data patterns.

14. The method of claim 13, wherein the pages of data are arranged so that for each of said data patterns, the data pattern and the inverted version of the data pattern are written into the same NAND string.

15. The method of claim 14, wherein the data pattern and the inverter version of the data pattern are interleaved along said same NAND string.

16. The method of claim 14, wherein the pages of data are arranged so that for each of said data patterns, the data pattern and the inverted version of the data pattern are written into different NAND strings.

17. The method of claim 1, further comprising:

for each of the data patterns, generating on the memory system a corresponding set of one or more parity bits;

subsequently arranging the sets of parity bits into pages so that when written into first array, each set of parity bits is written into the same NAND string as the corresponding data pattern; and

writing said pages of parity bits into the first array.

18. The method of claim 17, further comprising:

subsequently performing a pattern search operation, including;

receiving a search pattern from the host device;

biasing the word lines according to the search pattern, wherein word lines holding parity bits are set to be conducting independently of the search pattern; and

concurrently determining those of the NAND strings that conduct in response to the word lines biased according the search pattern being applied thereto.

19. The method of claim 17, further comprising:

subsequent to writing the pages of data and the pages of parity bits into the first array, checking the result of the write using said parity bits.

20. The method of claim 1, further comprising:

storing a copy of each of the data patterns in non-volatile memory on the memory system; and

for each of the data patterns, maintaining a correspondence between the copy of the data pattern and the location of data pattern in the first array.

21. The method of claim 20, wherein the copies of data patterns are stored with metadata associated with the data patterns.

22. The method of claim 20, further comprising:

for the data patterns, generating corresponding error correction code (ECC); and

for each of the data patterns, storing the corresponding error correction code along with the copy in non-volatile memory on the memory system.

23. The method of claim 20, further comprising:

subsequently performing a pattern search operation, including;

receiving a search pattern from the host device;

biasing the word lines according to the search pattern;

concurrently determining those of the NAND strings that conduct in response to the word lines biased according the search pattern being applied thereto; and

for those of the NAND strings determined to conduct, comparing the corresponding data pattern as stored on the NAND string with the copy thereof.

24. The method of claim 1, further comprising:

subsequent to writing said pages of data into the first array, performing a read operation to determine the accuracy of said writing; and

in response to the read operation finding error in the pages of data as written, rewriting said pages into the first array.

25. The method of claim 24, wherein said rewriting is to a different location of the memory system and the method further comprises making as obsolete where the written pages of data were found to have error.

26. The method of claim 25, wherein the first array is a flash memory array and said different location is a different erase block from that where the written pages of data were found to have error.

27. The method of claim 1, wherein the first array of non-volatile memory cells is of a 3D-type of architecture.