KR20240121657A - A storage device and an operatiing method of a storage controller - Google Patents

Abstract

A storage device and an operating method of a storage controller are provided. The storage device includes a nonvolatile memory device configured with a plurality of physical blocks, each of which includes a plurality of sub-blocks, and a free block list and a victim selectable block list for the plurality of physical blocks, and a storage controller for controlling operation of the nonvolatile memory device, wherein, when there are insufficient free blocks for storing data according to a write request received from a host, the storage controller checks for a full reusable physical block in the free block list and selects a head of the checked block, and when there is no full reusable physical block, performs garbage collection based on the victim selectable block list and transmits an address of a physical block on which the garbage collection was performed to the nonvolatile memory device together with the write request.

Description

{A STORAGE DEVICE AND AN OPERATIING METHOD OF A STORAGE CONTROLLER}

The present invention relates to a storage device including a nonvolatile memory device.

As electronic devices become faster and less power-consuming, memory devices embedded in them also require fast read/write operations and low operating voltages. Random Access Memory (RAM) can be volatile or nonvolatile. Volatile RAM loses information stored in volatile random access memory whenever power is removed, while nonvolatile random access memory can retain memory contents of nonvolatile random access memory even when power is removed from the memory.

The problem to be solved by the present invention is to provide a storage device with improved storage space efficiency in a nonvolatile memory device including sub-blocks in a multi-stack structure.

The problem to be solved by the present invention is to provide an operating method of a storage controller that can more efficiently utilize the space of a nonvolatile memory device while freely performing an erase operation for a sub-block during a write operation for a nonvolatile memory device including a sub-block.

The problems to be solved by the present invention are not limited to the problems mentioned above, and other problems not mentioned will be clearly understood by those skilled in the art from the description below.

According to some embodiments of the present invention for solving the above problem, a storage device includes a nonvolatile memory device comprising a plurality of physical blocks, each of which includes a plurality of sub-blocks, and a free block list and a victim selectable block list for the plurality of physical blocks, and a storage controller for controlling operation of the nonvolatile memory device, wherein, when there are insufficient free blocks for storing data according to a write request received from a host, the storage controller checks for all reusable physical blocks in the free block list and selects a head of the checked block, and when there are no all reusable physical blocks, performs garbage collection based on the victim selectable block list and transmits an address of a physical block on which the garbage collection was performed to the nonvolatile memory device together with the write request.

According to some embodiments of the present invention for solving the above problem, a storage device includes a nonvolatile memory device including a plurality of physical blocks divided into a plurality of sub-blocks in a multi-stack structure, a storage controller for controlling operation of the nonvolatile memory device, and the storage controller includes a write module for requesting an address of a free block according to the write request when a write request from a host is received, a garbage collector for requesting an address of a victim block for performing garbage collection, and a block management unit for storing a free block list and a victim selectable block list, and selecting and returning a physical block corresponding to a request of the write module or a request of the garbage collector from the free block list or the victim selectable block list.

According to some embodiments of the present invention for solving the above problem, a method of operating a storage controller includes the steps of: receiving a write request from a host; checking whether there is a first physical block in a free block list corresponding to the write request that is entirely reusable and capable of storing the write-requested data; if there is a first physical block in a free block list that is entirely reusable, selecting a first head of a group to which the first physical block belongs and returning a free block address including the first head to a nonvolatile memory device; if there is no first physical block, selecting a second head including at least one valid sub-block from the free block list, and returning an address of the physical block to which the second head belongs if the physical block to which the second head belongs is sufficient to store the write-requested data; and transmitting the address of the returned physical block to the nonvolatile memory device together with the write request.

FIG. 1 is a block diagram illustrating a host-storage system according to an exemplary embodiment of the present invention.
Figure 2 is an exemplary block diagram illustrating a memory device.
FIG. 3 is a drawing specifically illustrating an FTL module (400) according to some embodiments.
FIG. 4 is a diagram illustrating one physical block (500) according to some embodiments.
FIG. 5 is a schematic diagram illustrating one physical block to illustrate data access operations according to some embodiments.
FIG. 6 is a conceptual diagram illustrating a free block list according to some embodiments.
FIG. 7 is a conceptual diagram illustrating a big team selectable block list according to some embodiments.
Figure 8 is a conceptual diagram illustrating a block list stored in an FTL module according to some embodiments.
FIG. 9 is a diagram illustrating light operation of a storage device according to some embodiments.
FIGS. 11 to 13 are flowcharts illustrating a method of operating a storage device according to some embodiments.
FIG. 14 is a diagram illustrating a system to which a storage device according to one embodiment of the present invention is applied.

Hereinafter, storage devices according to some embodiments of the present invention will be described with reference to FIGS. 1 to 14.

FIG. 1 is a block diagram illustrating a host-storage system according to an exemplary embodiment of the present invention.

The host-storage system (10) may include a host (100) and a storage device (200). In addition, the storage device (200) may include a storage controller (210) and a non-volatile memory device (NVM, 220). In addition, according to an exemplary embodiment of the present invention, the host (100) may include a host controller (110) and a host memory (120). The host memory (120) may function as a buffer memory for temporarily storing data to be transmitted to the storage device (200) or data transmitted from the storage device (200).

The storage device (200) may include storage media for storing data according to a request from the host (100). As an example, the storage device (200) may include at least one of a solid state drive (SSD), an embedded memory, and a removable external memory. If the storage device (200) is an SSD, the storage device (200) may be a device following the NVMe (non-volatile memory express) standard. If the storage device (200) is an embedded memory or an external memory, the storage device (200) may be a device following the UFS (universal flash storage) or eMMC (embedded multi-media card) standard. The host (100) and the storage device (200) may each generate a packet according to an adopted standard protocol and transmit the packet.

When the nonvolatile memory device (220) of the storage device (200) 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 device (200) may include various other types of nonvolatile memory devices. For example, the storage device (200) may apply MRAM (Magnetic RAM), Spin-Transfer Torgue MRAM, Conductive bridging RAM (CBRAM), FeRAM (Ferroelectric RAM), PRAM (Phase RAM), Resistive RAM, and various other types of memory.

