Patent Publication Number: US-9417803-B2

Title: Adaptive mapping of logical addresses to memory devices in solid state drives

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Patent Application 61/536,597, filed Sep. 20, 2011, whose disclosure is incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates generally to memory devices, and particularly to methods and systems for logical-to-physical address mapping. 
     BACKGROUND OF THE INVENTION 
     Data storage in non-volatile memory devices such as Flash devices often involves translating logical addresses into physical storage locations in the memory. Various techniques for mapping logical addresses to physical addresses are known in the art. For example, U.S. Pat. No. 7,631,138, whose disclosure is incorporated herein by reference, describes techniques for adaptive mode switching of Flash memory address mapping based on host usage characteristics. In some embodiments, a controller switches the manner in which data sectors are mapped into blocks and meta-blocks of the memory in response to host programming and controller data consolidation patterns, in order to improve performance and reduce wear. 
     SUMMARY OF THE INVENTION 
     An embodiment of the present invention that is described herein provides a method for data storage. The method includes receiving data items associated with respective logical addresses for storage in a memory that includes multiple memory units. Respective estimates of a performance characteristic are obtained for the multiple memory units. A mapping, which maps the logical addresses to respective physical storage locations in the multiple memory units, is adapted based on the estimates so as to balance the performance characteristic across the memory units. The data items are stored in the physical storage locations in accordance with the adapted mapping. 
     In some embodiments, adapting the mapping includes modifying a total number of the logical addresses that are mapped to a given memory unit. In an embodiment, storing the data items includes distributing the data items among the memory units in accordance with a weighted Round-Robin scheduling scheme that assigns respective weights to the memory units, and adapting the mapping including modifying one or more of the weights. Modifying the weights may include assigning to a given memory unit different first and second weights for respective different first and second types of memory access commands. 
     In another embodiment, obtaining the estimates includes evaluating the performance characteristic for the multiple memory units during production of the memory or the memory units. Additionally or alternatively, obtaining the estimates may include evaluating the performance characteristic for the multiple memory units while the memory is operating in a host system. 
     In a disclosed embodiment, adapting the mapping includes initially storing the data items in the memory in accordance with an initial setting of the mapping, and subsequently adapting the mapping and copying one or more of the data items so as to store the data items in the memory in accordance with the adapted mapping. 
     In various example embodiments, the performance characteristic for each memory unit is indicative of a respective count of memory blocks in the memory unit that are available for programming, of a respective count of faulty memory blocks in the memory unit, of a respective time duration of a memory access command applied to the memory unit, of a respective read error performance of the memory unit, of a respective endurance of the memory unit, of a respective frequency of access to data stored in the memory unit, and/or of a respective count of memory access commands pending for execution in the memory unit. 
     There is additionally provided, in accordance with an embodiment of the present invention, a data storage apparatus that includes an interface and a processor. The interface is configured to communicate with a memory that includes multiple memory units. The processor is configured to receive data items associated with respective logical addresses for storage in the memory, to obtain respective estimates of a performance characteristic for the multiple memory units, to adapt, based on the estimates, a mapping that maps the logical addresses to respective physical storage locations in the multiple memory units, so as to balance the performance characteristic across the memory units, and to store the data items in the physical storage locations in accordance with the adapted mapping. 
     There is also provided, in accordance with an embodiment of the present invention, a data storage apparatus that includes a memory and a processor. The memory includes multiple memory units. The processor is configured to receive data items associated with respective logical addresses for storage in the memory, to obtain respective estimates of a performance characteristic for the multiple memory units, to adapt, based on the estimates, a mapping that maps the logical addresses to respective physical storage locations in the multiple memory units, so as to balance the performance characteristic across the memory units, and to store the data items in the physical storage locations in accordance with the adapted mapping. 
     The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings in which: 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram that schematically illustrates a data storage system, in accordance with an embodiment of the present invention; and 
         FIG. 2  is a flow chart that schematically illustrates a method for logical-to-physical address mapping, in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Overview 
     Some types of memory devices are constructed from multiple memory units. For example, a Solid State Drive (SSD) typically comprises multiple non-volatile memory dies such as Flash dies. In many practical scenarios, memory units in a given memory device may differ from one another in characteristics such as the number of free memory blocks, the number of bad blocks, memory access latency, error performance, expected endurance, the presence of frequently-used vs. rarely-used data, and/or the number of commands that are currently pending for execution. Some of the differences may already be present when the memory units are produced, and some may develop during the lifetime of the memory device in a host system. 
     Embodiments of the present invention that are described herein provide improved methods and systems for data storage. The disclosed techniques distribute data for storage in the multiple memory units based on estimated characteristics of the individual memory units. 
     In a typical flow, a memory controller or other processor estimates one or more characteristics of each memory unit, such as the example characteristics listed above. The processor distributes incoming data for storage in the various memory units in a manner that balances the characteristics across the memory device. 
     For example, the processor may adapt a Virtual-to-Physical (V-P) address mapping, which translates virtual addresses associated with the data into physical storage locations in the memory units, based on the estimated memory unit characteristics. In other words, the processor may adapt the assignment of Logical Block Addresses (LBAs) to memory units based on the estimated characteristics. Adapting the V-P mapping in this manner enables the processor to balance characteristics such as lifetime, storage latency or error performance across the memory device. 
     It is possible in principle to define the V-P mapping, either statically or adaptively, without considering the memory unit characteristics. Such a solution, however, is likely to cause the worst-performing memory units to dominate the overall performance of the memory device. By contrast, the disclosed techniques adapt the V-P mapping to the actual individual characteristics of each memory unit, resulting in better overall memory device performance. 
     System Description 
       FIG. 1  is a block diagram that schematically illustrates a data storage system  20 , in accordance with an embodiment of the present invention. System  20  comprises a memory device  22  and a host  24 . Memory device  22  accepts data for storage from host  24  and stores it in memory, and retrieves data from memory and provides it to the host. 
     In various embodiments, memory device  22  may comprise, for example, a Solid State Drive (SSD) that stores data for a personal or mobile computing device or an enterprise system, or a Micro-Secure Digital (μSD) card that stores data for a cellular phone, media player, digital camera or other host. In alternative embodiments, memory device  22  may be used in any other suitable application in which data is stored and retrieved and with any other suitable host. 
     Memory device  22  comprises multiple memory units  28 . In the present example, each memory unit  28  comprises a respective Flash die that comprises multiple non-volatile analog memory cells. The terms “memory unit” and “die” are thus used interchangeably herein. The memory cells may comprise, for example, NAND Flash cells, NOR or Charge Trap Flash (CTF) Flash cells, phase change RAM (PRAM, also referred to as Phase Change Memory—PCM) cells, Nitride Read Only Memory (NROM) cells, Ferroelectric RAM (FRAM) and/or magnetic RAM (MRAM) cells, or any other suitable memory technology. 
     In the context of the present patent application and in the claims, the term “analog memory cell” is used to describe any memory cell that holds a continuous, analog value of a physical parameter, such as an electrical voltage or charge. Any suitable type of analog memory cells, such as the types listed above, can be used. In the present example, each memory unit  28  comprises a non-volatile memory of NAND Flash cells. The charge levels stored in the cells and/or the analog voltages or currents written into and read out of the cells are referred to herein collectively as analog values or storage values. 
     Memory device  22  stores data in the analog memory cells by programming the cells to assume respective memory states, which are also referred to as programming levels. The programming levels are selected from a finite set of possible levels, and each level corresponds to a certain nominal storage value. For example, a 2 bit/cell MLC can be programmed to assume one of four possible programming levels by writing one of four possible nominal storage values into the cell. The memory cells are typically arranged in rows and columns. Typically, a given memory unit comprises multiple erasure blocks (also referred to as memory blocks), i.e., groups of memory cells that are erased together. 
     In various embodiments, each memory unit  28  may comprise a packaged device or an unpackaged semiconductor chip or die. Generally, memory device  22  may comprise any suitable number of memory devices of any desired type and size. 
     Memory device  22  comprises a memory controller  32 , which accepts data from host  24  and stores it in memory units  28 , and retrieves data from the memory units and provides it to the host. Memory controller  32  comprises a host interface  36  for communicating with host  24 , a memory interface  40  for communicating with memory units  28 , and a processor  44  that processes the stored and retrieved data. For example, processor  44  may encode the data for storage with an Error Correction Code (ECC) and decode the ECC of data read from memory. The functions of processor  44  can be implemented, for example, using software running on a suitable Central Processing Unit (CPU), using hardware (e.g., state machine or other logic), or using a combination of software and hardware elements. 
     Memory controller  32 , and in particular processor  44 , may be implemented in hardware. Alternatively, the memory controller may comprise a microprocessor that runs suitable software, or a combination of hardware and software elements. In some embodiments, processor  44  comprises a general-purpose processor, which is programmed in software to carry out the functions described herein. The software may be downloaded to the processor in electronic form, over a network, for example, or it may, alternatively or additionally, be provided and/or stored on tangible media, such as magnetic, optical, or electronic memory. 
     The system configuration of  FIG. 1  is an example configuration, which is shown purely for the sake of conceptual clarity. Any other suitable memory system configuration can also be used. For example, in some embodiments two or more memory controllers  32  may be connected to the same host. Elements that are not necessary for understanding the principles of the present invention, such as various interfaces, addressing circuits, timing and sequencing circuits and debugging circuits, have been omitted from the figure for clarity. 
     In the exemplary system configuration shown in  FIG. 1 , memory units  28  and memory controller  32  are implemented as separate Integrated Circuits (ICs). In alternative embodiments, however, the memory units and the memory controller may be integrated on separate semiconductor dies in a single Multi-Chip Package (MCP) or System on Chip (SoC), and may be interconnected by an internal bus. Further alternatively, some or all of the memory controller circuitry may reside on the same die on which one or more of the memory units are disposed. Further alternatively, some or all of the functionality of memory controller  32  can be implemented in software and carried out by host  24 , or by any other type of memory controller. In some embodiments, host  24  and Memory controller  32  may be fabricated on the same die, or on separate dies in the same device package. 
     Assignment of Logical Addresses to NAND Dies Based on Estimated Die Characteristics 
     In memory device  22 , memory controller  32  writes data to memory units  28  in page units, but erasure is applied to entire memory blocks. Data is written only to erased pages, and it is therefore not possible to update data in-place. Because of this property of Flash memory, processor  44  of memory controller  32  typically applies a Virtual-to-Physical (V-P) address mapping scheme. When using V-P mapping, data items for storage are received from host  24  with respective virtual addresses, also referred to as Logical Block Addresses (LBAs). Processor  44  translates the virtual addresses into respective physical storage locations in memory units  28  in which the data is to be stored. 
     Updating a data item thus involves writing the updated data item to another physical storage location, marking the previous version of the data as invalid, and dynamically updating the V-P address mapping to indicate the new physical storage location of the data item. 
     In some embodiments, processor  44  estimates certain characteristics of the individual Flash dies  28 , and adapts the V-P address mapping based on the estimated characteristics. Typically, processor  44  adapts the V-P mapping so as to balance the characteristic across the multiple dies. 
     The following list gives several examples of characteristics that processor  44  may estimate for each die  28 . The list also gives the rationale for balancing each characteristic by adapting the V-P mapping:
         The number of memory blocks in the die that are erased and available for new programming. It is typically desirable to have a similar number of free blocks in each die. This sort of balancing enables the memory controller to maximize parallelism in storing and retrieval of data in dies  28 .   The number of faulty memory blocks (“bad blocks”). Faulty blocks may be identified and marked as bad during production or during use in a host system. Bad blocks reduce the memory device&#39;s over-provisioning and may eventually cause data loss. It is desirable to balance the number of bad blocks per die to maximize parallelism. Moreover, dies having a large number of bad blocks can be used less frequently or even ignored altogether.   The time duration needed to perform a memory access command of a given type in the die (e.g., program, read or erase command). Distributing the memory access operations based on the differences in execution time in the various dies can help reduce the overall storage latency. For example, frequently-accessed data can be written to faster dies and rarely-accessed data to slower dies.   Error performance of the die, e.g., the number of errors corrected in readout of data from the die. Distributing the memory access operations based on the differences in error performance of the various dies can help reduce the overall error probability. Balancing of this sort can also reduce management overhead, since error-prone dies typically incur high management overhead on the memory controller.   Endurance estimation of the die, e.g., the expected number of Programming and Erasure (P/E) remaining until the die reaches its end-of-life. Endurance can be quantified as the maximum or average endurance, and can be estimated either during production and/or along the lifetime of the memory device&#39;s use in a host system. Balancing the expected endurance of the various dies improves the overall endurance of the memory device.   The presence of frequently-used (“hot”) and/or rarely-used (“cold”) data in the die. Balancing this characteristic can reduce latency and improve user experience.   The number of memory access commands that are currently pending for execution in the die. Balancing this characteristic, for example by giving preference to less busy dies, can increase parallelism and reduce the overall latency of the memory device.       

     The characteristics and balancing criteria listed above are chosen purely by way of example. In alternative embodiments, processor  44  may adapt the V-P mapping based on any other suitable die characteristic. In some embodiments, processor  44  estimates multiple different characteristics for each die, and adapts the V-P mapping based on the combination of estimates. 
     Each of the characteristics can be estimated either during production of dies  28  or of memory device  22 , in which case processor  44  may accept information regarding the estimates from an external source. Additionally or alternatively, processor  44  may estimate or re-estimate a given characteristic during operation of memory device  22  in the host system. For example, processor  44  may accept initial estimates of the expected endurance of each die from production testing, and re-estimate the endurance during operation of the memory device in the host system. A similar process can be performed for the number of bad blocks. 
     In various embodiments, processor  44  may adapt the V-P mapping in different ways. In an example embodiment, processor  44  maps LBAs to physical storage locations using a weighted Round-Robin scheduling scheme. In such a process, processor  44  alternates among memory units  28  in a cyclical manner. At any given point in time, one of the memory units is selected as the next memory unit for storing the next incoming data item, in accordance with the cyclic alternation order. Upon receiving a data item for storage, processor  44  maps the logical address of the data item to a physical storage location in the currently-selected memory unit. 
     When using a weighted Round-Robin scheme, processor  44  assigns a respective weight to each memory unit  28 . The weight defines the relative frequency with which data will be stored in that memory unit in the cyclic alternation order. For example, if the weight of one memory unit is twice the weight of another memory unit, processor  44  will typically store in the former memory unit twice the amount of data that in the latter memory unit. 
     In some embodiments, processor  44  adapts the V-P mapping (based on the estimated die characteristics) by adapting the weights used in the weighted Round-Robin scheme. Typically, a memory unit that is to store data items at a higher frequency (e.g., because it has a high expected endurance or a small number of bad blocks) will be assigned a high weight, and vice versa. Processor  44  may modify the weights over time, to track variations in the memory unit characteristics. In some embodiments, processor  44  uses different weights for different memory access operations. In an example embodiment, processor  44  assigns different weights for different usage patterns, e.g., one set of weights for random storage and another set of weights for sequential storage. 
       FIG. 2  is a flow chart that schematically illustrates a method for logical-to-physical address mapping, in accordance with an embodiment of the present invention. The method begins with processor  44  of memory controller  32  estimating respective characteristics of memory dies  28 , at a characteristic estimation step  50 . 
     Based on the estimated die characteristics, processor  44  defines respective weights for dies  28 , to be used in the Round-Robin scheduling scheme, at a weight assignment step  54 . Processor  44  maps logical addresses of incoming data items to respective physical locations based on the weights, at a mapping step  58 . In other words, processor  44  maps LBAs to dies  28  in a weighted Round-Robin scheduling scheme, in which the weights are determined based on the estimated die characteristics. Processor  44  stores the data items in dies  28  in accordance with the mapping, at a storage step  62 . 
     In alternative embodiments, processor  44  may adapt and apply the V-P mapping in any other suitable way, not necessarily involving Round-Robin scheduling. 
     In some embodiments, processor  44  adapts the V-P mapping in real time to data items that are received for storage. In these embodiments, processor  44  stores each data item that is accepted from host  24  in accordance with the adapted mapping. 
     In alternative embodiments, processor  44  adapts the V-P mapping in an off-line background process. In these embodiments, processor  44  initially stores the incoming data items in accordance with an initial setting of the V-P mapping, and later adapts the V-P mapping and copies at least some of the data items to alternative physical storage locations in accordance with the adapted V-P mapping. 
     In an example embodiment, processor  44  initially stores the incoming data items in accordance with a V-P mapping that optimizes write latency, e.g., a mapping that is based on the average programming time of each memory die  28 . Later, processor  44  modifies the V-P mapping to optimize readout latency, e.g., to a mapping that is based on the average readout time of each memory die  28 . This background technique optimizes both programming and readout latency. 
     Although the embodiments described herein mainly address Flash dies, the methods and systems described herein can also be used for adapting the V-P mapping based on characteristics of other suitable memory units of any desired size, such as packaged devices, or groups of blocks (e.g., memory planes) within the dies. 
     It will thus be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and sub-combinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art. Documents incorporated by reference in the present patent application are to be considered an integral part of the application except that to the extent any terms are defined in these incorporated documents in a manner that conflicts with the definitions made explicitly or implicitly in the present specification, only the definitions in the present specification should be considered.