Double writing map table entries in a data storage system to guard against silent corruption

A method for writing data in a data storage device includes: writing data to a physical memory location in a non-volatile memory; writing, for a first time, to a location in a volatile memory corresponding to a logical address of the data, a physical address of the physical memory location of the non-volatile memory containing the data; and writing, for a second time, to the location in the volatile memory corresponding to the logical address of the data, the address of the physical memory location of the non-volatile memory containing the data. The physical address of the physical memory location is written with appended error detection code information, and the error detection code information is determined based on the logical address of the data.

BACKGROUND

1. Technical Field

Apparatuses and methods consistent with the present inventive concept relate to data storage systems, and more particularly to double writing of map table entries in a data storage system to avoid silent corruption.

2. Related Art

Any data storage device that uses address indirection relies on a map table to point to a physical location of a latest copy of data at various logical page (L-page) addresses. Thus, the map table serves an important function of maintaining a logical-to-physical correspondence of stored data. Map table entries may be stored in volatile memory such as dynamic random access memory (DRAM). However, map table entries are susceptible to silent corruption.

DETAILED DESCRIPTION

While certain embodiments are described, these embodiments are presented by way of example only, and are not intended to limit the scope of protection. The methods and systems described herein may be embodied in a variety of other forms. Furthermore, various omissions, substitutions, and changes in the form of the example methods and systems described herein may be made without departing from the scope of protection.

Overview

Example embodiments of the present inventive concept provide a method of guarding against silent corruption in a data storage system.

FIG. 1is a block diagram illustrating a data storage system according to an example embodiment of the present inventive concept. The data storage system100may include a host120and a data storage device (DSD) such as a solid-state drive (SSD)110. The SSD110may include a control unit130, a volatile memory140, for example, but not limited to, a plurality of dynamic random access memory (DRAM) devices or other volatile memory, and a non-volatile memory150, for example, but not limited to, a non-volatile semiconductor memory (NVSM). The NVSM may be, for example, but not limited to, NAND flash memory devices, NOR flash memory devices, or other NVSM memory devices. The host120may issue data read and write commands to the SSD110. The volatile memory140may store a map table. A DSD is generally a device that electronically stores data, so in other embodiments, the DSD may additionally include other types of memory such as rotational magnetic media (e.g., a solid-state hybrid drive (SSHD)).

FIG. 2is a diagram illustrating a relationship between a map table and a non-volatile physical memory. As illustrated inFIGS. 1 and 2, the map table210may be arranged in the volatile memory140with memory locations215assigned according to a consecutive order (e.g., according to L-page address) and each memory location215may contain an entry of a physical address230of a physical memory location225in non-volatile memory150that holds data corresponding to a logical address of the data (L-page)235. The entries in the memory locations215in the map table210may be indexed at least in part according to the L-page235. Referring toFIG. 2, data corresponding to L-page0may be stored at a physical memory location225in the non-volatile memory150having a physical address230aaa, data corresponding to L-page1may be stored at a physical memory location225in the non-volatile memory150having a physical address230address bbb, etc. Thus, the map table210acts as a set of pointers to the physical memory locations225of L-page data in the non-volatile memory150. Each time L-page data is updated, the new data will be written to a new physical memory location225in the non-volatile memory150. Accordingly, the entries in the memory locations215in the map table210for the updated L-page data must also be updated to refer to the physical addresses230of the new physical memory locations225of the data in the non-volatile memory150.

FIG. 3is a diagram illustrating an occurrence of silent corruption in a map table. Silent corruption occurs when an update to the map table210is written to the wrong map table entry. Referring toFIGS. 1, 2, and 3, an example scenario is described which involves a new write to L-page address4001. In this example, the entry in the memory location215a(i.e., the E-page location) in the map table210in the volatile memory140corresponding to data for L-page4001should have been updated. However, the update was erroneously written to the map table entry in the memory location215bcorresponding to L-page C001in the L-page indexed map table210. This could be caused by a bit flip in the L-page address4001to C0001. Hence, the map table entry in the memory location215acorresponding to L-page4001points to stale data stored at the old physical address in the non-volatile memory150. This is an undetectable problem because on the next request for L-page4001by the host120, no mechanism exists to determine that the map table entry in the memory location215bcorresponding to L-page4001is stale.

In the map table210, the entry in the memory location215of the physical address230for the physical memory location225in the non-volatile memory150is written with error detection code information216, for example, but not limited to, cyclic redundancy code (CRC), a hash value, etc., appended to the entry. The error detection code information216is determined based at least in part on the L-page address235of the data stored at the physical memory location225in the non-volatile memory150. However, a check of the error detection code information216ain the map table entry in the memory location215acorresponding to the stale data at L-page4001will evaluate correctly since the error detection code information216ais seeded with the value of L-page4001. Accordingly, the stale data will be passed to the host120undetected. The undetectable the stale data problem is termed “silent corruption” of data. Note that, however, the error detection code information216bis effective in triggering an error condition, since error detection code information216bis generated based on L-page4001, but it is written in the entry for L-page C001which will generate a mismatch.