The storage device (200) may be manufactured in the form of any one of various types of packages, such as, for example, a PoP (Package on Package), a SIP (System in Package), a SoC (System on Chip), an MCP (Multi Chip Package), a CoB (Chip on Board), a WFP (Wafer-level Fabricated Package), a WSP (Wafer-level Stack Package), etc.

According to one embodiment, the host controller (110) and the host memory (120) may be implemented as separate semiconductor chips. Alternatively, in some embodiments, the host controller (110) and the host memory (120) may be integrated into the same semiconductor chip. As an example, the host controller (110) may be one of a plurality of modules provided in an application processor, and the application processor may be implemented as a system on chip (SoC). In addition, the host memory (120) may be an embedded memory provided in the application processor, or a nonvolatile memory or memory module disposed outside the application processor.

The host controller (110) can manage an operation of storing data (e.g., write data) of the host memory (120) in a nonvolatile memory device (220), or storing data (e.g., read data) of the nonvolatile memory device (220) in the host memory (120).

The storage controller (210) may include a host interface (211), a memory interface (212), and a central processing unit (CPU, 213). In addition, the storage controller (210) may further include a flash translation layer module (Flash Translation Layer (hereinafter referred to as FTL module), 214), a packet manager (215), a buffer memory (216), an ECC module (error correction code, 217) engine, and an AES (advanced encryption standard, 218) engine. The storage controller (210) may further include a working memory (not shown) into which a flash translation layer (FTL, 214) is loaded, and data write and read operations for a non-volatile memory may be controlled by the CPU (211) executing the flash translation layer.

The host interface (211) is connected to the host (100) and can transmit and receive packets. A packet transmitted from the host (100) to the host interface (211) may include a command or data to be written to a nonvolatile memory device (220), and a packet transmitted from the host interface (211) to the host (100) may include a response to the command or data read from the nonvolatile memory device (220). A memory interface (212) may transmit data to be written to the nonvolatile memory device (220) from the storage controller (210) to the nonvolatile memory device (220), or receive data read from the nonvolatile memory device (220). This memory interface (212) may be implemented to comply with a standard protocol such as Toggle or ONFI.

The FTL module (214) can perform various functions such as address mapping, wear-leveling, and garbage collection. The address mapping operation is an operation to change a logical address received from a host into a physical address used to actually store data in the nonvolatile memory device (220). Wear-leveling is a technology to prevent excessive deterioration of a specific block by ensuring that blocks in the nonvolatile memory device (220) are used uniformly, and can be implemented through a firmware technology that balances the erase counts of physical blocks, for example. Garbage collection is a technology to secure available capacity in the nonvolatile memory device (220) by copying valid data of a sub-block to a new sub-block and then erasing the existing sub-block.

The packet manager (215) can generate a packet according to the protocol of the interface agreed upon with the host (100), or parse various pieces of information from a packet received from the host (100). In addition, the buffer memory (216) can temporarily store data to be written to the nonvolatile memory device (220) or data to be read from the nonvolatile memory device (220). The buffer memory (216) may be a configuration provided within the storage controller (210), but may also be placed outside the storage controller (210).

The ECC engine (217) can perform an error detection and correction function for read data read from a nonvolatile memory device (220). More specifically, the ECC engine (217) can generate parity bits for write data to be written to the nonvolatile memory device (220), and the parity bits generated in this way can be stored in the nonvolatile memory device (220) together with the write data. When reading data from the nonvolatile memory device (220), the ECC engine (217) can correct an error in the read data by using the parity bits read from the nonvolatile memory device (220) together with the read data, and output the read data with the error corrected.

The AES engine (218) can perform at least one of an encryption operation and a decryption operation on data input to the storage controller (210) using a symmetric key algorithm.

Figure 2 is an exemplary block diagram illustrating a memory device.

Referring to FIG. 2, the memory device (300) may include a control logic circuit (320), a memory cell array (330), a page buffer unit (340), a voltage generator (350), and a row decoder (360). Although not shown in FIG. 2, the memory device (300) may further include a memory interface circuit (212, 310) shown in FIG. 1, and may also further include column logic, a pre-decoder, a temperature sensor, a command decoder, an address decoder, etc.

The control logic circuit (320) can control various operations within the memory device (300) in general. The control logic circuit (320) can output various control signals in response to a command (CMD) and/or an address (ADDR) from the memory interface circuit (310). For example, the control logic circuit (320) can output a voltage control signal (CTRL_vol), a row address (X-ADDR), and a column address (Y-ADDR).

The memory cell array (330) may include a plurality of memory blocks (BLK1 to BLKz) (z is a positive integer), and each of the plurality of memory blocks (BLK1 to BLKz) may include a plurality of memory cells. The memory cell array (330) may be connected to a page buffer unit (340) through bit lines (BL) and may be connected to a row decoder (360) through word lines (WL), string select lines (SSL), and ground select lines (GSL).

In an exemplary embodiment, the memory cell array (330) may include a three-dimensional memory cell array, and the three-dimensional memory cell array may include a plurality of NAND strings. Each NAND string may include memory cells respectively connected to word lines vertically stacked on the substrate. U.S. Patent Publication No. 7,679,133, U.S. Patent Publication No. 8,553,466, U.S. Patent Publication No. 8,654,587, U.S. Patent Publication No. 8,559,235, and U.S. Patent Application Publication No. 2011/0233648 are herein incorporated by reference in their entirety. In an exemplary embodiment, the memory cell array (330) may include a two-dimensional memory cell array, and the two-dimensional memory cell array may include a plurality of NAND strings arranged along the row and column directions.

According to some embodiments, the memory cell array (330) may include a plurality of physical blocks implemented in a multi-stack structure. Each physical block may include a plurality of sub-blocks separated by stacks, for example. The sub-blocks include a plurality of pages. The physical block and the sub-block may be units of an erase operation, and the page may be a unit of a read or write operation.

In general, the memory cell array (330) does not allow data overwriting. That is, existing data on the same page is not written in place with other data. New data is written to a new page, and the original page becomes an invalid page. That is, pages can be in one of three states: a free page (can be written), a valid page (a state in which valid data is stored), and an invalid page (a state in which valid data is no longer contained and cannot be used until erased).

