Time sequence data management

• US 10,509,776 B2
• Filed: 03/14/2013
• Issued: 12/17/2019
• Est. Priority Date: 09/24/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Talagala, Nisha, Sundararaman, Swaminathan, Subramanian, Sriram, Peterson, James, Flynn, David
• Primary Examiner(s): Gurmu, Muluemebet
• Application Number:
  US13/830,809
• Publication Number:
  US 20140089265A1
• Time in Patent Office: 2,469 Days
• Field of Search: 707674
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

An apparatus, system, and method are disclosed for data management. The method includes writing data in a sequential log structure. The method also includes receiving a time sequence request from a client. The method further includes servicing the time sequence request based on a temporal order of the data in the sequential log structure.

Claims

1. A method comprising:

storing, in a memory device, a sequential, log-based writing structure comprising data and one or more epoch identifiers written with the data, wherein the one or more epoch identifiers are associated with one or more temporal ranges of data, and are stored in one or more metadata headers of the one or more associated temporal ranges of data;

preserving a temporal order of data in the sequential, log-based writing structure in response to storage capacity recovery events, wherein;

the storage capacity recovery events comprise garbage collection cycles that change a location of data within the sequential, log-based writing structure by relocating data from a storage region and erasing the storage region; and

preserving the temporal order comprises changing a location of an epoch identifier within the sequential, log-based writing structure by relocating the epoch identifier with the data; and

servicing a time sequence request comprising a snapshot request, by providing a client with read and write access to data corresponding to a snapshot epoch identifier, from the sequential, log-based writing structure, based on the temporal order, without affecting data associated with a current epoch identifier.

2. The method of claim 1, wherein the storage capacity recovery events write valid data from a set of storage media to an append point of the sequential, log-based writing structure.

3. The method of claim 1, wherein the one or more epoch identifiers mark the one or more temporal ranges of data.

4. The method of claim 2, wherein preserving the temporal order of the data in response to the storage capacity recovery events comprises retaining at least one version of data from each of a plurality of epochs.

5. The method of claim 1, wherein the data corresponding to the snapshot epoch identifier comprises a snapshot of data from a point in time based on the temporal order.

6. The method of claim 1, wherein:

the time sequence request further comprises a delta clone request; and

servicing the delta clone request comprises providing, to the client, changes to the data between points in time based on the temporal order.

7. The method of claim 6, wherein the changes to the data are provided in one or more of the temporal order and a logical address order for the data.

8. The method of claim 1, wherein:

the time sequence request further comprises a rollback request; and

servicing the rollback request comprises providing access to a previous state of the data based on the temporal order.

9. The method of claim 8, further comprising providing access to a state of the data adjacent in time to the previous state based on the temporal order in response to an iterate request.

10. The method of claim 8, further comprising determining a logical-to-physical mapping for the previous state of the data based on the temporal order, the logical-to-physical mapping comprising a mapping between logical addresses of the data and physical locations for the previous state of the data in the sequential, log-based writing structure.

11. The method of claim 8, wherein the previous state comprises a state of the data prior in the temporal order to a failed operation.

12. The method of claim 1, wherein:

the time sequence request further comprises an asynchronous replication request; and

servicing the asynchronous replication request comprises asynchronously replicating the data, in the temporal order, to a different storage location.

13. An apparatus comprising:

a log storage module configured to store, in a memory device, a sequential, log-based writing structure comprising data and one or more epoch identifiers written with the data, wherein the one or more epoch identifiers are associated with one or more chronological spans of data, and are stored in one or more metadata headers of the one or more associated chronological spans of data;

a temporal order module configured to preserve a temporal order of data in the sequential, log-based writing structure in response to storage capacity recovery events, wherein;

the storage capacity recovery events comprise garbage collection cycles that change a location of data within the sequential, log-based writing structure by relocating data from a storage region and erasing the storage region; and

preserving the temporal order comprises changing a location of an epoch identifier within the sequential, log-based writing structure by relocating the epoch identifier with the data; and

