Patent Description:
A file system, such as the extended file system <NUM> (EXT4), overwrites new data to the original location when random data is updated. This is referred to as an in-place-update scheme. A log-structured file system (LFS) uses an out-of-place update scheme that invalidates old data and writes new data to another location.

From document <CIT> there is known a method of operating a storage device including at least one nonvolatile storage and a storage controller configured to control the nonvolatile storage. A first type of request, original data and a first request information associated with the original data are received, in the storage controller, from an external host device, a compression operation to compress the original data to generate compressed data is performed in the storage controller, in response to the first type of request, and a write operation to write the compressed data in a data storage area of the nonvolatile storage is performed in the storage controller. The external host manages mapping information in the form of a mapping table associated with compression/decompression at the storage device.

From document <CIT> there are known techniques for processing unaligned IO requests in data storage systems that provide optimization of inline compression. The disclosed techniques employ an unaligned IO cache, which is used by a data storage system to process unaligned IO requests containing data with sizes that are not multiples of a predetermined block size. By employing the unaligned IO cache while processing such unaligned IO requests, the data storage system can reduce the number of read-modify-write sequences required to process a sequential load of unaligned IO requests, thereby reducing the burden on processing resources of the data storage system.

From document <CIT> there is known a line-based memory capacity compression scheme that can be employed where additional translation of a physical address (PA) to a physical buffer address is performed to allow compressed data in a system memory at the physical buffer address for efficient compressed data storage. A translation lookaside buffer (TLB) is employed to store TLB entries comprising PA tags corresponding to a physical buffer address in the system memory to more efficiently perform the translation of the PA to the physical buffer address in the system memory.

Embodiments of the inventive concept relate to a computing system, and provides a computing system having increased write performance by writing a merged block into which a compressed data block, a node identifier, and an offset are merged, asynchronously with a node block.

According to an aspect of the inventive concept, there is provided a computing system including a storage system configured to store data and a host configured to compress a data block of a preset size loaded to a memory, generate a merged block of the preset size by merging a compressed block corresponding to the data block, an identifier of a node block referring the data block, and an offset indicating an index of the data block among at least one data block referred by the node block, and provide the merged block to the storage system.

According to an aspect of the inventive concept, there is provided a host device that writes data to a storage system, the host device including a memory that stores data to be written to the storage system or data read from the storage system, a compression manager configured to compress a data block of a preset size loaded to the memory, and a file system configured to receive a compressed block corresponding to the data block from the compression manager, generate a merged block by merging the compressed block, an identifier of a node block referring the data block, and an offset indicating an index of the data block among at least one data block referred by the node block, and write the merged block to the storage system.

According to an aspect of the inventive concept, there is provided a computing system including a universal flash storage (UFS) system including a plurality of storage regions and a UFS host configured to store a merged block into which a compressed block in which a data block is compressed, an identifier of a node block referring the data block, and an offset indicating an index of the data block among at least one data block referred by the node block are merged, in a first storage region among the plurality of storage regions, and store a node block indicating the address of the data block in a second storage region among the plurality of storage regions.

Embodiments of the inventive concept will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings, in which:.

Embodiments of the inventive concept will be described more fully hereinafter with reference to the accompanying drawings. Like reference numerals may refer to like elements throughout the accompanying drawings.

It will be understood that the terms "first," "second," "third," etc. are used herein to distinguish one element from another, and the elements are not limited by these terms. Thus, a "first" element in an embodiment may be described as a "second" element in another embodiment.

It should be understood that descriptions of features or aspects within each embodiment should typically be considered as available for other similar features or aspects in other embodiments, unless the context clearly indicates otherwise.

Herein, when one value is described as being about equal to another value or being substantially the same as or equal to another value, it is to be understood that the values are identical, the values are equal to each other within a measurement error, or if measurably unequal, are close enough in value to be functionally equal to each other as would be understood by a person having ordinary skill in the art. For example, the term "about" as used herein is inclusive of the stated value and means within an acceptable range of deviation for the particular value as determined by one of ordinary skill in the art, considering the measurement in question and the error associated with measurement of the particular quantity (i.e., the limitations of the measurement system). For example, "about" may mean within one or more standard deviations as understood by one of the ordinary skill in the art. Further, it is to be understood that while parameters may be described herein as having "about" a certain value, according to embodiments, the parameter may be exactly the certain value or approximately the certain value within a measurement error as would be understood by a person having ordinary skill in the art.

<FIG> is a diagram of a computing system according to an embodiment of the inventive concept.

Referring to <FIG>, a computing system <NUM> may include a host <NUM> and a storage system <NUM>.

The host <NUM> may provide a write request, a read request, or an erase request for data to the storage system <NUM>. The storage system <NUM> may store data in a storage region in response to the write request, read data stored in the storage region and provide the read data to the host <NUM> in response to the read request, and perform an erase operation on the data in response to the erase request. The data may be stored or read in the unit of a preset block (e.g., <NUM> KB).

The host <NUM> may include a file system <NUM>. The file system <NUM> may process the data such that the data may be stored in a particular logical or physical location in storage regions included in the storage system <NUM>. For example, the file system <NUM> may process data provided from a user application and store the processed data in the storage system <NUM>.

In this case, in an embodiment, the file system <NUM> may be a log-structured file system (LFS). For example, the file system <NUM> may be a flash-friendly file system (F2FS) that is a file system for a Linux kernel designed according to flash memory characteristics, or a j ournaling flash file system (JFFS) that is a Linux LFS used in a NOR flash memory device.

However, the type of the file system <NUM> is not limited to LFS, and embodiments of the inventive concept may be applied to any file system of a type in which new data is written to a logical address that is different from a logical address to which existing data is written, when a file is updated.

The storage system <NUM> may include a storage controller <NUM> and a storage device <NUM>. The storage device <NUM> may include at least one non-volatile memory. The storage controller <NUM> may convert a logical address received from the host <NUM> into a physical address and control the storage device <NUM> to store data in a storage region having the physical address.

The storage system <NUM> may include storage media in which data is stored in response to a request from the host <NUM>. For example, the storage system <NUM> may include one or more solid state drives (SSDs). When the storage system <NUM> includes SSDs, the storage device <NUM> may include multiple flash memory chips (e.g., NAND memory chips) that store data in a non-volatile manner. The storage device <NUM> may correspond to one flash memory device, or the storage device <NUM> may include a memory card including one or more flash memory chips.

When the storage system <NUM> includes a flash memory, the flash memory may include a two-dimensional (2D) NAND memory array or a three-dimensional (3D) (or vertical) NAND (VNAND) memory array. The 3D memory array may be formed monolithically in arrays of memory cells having active regions arranged on a silicon substrate or at least one physical level of a circuit related to operations of the memory cells and formed on or in the substrate. The term "monolithic" means that layers of each level constituting the array are stacked immediately on layers of each lower level of the array.

In an embodiment of the inventive concept, the 3D memory array may include VNAND strings arranged vertically such that at least one memory cell is located on another memory cell. The at least one memory cell may include a charge trap layer.

In another example, the storage system <NUM> may include other various types of memories. For example, the storage system <NUM> may include non-volatile memory such as, for example, magnetic random access memory (MRAM), spin-transfer torque MRAM, conductive bridging RAM (CBRAM), ferroelectric RAM (FeRAM), phase RAM (PRAM), resistive RAM, nanotube RAM, polymer RAM (PoRAM), nano floating gate memory (NFGM), holographic memory, molecular electronics memory, insulator resistance change memory, etc..

