Patent Description:
A memory device stores data in response to a write request and outputs data stored therein in response to a read request. For example, the memory device is classified as a volatile memory device, which loses data stored therein when a power supply is turned off, such as a dynamic random access memory (DRAM) device or a static RAM (SRAM) device, or a non-volatile memory device, which retains data stored therein even when a power supply is turned off, such as a flash memory device, a phase-change RAM (PRAM), a magnetic RAM (MRAM), or a resistive RAM (RRAM).

Nowadays, as sizes of user data, an application, and the like increase, the management of a large amount of data is required. To manage a large amount of data, a non-volatile memory device may use memory blocks having a multi-layer structure. For example, a high layer may include a metadata block, and a low layer may include a data block. As the number of layers increases, a capacity of data capable of being managed may increase. However, because an access to plural metadata blocks is sequentially made, an access to a data block including target data may be delayed. Accordingly, there is required a technique for decreasing the delay due to the access to the data block.

From <CIT> it is known a method of accessing data in a storage device. The method includes setting a meta data attribute table by classifying a plurality of meta data based on a plurality of data attributes and accessible memory types, detecting a data attribute of first meta data among the plurality of meta data based on the meta data attribute table in response to receiving a first access request for the first meta data, determining a target memory optimized for the first meta data from among the first and second nonvolatile memories based on the detected data attribute of the first meta data, and performing an access operation on the target memory based on the first meta data.

Embodiments of the present invention provide a method of operating a storage device which communicates with a host device.

A method according to the invention is defined by independent claim <NUM>. Further developments of the method are defined in the dependent claims.

The above and other objects and features of the present invention will become apparent by describing in detail embodiments thereof with reference to the accompanying drawings.

Herein, when it is referred to a figure showing "aspects of the present invention", it is understood that said figure shows some of the claimed features but not all of them.

Below, embodiments of the present invention will be described in detail and clearly to such an extent that one skilled in the art easily carries out the present invention.

<FIG> is a block diagram of a storage system which may be operated according to embodiments of the present invention. Referring to <FIG>, a storage system <NUM> may include a host device <NUM> and a storage device <NUM>. In some embodiments, the storage system <NUM> may include a computing system, which is configured to process a variety of information, such as a personal computer (PC), a notebook, a laptop, a server, a workstation, a tablet PC, a smartphone, a digital camera, and a black box.

The host device <NUM> may control an overall operation of the storage system <NUM>. For example, the host device <NUM> may store data in the storage device <NUM> or may read data stored in the storage device <NUM>.

The host device <NUM> may include a user interface <NUM>, an application <NUM>, and an operating system <NUM>. The user interface <NUM> may provide an interface with a user of the storage system <NUM>. For example, the user interface <NUM> may provide an interface with the user through an external device such as a touchscreen, a monitor, a mouse, a keyboard, a microphone, or a speaker.

The application <NUM> may refer to a software program designed to perform a specific function. For example, the application <NUM> may include a word processor, a database program, a web browser, an image editing program, and the like.

The operating system <NUM> may provide an interface between hardware and software. For example, the operating system <NUM> may execute the application <NUM> and may allocate a resource to the application <NUM>. The operating system <NUM> may automatically manage files through a file system or may manage the files through the file system depending on a request of the application <NUM>. For example, the file system may systematically manage an operation of creating a file, an operation of accessing the file, an operation of opening the file, an operation of changing the file, and an operation of deleting the file, and the like. A file may refer to a set of data. The data set corresponding to the file may be stored in the storage device <NUM>.

The storage device <NUM> may store data received from the host device <NUM> or may provide the stored data to the host device <NUM>. The storage device <NUM> may include a storage controller <NUM> and a non-volatile memory device <NUM>.

The non-volatile memory device <NUM> may store data. The storage controller <NUM> may store data in the non-volatile memory device <NUM> or may read data stored in the non-volatile memory device <NUM>. The non-volatile memory device <NUM> may operate under control of the storage controller <NUM>. For example, based on a command CMD indicating an operation and an address ADD indicating a location of data, the storage controller <NUM> may store the data in the non-volatile memory device <NUM> or may read the data stored in the non-volatile memory device <NUM>.

In some embodiments, the non-volatile memory device <NUM> may be a NAND flash memory device, but the present invention is not limited thereto. For example, the non-volatile memory device <NUM> may be one of various storage devices, which retain data stored therein even though a power is turned off, such as a phase-change random access memory (PRAM), a magnetic random access memory (MRAM), a resistive random access memory (RRAM), and a ferroelectric random access memory (FRAM).

The storage controller <NUM> may include an indirect access module <NUM> and a module manager <NUM>. The indirect access module <NUM> may assist an operation of the file system of the operating system <NUM>. In general, because a file system manages a file, target data may be required. The target data may be included in a data block. As metadata, information (e.g., a pointer) indicating a location of the target data may be included in a metadata block.

To obtain target data, a general file system may sequentially access metadata blocks to read metadata, may obtain a target address of the target data from the metadata, and may read the target data of a data block based on the obtained target address. A processor of the host device <NUM> may be more excellent in performance than a processor of the storage controller <NUM>. However, in the case where the host device <NUM> directly processes metadata, because operations of receiving the metadata and returning the target address are performed, an input/output (I/O) load between the host device <NUM> and the storage device <NUM> may increase. This may mean that data processing is delayed.

According to an embodiment of the present invention, the indirect access module <NUM> may assist an operation that is necessary for the file system of the host device <NUM> to process metadata. For example, the indirect access module <NUM> may receive an access request for target data from the host device <NUM>. The access to the target data may include the direct access to the target data and the indirect access to the target data. For example, the direct access may refer to an operation of accessing a data block in which target data are stored, and the indirect access may refer to an operation of accessing a metadata block in which metadata indicating a target address are stored.

A request for an access may include an access parameter. The access parameter may indicate information that is received from the host device <NUM> and is necessary to retrieve target data or metadata corresponding to the target data. For example, the access parameter may include an identifier of target data, indirect layer information, return information, and the like. The identifier of the target data may mean a file byte offset, a record key, or the like for identifying the target data. The indirect layer information may indicate a specific indirect layer of a plurality of indirect layers included in the non-volatile memory device <NUM>. The return information may define a type of data to be returned to the host device <NUM>.