a time sequence interface module configured to service a time sequence request comprising a snapshot request, by providing a client with read and write access to data corresponding to a snapshot epoch identifier from the sequential, log-based writing structure, based on the temporal order, without affecting data associated with a current epoch identifier,

wherein at least a portion of the log storage module, the temporal order module, and the time sequence interface module comprise one or more of hardware and executable code, the executable code stored on one or more non-transitory computer readable storage media.

14. The apparatus of claim 13, further comprising a storage capacity recovery module configured to relocate a chronological span of data and an epoch identifier associated with the chronological span of data to a different append point of the sequential, log-based writing structure than an intake append point in response to a storage capacity recovery event.

15. The apparatus of claim 13, wherein the temporal order module is configured to increment an epoch identifier associated with a chronological span of data for association with a subsequent chronological span of data in response to a time sequence request comprising a new span request.

16. A system for time sequence data management, the system comprising:

a memory device configured to store a sequential, log-based writing structure comprising data and one or more epoch identifiers written with the data, wherein the one or more epoch identifiers are associated with one or more temporal ranges of data, and are stored in one or more metadata headers of the one or more associated temporal ranges of data;

a temporal order module configured to preserve a temporal order of data in the sequential, log-based writing structure in response to storage capacity recovery events, wherein;

the storage capacity recovery events comprise garbage collection cycles that change a location of data within the sequential, log-based writing structure by relocating data from a storage region and erasing the storage region; and

preserving the temporal order comprises changing a location of an epoch identifier within the sequential, log-based writing structure by relocating the epoch identifier with the data; and

a time sequence interface module configured to service a time sequence request comprising a snapshot request, by providing a client with read and write access to data corresponding to a snapshot epoch identifier, from the sequential, log-based writing structure, based on the temporal order, without affecting data associated with a current epoch identifier, wherein at least a portion of the temporal order module and the time sequence interface module comprise one or more of hardware and executable code, the executable code stored on one or more non-transitory computer readable storage media.

17. The system of claim 16, further comprising a host computing device in communication with the memory device, wherein the temporal order module and the time sequence interface module are configured to execute on the host computing device.

18. A computer program product comprising a non-transitory computer readable storage medium storing computer usable program code executable to perform operations for time sequence data management, the operations comprising:

marking a chronological period of data in a sequential journal with an era identifier in the sequential journal, wherein the era identifier that marks the chronological period of data is stored in one or more metadata headers of the chronological period of data;

preserving at least one version of data from the chronological period in the sequential journal in response to a storage capacity recovery event for the chronological period, wherein the storage capacity recovery event comprises a garbage collection cycle that changes a location of data and a location of the era identifier within the sequential journal by relocating data from a storage region, relocating the era identifier with the data, and erasing the storage region; and

providing a client with read and write access to a snapshot of the chronological period of data using the era identifier, without affecting data associated with a current era identifier.

19. The computer program product of claim 18, wherein marking the chronological period comprises storing the era identifier in one or more metadata headers for the chronological period of data.

20. The computer program product of claim 18, wherein marking the chronological period comprises storing the era identifier in the sequential journal at a beginning of the chronological period of data.

21. An apparatus for time sequence data management, the apparatus comprising:

means for maintaining data with one or more epoch identifiers in a sequential log writing structure, wherein the one or more epoch identifiers are associated with one or more temporal ranges of data, and are stored in one or more metadata headers of the one or more associated temporal ranges of data;

means for preserving, in response to a storage capacity recovery event, an order in which the data is written, wherein;

the storage capacity recovery event comprises a garbage collection cycle that changes a location of data within the sequential log writing structure by relocating data from a storage region and erasing the storage region; and

preserving the order comprises changing a location of an epoch identifier within the sequential log writing structure by relocating the epoch identifier with the data; and

means for servicing a time sequence request comprising a snapshot request, by providing a client with read and write access to data corresponding to a snapshot epoch identifier, based on the order in which the data is written, without affecting data associated with a current epoch identifier.

22. The apparatus of claim 21, further comprising means for asynchronously replicating the data, at a remote location, in the order in which the data is written.