Space accounting for storage system snapshots

Patent metadata

Field	Value
Publication number	US-9753932-B1
Application number	US-201715473051-A
Country	US
Kind code	B1
Filing date	Mar 29, 2017
Priority date	Feb 10, 2017
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

Abstract

A facility for snapshot space accounting for a storage system, such as a filesystem is disclosed. The facility enables users to quickly and easily determine the amount of storage space that would be released or recovered if a snapshot were to be purged. The facility may work in conjunction with, or as part of, a snapshot service. The facility maintains an expiration data structure and a count data structure and uses these data structures in implementing the disclosed snapshot space accounting techniques. The expiration data structure represents the life cycle of each snapshot element maintained by the facility while the count data structure represents, for pairs of snapshots, the size of the information stored in the snapshot data that expired and that spans the corresponding pair of snapshots.

First claim

We claim:

1. A method, performed by a computing system having one or more processors, for snapshot space accounting in a storage system, the method comprising:
receiving a request to write to a plurality of blocks of data within the storage system; and
in response to receiving the request to write to the plurality of blocks of data,
determining a current value for an epoch counter;
for each block of the plurality of blocks of data,
determining a previous birthdate associated with the block,
adding an expiration entry to an expiration data structure, wherein the expiration entry includes:
the determined previous birthdate for the block,
the current value for the epoch counter, and
an identifier for the block; and

determining that a count data structure includes an entry for a pair of snapshot values, the first snapshot value in the pair of snapshot values corresponding to the determined previous birthdate for the block and the second snapshot value in the pair of snapshot values corresponding to the current value for the epoch counter, and
in response to determining that the count data structure includes an entry for the pair of snapshot values, increasing a size associated with the entry by a size of the block of data.

2. The method of claim 1 , further comprising:
writing to each of the plurality of blocks of data within the storage system; and
storing, for each block, an indication of the current value for the epoch counter.

3. The method of claim 1 , further comprising:
receiving a request to determine the amount of storage space that would be recovered if at least one snapshot identified by the received request to determine the amount of storage space that would be recovered if at least one snapshot identified by the received request were purged;
in response to receiving the request, determining at least one range of two or more snapshots based at least in part on the at least one snapshot identified by the received request to determine the amount of storage space that would be recovered if at least one snapshot identified by the received request were purged;
generating a set of one or more chronologically-ordered snapshot pairs based at least in part on the determined range; and
for at least one chronologically-ordered snapshot pair of the generated set of one or more chronologically-ordered snapshot pairs,
querying the count data structure, and
determining a size for the chronologically-ordered snapshot pair based at least in part on a result of querying the count data structure.

4. The method of claim 3 , wherein determining the at least one range of two or more snapshots based at least in part on the at least one snapshot identified by the received request were purged comprises:
identifying one or more previously deleted snapshots that are chronologically adjacent to the at least one snapshot.

5. The method of claim 3 , wherein determining the size for at least one chronologically-ordered snapshot pair comprises:
receiving a query result for the at least one chronologically-ordered snapshot pair comprising a count value; and
generating a value based at least in part on the count value and a predetermined block size.

6. The method of claim 1 , further comprising:
receiving a request to purge at least one snapshot; and
in response to receiving the request to purge the at least one snapshot,
identifying a range of snapshots corresponding to the at least one snapshot,
wherein a first snapshot in the identified range of snapshots represents a birthdate of snapshot elements to be deleted and wherein a second snapshot in the identified range of snapshots represents an expiration date of snapshot elements to be deleted,
identifying one or more snapshot pairs based at least in part on the identified range of snapshots, and
for each snapshot pair of one or more of the identified one or more snapshot pairs,
identifying at least one snapshot element,
deleting the identified at least one snapshot element,
removing, from the expiration data structure, at least one entry corresponding to the identified at least one snapshot element, and
decrementing a value stored in the count data structure for the snapshot pair.

7. The method of claim 1 , further comprising:
for each of a plurality of chronologically-ordered snapshot pairs,
retrieving, from the count data structure, a value corresponding to the chronologically-ordered snapshot pair,
providing information usable to generate a graphical user interface element indicative of an amount of data that would be recovered if one or more snapshots corresponding to the chronologically-ordered snapshot pair were purged,
causing the graphical user interface element indicative of the amount of data that would be recovered if one or more snapshots corresponding to the chronologically-ordered snapshot pair were purged to be displayed.

8. The method of claim 7 , wherein a width of a first graphical user interface element caused to be displayed for a first chronologically-ordered snapshot pair of the plurality of chronologically-ordered snapshot pairs is determined based at least in part on the value retrieved from the count data structure for the first chronologically-ordered snapshot pair, and wherein a height of the first graphical user interface element is determined based at least in part on a difference between an identifier of each snapshot of the first chronologically-ordered snapshot pair.

9. The method of claim 1 , further comprising:
receiving an indication that a new snapshot has been generated; and
in response to receiving the indication that the new snapshot has been generated, incrementing the epoch counter.

10. A computer-readable medium storing instructions that, if executed by a computing system having a memory and a processor, cause the computing system to perform a method comprising:
receiving a request to write to a plurality of blocks of data within a storage system; and
in response to receiving the request to write to the plurality of blocks of data, determining a current value for an epoch counter;
for each block of the plurality of blocks of data, determining a previous birthdate associated with the block,
adding an expiration entry to an expiration data structure, wherein the expiration entry includes:
the determined previous birthdate for the block,
the current value for the epoch counter, and
an identifier for the block; and

determining that a count data structure includes an entry for a pair of snapshot values, the first snapshot value in the pair of snapshot values corresponding to the determined previous birthdate for the block and the second snapshot value in the pair of snapshot values corresponding to the current value for the epoch counter, and
in response to determining that the count data structure includes an entry for the pair of snapshot values, increasing a size associated with the entry by a size of the block of data.

11. The computer-readable medium of claim 10 , further comprising:
receiving an indication that a new snapshot has been generated; and
in response to receiving the indication that the new snapshot has been generated, incrementing the epoch counter.

12. The computer-readable medium of claim 11 , further comprising:
writing to each of the plurality of blocks of data within the storage system; and
storing, for each block, an indication of the current value for the epoch counter.

13. The computer-readable medium of claim 10 , the method further comprising:
receiving a request to determine the amount of storage space that would be recovered if at least one snapshot identified by the received

Assignees

• Qumulo Inc

Inventors

• Brow Edward
• Wilson Nicholas
• Gebert Robert
• Urban Thomas Scott
• Krasnow Michael Adam
• Haber Steven

Classifications

• G06F16/148

  File search processing · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title

• G06F16/162

  Delete operations (erasing in storage systems G06F3/0652) · 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/113

  Details of archiving (lifecycle management in storage systems G06F3/0649; point-in-time backing up or restoration of persistent data G06F11/1446) · CPC title