The page buffer unit (340) may include a plurality of page buffers (PB1 to PBn) (n is an integer greater than or equal to 3), and the plurality of page buffers (PB1 to PBn) may be respectively connected to memory cells via a plurality of bit lines (BL). The page buffer unit (340) may select at least one bit line among the bit lines (BL) in response to a column address (Y-ADDR). The page buffer unit (340) may operate as a write driver or a sense amplifier depending on the operation mode. For example, in a write operation, the page buffer unit (340) may apply a bit line voltage corresponding to data to be written to the selected bit line. In a read operation, the page buffer unit (340) may detect data stored in the memory cell by detecting a current or voltage of the selected bit line.

The voltage generator (350) can generate various types of voltages for performing write, read, and erase operations based on the voltage control signal (CTRL_vol). For example, the voltage generator (350) can generate a write voltage, a read voltage, a write verify voltage, an erase voltage, etc. as a word line voltage (VWL).

The row decoder (360) can select one of a plurality of word lines (WL) and one of a plurality of string select lines (SSL) in response to a row address (X-ADDR). For example, during a write operation, the row decoder (360) can apply a write voltage and a write verify voltage to the selected word line, and during a read operation, the row decoder (360) can apply a read voltage to the selected word line.

FIG. 3 is a drawing specifically illustrating an FTL module (400) according to some embodiments.

Referring to FIG. 3, according to some embodiments, the FTL module (214) of FIG. 1 may be implemented like the FTL module (400) of FIG. 3. The FTL module (400) may include a block management unit (410), a garbage collector (420), and a write module (430).

The block management unit (410) may include a free block list (411) and a victim selectable block list (415). The block management unit (410) may manage addresses of physical blocks and sub blocks by dividing them into a free block list and a victim selectable block list for address mapping, wear-leveling operation, and garbage collection operation.

Wear-leveling operation counts the number of writes/erases per block and ensures that the degree of degradation is evenly distributed across multiple blocks.

The garbage collector (420) can rearrange data based on the wear-leveling status information of the block management unit (410). For example, the data is rearranged to address the increase in invalid pages and invalid sub-blocks due to repeated write/erase operations performed in the nonvolatile memory device (220).

The garbage collector (420) may perform a garbage collection operation as a background operation related to improving the reliability of data in an arbitrary section where writes and reads of user data are not performed. In this specification, a valid page/valid sub-block refers to a page/sub-block including data, and an invalid page/invalid sub-block refers to a page/sub-block not including data. The garbage collection operation includes moving a valid page in a first physical block to a second physical block and writing it, and erasing the first physical block to secure a free block. In addition, the garbage collection operation includes moving a valid page in the first sub-block to the second sub-block and writing it, and erasing the first sub-block. In this specification, a victim block refers to a block requiring garbage collection, and refers to a first physical block or a first sub-block from which a valid page is moved and erased.

The light module (430) can perform an operation of writing data of the host memory (120) to the nonvolatile memory device (220) according to a request of the host (100). The light module (430) can write data to a free block.

A free block may be a physical block that contains only invalid sub-blocks, or may be a physical block that contains at least one valid sub-block, depending on some embodiments. However, a physical block that consists of only valid sub-blocks is not included in a free block. The free block list may be a list of addresses of physical blocks that are sorted by a first priority based on the proportion of invalid sub-blocks and grouped, and then sorted by a second priority based on the degree of deterioration (e.g., erase count) within each group.

The storage controller (210) searches for a free block having a size corresponding to the data for which a write request has been made, and transmits the address of the free block to the nonvolatile memory device (220). If the free block includes at least one valid sub-block, the storage controller (210) performs garbage collection to move the valid sub-block to another physical block, and then designates the corresponding sub-block for which garbage collection has been completed as an invalid sub-block, and views the physical block including the invalid sub-block as a free block, and transmits the address to the nonvolatile memory device.

A victim block may be a valid sub-block from which data saved in garbage collection is moved to another sub-block. A victim block may include at least one valid page according to some embodiments. However, a victim block composed entirely of invalid sub-blocks is not included in the victim block. A victim selectable block list may be a list of addresses of physical blocks that are sorted by a first priority based on a ratio of invalid sub-blocks and grouped, and sorted by a second priority based on a valid page count within each group.

FIG. 4 is a diagram illustrating one physical block (500) according to some embodiments.

Referring to FIG. 4, the memory cell array (330) of FIG. 2 may include a plurality of physical blocks (BLK, 500). Each physical block may include a plurality of memory cells, and the plurality of memory cells may configure a plurality of pages. The physical block (BLK) may include a plurality of sub-blocks. The physical block may include a plurality of metal pads stacked between a common source line (CSL) and a bit line (BL), and the sub-blocks (511, 512, 513) may be divided into a predetermined number of stacked metal pads. In the illustrated example, the Nth physical block (500) may include three sub-blocks (511, 512, 513). The sub-blocks may include two or more pages.

The sub-blocks may be arranged to be stacked on each other between the common source line (CSL) arranged at the bottom of the physical block (500) and the bit line (BL) arranged at the top. That is, the first sub-block (511) may be arranged on the common source line (CSL), the second sub-block (412) may be stacked on the first sub-block (512), and the third sub-block (513) may be stacked on the second sub-block (512) below the bit line (BL). In the exemplary embodiment of the present invention below, it is described that one physical block includes three sub-blocks, but the scope of the present invention is not limited thereto and may be applied even when one physical block includes two or more sub-blocks.

Sub-blocks can be managed by a free block list and a victim selectable block list. A free block can be a physical block on which a write operation is to be performed. According to some embodiments, a free block can include all invalid sub-blocks. A physical block including all invalid sub-blocks can be reusable after a full erase (Full reusable).

A victim block may be a physical block from which data is to be erased when garbage collection is performed. A victim block may include at least one valid sub-block among a plurality of physical blocks. Or, in some embodiments, a victim block may be a physical block that includes only valid sub-blocks.

The free block and the big team block are described in more detail in Figures 5 and 6.

