Self-journaling and hierarchical consistency for non-volatile storage

• US 8,949,517 B2
• Filed: 10/04/2012
• Issued: 02/03/2015
• Est. Priority Date: 10/05/2011
• Status: Expired due to Fees

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Cohen, Earl T, Canepa, Timothy L
• Primary Examiner(s): Bradley, Matthew
• Assistant Examiner(s): TSUI, DANIEL D
• Application Number:
  US13/988,019
• Publication Number:
  US 20140082261A1
• Time in Patent Office: 852 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 11/07 Responding to the occurrence of a fault, e.g. fault tolerance
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 16/02 electrically programmable
• CPC Class Codes: G11C 16/06 Auxiliary circuits, e.g. for writing into memory

Abstract

A non-volatile storage system having Non-Volatile Memory (NVM) provides self-journaling and hierarchical consistency, enabling low-latency recovery and force unit access handshake. Mappings between host addresses and addresses in the NVM are maintained via one or more map entries, enabling locating of host data written to the NVM. Objects stored in the NVM include sufficient information to recover the object solely within the object itself. The NVM is managed as one or more data streams, a map stream, and a checkpoint stream. Host data is written to the data streams, map entries are written to the map stream, and checkpoints of map entries and other data structures are written to the checkpoint stream. Time markers embedded in the streams enable determination, during recovery, that selected portions of the streams are inconsistent with each other and are to be discarded.

Claims

1. A system comprising:

means for arranging a series of data units in a Non-Volatile Memory (NVM) in a first order, each of the data units associated with a respective one of a plurality of timestamps;

means for arranging a series of data map units in the NVM in a second order, each of the data map units associated with a respective one of the timestamps;

means for determining a latest valid and contiguous one of the data units;

means for determining a latest valid and contiguous one of the data map units, wherein the respective timestamp associated with the latest valid and contiguous one of the data map units is at or before the respective timestamp associated with the latest valid and contiguous one of the data units;

means for recovering only ones of the data map units up to the latest valid and contiguous one of the data map units;

wherein each of the data map units comprises a location in the NVM of a corresponding one of the data units;

wherein the respective timestamp associated with each of the data units is at or before the respective timestamp associated with the corresponding data map unit; and

whereby any of the data map units associated with any of the respective timestamps after the respective timestamp associated with the latest valid and contiguous one of the data units are ignored in recovery.

2. The system of claim 1, wherein:

each of the data units corresponds to a respective data write from a host to a respective Logical Block Address (LBA);

a prior one and a subsequent one of the data units correspond to ones of the data writes to a same one of the respective LBAs; and

the prior data unit does not have an associated one of the data map units.

3. The system of claim 1, further comprising a means for interfacing with a host to communicate information read from and/or written to the NVM.

4. The system of claim 3, wherein the means for interfacing is compatible with one or more of

a Universal Serial Bus (USB) interface standard,

a Compact Flash (CF) interface standard,

a MultiMediaCard (MMC) interface standard,

an embedded MMC (eMMC) interface standard,

a Thunderbolt interface standard,

a UFS interface standard,

a Secure Digital (SD) interface standard,

a Memory Stick interface standard,

an xD-picture card interface standard,

an Integrated Drive Electronics (IDE) interface standard,

a Serial Advanced Technology Attachment (SATA) interface standard,

an external SATA (eSATA) interface standard,

a Small Computer System Interface (SCSI) interface standard,

a Serial Attached Small Computer System Interface (SAS) interface standard,

a Fibre Channel interface standard,

an Ethernet interface standard, and

a Peripheral Component Interconnect express (PCIe) interface standard.

5. The system of claim 3, wherein the host comprises one or more of

a computer,

a workstation computer,

a server computer,

a storage server,

a Storage Attached Network (SAN),

a Network Attached Storage (NAS) device,

a Direct Attached Storage (DAS) device,

a storage appliance,

a Personal Computer (PC),

a laptop computer,

a notebook computer,

a netbook computer,

a tablet device or computer,

an ultrabook computer,

an electronic reading device (an e-reader),

a Personal Digital Assistant (PDA),

a navigation system,

a (handheld) Global Positioning System (GPS) device,

an automotive control system,

an automotive media control system or computer,

a printer, copier or fax machine or all-in-one device,

a Point Of Sale (POS) device,

a cash-register,

a media player,

a television,

a media recorder,

a Digital Video Recorder (DVR),

a digital camera,

a cellular handset,