For example, the storage device <NUM> may include an embedded multi-media card (eMMC) or an embedded universal flash storage (UFS) memory device. In an example, the storage device <NUM> may be external memory detachably attached to the storage system <NUM>. For example, the storage device <NUM> may include, but is not limited to, a UFS memory card, a compact flash (CF) card, secure digital (SD) card, a microSD card, a miniSD card, an extreme digital (xD) card, or a memory stick.

The host <NUM> may communicate with the storage system <NUM> through various interfaces. For example, the host <NUM> may communicate with the storage system <NUM> through various interfaces such as universal serial bus (USB), multimedia card (MMC), PCI-express (PCI-E), AT attachment (ATA), serial AT attachment (SATA), parallel AT attachment (PATA), small computer system interface (SCSI), serial attached SCSI (SAS), enhanced small disk interface (ESDI), interchanged drive electronics (IDE), non-volatile memory express (NVMe), etc..

The host <NUM> may transmit a write request (or a write command) for new data to the storage system <NUM> when data of a random file is updated with the new data.

Herein, data provided to the file system <NUM> from the user application may be referred to as file data. The file data may be stored in the storage system <NUM> in the unit of a preset block (e.g., <NUM> KB), and the file data in the unit of a block may be referred to as a data block. The file data may include a plurality of data blocks.

The file system <NUM> may generate a node block corresponding to the data block. The node block may include information about the data block. For example, the node block may include a name of a file, a node identifier, a size of the file, or a logical address of the data block. In an embodiment, the name of the file refers to a name of the file formed of the data block, the node identifier is a unique identifier for the node block, and the size of the file refers to the size of the file formed of the data block. A node block may refer the plurality of data blocks, and each of the plurality of data blocks may be identified based on an offset.

The node block may be stored in the storage system <NUM> in the unit of a preset block (e.g., <NUM> KB). For example, the node block may be used to find a location of the data block. For example, the file system <NUM> may allocate a node identifier to each node block. The file system <NUM> may manage a node identifier and a logical address corresponding to the node identifier through a node address table (NAT). The file system <NUM> may access a node block through the NAT and access a data block by identifying a logical address of the data block, stored in the node block.

The host <NUM> according to an embodiment of the inventive concept may include a compression manager <NUM>. The compression manager <NUM> may generate a compressed block by compressing the data block. The file system <NUM> may generate a block in a preset unit (e.g., <NUM> KB) by merging the compressed block, the node identifier of the node block corresponding to the data block, and the offset of the data block. Herein, the block generated by merging the compressed block, the node identifier, and the offset may be referred to as a merged block. A node block may refer a plurality of data blocks corresponding to a file data. A node block may identify each of the plurality of data blocks based on offset. The offset included in the merged block may be information for identifying the data block among the plurality of data blocks. In some embodiments of the inventive concept, the merged block may include a bit indicating the merged block. The compression manager <NUM> may also be referred to as a compression circuit or a compression manager circuit.

The file system <NUM> may asynchronously write the merged block and the node block corresponding to the merged block to the storage system <NUM>. That is, a time period in which the merged block is transmitted to the storage system <NUM> and a time period in which the node block is transmitted to the storage system <NUM> may be discontinuous. For example, the merged block may be transmitted to the storage system <NUM> at a different time than the time at which the node block is transmitted to the storage system <NUM>. For example, the file system <NUM> may write the merged block to the storage system <NUM> in response to a request of the user application and write the node block to the storage system <NUM> in a time period where an interface between the host <NUM> and the storage system <NUM> is in an idle state. Thus, a time period in which the interface between the host <NUM> and the storage system <NUM> is occupied by the node block and a time period in which the interface is occupied by the merged block may be distributed, thus increasing write performance.

The host <NUM> may include a memory <NUM>. The file system <NUM> may divide the file data provided from the user application into data blocks and load the data blocks to the memory <NUM>. The file system <NUM> may generate a node block corresponding to each data block and load the generated node block to the memory <NUM>. The memory <NUM> may be a volatile memory device. For example, the memory <NUM> may include volatile memory such as DRAM, SDRAM, DDR SDRAM, LPDDR SDRAM, GRAM, etc..

When sudden power-off (SPO) occurs in which power supply to the host <NUM> is suddenly cut off, data loaded to the memory <NUM> may be destroyed/erased. To protect against SPO, the file system <NUM> may perform a checkpointing operation of storing the entire data (e.g., an NAT, a data block, and a node block) loaded to the memory <NUM> in the storage system <NUM>. The storage device <NUM> may continuously store data even when power supply is cut off. The checkpointing operation may be periodically or aperiodically performed. For example, the checkpointing operation may be performed every <NUM> seconds. However, the interval at which the checkpointing operation is performed is not limited thereto.

When power is supplied again to the host <NUM> after SPO, the file system <NUM> may perform a sudden power-off recovery (SPOR) operation. In SPOR, the file system <NUM> may load the merged block to the memory <NUM> and obtain a data block from the merged block. The file system <NUM> may obtain a node identifier and an offset from the merged block and generate a node block corresponding to the data block.

The file system <NUM> according to an embodiment of the inventive concept may asynchronously write the merged block and the node block to the storage device <NUM>. Thus, when SPO occurs after the merged block is written to the storage device <NUM>, the node block corresponding to the merged block may be destroyed/erased in the memory <NUM> without being written to the storage device <NUM>. Thus, the file system <NUM> may read the merged block written to the storage device <NUM> and generate the node block corresponding to the merged block by using the node identifier and the offset that are included in the merged block.

<FIG> is a block diagram of the host <NUM> of <FIG> according to an embodiment of the inventive concept.

Referring to <FIG>, the host <NUM> may include a user space <NUM> and a kernel space <NUM>.

Components shown in <FIG> may be software components, or hardware components such as, for example, a field-programmable gate array (FPGA) or an application-specific integrated circuit (ASIC). However, the components are not limited thereto. For example, in some embodiments, the components may be configured to exist in an addressable storage medium or may be configured to execute one or more processors. Functions provided in the components may be implemented by a further detailed component, or may be implemented as one component that performs a specific function by combining a plurality of components.

In an embodiment, the user space <NUM> is a region where a user application <NUM> is executed, and the kernel space <NUM> is a region that is restrictively reserved for kernel execution. For the user space <NUM> to access the kernel space <NUM>, a system call may be used.

The kernel space <NUM> may include a virtual file system <NUM>, the file system <NUM>, a device driver <NUM>, etc. According to embodiments, there may be one or more file systems <NUM>. In some embodiments, the file system <NUM> may be an F2FS.

In some embodiments, the file system <NUM> may divide a storage region of the storage device <NUM> into a plurality of blocks, a plurality of sections, and a plurality of zones, and write a log provided from the user application <NUM> to each block. Division of the storage region of the storage device <NUM> into a plurality of blocks, a plurality of sections, and a plurality of zones will be described in detail with reference to <FIG>.

The virtual file system <NUM> may allow one or more file systems <NUM> to operate with one another. The virtual file system <NUM> may enable use of a standardized system call to perform a read/write operation with respect to different file systems <NUM> of different media. Thus, for example, a system call such as open(), read(), and write() may be used regardless of a type of the file system <NUM>. That is, the virtual file system <NUM> may be an abstraction layer existing between the user space <NUM> and the file system <NUM>.

