Flash translation layer (FTL) database journaling schemes

A method includes, in a storage device that includes a non-volatile memory and a volatile memory, maintaining at least one data structure that stores management information used for managing data storage in the non-volatile memory, such that at least a portion of the data structure is stored in the volatile memory. A sequence of journaling chunks is created during operation of the storage device, each journaling chunk including a respective slice of the data structure and one or more changes that occurred in the data structure since a previous journaling chunk in the sequence. The sequence of the journaling chunks is stored in the non-volatile memory. Upon recovering from an electrical power interruption in the storage device, the data structure is reconstructed using the stored journaling chunks.

FIELD OF THE INVENTION

The present invention relates generally to data storage, and particularly to methods and systems for journaling in non-volatile storage devices.

BACKGROUND OF THE INVENTION

Various memory systems use non-volatile memory, such as Flash memory, for storing data. Flash memory devices are typically managed by a management layer referred to as Flash Management or Flash Translation Layer (FTL). Among other tasks, the FTL typically manages the operation of the Flash memory before and after electrical power interruptions.

SUMMARY OF THE INVENTION

An embodiment of the present invention that is described herein provides a method in a storage device that includes a non-volatile memory and a volatile memory. The method includes maintaining at least one data structure that stores management information used for managing data storage in the non-volatile memory, such that at least a portion of the data structure is stored in the volatile memory. A sequence of journaling chunks is created during operation of the storage device, each journaling chunk including a respective slice of the data structure and one or more changes that occurred in the data structure since a previous journaling chunk in the sequence. The sequence of the journaling chunks is stored in the non-volatile memory. Upon recovering from an electrical power interruption in the storage device, the data structure is reconstructed using the stored journaling chunks.

In some embodiments, the data structure includes a mapping of logical addresses to respective physical storage locations in the non-volatile memory. Additionally or alternatively, the data structure includes a database of parameters of respective memory blocks of the non-volatile memory.

In a disclosed embodiment, creating the sequence of the journaling chunks includes accumulating the changes, and, when the accumulated changes reach a predefined data size, storing the journaling chunk including the accumulated changes and the slice of the data structure. In an embodiment, creating the sequence of the journaling chunks includes including in the changes stored in a given journaling chunk at least one change that does not relate to the slice of the data structure stored in the given journaling chunk.

In another embodiment, creating the sequence of the journaling chunks includes storing in successive journaling chunks respective successive slices that cyclically scan the data structure. In yet another embodiment, creating the sequence of the journaling chunks includes storing in each journaling chunk an indication that points to a respective location in the data structure from which the respective slice was obtained.

In yet another embodiment, the at least one data structure includes multiple data structures, and each journaling chunk includes respective slices of the multiple data structures. In still another embodiment, reconstructing the data structure includes identifying a last journaling chunk that was written most recently to the non-volatile memory before the power interruption, identifying a first journaling chunk including a first valid slice of the data structure, and recovering the journaling chunks from the non-volatile memory, from the identified first journaling slice until the identified last journaling chunk. Recovering the journaling chunks may include applying a given change read from a given journaling chunk only upon verifying that the slice referred to by the given change has been recovered already.

There is additionally provided, in accordance with an embodiment of the present invention, a storage device including a non-volatile memory, a volatile memory and a processor. The processor is configured to maintain at least one data structure that stores management information used for managing data storage in the non-volatile memory, such that at least a portion of the data structure is stored in the volatile memory, to create, during operation of the storage device, a sequence of journaling chunks, each journaling chunk including a respective slice of the data structure and one or more changes that occurred in the data structure since a previous journaling chunk in the sequence, to store the sequence of the journaling chunks in the non-volatile memory, and, upon recovering from an electrical power interruption in the storage device, to reconstruct the data structure using the stored journaling chunks.

DETAILED DESCRIPTION OF EMBODIMENTS

Overview

Embodiments of the present invention that are described herein provide improved methods and systems for protection against electrical power interruptions in non-volatile storage devices.

