NAND flash based content addressable memory

• US 9,098,403 B2
• Filed: 01/24/2013
• Issued: 08/04/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): Tseng, Cheng-Yuan
• Assistant Examiner(s): GOLDSCHMIDT, CRAIG S
• Application Number:
  US13/749,407
• Publication Number:
  US 20140136757A1
• Time in Patent Office: 922 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: 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 non-volatile memory system, comprising:

receiving on a controller circuit of the memory system a plurality of multi-bit data keys and, for each of the keys, an associated set of data from a host to which the memory system is connected;

forming the data keys into a plurality of data pages, each of the data pages having one or more bits of more than one of the keys, and each of the keys having one or more bits on more than one of the data pages;

writing the data pages into a corresponding plurality of word lines into a first non-volatile memory array of the memory system;

writing the associated sets of data into a second non-volatile memory array of the memory system; and

maintaining by the controller circuit of a mapping between each of the keys and the associated sets of data.

2. The method of claim 1, wherein the controller maintains a copy of the mapping in non-volatile memory of the memory system.

3. The method of claim 1, wherein the mapping in non-volatile memory of the memory system is metadata associated with the location of the data keys in said array.

4. The method of claim 3, wherein the mapping is based upon an equation relating the location of the data keys and the associated data sets'"'"' location.

5. The method of claim 1, further comprising:

subsequently receiving a search key from the host;

comparing the search key with the data keys as written on the first non-volatile memory array; and

for those data keys determined to match the search key, providing the associated sets of data to the host.

6. The method of claim 5, wherein said comparing includes:

transferring the search key to a first set of registers associated with the first non-volatile memory array;

sequentially reading the plurality of pages data into a second set of registers associated with the first non-volatile memory array; and

individually comparing the data keys as held in the second set of registers with the search key as held in the first set of registers.

7. The method of claim 1, further comprising:

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

for each of the keys, maintaining a correspondence between the copy of the key and the location of the key in the first non-volatile memory array.

8. The method of claim 7, wherein the copies of keys are stored with metadata associated with the keys.

9. The method of claim 7, further comprising:

for each of the keys, generating a corresponding error correction code (ECC); and

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

10. The method of claim 1, further comprising:

subsequent to writing said data pages, performing a read operation to determine the accuracy with which said data pages were written; and

in response to the read operation finding an error in the data pages as written, rewriting said pages into the first non-volatile memory array.

11. The method of claim 10, wherein said rewriting is to a different location of the first non-volatile memory array and the method further comprises making as obsolete the location or the written pages of data that were found to have the error and said mapping reflects said rewriting.

12. The method of claim 11, wherein the first non-volatile memory array is a flash memory array and said different location is a different erase block from that in which the written data pages were found to have the error.

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

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

15. A method of operating a non-volatile memory system, comprising:

receiving on a controller circuit of the memory system a plurality of multi-bit data keys and, for each of the keys, an associated set of data from a host to which the memory system is connected;

forming the data keys into a plurality of data pages, each having one or more bits of one or more keys;

writing the data pages into a corresponding plurality of word lines into a first non-volatile memory array of the memory system;

writing the associated sets of data into a second non-volatile memory array of the memory system;

maintaining by the controller circuit of a mapping between each of the keys and the associated sets of data;

storing a copy of each of the keys in non-volatile memory on the memory system;

for each of the keys, maintaining a correspondence between the copy of the key and the location of the key in the first non-volatile memory array,

subsequently receiving a search key from the host;

comparing the search key with the data keys as written on the first non-volatile memory array;

for those data keys determined to match the search key, determining whether the search key also matches the corresponding copy of the data key; and

providing the associated sets of data to the host for those keys whose copies also match the search key.

16. The method of claim 15, wherein the controller maintains a copy of the mapping in non-volatile memory of the memory system.

17. The method of claim 15, wherein the mapping in non-volatile memory of the memory system is metadata associated with the location of the data keys in said array.

18. The method of claim 17, wherein the mapping is based upon an equation relating the location of the data keys and the associated data sets'"'"' location.

19. The method of claim 15, further comprising:

subsequently receiving a search key from the host;

comparing the search key with the data keys as written on the first non-volatile memory array; and

for those data keys determined to match the search key, providing the associated sets of data to the host.

20. The method of claim 19, wherein said comparing includes:

transferring the search key to a first set of registers associated with the first non-volatile memory array;

sequentially reading the plurality of pages data into a second set of registers associated with the first non-volatile memory array; and

individually comparing the data keys as held in the second set of registers with the search key as held in the first set of registers.

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

22. The method of claim 20, further comprising:

for each of the keys, generating a corresponding error correction code (ECC); and

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

23. The method of claim 15, further comprising:

subsequent to writing said data pages, performing a read operation to determine the accuracy with which said data pages were written; and

in response to the read operation finding an error in the data pages as written, rewriting said pages into the first non-volatile memory array.

24. The method of claim 23, wherein said rewriting is to a different location of the first non-volatile memory array and the method further comprises making as obsolete the location or the written pages of data that were found to have the error and said mapping reflects said rewriting.

25. The method of claim 24, wherein the first non-volatile memory array is a flash memory array and said different location is a different erase block from that in which the written data pages were found to have the error.

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

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