Snapshot clustering techniques for multipart volumes

Patent metadata

Field	Value
Publication number	US-10481983-B1
Application number	US-201615087710-A
Country	US
Kind code	B1
Filing date	Mar 31, 2016
Priority date	Mar 31, 2016
Publication date	Nov 19, 2019
Grant date	Nov 19, 2019

Abstract

A snapshot analysis system analyzes a plurality of data snapshots taken in connection with data stored on a block device allocated by a data storage system. The snapshot analysis system may include an ingestor capable of initially detecting new snapshots and adding a root node for the snapshots. The system may include a block device analyzer that analyzes each snapshot to determine its contents, the relationship within data structures extant within the snapshot, and the snapshot's relationship to other snapshots and/or that of other block devices. The system may also include a clustering analyzer capable of determining whether snapshots are associated with multipart block devices, such as LVM or MD RAID devices. The system may further include a block device emulator that exposes data associated with a given snapshot as an addressable block device without necessitating retrieval or exposure of the full block device to which the snapshot is associated.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
under the control of one or more computer systems configured with executable instructions,
processing a plurality of snapshots, a respective snapshot of the plurality reflecting contents of at least one block device, by at least:
performing, for a respective snapshot of the plurality of snapshots, a first analysis comprising:
scanning the snapshot for one or more signatures that identifies whether the snapshot is associated with a portion of a multipart block device; and
marking the snapshot as multipart; and

performing, for a subset of snapshots of the plurality of snapshots and marked as multipart by the first analysis, a second analysis comprising:
determining at least one attribute being associated with the portion to which the snapshot is associated;
applying a clustering analysis to the subset of snapshots using the at least one attribute as an input;
determining, from the clustering analysis, at least one cluster of snapshots of the subset of snapshots that reflects a state of data stored in the multipart block device; and
marking each snapshot in the cluster of snapshots to identify the state and the multipart block device.

2. The computer-implemented method of claim 1 , wherein marking the snapshot as multipart and marking each snapshot in the cluster to identify state and the multipart block device includes updating a model associated with each snapshot.

3. The computer-implemented method of claim 2 , wherein the model is a directed acyclic graph, and wherein the state and the multipart block device are identified within the directed acyclic graph as vertices.

4. The computer-implemented method of claim 1 , further comprising:
applying a second clustering analysis to the subset of snapshots; and
determining the at least one cluster of snapshots by comparing results from the clustering analysis and the second clustering analysis.

5. A system, comprising:
at least one computing device configured to implement one or more services that at least:
process a plurality of snapshots of block devices allocated by a data storage system connected to the at least one computing device, by at least:
scanning a snapshot of the plurality of snapshots for one or more signatures that identify whether the snapshot is associated with a portion of a multipart block device;
if a scanned snapshot includes one or more signatures that identify the snapshot as associated with the portion, marking the scanned snapshot as multipart, thereby generating a marked set of snapshots; and
analyzing the marked set of snapshots to determine at least one cluster of snapshots of the marked set, the at least one cluster of snapshots associated with a state of data stored in the multipart block device.

6. The system of claim 5 , wherein the at least one computing device is configured to implement the one or more services to process the plurality of snapshots using at least a snapshot block device emulator to mount each snapshot of the plurality of snapshots as snapshot block devices.

7. The system of claim 5 , wherein the at least one computing device is configured to implement the one or more services to scan each snapshot of the plurality of snapshots for the one or more signatures by locating information specific locations within each snapshot, the information and the specific locations being associated with presence or absence of the one or more signatures.

8. The system of claim 5 , wherein the at least one computing device is configured to implement the one or more services to analyze the marked set of snapshots using a nearest neighbor analysis.

9. The system of claim 5 , wherein the at least one computing device is configured to implement the one or more services to analyze the marked set of snapshots using a heuristic analysis.

10. The system of claim 5 , wherein the at least one computing device is configured to implement the one or more services to further:
apply a second clustering analysis to the marked set; and
compare an outcome of the second clustering analysis to an outcome of the analyzing of the marked set of snapshots to determine the at least one cluster of snapshots.

11. The system of claim 10 , wherein the at least one computing device is configured to implement the one or more services to further analyze the marked set of snapshots and perform the second clustering analysis using different types of analyses.

12. The system of claim 10 , wherein the at least one computing device is configured to implement the one or more services to further analyze the marked set of snapshots and perform the second clustering analysis using the same type of analysis but using different respective clustering criteria as inputs.

13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
filter a plurality of snapshots, a snapshot reflecting contents of at least one block device allocated by a data storage system, to generate a subset of snapshots associated with a portion of a multipart block device;
determine at least one common criterion for the subset of snapshots;
analyze the subset of snapshots using the at least one common criterion and a clustering analysis to determine at least one cluster of snapshots that is associated with a state of data stored in the multipart block device; and
associate a snapshot in the cluster of snapshots with the state and the multipart block device.

14. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to analyze the subset of snapshots by mounting the snapshots as emulated snapshot block devices.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the emulated snapshot block devices are mounted as raw block devices.

16. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to associate the snapshots in the cluster of snapshots with the state and the multipart block device by updating respective models associated the snapshots.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the respective models include directed acyclic graphs.

18. The non-transitory computer-readable storage medium of claim 13 , wherein the at least one common criterion is a time at which the snapshot was generated.

19. The non-transitory computer-readable storage medium of claim 13 , wherein a constituent block device of the multipart block device has a unique identifier, and a second snapshot associated with the portion includes the unique identifier regardless of a difference of reflect states between the snapshot and the second snapshot.

20. The non-transitory computer-readable storage medium of claim 13 , wherein the clustering analysis includes a plurality of disparate analyses.

Assignees

• Amazon Tech Inc

Inventors

• Miah Mahmood
• Eddey Matthew James
• Yuhan John Sandeep

Classifications

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F11/1446

  Point-in-time backing up or restoration of persistent data · CPC title

• G06F16/128 Primary

  Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16) · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F11/1451 Primary

  by selection of backup contents · CPC title