In some embodiments, a storage device comprises a non-volatile memory such as a NAND Flash memory, and a processor that manages data storage in the non-volatile memory. The processor maintains at least one data structure that stores management information used for data storage in the non-volatile memory. The data structure may comprise, for example, a logical-to-physical address translation table and/or a memory block parameter database.

At least part of the data structure is stored in a volatile memory, such as a Random Access Memory (RAM) of the storage device. As such, the data structure should be protected against electrical power interruption. In some embodiments that are described herein, the processor protects the data structure by applying a periodic journaling scheme.

In a typical implementation, the processor divides the data structure into a large number of successive slices. During operation of the storage device, the processor gradually accumulates the changes that occur in the data structure. When the accumulated changes reach a predefined data size, the processor creates a “journaling chunk,” which comprises the changes that occurred since the previous journaling chunk, and also comprises the next slice of the data structure. The processor then stores the journaling chunk in the non-volatile memory.

In other words, the processor continuously creates and stores a sequence of journaling chunks, such that each chunk comprises a respective slice of the data structure plus the changes that occurred in the data structure since the previous chunk. The changes stored in a given chunk, however, may relate to the entire data structure, not necessarily to the individual slice stored in the given chunk.

The sequence of journaling chunks enables the processor to reconstruct the data structure in the event of power interruption. An example recovery scheme is described further below.

Since the processor backs-up the data structure and the changes in small chunks rather than in bulk, the disclosed journaling scheme causes little or no degradation in storage performance. Moreover, this scheme enables the processor to reconstruct the data structure with high speed following power interruption.

Since the slices of the data structures are backed-up at frequent intervals, the number of changes that need to be backed-up is relatively small. Consequently, only a small number of changes need to be applied during recovery. This feature also reduces the number of changes that have not yet been backed-up to the non-volatile memory at any given time, i.e., the changes that will be lost due to the power interruption.

Moreover, the flexibility in choosing the chunk size and the sizes of individual fields in the chunk allows tuning the journaling scheme to any desired trade-off between runtime storage performance and recovery time. The rate at which the processor stores the journaling chunks is typically variable and depends on the level of activity: During intensive storage, changes accumulate rapidly, the journaling chunks fill quickly, and the journaling rate is high. During idle times, changes accumulate slowly and the journaling rate decreases accordingly.

System Description

FIG. 1is a block diagram that schematically illustrates a memory system, in accordance with an embodiment of the present invention. In the present example, the memory system comprises a computer20that stores data in a Solid state Drive (SSD)24. Computer20may comprise, for example, a mobile, tablet or personal computer. The computer comprises a Central Processing Unit (CPU)26that serves as a host.

In alternative embodiments, the host may comprise any other suitable processor or controller, and the storage device may comprise any other suitable device. For example, the host may comprise a storage controller of an enterprise storage system, and the storage device may comprise an SSD or an array of SSDs. Other examples of hosts that store data in non-volatile storage devices comprise mobile phones, digital cameras, media players and removable memory cards or devices.

SSD24stores data for CPU26in a non-volatile memory, in the present example in one or more NAND Flash memory devices34. In alternative embodiments, the non-volatile memory in SSD24may comprise any other suitable type of non-volatile memory, such as, for example, NOR Flash, Charge Trap Flash (CTF), Phase Change RAM (PRAM), Magnetoresistive RAM (MRAM) or Ferroelectric RAM (FeRAM).

An SSD controller30performs the various storage and management tasks of the SSD. The SSD controller is also referred to generally as a memory controller. SSD controller30comprises a host interface38for communicating with CPU26, a memory interface46for communicating with Flash devices34, and a processor42that carries out the various processing tasks of the SSD.

SSD24further comprises a volatile memory, in the present example a Random Access Memory (RAM)50. In the embodiment ofFIG. 1RAM50is shown as part of SSD controller30, although the RAM may alternatively be separate from the SSD controller. RAM50may comprise, for example a Static RAM (SRAM), a Dynamic RAM (DRAM), a combination of the two RAM types, or any other suitable type of volatile memory.