The indirect access module <NUM> may fetch metadata of a metadata block based on the access parameter of the request. The indirect access module <NUM> may determine a target address based on the access parameter and the fetched metadata. The indirect access module <NUM> may fetch target data in a data block based on the target address. The indirect access module <NUM> may return the target data to the host device <NUM>.

That is, the indirect access module <NUM> may instead perform a metadata-related operation that a general file system has performed, and thus, target data that the host device <NUM> requests may be provided directly without an additional I/O. The host device <NUM> may obtain target data through one request and one response. How the I/O load is reduced by the indirect access module <NUM> will be described in detail with reference to <FIG> and <FIG>.

The module manager <NUM> may manage the indirect access module <NUM>. The module manager <NUM> may execute the indirect access module <NUM> based on a request for an access (hereinafter referred to as an "access request") received from the host device <NUM>.

The indirect access module <NUM> and the module manager <NUM> may be implemented in the form of hardware, software, or a combination thereof. For example, in the case where the indirect access module <NUM> and the module manager <NUM> are implemented with hardware, the indirect access module <NUM> and the module manager <NUM> may be included in the storage controller <NUM> in the form of a separate module, circuit, or chip.

For example, in the case where the indirect access module <NUM> and the module manager <NUM> are implemented by software, the non-volatile memory device <NUM> may be used as a firmware memory together with a read only memory (ROM) in the storage controller <NUM>. Instructions corresponding to the indirect access module <NUM> and the module manager <NUM> may be stored in the non-volatile memory device <NUM> and may be loaded to the volatile memory (e.g., a main memory) of the storage controller <NUM> to communicate with the host device <NUM>.

The non-volatile memory device <NUM> may include a metadata block and a data block. The metadata block may include a plurality of metadata. The metadata may include at least one of a variety of information about data, such as a type of data, a location of the data, a way to access the data, and identification information. The data block may include a plurality of data. The data may correspond to a file that a file system manages. For example, the data block may include target data that the host device <NUM> requests.

In some embodiments, the metadata may indicate a location of data. For example, the metadata may include an address of data or may include an address of any other metadata indicating the address of the data. A structure in which data are indicated by a plurality of metadata may be referred to as a "multi-layer structure". The multi-layer structure will be described in detail with reference to <FIG> together.

As described above, according to an embodiment of the present invention, there may be provided the storage device <NUM> that includes the indirect access module <NUM> assisting a metadata-related operation of the host device <NUM>. The indirect access module <NUM> may process metadata and may provide the host device <NUM> with the direct access to target data. Accordingly, the I/O load between the host device <NUM> and the storage device <NUM> may be reduced, and a speed at which a data block is accessed may be improved.

<FIG> is a block diagram illustrating a storage controller of <FIG> in detail. Referring to <FIG> and <FIG>, the storage controller <NUM> may communicate with the host device <NUM> and the non-volatile memory device <NUM>. The storage controller <NUM> may include the indirect access module <NUM>, the module manager <NUM>, a processor <NUM>, a volatile memory device <NUM>, a read only memory (ROM) <NUM>, an error correcting code (ECC) engine <NUM>, a host interface circuit <NUM>, and a non-volatile memory interface circuit <NUM>. The indirect access module <NUM> and the module manager <NUM> are similar to the indirect access module <NUM> and the module manager <NUM> of <FIG>, and thus, additional description will be omitted to avoid redundancy.

In some embodiments, the indirect access module <NUM> and the module manager <NUM> may be implemented by software. In detail, the storage device <NUM> may include a firmware memory. The firmware memory may store a variety of information, which is necessary for the storage device <NUM> to operate, in the form of instructions. As the processor <NUM> executes the instructions stored in the firmware memory (i.e., the processor <NUM> loads the instructions to the volatile memory device <NUM>), the indirect access module <NUM> and the module manager <NUM> may be executed or implemented. Because the indirect access module <NUM> and the module manager <NUM> are implemented regardless of the operating system <NUM> of the host device <NUM>, the indirect access module <NUM> and the module manager <NUM> may be compatible with various kinds of operating systems. However, the present invention is not limited thereto. For example, the indirect access module <NUM> and the module manager <NUM> may be implemented with a separate hardware device(s) or may be implemented with a combination of hardware and software.

The processor <NUM> may control an overall operation of the storage controller <NUM>. The volatile memory device <NUM> may be used as a main memory, a buffer memory, a cache memory, or a working memory of the storage controller <NUM>. For example, the volatile memory device <NUM> may be implemented with a static random access memory (SRAM) or a dynamic random access memory (DRAM). In some embodiments, the indirect access module <NUM> and the module manager <NUM> loaded to the volatile memory device <NUM> may process a request for accessing target data, which is received from the host device <NUM>. The ROM <NUM> may be used as a read only memory that stores information necessary for the operation of the storage controller <NUM>.

The ECC engine <NUM> may detect and correct an error of data read from the non-volatile memory device <NUM>. For example, the ECC engine <NUM> may have an error correction capability of a given level. The ECC engine <NUM> may correct an error of data not exceeding the error correction capability and may process data having an error level (e.g., the number of flipped bits) exceeding the error correction capability as an uncorrectable error.

The storage controller <NUM> may communicate with the host device <NUM> through the host interface circuit <NUM>. The host interface circuit <NUM> may provide a host interface layer (HIL). In some embodiments, the host interface circuit <NUM> may be implemented based on at least one of various interfaces such as a serial ATA (SATA) interface, a peripheral component interconnect express (PCIe) interface, a serial attached SCSI (SAS), a nonvolatile memory express (NVMe) interface, and an universal flash storage (UFS) interface.

The storage controller <NUM> may communicate with the non-volatile memory device <NUM> through the non-volatile memory interface circuit <NUM>. In some embodiments, the non-volatile memory interface circuit <NUM> may be implemented based on a NAND interface.

<FIG> is a block diagram illustrating a non-volatile memory device of <FIG> in detail. Referring to <FIG> and <FIG>, the non-volatile memory device <NUM> may communicate with the storage controller <NUM>. For example, the non-volatile memory device <NUM> may receive the address ADD and the command CMD from the storage controller <NUM>. The non-volatile memory device <NUM> may exchange data with the storage controller <NUM>.

