Patent Publication Number: US-2016246831-A1

Title: Data storage device supporting accelerated database operations

Description:
CROSS-REFERENCE TO RELATED APPLICATION(S) 
     This application is a continuation of U.S. patent application Ser. No. 14/133,302, filed on Dec. 18, 2013, entitled “Data Storage Device Supporting Accelerated Database Operations,” which claims the benefit of U.S. provisional application No. 61/895,263 (Docket. No. T6519.P), filed Oct. 24, 2013, entitled “Data Storage Device Supporting Accelerated Database Operations,” the disclosures of which are hereby incorporated by reference in their entirety. 
     This application is related to U.S. application Ser. No. 14/673,392 (Docket No. T6519.X1), filed on Mar. 30, 2015, entitled “Data Storage Device Providing Maintenance Services.” 
    
    
     BACKGROUND 
     1. Technical Field 
     This disclosure relates to non-volatile data storage devices and methods for accelerating data operations in such devices. 
     2. Description of the Related Art 
     Database operations are often performed in an environment where speed of execution is of great importance. Common operations such as returning query results and indexing are often I/O-intensive and consume much data bandwidth between a host system (e.g., computing device) and a data storage device at which such operations are executed. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Systems and methods that embody the various features of the various embodiments of the invention will now be described with reference to the following drawings, in which: 
         FIG. 1A  illustrates an example data storage device according to one embodiment of the invention. 
         FIG. 1B  illustrates an example database operation acceleration method according to one embodiment of the invention. 
         FIG. 2  shows the internal data layout of the data storage device according to one embodiment. 
         FIGS. 3A and 3B  are block diagrams showing example layouts of database elements according to one embodiment. 
         FIGS. 4A and 4B  are flow diagrams showing how a filtered read operation may be executed according to one embodiment. 
         FIG. 5  is a flow diagram showing how an indexing operation may be executed according to one embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     Some embodiments of this disclosure are directed to a data storage device (e.g., solid-state drive (SSD)) that is configured to accelerate database operations. In an embodiment, the data storage device supports a variable sized logical page whose size can be customized to match the individual data units (e.g., tuples) within a database data structure. As a result, certain database operations can be accelerated as certain data may be skipped by logical address range(s) to reduce the number of data read out of the storage media and transferred to the host, which results in more efficient database operations. 
     While certain embodiments of the disclosure are described, these embodiments are presented by way of example only, and are not intended to limit the scope of the disclosure. Indeed, the novel methods and systems described herein may be embodied in a variety of other forms. Furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made without departing from the spirit of the disclosure. 
     Data Storage System Overview 
       FIG. 1A  illustrates an example data storage device  120  according to one embodiment of the invention. As is shown, a data storage device  120  (e.g., solid state drive, hybrid drive, etc.) includes a controller  130  and a non-volatile solid-state memory  140 , which comprises one or more units of storage, such as blocks of storage.  FIG. 1A  illustrates an example where the blocks are identified as block “A”  142  through block “N.” While a single non-volatile solid-state memory  140  is illustrated for convenience, the storage device may include multiple of such memories. Each block of the non-volatile solid-state memory  140  comprises a plurality of flash pages (F-pages). For example, block A  142  of  FIG. 1A  includes a plurality of F-pages, identified as F-pages A  143 , B, through N. In some embodiments, each “F-page” is a smallest grouping of memory cells in the nonvolatile solid-state memory  140  that can be programmed in a single operation or as a unit. In lieu of or in addition to the non-volatile solid-state memory  140 , a magnetic rotating media and/or other non-volatile memory such as MRAM and/or phase change memory may be used. 
     The controller  130  can receive data and/or storage access commands from a storage interface  112  (e.g., a device driver) in a host system  110 . Storage access commands communicated by the storage interface  112  can include write and read commands issued by the host system  110 . The commands can specify a logical block address in the data storage device  120 , and the controller  130  can execute the received commands in the non-volatile solid-state memory  140 . In a hybrid hard drive, data may be stored in magnetic media storage component (not shown in  FIG. 1A ) in addition to the non-volatile solid-state memory  140 . 
     The data storage device  120  can store data received from the host system  110  so that the data storage device  120  can act as memory storage for the host system  110 . To facilitate this function, the controller  130  can implement a logical interface. The logical interface can present to the host system  110  the storage device&#39;s memory as a set of logical addresses (e.g., contiguous address) where data can be stored. Internally, the controller  130  can map logical addresses to various physical memory addresses in the non-volatile solid-state memory  140  and/or other memory module(s). 
     In one embodiment, the controller  130  includes storage device hardware and firmware  148  and a memory for database operation code/firmware  150 . The storage device hardware and firmware  148  is/are used to control data operations within the data storage device. In one embodiment, the database operation code/firmware in memory  150  is configurable by the host, and can be executed in its own dedicated processor (not shown in  FIG. 1A ). Those queries are executed against data stored in the non-volatile solid-state memory  140 . Data related to the queries are temporarily stored in a query processing buffer  160  and results are returned to the host system  110  via a host response buffer  162 . Additional details related to how the components interact are provided below. It is noted that these components may be arranged differently in various embodiments. They may be omitted, combined, or separated into further sub-components. Also, components  148 ,  150 ,  160 , and  162  may be integrated into a single processor package or implemented as various discrete components in communication with one another. 
       FIG. 1B  illustrates an example database operation acceleration method according to one embodiment. In one embodiment, the controller  130  is configured to perform the flow shown in  FIG. 1B . At block  168 , the controller is configured to load instructions/code into the memory  150 . The instructions/code may be from a host system. At block  170 , the controller is configured to execute instructions in the memory  150 . In one embodiment, a dedicated processor may be used to handle the executions to provide further acceleration. At block  172 , the controller is configured to cause data to be read from the solid-state memory  140  into the query processing buffer  160 . At block  174 , the controller is configured to determine whether the data match a database query specified by the instructions. At block  176 , the controller is configured to perform a database operation based on the query match determination. In one embodiment, one or more actions in blocks  172 - 176  may be triggered as a result of executing the instructions. As will be explained further below, the database operation performed may include, for example, one or more of: (1) returning data matching the query to the host system  110 ; (2) adding an indication to an index when the data matches the query; (3) modifying the data matching the query and writing the modified data back to the solid-state memory. 
     Acceleration of Database Operations 
       FIG. 2  shows the internal data layout of the data storage device according to one embodiment. As shown, logical pages (L-Pages)  212  of variable size are stored across various error correction pages (E-Page  210 ), which are themselves physical sub-division of physical flash pages F-Pages  208 . In some embodiments, there is one E-Page per F-Page, i.e., the F-Pages are not sub-divided. The L-Pages may cross the underlying physical boundaries of the E-Pages, F-Pages, as well as the boundaries of the dies/blocks/units within the non-volatile solid-state memory  140  (as shown by boundary  217 ). For example, as shown, L-Pages may be distributed across multiple E-Pages. In an example implementation, an E-Page  210  may have a data portion  214  protected by an ECC portion  216 . In some implementations, compression may be used to further change the size of the L-Page as written to the non-volatile solid-state memory. 
     In one embodiment, the size of the logical page is configured to be equal to the size of a tuple of the database, or an integer multiple of it. Due to this flexibility in the logical page size, a database administrator, when designing/configuring the database, can create a matching correlation between the stored data and the access index. For example, as shown in  FIG. 3A , if one tuple takes 2 logical pages, in order to read tuple 7, read logical block addresses (LBAs) 14 and 15 would be read. Having the data indexed based on logical address provides many advantages, including eliminating the overhead of partitioning by the host system&#39;s operating system (OS) and allowing the use of all available storage. 
     In addition, the logical page and database data alignment may allow for selective skipping of certain logical page ranges in query operations (for example, during the execution of the action in the block  172  in  FIG. 1B ). For example, in  FIG. 3B , the data record is set up so that the logical page boundaries are aligned with individual fields of a database record. For example, if a user is interested in accessing just the name and address fields, targeted reads can be executed to read L-Page 0 and L-Page 1. It can be appreciated that the example shown in  FIG. 3B  shows one record and that the same principle can be extended to the case when reading many different records. Following this example further, because of the field and logical address alignment, the index to certain fields can be accessed by a modulo operation on the logical address. By allowing the skipping of certain logical address(es) in the preconfigured logical page arrangement, the database performance can be substantially improved over conventional approaches in which all data is read and then matching results are filtered and provided. In addition, the logical page address can be accessed based on formula and/or condition. For example, different database users may have different access privileges. One user may only have access to the name, address, and phone fields. So for that user, a logic may be formulated such that his query would be blocked from accessing L-Page 3, N+3, 2N+3, etc., as well as L-Page 4, N+4, 2N+4, etc. where N is the number of fields in the record. Another user who has a higher access privilege may access additional fields such as social security number and account number, and a formula based on different logic can be used to allow that access. The different queries as a result of the different access privileges are efficiently handled when the fields are aligned with the logical page boundaries, allowing the data storage device to perform the filtering that is common to many database operations at the storage device&#39;s logical address level. 
     In one embodiment, the data storage device includes a dedicated buffer for query processing, e.g., the query processing buffer  160  shown in  FIG. 1 , or “QPB.” In one embodiment, the QPB is a part of a data path and is capable to hold one logical page. 
     In addition, in one embodiment, the data storage device includes a buffer to hold a response to the host query, e.g., the host response buffer  162  shown in  FIG. 1 , or “HRB.” The size of the buffer in one embodiment is an integer multiple of the logical page size but can be different depending on the configuration. 
     In addition, in one embodiment, the data storage device includes a dedicated processor to execute host-provided code (xenocode, or XC). In one embodiment, xenocode shall have as minimum read access to the query processing buffer  160  and read/write access to the host response buffer  162 . In one embodiment, the data storage device includes a code memory for the xenocode (XC memory or XCM), as shown in element  150  of  FIG. 1 . The size of XCM may be sized to be large enough to execute queries. In addition, in one embodiment, the data storage device has a set of control registers (XCR) allowing the storage device&#39;s hardware and firmware (e.g.,  148  in  FIG. 1 ) to communicate with the xenocode and providing hardware mechanisms to reset and un-reset the xenocode. In one embodiment, a “watchdog” function is provided such that the execution of the xenocode is monitored for hung or timed-out condition so that the device&#39;s hardware/firmware can reset the execution of the xenocode and prevent the entire storage device from hanging and timing out. 
     In one embodiment, the data storage device is configured to provide to the host information about XC type, size of the XCM and HRB, XCR configuration, and execution timing. This information can be provided electronically or in the product documentation. 
     Query Execution Flows 
     In one embodiment, the data storage device may be filled with relational database tuples in accordance with the description above.  FIGS. 4A and 4B  shows how a filtered read may be executed.  FIG. 4A  shows some of the initialization that takes place in anticipation of the query execution. In block  400 , the host system requests configuration information from the data storage device. The information may be related to various settings including xenocode set up information. In block  402 , the data storage device responds with the requested configuration information, including details such as XC type, XCM size, QPB and HRB mapping, execution time, etc. In block  404 , the host system sends a command (e.g., a vendor specific command (VSC)) to load the xenocode for execution. The xenocode could have been previously sent by the host system for storage in the XCM or the solid-state memory of the data storage device. This allows for maximum flexibility by the host to configure/alter the xenocode as needed, while offering the benefits of optimized query execution that is localized with the data storage. In one embodiment, hardware may be used to further speed up these operations. In block  406 , the data storage device receives the command, starts preparation for the execution of the xenocode, and confirms readiness to the host system. The preparation work may include filling up the XCM with a given image, clearing up the HRB etc. In block  408 , the host system sends a command (e.g., VSC) to start the operation (e.g., in this case, XC-filtered read with a set of logical pages). 
       FIG. 4B  shows a part of the flow of the filtered read operation.  FIG. 4B  shows the actions performed for every logical page in the set. In block  420 , the data storage device reads the next logical page into the query processing buffer. In block  422 , the data storage device releases the reset of the xenocode. The reset is related to the watchdog monitor to ensure that the code executes properly and does not result in a hung condition. Then in block  424 , the code in the xenocode memory is executed. If the query result is successful, the xenocode writes an indication to the xenocode register (e.g., XCR.Good=1), in block  426 . In one embodiment, when xenocode execution is completed, it writes a completion indication in the xenocode register (e.g., XCR.Done=1). This causes the data storage device to send the logical page to the host system (e.g., via the host response buffer) and reset xenocode (block  428 ). In one embodiment, if the xenocode takes too long to execute, the watchdog resets the xenocode. The logical page is considered to not match the query. As a result of the execution in  FIGS. 4A and 4B , the data storage device may internally read all the database tuples, but only matching records are transferred to the host. This localized processing reduces the amount of data transfer and thus increases data throughput. The processing can further be coupled and/or supplemented with the storage device&#39;s hardware acceleration to deliver even better improvement. In one implementation, this filtered read operation may be performed in addition to the filtered reads based on logical addresses as previously described. 
     In one embodiment, an indexing operation may take place as follows. Much like  FIG. 4A , the host system and the data storage device may perform some initialization operations. Once the initialization is completed, in one embodiment the host system sends a command (e.g., VSC) to create xenocode-assisted subset of logical pages with a set of logical pages. The process flows for each logical page in the set is shown in  FIG. 5 . The data storage device reads the next logical page to the query processing buffer in block  500 . In block  502 , the data storage device releases the reset of the xenocode. Then in block  504 , the code in the xenocode memory is executed. If the query result is successful, the xenocode writes to the host response buffer the logical page number (e.g., XCR.Page), in block  506 . In one embodiment, when xenocode execution is completed, it writes a completion indication in the xenocde register (e.g., XCR.Done=1). This causes the data storage device to reset xenocode (block  508 ). The logical page may also optionally be sent to the host system. In one embodiment, if the xenocode takes too long to execute, the watchdog resets the xenocode. In such case, the logical page is considered to not match the query. After the set is completed, the data storage device sends to the host system the content of the HRB, giving the host system the results of the index operation. In one embodiment, instead of, or in addition to, returning set of the matching pages, the xenocode may provide more sophisticated operations, such as calculating average values, or doing other statistical analysis. 
     In one embodiment, the data storage device may provide configurable watchdog timing to better match xenocode execution with expected traffic. 
     In one embodiment, the data storage device can go beyond read-only access to the data content. For example, the xenocode can provide read-modify-write operations if necessary. The data storage device may implement this functionality by supporting write access to the query processing buffer by the xenocode, and providing the ability to write the modified logical page back to the solid-state memory. The xenocode, for example, may be configured to read out a page matching certain value, perform some operation, and write the modified page back to the solid-state memory. This can be done without data transfer between the host system and the data storage device and without requiring the host system&#39;s processing power to perform such operations. 
     Other Variations 
     Those skilled in the art will appreciate that in some embodiments, other approaches and methods can be used. For example, the non-volatile solid-state memory array can be implemented using NAND flash memory devices. Other types of solid-state memory devices can alternatively be used, such as array of flash integrated circuits, Chalcogenide RAM (C-RAM), Phase Change Memory (PC-RAM or PRAM), Programmable Metallization Cell RAM (PMC-RAM or PMCm), Ovonic Unified Memory (OUM), Resistance RAM (RRAM), NOR memory, EEPROM, Ferroelectric Memory (FeRAM), Magnetoresistive RAM (MRAM), other discrete NVM (non-volatile solid-state memory) chips, or any combination thereof In one embodiment, the non-volatile solid-state memory array preferably includes multi-level cell (MLC) devices having multi-level cells capable of storing more than a single bit of information, although single-level cell (SLC) memory devices or a combination of SLC and MLC devices may be used. In one embodiment, the data storage device  120  can include other memory modules, such as one or more magnetic memory modules. In addition, the systems and methods of this disclosure may also be useful in more conventional hard drives and hybrid drives including both solid-state and hard drive components. For example, certain hard disk drive employing magnetic recording technology may employ the data addressing and processing schemes described above. 
     While certain embodiments of the disclosure have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the disclosure. Indeed, the novel methods and systems described herein may be embodied in a variety of other forms. Furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made without departing from the spirit of the disclosure. The accompanying claims and their equivalents are intended to cover such forms or modifications as would fall within the scope and spirit of the disclosure. For example, the various components described may be implemented as software and/or firmware on a processor, ASIC/FPGA, or dedicated hardware. For example, those skilled in the art will appreciate that in some embodiments, the actual steps taken in the processes of some embodiments may differ from those shown in the figures. Depending on the embodiment, certain of the steps described in the example above may be removed, others may be added, and the sequence of steps may be altered and/or performed in parallel. Also, the features and attributes of the specific embodiments disclosed above may be combined in different ways to form additional embodiments, all of which fall within the scope of the present disclosure. Although the present disclosure provides certain preferred embodiments and applications, other embodiments that are apparent to those of ordinary skill in the art, including embodiments which do not provide all of the features and advantages set forth herein, are also within the scope of this disclosure. Accordingly, the scope of the present disclosure is intended to be defined only by reference to the appended claims.