A nonvolatile memory device (330) can write or read data to a memory cell array (330) in units of pages. The nonvolatile memory device (330) can erase data in units of sub blocks or physical blocks. During an erase operation, one or more sub blocks can be selected, and the selected sub blocks can have their data erased simultaneously or sequentially. Invalid sub blocks selected by the erase operation can be sub blocks that only include invalid pages. The sub blocks included in a victim block may include the same number of pages according to one embodiment, or may include different numbers of pages according to another embodiment.

FIG. 5 is a schematic diagram illustrating one physical block to illustrate data access operations according to some embodiments.

Referring to FIGS. 4 and 5, according to some embodiments, one physical block includes a plurality of sub-blocks. Assume that a physical block (BLK a, BLK b, BLK c, BLK d) includes three sub-blocks. A sub-block that includes only invalid pages that store data and are not writable is indicated by I. A sub-block that includes at least one valid page is indicated by V. That is, a sub-block indicated by V may include only valid pages, or may include both valid pages and invalid pages.

In a nonvolatile memory device based on a multi-stack, data read and write operations are performed in units of pages, and the erase operation can be performed in units of sub blocks. There is no restriction on the erase order between sub blocks within a single physical block during the erase operation, but there is a restriction that the order in which data is written between each sub block must be maintained.

For example, since the physical block (BLK a) has sub-blocks ①, ②, and ③ all as valid sub-blocks, it cannot be written, so it can become a big team block for garbage collection, but it cannot be a free block that can be written.

For example, in the physical block (BLK b), the top ③ is an invalid sub-block, while the lower sub-block ① and sub-block ② are valid sub-blocks. In this case, the invalid sub-block ③ can be erased by garbage collection and the sub-block ③ that has been converted to a free state can be written.

For example, in a physical block (BLK c), the middle sub-block ② is an invalid sub-block, and the top sub-block ③ and the bottom sub-block ① are valid sub-blocks. In this case, the top sub-block ③ is a victim sub-block, and after data is moved to the sub-block of another physical block, the sub-block ③ and the middle sub-block ② can be erased to convert it into a free block. In other words, since the physical block (BLK c) must be moved data once and erased once, it requires more management cost than the physical block (BLK b) that only performs one erase.

For example, since all subblocks ①, ②, and ③ of a physical block (BLK d) contain only invalid pages, they can all be erased simultaneously to convert them into free blocks, and then written in the order of subblock ①, subblock ②, and subblock ③.

To overcome these limitations, the storage controller (210) can manage blocks by sorting the writable priority by distinguishing between free blocks that are immediately writable, usable blocks that are writable after performing one erase, and victim selectable blocks that become writable after performing garbage collection for other sub blocks, even if erased in sub-block units. In the embodiments of FIGS. 6 to 10 below, reusable blocks and victim blocks will be described in more detail, excluding pure free blocks.

Fig. 6 is a conceptual diagram illustrating a free block list according to some embodiments. The free block list (411) of Fig. 3 can be implemented as in Fig. 6.

For example, the block management unit (410) sorts and groups a plurality of physical blocks in a first order based on the ratio of invalid sub-blocks (I) among the plurality of sub-blocks. Or, for example, the block management unit (410) sorts and groups a plurality of physical blocks in a first order based on the ratio of valid sub-blocks (V) among the plurality of sub-blocks. For example, the first order may be set to have a higher priority as the number of invalid sub-blocks (I) increases or as the number of valid sub-blocks (V) decreases.

The free block list (411) may be a block list sorted in the first order of L1, L2, L3, and L4 according to the ratio and location of invalid sub-blocks.

As described in Fig. 5, the more free blocks there are of invalid sub-blocks, the more space there is to erase and write data, so the block management unit (410) can determine physical blocks that contain only invalid sub-blocks (i.e., all three are invalid sub-blocks) as the highest priority L1 (Full Reusable Block).

The block management unit (410) can determine the priority differently according to the location of the invalid sub-block (or the location of the valid sub-block) for physical blocks including at least one valid sub-block (Partial Reusable Block). This is because, depending on the location of the invalid sub-block, there are cases where it can be reused as a free sub-block by performing only erase, and cases where it can be reused as a free sub-block by performing erase after moving the data of the victim sub-block by garbage collection.

For example, for L2, valid sub-blocks are located at the bottom of the physical block, and invalid sub-blocks are located at the middle and top of the physical block. In this case, data of invalid sub-blocks located at the middle and top of the physical block can be erased simultaneously.

For example, in the case of L3, a valid sub-block is located in the middle of a physical block, and invalid sub-blocks are located at the bottom and top of the physical block. In this case, the invalid sub-block located at the top of the physical block can be reused after erasing. However, the middle valid sub-block cannot be erased because data is stored there before garbage collection. Even if the physical blocks include the same number of invalid sub-blocks as in the embodiments of L2 and L3, the size of the writable sub-blocks varies depending on the location of the invalid sub-blocks. That is, the write priority can be set higher depending on the number of writable sub-blocks with the erase alone.

For example, in the case of L4, valid sub-blocks are located at the bottom and middle of the physical block, and invalid sub-blocks are located at the top of the physical block. In this case, the invalid sub-block located at the top of the physical block can be easily erased. However, since the number of reusable sub-blocks is small compared to L1 or L3 groups, it can have the last write priority.

For a plurality of physical blocks grouped (L1, L2, L3, L4) sorted in the first order, they can be sorted in the second order. The second order may be sorted according to the degree of wear leveling of the physical blocks. The physical blocks ①, ②, ③, and ④ illustrated in Fig. 6 may be arranged in the sorted order according to wear leveling including the erase count, etc. Since a block has a smaller erase count and is less deteriorated, the physical blocks ①, ②, ③, and ④ grouped in the first order can be sorted in the second order according to the erase count.

That is, for wear leveling, within the same group (e.g., L1 group), physical block ① can have a higher priority than physical block ② because it is less degraded based on the erase count.

Fig. 7 is a conceptual diagram illustrating a big team selectable block list according to some embodiments. The big team selectable block list (415) of Fig. 3 can be implemented as in Fig. 7.