The non-volatile memory device <NUM> may include control logic <NUM>, a voltage generator <NUM>, a row decoder <NUM>, a memory cell array <NUM>, a page buffer unit <NUM>, a column decoder <NUM>, and an input/output (I/O) circuit <NUM>. The metadata block and the data block of <FIG> may be included in the memory cell array <NUM>.

The control logic <NUM> may receive the command CMD and the address ADD from the storage controller <NUM>. The command CMD may refer to a signal indicating an operation to be performed by the non-volatile memory device <NUM>, such as a read operation, a write operation, or an erase operation. The address ADD may include a row address ADDR and a column address ADDC. The control logic <NUM> may generate the row address ADDR and the column address ADDC based on the address ADD.

Under control of the control logic <NUM>, the voltage generator <NUM> may control voltages to be applied to the memory cell array <NUM> through the row decoder <NUM>.

The row decoder <NUM> may receive the row address ADDR from the control logic <NUM>. The row decoder <NUM> may be connected with the memory cell array <NUM> through string selection lines SSL, word lines WL, and ground selection lines GSL. The row decoder <NUM> may decode the row address ADDR and may control voltages to be applied to the string selection lines SSL, the word lines WL, and the ground selection lines GSL based on a decoding result and a voltage(s) received from the voltage generator <NUM>.

The memory cell array <NUM> may include a plurality of memory cells. Each of the memory cells may have a threshold voltage level corresponding to data. The memory cells may be arranged in a row direction and a column direction. Some of the memory cells may correspond to the metadata block and the data block of <FIG>. Others of the memory cells may store the instructions corresponding to the indirect access module <NUM> and the module manager <NUM> implemented by software in <FIG>. In some embodiments, the metadata block and the memory block may correspond to a physical erase unit of the non-volatile memory device <NUM>, but the present invention is not limited thereto. For example, the physical erase unit may be changed to a page unit, a word line unit, a sub-block unit, or the like.

The page buffer unit <NUM> may include a plurality of page buffers PB. The page buffer unit <NUM> may be connected with the memory cell array <NUM> through the bit lines BL. The page buffer unit <NUM> may read data from the memory cell array <NUM> in units of page, by sensing voltages of the bit lines BL.

The column decoder <NUM> may receive the column address ADDC from the control logic <NUM>. The column decoder <NUM> may decode the column address ADDC and may provide the data read by the page buffer unit <NUM> to the I/O circuit <NUM> based on a decoding result.

The column decoder <NUM> may receive data from the I/O circuit <NUM> through data lines DL. The column decoder <NUM> may receive the column address ADDC from the control logic <NUM>. The column decoder <NUM> may decode the column address ADDC and may provide the data received from the I/O circuit <NUM> to the page buffer unit <NUM> based on a decoding result. The page buffer unit <NUM> may store the data provided from the I/O circuit <NUM> in the memory cell array <NUM> through the bit lines BL in units of page.

The I/O circuit <NUM> may be connected with the column decoder <NUM> through the data lines DL. The I/O circuit <NUM> may provide data received from the storage controller <NUM> to the column decoder <NUM> through the data lines DL. The I/O circuit <NUM> may output data received through the data lines DL to the storage controller <NUM>.

<FIG> is a diagram describing a data processing method of a related art storage system. Referring to <FIG>, a storage system may include a host device and a storage device. The host device may include a file system. The file system manages files corresponding to an application. The storage device may include first to N-th metadata blocks MBK1, MBK2,. Each of the first to N-th metadata blocks MBK1 to MBKN may include first to i-th metadata. The storage device may include first to M-th data blocks DBK1, DBK2,. Each of the first to M-th data blocks DBK1 to DBKM may include first to j-th data DT1 to DTj. Herein, N, M, i, and j may be arbitrary natural numbers.

Below a method in which a related art storage system processes target data will be described.

In a first operation ①, the file system of the host device may request a first access to target data. The first access may be an indirect access to the target data or a direct access to metadata corresponding to the target data. The target data may be final data that the file system requires. The host device may issue a command such that a request for the first access to the target data is provided to the storage device. For example, the target data may be the first data DT1 of the first data block DBK1 (for better understanding of the present disclosure, in <FIG>, "TG" is written side-by-side together with target data and metadata corresponding to the target data).

In a second operation ②, the storage device may read first metadata MD1 of the first metadata block MBK1 based on the request for the first access in the first operation ①. The first metadata MD1 of the first metadata block MBK1 may be metadata associated with the target data. The storage device may provide the first metadata MD1 of the first metadata block MBK1 to the host device.

In a third operation ③, the file system of the host device may calculate an address of the target data based on the metadata received through the second operation ②. That is, a processor of the host device may process the metadata and may obtain an address corresponding to the metadata. For example, the file system may calculate an address of the first data DT1 in the first data block DBK1, based on the first metadata MD1 of the first metadata block MBK1.

In a fourth operation ④, the file system of the host device may request a second access to the target data, based on the address calculated in the third operation ③. For example, the second access may be a direct access to the target data. The file system may access the first data block DBK1 based on the address calculated from the first metadata MD1.

In a fifth operation ⑤, the storage device may provide the host device with the target data as a response to the request for the second access corresponding to the fourth operation ④. For example, the storage device may receive the second access request including the calculated address from the host device. The storage device may return the first data DT1 of the first data block DBK1 to the host device as a response to the request.

As described above, in the related art storage system, an operation of processing metadata (i.e., an operation in which an address is calculated from metadata) may be performed by the host device. Independently of requesting target data or receiving target data, the related art storage system may perform the second operation ② in which metadata are transferred and the fourth operation ④ in which an access is made based on a calculated address. The metadata processing operation may cause an increase in the I/O load between the host device and the storage device. The way to reduce the I/O load will be described with reference to <FIG>.

<FIG> is a diagram illustrating a data processing method according to some aspects of the present invention. Referring to <FIG>, the storage system <NUM> may include the host device <NUM> and the storage device <NUM>. The storage system <NUM>, the host device <NUM>, and the storage device <NUM> may respectively correspond to the storage system <NUM>, the host device <NUM>, and the storage device <NUM> of <FIG>.

