JP7567009B2 - MEMORY SYSTEM AND CONTROL METHOD - Patent application - Google Patents

Description

An embodiment of the present invention relates to a technology for controlling non-volatile memory.

In recent years, memory systems equipped with non-volatile memory have become widespread.

One such memory system is a solid-state drive (SSD) based on NAND flash technology.

Recently, new interfaces between hosts and storage have begun to be proposed.

Yiying Zhang et al., "De-indirection for flash-based SSDs with nameless writes." FAST. 2012, [online], [Retrieved September 13, 2017], Internet <URL: https://www.usenix.org/system/files/conference/fast12/zhang.pdf >

However, since the control of NAND flash memory is generally complex, when implementing a new interface to improve I/O performance, it is necessary to consider an appropriate division of roles between the host and the storage (memory system).

The problem that this invention aims to solve is to provide a memory system and control method that can improve I/O performance.

According to an embodiment, a memory system connectable to a host includes a non-volatile memory including a plurality of blocks, each of which is a unit of an erase operation and each of which is specified by a block number, and a controller electrically connected to the non-volatile memory and controlling the non-volatile memory. In response to receiving a copy command from the host specifying at least a first block number, the controller reads first data from a first block specified by the first block number among the plurality of blocks, writes the first data to a first position in a second block different from the first block among the plurality of blocks, and notifies the host of a first identifier for identifying the first data, a second block number specifying the second block, and a physical address within the first block indicating the first position within the second block.

FIG. 2 is a block diagram showing the relationship between a host and a memory system (flash storage device) according to an embodiment. 1A and 1B are diagrams for explaining the division of roles between a conventional SSD and a host, and the division of roles between a flash storage device and a host in the embodiment. FIG. 1 is a block diagram showing an example of the configuration of a computer system in which data transfer between multiple hosts and multiple flash storage devices is performed via a network device. FIG. 2 is a block diagram showing an example of the configuration of a memory system according to the embodiment. FIG. 2 is a block diagram showing the relationship between a NAND interface and multiple NAND flash memory dies provided in the memory system of the embodiment. FIG. 13 is a diagram showing an example of the configuration of a superblock constructed by a set of multiple blocks. A diagram for explaining a data write operation in which the host specifies a logical address and a block number and the memory system of the embodiment determines a physical address within the block (offset within the block), and a data read operation in which the host specifies a block number and a physical address within the block (offset within the block). 4 is a diagram for explaining a write command applied to the memory system of the embodiment. 9 is a diagram for explaining a response to the write command in FIG. 8 . 4 is a diagram for explaining a Trim command applied to the memory system of the embodiment. FIG. 2 is a diagram for explaining a block number and an offset that represent a physical address. FIG. 4 is a diagram for explaining a write operation executed in response to a write command. 11A and 11B are diagrams for explaining a write operation that skips a defective page. 11A and 11B are diagrams for explaining another example of a write operation that skips a bad page. 1A and 1B are diagrams for explaining an operation of writing a pair of a logical address and data to a page in a block. 13 is a diagram for explaining an operation of writing data to a user data area of a page in a block and writing the logical address of this data to a redundant area of this page. FIG. 13 is a diagram for explaining the relationship between block numbers and offsets when a superblock is used. 11 is a diagram for explaining a maximum block number get command applied to the memory system of the embodiment. FIG. 13 is a diagram for explaining a response to a maximum block number get command. 4 is a diagram for explaining a block size get command applied to the memory system of the embodiment. FIG. 13 is a diagram for explaining a response to a block size get command. 4 is a diagram for explaining a block allocate command (block allocation request) applied to the memory system of the embodiment. FIG. 13 is a diagram for explaining a response to a block allocate command. 11 is a sequence chart showing a block information acquisition process executed by the host and the memory system of the embodiment. 11 is a sequence chart showing a sequence of a write process executed by a host and the memory system of the embodiment. 11A and 11B are diagrams showing a data update operation for writing update data for data that has already been written; 4 is a diagram for explaining an operation of updating a block management table managed by the memory system of the embodiment. 11 is a diagram for explaining an operation of updating a lookup table (logical-physical address conversion table) managed by a host. 11 is a diagram for explaining an operation of updating the block management table in response to a notification from a host indicating a block number and a physical address corresponding to data to be invalidated. 4 is a diagram for explaining a read command applied to the memory system of the embodiment. 4 is a diagram for explaining a read operation executed by the memory system of the embodiment. 1A and 1B are diagrams for explaining an operation of reading data portions stored in different physical storage locations in response to a read command from a host. 11 is a sequence chart showing a sequence of a read process executed by a host and the memory system of the embodiment. 3A and 3B are diagrams for explaining garbage collection (GC) control commands applied to the memory system of the embodiment. 4 is a diagram for explaining a GC callback command applied to the memory system of the embodiment. 1 is a sequence chart showing the procedure of a garbage collection (GC) operation executed by the host and the memory system of the embodiment. 1A and 1B are diagrams for explaining an example of a data copy operation executed for garbage collection (GC); 38 is a diagram for explaining the contents of the host's lookup table that is updated based on the result of the data copy operation of FIG. 37 .

The following describes the embodiment with reference to the drawings.

First, referring to FIG. 1, the configuration of a computer system including a memory system according to one embodiment will be described.

The memory system is a semiconductor storage device configured to write data to and read data from non-volatile memory. The memory system is realized as a flash storage device 3 based on NAND flash technology.

This computer system may include a host (host device) 2 and multiple flash storage devices 3. The host 2 may be a server configured to use a flash array composed of multiple flash storage devices 3 as storage. The host (server) 2 and multiple flash storage devices 3 are interconnected via an interface 50 (internal interconnection). The interface 50 for this internal interconnection may be, but is not limited to, PCI Express (PCIe) (registered trademark), NVM Express (NVMe) (registered trademark), Ethernet (registered trademark), NVMe over Fabrics (NVMeOF), etc.

A typical example of a server that functions as a host 2 is a server in a data center.

In the case where the host 2 is realized by a server in a data center, this host (server) 2 may be connected to multiple end user terminals (clients) 61 via a network 51. The host 2 can provide various services to these end user terminals 61.

Examples of services that can be provided by the host (server) 2 include (1) Platform as a Service (PaaS), which provides a system operation platform to each client (each end-user terminal 61), and (2) Infrastructure as a Service (IaaS), which provides infrastructure such as a virtual server to each client (each end-user terminal 61).

Multiple virtual machines may be executed on this physical server functioning as the host (server) 2. Each of these virtual machines running on the host (server) 2 can function as a virtual server configured to provide various services to a number of corresponding clients (end-user terminals 61).

The host (server) 2 includes a storage management function that manages multiple flash storage devices 3 that make up the flash array, and a front-end function that provides various services, including storage access, to each end-user terminal 61.

In conventional SSDs, the block/page hierarchical structure of the NAND flash memory is hidden by the flash translation layer (FTL) in the SSD. In other words, the FTL of conventional SSDs has the following functions: (1) a function to manage mapping between each logical address and each physical address of the NAND flash memory using a lookup table that functions as a logical-physical address translation table, (2) a function to conceal page-based read/write and block-based erase operations, and (3) a function to perform garbage collection (GC) of the NAND flash memory. The mapping between each logical address and the physical address of the NAND flash memory is invisible to the host. The block/page structure of the NAND flash memory is also invisible to the host.

On the other hand, a type of address conversion (application level address conversion) may also be performed on the host. This address conversion uses an application level address conversion table to manage the mapping between each application level logical address and each logical address for the SSD. Also, on the host, a type of GC (application level GC) is performed that changes the data arrangement on the logical address space for the SSD to eliminate fragmentation that occurs in this logical address space.

However, in a redundant configuration in which the host and SSD each have their own address translation table (the SSD has a lookup table that functions as a logical-physical address translation table, and the host has an application-level address translation table), huge memory resources are consumed to hold these address translation tables. Furthermore, the double address translation, which includes address translation on the host side and address translation on the SSD side, can also cause a decrease in I/O performance.

