Snapshot mapping structure characterizing data dependencies between a storage volume and its snapshots

Patent metadata

Field	Value
Publication number	US-11797478-B1
Application number	US-202217721580-A
Country	US
Kind code	B1
Filing date	Apr 15, 2022
Priority date	Apr 15, 2022
Publication date	Oct 24, 2023
Grant date	Oct 24, 2023

Abstract

An apparatus comprises a processing device configured to maintain a snapshot mapping structure for a storage volume. The snapshot mapping structure comprises objects representing the storage volume and snapshots thereof. The objects are organized in a tree structure representing data dependencies between the storage volume and its snapshots. Each of the objects comprises a dynamic bitmap indicating whether that object contains new data for different offset positions relative to its ancestor objects in the tree structure. The processing device is further configured to detect operations directed to a specified one of the storage volume or one of its snapshots, to parse the snapshot mapping structure to identify objects to utilize for processing the operations, and to processing the operations utilizing the dynamic bitmaps of the identified objects.

First claim

What is claimed is:

1. An apparatus comprising:
at least one processing device comprising a processor coupled to a memory;
the at least one processing device being configured to perform steps of:
maintaining a snapshot mapping structure for a given storage volume, the snapshot mapping structure comprising a plurality of objects representing the given storage volume and one or more snapshots of the given storage volume, the plurality of objects being organized in a tree structure representing data dependencies between the given storage volume and the one or more snapshots, each of the plurality of objects comprising a dynamic bitmap indicating whether that object contains new data for different offset positions relative to one or more ancestor objects for that object in the tree structure;
detecting one or more operations directed to one of the given storage volume and a given one of the one or more snapshots;
parsing the snapshot mapping structure to identify respective ones of the plurality of objects in the snapshot mapping structure to utilize for processing the one or more operations; and
processing the one or more operations utilizing the dynamic bitmaps of the identified ones of the plurality of objects in the snapshot mapping structure.

2. The apparatus of claim 1 wherein a given one of the plurality of objects in the snapshot mapping structure comprises:
a position field indicating a given offset in the tree structure; and
a bitmap field comprising a series of bits indicating whether the given object has new data relative to its one or more ancestor objects in the tree structure at the given offset.

3. The apparatus of claim 2 wherein the given object further comprises a pack number field indicating a given pack number, the series of bits of the bitmap field indicating whether the given object has new data relative to its one or more ancestor objects in the tree structure at an index in an index vector of the tree structure that is a multiple of the given pack number.

4. The apparatus of claim 3 wherein the given offset comprises an integer multiple of a designated offset size.

5. The apparatus of claim 4 wherein the designated offset size is eight kilobytes, the position field is five bytes, the pack number field is one byte, and the bitmap field is four bytes.

6. The apparatus of claim 1 wherein each of the one or more snapshots of the given storage volume comprises one of:
a writeable snapshot of one of: the given storage volume; and another one of the one or more snapshots;
a read-only snapshot of one of: the given storage volume; and another one of the one or more snapshots; and
an internal snapshot comprising data that is used by at least one of: the given storage volume; and one or more other ones of the one or more snapshots.

7. The apparatus of claim 1 wherein:
a given one of the one or more operations comprises a write operation, the write operation specifying data to be written to a given address of said one of the given storage volume and the given snapshot;
parsing the snapshot mapping structure comprises identifying a given one of the plurality of objects corresponding to said one of the given storage volume and the given snapshot; and
processing the write operation utilizing the given object by updating the dynamic bitmap of the given object to indicate that new data exists at the given address of said one of the given storage volume and the given snapshot.

8. The apparatus of claim 1 wherein:
a given one of the one or more operations comprises a read operation, the read operation specifying data to be read from a given address of said one of the given storage volume and the given snapshot;
parsing the snapshot mapping structure comprises:
determining whether a given one of the plurality of objects corresponding to said one of the given storage volume and the given snapshot has new data at the given address relative to its one or more ancestor objects in the tree structure;
responsive to determining that the given object has new data at the given address relative to its one or more ancestor objects in the tree structure, processing the read operation utilizing the given object; and
responsive to determining that the given object does not have new data at the given address relative to its one or more ancestor objects, determining a closest one of the one or more ancestor objects that has new data at the given address and processing the read operation utilizing the closest ancestor object that has new data at the given address.

9. The apparatus of claim 1 wherein:
a given one of the one or more operations comprises a snapshot differential operation for finding the difference between the given snapshot and one of the given storage volume and another one of the one or more snapshots;
parsing the snapshot mapping structure comprises identifying a closest common ancestor object of a first one of the plurality of objects corresponding to the given snapshot and a second one of the plurality of objects corresponding to said one of the given storage volume and the other one of the one or more snapshots; and
processing the snapshot differential operation comprises identifying the difference between the given snapshot and said one of the given storage volume and the other one of the one or more snapshots as positions in the dynamic bitmaps of the first object and the second object which have changed relative to corresponding positions in the dynamic bitmap of the closest common ancestor object.

10. The apparatus of claim 1 wherein:
a given one of the one or more operations comprises a read-only snapshot creation operation for said one of the given storage volume and the given snapshot;
parsing the snapshot mapping structure comprises identifying a given one of the plurality of objects corresponding to said one of the given storage volume and the given snapshot; and
processing the read-only snapshot creation operation comprises:
creating a new object in the tree structure as a child of the given object;
associating the new object with said one of the given storage volume and the given snapshot; and
associating the given object with a read-only snapshot of said one of the given storage volume and the given snapshot.

11. The apparatus of claim 1 wherein:
a given one of the one or more operations comprises a writeable snapshot creation operation for said one of the given storage volume and the given snapshot;
parsing the dynamic bitmap of the snapshot mapping structure comprises identifying a given one of the plurality of objects corresponding to said one of the given storage volume and the given snapshot; and
processing the writeable snapshot creation operation comprises:
creating first and second new objects in the tree structure as a children of the given object;
associating the first new object with said one of the given storage volume and the given snapshot;
associating the second new object with a writeable snapshot of said one of the given storage volume and the given snapshot; and
converting the given object to an internal snapshot object.

12. The apparatus of claim 1 wherein:
a given one of the one or more operations comprises a snapshot deletion operation for the given snapshot;
parsing the snapshot mapping structure comprises identifying a given one of the plurality of objects corresponding to the given snapshot and identifying one or more descendant objects and one or more ancestor objects of the given object in the tree structure; and
processing the snapshot deletion operation by comparing dynamic bitmaps of the given object, the one or more descendant objects, and the one or more ancestor ob

Assignees

• Dell Products Lp

Inventors

• Shatsky Yosef
• Tal Doron

Classifications

• G06F11/1451

  by selection of backup contents · 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

• G06F3/065

  Replication mechanisms · CPC title

• G06F3/0626

  Reducing size or complexity of storage systems · CPC title

• G06F3/0673

  Single storage device · CPC title