The host device <NUM> may include a file system. The file system manages files corresponding to an application. The storage device <NUM> may include the first to N-th metadata blocks MBK1 to MBKN. Each of the first to N-th metadata blocks MBK1 to MBKN may include first to i-th metadata. The storage device <NUM> may include the first to M-th data blocks DBK1 to DBKM. Each of the first to M-th data blocks DBK1 to DBKM may include first to j-th data DT1 to DTj. Herein, N, M, i, and j may be arbitrary natural numbers.

The storage device <NUM> may include the indirect access module <NUM>. The indirect access module <NUM> may assist an operation of the file system of the host device <NUM>. The indirect access module <NUM> may correspond to the indirect access module <NUM> of <FIG> and <FIG>.

Below, a method in which the storage system <NUM> processes target data will be described, according to some aspects of the present invention.

In a first operation ①, the file system of the host device <NUM> may request an access to the target data. The access to the target data may include the direct access to the target data and the indirect access to the target data. For example, the direct access may refer to an operation of accessing a data block in which target data are stored, and the indirect access may refer to an operation of accessing a metadata block in which metadata indicated by a target address are stored. The target data may be final data that the file system requires.

The host device <NUM> may issue a command such that a request for the access to the target data is provided to the storage device <NUM>. For example, the target data may be the first data DT1 of the first data block DBK1 (for better understanding of the present disclosure, in <FIG>, "TG" is written side-by-side together with target data and metadata corresponding to the target data).

In a second operation ②, the indirect access module <NUM> of the storage device <NUM> may access a metadata block based on an access parameter of the request received through the first operation ①. The access parameter may indicate information that is received from the host device <NUM> and is necessary to retrieve the target data or metadata corresponding to the target data. For example, the access parameter may include an identifier of the target data, indirect layer information, return information, and the like.

For example, the indirect access module <NUM> may access the first metadata MD1 of the first metadata block MBK1 based on the access parameter of the request. The first metadata MD1 may be metadata associated with the target data.

In a third operation ③, the indirect access module <NUM> of the storage device <NUM> may calculate an address of the target data based on the access parameter and the metadata. For example, the indirect access module <NUM> may access the first metadata MD1 of the first metadata block MBK1 accessed through the second operation ②. The indirect access module <NUM> may calculate an address of the first data DT1 in the first data block DBK1, based on the access parameter and the first metadata MD1.

In a fourth operation ④, the indirect access module <NUM> may access a data block having target data, based on the address calculated in the third operation ③ and the access parameter. For example, the indirect access module <NUM> may access the first data DT1 of the first data block DBK1, based on the address calculated from the first metadata MD1 of the first metadata block MBK1.

In a fifth operation ⑤, the indirect access module <NUM> may fetch the target data located at the address calculated in the third operation ③. For example, the indirect access module <NUM> may fetch the first data DT1 of the first data block DBK1 accessed through the fourth operation ④, based on the calculated address.

In some embodiments, based on a return type included in the access parameter, the indirect access module <NUM> may fetch the target data or may fetch the data block including the target data.

In a sixth operation ⑥, the indirect access module <NUM> may provide the host device <NUM> with the target data fetched through the fifth operation ⑤. For example, the indirect access module <NUM> may provide the file system of the host device <NUM> with the first data DT1 thus fetched. The target data provided through the sixth operation ⑥ may be provided to the host device <NUM> as a response to the request in the first operation ①.

In some embodiments, based on the return type included in the access parameter, the indirect access module <NUM> may return the target data or may return the data block including the target data. The indirect access module <NUM> may determine whether to return metadata based on the return type included in the access parameter, when the determination is made to return the metadata, the indirect access module <NUM> may determine whether to return the metadata or whether to return a data block including the metadata.

As described above, according to an embodiment of the present invention, the indirect access module <NUM> of the storage device <NUM> may process the metadata. Without intervention of the host device <NUM>, the storage device <NUM> may fetch metadata, may obtain an address from the metadata, and may access a data block corresponding to the address. Unlike the related art storage system of <FIG>, as the I/O load between the host device and the storage device due to metadata processing, is reduced, the storage system <NUM> in which a data block access speed is improved may be provided.

<FIG> is a diagram describing a data processing method according to some aspects of the present invention. A method in which a storage system processes metadata according to some aspects of the present invention will be described with reference to <FIG>.

According to some embodiments of the present invention, the storage system may support a Linux operating system. For example, the host device <NUM> may support a file system of the Linux operating system. The storage device <NUM> may manage an inode according to the file system of the Linux operating system. The inode may be generated for each file and may include pointers for accessing a plurality of data, respectively.

The host device <NUM> may provide a request for the access to target data to the storage device <NUM>. The storage device <NUM> may provide the target data to the host device <NUM> based on the access request for the target data.

The storage device <NUM> may include a data layer, a first indirect layer, a second indirect layer, a third indirect layer, and a fourth indirect layer. The data layer may include at least one data block. Each of the first to fourth indirect layers may include at least one metadata block.

Each of the first to fourth indirect layers may be referred to as a high layer when it is relatively close to the host device <NUM> and may be referred to as a low layer when it is relatively close to the data layer. For example, the first indirect layer of the first to fourth indirect layers may be referred to as a "lowest indirect layer" The second indirect layer may be a lower layer compared to the third indirect layer but may be a high layer compared to the first indirect layer. The third indirect layer may be a lower layer compared to the fourth indirect layer but may be a high layer compared to the second indirect layer. The fourth indirect layer of the first to fourth indirect layers may be referred to as a "highest indirect layer".

When a request for the access to target data is received from the host device <NUM>, the storage device <NUM> may access an inode block INB. The storage device <NUM> may access another pointer or data based on a pointer of the inode block INB and may return final target data to the host device <NUM>.

The inode block INB may be a metadata block included in the fourth indirect layer. The inode block INB may include a direct pointer block DPBi, an indirect pointer block IPBi, a double indirect pointer block DIPBi, and a triple indirect pointer block TIPBi.

The direct pointer block DPBi may include a plurality of direct pointers. A direct pointer may refer to one of a variety of information included in metadata. A direct pointer may be used to directly access a data layer without separately passing through any other metadata blocks.