Double Writing Map Table Entries

Some embodiments of the present inventive concept provide a double writing procedure to write each map table update twice to guard against the undetectable problem of silent corruption where an update to an entry is erroneously written to an incorrect location leaving the intended location pointing to stale data.

As discussed above, when data corresponding to an L-page235is updated, the updated data is written to a different physical memory location225in non-volatile memory150than the original data. The updated data may be data received from a host120or may be data read from a physical address230of a physical memory location225in the non-volatile memory150, for example during garbage collection. In either case, the new physical address230corresponding to the updated data at the L-page235should be written to the map table210. In one embodiment, this is performed at least twice. First, the new physical address230is written to the map table entry in the memory location215corresponding to the L-page235for the data that was updated. Then, the same new physical address230is written a second time to the same map table entry in the memory location215.

By writing twice, the chance of silent corruption is reduced. Given that the probability of writing an update to the wrong location in the map table is 1/P, the probability of writing an update to the wrong location twice becomes 1/P×1/P=1/P2.

If both update attempts write to the same correct L-page indexed location of the map table210no problem is caused and a subsequent read at that L-page235would return the correct data.

FIG. 4is a flowchart illustrating a method for writing data in a storage device according to an example embodiment of the present inventive concept. Referring toFIGS. 1, 2, and 4, the control unit130may be configured to receive data for an L-page235cfrom a host120(410), and write the data to a physical memory location225cat a physical address yyy230cin the non-volatile memory150(420).

The control unit130may be configured to write for a first time the physical address yyy230cof the physical memory location225ccontaining the data corresponding to the L-page235cto the entry in the memory location215cin the map table210corresponding to the L-page235c(430). The control unit130may be further configured to write for a second time the physical address yyy230cto the entry in the memory location215c, thereby reducing the chance of silent corruption.

FIG. 5is a diagram illustrating detection of a map table error according to an example embodiment of the present inventive concept. As illustrated inFIG. 5, if one update attempt writes to the incorrect entry in the memory location215bin the map table210but the second update attempt writes to the correct entry in the memory location215ain the map table210, the intended entry in the memory location215ain the map table210will have been correctly updated. The update to the incorrect entry in the memory location215bin the map table210is detectable by the error detection code216b, for example, a CRC mismatch due to the fact that the CRC is L-page value seeded, and an error will be reported when the incorrectly updated entry in the memory location215bin the map table210is subsequently read.

Thus, example embodiments of the present inventive concept reduce the probability of map table errors resulting from update errors, and mitigate the undetectable silent corruption problem.

FIG. 6is a flow chart illustrating a method for writing data in a storage device after a memory read according to an example embodiment of the present inventive concept.FIGS. 7A and 7Bare diagrams illustrating a relationship between a map table and a physical memory a method for writing data in a storage device after a memory read according to an example embodiment of the present inventive concept.

Referring toFIGS. 1, 6, 7A, and 7B, the control unit130may be configured to read data corresponding to an L-page235cfrom a first physical location225cat a first physical address yyy230cin the non-volatile memory150(610), and to subsequently write the data corresponding to the L-page235cto a second physical memory location225dat a second physical address www230din the non-volatile memory150(620). The control unit130may be further configured to modify the data that was read before subsequently writing the data to the second physical memory location225d.

The control unit130may be configured to write for a first time the second physical address www230dof the second physical memory location225dcontaining the subsequently written data corresponding to the L-page235cto the entry in the memory location215c(630). The control unit130may be further configured to write for a second time the second physical address www230dto the entry in the memory location215c(640), thereby reducing the chance of silent corruption.

While certain embodiments have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the protection. The methods and systems described herein may be embodied in a variety of other forms. Various omissions, substitutions, and/or changes in the form of the example methods and systems described herein may be made without departing from the spirit of the protection.

The example embodiments disclosed herein can be applied to solid state drives, hybrid hard drives, and the like. Solid-state memory may comprise a wide variety of technologies, such as flash integrated circuits, Phase Change Memory (PC-RAM or PRAM), Programmable Metallization Cell RAM (PMC-RAM or PMCm), Ovonic Unified Memory (OUM), Resistance RAM (RRAM), NAND memory, NOR memory, EEPROM, Ferroelectric Memory (FeRAM), MRAM, or other discrete NVM (non-volatile solid-state memory) chips. In addition, other forms of storage, for example, but not limited to, DRAM or SRAM, battery backed-up volatile DRAM or SRAM devices, EPROM, EEPROM memory, etc., may additionally or alternatively be used. As another example, various components illustrated in the figures may be implemented as software and/or firmware on a processor, ASIC/FPGA, or dedicated hardware. Also, the features and attributes of the specific example embodiments disclosed above may be combined in different ways to form additional embodiments, all of which fall within the scope of the present disclosure.

Although the present disclosure provides certain example embodiments and applications, other embodiments that are apparent to those of ordinary skill in the art, including embodiments which do not provide all of the features and advantages set forth herein, are also within the scope of this disclosure. Accordingly, the scope of the present disclosure is intended to be defined only by reference to the appended claims.