The device driver <NUM> may manage an interface between hardware and the user application <NUM> (or an operating system). The device driver <NUM> may be a program utilized for hardware to operate normally under a specific operating system.

<FIG> is a block diagram of the storage device <NUM> of <FIG> according to an embodiment of the inventive concept.

Referring to <FIG>, a storage region of the storage device <NUM> may be configured to include a block <NUM>, a segment <NUM>, a section <NUM>, and a zone <NUM>. The storage region of the storage device <NUM> may include a plurality of zones <NUM>. The zone <NUM> may include a plurality of sections <NUM>, the section <NUM> may include a plurality of segments <NUM>, and the segment <NUM> may include a plurality of blocks <NUM>. For example, the block <NUM> may be a storage region that stores <NUM> KB data, and the segment <NUM> may be a storage region that stores <NUM> MB data by including <NUM> blocks <NUM>. A configuration of the storage device <NUM> as shown in <FIG> may be determined at, but is not limited to, the time of formatting the storage device <NUM>. The file system <NUM> may read and write data in the unit of a <NUM> KB page. That is, the block <NUM> may store one page.

<FIG> is a view of a structure of a file stored in the storage device <NUM> of <FIG> according to an embodiment of the inventive concept.

The file stored in the storage device <NUM> may have an indexing structure. One file may include file data including content of a file to be stored by the user application <NUM> (of <FIG>) and node data including an attribute of the file, a location of a data block in which the file data is to be stored, etc..

Referring to <FIG>, data blocks <NUM> to <NUM> may be storage regions that store the file data, and node blocks <NUM> to <NUM> may be storage regions that store the node data.

The node blocks <NUM> to <NUM> may include an inode block <NUM>, direct node blocks <NUM>, <NUM>, and <NUM>, and indirect node blocks <NUM>, <NUM>, and <NUM>.

The inode block <NUM> may include at least one of a direct pointer directly pointing to the data block <NUM>, a single-indirect node pointer pointing to the direct node block <NUM>, a double-indirect node pointer pointing to the indirect node block <NUM>, or a triple-indirect node pointer pointing to the indirect node block <NUM>. An inode block may be provided for each file. Although each of the node blocks <NUM> to <NUM> is illustrated as indicating on data block, the embodiment is not limited thereto. Each of the node blocks <NUM> to <NUM> may indicate plurality of data blocks. In some embodiments, each of the plurality of data blocks may be identified based on an offset. The offset may be an index of each of the plurality of data blocks.

The indirect node blocks <NUM>, <NUM>, and <NUM> may include data pointers directly pointing to the data blocks <NUM>, <NUM>, and <NUM>.

The indirect node blocks <NUM>, <NUM>, and <NUM> may include first indirect node blocks <NUM> and <NUM> and a second indirect node block <NUM>. The first indirect node blocks <NUM> and <NUM> may include a first node pointer pointing to the direct node blocks <NUM> and <NUM>. The second indirect node block <NUM> may include a second node pointer pointing to the first indirect node block <NUM>.

<FIG> is a block diagram of the storage device of <FIG> according to an embodiment of the inventive concept. <FIG> is a diagram of an NAT according to an embodiment of the inventive concept.

Referring to <FIG>, a storage region of the storage device <NUM> may include a first region REGION <NUM> and a second region REGION <NUM>. In the file system <NUM>, the storage region of the storage device <NUM> may be divided into the first region REGION <NUM> and the second region REGION <NUM> in formatting, but embodiments of the inventive concept are not limited thereto.

In an embodiment, the first region REGION <NUM> is a region where various pieces of information managed by the entire system are stored, and may include, for example, the number of files allocated currently, the number of valid pages, a location, etc. In an embodiment, the second region REGION <NUM> is a storage region that stores various pieces of directory information, data, file information actually used by a user, etc..

The first region REGION <NUM> may include a first super block SB1 <NUM> and a second super block SB2 <NUM>, a checkpoint area (CP) <NUM>, a segment information table (SIT) <NUM>, an NAT <NUM>, a segment summary area (SSA) <NUM>, etc..

The first super block SB1 <NUM> and the second super block SB2 <NUM> may store default information of the file system <NUM>. For example, a size of the first super block SB1 <NUM>, the number of blocks <NUM>, a state plug (clean, stable, active, logging, unknown) of the file system <NUM>, etc., may be stored. As shown, the first super block <NUM> and the second super block <NUM> may be a total of two blocks, each of which stores the same content. Thus, even when a problem occurs in any one of the two super blocks, the other super block may be used.

The CP <NUM> may store a checkpoint. The checkpoint may be a logical breakpoint, and a state to the breakpoint may be fully preserved. When SPO occurs during an operation of the computing system <NUM>, the file system <NUM> may recover data by using the preserved checkpoint. The checkpoint may be periodically generated. However, generation of the checkpoint is not limited thereto.

The NAT <NUM> may include a plurality of node identifiers NODE IDs (NIDs) respectively corresponding to node blocks and a plurality of addresses respectively corresponding to the plurality of node identifiers, as shown in <FIG>. For example, a node block corresponding to a node identifier N1 may correspond to an address A1, a node block corresponding to a node identifier N2 may correspond to an address A2, and a node block corresponding to a node identifier N3 may correspond to an address A3.

All nodes (an inode, a direct node, an indirect node, etc.) may have their unique node identifiers. The NAT <NUM> may store a node identifier of an inode, a node identifier of a direct node, a node identifier of an indirect node, etc. The file system <NUM> may update an address corresponding to each node identifier.

The SIT <NUM> may include the number of valid pages of each segment and a bitmap of a plurality of pages. In the bitmap, whether each page is valid may be indicated by <NUM> or <NUM>. The SIT <NUM> may be used in a cleaning task (or garbage collection). For example, the bitmap may reduce an unnecessary read request when the cleaning task is performed, and the bitmap may be used when block allocation is performed in adaptive data logging.

In an embodiment, the SSA <NUM> is an area where summary information of each segment of the second region REGION <NUM> is gathered. For example, the SSA <NUM> may describe information of a node including a plurality of blocks of each segment of the second region REGION <NUM>. The SIT <NUM> may be used in the cleaning task (or garbage collection). For example, an upper-node block may have a node identifier list or address to identify a location of the data blocks <NUM> to <NUM> or a lower node block. In an embodiment, the upper node block is a node block that refers to a lower node block through a node pointer, and the lower node block is a node block referred to by the upper node block through the node pointer. The SSA <NUM> may provide an index that allows the data blocks <NUM> to <NUM> or the lower node block to identify a location of the upper node block. The SSA <NUM> may include a plurality of segment summary blocks. One segment summary block may have information about one segment located in the second region REGION <NUM>. The segment summary block may include a plurality of pieces of summary information, and one piece of summary information may correspond to one data block or one node block.

<FIG> is a diagram of a method of accessing a data block, according to an embodiment of the inventive concept. <FIG> will be described below with reference to <FIG>.

Referring to <FIG>, a data block <NUM> may include at least a part of file data. The data block <NUM> may be stored in an address A2. A node block <NUM> may store an address A2 indicating a storage location of the data block <NUM>, and may be stored in the address A1. The file system <NUM> may allocate the node identifier N1 to the node block <NUM>.

The file system <NUM> may refer to an NAT to access a data block corresponding to the node identifier N1. The file system <NUM> may obtain the address A1 from the NAT. The file system <NUM> may access the node block <NUM> by using the address A1. The file system <NUM> may obtain the address A2 from the node block <NUM>. The file system <NUM> may access the data block <NUM> by using the address A2.

