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

• US 10,127,150 B2
• Filed: 01/24/2013
• Issued: 11/13/2018
• Est. Priority Date: 11/09/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Sprouse, Steven T., Li, Yan
• Primary Examiner(s): Yi, David
• Assistant Examiner(s): Otto, Alan
• Application Number:
  US13/749,523
• Publication Number:
  US 20140136758A1
• Time in Patent Office: 2,119 Days
• 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. An apparatus, comprising:

a memory block comprising a plurality of bit lines and a plurality of word lines, the memory block further comprising a plurality of NAND strings, each NAND string comprising a series of non-volatile memory cells coupled to a same one of the bit lines, and a plurality of NAND pages, each NAND page comprising non-volatile memory cells of respective NAND strings coupled to a same one of the word lines of the memory block; and

control circuitry configured to;

buffer a plurality of data keys for storage within the memory block in a first orientation, the first orientation arranging the data keys for storage within respective NAND pages of the memory block, and

perform a plurality of write operations to store the data keys in a second orientation different from the first orientation, the second orientation arranging the data keys for storage along respective NAND strings of the memory block,

wherein each write operation comprises storing data within one of the plurality of NAND pages of the memory block, the data stored in each write operation comprising data bits of each data key, such that the data bits of each data key stored within the plurality of NAND pages are aligned along the respective NAND strings of the memory block and the series of non-volatile memory cells of each of the respective NAND strings store data bits of a selected one of the plurality of data keys and exclude data bits of data keys other than the selected data key,

wherein the control circuitry is further configured to identify a NAND string storing a data key that matches a search pattern in response to a sense operation, comprising sensing the identified NAND string while the search pattern is applied to the word lines of the memory block.

2. The apparatus of claim 1, wherein the control circuitry is configured to buffer the data keys in a volatile memory.

3. The apparatus of claim 1, wherein the control circuitry is further configured to generate a data key of the plurality of data keys, the generated data key comprising one or more of a hash value, a hash code, and a signature of a data value.

4. The apparatus of claim 1, wherein:

the control circuitry comprises a table to map data keys stored within the memory block to storage addresses of corresponding data values, and

the control circuitry is further configured to determine a storage address for the search pattern by use of the table and in response to identifying the NAND string that matches the search pattern in the sense operation.

5. The apparatus of claim 4, wherein:

each data key comprises key data,

the control circuitry is further configured to generate inverted key data for each of the data keys, and store the key data and the inverted key data of each data key within respective NAND strings of the memory block, and

the sense operation comprises sensing electrical characteristics of one or more of the NAND strings of the memory block while word lines of the memory block are driven in accordance with one or more of the search pattern and an inverted version of the search pattern.

6. The apparatus of claim 5, wherein the control circuitry is further configured to store the key data and the inverted key data of each data key within respective NAND strings of the memory block and to identify the NAND string storing the data key that matches the search pattern in response to sensing the matching NAND string while first word lines coupled to non-volatile memory cells storing key data of the data keys are driven in accordance with the search pattern, and second word lines coupled to non-volatile memory cells storing inverted key data of the data keys are driven in accordance with an inverted version of the search pattern.

7. The apparatus of claim 6, wherein the control circuitry is further configured to store data keys within the memory block such that the key data and the inverted key data of each data key are interleaved within respective NAND strings.

8. The apparatus of claim 5, wherein:

the control circuitry is further configured to store the key data and the inverted key data of each data key within different respective NAND strings of the memory block,

identifying the matching NAND string comprises identifying a first matching NAND string in a first sense operation and identifying a second matching NAND string in a second sense operation,

the first sense operation comprises applying the search pattern to the word lines of the memory block, and

the second sense operation comprises applying an inverted version of the search pattern to the word lines of the memory block.

9. The apparatus of claim 1, wherein the control circuitry is further configured to:

buffer the data keys in non-volatile storage; and

transpose the buffered data keys into the second orientation in response to reading the data keys from the non-volatile storage.

10. The apparatus of claim 1, further comprising a first-in-first-out (FIFO) circuit comprising a plurality of registers, wherein the control circuitry is further configured to buffer the data keys within the registers of the FIFO such that the data keys are buffered within the first orientation and are read out from registers of the FIFO in the second orientation.

11. The apparatus of claim 1, wherein the memory block comprises an array of non-volatile memory cells having a 3D-type architecture.

12. An apparatus, comprising:

a controller configured to store data keys within a memory array comprising a plurality of bit lines, each bit line coupled to a series of non-volatile memory cells, each non-volatile memory cell coupled to one of a plurality of word lines, wherein storing the data keys comprises;

