# Patent

## Title
Non-volatile semiconductor memory segregating sequential, random, and system data to reduce garbage collection for page based mapping

## Abstract

A non-volatile semiconductor memory is disclosed comprising a memory device having a memory array including a plurality of memory segments. A plurality of sequential access write commands and random access write commands are received from a host, wherein each write command identifies at least one logical block address (LBA). The LBAs for the sequential access write commands are mapped to a plurality of the memory segments to generate sequential mapping data, and the sequential mapping data is mapped to a first one of the zones. The LBAs for the random access write commands are mapped to a plurality of the memory segments to generate random mapping data, and the random mapping data is mapped to a second one of the zones.

## Background
BACKGROUND
A non-volatile semiconductor memory may be employed as mass storage for a computer system (e.g., desktop, laptop, portable, etc.) or a consumer device (e.g., music player, cell phone, camera, etc.) or other suitable application. The non-volatile semiconductor memory may comprise one or more memory devices (such as a flash memory) and control circuitry for accessing each memory device. Each memory device is coupled to an I/O bus, as well as a number of interface control lines. When issuing a program command or an erase command to a memory device, the control circuitry transfers the address and command data (and write data for a program operation) over the I/O bus. When issuing a read command, the control circuitry transfers the address and command data over the I/O bus and then receives the read data over the I/O bus.
Each memory device typically comprises a number of blocks which are accessed a page at a time. For example, a single block may comprise 128 pages where each page comprises 4k bytes. Since a page typically cannot be overwritten without first being erased, a new page in a different block is typically selected to perform an “overwrite” operation. To facilitate relocating data to a different page, the non-volatile semiconductor memory implements indirect accessing wherein a logical block address (LBA) representing a data block is mapped to a physical block address (PBA) representing one of the pages. In this manner, when the page for a data block is moved, the LBA is simply reassigned to the new PBA.
Periodically the non-volatile semiconductor memory will perform a garbage collection operation wherein the remaining valid pages of a first block are relocated to a second block so that the first block can be erased (thereby erasing the invalid pages that were previously relocated during overwrite operations). It is desirable to minimize the amount of garbage collection in a non-volatile semiconductor memory in order to decrease write amplification and power consumption, as well as increase endurance and performance.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows a non-volatile semiconductor memory comprising a memory device having a memory array including a plurality of memory segments according to an embodiment of the present invention.
FIG. 2 shows an embodiment of the present invention wherein mapping data for system data, random data, and sequential data is stored in respective mapping zones.
FIGS. 3A-3D illustrate an embodiment of the present invention wherein a page based mapping scheme is used to address the memory segments (pages in this embodiment).
FIGS. 4A-4C illustrate an embodiment of the present invention wherein mapping data for a number of write commands are buffered in volatile memory before being written to the non-volatile memory.
FIG. 5A shows a global LBA/PBA map accessed while in volatile memory according to an embodiment of the present invention.
FIG. 5B shows a sequential log for storing mapping data for sequential access write commands, wherein the sequential log for updating the global LBA/PBA map in the event of a power failure.
FIG. 5C shows a random/system log for storing mapping data for random/system access write commands, wherein the random/system log for updating the global LBA/PBA map in the event of a power failure.
FIG. 6 is a flow diagram according to an embodiment of the present invention wherein a full page of mapping data is stored in each write log before they are written to the non-volatile memory, and periodically the global LBA/PBA map is written to the non-volatile memory.



DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION
FIG. 1 shows a non-volatile semiconductor memory 2 comprising a memory device 4 having a memory array 6 including a plurality of memory segments, and control circuitry 8 for defining a plurality of zones each comprising a plurality of the memory segments. A plurality of sequential access write commands are received from a host 10 to write sequential data to the memory device 4, wherein each sequential access write command identifies at least one logical block address (LBA). A plurality of random access write commands are received from the host 10 to write random data to the memory device 4, wherein each random access write command identifies at least one LBA. The LBAs for the sequential access write commands are mapped to a plurality of the memory segments to generate sequential mapping data, and the sequential mapping data is mapped to a first one of the zones. The LBAs for the random access write commands are mapped to a plurality of the memory segments to generate random mapping data, and the random mapping data is mapped to a second one of the zones.
The non-volatile semiconductor memory 2 may comprise any suitable configuration of control circuitry 8 and memory device 4. In the embodiment of FIG. 1, the memory device 4 comprises a suitable flash memory (e.g., NAND or NOR flash), and the control circuitry comprises a flash memory controller 8 including a microprocessor 12 for implementing various algorithms (e.g., LBA to PBA mapping, error correction coding (ECC), wear leveling, etc.). The memory controller 8 further comprises a buffer 14 for buffering write/read data in volatile memory (e.g., DRAM), and suitable interface circuitry 16 for interfacing with the memory device 4. The memory device 4 is coupled to an I/O bus 18, as well as a number of interface control lines 20. When issuing a program command or an erase command to the memory device 4, the microprocessor 12 transfers the address and command data (and write data for a program operation) over the I/O bus 18. When issuing a read command, the microprocessor 12 transfers the address and command data over the I/O bus 18 and then receives the read data over the I/O bus 18. In one embodiment, the microprocessor 12 receives status information 22 from the memory device 4 to determine when it has completed a write/read operation.
The memory device 4 in the embodiment of FIG. 1 comprises a controller 24 for receiving the control signals and command data from the interface circuitry 16. For example, the command data may comprise address information for writing data to a particular memory segment in the memory array 6. The write data is buffered in a data register 26 and when the controller 24 receives a flush command, the controller 24 transfers the data buffered in the data register 26 to a target memory segment (page) in the memory array 6.
In one embodiment, the memory controller 8 implements a solid state drive (SSD) by emulating a disk drive accessible by a host system using a standard disk drive communication protocol (e.g., the ATA protocol). The host 10 in this embodiment may comprise a separate microprocessor (e.g., in a desktop or laptop computer) which communicates with the SSD over a suitable interface (e.g., serial or parallel ATA). In an alternative embodiment, the non-volatile semiconductor memory 2 may be implemented within a consumer device (e.g., a camera or cell phone), wherein the host 10 may be implemented as a firmware component executed by the same microprocessor 12 for implementing the memory controller 8.
In one embodiment, the memory array 6 in the memory device 4 comprises a plurality of blocks, where each block comprises a plurality of pages. In one embodiment, a page must be erased before it is written. A page is therefore “overwritten” by writing the new data to a different page (typically in a different block), remapping the LBA to the new PBA, and invalidating the old page. Periodically, the invalid pages of a block are recovered during a garbage collection procedure by copying the valid page of a block to a new block, and then erasing the entire block.
The memory controller 8 defines a number of zones by allocating a number of blocks to each zone, wherein each zone stores write data or mapping data associated with sequential access write commands, random access write commands, or system access write commands as illustrated in FIG. 2. In one embodiment, the blocks may be dynamically allocated to each zone as needed. Segregating the write data as well as the mapping data into respective zones may help reduce the amount of garbage collection within each zone by reducing the number of blocks storing both valid and invalid pages. That is, if the write data and the mapping data are segregated, it increases the likelihood that an entire block will be overwritten within a zone such that the block can be erased without relocating valid pages.
This concept is understood with reference to FIGS. 3A-3D which illustrates a page based mapping scheme according to an embodiment of the present invention. With page based mapping, each LBA may be mapped to the PBA of any page within any block. When writing data having a first LBA mapped to a first page of a first block to a second page of a second block, valid pages of the first block are not relocated to the second block as with block based mapping. This is illustrated in FIGS. 3A and 3B wherein during a write operation the write data is written to a page in a second block and the corresponding page in a first block is invalidated. This process is repeated during subsequent write operations for different pages as illustrated in FIGS. 3B and 3C until all of the pages of the first block have been invalidated as illustrated in FIG. 3D. The first block is then erased so that it can be re-allocated without needing to relocate any valid pages (because there are no valid pages).
During each write operation, the LBA to PBA mapping is updated to reflect the relocation of pages or to reflect the allocation of a new page for a new LBA. In addition, the mapping data is periodically written to the memory device 4 so that the mapping is preserved in the event of a power failure. In one embodiment illustrated in FIGS. 4A-4C, the mapping data for a number of write commands is cached in the volatile memory before being written to the memory device 4. For example, in one embodiment the mapping data is not written to the memory device 4 until enough write commands have been executed to fill up an entire page with mapping data. Once a page of mapping data has been cached, the mapping data is written to a page of the memory array. This reduces the number of write operations to the memory array (and associated fragmentation of the memory array) as compared to writing partial pages of mapping data at a time.
FIG. 5A shows an embodiment of the present invention wherein a global LBA to PBA map is stored in the memory device 4 and read into a volatile memory of the memory controller 8 when powered on. When a write command is executed by the memory controller 8, the global map in the volatile memory is updated to reflect the change in the LBA to PBA mapping. Mapping data is also stored in a write log corresponding to the type of write operation (sequential, random, or system). The write logs are then periodically stored in the memory device 4 so that the mapping data is preserved in the event of a power failure. The write logs are much smaller than the global map and therefore saving the write logs to the memory device 4 requires less time and results in less write amplification as compared to saving the entire global map to the memory device 4. If a power failure occurs, the write logs are read from the memory device 4 and used to update the global map. The global map is also periodically saved to the memory device 4 but much less frequently than the write logs.
FIG. 5B shows part of an example write log storing mapping data associated with a sequential access write command. With a sequential access the LBAs and corresponding PBAs are consecutive, and therefore only the starting LBA is stored (LBA 0 in the example of FIG. 5B) together with the consecutive PBAs (zone and page number within the zone). In an alternative embodiment, the start PBA is stored together with the run-length of PBAs which may require even less memory space. FIG. 5C shows part of an example write log storing mapping data associated with either a random access write command or a system access write command. Because the mapping of LBA to PBA is random, the write log stores both the LBA and the PBA for each corresponding page (zone and page number within the zone). FIGS. 5B and 5C also illustrate that in one embodiment each write log stores enough mapping data to fill one page, wherein the write log is saved to the memory device 4 once enough write operations have been executed to fill the write log.
FIG. 6 is a flow diagram according to an embodiment of the present invention wherein when the non-volatile semiconductor memory is powered on, a global map is read from the memory device into a volatile memory (step 28). The mapping logs are read from the memory device and used to update the global map if needed (step 30). When a write command is received (step 32), the write data is written to the target zone depending on the type of write command. If the write command is a sequential access write command, the user data is written to a sequential data zone of the memory device (step 34) and sequential mapping data is generated and stored in the sequential write log(step 36). If the sequential write log is full (step 38), then the sequential write log is written to a sequential mapping zone of the memory device and the sequential write log purged to process subsequent sequential access write commands (step 40). If the write command is a random access write command, the user data is written to a random data zone of the memory device (step 42) and random mapping data is generated and stored in the random write log(step 44). If the random write log is full (step 46), then the random write log is written to a random mapping zone of the memory device and the random write log purged to process subsequent random access write commands (step 48). If the write command is a system access write command, the system data is written to a system data zone of the memory device (step 50) and system mapping data is generated and stored in the system write log(step 52). If the system write log is full (step 54), then the system write log is written to a system mapping zone of the memory device and the system write log purged to process subsequent system access write commands (step 56). After a predetermined interval (step 58), the global map is written to the memory device (step 60) and the write logs currently stored in the memory device are invalidated (step 62) since they are no longer needed to update the global map in the event of a power failure (until more write commands are processed).
The system data written to the memory device during a system access write command may include any suitable system data. For example, when the write logs are written to the memory device (at steps 40, 48 and 56 of FIG. 6), the write commands are system access write commands. The write logs are written to a system data zone and the corresponding mapping data is stored in the system write log. Other suitable system data may be generated during normal operation, such as system data associated with a garbage collection or wear leveling algorithm.
The memory controller 8 may identify a write command as being sequential or random in any suitable manner. In one embodiment, the write commands received from the host may include an identifier that specifies the type of write command. In another embodiment, new write commands are initially processed as random access write commands until a consecutive number of sequential write commands exceeds a predetermined threshold. Subsequent write commands are then processed as sequential access write commands until there is a break in the consecutive sequence.