In <FIG>, the node block <NUM> may correspond to the direct node blocks <NUM>, <NUM>, and <NUM> of <FIG>. However, embodiments of the inventive concept are not limited thereto. For example, in some embodiments, the file system <NUM> may access the data block <NUM> by using the indirect node blocks <NUM>, <NUM>, and <NUM> or the inode block <NUM>.

<FIG> is a diagram of a write operation according to an embodiment of the inventive concept. <FIG> will be described below with reference to <FIG>.

The file system <NUM> may provide data utilized by a user application using data loaded onto the memory <NUM> and update the data loaded onto the memory <NUM> based on file data provided by the user application. The memory <NUM> is volatile memory, such that the file system <NUM> may write data on the memory <NUM> to the storage system <NUM> including non-volatile memory to protect the data. The host <NUM> may write the data loaded onto the memory <NUM> to the storage system <NUM> through a plurality of operations S810 through S850.

In operation S810, the compression manager <NUM> included in the host <NUM> may generate a compressed block c_BLOCK by compressing a first data block DATA BLOCK <NUM>. A size of the first data block DATA BLOCK <NUM> may be L1. In some embodiments of the inventive concept, L1 may be <NUM> KB. A size of the compressed block c_BLOCK may be L2, which is smaller than L1. The compression manager <NUM> may compress the first data block DATA BLOCK <NUM> by using a compression algorithm such as, for example, a run-length encoding scheme, a Huffman coding scheme, an arithmetic coding scheme, an entropy coding scheme, a Markov chain scheme, a range coding scheme, or a differential pulse-code-modulation scheme.

In operation S820, the file system <NUM> may generate a merged block m_BLOCK by merging the compressed block c_BLOCK, the node identifier N1, and an offset ofs of the first data block DATA BLOCK <NUM>. A size of the merged block m_BLOCK may be L1. In some embodiments of the inventive concept, L1 may be <NUM> KB. That is, a sum of the size L2 of the compressed block c_BLOCK, the size L3 of the node identifier N1, and the size L4 of the offset ofs may be L1. The file system <NUM> may generate a node block <NUM> corresponding to the first data block DATA BLOCK <NUM>. The node block <NUM> may be a block including the node identifier N1 and the address A2. The address A2 may indicate a location where the merged block m_BLOCK is stored. The node block <NUM> may refer a plurality of data blocks including the first data block DATA BLOCK <NUM>. The node block <NUM> may identify the first data block DATA BLOCK <NUM> based on the offset ofs among the plurality of data blocks.

In operation S830, the file system <NUM> may write the merged block m_BLOCK to the storage system <NUM>. The merged block m_BLOCK may be written to a data log included in the storage device <NUM>. In the data log, a data block may be sequentially written. Thus, the merged block m_BLOCK may be sequentially written from a location next to a location where a second data block DATA BLOCK <NUM>, which is an existing data block, is stored. The first data block DATA BLOCK <NUM> and the second data block DATA BLOCK <NUM> may be data regarding the same file, in which the first data block DATA BLOCK <NUM> may be the latest data block and the second data block DATA BLOCK <NUM> may be an existing data block. In an embodiment, the data log means a storage region corresponding to a data segment of <FIG>. The first data block DATA BLOCK <NUM> may be a merged block.

In operation S840, the file system <NUM> may write a node block <NUM> corresponding to the merged block m_BLOCK to the storage system <NUM>. The node block <NUM> may be written to a node log included in the storage device <NUM>. In the node log, a node block may be sequentially written. Thus, the node block <NUM> may be sequentially written from a location next to a location where a second node block <NUM>, which is an existing node block, is stored. The second node block <NUM> may store an address A4 of the second data block DATA BLOCK <NUM> that is an existing data block. Operation S840 may be performed during an idle time when an interface between the host <NUM> and the storage system <NUM> is not occupied by data. That is, a time period in which the merged block m_BLOCK is written. A time period in which the node block <NUM> is written may be discontinuous. For example, a time in which the interface between the host <NUM> and the storage system <NUM> is occupied by the merged block m_BLOCK and a time in which the interface is occupied by the node block may be distributed, thus increasing write performance.

In operation S850, the file system <NUM> may perform an update operation on an NAT by performing a write operation of changing an address for the node identifier N1 into A1. Before the update operation is performed, the address A3 may correspond to the node identifier N1 on the NAT of the storage system <NUM>. After the update operation is performed, the address A1 may correspond to the node identifier N1.

After operation S850, even when SPO occurs, the file system <NUM> may read the address A1 corresponding to the node identifier N1 by referring to an NAT stored in the storage system <NUM>, access the node block <NUM> by using the address A1, and access the merged block m_BLOCK by using the address A2 stored in the node block <NUM>.

The file system <NUM> according to an embodiment of the inventive concept may access the merged block m_BLOCK, update the node block <NUM> indicating the merged block m_BLOCK, and update the NAT to indicate the node block <NUM>, even when SPO occurs after operation S830.

<FIG> is a diagram of an operating method of a computing system according to an embodiment of the inventive concept.

Referring to <FIG>, an operating method of a computing system may include a plurality of operations S910 to S960.

In operation S910, a user application may transmit a write request w_REQ to the file system <NUM>. The write request w_REQ may be a type of a system call. For example, the write request w_REQ may be write().

In operation S920, the file system <NUM> may generate a data block corresponding to the write request and transmit the data block to the compression manager <NUM>. The file system <NUM> may generate at least one node block corresponding to the data block. At least one node block may include at least one of an inode block, a direct block, or an indirect block. The data block and the node block may have a preset size L1 (e.g., <NUM> KB).

In operation S930, the compression manager <NUM> may generate the compressed block c_BLOCK. For example, the compression manager <NUM> may stop a compression operation according to whether the size of the data block is reduced by a reference size. The reference size may be determined based on a sum of a size of a node identifier and a size of an offset of the data block. In some embodiments of the inventive concept, the reference size may be determined based on the size of the node identifier, the size of the offset, and a size of a compression mark. In an embodiment, the compression mark means at least one bit indicating that the data block is compressed. In operation S930, when the size of the data block is not reduced by the reference size, the compression manager <NUM> may provide a compression failure signal to the file system <NUM>.

In operation S940, the compression manager <NUM> may provide the compressed block c_BLOCK to the file system <NUM>. The size of the compressed block c_BLOCK may be L2, which is smaller than L1.

In operation S950, the file system <NUM> may generate the merged block m_BLOCK. For example, the file system <NUM> may generate the merged block m_BLOCK by merging the compressed block c_BLOCK, an offset of the data block, and a node identifier. The size of the merged block m_BLOCK may be equal to a size of a data block. For example, the size of the merged block m_BLOCK may be <NUM> KB.

In operation S960, the file system <NUM> may transmit a write command w_CMD and the merged block m_BLOCK to the storage system <NUM>. When an idle time of the storage system <NUM> occurs after the file system <NUM> transmits the merged block m_BLOCK to the storage system <NUM>, the node block may be transmitted to the storage system <NUM>. That is, the storage system <NUM> may asynchronously write the merged block m_BLOCK and the node block. In operation S930, when the compressed block c_BLOCK is not generated, the file system <NUM> may transmit the write command w_CMD, the data block, and the node block to the storage system <NUM>. That is, the storage system <NUM> may synchronously write the data block and the node block.