storing the data keys in a plurality of write operations, the plurality of write operations comprising transposing the data keys from a word line orientation to a bit line orientation, the word line orientation arranging data bits of respective data keys for storage along respective word lines of the memory block, and the bit line orientation arranging the data bits of the respective data keys for storage along respective bit lines of the memory block, each write operation comprising storing a data bit of each data key along one of the plurality of word lines of the memory array such that the data bits of each data key are stored along the respective bit lines of the memory block in the plurality of write operations;

wherein the controller is further configured to determine whether a data key matching a search key is stored within the memory array, the determining comprising sensing the bit lines of the memory array while the word lines of the memory array are driven in accordance with the search key.

13. The apparatus of claim 12, further comprising:

a table configured to map data keys to storage addresses of corresponding data values, wherein the search key is specified in a read request, and wherein the controller is further configured to return a data set stored at a storage address associated with a data key stored along an identified bit line of the memory array, the bit line identified in response to sensing the particular bit line while the word lines of the memory array are driven in accordance with the search key.

14. The apparatus of claim 12, wherein the memory system comprises a solid-state memory device.

15. The apparatus of claim 13, wherein the controller is further configured to write data values corresponding to the data keys, wherein writing a data value corresponding to a first data key comprises:

writing the data value to a designated storage address; and

updating the table to map the first data key to the designated storage address.

16. The apparatus of claim 15, wherein the memory array is embodied within a first memory, and the designated storage address corresponds to a second memory, separate from the first memory.

17. The apparatus of claim 12, wherein the memory array is embodied in a memory having a 3D-type architecture.

18. A memory system, comprising:

a buffer memory;

a memory array comprising a plurality of NAND chains, each of the NAND chains comprising a series of memory cells, each memory cell coupled to one of a plurality of word lines; and

control circuitry configured to;

accumulate data keys in the buffer memory in a first arrangement, the first arrangement configured to map bit values of respective data keys to a plurality of different NAND chains of the memory array,

store the data keys within the memory array in accordance with a second arrangement, the second arrangement configured to map the bit values of each respective data key to respective NAND chains of the memory array, wherein storing the data keys comprises performing a plurality of write operations, each write operation to store a bit value of each data key along one of the plurality of word lines, the plurality of write operations configured such that the bit values of each data key are stored along the respective NAND chains, and each of the respective NAND chains stores bit values of one of the data keys and excludes bit values of others of the plurality of data keys,

wherein the control circuitry is further configured to identify a NAND chain that matches a search key in response to a parallel sense operation, the parallel sense comprising sensing the respective NAND chains of the memory array while voltage potentials on the plurality of word lines are driven in accordance with the search pattern.

19. The memory system of claim 18, wherein the controller is further configured to store the data keys within the respective NAND chains of the memory array in accordance with a sorted order of the data keys.

20. The memory system of claim 19, wherein the sense operation further comprises determining that the identified NAND chain is in a conductive state while the voltage potentials on the plurality of word lines are driven in accordance with the search key.

21. The memory system of claim 18, wherein the memory array comprises an array of non-volatile memory cells in a 3D-type architecture.

22. A system, comprising:

a memory comprising a plurality of NAND strings, each NAND string comprising memory cells arranged in series along a bit line, each memory cell coupled to a respective one of a plurality of word lines;

a FIFO comprising a plurality of registers;

a control circuit configured to;

buffer a plurality of data keys within the FIFO in word line orientation corresponding to storage of bit values of respective data keys along respective word lines of the memory,

transfer the plurality of data keys from the FIFO to the memory in a plurality of write operations, the write operations comprising;

transposing the data keys to a bit line orientation, the bit line orientation corresponding to storage of the bit values of the respective data keys along respective bit lines of the memory, wherein each write operation comprises storing bit values of each of the respective data keys along a selected one of the word lines,

wherein the plurality of write operations comprises storing the bit values of the respective data keys along the respective bit lines of the memory such that the memory cells of each NAND string of the respective NAND strings store data bits that correspond to one of the plurality of data keys and exclude data keys that correspond to others of the plurality of data keys,

wherein the control circuit is further configured to identify a NAND string storing a data key that matches a search pattern in response to performing a sense operation, comprising;

applying the search pattern to the plurality of word lines, and

sensing the respective NAND strings storing the bit values of the respective data keys in parallel.

23. The system of claim 22, wherein:

the search pattern corresponds to a request to access one of a plurality of data values, and

the control circuit is further configured to determine a memory address corresponding to the data value in response to identifying the NAND string storing the data key that matches the search pattern in the sense operation.

24. The system of claim 23, further comprising a mapping table configured to translate data keys to memory locations of respective data values of the plurality of data values, wherein the control circuit is configured to determine the memory address of the data value within the mapping table by use of an index of the identified NAND string.