Unlike the free block list (411), the victim selectable block list (415) includes every physical block with at least one valid sub-block. A victim block refers to a physical block that includes at least one valid page containing data and can be converted into a free block by erasing it after moving data at least once.

For example, the block management unit (410) sorts the plurality of physical blocks in a first order based on the ratio of valid sub-blocks (V) among the plurality of sub-blocks. Or, for example, the block management unit (410) sorts the plurality of physical blocks in a first order based on the ratio of invalid sub-blocks (I) among the plurality of sub-blocks. The first order may have a higher priority set, for example, as the number of valid sub-blocks (V) is smaller or the number of invalid sub-blocks (I) is larger. The big team selectable block list (415) may be a block list sorted in the first order of L1, L2, L3, and L4 according to the ratio of invalid sub-blocks (I) and the position of the invalid sub-blocks (I).

The Big Team Selectable Block List (415) sets the priority of physical blocks higher as the number of invalid sub-blocks increases, so that space is secured for erasing sub-blocks and writing data during garbage collection.

For example, a physical block belonging to an L1 group in the big team selectable block list (415) includes two invalid sub-blocks and one valid sub-block, a physical block belonging to an L2 and L3 group includes one invalid sub-block and two valid sub-blocks, and a physical block belonging to an L4 group includes three valid sub-blocks.

For L1 group, valid sub-blocks are located at the top of the physical block, and invalid sub-blocks are located at the middle and bottom of the physical block. In this case, invalid sub-blocks located at the middle and bottom of the physical block can be used by first moving the data of the valid sub-block (V) located at the top to another physical block, and then erasing the bottom, middle, and top sub-blocks.

For example, in the case of the L2 group, valid sub-blocks are located at the top and middle of the physical block, and invalid sub-blocks are located at the bottom of the physical block. In this case, the invalid sub-block located at the bottom of the physical block can be used by first moving the data of the valid sub-blocks (V) located at the top and middle of the physical block to other physical blocks, respectively, and then erasing the entire physical block. Since the physical blocks of the L2 group must move the data of the valid sub-blocks (V) of two stages (top and middle) and then erase them, the load is greater than that of the physical blocks of the L1 group that only moves the valid sub-block of the first stage (top). Therefore, the L2 group has a lower priority than the L1 group as a victim block.

For example, in the case of the L3 group, valid sub-blocks are located at the top and bottom of the physical block, and invalid sub-blocks are located in the middle of the physical block. In this case, the valid sub-block located at the top of the physical block can be used after moving data to a sub-block of another physical block and erasing it together with the invalid sub-blocks. However, the valid sub-block located at the bottom of the physical block must be moved data to another physical block and erased after both the top and middle sub-blocks are erased, so the load of the garbage collection operation may be greater than that of the L2 group. In other words, erase-and-write is possible only for the top and middle sub-blocks. Since the L3 group can reuse only two sub-blocks, it has a lower priority than the L2 group.

For example, for the L4 group, valid sub-blocks are located at the top, middle, and bottom of the physical block. In this case, the data of the valid sub-block located at the top of the physical block is moved and erased, then the data of the valid sub-block located in the middle is moved and erased, and then the data of the valid sub-block located at the bottom is moved and erased. In other words, since the load of the garbage collection operation is greater than that of other L1, L2, and L3 groups, the L4 group has the lowest priority.

For a plurality of physical blocks included in physical blocks (L1, L2, L3, L4) sorted and grouped in the first order, sorting can be performed in the second order. The second order may be sorted according to the valid page count of the physical blocks. The physical blocks ①, ②, ③, and ④ illustrated in Fig. 8 may be arranged in the sorted order according to the order of physical blocks with good garbage collection efficiency including the valid page count, etc. Since a block has many invalid pages as the valid page count is smaller, the physical blocks L1, L2, L3, and L4 grouped in the first order can be sorted in the second order ①, ②, ③, and ④ in which the valid page count gradually increases.

That is, in order to save on the cost of garbage collection, within the same group (e.g., L1 group), physical block ① can have a higher priority than physical block ② because it has fewer valid pages based on the erase count.

Figure 8 is a conceptual diagram illustrating a block list stored in an FTL module according to some embodiments.

Referring to FIG. 8, the free block list (411) and the big team selectable block list (415) can be stored as a linked list structure of multiple physical block lists.

When receiving a write request from a host, the FTL module (214) first selects a physical block grouped in the first order from the free block list. If the L1 group of FIG. 6 is described as an example, the FTL module (214) checks the free block information of the physical block according to the write request. The FTL module (214) first checks the head #N indicating the L1 group from the free block list (411), and checks the free block information stored in the first physical block having the head #N in the memory. At this time, the memory may be a nonvolatile memory included in the block management unit (410) of the FTL module (214).