<FIG> is a flowchart of an operating method of a host according to an embodiment of the inventive concept.

Referring to <FIG>, an operating method of a host may include a plurality of operations S1010 to S1060.

In operation S1010, the compression manager <NUM> may perform a compression operation on a first part of a data block. The first part may be a part having a preset size of the data block. A compression size may differ with a data state of a part having a preset size and a compression algorithm.

In operation S1020, the compression manager <NUM> may compare a compressed size with the reference size. In some embodiments of the inventive concept, the compression manager <NUM> may compare a size reduced by compression for the first part with the reference size. The reference size may correspond to a sum of the size of the node identifier and the size of an offset of the data block. In some embodiments of the inventive concept, the reference size may correspond to the size of the node identifier, the size of the offset, and the size of the merge mark. When the compressed size is less than the reference size, operation S1040 may be performed, and when the compressed size is equal to or greater than the reference size, operation S1030 may be performed.

In operation S1030, the file system <NUM> may generate a merged block and transmit the merged block to the storage system <NUM>. The file system <NUM> may transmit the merged block and a write command, together, to the storage system <NUM> to perform a write operation on the merged block. The file system <NUM> may provide, to the storage system <NUM>, a node block corresponding to the merged block in a time period that is different from a time period in which the merged block is transmitted, thereby increasing write performance.

In operation S1040, the compression manager <NUM> may determine whether maximal compression is performed on the data block. When maximal compression is performed, operation S1060 may be performed, and when maximal compression is not performed, operation S1050 may be performed.

In operation S1050, the compression manager <NUM> may compress a next part of the data block. The next part of the data block may have a size that is equal to or different from the size of the first part. After the next part is compressed, operation S1020 may be performed again. As the compression manager <NUM> compresses the data block in a stepwise manner, a compression time utilized for generating the merged block may be reduced.

In operation S1060, the file system <NUM> may transmit the data block and the node block to the storage system <NUM> such that the data block and the node block are written to the storage system <NUM> in a continuous time period.

<FIG> is a diagram of a SPOR operation according to an embodiment of the inventive concept.

Referring to <FIG>, after operation S830, SPO may occur. Thus, when the node block <NUM> is not written to the node log, data in the memory <NUM> may be destroyed/erased. That is, as shown in <FIG>, when the merged block m_BLOCK is written to the data log and the first node block <NUM> corresponding to the merged block m_BLOCK is not written, SPO may occur. Thus, the existing second node block <NUM> written to the node log may indicate the address A4 of the second data block DATA BLOCK <NUM> that is the existing data block, instead of the address A2 of the merged block m_BLOCK. The SPOR operation may include a plurality of operations S1110 to S1150.

In operation S1110, the file system <NUM> may load the NAT to the memory <NUM>. While it is illustrated in <FIG> that existing data is written to the NAT, embodiments of the inventive concept are not limited thereto. For example, in some embodiments, the NAT loaded to the memory <NUM> may store the address A3 corresponding to the node identifier N1 and store the address A2 corresponding to the node identifier N1.

In operation S1120, the file system <NUM> may load the merged block m_BLOCK written to the data log to the memory <NUM>. As blocks are sequentially written to the data log, the file system <NUM> may sequentially load the blocks to the memory <NUM> from the latest written blocks. It is illustrated in <FIG> that the merged block m_BLOCK is loaded, but the data block instead of the merged block may be loaded to the memory <NUM>. The file system <NUM> may load the second node block <NUM> written to the node log to the memory <NUM>.

In operation S1130, the file system <NUM> may search for the merged block m_BLOCK among loaded blocks. The file system <NUM> may search for the merged block m_BLOCK by identifying a merge mark e_m among the loaded blocks.

In operation S1140, the file system <NUM> may generate the first node block <NUM> by updating the second node block <NUM> such that the second node block <NUM> corresponds to the merged block m_BLOCK. For example, the file system <NUM> may update the second node block <NUM> based on the node identifier N1 and an offset ofs of the data block included in the merged block m_BLOCK. As a plurality of data blocks are sequentially written to the data log and sizes of the plurality of data blocks, the file system <NUM> may obtain an address of the merged block m_BLOCK. Further, the file system <NUM> may connect the first node block <NUM> to first data block DATA BLOCK <NUM> based on the offset ofs. Specifically, the file system <NUM> may set a data block corresponding to the offset ofs among a plurality of data blocks referred to the first node block <NUM> to the first data block DATA BLOCK <NUM>. Accordingly, as the second node block <NUM> may be updated to the first node block <NUM> based on the node identifier N1 and the offset ofs, the first node block <NUM> may be recovered even when operation S840 of <FIG> is not performed.

In operation S1150, the file system <NUM> may update the NAT. For example, the file system <NUM> may update the address corresponding to the node identifier N1 from A3 to A1.

<FIG> is a diagram of an operating method of a computing system that performs a recovery operation according to an embodiment of the inventive concept.

Referring to <FIG>, an operating method of a computing system may include a plurality of operations S1210 to S1240.

In operation S1210, the file system <NUM> may transmit a read command r_CMD to the storage system <NUM>. The file system <NUM> may transmit an address of a block recently written to the data log, together with the read command r_CMD, to the storage system <NUM>. The address of the recently written block may be obtained through a CP. The recently written block may be the most recently written bock (e.g., the latest written block).

In operation S1220, the storage system <NUM> may transmit the merged block m_BLOCK to the file system <NUM>. The storage system <NUM> may transmit the data block and the node block as well as the merged block m_BLOCK.

In operation S1230, the file system <NUM> may search for the merged block m_BLOCK among blocks received from the storage system <NUM> and transmit the compressed block c_BLOCK included in the found merged block m_BLOCK to the compression manager <NUM>.

In operation S1240, the compression manager <NUM> may generate a data block by performing decompression on the compressed block c_BLOCK, and transmit the data block to the file system <NUM>. The data block may be stored in the memory <NUM>.

In operation S1250, the file system <NUM> may generate a node block corresponding to the data block based on the node identifier and the address included in the merged block m_BLOCK. The node block may be stored in the memory <NUM>.

<FIG> is a diagram of a computing system <NUM> to which a storage device is applied according to an embodiment of the inventive concept. The system <NUM> of <FIG> may be, for example, a mobile system, such as a portable communication terminal (e.g., a mobile phone), a smartphone, a tablet personal computer (PC), a wearable device, a healthcare device, or an Internet of things (IOT) device. However, the system <NUM> of <FIG> is not necessarily limited to such a mobile system, and may be, for example, a PC, a laptop computer, a server, a media player, or an automotive device (e.g., a navigation device). The system <NUM> may include the computing system <NUM> of <FIG>.

Referring to <FIG>, the computing system <NUM> may include a main processor <NUM>, memories (e.g., 1200a and 1200b), and storage systems (e.g., 1300a and 1300b). In addition, the computing system <NUM> may include at least one of an image capturing device <NUM>, a user input device <NUM>, a sensor <NUM>, a communication device <NUM>, a display <NUM>, a speaker <NUM>, a power supplying device <NUM>, and a connecting interface <NUM>.

The main processor <NUM> may control all operations of the computing system <NUM>, including, for example, operations of components included in the computing system <NUM>. The main processor <NUM> may be implemented as, for example, a general-purpose processor, a dedicated processor, or an application processor.