Furthermore, application-level GC on the host side causes the amount of data written to the SSD to increase by several times (e.g., twice) the actual amount of user data. This increase in the amount of data written, combined with write amplification in the SSD, reduces the storage performance of the entire system and also shortens the lifespan of the SSD.

To resolve these issues, one possible solution would be to move all of the FTL functions of conventional SSDs to the host.

However, to implement this measure, it is necessary for the host to directly handle the blocks and pages of the NAND flash memory. In NAND flash memory, there are page write order constraints, so it is difficult for the host to directly handle the pages. Also, in NAND flash memory, blocks may contain defective pages (bad pages). It is even more difficult for the host to handle bad pages.

Therefore, in this embodiment, the role of the FTL is shared between the host 2 and the flash storage device 3. Generally speaking, the host 2 manages a lookup table that functions as a logical-physical address conversion table, but the host 2 specifies only the block number of the block to which data is to be written and the logical address corresponding to this data, and the location within this block to which this data is to be written (destination location) is determined by the flash storage device 3. The physical address within the block indicating the determined location within the block (destination location) is notified to the host 2 by the flash storage device 3.

In this way, the host 2 only handles blocks, and the positions within the blocks (e.g. pages, positions within pages) are handled by the flash storage device 3.

When data needs to be written to the flash storage device 3, the host 2 selects a block number (or requests the flash storage device 3 to allocate a free block) and sends a write request (write command) to the flash storage device 3, specifying the logical address and the block number of the selected block (or the block number of the allocated block notified by the flash storage device 3). The flash storage device 3 writes the data from the host 2 to the block having the specified block number. In this case, the flash storage device 3 determines a position within this block (destination position) and writes the data from the host 2 to this position within this block (destination position). The flash storage device 3 then notifies the host 2 of the physical address within the block indicating the position within this block (destination position) as a response (return value) to the write request. Hereinafter, the FTL function transferred to the host 2 is referred to as global FTL.

The global FTL of the host 2 has functions such as a function to execute storage services, a wear control function, a function to realize high availability, a deduplication function to prevent multiple duplicate data parts having the same contents from being stored in the storage, a garbage collection (GC) block selection function, and a QoS control function. The QoS control function includes a function to determine the access unit for each QoS domain (or for each block). The access unit indicates the minimum data size (grain) that the host 2 can write/read. The flash storage device 3 supports single or multiple access units (grain), and the host 2 can instruct the flash storage device 3 which access unit to use for each QoS domain (or for each block) if the flash storage device 3 supports multiple access units.

The QoS control function also includes a function for preventing performance interference between QoS domains as much as possible. This function is basically a function for maintaining stable latency.

On the other hand, the flash storage device 3 can execute low-level abstraction (LLA). LLA is a function for abstraction of NAND-type flash memory. LLA includes a function for concealing defective pages (bad pages) and a function for observing page write order constraints. LLA also includes a GC execution function. The GC execution function copies valid data in a source block (GC source block) specified by the host 2 to a destination block (GC destination block) specified by the host 2. The GC execution function of the flash storage device 3 determines a position (destination position) in the GC destination block to which the valid data should be written, and copies the valid data in the GC source block to the destination position in the GC destination block.

Figure 2 shows the division of roles between a conventional SSD and a host, and the division of roles between the flash storage device 3 and the host 2 in this embodiment.

The left part of Figure 2 shows the hierarchical structure of the entire computer system, including a conventional SSD and a host running a virtual disk service.

A virtual machine service 101 is executed on the host (server) to provide multiple virtual machines to multiple end users. Each virtual machine on the virtual machine service 101 executes an operating system and user applications 102 used by the corresponding end user.

In addition, in the host (server), multiple virtual disk services 103 corresponding to multiple user applications 102 are executed. Each virtual disk service 103 allocates a portion of the capacity of the storage resources in the conventional SSD as a storage resource (virtual disk) for the corresponding user application 102. In each virtual disk service 103, an application level address conversion is also executed, which converts an application level logical address into a logical address for the SSD, using an application level address conversion table. In addition, in the host, an application level GC 104 is also executed.

The sending of commands from the host (server) to the conventional SSD and the return of command completion responses from the conventional SSD to the host (server) are performed via an I/O queue 200 present in each of the host (server) and the conventional SSD.

A conventional SSD includes a write buffer (WB) 301, a lookup table (LUT) 302, a garbage collection function 303, and a NAND flash memory (NAND flash array) 304. A conventional SSD manages only one lookup table (LUT) 302, and the resources of the NAND flash memory (NAND flash array) 304 are shared by multiple virtual disk services 103.

In this configuration, write amplification increases due to overlapping GCs including the application level GC 104 under the virtual disk service 103 and the garbage collection function 303 (LUT level GC) in the conventional SSD. In addition, in conventional SSDs, an increase in the amount of data written from an end user or a virtual disk service 103 increases the frequency of GCs, which can cause a noisy neighbor problem in which I/O performance for other end users or other virtual disk services 103 deteriorates.

In addition, the existence of overlapping resources, including the application level address translation table in each virtual disk service and the LUT 302 in a conventional SSD, consumes a lot of memory resources.

The right part of Figure 2 shows the hierarchical structure of the entire computer system including the flash storage device 3 and the host 2 of this embodiment.

A virtual machine service 401 is executed on the host (server) 2 to provide multiple virtual machines to multiple end users. An operating system and user applications 402 used by the corresponding end user are executed on each virtual machine on the virtual machine service 401.

In addition, in the host (server) 2, multiple I/O services 403 corresponding to multiple user applications 402 are executed. These I/O services 403 may include an LBA-based block I/O service, a key-value store service, and the like. Each I/O service 403 includes a lookup table (LUT) 411 that manages the mapping between each logical address and each physical address of the flash storage device 3. Here, a logical address means an identifier that can identify the data to be accessed. This logical address may be a logical block address (LBA) that specifies a position in the logical address space, or may be a key (tag) of a key-value store, or may be a hash value of the key.

In an LBA-based block I/O service, a LUT 411 may be used to manage the mapping between each logical address (LBA) and each physical address of the flash storage device 3.

In the key-value store service, a LUT 411 may be used that manages the mapping between each logical address (i.e., a key-like tag) and each physical address indicating the physical memory location in the flash storage device 3 where the data corresponding to these logical addresses (i.e., the key-like tag) is stored. This LUT 411 may manage the correspondence between the tag, the physical address where the data identified by this tag is stored, and the data length of this data.

Each end user can choose which addressing method to use (LBA, key-value store key, etc.).

Each of these LUTs 411 does not convert each logical address from the user application 402 into a respective logical address for the flash storage device 3, but converts each logical address from the user application 402 into a respective physical address for the flash storage device 3. In other words, each of these LUTs 411 is a table in which a table for converting logical addresses for the flash storage device 3 into physical addresses and an application level address conversion table are integrated (merged).

Each I/O service 403 also includes a GC block selection function. The GC block selection function can manage the amount of valid data in each block using a corresponding LUT, thereby selecting a GC source block.

In the host (server) 2, an I/O service 403 may exist for each of the above-mentioned QoS domains. The I/O service 403 belonging to a certain QoS domain may manage the mapping between each of the logical addresses used by the user application 402 in the corresponding QoS domain and each of the block numbers of the block group belonging to the resource group assigned to the corresponding QoS domain.

The sending of commands from the host (server) 2 to the flash storage device 3 and the return of command completion responses and the like from the flash storage device 3 to the host (server) 2 are performed via I/O queues 500 present in both the host (server) 2 and the flash storage device 3. These I/O queues 500 may also be classified into multiple queue groups corresponding to multiple QoS domains.

The flash storage device 3 includes multiple write buffers (WB) 601 corresponding to multiple QoS domains, multiple garbage collection (GC) functions 602 corresponding to multiple QoS domains, and a NAND type flash memory (NAND flash array) 603.

