Systems and methods for performing single and multi threaded searches and complex pattern matching in a solid state drive

• US 9,336,313 B1
• Filed: 12/31/2013
• Issued: 05/10/2016
• Est. Priority Date: 07/24/2013
• Status: Active Grant

• Current Assignee: NxGn Data, Inc.
• Original Assignee: NxGn Data, Inc.
• Inventors: Salessi, Nader, Alcantara, Joao
• Primary Examiner(s): Rigol, Yaima
• Application Number:
  US14/145,050
• Time in Patent Office: 861 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: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 16/24569 Query processing with adaptation to specific hardware, e.g. adapted for using GPUs or SSDs
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

System and methods for enhanced data processing and analysis in a storage device, such as a solid state drive (SSD) include an SSD having a data storage and a controller. The data storage stores a plurality of data sets. The controller has a pattern buffer and a data engine. The controller receives a query, processes the query to extract a pattern, loads the pattern into the pattern buffer, and accesses the data storage. The data engine searches a data subset from the data storage for instances of the pattern using a rolling window method. The controller generates a result from the search.

Claims

1. A solid state drive comprising:

a host interface;

a processing unit; and

a flash memory, the flash memory storing a plurality of data sets;

the processing unit being in communication with the host interface, and the flash memory, the processing unit to receive a query through the host interface, and comprising;

a digital signal processing (DSP) core; and

a micro controller having a pattern buffer and a data engine;

the DSP configured to be controlled by the microcontroller, and;

to process the query to extract a pattern, to load the pattern into the pattern buffer, to access the flash memory, to create a window containing the pattern, to search a data subset from the flash memory for instances of the pattern using a rolling window method to search data subsets of the data sets in response to the query;

to process, using a processing algorithm, data received from the flash memory to form processed data and to generate a result from the search,

the processing unit configured to execute a search analysis on the processed data, the processed data comprising unstructured data, the search analysis comprising an analysis selected from the group consisting of;

comparing the processed data to a specified pattern in the window, wherein the comparing

comprises first testing the processed data with a first set of criteria, and second testing the processed data with a second set of criteria in response to the first testing only when the processed data meet the first set of criteria,

counting words in the processed data, wherein the counting comprises counting the number of occurrences of a word in the processed data,

performing in-line indexing of the processed data,

and combinations thereof,

wherein the search analysis comprises the comparing of the processed data to the specified pattern, wherein the comparing comprises the first testing of the processed data with the first set of criteria, and the second testing of the processed data with the second set of criteria in response to the first testing only when the processed data meet the first set of criteria,

wherein the unstructured data comprises a header and a body,

wherein the first testing comprises first testing the header with the first set of criteria, and the second testing comprises second testing the body with the second set of criteria in response to the first testing only when the header meets the first set of criteria.

2. The solid-state drive of claim 1 wherein the pattern is made up of a number of bytes, the rolling window has a size, and the size of the rolling window is determined from the number of bytes.

3. The solid-state drive of claim 1 wherein the data engine positions the rolling window at a first data position in the data subset, the data engine compares data in the rolling window with the pattern byte by byte until a determination about matching is made and then the data engine moves the rolling window to a second data position in the data subset.

4. The solid-state drive of claim 1 wherein the data engine establishes a table based on the pattern in the pattern buffer and the data engine to use the table in positioning the rolling window in the data subset.

5. The solid-state drive in claim 1 wherein the processing unit receives a plurality of queries and searches one data subset at a time against the plurality of queries.

6. The solid-state drive in claim 1 wherein the controller receives a plurality of queries and searches a plurality of data subsets wherein each data subset is associated with one of the plurality of queries.

7. The solid-state drive in claim 1 wherein the micro controller further includes a CPU, a plurality of pattern buffers and a plurality of data engines wherein each data engine of the plurality of data engines is associated with one of the plurality of pattern buffers, wherein the micro controller receives a plurality of queries, and the CPU is configured to process each of the plurality of queries to extract patterns, to the load each extracted pattern into one of the plurality of pattern buffers, and the data engines search data subsets using the pattern from its associated pattern buffer.

8. A method of storing data in, and retrieving data from, a solid state drive comprising a host interface, and a flash memory, and a controller having a data engine and a pattern buffer, the method comprising:

receiving a query by the solid state drive;

storing a pattern derived from the query in the pattern buffer;

creating a window containing the pattern;

retrieving, by the solid state drive, data from the flash memory in response to the query;

processing, by the solid state drive, the retrieved data, using a processing algorithm including a rolling window, to generate processed data, the processed data being unstructured data,

the processing algorithm comprising a first search analysis, the first search analysis comprising comparing the unstructured data to a specified pattern in a first rolling window,

wherein the processing algorithm further comprises a second search analysis executed concurrently with the first search analysis, the second search analysis comprising comparing the unstructured data to a specified pattern in a second rolling window,

wherein the first search analysis is on a header of the processed data, and the second search analysis is on a body of the processed data, and,

generating search results.

9. The method of claim 8 wherein the pattern is made up of a number of characters, the method further comprising setting a size of the rolling window from the number of characters.

10. The method of claim 8 further comprising:

positioning the rolling window at a first data position in the partial data;

comparing the pattern with the data in the rolling window byte by byte until a determination about matching is made; and

repositioning the rolling window at a second position in the partial data.

11. The method of claim 10 further comprising:

establishing a table based on the pattern;

entering search data into the table; and

positioning the rolling window using search data from the table.

12. The method of claim 8 further comprising:

receiving a plurality of queries by the solid state drive;

searching partial data from the data storage, by the controller, in response to the plurality of queries; and

generating results by the controller from the searching.

13. The method of claim 8 wherein the data storage stores a plurality of data sets and the partial data is a data subset.

14. The method of claim 13 wherein the searching step further comprises searching a plurality of data subsets.

15. The method of claim 8 wherein the controller further comprises a data buffer, wherein the data storage stores a plurality of data sets, wherein the partial data is a data subset, and wherein the method further comprises loading a data subset into the data buffer.