The main processor <NUM> may include at least one CPU core <NUM>, and may further include a controller <NUM> configured to control the memories 1200a and 1200b and/or the storage systems 1300a and 1300b. In some embodiments, the main processor <NUM> may further include an accelerator <NUM>, which is a dedicated circuit for a high-speed data operation, such as an artificial intelligence (AI) data operation. The accelerator <NUM> may include, for example, a graphics processing unit (GPU), a neural processing unit (NPU) and/or a data processing unit (DPU), and be implemented as a chip that is physically separate from the other components of the main processor <NUM>.

The memories 1200a and 1200b may be used as main memory devices of the computing system <NUM>. Although each of the memories 1200a and 1200b may include a volatile memory, such as, for example, static random access memory (SRAM) and/or dynamic RAM (DRAM), in some embodiments, each of the memories 1200a and 1200b may include a non-volatile memory, such as, for example, a flash memory, phase-change RAM (PRAM) and/or resistive RAM (RRAM). The memories 1200a and 1200b may be implemented in the same package as the main processor <NUM>. The host <NUM> of <FIG> may be implemented by the main processor <NUM> and the memories 1200a and 1200b of <FIG>.

The storage systems 1300a and 1300b may serve as non-volatile storage devices configured to store data regardless of whether power is supplied thereto, and have larger storage capacity than the memories 1200a and 1200b. The storage systems 1300a and 1300b may respectively include storage controllers 1310a and 1310b and NVMs 1320a and 1320b configured to store data via the control of the storage controllers 1310a and 1310b. Although the NVMs 1320a and 1320b may include flash memories having a two-dimensional (2D) structure or a three-dimensional (3D) V-NAND structure, in some embodiments, the NVMs 1320a and 1320b may include other types of NVMs, such as, for example, PRAM and/or RRAM.

The storage systems 1300a and 1300b may be physically separated from the main processor <NUM> and included in the computing system <NUM>, or implemented in the same package as the main processor <NUM>. The storage systems 1300a and 1300b may be solid-state devices (SSDs) or memory cards and be removably combined with other components of the system <NUM> through an interface, such as the connecting interface <NUM> that will be described further below. The storage systems 1300a and 1300b may be devices to which a standard protocol, such as, for example, universal flash storage (UFS), embedded multi-media card (eMMC), or non-volatile memory express (NVMe), is applied, without being limited thereto. The storage system <NUM> of <FIG> may be included in at least one of the storage systems 1300a and 1300b.

The image capturing device <NUM> may capture still images or moving images. The image capturing device <NUM> may include, for example, a camera, a camcorder, and/or a webcam.

The user input device <NUM> may receive various types of data input by a user of the system <NUM> and include, for example, a touch pad, a keypad, a keyboard, a mouse, and/or a microphone.

The sensor <NUM> may detect various types of physical quantities, which may be obtained from outside of the computing system <NUM>, and convert the detected physical quantities into electric signals. The sensor <NUM> may include, for example, a temperature sensor, a pressure sensor, an illuminance sensor, a position sensor, an acceleration sensor, a biosensor, and/or a gyroscope sensor.

The communication device <NUM> may transmit and receive signals between other devices outside the system <NUM> according to various communication protocols. The communication device <NUM> may include, for example, an antenna, a transceiver, and/or a modem.

The power supplying device <NUM> may appropriately convert power supplied from a battery embedded in the computing system <NUM> and/or an external power source, and supply the converted power to each of components of the computing system <NUM>.

The connecting interface <NUM> may provide a connection between the computing system <NUM> and an external device, which is connected to the computing system <NUM> and capable of transmitting and receiving data to and from the computing system <NUM>. The connecting interface <NUM> may be implemented by using various interface schemes, such as, for example, advanced technology attachment (ATA), serial ATA (SATA), external SATA (e-SATA), small computer small interface (SCSI), serial attached SCSI (SAS), peripheral component interconnection (PCI), PCI express (PCIe), NVMe, IEEE <NUM>, a universal serial bus (USB) interface, a secure digital (SD) card interface, a multi-media card (MMC) interface, an eMMC interface, a UFS interface, an embedded UFS (eUFS) interface, and a compact flash (CF) card interface.

<FIG> is a block diagram of a computing system <NUM> according to an embodiment of the inventive concept.

The computing system <NUM> may include a host <NUM> and a storage system <NUM>. The storage system <NUM> may include a storage controller <NUM> and an NVM <NUM>. According to an embodiment, the host <NUM> may include a host controller <NUM> and a host memory <NUM>. The host memory <NUM> may serve as a buffer memory configured to temporarily store data to be transmitted to the storage system <NUM> or data received from the storage system <NUM>. The host <NUM> is an example of the host <NUM> of <FIG>.

The storage system <NUM> may include storage media configured to store data in response to requests from the host <NUM>. As an example, the storage system <NUM> may include at least one of an SSD, an embedded memory, and a removable external memory. When the storage system <NUM> is an SSD, the storage system <NUM> may be a device that conforms to an NVMe standard. When the storage system <NUM> is an embedded memory or an external memory, the storage system <NUM> may be a device that conforms to a UFS standard or an eMMC standard. Each of the host <NUM> and the storage system <NUM> may generate a packet according to an adopted standard protocol and transmit the packet.

When the NVM <NUM> of the storage system <NUM> includes a flash memory, the flash memory may include a 2D NAND memory array or a 3D (or vertical) NAND (VNAND) memory array. As another example, the storage system <NUM> may include various other kinds of NVMs. For example, the storage system <NUM> may include magnetic RAM (MRAM), spin-transfer torque MRAM, conductive bridging RAM (CBRAM), ferroelectric RAM (FRAM), PRAM, RRAM, and various other kinds of memories.

According to an embodiment, the host controller <NUM> and the host memory <NUM> may be implemented as separate semiconductor chips. Alternatively, in some embodiments, the host controller <NUM> and the host memory <NUM> may be integrated in the same semiconductor chip. As an example, the host controller <NUM> may be any one of a plurality of modules included in an application processor (AP). The AP may be implemented as a system-on-chip (SoC). Further, the host memory <NUM> may be an embedded memory included in the AP or an NVM or memory module located outside the AP.

The host controller <NUM> may manage an operation of storing data (e.g., write data) of a buffer region of the host memory <NUM> in the NVM <NUM> or an operation of storing data (e.g., read data) of the NVM <NUM> in the buffer region.

The storage controller <NUM> may include a host interface <NUM>, a memory interface <NUM>, and a CPU <NUM>. The storage controller <NUM> may further include a flash translation layer (FTL) <NUM>, a packet manager <NUM>, a buffer memory <NUM>, an error correction code (ECC) engine <NUM>, and an advanced encryption standard (AES) engine <NUM>. The storage controller <NUM> may further include a working memory in which the FTL <NUM> is loaded. The CPU <NUM> may execute the FTL <NUM> to control data write and read operations on the NVM <NUM>.

The host interface <NUM> may transmit and receive packets to and from the host <NUM>. A packet transmitted from the host <NUM> to the host interface <NUM> may include a command or data to be written to the NVM <NUM>. A packet transmitted from the host interface <NUM> to the host <NUM> may include a response to the command or data read from the NVM <NUM>. The memory interface <NUM> may transmit data to be written to the NVM <NUM> to the NVM2 <NUM> or receive data read from the NVM <NUM>. The memory interface <NUM> may be configured to comply with a standard protocol, such as, for example, Toggle or open NAND flash interface (ONFI).