For example, a direct pointer of the direct pointer block DPBi may point data DT of the first data block DBK1 in the data layer. To prevent a drawing from being complicated, only a correspondence relationship of one direct pointer is illustrated in <FIG>, but pointers of the direct pointer block DPBi may point any other data in the data layer.

The indirect pointer block IPBi may include a plurality of indirect pointers. Below, for better understanding, an indirect pointer is intended to refer to a single indirect pointer. An indirect pointer may refer to one of a variety of information included in metadata. An indirect pointer may be used to access the data layer through the first indirect layer.

For example, an indirect pointer of the indirect pointer block IPBi may point a direct pointer of the first direct pointer block DPB1 of the first indirect layer. The direct pointer of the first direct pointer block DPB1 may point data DT of the second data block DBK2 in the data layer.

The double indirect pointer block DIPBi may include a plurality of double indirect pointers. A double indirect pointer may refer to one of a variety of information included in metadata. A double indirect pointer may be used to sequentially pass through the second indirect layer and the first indirect layer to access the data layer.

For example, a double indirect pointer of the double indirect pointer block DIPBi may point an indirect pointer of a first indirect pointer block IPB1 of the second indirect layer. The indirect pointer of the first indirect pointer block IPB <NUM> may point a direct pointer of a second direct pointer block DPB2 of the first indirect layer. The direct pointer of the second direct pointer block DPB2 may point data DT of the third data block DBK3 in the data layer.

The triple indirect pointer block TIPBi may include a plurality of triple indirect pointers. A triple indirect pointer may refer to one of a variety of information included in metadata. A triple indirect pointer may be used to sequentially pass through the third indirect layer, the second indirect layer, and the first indirect layer to access the data layer.

For example, a triple indirect pointer of the triple indirect pointer block TIPBi may point a double indirect pointer of a double indirect pointer block DIPB of the third indirect layer. The double indirect pointer of the double indirect pointer block DIPB may point an indirect pointer of a second indirect pointer block IPB2 of the second indirect layer. The indirect pointer of the second indirect pointer block IPB2 may point a direct pointer of a third direct pointer block DPB3 of the first indirect layer. The direct pointer of the third direct pointer block DPB3 may point data DT of the fourth data block DBK4 in the data layer.

In some embodiments, depending on the request of the host device <NUM>, the storage device <NUM> may return the target data together with pointers corresponding to the target data. For example, the request from the host device <NUM> may include an access parameter. The access parameter may include return information. When returning the target data as a result of accessing the data layer, based on the return information, the storage device <NUM> may return only the target data or may return the target data together with some or all of pointers corresponding to the target data. For example, in the case where the return information requests the return of all pointers and target data are indicated by a triple indirect pointer of the inode block INB, the storage device <NUM> may return, to the host device <NUM>, the target data together with a triple indirect pointer, a double indirect pointer, an indirect pointer, and a direct pointer corresponding to the target data.

Alternatively, based on the return information of the access parameter, the storage device <NUM> may return, to the host device <NUM>, <NUM>) a triple indirect pointer block including a triple indirect pointer, <NUM>) a double indirect pointer block including a double indirect pointer, <NUM>) an indirect pointer block including an indirect pointer, <NUM>) a direct pointer block including a direct pointer, and <NUM>) a data block including target data.

In some embodiments, the storage device <NUM> may receive a request for an access corresponding to a layer lower than a layer of the inode block INB. For example, the storage device <NUM> may return corresponding pointers together with previous target data to the host device <NUM>. Instead of an address corresponding to a pointer of the inode block INB, the host device <NUM> may provide the storage device <NUM> with an address corresponding to a pointer of the first indirect layer as a portion of the access parameter of the request, based on information loaded to a main memory or a cache memory of the host device <NUM>. In this case, instead of performing pointer processing sequentially from the inode block INB, the storage device <NUM> may start pointer processing from the first indirect layer based on the address received from the host device <NUM> as a portion of the access parameter.

In some embodiments, as the number of indirect layers increases, a storage capacity may increase, but a data access may be delayed. For example, in the case where the inode block INB uses only a direct pointer, the inode block INB may manage a file whose size is 4KB. In the case where the inode block INB uses an indirect pointer, the inode block INB may manage a file whose size is 2MB. In the case where the inode block INB uses a double indirect pointer, the inode block INB may manage a file whose size is 1GB. In the case where the inode block INB uses a triple indirect pointer, the inode block INB may manage a file whose size is 512GB. However, as a level of an indirect pointer becomes higher, the number of times of a block access required to obtain target data may increase. This may mean that data processing is delayed. That a level of an indirect pointer is high may mean that the number of pointers to be sequentially processed to obtain target data is many.

In the case of a related art storage system (e.g., the storage system of <FIG>) in which the host device calculates an address of data of a next block (e.g., a pointer block or a data block) from a pointer, as a level of a pointer becomes higher, the number of times of an input/output between the host device and the storage device may increase.

In contrast, according to an embodiment of the present invention, because the storage device <NUM> automatically calculates an address of a next block from a pointer without intervention of the host device <NUM>, even though an indirect pointer of a high level is used, the I/O load may not increase. That is, the storage device <NUM> according to an embodiment of the present invention may manage a large amount of data together with minimizing a delay of data processing.

An operation in which the storage device <NUM> processes a pointer may be performed by an indirect access module in the storage device <NUM>. For example, the storage device <NUM> may include an indirect access module corresponding to the inode block INB. The indirect access module may be compatible with the Linux operating system. The indirect access module may support a pointer processing operation of a file system, which starts from the inode block INB. An access parameter of a request received from the host device <NUM> may be used to process at least one of a direct pointer, an indirect pointer, a double indirect pointer, and a triple indirect pointer of the inode block INB. For example, an access parameter received from a host may include an address of a pointer to be processed, and information of a layer in which the pointer is included.

According to some embodiments of the present invention, a storage system may support a RocksDB. For example, the host device <NUM> may provide an access request compatible with a file store format of the RocksDB. The storage device <NUM> may store a key-value in a serialized certificate store (SST) file structure of the file store formats of the RocksDB.

