Data search using bloom filters and NAND based content addressable memory

• US 8,817,541 B2
• Filed: 03/14/2013
• Issued: 08/26/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: Li, Yan, Sprouse, Steven T.
• Primary Examiner(s): Byrne, Harry W
• Application Number:
  US13/827,609
• Publication Number:
  US 20140136762A1
• Time in Patent Office: 530 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 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• 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. 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 data search operations using bloom filters stored along bit lines of search matrix, where the search matrix can extend across large numbers of arrays. In the example of an internet search, the bloom filters are formed from key words associated with a website are stored along bit lines of the matrix and corresponding URLs are stored in primary storage. In response to search word based query, any matching URLs are returned.

Claims

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

storing a plurality of bloom filters, each generated from a corresponding set of search elements, on a search matrix formed of one or more non-volatile memory arrays of the memory system, wherein the memory arrays are of a NAND type architecture and the bloom filters are stored therein oriented along the arrays'"'"' bit lines;

for each of the bloom filters, storing a corresponding data element in a first non-volatile memory section of the memory system; and

maintaining by the control circuitry of the memory system of a correspondence between the location of the bit lines of the search matrix upon which the bloom filters are stored and the location at which the corresponding data elements are store in the first non-volatile memory section.

2. The method of claim 1, wherein the data elements are sets of data with which the corresponding search terms are associated.

3. The method of claim 1, wherein the data elements derived from sets of data with which the corresponding search terms are associated.

4. The method of claim 1, wherein the data elements are a pointer from which the sets of data with which the corresponding search terms are associated can be located.

5. The method of claim 4, wherein the data elements are URLs.

6. The method of claim 5, wherein the corresponding search terms are key words associated with web page of the corresponding URL.

7. The method of claim 1, further comprising:

prior to storing the bloom filters and the corresponding data elements, receiving the bloom filters and the corresponding data elements at the memory system; and

prior to storing the received bloom filters, in circuitry on the memory system transposing the bloom filters from a horizontal to vertical orientation.

8. The method of claim 1, further comprising:

prior to storing the bloom filters and the corresponding data elements, receiving the search elements and the corresponding data elements at the memory system; and

prior to storing the bloom filters, in circuitry on the memory system generating the bloom filters from the corresponding search elements.

9. The method of claim 1, further comprising:

prior to storing the bloom filters and the corresponding data elements, receiving hash values generated from the search elements and the corresponding data elements at the memory system; and

prior to storing the bloom filters, in circuitry on the memory system generating the bloom filters from the hash values generated from the corresponding search elements.

10. The method of claim 1, wherein the search elements from which a bloom filter is generated include elements extracted from a data set associated with the corresponding data element.

11. The method of claim 1, wherein the search elements from which a bloom filter is generated include descriptive data for a data set associated with the corresponding data element.

12. The method of claim 1, wherein the control circuitry maintains the correspond as a mapping.

13. The method of claim 12, wherein the maintaining of a correspondence includes maintaining a copy of the mapping as meta-data in non-volatile memory of the memory system.

14. The method of claim 1, wherein the control circuitry maintains the correspond through a formula.

15. The method of claim 1, wherein the memory arrays are flash memory arrays having a block structure and the individual bloom filters are stored spanning multiple blocks.

16. The method of claim 1, wherein the search matrix is formed of in excess of a thousand arrays.

17. The method of claim 1, further comprising:

subsequently receiving a query based on one or more search elements;

biasing the arrays of the search matrix according to a query bloom filter generated from the search elements on which the query is based;

determining bloom filters stored in the search matrix that provide positive matches for query bloom filter; and

providing the corresponding data elements for the bloom filter that provide positive matches.

18. The method of claim 17, wherein the query includes the query bloom filter.

19. The method of claim 17, wherein the query includes the search element upon which the query is based, the method further comprising:

in circuitry on the memory system, generating the query bloom filter from the search elements upon which the query is based.

20. The method of claim 17, wherein the query includes hashes of the search elements upon which the query is based, the method further comprising:

in circuitry on the memory system, generating the query bloom filter from the hashes of the search elements upon which the query is based.

21. The method of claim 17, wherein the memory arrays are flash memory arrays having a block structure and the individual bloom filters are stored spanning multiple blocks and wherein said biasing and determining are performed for multiple blocks in parallel.

22. The method of claim 17, wherein said biasing and determining are performed for multiple arrays in parallel.