Snapshot clustering techniques for multipart volumes

Patent metadata

Field	Value
Publication number	US-2020089574-A1
Application number	US-201916687361-A
Country	US
Kind code	A1
Filing date	Nov 18, 2019
Priority date	Mar 31, 2016
Publication date	Mar 19, 2020
Grant date	—

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

1 - 20 . (canceled)

21 . A computer-implemented method, comprising:
determining that individual snapshots of a plurality of snapshots are associated with a portion of a multipart block device by at least scanning the plurality of snapshots for one or more signatures; and identifying, from the individual snapshots, at least one cluster of snapshots, the at least one cluster of snapshots associated with a state of data stored in the multipart block device.

22 . The computer-implemented method of claim 21 , wherein the at least one cluster of snapshots is marked by at least updating a model associated with each snapshot of the at least one cluster of snapshots.

23 . The computer-implemented method of claim 22 , 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 respective vertices.

24 . The computer-implemented method of claim 21 , further comprising:
identifying, from the individual snapshots, an additional cluster of snapshots, the additional cluster of snapshots associated with a state of data stored in the multipart block device; and determining the at least one cluster of snapshots by comparing the at least one cluster of snapshots to the additional cluster of snapshots.

25 . The computer-implemented method of claim 21 , further comprising processing the plurality of snapshots using at least a snapshot block device emulator to mount each snapshot of the plurality of snapshots as respective snapshot block devices.

26 . The computer-implemented method of claim 21 , wherein the at least one cluster of snapshots is associated with the state and the multipart block device by updating respective models associated with the snapshots.

27 . The computer-implemented method of claim 26 , wherein the respective models are represented as directed acyclic graphs.

28 . A system, comprising:
one or more processors; and memory storing executable instructions that, as a result of being executed by the one or more processors, cause the system to:
scan a plurality of snapshots to detect one or more signatures indicative of association with at least a portion of a multipart block device; and
determine, based at least in part on individual snapshots, at least one cluster of snapshots that corresponds to a state of data stored in the multipart block device.

29 . The system of claim 28 , wherein the system scans each snapshot of the plurality of snapshots for the one or more signatures by locating information-specific locations within each snapshot, the information-specific locations being associated with presence or absence of the one or more signatures.

30 . The system of claim 28 , wherein the system analyzes the at least one cluster of snapshots using a nearest neighbor analysis or a heuristic analysis.

31 . The system of claim 28 , wherein the system further:
marks a subset of the individual snapshots to produce a set of marked snapshots; and selects the at least one cluster of snapshots from the set of marked snapshots.

32 . The system of claim 31 , wherein:
the system performs, using a first type of analysis, a first clustering analysis on the set of marked snapshots; the system performs, using a second type of analysis, a second clustering analysis on the set of marked snapshots; and the at least one cluster of snapshots is determined based at least in part on a comparison of results of the first clustering analysis and the second clustering analysis.

33 . The system of claim 32 , wherein the first type of analysis and the second type of analysis are different types of analyses.

34 . The system of claim 32 , wherein:
the first type of analysis and the second type of analysis are a matching type of analysis; and the first clustering analysis and the second clustering analysis use different respective clustering criteria as inputs.

35 . 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:
identify a set of snapshots associated with a portion of a multipart block device; individual snapshots reflecting contents of at least one block device allocated by a data storage system; use a common criterion for the set of snapshots to identify a cluster of snapshots associated with a state of data stored on the multipart block device; and associate a snapshot in the cluster of snapshots with the state of the multipart block device.

36 . The non-transitory computer-readable storage medium of claim 35 , wherein the executable instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to mount individual snapshots in the set of snapshots as emulated snapshot block devices.

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

38 . The non-transitory computer-readable storage medium of claim 35 , wherein the common criterion is a creation time at which the snapshot was generated.

39 . The non-transitory computer-readable storage medium of claim 35 , wherein:
a constituent block device of the multipart block device has a unique identifier; and a second snapshot associated with the portion of the multipart block device includes the unique identifier.

40 . The non-transitory computer-readable storage medium of claim 35 , wherein the executable instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to perform a plurality of different clustering analyses.

Assignees

• Amazon Tech Inc

Inventors

• Miah Mahmood
• Eddey Matthew James
• Yuhan John Sandeep

Classifications

• G06F11/1446

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

• G06F16/9024

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

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the 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

• G06F11/1451 Primary

  by selection of backup contents · CPC title