Technique to compute deltas between any two arbitrary snapshots in a deep snapshot repository
A differencing technique enables efficient retrieval of data from one of a substantial number of point-in-time images (e.g., snapshots) maintained over substantially long periods of time in a long-term storage service (LTSS) of an archival storage system. The LTSS efficiently retrieves the data by computing differences or deltas between any two arbitrary snapshots in accordance with a differencing procedure. According to the technique, the differencing procedure operates on one or more index tree structures configured to translate a logical offset range of snapshot data in a snapshot address space (e.g., of a file system) to a data object address space (e.g., of an object store hosting the snapshot data).
1 . A method for restoring data from an archival storage system comprising:
retrieving first and second index data structures each organized as a tree mapping a first address space of first and second snapshots respectively to a second address space of data objects stored at the archival storage system, wherein each node of the trees includes an identifier (ID) associated with a respective data object, wherein the index data structures reference data objects across an arbitrary number of snapshots;
organizing a reference (REF) set based on the first snapshot and a restore (RES) set based on the second snapshot;
acquiring a next level of node IDs from the first snapshot in the REF set;
acquiring a same next level of node IDs from the second snapshot pruned by the first address space in the RES set;
performing a first set subtraction of the REF set from the RES set to update the RES set; and
restoring the data from the data objects based on remaining node IDs in the subtracted RES set.
2 . The method of claim 1 further comprising:
determining whether any data is changed from the first snapshot to the second snapshot by comparing a root node ID of the first and second index data structures; and
in response to determining that the root node IDs are identical, indicating that no data is changed between the first and second snapshots.
3 . The method of claim 1 further comprising:
organizing leaf nodes IDs from the remaining node IDs of the REF set into a first set;
organizing the leaf node IDs from the remaining node IDs in the subtracted RES set into a second set;
performing a second set subtraction of the first set from the second set; and
determining a remaining set of extents stored in the data objects related to remaining leaf nodes IDs from the subtracted second set.
4 . The method of claim 3 further comprising:
determining whether the next level of nodes in the subtracted RES set are leaf nodes; and
in response to determining that the next level of nodes in the subtracted RES set are leaf nodes, computing locations of a remaining set of extents stored in the data objects related to the remaining leaf nodes IDs from the second set.
5 . The method of claim 1 further comprising:
determining whether node IDs remain in the subtracted RES set; and
in response to determining that node IDs remain in the subtracted RES set, indicating that no data is changed between the first and second snapshots.
6 . The method of claim 1 further comprising:
replicating the first snapshot from a primary site to the archival storage system; and
creating the first index data structure for retrieval via a long-term storage service.
7 . The method of claim 1 , wherein the first address space is native to a file system of the snapshots and the second address space is of the data objects of the archival storage system.
8 . The method of claim 1 , wherein missing address ranges of the node IDs are denoted as having no data for the set subtraction.
9 . The method of claim 1 , wherein leaf nodes of the index data structures include location information of extents in the data objects.
10 . A non-transitory computer readable medium including program instructions for
execution on a processor, the program instructions configured to:
retrieve first and second index data structures each organized as a tree mapping a first address space of first and second snapshots respectively to a second address space of data objects stored at an archival storage system, wherein each node of the trees includes an identifier (ID) associated with a respective data object, wherein the index data structures reference data objects across an arbitrary number of snapshots;
organize a reference (REF) set based on the first snapshot and a restore (RES) set based on the second snapshot;
acquire a next level of node IDs from the first snapshot in the REF set;
acquire a same next level of node IDs from the second snapshot pruned by the first address space in the RES set;
perform a first set subtraction of the REF set from the RES set to update the RES set; and
restore the data from the data objects based on remaining node IDs in the subtracted RES set.
11 . The non-transitory computer readable medium of claim 10 , wherein the program instructions further include program instructions configured to:
determine whether any data is changed from the first snapshot to the second snapshot by comparing a root node ID of the first and second index data structures; and
in response to determining that the root node IDs are identical, indicate that no data is changed between the first and second snapshots.
12 . The non-transitory computer readable medium of claim 10 , wherein the program instructions further include program instructions configured to:
organize leaf nodes IDs from the remaining node IDs of the REF set into a first set;
organize the leaf node IDs from the remaining node IDs in the subtracted RES set into a second set;
perform a second set subtraction of the first set from the second set; and
determine a remaining set of extents stored in the data objects related to remaining leaf nodes IDs from the subtracted second set.
13 . The non-transitory computer readable medium of claim 12 , wherein the program instructions further include program instructions configured to:
determine whether the next level of nodes in the subtracted RES set are leaf nodes; and
in response to determining that the next level of nodes in the subtracted RES set are leaf nodes, compute locations of a remaining set of extents stored in the data objects related to the remaining leaf nodes IDs from the second set.
14 . The non-transitory computer readable medium of claim 10 , wherein the program instructions further include program instructions configured to:
determine whether node IDs remain in the subtracted RES set; and
in response to determining that node IDs remain in the subtracted RES set, indicate that no data is changed between the first and second snapshots.
15 . The non-transitory computer readable medium of claim 10 , wherein the program instructions further include program instructions configured to:
replicate the first snapshot from a primary site to the archival storage system; and
create the first index data structure for retrieval via a long-term storage service.
16 . The non-transitory computer readable medium of claim 10 , wherein the first address space is native to a file system of the snapshots and the second address space is of the data objects of the archival storage system.
17 . The non-transitory computer readable medium of claim 10 , wherein missing address ranges of the node IDs are denoted as having no data for the set subtraction.
18 . The non-transitory computer readable medium of claim 10 , wherein leaf nodes of the index data structures include location information of extents in the data objects.
19 . An apparatus comprising:
a long-term storage service (LTSS) of an archival storage system, the LTSS configured to execute on a processor that is further configured to execute program instructions to,
retrieve first and second index data structures each organized as a tree mapping a first address space of first and second snapshots respectively to a second address space of data objects stored at an archival storage system, wherein each node of the trees includes an identifier (ID) associated with a respective data object, wherein the index data structures reference data objects across an arbitrary number of snapshots;
organize a reference (REF) set based on the first snapshot and a restore (RES) set based on the second snapshot;
acquire a next level of node IDs from the first snapshot in the REF set;
acquire a same next level of node IDs from the second snapshot pruned by the first address space in the RES set;
perform a first set subtraction of the REF set from the RES set to update the RES set; and
restore the data from the data objects based on remaining node IDs in the subtracted RES set.
20 . The apparatus of claim 19 wherein the program instructions further include program instructions to:
determine whether any data is changed from the first snapshot to the second snapshot by comparing a root node ID of the first and second index data structures; and
in response to determining that the root node IDs are identical, indicate that no data is changed between the first and second snapshots.
21 . The apparatus of claim 19 wherein the program instructions further include program instructions to:
organize leaf nodes IDs from the remaining node IDs of the REF set into a first set;
organize the leaf node IDs from the remaining node IDs in the subtracted RES set into a second set;
perform a second set subtraction of the first set from the second set; and
determine a remaining set of extents stored in the data objects related to remaining leaf nodes IDs from the subtracted second set.
22 . The apparatus of claim 21 wherein the program instructions further include program instructions to:
determine whether the next level of nodes in the subtracted RES set are leaf nodes; and
in response to determining that the next level of nodes in the subtracted RES set are leaf nodes, compute locations of a remaining set of extents stored in the data objects related to the remaining leaf nodes IDs from the second set.
23 . The apparatus of claim 19 wherein the program instructions further include program instructions to:
determine whether node IDs remain in the subtracted RES set; and
in response to determining that node IDs remain in the subtracted RES set, indicate that no data is changed between the first and second snapshots.
24 . The apparatus of claim 19 wherein the program instructions further include program instructions to:
replicate the first snapshot from a primary site to the archival storage system; and
create the first index data structure for retrieval via a long-term storage service.
25 . The apparatus of claim 19 , wherein the first address space is native to a file system of the snapshots and the second address space is of the data objects of the archival storage system.
26 . The apparatus of claim 19 , wherein missing address ranges of the node IDs are denoted as having no data for the set subtraction.
27 . The apparatus of claim 19 , wherein leaf nodes of the index data structures include location information of extents in the data objects.