The host device <NUM> may provide a request for the access to target data to the storage device <NUM>. The storage device <NUM> may provide the target data to the host device <NUM> based on an access parameter of the request. For example, the target data may be the data DT of the first data block DBK1 (for better understanding of the present disclosure, in <FIG>, "TG" is written side-by-side together with target data).

The storage device <NUM> may include an SST file. The SST file may include a footer, an index block, a metaindex block, the first to N-th metadata blocks MBK1 to MBKN, and the first to M-th data blocks DBK1 to DBKM. Herein, N and M may be arbitrary natural numbers.

The footer may include a metaindex handler and an index handler. The metaindex handler may indicate a location of metadata. The index handler may indicate a location of a data block handler.

The index block may include a plurality of data block handlers. The data block handler may indicate a location of target data. For example, the data block handler may indicate a data block including the target data from among the first to M-th data blocks DBK1 to DBKM, or may indicate a location of the target data in a corresponding data block.

The metaindex block may include a plurality of metadata block handlers. The metadata block handler may indicate a location of a metadata block or a location of metadata in the metadata block. For example, the metadata block handler may indicate a location of a metadata block necessary to process the target data from among the first to N-th metadata blocks MBK1 to MBKN or may indicate a location of metadata in a metadata block.

Each of the first to M-th data blocks DBK1 to DBKM may include a plurality of data. Data may correspond to a portion of the SST file that is managed by the host device <NUM>.

Each of the first to N-th metadata blocks MBK1 to MBKN may include a plurality of metadata. For example, metadata may include a Bloom filter indicating whether there is a key-value corresponding to target data, a stats for estimating a table size and the number of records, a dictionary for compressing or decompressing a data block, a range deletion for deleting key-values of a given range, and the like. A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.

Below, a method in which a storage system processes target data according to some aspects of the present invention will be described. The storage system may include the host device <NUM> and the storage device <NUM>. The host device <NUM> may provide a request for the access to target data to the storage device <NUM>.

In a first operation ①, the storage device <NUM> may access the footer based on the request. The request may include an access parameter. The storage device <NUM> may refer to the index handler of the footer based on the access parameter and may access the index block. The storage device <NUM> may check a location of a data block including the data DT, based on the access parameter and the data block handler in the accessed index block.

In a second operation ②, the storage device <NUM> may refer to the metaindex handler of the footer based on the access parameter and may access the metaindex block.

In a third operation ③, the storage device <NUM> may read the metadata block handler in the metaindex block accessed through the second operation ② and may access the metadata block based on the access parameter and the metadata block handler. The storage device <NUM> may process metadata in the accessed metadata block. For example, the storage device <NUM> may access the first metadata block MBK1 with reference to the metaindex block handler in the metaindex block. The storage device <NUM> may determine that there is a key-value corresponding to the target data, based on the Bloom filter information of the first metadata block MBK1.

In a fourth operation ④, the storage device <NUM> may access a data block. For example, the storage device <NUM> may access the data DT of the first data block DBK1, based on the target data identifier (e.g., a record key corresponding to the target data) included in the access parameter, the location of the data DT obtained in the first operation ①, and the metadata processed in the third operation ③. Afterwards, the storage device <NUM> may provide the host device <NUM> with the data DT obtained through the fourth operation ④ or the first data block DBK1 including the data DT.

The operations of the storage device <NUM> necessary to process the index handler, the metaindex handler, the data block handler, and the metadata block handler may be performed by the indirect access module in the storage device <NUM>. The indirect access module may be compatible with the RocksDB. The access parameter of the request received from the host device <NUM> may be used to process the metaindex handler and the index handler of the footer.

<FIG> is a block diagram of a storage which may be operated according to embodiments of the present invention. A block diagram of the storage device <NUM> is illustrated in <FIG>. The storage device <NUM> may correspond to the storage device <NUM> of <FIG>, <FIG>, <FIG>, and <FIG>.

The storage device <NUM> may communicate with the host device <NUM>. The storage device <NUM> may receive a request for the access to target data from the host device <NUM>. After performing a metadata-related operation according to the access request for the target data, the storage device <NUM> may provide the target data to the host device <NUM>.

The storage device <NUM> may include first to N-th indirect access modules <NUM>-<NUM> to <NUM>-N, the module manager <NUM>, the host interface circuit <NUM>, and the non-volatile memory device <NUM>. Herein, "N" is an arbitrary natural number.

The host interface circuit <NUM> may provide an interface between the host device <NUM> and the storage device <NUM>. For example, the host interface circuit <NUM> may communicate with the host device <NUM>. The host interface circuit <NUM> may provide the module manager <NUM> or a corresponding indirect access module with the access request for the target data received from the host device <NUM>. The host interface circuit <NUM> may provide the target data received from the corresponding indirect access module to the host device <NUM>.

The non-volatile memory device <NUM> may include first to N-th data sets DS1 to DSN. Each of the first to N-th data sets DS1 to DSN may include a plurality of data blocks DBK and a plurality of metadata blocks MBK. Each of the first to N-th data sets DS1 to DSN may correspond to a file or a software program that is managed by the host device <NUM>, but the present invention is not limited thereto.

In some embodiments, the first to N-th indirect access modules <NUM>-<NUM> to <NUM>-N may respectively manage the first to N-th data sets DS1 to DSN. For example, an operating system of the host device <NUM> may execute a first application and a second application. The first data set DS1 may correspond to the first application, and the second data set DS2 may correspond to the second application. The first indirect access module <NUM>-<NUM> may manage the first data set DS1 associated with the first application (e.g., may manage the access to data included in the first data set DS1). The second indirect access module <NUM>-<NUM> may manage the second data set DS2 associated with the second application (e.g., may manage the access to data included in the second data set DS2).

In detail, in the case where target data are included in the data block DBK of the first data set DS1, based on the access request received from the host device <NUM>, the first indirect access module <NUM>-<NUM> may perform a metadata processing operation, may fetch the target data of the data block DBK, and may provide the fetched target data to the host device <NUM>. In this case, the second to N-th indirect access modules <NUM>-<NUM> to <NUM>-N may not perform the above operation associated with the target data. That is, the storage device <NUM> may include an indirect access module that manages a program or a file individually.