The FTL <NUM> may perform various functions, such as, for example, an address mapping operation, a wear-leveling operation, and a garbage collection operation. The address mapping operation may be an operation of converting a logical address received from the host <NUM> into a physical address used to actually store data in the NVM2 <NUM>. The wear-leveling operation may be a technique that prevents or reduces excessive deterioration of a specific block by allowing blocks of the NVM <NUM> to be uniformly used. As an example, the wear-leveling operation may be implemented using a firmware technique that balances erase counts of physical blocks. The garbage collection operation may be a technique for obtaining usable capacity in the NVM <NUM> by erasing an existing block after copying valid data of the existing block to a new block.

The packet manager <NUM> may generate a packet according to a protocol of an interface, which consents to the host <NUM>, or parse various types of information from the packet received from the host <NUM>. In addition, the buffer memory <NUM> may temporarily store data to be written to the NVM <NUM> or data to be read from the NVM <NUM>. Although the buffer memory <NUM> is a component included in the storage controller <NUM> in <FIG>, in some embodiments, the buffer memory <NUM> may be disposed outside of the storage controller <NUM>.

The ECC engine <NUM> may perform error detection and correction operations on read data read from the NVM <NUM>. For example, the ECC engine <NUM> may generate parity bits for write data to be written to the NVM2 <NUM>, and the generated parity bits may be stored in the NVM <NUM> together with write data. During the reading of data from the NVM <NUM>, the ECC engine <NUM> may correct an error in the read data by using the parity bits read from the NVM <NUM> along with the read data, and output error-corrected read data.

The AES engine <NUM> may perform at least one of an encryption operation and a decryption operation on data input to the storage controller <NUM> by using a symmetric-key algorithm.

<FIG> is a diagram of a UFS system <NUM> according to an embodiment of the inventive concept. The UFS system <NUM> may be a system conforming to a UFS standard according to Joint Electron Device Engineering Council (JEDEC) and includes a UFS host <NUM>, a UFS device <NUM>, and a UFS interface <NUM>. Aspects of the above description of the computing system <NUM> of <FIG> may also be applied to the UFS system <NUM> of <FIG>, unless the context indicates otherwise. The host <NUM> may include at least some element(s) of the host <NUM> of <FIG> and the UFS device <NUM> may include at least some element(s) of the storage system <NUM> of <FIG>.

Referring to <FIG>, the UFS host <NUM> may be connected to the UFS device <NUM> through the UFS interface <NUM>.

The UFS host <NUM> may include a UFS host controller <NUM>, an application <NUM>, a UFS driver <NUM>, a host memory <NUM>, and a UFS interconnect (UIC) layer <NUM>. The UFS device <NUM> may include the UFS device controller <NUM>, the NVM <NUM>, a storage interface <NUM>, a device memory <NUM>, a UIC layer <NUM>, and a regulator <NUM>. The NVM <NUM> may include a plurality of memory units <NUM>. Although each of the memory units <NUM> may include a V-NAND flash memory having a 2D structure or a 3D structure, in some embodiments, each of the memory units <NUM> may include another kind of NVM, such as, for example, PRAM and/or RRAM. The UFS device controller <NUM> may be connected to the NVM <NUM> through the storage interface <NUM>. The storage interface <NUM> may be configured to comply with a standard protocol, such as, for example, Toggle or ONFI.

The application <NUM> may refer to a program that communicates with the UFS device <NUM> to use functions of the UFS device <NUM>. The application <NUM> may transmit input-output requests (IORs) to the UFS driver <NUM> for input/output (I/O) operations on the UFS device <NUM>. The IORs may refer to, for example, a data read request, a data storage (or write) request, and/or a data erase (or discard) request, without being limited thereto.

The UFS driver <NUM> may manage the UFS host controller <NUM> through a UFS-host controller interface (UFS-HCI). The UFS driver <NUM> may convert the IOR generated by the application <NUM> into a UFS command defined by the UFS standard and transmit the UFS command to the UFS host controller <NUM>. One IOR may be converted into a plurality of UFS commands. Although the UFS command may be defined by an SCSI standard, the UFS command may be a command dedicated to the UFS standard.

The UFS host controller <NUM> may transmit the UFS command converted by the UFS driver <NUM> to the UIC layer <NUM> of the UFS device <NUM> through the UIC layer <NUM> and the UFS interface <NUM>. During the transmission of the UFS command, a UFS host register <NUM> of the UFS host controller <NUM> may serve as a command queue (CQ).

The UIC layer <NUM> on the side of the UFS host <NUM> may include a mobile industry processor interface (MIPI) M-PHY <NUM> and an MIPI UniPro <NUM>, and the UIC layer <NUM> on the side of the UFS device <NUM> may also include an MIPI M-PHY <NUM> and an MIPI UniPro <NUM>.

The UFS interface <NUM> may include a line configured to transmit a reference clock signal REF_CLK, a line configured to transmit a hardware reset signal RESET_n for the UFS device <NUM>, a pair of lines configured to transmit a pair of differential input signals DIN_T and DIN_C, and a pair of lines configured to transmit a pair of differential output signals DOUT_T and DOUT_C.

In some embodiments, a frequency of a reference clock signal REF_CLK provided from the UFS host <NUM> to the UFS device <NUM> may be one of about <NUM>, about <NUM>, about <NUM>, and about <NUM>, without being limited thereto. The UFS host <NUM> may change the frequency of the reference clock signal REF_CLK during an operation, that is, during data transmission/receiving operations between the UFS host <NUM> and the UFS device <NUM>. The UFS device <NUM> may generate clock signals having various frequencies from the reference clock signal REF_CLK provided from the UFS host <NUM> by using a phase-locked loop (PLL). Also, the UFS host <NUM> may set a data rate between the UFS host <NUM> and the UFS device <NUM> by using the frequency of the reference clock signal REF_CLK. That is, the data rate may be determined depending on the frequency of the reference clock signal REF_CLK.

The UFS interface <NUM> may support a plurality of lanes, each of which may be implemented as a pair of differential lines. For example, the UFS interface <NUM> may include at least one receiving lane and at least one transmission lane. In <FIG>, a pair of lines configured to transmit a pair of differential input signals DIN_T and DIN_C may constitute a receiving lane, and a pair of lines configured to transmit a pair of differential output signals DOUT_T and DOUT_C may constitute a transmission lane. Although one transmission lane and one receiving lane are illustrated in <FIG>, the number of transmission lanes and the number of receiving lanes are not limited thereto.

The receiving lane and the transmission lane may transmit data based on a serial communication scheme. Full-duplex communications between the UFS host <NUM> and the UFS device <NUM> may be enabled due to a structure in which the receiving lane is separated from the transmission lane. That is, while receiving data from the UFS host <NUM> through the receiving lane, the UFS device <NUM> may transmit data to the UFS host <NUM> through the transmission lane. In addition, control data (e.g., a command) from the UFS host <NUM> to the UFS device <NUM> and user data to be stored in or read from the NVM <NUM> of the UFS device <NUM> by the UFS host <NUM> may be transmitted through the same lane. Accordingly, between the UFS host <NUM> and the UFS device <NUM>, in some embodiments, a separate lane for data transmission is not utilized in addition to a pair of receiving lanes and a pair of transmission lanes.