SSD controller30, and in particular processor42, may be implemented in hardware. Alternatively, the SSD controller may comprise a microprocessor that runs suitable software, or a combination of hardware and software elements.

The configuration ofFIG. 1is an exemplary configuration, which is shown purely for the sake of conceptual clarity. Any other suitable SSD or other memory system configuration can also be used. 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 some applications, e.g., non-SSD applications, the functions of SSD controller30are carried out by a suitable memory controller.

In the exemplary system configuration shown inFIG. 1, memory devices34and SSD controller30are implemented as separate Integrated Circuits (ICs). In alternative embodiments, however, the memory devices and the SSD 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 SSD controller circuitry may reside on the same die on which one or more of memory devices34are disposed. Further alternatively, some or all of the functionality of SSD controller30can be implemented in software and carried out by CPU26or other processor in the computer. In some embodiments, CPU26and SSD controller30may be fabricated on the same die, or on separate dies in the same device package.

In some embodiments, processor42of SSD controller30runs a management layer, typically implemented in software, which manages the data storage in Flash devices34. The management layer is referred to as Flash Translation Layer (FTL) or Flash management. As part of this management layer, processor42maintains one or more data structures, which store management information used in data storage in the Flash devices. The processor continuously updates the management information during operation of the SSD.

Processor42may maintain any suitable number and types of data structures, containing any suitable type of management information. One example type of data structure comprises a logical-to-physical address translation, which maps logical addresses (also referred to as Logical Block Addresses—LBAs) specified by the host into respective physical storage locations in Flash devices34.

In another example, the data structure may comprise a database of parameters of memory blocks of Flash devices34, e.g., usage information of the memory blocks, block status, and/or storage parameters used for data programming and readout in the memory blocks.

In the description that follows, processor42maintains two data structures—a logical-to-physical address translation table (also referred to as Virtual-to-Physical mapping—V2P) and a Block Database (BDB). At least part of the V2P and BDB is stored in RAM50. It is important to protect the management information stored in RAM50against power interruption, in order to avoid loss of management information. In many practical cases, loss of management information may cause severe damage to large amounts of stored data.

Robust Journaling Scheme

FIG. 2is a diagram that schematically illustrates a database journaling scheme, in accordance with an embodiment of the present invention. The present example shows a V2P table60and a BDB64. Processor42divides V2P table60into multiple slices62, and divides BDB64into multiple slices66. The slices of a given data structure are typically of uniform size.

In order to back-up the V2P table and the BDB to Flash devices34, processor42creates a sequence of journaling chunks68during operation of the SSD. Each journaling chunk68comprises a V2P snapshot field70for storing a respective slice62of V2P table60, a BDB snapshot field72for storing a respective slice66of BDB64, and a changes field74for storing the changes that occurred in the V2P table and in the BDB since the previous journaling chunk68. In an embodiment, each chunk comprises indications that point to the locations in the V2P table and in the BDB from which the respective slices were obtained.

Typically, processor42stores each journaling chunk68in Flash devices34as soon as the changes field74of the chunk fills-up. In other words, processor42continually updates changes field74of the current chunk with the changes that are made in the V2P table and in the BDB. When the changes field is full, i.e., when the accumulated changes reach the size of field74, processor42writes the journaling chunk to Flash devices34.

In this mode of operation, the rate of storing the chunks is variable and depends on the level of variability of the data structures. During idle times, the changes accumulate slowly and field74fills-up after a relatively long time period. During intensive storage activity, changes accumulate quickly, field74fills-up quickly, and therefore the rate of writing chunks to the Flash devices increases.

Typically, processor42scans V2P table60and BDB64cyclically, slice by slice. After storing the last slice of a given data structure in a chunk68, processor42typically wraps around and begins backing-up the first slice of the data structure again. Processor42holds pointers that track the locations of slices62and66that were most recently backed-up to the Flash devices. When reaching the end of a given data structure, the respective pointer wraps-around to the beginning of the data structure.