## Claims

1. A non-volatile semiconductor memory comprising:
a memory device comprising a memory array including a plurality of memory segments; and
control circuitry operable to:
allocate a first set of the plurality of memory segments to a first zone and a second set of the plurality of memory segments to a second zone, wherein the first zone is reserved for storing sequential data and the second zone is reserved for storing random data;
receive a plurality of sequential access write commands including sequential data from a host after said allocation of memory segments to the first zone, wherein each of the sequential access write commands identifies one or more logical block addresses (LBAs);
receive a plurality of random access write commands including random data from the host after said allocation of memory segments to the second zone, wherein each of the random access write commands identifies one or more LBAs;
map the LBAs identified by the sequential access write commands to one or more memory segments of the first zone to generate sequential mapping data including zone number and page number information associated with the one or more memory segments of the first zone;
store the sequential data in the one or more memory segments of the first zone;
allocate a third set of the plurality of memory segments to a third zone for storing sequential mapping data and store the sequential mapping data in the third zone;
map the LBAs identified by the random access write commands to one or more memory segments of the second zone to generate random mapping data including zone number and page number information associated with the one or more memory segments of the second zone;
store the random data in the one or more memory segments of the second zone; and
allocate a fourth set of the plurality of memory segments to a fourth zone for storing random mapping data and store the random mapping data in the fourth zone.

