Self-journaling and hierarchical consistency for non-volatile storage
First Claim
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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
15 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12)
-
-
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. - View Dependent Claims (14, 15)
-
Specification