<FIG> is a flowchart describing a method of operating a storage device according to some aspects of the present invention. A method of operating a storage device according to some aspects of the present invention will be described with reference to <FIG>. The storage device communicates with a host device. The storage device may correspond to the storage device <NUM> of <FIG>, <FIG>, <FIG>, <FIG>, and <FIG>.

In operation S110, the storage device receives a request for the access to target data from the host device. The access to the target data may include the direct access to the target data and the indirect access to metadata corresponding to the target data. The target data may be data stored in a data block of the storage device.

In operation S120, the storage device executes an indirect access module based on the request received in operation S110. For example, the storage device may include a processor, a volatile memory device, and a non-volatile memory device. As the processor executes instructions stored in the non-volatile memory device, the indirect access module may be executed.

In operation S130, the indirect access module of the storage device determines a target address indicating a location of the target data, based on an access parameter of the request. For example, the request received from the host device may include the access parameter. The access parameter may include information that is necessary to retrieve the target data or metadata corresponding to the target data. For example, the access parameter may include an identifier of target data, indirect layer information, return information, and the like.

The storage device may fetch metadata in a metadata block, based on the access parameter included in the request. The storage device may determine a target address indicating a location of the target data, based on the fetched metadata. In this case, because the storage device automatically determines the target address based on the metadata, without intervention of the host device, the I/O load between the host device and the storage device may not be caused.

In operation S140, the indirect access module of the storage device accesses a data block based on the target address. The accessed data block may include the target data requested in operation S110. In this case, the storage device may access the data block including the target data, based on the address determined in operation S130 without the intervention of the host device.

In operation S150, the indirect access module of the storage device provides the target data in the accessed data block to the host device. That is, the host device may obtain the target data based on the I/O operation of providing the request in operation S110 and receiving the target data in operation S150.

In some embodiments, based on return information included in the access parameter, the indirect access module may determine whether to return the target data or may return the data block including the target data. The indirect access module may provide the host device with the data block accessed in operation S140 or the target data in the data block based on the return information.

<FIG> is a flowchart describing a method of operating a storage device according to some aspects of the present invention. A method of operating a storage device according to some aspects of the present invention will be described with reference to <FIG>. The storage device communicates with a host device. The storage device may correspond to the storage device <NUM> of <FIG>, <FIG>, <FIG>, <FIG>, and <FIG>. Operation S210 is similar to operation S110 of <FIG>, and thus, additional description will be omitted to avoid redundancy.

In operation S220, the storage device determines whether an indirect access module is present in a non-volatile memory device. For example, the storage device may include a non-volatile memory device and a processor. As the processor executes instructions stored in the non-volatile memory device, the indirect access module may be implemented or executed. However, when the indirect access module is absent from the non-volatile memory device, an operation of downloading the indirect access module may be further required.

When it is determined in operation S220 that the indirect access module is absent from the non-volatile memory device, the storage device performs operation S221. When it is determined in operation S220 that the indirect access module is present in the non-volatile memory device, the storage device may perform operation S222.

In operation S221, the storage device downloads the indirect access module. For example, the storage device may download the indirect access module from the host device. The indirect access module may be stored in the non-volatile memory device of the storage device in the form of an instruction.

In operation S222, the storage device may determine whether the indirect access module is loaded. For example, the storage device may include a non-volatile memory device, a volatile memory device, and a processor. The operation S222 may determine whether the indirect access module loaded in the volatile memory device.

The non-volatile memory device may include instructions corresponding to the indirect access module. The instructions may be instructions stored in advance and may be the instructions downloaded through operation S221. As the processor executes instructions stored in the non-volatile memory device, the indirect access module may be loaded to the volatile memory device. The indirect access module loaded to the volatile memory device may process a request received from the host device. That is, the non-volatile memory device may be used as a firmware memory, and the volatile memory device may be used as a main memory.

When it is determined in operation S222 that the indirect access module is not loaded, the storage device may perform operation S223. Operation S223 may include loading the indirect access module in the volatile memory device. In some embodiments of S223, the recently-loaded indirect access module may then be used.

When it is determined in operation S222 that the indirect access module is loaded, the storage device may perform operation S224.

In operation S223, the storage device may load the indirect access module to the volatile memory.

In operation S224, the storage device may use a pre-loaded indirect access module. That is, because the indirect access module is already loaded to the volatile memory device, the pre-loaded indirect access module may be used without again loading the indirect access module.

<FIG> is a flowchart describing a method of operating a storage device according to some aspects of the present invention. A method of operating a storage device according to some aspects of the present invention will be described with reference to <FIG>. The storage device may communicate with a host device. The storage device may correspond to the storage device <NUM> of <FIG>, <FIG>, <FIG>, <FIG>, and <FIG>. Operation S320 is similar to operation S120 of <FIG>, and thus, additional description will be omitted to avoid redundancy. The storage device may include an indirect access module.

In operation S310, the storage device may receive a request for the access to target data from the host device. For example, the access request may include an access parameter. The access parameter may include indirect layer information. The indirect layer information may point the first indirect layer in which metadata for accessing target data is present.

In this case, the first indirect layer may refer to only one of a plurality of indirect layers that the storage device supports, and the present invention is not limited thereto. For example, the first indirect layer may refer to the highest indirect layer or the lowest indirect layer. However, the first indirect layer is not limited to the highest indirect layer or the lowest indirect layer.

In some embodiments, the storage device may start a metadata-related operation (or metadata processing operation) from any other indirect layer being not the highest indirect layer from among the plurality of indirect layers. For example, the first indirect layer mentioned in operation S310 may not be the highest indirect layer of the plurality of indirect layers that the storage device supports. That is, the host device may request target data from an intermediate indirect layer, based on the cached metadata.

In operation S330, the indirect access module of the storage device may fetch first metadata from the first indirect layer based on the indirect layer information of the access parameter received in operation S310. The first metadata may point a location of second metadata included in the second indirect layer or a location of third metadata included in the second indirect layer. The second indirect layer may be a layer lower than the first indirect layer. For example, the second indirect layer may be closer to a data layer lower than the first indirect layer. The data layer may include the target data requested in operation S310.