2. The non-volatile semiconductor memory as recited in claim 1, wherein the control circuitry is further operable to:
allocate a fifth set of the plurality of memory segments to a fifth zone for storing system data;
generate a plurality of system access write commands to write system data to the memory device, wherein each system access write command identifies one or more LBAs;
map the LBAs identified by the system access write commands to one or more memory segments of the fifth zone to generate system mapping data.

3. The non-volatile semiconductor memory as recited in claim 2, wherein:
the plurality of memory segments comprises a plurality of blocks, each block comprising a plurality of pages;
the control circuitry is further operable to erase a page by erasing an entire block;
the first zone comprises a first block;
the second zone comprises a second block; and
the third zone comprises a third block.

4. The non-volatile semiconductor memory as recited in claim 2, wherein the control circuitry is further operable to:
allocate a sixth set of the plurality of memory segments to a sixth zone for storing system mapping data and store the system mapping data in the sixth zone after executing the plurality of the system access write commands.

5. The non-volatile semiconductor memory as recited in claim 4, wherein the control circuitry is further operable to erase a block in one of the first, second, third, fourth, fifth or sixth zones without relocating valid pages from the block to another block.

6. A method of operating a non-volatile semiconductor memory comprising a memory device comprising a memory array including a plurality of memory segments, the method comprising:
allocating a first set of the plurality of memory segments to a first zone and a second set of the plurality of memory segments to a second zone, wherein the first zone is reserved for storing sequential data and the second zone is reserved for storing random data;
receiving a plurality of sequential access write commands including sequential data from a host after said allocating memory segments to the first zone, wherein each of the sequential access write commands identifies one or more logical block addresses (LBAs);
receiving a plurality of random access write commands including random data from the host after said allocating memory segments to the second zone, wherein each of the random access write commands identifies one or more LBAs;
mapping the LBAs identified by the sequential access write commands to one or more memory segments of the first zone to generate sequential mapping data including zone number and page number information associated with the one or more memory segments of the first zone;
storing the sequential data in the one or more memory segments of the first zone;
allocating a third set of the plurality of memory segments to a third zone for storing sequential mapping data and storing the sequential mapping data in the third zone;
mapping the LBAs identified by the random access write commands to one or more memory segments of the second zone to generate random mapping data including zone number and page number information associated with the one or more memory segments of the second zone;
storing the random data in the one or more memory segments of the second zone; and
allocating a fourth set of the plurality of memory segments to a fourth zone for storing random mapping data and storing the random mapping data in the fourth zone.

7. The method as recited in claim 6, further comprising:
allocating a fifth set of the plurality of memory segments to a fifth zone for storing system mapping data;
generating a plurality of system access write commands to write system data to the memory device, wherein each system access write command identifies one or more LBAs;
mapping the LBAs identified by the system access write commands to one or more memory segments of the fifth zone to generate system mapping data.

8. The method as recited in claim 7, wherein:
the plurality of memory segments comprise a plurality of blocks, each block comprising a plurality of pages;
a page is erased by erasing an entire block;
the first zone comprises a first block;
the second zone comprises a second block; and
the third zone comprises a third block.

9. The method as recited in claim 7, further comprising:
allocating a sixth set of the plurality of memory segments to a sixth zone for storing system mapping data and storing the system mapping data in the sixth zone after executing the plurality of the system access write commands.

10. The method as recited in claim 9, further comprising erasing a block in one of the first, second, third, fourth, fifth or sixth zones without relocating valid pages from the block to another block.