Free block information may include a head of a group (#N), a physical block address, an erase count for a sub-block, and a page valid status, depending on some embodiments. The page valid status may include whether a page is valid/invalid and location information of a valid page (or an invalid page), depending on some embodiments.

When a garbage collection operation is required, the storage device (200) activates the garbage collection operation, and the FTL module (214) selects a physical block grouped in the first order from the victim selectable block list. As an example of the L1 group of FIG. 7, the FTL module (214) checks the victim block information of the physical block according to the garbage collection activation. The FTL module (214) first checks the head #N indicating the L1 group from the victim selectable block list (415), and checks the victim block information stored in the first physical block having the head #N in the memory. At this time, the memory may be a nonvolatile memory included in the block management unit (410) of the FTL module (214).

The big team block information may include, according to some embodiments, a head of the group (#N), a physical block address connected to the head, a valid page count for a sub-block, and a page valid status. The page valid status may be, according to some embodiments, whether a page is valid/invalid and location information of a valid page (or an invalid page).

The FTL module (214) returns the addresses of sub-blocks included in the physical blocks of the L1 group if the corresponding write request can be processed in the L1 group (#N) based on the free block information, and transmits the write request and the addresses of the returned sub-blocks to the non-volatile memory device (220).

However, if the FTL module (214) cannot process the corresponding write request in the L1 group (#N) based on the free block information, it moves on to the L2 group (head #M) connected in the next order to the L1 group (#N). The head #N and head #M of each group can be, for example, a list connected to the node of the first physical block of the L2 group for the node of the first physical block of the L1 group.

Similarly, if garbage collection is processable in the L1 group (#N) based on the big team block information, the FTL module (214) returns the addresses of the sub blocks included in the physical blocks of the L1 group and transmits a garbage collection request and the addresses of the returned sub blocks to the nonvolatile memory device (220).

However, if the FTL module (214) cannot process a garbage collection request in the L1 group (#N) based on the big team block information, it moves on to the L2 group (head #M) connected in the next order to the L1 group (#N). The head #N and head #M of each group can be, for example, a list connected to the node of the first physical block of the L2 group for the node of the first physical block of the L1 group.

FIG. 9 is a diagram illustrating light operation of a storage device according to some embodiments.

Referring to FIG. 9, when receiving a write request from a host (100), the FTL module (214) searches for a logical block-physical block address to process the write request in the write module (430).

For example, the light module (430) requests a free block address to the block management unit (410) (① Get Free Block), and the block management unit (410) checks the free block list (411) (② List Check). The block management unit (410) checks the head of the group sorted in the first order in the free block list (411) (③ Pop Head), and searches for a physical block that can process the light request based on the free block information.

If the physical block of the L1 group can process the write request, the address of the physical block and the address of the sub-block determined to be processable are returned in response to the write request (④ Return Block).

In this way, when performing a write operation on a nonvolatile memory device including sub-blocks according to some embodiments, by separately managing a free block list while considering write restrictions (program sequence) between sub-blocks, there is an advantage in that the space of the nonvolatile memory device can be utilized more efficiently while freely performing an erase operation on the sub-blocks. In addition, by performing a write operation based on the free block list and free block information, the FTL (File Tranlation Layer) can be utilized efficiently.

FIG. 10 is a diagram illustrating garbage collection operations of a storage device according to some embodiments.

Referring to FIG. 10, when garbage collection is activated based on an external request or internal judgment, the FTL module (214) searches for a logical block-physical block address to process garbage collection in the garbage collector (420).

For example, the garbage collector (420) requests the block management unit (410) for a victim block address (① Get Victim Block), and the block management unit (410) checks the victim selectable block list (415) (② List Check). The block management unit (410) checks the head of the group sorted in the first order in the victim selectable block list (415) (③ Pop Head), and searches for a physical block requiring garbage collection based on the victim block information.

If a physical block of the L1 group requires the above garbage collection, the address of the physical block and the address of the sub-block determined to require garbage collection based on the search result are returned (④ Return Block).

In this way, when performing a garbage collection operation on a nonvolatile memory device including a sub-block according to some embodiments, by managing the victim selectable block list while considering the write operation order and erase constraints on the sub-block, there is an advantage in that the cost required for moving data can be reduced while freely performing an erase operation on the sub-block. In addition, by performing the garbage collection operation based on the victim selectable block list and the victim block information, the FTL (File Tranlation Layer) can be efficiently used.

FIGS. 11 to 13 are flowcharts illustrating a method of operating a storage device according to some embodiments.

Referring to FIGS. 11 to 13, the storage controller (210) receives a write request from the host (100) (S100). The storage controller (210) checks whether there is a free block in the nonvolatile memory device (220) to store data according to the write request (S110), and if there are many free blocks in the nonvolatile memory device (220), transmits the write request to the nonvolatile memory device (S160).

However, if there are not enough free blocks to process the write request in the nonvolatile memory device (220) (S110, Yes), a reusable free block is requested (S120). The write module (430) obtains the address of the reusable free block based on the free block list (411). Specifically, if there is a group that includes only invalid sub-blocks (Full Resulable Block), for example, if it is determined that the write request can be processed in the L1 group of FIG. 6 (S130, Yes), the head of the L1 group is selected (S140). The storage controller transmits the address of the physical block belonging to the L1 group to the nonvolatile memory device (220) together with the write request (S150).

On the other hand, if the write request cannot be processed in a group that includes only invalid sub-blocks (S130, No), it is checked whether the write request is possible in the next group with a lower priority. For example, if the processing is impossible in the L1 group of FIG. 6, the storage controller (210) checks the next group L2 group (i.e., Partial Reusable block, if it includes at least one valid sub-block) according to the linked list in the pro block list (411) (S200).

If the write request can be processed in a physical block belonging to the L2 group (S210, Yes), and since it contains at least one valid sub-block, the storage controller (210) requests a big block to perform garbage collection in order to move the valid sub-block at the minimum cost and reuse the invalid sub-block (S300).

The storage controller (210) checks the selectable victim block with the highest priority in the victim selectable block list to perform garbage collection (S310). If garbage collection is possible in the physical block belonging to the L1 group of FIG. 7 (S310, Yes), the head of the L1 group is selected (S340), and garbage collection is performed to move and erase data stored in at least one valid sub-block to the address and sub-block address of the physical block belonging to the L1 group (S350), and a free block is requested for the physical block of the L1 group in the victim selectable block list (415) for which garbage collection is completed (S120).

However, if garbage collection is not possible in a physical block belonging to an L1 group of FIG. 7 (S310, No), it is checked whether garbage collection is possible in a group of the next priority in the victim selectable block list (415) (S320). For example, if garbage collection is possible in an L2 group having the next priority after the L1 group (S330, Yes), the head of the L2 group is selected (S340), and garbage collection is performed by moving and erasing data stored in at least one valid sub-block to the address and sub-block address of the physical block belonging to the L2 group (S350), and a free block is requested for the physical block of the L2 group in the victim selectable block list (415) for which garbage collection is completed (S120).

Similarly, if garbage collection is not possible in a physical block belonging to the L2 group of Fig. 7 (S330, No), it is checked whether garbage collection is possible in the next priority group in the big team selectable block list (415) (S320).

If there is no empty physical block to process the write request in the physical block belonging to the L2 group (S210, No), it is checked whether the write request is possible in the next L3 group with lower priority (S230).

*If a write request can be processed in the L3 group (S230, Yes), the head of the L3 group is selected (S140) and the address of the physical block belonging to the L3 group is returned to the nonvolatile memory device (220) (S150).

In some embodiments, a nonvolatile memory device implemented with a multi-stack including sub-blocks has no constraints on the erase operation order of the sub-blocks, but has constraints on the write operation order of the sub-blocks. Therefore, the free block list and the victim selectable block list are managed separately in consideration of the write constraints on the sub-blocks. Accordingly, the storage device (200) can efficiently use the space of the nonvolatile memory device and efficiently use the FTL (File Tranlation Layer) by first writing to a sub-block with a smaller garbage collection load for the write operation while freely performing an erase operation on the sub-blocks.

FIG. 14 is a diagram illustrating a system to which a storage device according to one embodiment of the present invention is applied.

The system (1000) of FIG. 14 may be a mobile system, such as a mobile phone, a smart phone, a tablet personal computer, a wearable device, a healthcare device, or an Internet of Things (IoT) device. However, the system (1000) of FIG. 14 is not necessarily limited to a mobile system, and may also be a personal computer, a laptop computer, a server, a media player, or an automotive device, such as a navigation device.

Referring to FIG. 14, the system (1000) may include a main processor (1100), a memory (1200a, 1200b), and a storage device (1300a, 1300b), and may additionally include one or more of an image capturing device (1410), a user input device (1420), a sensor (1430), a communication device (1440), a display (1450), a speaker (1460), a power supplying device (1470), and a connecting interface (1480).

The main processor (1100) can control the overall operation of the system (1000), more specifically, the operation of other components forming the system (1000). The main processor (1100) can be implemented as a general-purpose processor, a dedicated processor, or an application processor.

The main processor (1100) may include one or more CPU cores (1110) and may further include a controller (1120) for controlling a memory (1200a, 1200b) and/or a storage device (1300a, 1300b). Depending on the embodiment, the main processor (1100) may further include an accelerator block (1130), which is a dedicated circuit for high-speed data operations such as artificial intelligence (AI) data operations. Such an accelerator block (1130) may include a GPU (Graphics Processing Unit), an NPU (Neural Processing Unit), and/or a DPU (Data Processing Unit), and may be implemented as a separate chip that is physically independent from other components of the main processor (1100).

The memory (1200a, 1200b) may be used as a main memory device of the system (1000), and may include volatile memory such as SRAM and/or DRAM, but may also include nonvolatile memory such as flash memory, PRAM and/or RRAM. The memory (1200a, 1200b) may also be implemented in the same package as the main processor (1100).

The storage device (1300a, 1300b) can function as a non-volatile storage device that stores data regardless of whether power is supplied, and can have a relatively large storage capacity compared to the memory (1200a, 1200b). The storage device (1300a, 1300b) can include a storage controller (1310a, 1310b) and a non-volatile memory (NVM) storage (1320a, 1320b) that stores data under the control of the storage controller (1310a, 1310b). The non-volatile memory (1320a, 1320b) can include a V-NAND flash memory having a 2D (2-dimensional) structure or a 3D (3-dimensional) structure, but can also include other types of non-volatile memory such as PRAM and/or RRAM.

The storage device (1300a, 1300b) may be included in the system (1000) in a physically separated state from the main processor (1100), or may be implemented in the same package as the main processor (1100). In addition, the storage device (1300a, 1300b) may have a form such as an SSD (solid state device) or a memory card, and may be detachably coupled to other components of the system (1000) through an interface such as a connection interface (1480) to be described later. Such storage device (1300a, 1300b) may be a device to which standard specifications such as UFS (universal flash storage), eMMC (embedded multi-media card), or NVMe (non-volatile memory express) are applied, but is not necessarily limited thereto.

The photographing device (1410) can capture still images or moving images and may be a camera, a camcorder, and/or a webcam.

The user input device (1420) can receive various types of data input from a user of the system (1000), and may be a touch pad, a keypad, a keyboard, a mouse, and/or a microphone.

The sensor (1430) can detect various types of physical quantities that can be obtained from the outside of the system (1000) and convert the detected physical quantities into electrical signals. Such a sensor (1430) can be a temperature sensor, a pressure sensor, a light sensor, a position sensor, an acceleration sensor, a biosensor, and/or a gyroscope.

The communication device (1440) can transmit and receive signals between other devices outside the system (1000) according to various communication protocols. Such a communication device (1440) can be implemented by including an antenna, a transceiver, and/or a modem.

The display (1450) and speaker (1460) can function as output devices that output visual information and auditory information, respectively, to the user of the system (1000).

The power supply unit (1470) can appropriately convert power supplied from a battery (not shown) built into the system (1000) and/or an external power source and supply it to each component of the system (1000).

The connection interface (1480) can provide a connection between the system (1000) and an external device that is connected to the system (1000) and can exchange data with the system (1000). The connection interface (1480) can be implemented in various interface methods, such as an Advanced Technology Attachment (ATA), a Serial ATA (SATA), an external SATA (e-SATA), a Small Computer Small Interface (SCSI), a Serial Attached SCSI (SAS), a Peripheral Component Interconnection (PCI), a PCI express (PCIe), a NVM express (NVMe), an IEEE 1394, a universal serial bus (USB), a secure digital (SD) card, a multi-media card (MMC), an embedded multi-media card (eMMC), a Universal Flash Storage (UFS), an embedded Universal Flash Storage (eUFS), a compact flash (CF) card interface, etc.

Although the embodiments of the present invention have been described with reference to the attached drawings, those skilled in the art will understand that the present invention can be implemented in other specific forms without changing the technical idea or essential features thereof. Therefore, it should be understood that the embodiments described above are exemplary in all respects and not restrictive.

10: Storage System
100: Host 200: Storage Device
110 : Host controller 120 : Host memory
210 : Storage controller 220,300 : Nonvolatile memory device
214, 400 : FTL 410 : Block Management
411: Free Block List 415: Big Team Selectable Block List
420: Garbage Collector 430: Light Module
500 : Physics Block

Claims (20)

A nonvolatile memory device comprising a plurality of physical blocks, each of which includes a plurality of sub-blocks; and
A storage controller including a free block list and a victim selectable block list for the plurality of physical blocks and controlling operation of the nonvolatile memory device,
The above storage controller
If there are not enough free blocks to store data according to a write request received from the host, the entire reusable physical block is checked in the free block list and the head of the checked block is selected.
If there is no fully reusable physical block above, garbage collection is performed based on the big team selectable block list.
A storage device that transmits the address of a physical block on which the garbage collection has been performed to the non-volatile memory device together with the write request. In the first paragraph, the free block list
Based on the ratio of invalid sub-blocks among the plurality of sub-blocks, the plurality of physical blocks are sorted and grouped in a first order,
A storage device, wherein the list of blocks is organized by sorting at least two physical blocks belonging to one group in a second order based on the erase count of each of the grouped physical blocks. In the second paragraph, the free block list
A storage device that stores a plurality of physical blocks in a linked list structure in the storage controller based on free block information including a head of a group according to the first order, an erase count of the physical block, and a page validity status of the sub block. In the second paragraph, the storage controller
When the above light request is received, the above free block list is called,
Check the head of the group grouped according to the first order in the above free block list,
Select a head corresponding to the light request according to the above free block list,
A storage device that returns the address of a physical block corresponding to the write request among the physical blocks connected to the selected head and transmits it to the non-volatile memory device. In the fourth paragraph, selecting the head
A storage device that selects a first head of a first physical block belonging to a first group when there is a first group including only invalid sub-blocks. In the fifth paragraph, when selecting the head,
A storage device that selects a second head of a second physical block including at least one valid sub-block when the first physical block is absent. In the first paragraph, the big team selectable block list is
The plurality of physical blocks are sorted and grouped in a third order based on the ratio of invalid sub-blocks among the plurality of sub-blocks,
A storage device, wherein the block list is organized by sorting at least two physical blocks belonging to one group in a fourth order based on the valid page count of each physical block grouped in the third order. In the 7th paragraph, the big team selectable block list is
A storage device that stores a plurality of physical blocks in a linked list structure in the storage controller based on victim block information including a head of a group according to the third order, a valid page count of the physical block, and a page valid status of the sub block. A nonvolatile memory device comprising a plurality of physical blocks divided into a plurality of sub-blocks in a multi-stack structure;
A storage controller is included that controls the operation of the non-volatile memory device,
The above storage controller
A light module that requests the address of a free block according to the light request upon receiving a light request from the host;
A garbage collector requesting the address of a big team block to perform garbage collection; and
A storage device comprising a block management unit storing a free block list and a victim selectable block list, and selecting and returning a physical block corresponding to a request of a light module or a request of a garbage collector from the free block list or the victim selectable block list. In the 9th paragraph, the free block list
Sorting and grouping in the first writing order from the number of invalid sub-blocks among the above multiple sub-blocks starting from the largest to the smallest,
A storage device, which is a list of physical blocks sorted in second writing order from smallest to largest erase count among the above grouped physical blocks. In the 9th paragraph, the block management unit
In response to the request of the above light module, check the entire reusable physical block in the above free block list,
If there is a first physical block including a fully reusable sub-block, select the first head of the group to which the first physical block belongs and the first physical block connected to the first head,
A storage device that returns the address of the first physical block to the light module. In the 11th paragraph, the block management unit
If there is no first physical block that is entirely reusable, select a second head of a group to which a second physical block including at least one valid sub-block belongs,
A storage device that selects an address of a second physical block corresponding to a request of the light module from among a plurality of second physical blocks connected to the second head. In the 12th paragraph, the block management unit
A storage device that requests the victim block from the victim selectable block list by requesting the garbage collector when there is no physical block belonging to the second head. In the 9th paragraph, the block management unit
In response to the request of the above garbage collector, check the big team block belonging to the first priority group from the big team selectable block list,
If selectable within the above first-priority group, select the head of the above first-priority group,
A storage device that returns, to the garbage collector, the address of a third physical block having victim block information corresponding to a request of the garbage collector among the third physical blocks connected to the head. In the 14th paragraph, the big team selectable block list is
Sorting and grouping in order of the first big team with the smallest number of valid sub-blocks among the above multiple sub-blocks,
A storage device, which is a list of physical blocks sorted in second big team order from smallest to largest valid page count among the above grouped physical blocks. Step of receiving a light request from a host;
A step of checking whether there is a first physical block available for reuse in the free block list corresponding to the write request and capable of storing the write-requested data;
A step of selecting a first head of a group to which the first physical block belongs when there is a first physical block that is entirely reusable and returning a free block address including the first head to a nonvolatile memory device;
If the first physical block is not present, selecting a second head including at least one valid sub-block from the free block list, and returning an address of the physical block to which the second head belongs if the physical block to which the second head belongs is sufficient to store the write-requested data; and
A method of operating a storage controller, comprising the step of transmitting an address of the returned physical block together with the write request to the non-volatile memory device. In the 16th paragraph, if the physical block to which the second head belongs is not sufficient to store the write-requested data, the step of returning the physical block address to which the second head belongs
Steps to start garbage collection;
When the above garbage collection starts, a step of selecting a big team block based on the light-requested data from the big team selectable block list;
A step of performing garbage collection on the above-mentioned selected big team blocks to convert them into free blocks; and
A method of operating a storage controller, comprising the step of returning an address of the converted free block. In the 16th paragraph, the nonvolatile memory device includes a plurality of physical blocks including a plurality of sub blocks,
The above free block list is
Sorting and grouping in the first writing order from the largest number of invalid sub-blocks among multiple sub-blocks to the smallest number,
A method of operating a storage controller, the method comprising: organizing a list of physical blocks by sorting them in second writing order from a small erase count among the above grouped physical blocks; In the 18th paragraph, the free block list is
A method of operating a storage controller, wherein a plurality of physical blocks are stored in the storage controller in a linked list structure based on free block information including a head of a group according to the first writing order, an erase count of the physical block, and a page validity status of the sub block. In the 17th paragraph, the big team selectable block list is
Sorting and grouping in order of the first big team with the smallest number of valid sub-blocks among the above multiple sub-blocks,
A method of operating a storage controller, the method comprising: organizing a list of physical blocks by sorting them in the order of the second big team, from the smallest valid page count among the above grouped physical blocks.

Images