The UFS device controller <NUM> of the UFS device <NUM> may control all operations of the UFS device <NUM>. The UFS device controller <NUM> may manage the NVM <NUM> by using a logical unit (LU) <NUM>, which is a logical data storage unit. The number of LUs <NUM> may be <NUM>, without being limited thereto. In some embodiments, the data log and the node log described above with reference to <FIG> and <FIG> may include at least one of the logic units (LU) <NUM>. For example, a first logic unit (LU) may be included in the data log and a second logic unit (LU) may be included in the node log. The logic unit (LU) <NUM> may be referred as a storage region. The UFS device controller <NUM> may include an FTL and convert a logical data address (e.g., a logical block address (LBA)) received from the UFS host <NUM> into a physical data address (e.g., a physical block address (PBA)) by using address mapping information of the FTL. A logical block configured to store user data in the UFS system <NUM> may have a size in a predetermined range. For example, a minimum size of the logical block may be set to <NUM> Kbyte.

When a command from the UFS host <NUM> is applied through the UIC layer <NUM> to the UFS device <NUM>, the UFS device controller <NUM> may perform an operation in response to the command and transmit a completion response to the UFS host <NUM> when the operation is completed.

As an example, when the UFS host <NUM> intends to store user data in the UFS device <NUM>, the UFS host <NUM> may transmit a data storage command to the UFS device <NUM>. When a response (a 'ready-to-transfer' response) indicating that the UFS host <NUM> is ready to receive user data (ready-to-transfer) is received from the UFS device <NUM>, the UFS host <NUM> may transmit user data to the UFS device <NUM>. The UFS device controller <NUM> may temporarily store the received user data in the device memory <NUM> and store the user data, which is temporarily stored in the device memory <NUM>, at a selected position of the NVM <NUM> based on the address mapping information of the FTL.

As another example, when the UFS host <NUM> intends to read the user data stored in the UFS device <NUM>, the UFS host <NUM> may transmit a data read command to the UFS device <NUM>. The UFS device controller <NUM>, which has received the command, may read the user data from the NVM <NUM> based on the data read command and temporarily store the read user data in the device memory <NUM>. During the read operation, the UFS device controller <NUM> may detect and correct an error in the read user data by using an ECC engine embedded therein. For example, the ECC engine may generate parity bits for write data to be written to the NVM <NUM>, and the generated parity bits may be stored in the NVM <NUM> along with the write data. During the reading of data from the NVM <NUM>, the ECC engine may correct an error in read data by using the parity bits read from the NVM <NUM> along with the read data, and output error-corrected read data.

In addition, the UFS device controller <NUM> may transmit user data, which is temporarily stored in the device memory <NUM>, to the UFS host <NUM>. In addition, the UFS device controller <NUM> may further include an AES engine. The AES engine may perform at least one of an encryption operation and a decryption operation on data transmitted to the UFS device controller <NUM> by using a symmetric-key algorithm.

The UFS host <NUM> may sequentially store commands, which are to be transmitted to the UFS device <NUM>, in the UFS host register <NUM>, which may serve as a common queue, and sequentially transmit the commands to the UFS device <NUM>. In this case, even while a previously transmitted command is still being processed by the UFS device <NUM>, that is, even before receiving a notification that the previously transmitted command has been processed by the UFS device <NUM>, the UFS host <NUM> may transmit a next command, which is on standby in the CQ, to the UFS device <NUM>. Thus, the UFS device <NUM> may also receive a next command from the UFS host <NUM> during the processing of the previously transmitted command. A maximum number (or queue depth) of commands that may be stored in the CQ may be, for example, <NUM>. Also, the CQ may be implemented as a circular queue in which a start and an end of a command line stored in a queue are indicated by a head pointer and a tail pointer.

Each of the plurality of memory units <NUM> may include a memory cell array and a control circuit configured to control an operation of the memory cell array. The memory cell array may include a 2D memory cell array or a 3D memory cell array. The memory cell array may include a plurality of memory cells. Although each of the memory cells is a single-level cell (SLC) configured to store <NUM>-bit information in some embodiments, in other embodiments, each of the memory cells may be a cell configured to store information of <NUM> bits or more, such as, for example, a multi-level cell (MLC), a triple-level cell (TLC), and a quadruple-level cell (QLC). The 3D memory cell array may include a vertical NAND string in which at least one memory cell is vertically oriented and located on another memory cell.

Voltages VCC, VCCQ1, and VCCQ2 may be applied as power supply voltages to the UFS device <NUM>. The voltage VCC may be a main power supply voltage for the UFS device <NUM> and be in a range of about <NUM> V to about <NUM> V. The voltage VCCQ1 may be a power supply voltage for supplying a low voltage mainly to the UFS device controller <NUM> and be in a range of about <NUM> V to about <NUM> V. The voltage VCCQ2 may be a power supply voltage for supplying a voltage, which is lower than the voltage VCC and higher than the voltage VCCQ1, primarily to an I/O interface, such as the MIPI M-PHY <NUM>, and be in a range of about <NUM> V to about <NUM> V. The power supply voltages may be supplied through the regulator <NUM> to respective components of the UFS device <NUM>. The regulator <NUM> may be implemented as a set of unit regulators respectively connected to different ones of the power supply voltages described above.

As is traditional in the field of the present inventive concept, embodiments are described, and illustrated in the drawings, in terms of functional blocks, units and/or modules. Those skilled in the art will appreciate that these blocks, units and/or modules are physically implemented by electronic (or optical) circuits such as logic circuits, discrete components, microprocessors, hardwired circuits, memory elements, wiring connections, etc., which may be formed using semiconductor-based fabrication techniques or other manufacturing technologies. In the case of the blocks, units and/or modules being implemented by microprocessors or similar, they may be programmed using software (e.g., microcode) to perform various functions discussed herein and may optionally be driven by firmware and/or software. Alternatively, each block, unit and/or module may be implemented by dedicated hardware, or as a combination of dedicated hardware to perform some functions and a processor (e.g., one or more programmed microprocessors and associated circuitry) to perform other functions.

In embodiments of the present inventive concept, a three dimensional (3D) memory array is provided. The 3D memory array is monolithically formed in one or more physical levels of arrays of memory cells having an active area disposed above a silicon substrate and circuitry associated with the operation of those memory cells, whether such associated circuitry is above or within such substrate. The term "monolithic" means that layers of each level of the array are directly deposited on the layers of each underlying level of the array. In embodiments of the present inventive concept, the 3D memory array includes vertical NAND strings that are vertically oriented such that at least one memory cell is located over another memory cell. The at least one memory cell may include a charge trap layer. The following patent documents, which are hereby incorporated by reference, describe suitable configurations for three-dimensional memory arrays, in which the three-dimensional memory array is configured as a plurality of levels, with word lines and/or bit lines shared between levels: <CIT>; <CIT>; <CIT>; <CIT>; and <CIT>.

Claim 1:
A computing system, comprising:
a storage system (<NUM>; 1300a, 1300b; <NUM>) configured to store data; and
a host (<NUM>; <NUM>; <NUM>) configured to compress (S810; S930) a data block (DATA BLOCK <NUM>) of a preset size (L1) loaded to a memory (<NUM>; 1200a, 1200b; <NUM>; <NUM>), generate (S820; S950) a merged block (m_Block) of the preset size (L1) by merging a compressed block (c_BLOCK) corresponding to the data block (DATA BLOCK <NUM>), an identifier (N1) of a node block (<NUM>) referring the data block (DATA BLOCK <NUM>), and an offset (ofs) indicating an index of the data block (DATA BLOCK <NUM>) among at least one data block referred by the node block (<NUM>), and provide (S830) the merged block (m_Block) to the storage system (<NUM>; 1300a, 1300b; <NUM>).