In the configuration shown on the right side of FIG. 2, the upper hierarchical level (host 2) can recognize block boundaries, so that user data can be written to each block taking into account block boundaries/block sizes. In other words, the host 2 can recognize each block of the NAND flash memory (NAND flash array) 603, which makes it possible to perform control such as writing data to an entire block at once, or invalidating all data in a block by deleting or updating it. As a result, it becomes possible to make it difficult for a situation in which valid data and invalid data are mixed in a single block to occur. Therefore, it is possible to reduce the frequency with which GC needs to be executed. By reducing the frequency of GC, write amplification is reduced, which improves the performance of the flash storage device 3 and maximizes the lifespan of the flash storage device 3. In this way, a configuration in which the upper hierarchical level (host 2) can recognize block numbers is useful.

On the other hand, the location within the block where data should be written is determined by the flash storage device 3, not the higher hierarchical level (host 2). Therefore, bad pages can be concealed and page write order constraints can be respected.

Figure 3 shows a modified example of the system configuration in Figure 1.

In FIG. 3, data transfer between multiple hosts 2A and multiple flash storage devices 3 is performed via a network device (here, a network switch 1).

In other words, in the computer system of FIG. 3, the storage management function of the host (server) 2 in FIG. 1 is transferred to the manager 2B, and the front-end function of the host (server) 2 is transferred to multiple hosts (hosts for end-user services) 2A.

The manager 2B manages multiple flash storage devices 3 and allocates the storage resources of these flash storage devices 3 to each host (host for end user services) 2A in response to a request from each host (host for end user services) 2A.

Each host (host for end user services) 2A is connected to one or more end user terminals 61 via a network. Each host (host for end user services) 2A manages a lookup table (LUT), which is the merged logical-physical address conversion table described above. Each host (host for end user services) 2A uses its own LUT to manage only the mapping between each of the logical addresses used by the corresponding end user and each of the physical addresses of the resources assigned to it. This configuration therefore makes it possible to easily scale out the system.

The global FTL of each host 2A has functions such as managing lookup tables (LUTs), achieving high availability, QoS control, and GC block selection functions.

The manager 2B is a dedicated device (computer) for managing multiple flash storage devices 3. The manager 2B has a global resource reservation function that reserves storage resources for the capacity requested by each host 2A. In addition, the manager 2B has a wear monitoring function for monitoring the wear level of each flash storage device 3, a NAND resource allocation function for allocating reserved storage resources (NAND resources) to each host 2A, a QoS control function, a global clock management function, and the like.

The low-level abstraction (LLA) of each flash storage device 3 has functions such as concealing bad pages, observing page write order constraints, managing write buffers, and executing GC.

According to the system configuration of FIG. 3, management of each flash storage device 3 is performed by the manager 2B, so each host 2A only needs to send an I/O request to one or more flash storage devices 3 assigned to it, and receive a response from the flash storage device 3. In other words, data transfer between multiple hosts 2A and multiple flash storage devices 3 is performed only via the network switch 1, and the manager 2B is not involved in this data transfer. Also, as described above, the contents of the LUTs managed by each host 2A are independent of each other. Therefore, the number of hosts 2A can be easily increased, making it possible to realize a scale-out system configuration.

Figure 4 shows an example configuration of a flash storage device 3.

The flash storage device 3 includes a controller 4 and a non-volatile memory (NAND flash memory) 5. The flash storage device 3 may also include a random access memory, for example, a DRAM 6.

The NAND flash memory 5 includes a memory cell array including a plurality of memory cells arranged in a matrix. The NAND flash memory 5 may be a two-dimensional NAND flash memory or a three-dimensional NAND flash memory.

The memory cell array of the NAND flash memory 5 includes multiple blocks BLK0 to BLKm-1. Each of the blocks BLK0 to BLKm-1 is organized into multiple pages (here, pages P0 to Pn-1). The blocks BLK0 to BLKm-1 function as erase units. A block may also be referred to as an "erase block," a "physical block," or a "physical erase block." Each of the pages P0 to Pn-1 includes multiple memory cells connected to the same word line. The pages P0 to Pn-1 are the units of data write and read operations.

The controller 4 is electrically connected to the NAND flash memory 5, which is a non-volatile memory, via a NAND interface 13 such as Toggle or an Open NAND Flash Interface (ONFI). The controller 4 is a memory controller (control circuit) configured to control the NAND flash memory 5.

As shown in FIG. 5, the NAND flash memory 5 includes a plurality of NAND flash memory dies. Each NAND flash memory die is a non-volatile memory die including a memory cell array including a plurality of blocks BLK and a peripheral circuit that controls the memory cell array. Each NAND flash memory die can operate independently. For this reason, the NAND flash memory die functions as a parallel operation unit. The NAND flash memory die is also called a "NAND flash memory chip" or a "non-volatile memory chip". In FIG. 5, 16 channels Ch1, Ch2, ... Ch16 are connected to the NAND interface 13, and the same number of NAND flash memory dies (e.g., two dies per channel) are connected to each of these channels Ch1, Ch2, ... Ch16. Each channel includes a communication line (memory bus) for communicating with the corresponding NAND flash memory die.

The controller 4 controls the NAND flash memory dies #1 to #32 via channels Ch1, Ch2, ... Ch16. The controller 4 can drive channels Ch1, Ch2, ... Ch16 simultaneously.

The 16 NAND flash memory dies #1 to #16 connected to channels Ch1 to Ch16 may be organized as a first bank, and the remaining 16 NAND flash memory dies #17 to #32 connected to channels Ch1 to Ch16 may be organized as a second bank. The bank functions as a unit for operating multiple memory modules in parallel by bank interleaving. In the configuration example of FIG. 5, a maximum of 32 NAND flash memory dies can be operated in parallel by using 16 channels and bank interleaving using two banks.

In this embodiment, the controller 4 may manage multiple blocks (hereinafter referred to as superblocks), each of which is composed of multiple blocks BLK, and may perform erase operations in units of superblocks.

Although not limited to this, the superblock may include a total of 32 blocks BLK selected one by one from the NAND flash memory dies #1 to #32. Each of the NAND flash memory dies #1 to #32 may have a multi-plane configuration. For example, if each of the NAND flash memory dies #1 to #32 has a multi-plane configuration including two planes, one superblock may include a total of 64 blocks BLK selected one by one from the 64 planes corresponding to the NAND flash memory dies #1 to #32. FIG. 6 illustrates a case in which one superblock SB is composed of a total of 32 blocks BLK (blocks BLK surrounded by a thick frame in FIG. 5) selected one by one from the NAND flash memory dies #1 to #32.

As shown in FIG. 4, the controller 4 includes a host interface 11, a CPU 12, a NAND interface 13, and a DRAM interface 14. The CPU 12, the NAND interface 13, and the DRAM interface 14 are interconnected via a bus 10.

The host interface 11 is a host interface circuit configured to communicate with the host 2. The host interface 11 may be, for example, a PCIe controller (NVMe controller). The host interface 11 receives various requests (commands) from the host 2. These requests (commands) include write requests (write commands), read requests (read commands), and various other requests (commands).

The CPU 12 is a processor configured to control the host interface 11, the NAND interface 13, and the DRAM interface 14. In response to power-on of the flash storage device 3, the CPU 12 loads a control program (firmware) from the NAND flash memory 5 or a ROM (not shown) into the DRAM 6, and executes this firmware to perform various processes. The firmware may be loaded onto an SRAM (not shown) in the controller 4. The CPU 12 can execute command processing and the like for processing various commands from the host 2. The operation of the CPU 12 is controlled by the above-mentioned firmware executed by the CPU 12. Some or all of the command processing may be executed by dedicated hardware in the controller 4.

The CPU 12 can function as a write operation control unit 21, a read operation control unit 22, and a GC operation control unit 23. In these write operation control unit 21, read operation control unit 22, and GC operation control unit 23, an application program interface (API) is implemented to realize the system configuration shown in the right part of FIG. 2.