a cordless telephone handset, and

an electronic game.

6. The system of claim 5, further comprising all or any portions of the host.

7. The system of claim 1, further comprising a means for interfacing with one or more flash memories comprising all or portions of the NVM.

8. The system of claim 7, wherein the means for interfacing is compatible with one or more of

an Open NAND Flash Interface (ONFI),

a Toggle-mode interface,

a Double-Data-Rate (DDR) synchronous interface,

a DDR2 synchronous interface;

a synchronous interface, and

an asynchronous interface.

9. The system of claim 7, wherein at least one of the flash memories comprises one or more of

NAND flash technology storage cells, and

NOR flash technology storage cells.

10. The system of claim 7, wherein at least one of the flash memories comprises one or more of

Single-Level Cell (SLC) flash technology storage cells, and

Multi-Level Cell (MLC) flash technology storage cells.

11. A system comprising:

means for writing a series of data storage units in a Non-Volatile Memory (NVM), each of the data storage units associated with a respective one of a plurality of timestamps;

means for writing a series of data map units in the NVM, each of the data map units associated with a respective one of the timestamps, and wherein the writing of the data storage units is in accordance with a first order and the writing of the data map units is in accordance with a second order;

means for determining, in accordance with the first order, a latest valid and contiguous one of the data storage units;

means for determining, in accordance with the second order, a latest valid and contiguous one of the data map units associated with a one of the respective timestamps indicating a relative age that is identical to or older than a relative age indicated by the respective timestamp associated with the latest valid and contiguous one of the data storage units;

means for recovering, in accordance with the first and the second orders, only ones of the data map units up to the latest valid and contiguous one of the data map units;

wherein each of the data map units comprises a location in the NVM of a corresponding one of the data storage units; and

wherein the respective timestamp associated with each of the data storage units indicates a relative age that is identical to or older than a relative age indicated by the respective timestamp associated with the corresponding data map unit.

12. The system of claim 11, wherein:

a first one of the data storage units corresponds to a first data write from a host to a particular Logical Block Address (LBA);

a second one of the data storage units corresponds to a second data write from the host to the particular LBA;

the first data write precedes, in time order, the second data write; and

none of the data map units correspond to the first data storage unit.

13. A system comprising:

means for writing a series of data storage units in a Non-Volatile Memory (NVM), each of the data storage units associated with a respective one of a plurality of timestamps;

means for writing a series of data map units in the NVM, each of the data map units associated with a respective one of the timestamps, and wherein the writing of the data storage units is in accordance with a first order and the writing of the data map units is in accordance with a second order;

means for determining, in accordance with the first order, a first one of the data storage units that is a latest valid and contiguous one of the data storage units;

means for determining, in accordance with the second order, a latest valid and contiguous one of the data map units associated with a one of the respective timestamps indicating a relative age that is identical to or older than a relative age indicated by the respective timestamp associated with the latest valid and contiguous one of the data storage units;

means for determining, in accordance with the first order, a second one of the data storage units that is a latest one of the data storage units associated with a one of the respective timestamps indicating a relative age that is identical or prior to a determined amount preceding the relative age indicated by the respective timestamp associated with the latest valid and contiguous one of the data map units;

means for recovering, in accordance with the first and second orders, ones of the data map units up to the latest valid and contiguous one of the data map units using ones of the data units solely from the second of the data storage units through the first of the data storage units;

wherein each of the data map units comprises a location in the NVM of a corresponding one of the data storage units; and

wherein the respective timestamp associated with each of the data storage units indicates a relative age that is identical to or older than a relative age indicated by the respective timestamp associated with the corresponding data map unit.

14. The system of claim 13, further comprising:

means for identifying, for each modified one of the data map units not previously written to the NVM, a respective one of the timestamps associated with an oldest update equal to the respective timestamp associated with a particular one of the data storage units, the modified data map unit comprising the location in the NVM of the particular data storage unit; and

means for writing each of the modified data map units not previously written to the NVM, to the NVM at or prior to writing one of the data storage units associated with a one of the respective timestamps more than the determined amount following the respective timestamp associated with the oldest update of the modified data map unit.

15. The system of claim 13, wherein:

a first one of the data storage units corresponds to a first data write from a host to a particular Logical Block Address (LBA);

a second one of the data storage units corresponds to a second data write from the host to the particular LBA;

the first data write precedes, in time order, the second data write; and

none of the data map units correspond to the first data storage unit.