The memory space needed for storing chunks68should typically allow for storing a single instance of each data structure, plus additional memory space for storing the incremental changes. Typically, processor42tracks the locations in Flash devices34where the journaling chunks are stored. These locations are typically backed-up in the Flash devices, since they too may be lost in the event of power interruption.

It should be noted that in a given chunk68, the changes in field74do not necessarily relate to the specific slices62and66that are stored in fields70and72of the same chunk. Generally, the changes stored in a given chunk may relate to any part of the data structures.

Writing a given slice (62or66) to chuck68is typically defined as an atomic operation. In other words, processor42typically does not allow any changes to the data structures during writing of a given slice. The changes stored in chunks68may comprise various types of changes. Generally, however, the changes are defined so as to enable reconstruction of the entire data structure based on the slices and the changes.

FIG. 3is a flow chart that schematically illustrates a method for database journaling, in accordance with an embodiment of the present invention. The method begins with processor42of SSD controller30initializing a new chunk, and incrementing the cyclic pointers to point to the next slices62and66to be backed-up, at an initialization step80.

Processor42populates the current chunk with the next data structure slices, at a chunk population step84. In the present example, processor42copies the next V2P table slice62to field70of the current chunk, and copies the next BDB table slice66to field72of the current chunk.

Processor42begins to accumulate changes that are performed in the data structures (e.g., in the V2P mapping and in the BDB) during data storage in the SSD, at a change accumulation step88. Processor42adds the new changes to changes field74of the currently created chunk68. Processor42checks whether the changes field is full, at a checking step84.

If the changes field is not yet full, the method loops back to step88above and processor42continues to accumulate V2P and BDB changes. If the changes field is full, processor42stores the current chunk68in Flash devices34, at a chunk storage step96. The method then loops back to step80above to initialize and start filling the next chunk.

The flow ofFIG. 3is an example flow that is chosen purely for the sake of clarity. In alternative embodiments, any other suitable flow of operations can be used.

Database Reconstruction Following Power Interruption

When recovering from an electrical power interruption, processor42reconstructs V2P table60and BDB64using the journaling chunks stored in Flash devices34. In an example embodiment, processor42carries out the recovery process as follows (for a given data structure):Processor42identifies the most recent chunk68written to the Flash devices. This chunk is referred to as the last chunk.Using the known size of each data structure, processor42identifies the stored chunk68that holds the first valid slice of the data structure. This chunk is referred to as the first chunk.Processor42reads the stored chunks from the Flash devices, from the above-identified first chunk to the above-identified last chunk.For each read chunk, processor42copies the slice from the chunk to the appropriate location in RAM50. Processor42then reviews the changes in the read chunk. If a given change relates to a slice that was already recovered to the RAM, processor42applies the specified change. Otherwise, the processor discards the change without applying it (the change should be accounted for by a later slice to be copied from a later chunk).

Following this process, processor42restores the various pointers to the data structures, and moves to normal runtime operation. From this point, processor42continues to back-up the data structures using the method ofFIG. 3. If needed, a second recovery process can be performed using chunks that were stored before the first recovery. In other words, it is not necessary for processor42to perform a full baseline back-up of the data structure following recovery from power interruption.

FIG. 4is a diagram that schematically illustrates a database recovery scheme, in accordance with an embodiment of the present invention. The present example demonstrates several additional features of the disclosed techniques. In this example, multiple journaling chunks68are stored in parallel across N Flash dies, e.g., using multi-plane write commands. Recovery of the stored chunks can also be performed using multi-plane read commands. This sort of storage increases the speed of both back-up and recovery.

The arrows inFIG. 4mark the process of copying the V2P and BDB slices from the journaling chunks to the V2P and BDB in RAM50, and applying the changes specified in the chunks. Some of the arrows are marked “VALID”, meaning that processor42applies the respective changes. Changes that are discarded by the processor, as explained above, are marked “IRRELEVANT”.