The write operation control unit 21 receives a write request (write command) that specifies a block number and a logical address from the host 2. The logical address is an identifier that can identify the data (user data) to be written, and may be, for example, an LBA, or a tag such as a key in a key-value store, or a hash value of the key. The block number is an identifier that specifies the block to which this data is to be written. As the block number, various values that can uniquely identify any one of multiple blocks may be used. The block specified by the block number may be a physical block or the above-mentioned superblock. When a write command is received, the write operation control unit 21 first determines a position (write destination position) in the block (write destination block) having the specified block number to which the data from the host 2 should be written. Next, the write operation control unit 21 writes the data (write data) from the host 2 to the write destination position of the write destination block. In this case, the write operation control unit 21 can write not only the data from the host 2 but also both the data and the logical address of the data to the write destination block.

Then, the write operation control unit 21 notifies the host 2 of the physical address within the block that indicates the above-mentioned write destination position in the write destination block. This physical address within the block is represented by an offset within the block that indicates the write destination position within the write destination block.

In this case, the offset within the block indicates the offset from the beginning of the destination block to the destination position, that is, the offset of the destination position relative to the beginning of the destination block. The size of the offset from the beginning of the destination block to the destination position is indicated as a multiple of a granularity (Grain) having a size different from the page size. The granularity (Grain) is the access unit described above. The maximum value of the granularity (Grain) size is limited to the block size. In other words, the offset within the block indicates the offset from the beginning of the destination block to the destination position as a multiple of a granularity having a size different from the page size.

The granularity may have a size smaller than the page size. For example, if the page size is 16 Kbytes, the granularity may have a size of 4 Kbytes. In this case, in one block, multiple offset positions are defined, each of which is 4 Kbytes in size. The intra-block offset corresponding to the first offset position in the block is, for example, 0, the intra-block offset corresponding to the next offset position in the block is, for example, 1, and the intra-block offset corresponding to the next offset position in the block is, for example, 2.

Alternatively, the granularity may have a size larger than the page size. For example, the granularity may be several times the size of the page size. If the page size is 16 Kbytes, the granularity may be 32 Kbytes in size.

In this way, the write operation control unit 21 determines by itself the write destination location within the block having the block number from the host 2, and writes the write data from the host 2 to this write destination location within this block. The write operation control unit 21 then notifies the host 2 of the physical address within the block (offset within the block) indicating this write destination location as a response (return value) corresponding to the write request. Alternatively, the write operation control unit 21 may notify the host 2 of a set of a logical address, block number, and physical address within the block (offset within the block) rather than notifying the host 2 of only the physical address within the block (offset within the block).

Therefore, the flash storage device 3 can hide page write order constraints, bad pages, page sizes, etc., while allowing the host 2 to handle block numbers.

As a result, host 2 can recognize block boundaries but can manage which user data resides in which block number without being aware of page write order constraints, bad pages, or page sizes.

When the read operation control unit 22 receives a read request (read command) from the host 2 that specifies a physical address (i.e., a block number and an offset within the block), it reads data from the physical storage location of the read target in the block to be read, based on the block number and offset within the block. The block to be read is identified by the block number. The physical storage location of the read target in this block is identified by the offset within the block. By using this offset within the block, the host 2 does not need to handle the different page sizes for each generation of NAND flash memory.

To obtain the physical memory location of the read target, the read operation control unit 22 may first divide this intrablock offset by the number of granularities representing the page size (if the page size is 16 Kbytes and the granularity (Grain) is 4 Kbytes, the number of granularities representing the page size is 4), and then determine the quotient and remainder obtained by this division as the page number and intrapage offset of the read target, respectively.

When the GC operation control unit 23 receives from the host 2 a GC control command specifying a source block number (GC source block number) and a destination block number (GC destination block number) for garbage collection in the NAND flash memory 5, it selects a block having the specified source block number and a block having the specified destination block number as the source block (GC source block) and the destination block (GC destination block) from among the multiple blocks in the NAND flash memory 5. The GC operation control unit 23 determines a destination position in the GC destination block to which valid data stored in the selected GC source block should be written, and copies the valid data to the destination position in the GC destination block.

Then, the GC operation control unit 23 notifies the host 2 of the logical address of the valid data, the copy destination block number, and the physical address within the block (offset within the block) indicating the copy destination position within the GC destination block.

Management of valid data/invalid data may be performed using a block management table 32. This block management table 32 may exist for each block, for example. In the block management table 32 corresponding to a certain block, a bitmap flag indicating whether each piece of data in this block is valid/invalid is stored. Here, valid data means data that is linked to a logical address as the latest data and has the potential to be read by the host 2 later. Invalid data means data that has no potential to be read by the host 2 any more. For example, data associated with a certain logical address is valid data, and data that is not associated with any logical address is invalid data.

As described above, the GC operation control unit 23 determines a position (destination position) in the destination block (GC destination block) to which valid data stored in the source block (GC source block) should be written, and copies the valid data to this determined position (destination position) in the destination block (GC destination block). In this case, the GC operation control unit 23 may copy both the valid data and the logical address of the valid data to the destination block (GC destination block).

In this embodiment, as described above, the write operation control unit 21 can write both the data from the host 2 (write data) and the logical address from the host 2 to the destination block. Therefore, the GC operation control unit 23 can easily obtain the logical address of each piece of data in the source block (GC source block) from this source block (GC source block), and can easily notify the host 2 of the logical address of the copied valid data.

The NAND interface 13 is a memory control circuit configured to control the NAND flash memory 5 under the control of the CPU 12. The DRAM interface 14 is a DRAM control circuit configured to control the DRAM 6 under the control of the CPU 12. A part of the memory area of the DRAM 6 is used for storing a write buffer (WB) 31. Another part of the memory area of the DRAM 6 is used for storing a block management table 32. The write buffer (WB) 31 and the block management table 32 may be stored in an SRAM (not shown) in the controller 4.

Figure 7 shows a data write operation in which the host 2 specifies a logical address and a block number and the flash storage device 3 determines a physical address within the block (offset within the block), and a data read operation in which the host 2 specifies a block number and a physical address within the block (offset within the block).

The data write operation is performed as follows:

(1) When the write processing unit 412 of the host 2 needs to write data (write data) to the flash storage device 3, the write processing unit 412 may request the flash storage device 3 to allocate a free block. The controller 4 of the flash storage device 3 includes a block allocation unit 701 that manages the free block group of the NAND flash memory 5. When the block allocation unit 701 receives this request (block allocation request) from the write processing unit 412, the block allocation unit 701 allocates one free block from the free block group to the host 2 and notifies the host 2 of the block number (BLK#) of the allocated block.

Alternatively, in a configuration in which the write processing unit 412 manages the free block group, the write processing unit 412 may itself select the destination block to write to.

(2) The write processing unit 412 sends a write request to the flash storage device 3, specifying the logical address (e.g., LBA) corresponding to the write data and the block number (BLK#) of the destination block.

(3) The controller 4 of the flash storage device 3 includes a page allocation unit 702 that allocates pages for writing data. When the page allocation unit 702 receives a write request, the page allocation unit 702 determines an intra-block physical address (intra-block PBA) that indicates a write destination position within a block (destination block) having a block number specified by the write request. The intra-block physical address (intra-block PBA) can be expressed by the intra-block offset (also simply referred to as an offset) described above. The controller 4 writes the write data from the host 2 to the write destination position within the destination block based on the block number and intra-block physical address (intra-block PBA) specified by the write request.

(4) The controller 4 notifies the host 2 of the in-block physical address (in-block PBA) indicating the write destination location as a response to the write request. Alternatively, the controller 4 may notify the host 2 of a set of the logical address (LBA) corresponding to the write data, the block number (BLK#) of the write destination block, and the in-block PBA (offset) indicating the write destination location as a response to the write request. In other words, the controller notifies the host 2 of either the in-block physical address or a set of the logical address, block number, and in-block physical address. In the host 2, the LUT 411 is updated so that the physical address (block number, in-block physical address (in-block offset)) indicating the physical memory location where the write data is written is mapped to the logical address of this write data.

The data read operation is performed as follows:

(1)'When the host 2 needs to read data from the flash storage device 3, the host 2 refers to the LUT 411 and obtains from the LUT 411 the physical address (block number, physical address within the block (offset within the block)) that corresponds to the logical address of the data to be read.

(2)' The host 2 sends a read request to the flash storage device 3, specifying the obtained block number and physical address within the block (offset within the block). When the controller 4 of the flash storage device 3 receives this read request from the host 2, the controller 4 identifies the block to be read and the physical memory location of the read target based on the block number and the physical address within the block, and reads data from the physical memory location of the read target within the block to be read.

Figure 8 shows a write command applied to flash storage device 3.

The write command is a command that requests writing data to the flash storage device 3. This write command may include a command ID, a block number BLK#, a logical address, a length, etc.

The command ID is an ID (command code) that indicates that this command is a write command, and the write command includes a command ID for the write command.

The block number BLK# is an identifier (block address) that uniquely identifies the block to which data should be written.

The logical address is an identifier for identifying the write data to be written. As described above, this logical address may be an LBA, a key in a key-value store, or a hash value of the key. If the logical address is an LBA, the logical address (start LBA) included in the write command indicates the logical location (first logical location) where the write data should be written.

The length indicates the length of the write data to be written. This length (data length) may be specified by the number of grains, the number of LBAs, or the size may be specified by bytes.

When a write command is received from the host 2, the controller 4 determines the write destination location within the block having the block number specified by the write command. This write destination location is determined taking into consideration page write order constraints and bad pages, etc. Then, the controller 4 writes the data from the host 2 to this write destination location within the block having the block number specified by the write command.

Figure 9 shows the response to the write command in Figure 8.

This response includes the physical address within the block and the length. The physical address within the block indicates the location (physical memory location) within the block where the data was written. The physical address within the block can be specified by the offset within the block, as described above. The length indicates the length of the written data. This length (data length) may be specified by the number of grains, the number of LBAs, or the size may be specified by bytes.

Alternatively, this response may further include a logical address and a block number in addition to the physical address and length within the block. The logical address is the logical address included in the write command in FIG. 8. The block number is the logical address included in the write command in FIG. 8.

Figure 10 shows the Trim command applied to flash storage device 3.

This Trim command includes a block number and a physical address within the block (offset within the block) that indicate the physical memory location where the data to be invalidated is stored. In other words, this Trim command can specify a physical address rather than a logical address such as an LBA. This Trim command includes a command ID, a physical address, and a length.

The command ID is an ID (command code) that indicates that this command is a Trim command, and the Trim command includes a command ID for the Trim command.

The physical address indicates the first physical memory location where the data to be invalidated is stored. In this embodiment, this physical address is specified by a combination of a block number and an offset (offset within the block).

The length indicates the length of the data to be invalidated. This length (data length) may be specified by the number of grains or by bytes.

The controller 4 manages flags (bitmap flags) indicating the validity/invalidity of each piece of data contained in each of the multiple blocks using the block management table 32. When a Trim command including a block number and offset (offset within block) indicating the physical storage location where the data to be invalidated is stored is received from the host 2, the controller 4 updates the block management table 32 and changes the flag (bitmap flag) corresponding to the data at the physical storage location corresponding to the block number and offset within block included in the Trim command to a value indicating invalidity.

Figure 11 shows the offset within a block that defines the physical address within the block.

The block number specifies a block BLK. Each block BLK contains multiple pages (here, page 0 to page n), as shown in Figure 11.

When the page size (user data storage area of each page) is 16 KB and the granularity is 4 KB, this block BLK is logically divided into 4 x (n + 1) areas.

Offset +0 points to the first 4KB area of page 0, offset +1 points to the second 4KB area of page 0, offset +2 points to the third 4KB area of page 0, and offset +3 points to the fourth 4KB area of page 0.

Offset +4 points to the first 4KB area on page 1, offset +5 points to the second 4KB area on page 1, offset +6 points to the third 4KB area on page 1, and offset +7 points to the fourth 4KB area on page 1.

Figure 12 shows the write operation performed in response to a write command.

Now, assume that block BLK#1 is assigned as the write destination block. The controller 4 writes data to block BLK#1 in units of pages in the order of page 0, page 1, page 2, ..., page n.

In FIG. 11, it is assumed that a write command specifying the block number (=BLK#1), logical address (LBAx), and length (=4) is received from the host 2 when 16K bytes of data have already been written to page 0 of block BLK#1. The controller 4 determines page 1 of block BLK#1 as the write destination location, and writes the 16K bytes of write data received from the host 2 to page 1 of block BLK#1. The controller 4 then returns the offset (offset within block) and length to the host 2 as a response to this write command. In this case, the offset (offset within block) is +5, and the length is 4. Alternatively, the controller 4 may return the logical address, block number, offset (offset within block), and length to the host 2 as a response to this write command. In this case, the logical address is LBAx, the block number is BLK#1, the offset (offset within block) is +5, and the length is 4.

Figure 13 shows a write operation that skips a bad page.

In FIG. 13, it is assumed that a write command specifying the block number (=BLK#1), logical address (LBAx+1), and length (=4) is received from the host 2 when data has already been written to page 0 and page 1 of block BLK#1. If page 2 of block BLK#1 is a defective page, the controller 4 determines page 3 of block BLK#1 as the write destination location and writes 16K bytes of write data received from the host 2 to page 3 of block BLK#1. The controller 4 then returns the offset (offset within block) and length to the host 2 as a response to this write command. In this case, the offset (offset within block) is +12 and the length is 4. Alternatively, the controller 4 may return the logical address, block number, offset (offset within block), and length to the host 2 as a response to this write command. In this case, the logical address is LBAx+1, the block number is BLK#1, the offset (offset within block) is +12, and the length is 4.

Figure 14 shows another example of a write operation that skips a bad page.

In FIG. 14, it is assumed that data is written across two pages, one of which is a defective page. Assume that data has already been written to page 0 and page 1 of block BLK#2, and that 8 KB of unwritten write data remains in the write buffer 31. In this state, if a write command specifying the block number (=BLK#2), logical address (LBAy), and length (=6) is received, the controller 4 uses the unwritten 8 KB of write data and the first 8 KB of write data in the 24 KB of write data newly received from the host 2 to prepare 16 KB of write data corresponding to the page size. The controller 4 then writes this prepared 16 KB of write data to page 2 of block BLK#2.

If the next page 3 of block BLK#2 is a defective page, the controller 4 determines page 4 of block BLK#2 as the next write location, and writes the remaining 16 KB of write data in the 24 KB of write data received from the host 2 to page 4 of block BLK#2.

The controller 4 then returns two offsets (offsets within a block) and two lengths to the host 2 as a response to this write command. In this case, this response may include offset (=+10), length (=2), offset (=+16), and length (=4). Alternatively, the controller 4 may return LBAy, block number (=BLK#2), offset (=+10), length (=2), block number (=BLK#2), offset (=+16), and length (=4) to the host 2 as a response to this write command.

Figures 15 and 16 show the operation of writing a logical address and data pair to a page in a block.

In each block, each page may include a user data area for storing user data and a redundant area for storing management data. The page size is 16KB+alpha.

The controller 4 writes both the 4 KB user data and the logical address (e.g., LBA) corresponding to the 4 KB user data to the destination block BLK. In this case, as shown in FIG. 15, four data sets, each including an LBA and 4 KB user data, may be written to the same page. The offset within the block may indicate a set boundary.

Alternatively, as shown in FIG. 16, four 4 KB user data may be written to the user data area in a page, and four LBAs corresponding to these four 4 KB user data may be written to the redundant area in the page.

Figure 17 shows the relationship between block number and offset (offset within block) when superblocks are used. In the following, offset within block is also referred to simply as offset.

To simplify the illustration, it is assumed here that one superblock SB#1 is made up of four blocks BLK#11, BLK#21, BLK#31, and BLK#41. The controller 4 writes data in the following order: page 0 of block BLK#11, page 0 of block BLK#21, page 0 of block BLK#31, page 0 of block BLK#41, page 1 of block BLK#11, page 1 of block BLK#21, page 1 of block BLK#31, page 1 of block BLK#41, and so on.

Offset +0 indicates the first 4KB area of page 0 of block BLK#11, offset +1 indicates the second 4KB area of page 0 of block BLK#11, offset +2 indicates the third 4KB area of page 0 of block BLK#11, and offset +3 indicates the fourth 4KB area of page 0 of block BLK#11.

Offset +4 indicates the first 4KB area of page 0 of block BLK#21, offset +5 indicates the second 4KB area of page 0 of block BLK#21, offset +6 indicates the third 4KB area of page 0 of block BLK#21, and offset +7 indicates the fourth 4KB area of page 0 of block BLK#21.

Similarly, offset +12 points to the first 4KB area of page 0 of block BLK#41, offset +13 points to the second 4KB area of page 0 of block BLK#41, offset +14 points to the third 4KB area of page 0 of block BLK#41, and offset +15 points to the fourth 4KB area of page 0 of block BLK#41.

Offset +16 indicates the first 4KB area of page 1 of block BLK#11, offset +17 indicates the second 4KB area of page 1 of block BLK#11, offset +18 indicates the third 4KB area of page 1 of block BLK#11, and offset +19 indicates the fourth 4KB area of page 1 of block BLK#11.

Offset +20 indicates the first 4KB area of page 1 of block BLK#21, offset +21 indicates the second 4KB area of page 1 of block BLK#21, offset +22 indicates the third 4KB area of page 1 of block BLK#21, and offset +23 indicates the fourth 4KB area of page 1 of block BLK#21.

Similarly, offset +28 indicates the first 4KB region of page 1 of block BLK#41, offset +29 indicates the second 4KB region of page 1 of block BLK#41, offset +30 indicates the third 4KB region of page 1 of block BLK#41, and offset +31 indicates the fourth 4KB region of page 1 of block BLK#41.

Figure 18 shows a get maximum block number command applied to flash storage device 3.

The get maximum block number command is a command for obtaining the maximum block number from the flash storage device 3. The host 2 can recognize the maximum block number indicating the number of blocks contained in the flash storage device 3 by sending the get maximum block number command to the flash storage device 3. The get maximum block number command includes a command ID for the get maximum block number command, but does not include any parameters.

Figure 19 shows the response to the Get Maximum Block Number command.

When the flash storage device 3 receives the maximum block number get command from the host 2, it returns the response shown in FIG. 19 to the host 2. This response includes a parameter indicating the maximum block number (i.e., the total number of available blocks contained in the flash storage device 3).

Figure 20 shows a get block size command applied to flash storage device 3.

The get block size command is a command for obtaining the block size from the flash storage device 3. By sending a get block size command to the flash storage device 3, the host 2 can recognize the block size of the NAND flash memory 5 included in the flash storage device 3.

In another embodiment, the get block size command may include a parameter that specifies a block number. When the flash storage device 3 receives a get block size command that specifies a block number from the host 2, the flash storage device 3 returns the block size of the block having this block number to the host 2. This allows the host 2 to recognize the block size of each individual block, even if the block sizes of the blocks included in the NAND flash memory 5 are not uniform.

Figure 21 shows the response to the get block size command.

When the flash storage device 3 receives a get block size command from the host 2, it returns the block size (the common block size for each block included in the NAND flash memory 5) to the host 2. In this case, if a block number is specified by the get block size command, the flash storage device 3 returns the block size of the block having this block number to the host 2, as described above.

Figure 22 shows a block allocate command applied to flash storage device 3.

The block allocate command is a command (block allocation request) that requests the flash storage device 3 to allocate a block (free block). By sending a block allocate command to the flash storage device 3, the host 2 requests the flash storage device 3 to allocate a free block, and is thereby able to obtain the block number (the block number of the allocated free block).

In cases where the flash storage device 3 manages the free blocks using a free block list and the host 2 does not manage the free blocks, the host 2 requests the flash storage device 3 to allocate a free block, thereby obtaining a block number. On the other hand, in cases where the host 2 manages the free blocks, the host 2 can select one of the free blocks by itself, and therefore does not need to send a block allocate command to the flash storage device 3.

Figure 23 shows the response to a block allocate command.

When a block allocate command is received from the host 2, the flash storage device 3 selects a free block to be allocated to the host 2 from the free block list, and returns a response including the block number of the selected free block to the host 2.

Figure 24 shows the block information acquisition process executed by the host 2 and the flash storage device 3.

When the host 2 starts using the flash storage device 3, the host 2 first sends a get maximum block number command to the flash storage device 3. The controller of the flash storage device 3 returns the maximum block number to the host 2. The maximum block number indicates the total number of available blocks. Note that in cases where the above-mentioned super blocks are used, the maximum block number may also indicate the total number of available super blocks.

Then, the host 2 sends a get block size command to the flash storage device 3 to obtain the block size. In this case, the host 2 may send a get block size command specifying block number 1, a get block size command specifying block number 2, a get block size command specifying block number 3, ... to the flash storage device 3 to obtain the block size of each of all blocks individually.

This block information acquisition process allows host 2 to recognize the number of available blocks and the block size of each block.

Figure 25 shows the sequence of a write process performed by the host 2 and the flash storage device 3.

The host 2 first selects a block (free block) to be used for writing, or requests the flash storage device 3 to allocate a free block by sending a block allocate command to the flash storage device 3. The host 2 then sends a write command to the flash storage device 3, including the block number BLK# of the block selected by the host 2 (or the block number BLK# of a free block allocated by the flash storage device 3), the logical address (LBA), and the length (step S20).

When the controller 4 of the flash storage device 3 receives this write command, the controller 4 determines the destination position within the block having this block number BLK# (destination block BLK#) to which the write data from the host 2 should be written, and writes the write data to the destination position of the destination block BLK# (step S11). In step S11, the controller 4 may write both the logical address (here, LBA) and the write data to the destination block.

The controller 4 updates the block management table 32 corresponding to the destination block BLK#, and changes the bitmap flag corresponding to the written data (i.e., the bitmap flag corresponding to the offset (offset within the block) at which this data was written) from 0 to 1 (step S12).

For example, as shown in Figure 26, assume that 16K byte update data with a starting LBA of LBAx is written to the physical memory location corresponding to offsets +4 to +7 of block BLK#1. In this case, as shown in Figure 27, in the block management table for block BLK#1, each of the bitmap flags corresponding to offsets +4 to +7 is changed from 0 to 1.

Then, as shown in FIG. 25, the controller 4 returns a response to this write command to the host 2 (step S13). This response includes at least the offset (offset within the block) to which this data was written.

When the host 2 receives this response, the host 2 updates the LUT 411 managed by the host 2 and maps a physical address to each logical address corresponding to the written write data. As shown in FIG. 28, the LUT 411 includes multiple entries corresponding to multiple logical addresses (e.g., LBAs). An entry corresponding to a certain logical address (e.g., a certain LBA) stores a physical address PBA indicating the location (physical memory location) in the NAND flash memory 5 where the data corresponding to this LBA is stored, that is, the block number and offset (offset within the block). As shown in FIG. 26, if 16K byte update data with a starting LBA of LBAx is written to the physical memory location corresponding to offsets +4 to +7 of block BLK#1, as shown in FIG. 28, LUT411 is updated so that BLK#1, offset +4 is stored in the entry corresponding to LBAx, BLK#1, offset +5 is stored in the entry corresponding to LBAx+1, BLK#1, offset +6 is stored in the entry corresponding to LBAx+2, and BLK#1, offset +7 is stored in the entry corresponding to LBAx+3.

As shown in FIG. 25, the host 2 then sends a Trim command to the flash storage device 3 to invalidate the previous data that has become unnecessary due to the writing of the update data. As shown in FIG. 26, if the previous data is stored at positions corresponding to offset +0, offset +1, offset +2, and offset +3 of block BLK#0, as shown in FIG. 29, a Trim command specifying the block number (=BLK#0), offset (=+0), and length (=4) is sent from the host 2 to the flash storage device 3. The controller 4 of the flash storage device 3 updates the block management table 32 in response to this Trim command (FIG. 25, step S14). In step S15, as shown in FIG. 29, the bitmap flags corresponding to offsets +0 to +3 in the block management table for block BLK#0 are changed from 1 to 0.

Figure 30 shows a read command applied to flash storage device 3.

The read command is a command that requests the flash storage device 3 to read data. This read command includes a command ID, a physical address PBA, a length, and a destination pointer.

The command ID is an ID (command code) that indicates that this command is a read command, and the read command includes a command ID for the read command.

The physical address PBA indicates the first physical memory location from which data is to be read. The physical address PBA is specified by the block number and offset (offset within the block).

The length indicates the length of the data to be read. This data length can be specified by the number of grains.

The destination pointer indicates the location in memory in host 2 to which the read data should be transferred.

A single read command can specify multiple pairs of physical address PBA (block number, offset) and length.

Figure 31 shows the read operation.

Here, it is assumed that a read command specifying the block number (=BLK#2), offset (=+5), and length (=3) has been received from the host 2. The controller 4 of the flash storage device 3 reads data d1 to d3 from BLK#2 based on the block number (=BLK#2), offset (=+5), and length (=3). In this case, the controller 4 reads one page's worth of data from page 1 of BLK#2, and extracts data d1 to d3 from this read data. The controller 4 then transfers data d1 to d3 to the host memory specified by the destination pointer.

Figure 32 shows the operation of reading data portions stored in different physical storage locations in response to a read command from host 2.

Here, it is assumed that a read command specifying the block number (=BLK#2), offset (=+10), length (=2), block number (=BLK#2), offset (=+16), and length (=4) is received from the host 2. The controller 4 of the flash storage device 3 reads one page's worth of data from page 2 of BLK#2 based on the block number (=BLK#2), offset (=+10), and length (=2), and extracts data d1 to data d2 from this read data. Next, the controller 4 reads one page's worth of data (data d3 to data d6) from page 4 of BLK#2 based on the block number (=BLK#2), offset (=+16), and length (=4). The controller 4 then transfers the read data of length (=6) obtained by combining data d1 to data d2 and data d3 to data d6 to the host memory specified by the transfer destination pointer in the read command.

This allows the data portion to be read from a separate physical memory location without causing a read error, even if a bad page exists in a block. Also, even if data is written across two blocks, this data can be read by issuing a single read command.

Figure 33 shows the sequence of a read process performed by the host 2 and the flash storage device 3.

The host 2 refers to the LUT 411 managed by the host 2 and converts the logical address included in the read request from the user application into a block number and offset. The host 2 then sends a read command to the flash storage device 3 that specifies the block number, offset, and length.

When the controller 4 of the flash storage device 3 receives a read command from the host 2, the controller 4 determines the block corresponding to the block number specified by the read command as the block to be read, and determines the page to be read based on the offset specified by the read command (step S31). In step S31, the controller 4 may first divide the offset specified by the read command by the granularity number representing the page size (here, 4). The controller 4 may then determine the quotient and remainder obtained by this division as the page number to be read and the offset position within the page to be read, respectively.

The controller 4 reads the data defined by the block number, offset, and length from the NAND flash memory 5 (step S32) and transmits this read data to the host 2.

Figure 34 shows the GC control commands applied to flash storage device 3.

The GC control command is used to notify the flash storage device 3 of the GC source block number and the GC destination block number. The host 2 manages the amount of valid data/invalid data for each block, and can select some blocks with a smaller amount of valid data as GC source blocks. The host 2 also manages a free block list, and can select some free blocks as GC destination blocks. This GC control command may include a command ID, a GC source block number, a GC destination block number, etc.

The command ID is an ID (command code) that indicates that this command is a GC control command, and the GC control command includes a command ID for the GC control command.

The GC source block number is a block number that indicates a GC source block. The host 2 can specify which block should be the GC source block. The host 2 may set multiple GC source block numbers in one GC control command.

The GC destination block number is a block number that indicates a GC destination block. The host 2 can specify which block should be the GC destination block. The host 2 may set multiple GC destination block numbers in one GC control command.

Figure 35 shows the callback command for GC.

The GC callback command is used to notify the host 2 of the logical address of the valid data copied by the GC and the block number and offset indicating the destination location of this valid data.

The GC callback command may include a command ID, a logical address, a length, and a destination physical address.

The command ID is an ID (command code) that indicates that this command is a GC callback command, and the GC callback command contains a command ID for the GC callback command.

The logical address indicates the logical address of the valid data copied by GC from the GC source block to the GC destination block.

Length indicates the length of the copied data. This data length may be specified by the number of grains.

The destination physical address indicates the location within the GC destination block where the valid data has been copied. The destination physical address is specified by the block number and offset (offset within the block).

Figure 36 shows the procedure for garbage collection (GC) operations.

For example, when the number of remaining free blocks included in the free block list managed by the host 2 falls below a threshold, the host 2 selects a GC source block and a GC destination block, and transmits a GC control command specifying the selected GC source block and the selected GC destination block to the flash storage device 3 (step S41). Alternatively, in a configuration in which the write processing unit 412 manages the free block group, when the number of remaining free blocks falls below a threshold, the write processing unit 412 may notify the host 2 of this, and the host 2 receiving the notification may select blocks and transmit a GC control command.

Upon receiving this GC control command, the controller 4 of the flash storage device 3 executes a data copy operation including an operation of determining a position (destination position) in the GC destination block to which the valid data in the GC source block should be written, and an operation of copying the valid data in the GC source block to the destination position in the GC destination block (step S51). In step S51, the controller 4 copies not only the valid data in the GC source block (source block), but also both the valid data and the logical address corresponding to the valid data from the GC source block (source block) to the GC destination block (destination block). This makes it possible to hold pairs of data and logical addresses in the GC destination block (destination block).

In addition, in step S51, the data copy operation is repeatedly executed until copying of all valid data in the GC source block is completed. If multiple GC source blocks are specified by the GC control command, the data copy operation is repeatedly executed until copying of all valid data in all GC source blocks is completed.

Then, the controller 4 notifies the host 2 of the logical address (LBA) of each valid data item copied, the destination physical address indicating the destination location of the valid data, etc., using a GC callback command (step S52). The destination physical address corresponding to a certain valid data item is represented by the block number of the destination block (GC destination block) to which the valid data is copied, and the intra-block physical address (intra-block offset) indicating the physical storage location within the destination block to which the valid data is copied.

When the host 2 receives this GC callback command, the host 2 updates the LUT 411 managed by the host 2 and maps the destination physical address (block number, offset within block) to the logical address corresponding to each valid data that was copied (step S42).

Figure 37 shows an example of a data copy operation performed for GC.

In FIG. 37, it is assumed that valid data (LBA=10) stored at a position corresponding to offset +4 in the GC source block (here, block BLK#50) is copied to a position corresponding to offset +0 in the GC destination block (here, block BLK#100), and valid data (LBA=20) stored at a position corresponding to offset +10 in the GC source block (here, block BLK#50) is copied to a position corresponding to offset +1 in the GC destination block (here, block BLK#100). In this case, the controller 4 notifies the host of {LBA10, BLK#100, offset (=+0), LBA20, BLK#100, offset (=+1)} (GC callback processing).

Figure 38 shows the contents of LUT 411 of host 2 that are updated based on the results of the data copy operation in Figure 37.

In this LUT411, the block number and offset corresponding to LBA10 are updated from BLK#50, offset (=+4) to BLK#100, offset (=+0). Similarly, the block number and offset corresponding to LBA20 are updated from BLK#50, offset (=+10) to BLK#100, offset (=+1).

After the LUT 411 is updated, the host 2 may send a Trim command specifying BLK#50 and an offset (=+4) to the flash storage device 3 to invalidate the data stored at the location corresponding to the offset (=+4) of BLK#50. Furthermore, the host 2 may send a Trim command specifying BLK#50 and an offset (=+10) to the flash storage device 3 to invalidate the data stored at the location corresponding to the offset (=+10) of BLK#50. Alternatively, the host 2 may not send a Trim command, and the controller 4 may update the block management table 32 as part of the GC process to invalidate this data.

As described above, according to this embodiment, when a write request specifying a first logical address and a first block number is received from the host 2, the controller 4 of the flash storage device 3 determines a position (destination position) in the block (destination block) having the first block number to which data from the host 2 should be written, writes the data from the host 2 to the destination position in the destination block, and notifies the host 2 of either a physical address in the first block indicating the first position, or a combination of the first logical address, the first block number, and a physical address in the first block.

Therefore, a configuration can be realized in which the host 2 handles the block number, and the flash storage device 3 determines the write destination position (offset within the block) within the block having the block number specified by the host 2, taking into account page write order constraints/bad pages, etc. By the host 2 handling the block number, it is possible to realize merging of the application level address conversion table of the upper layer (host 2) with the LUT level address conversion table of the conventional SSD. In addition, the flash storage device 3 can control the NAND flash memory 5 while taking into account the characteristics/constraints of the NAND flash memory 5. Furthermore, since the host 2 can recognize block boundaries, it is possible to write user data to each block while taking into account the block boundaries/block size. This allows the host 2 to control the data in the same block to be invalidated all at once by data update, etc., so that it is possible to reduce the frequency with which GC is executed. As a result, write amplification is reduced, and the performance of the flash storage device 3 can be improved and the life of the flash storage device 3 can be maximized.

As a result, appropriate division of roles between the host 2 and the flash storage device 3 can be achieved, thereby improving the I/O performance of the entire system including the host 2 and the flash storage device 3.

When a control command specifying a source block number and a destination block number for garbage collection is received from the host 2, the controller 4 of the flash storage device 3 selects a second block having the source block number and a third block having the destination block number from among the multiple blocks, determines a destination position in the third block to which the valid data stored in the second block should be written, and copies the valid data to the destination position in the third block. The controller then notifies the host 2 of the logical address of the valid data, the destination block number, and the physical address in the second block indicating the destination position in the third block. This allows a configuration to be realized in which, even in GC, the host 2 handles only the block numbers (source block number, destination block number), and the flash storage device 3 determines the destination position in the destination block.

The flash storage device 3 may be used as one of multiple flash storage devices 3 provided in a storage array. The storage array may be connected to an information processing device such as a server computer via a cable or a network. The storage array includes a controller that controls the multiple flash storage devices 3 in the storage array. When the flash storage device 3 is applied to a storage array, the controller of the storage array may function as a host 2 for the flash storage device 3.

In the present embodiment, a NAND flash memory is exemplified as a nonvolatile memory. However, the function of the present embodiment can be applied to, for example, MRAM (Magnetoresistive Random Access Memory).
Random Access Memory), PRAM (Phase change
The present invention can also be applied to various other non-volatile memories such as Random Access Memory (RRAM), Resistive Random Access Memory (ReRAM), or Ferroelectric Random Access Memory (FeRAM).

Although several embodiments of the present invention have been described, these embodiments are presented as examples and are not intended to limit the scope of the invention. These novel embodiments can be embodied in various other forms, and various omissions, substitutions, and modifications can be made without departing from the gist of the invention. These embodiments and their modifications are included in the scope and gist of the invention, and are included in the scope of the invention and its equivalents described in the claims.

2... host, 3... flash storage device, 4... controller, 5... NAND flash memory, 21... write operation control unit, 22... read operation control unit, 23... GC operation control unit.

Claims (20)

1. A memory system connectable to a host, comprising:
a non-volatile memory including a plurality of blocks, each of which is a unit of an erase operation and each of which is designated by a block number;
a controller electrically connected to the nonvolatile memory and controlling the nonvolatile memory;
The controller:
in response to receiving a copy command from the host that specifies at least a first block number;
reading first data from a first block designated by the first block number among the plurality of blocks;
writing the first data to a first location in a second block different from the first block among the plurality of blocks;
and notifying the host of a first identifier for identifying the first data, a second block number specifying the second block, and a physical address within the first block indicating the first location within the second block. The controller:
writing the first data and the first identifier to the first block in response to receiving a write command from the host, the write command specifying at least the first identifier and the first block number;
2. The memory system of claim 1, further configured to, in response to receiving the copy command from the host, read the first identifier stored in the first block and write the first identifier to the second block. The memory system of claim 1, wherein an offset from the beginning of the first block to the location where the first data was stored is different from an offset from the beginning of the second block to the first location. The memory system of claim 1, further configured to: read the first data from the first location in the second block based on the second block number and the physical address in the first block in response to receiving a read command from the host that specifies the second block number and the physical address in the first block. each of the plurality of blocks includes a plurality of pages;
2. The memory system of claim 1, wherein the physical address within the first block is represented by an offset within a first block indicating an offset from the beginning of the second block to the first location in a multiple of a granularity having a size different from a page size. The controller:
Managing a free block group among the plurality of blocks;
2. The memory system of claim 1, further configured to, in response to receiving a block allocation command from the host, allocate one free block of the group of free blocks to the host, and notify the host of a block number designating the allocated block. The controller:
notifying the host of a maximum block number indicating the number of the plurality of blocks in response to receiving a first command from the host requesting a maximum block number;
2. The memory system of claim 1, further configured to notify the host of a block size of each of the plurality of blocks in response to receiving a second command from the host requesting a block size. The memory system of claim 7, wherein the controller is configured to notify the host of the block size of the block specified by the block number included in the second command when the second command includes a block number. The memory system of claim 1, wherein the block number is specified as a physical address. The memory system of claim 1, wherein the first identifier is a logical address associated with the first data. A control method for controlling a non-volatile memory including a plurality of blocks, each of which is a unit of an erase operation and each of which is specified by a block number, by a controller, comprising:
in response to receiving a copy command from the host specifying at least a first block number;
reading first data from a first block designated by the first block number among the plurality of blocks;
writing the first data to a first location in a second block different from the first block among the plurality of blocks;
notifying the host of a first identifier for identifying the first data, a second block number for specifying the second block, and a physical address within the first block indicating the first position within the second block. writing the first data and the first identifier to the first block in response to receiving a write command from the host, the write command designating at least the first identifier and the first block number;
12. The control method according to claim 11, further comprising: in response to receiving the copy command from the host, reading the first identifier stored in the first block and writing the first identifier to the second block. The control method according to claim 11, wherein an offset from the beginning of the first block to the position where the first data was stored and an offset from the beginning of the second block to the first position are different from each other. The control method according to claim 11, further comprising: reading the first data from the first location in the second block based on the second block number and the physical address in the first block in response to receiving a read command from the host that specifies the second block number and the physical address in the first block. each of the plurality of blocks includes a plurality of pages;
12. The control method according to claim 11, wherein the physical address within the first block is represented by an offset within the first block indicating an offset from the beginning of the second block to the first position in a multiple of a granularity having a size different from a page size. managing a free block group among the plurality of blocks;
12. The control method according to claim 11, further comprising: in response to receiving a block allocation command from the host, allocating one free block from the group of free blocks to the host, and notifying the host of a block number specifying the allocated block. notifying the host of a maximum block number indicating the number of the plurality of blocks in response to receiving a first command from the host requesting a maximum block number;
12. The method according to claim 11, further comprising: in response to receiving a second command from the host requesting a block size, notifying the host of a block size of each of the plurality of blocks. The control method according to claim 17, further comprising: notifying the host of the block size of the block specified by the block number included in the second command if the second command includes a block number. The control method of claim 11, wherein the block number is specified as a physical address. The control method according to claim 11, wherein the first identifier is a logical address associated with the first data.

Images