In operation S331, the indirect access module of the storage device may determine whether the second indirect layer pointed by the first metadata is the lowest indirect layer. The lowest indirect layer may refer to a layer that is directly mapped onto the data layer. For example, metadata in the lowest indirect layer may indicate an address of data in a data layer.

When it is determined in operation S331 that the second indirect layer is the lowest indirect layer, the storage device may perform operation S332. When it is determined in operation S331 that the second indirect layer is not the lowest indirect layer, the storage device may perform operation S333.

In operation S332, the indirect access module of the storage device may fetch second metadata from the second indirect layer based on the first metadata. The indirect access module of the storage device may determine a target address based on the second metadata. For example, the second indirect layer may be the lowest indirect layer. The indirect access module of the storage device may determine the target address of the target data based on the second metadata in the second indirect layer being the lowest indirect layer.

In operation S333, the indirect access module of the storage device may fetch third metadata from the second indirect layer based on the first metadata. The indirect access module of the storage device may access the third indirect layer based on the third metadata. The third indirect layer may be a layer lower than the second indirect layer. For example, the third indirect layer may be closer to the data layer lower than the second indirect layer.

In some embodiments, the storage device may receive an access parameter including the indirect layer information indicating the lowest indirect layer. For example, in operation S330, the first indirect layer may be the lowest indirect layer. The first metadata may directly indicate the target address of the target data. In this case, operation S331, operation S332, and operation S333 may be omitted, and the indirect access module of the storage device may fetch the target data in the data layer based on the access parameter and the first metadata.

<FIG> is a flowchart describing a method of operating a storage device according to some aspects of the present invention. A method of operating a storage device according to some aspects of the present invention will be described with reference to <FIG>. The storage device may communicate with a host device. The storage device may correspond to the storage device <NUM> of <FIG>, <FIG>, <FIG>, <FIG>, and <FIG>. Operation S420, operation S430, and operation S440 are similar to operation S120, operation S130, and operation S140 of <FIG>, and thus, additional description will be omitted to avoid redundancy. The storage device may include an indirect access module.

In operation S410, the storage device may receive a request for the access to target data from the host device. The access request may include an access parameter. The access parameter may include return information. The return information may define a type of data to be returned to the host device <NUM> depending on the request.

For example, a return type may define whether to return target data or whether to return a data block including the target data. Alternatively, the return type may define whether to return metadata corresponding to the target data. In the case of returning metadata, the return type may define whether to return the metadata or whether to return a metadata block including the metadata. In the case where a plurality of metadata are used to obtain target data, the return type may define <NUM>) at least one metadata to be returned to the host device from among the plurality of metadata, and <NUM>) whether to return the at least one metadata to be returned or metadata blocks associated with the at least one metadata.

In operation S450, the indirect access module of the storage device may fetch the data block accessed in operation S440 or may fetch the target data in the data block. The target data may include the data requested in operation S410.

In operation S451, the indirect access module of the storage device may return the target data based on the return information. For example, based on the return information, the indirect access module of the storage device may provide the host device with the data block fetched in operation S450 or all the metadata or some metadata together with the target data fetched in operation S450.

<FIG> is a block diagram of a storage system which may be operated according to embodiments of the present invention. A storage system which may be operated according to embodiments of the present invention will be described with reference to <FIG>. A storage system <NUM> may correspond to the storage system <NUM> of <FIG>. The storage system <NUM> may be also referred to as a "storage box" including two or more storage devices, for example storage device <NUM>, storage device <NUM>, storage device <NUM>,. , storage device N00. As illustrated in <FIG>, the two or more storage devices may include respective storage controllers <NUM>, <NUM>, <NUM>,. , and N10 and respective non-volatile memory devices <NUM>, <NUM>, <NUM>,.

The storage system <NUM> may include the host device <NUM>, a storage box controller <NUM>, a PCIe switch <NUM>, and a plurality of storage devices <NUM> to N00. The host device <NUM> may correspond to the host device <NUM> of <FIG>.

The storage box controller <NUM> may communicate with the host device <NUM>. The storage box controller <NUM> may communicate with the plurality of storage devices <NUM> to N00 through the PCIe switch <NUM>. Each of the plurality of storage devices <NUM> to N00 may store data.

In some embodiments, the storage box controller <NUM> may include at least one indirect access module and a module manager. The module manager may manage the at least one indirect access module. The at least one indirect access module may assist an operation of processing metadata associated with a plurality of data respectively stored in the plurality of storage devices <NUM> to N00.

That is, an operation of the storage box controller <NUM> may be similar to the operation of the storage controller <NUM> of <FIG>, and an operation of each of the plurality of storage devices <NUM> to N00 may be similar to the operation of the non-volatile memory device <NUM> of <FIG>.

According to an embodiment of the present invention, a method of operating a storage device including an indirect access module, and a method of operating a storage system including the same are provided.

Also, as the indirect access module processes metadata and provides the access to target data, a storage device in which the input/output load between a host device and the storage device is reduced and a data block access speed is improved, a method of operating the storage device, and a method of operating a storage system including the storage device are provided.

Claim 1:
A method of operating a storage device (<NUM>) which communicates with a host device (<NUM>), the method comprising:
receiving (S110; S210; S310) a request for an access to target data (DT(TG); DT1(TG)) from the host device (<NUM>);
executing (S120; S320; S420) an indirect access module (<NUM>) based on the request;
based on an access parameter of the request, determining (S130; S430), by the indirect access module (<NUM>), a target address indicating a location of the target data (DT1(TG); DT(TG));
accessing (S140; S440), by the indirect access module (<NUM>), a data block (DBK1) based on the target address;
the method further comprises providing (S150), by the indirect access module (<NUM>), the host device (<NUM>) with the accessed data block (DBK1) or the target data (DT1(TG); DT(TG)) in the accessed data block (DBK1), and
wherein the storage device (<NUM>) includes a non-volatile memory device (<NUM>), and
wherein the executing (S120; S320; S420) the indirect access module (<NUM>) based on the request includes:
determining (S220) whether the indirect access module (<NUM>) is present in the non-volatile memory device (<NUM>) of the storage device (<NUM>);
based on determining that the indirect access module (<NUM>) is absent, downloading (S221) the indirect access module (<NUM>) from the host device (<NUM>); and
executing the indirect access module (<NUM>).