Incremental vault to object store

Patent metadata

Field	Value
Publication number	US-11714724-B2
Application number	US-202217810101-A
Country	US
Kind code	B2
Filing date	Jun 30, 2022
Priority date	Sep 29, 2017
Publication date	Aug 1, 2023
Grant date	Aug 1, 2023

Abstract

Systems and methods for managing incremental data backups on an object store. A computing device receives first data representing a changed chunk of data in a revision of a data volume on a storage device, the changed chunk includes data having changes from previous data of a previous revision. The computing device creates a block of data representing a copy of the changed chunk on the object store, the object store also includes a previous revision block representing previous revision data. The computing device determines a previous index stored on the object store corresponding to the previous revision, which includes entries including at least one corresponding to the previous revision block. The computing device creates a copy of at least one previous index from the object store, and a revised index that updates the corresponding entry with updated entry data representing the change block.

First claim

What is claimed is:

1. A computer-implemented method executed by data processing hardware that causes the data processing hardware to perform operations comprising:
receiving first data representing a changed chunk of data in a current revision of a data volume stored on a storage device, the changed chunk of data comprising:
revised data having changes from a first portion of previous data of a previous revision of the data volume; and
original data unchanged from a second portion of previous data of the previous revision of the data volume;

generating a changed block of data representing a copy of the changed chunk of data for storage on the storage device as object data, the storage device further storing:
a copy of the first portion of previous data as a respective version of a first portion of object data; and
a copy of the second portion of previous data as a respective version of a second portion of object data;

generating, based on the changed block of data, an index corresponding to the current revision, the index including:
a first timestamp corresponding to the revised data and representative of a first time instance at which a copy of the revised data was generated for storage as object data, the first timestamp identifying the copy of the revised data as a most recent version of the first portion of object data; and
a second timestamp corresponding to the original data and representative of a second time instance at which the copy of the second portion of previous data was generated for storage as object data, the second timestamp identifying the copy of the second portion of previous data as a most recent version of the second portion of object data;

determining that a threshold period of time has passed from the first time instance; and
in response to determining that the threshold period of time has passed from the first time instance:
permanently deleting, based on the first timestamp identifying the copy of the revised data as the most recent version of the first portion of object data, the copy of the first portion of previous data from the storage device as object data; and
maintaining, based on the second timestamp identifying the second portion of previous data as the most recent version of the second portion of object data, the copy of the second portion of previous data on the storage device as object data.

2. The method of claim 1 , wherein the operations further comprise retrieving from storage on the storage device, using the index, the current revision of the data volume.

3. The method of claim 1 , wherein generating the index comprises:
determining a previous index stored on the storage device and corresponding to the previous revision of the data volume;
determining a first entry in the previous index identifying the first portion of previous data;
determining a second entry in the previous index identifying the second portion of previous data;
updating the first entry with entry data representing the revised data; and
maintaining entry data of the second entry representing the second portion of previous data.

4. The method of claim 3 , wherein generating the index further comprises storing the index on the storage device.

5. The method of claim 1 , wherein the operations further comprise:
determining a reliance of the data volume on the first portion of previous data;
updating, based on the reliance, the index to further include a third timestamp corresponding to the first portion of previous data and representative of a third time instance at which the reliance of the data volume on the first portion of previous data was determined;
determining that a second threshold period of time has passed from the third time instance; and
in response to determining that the threshold period of time has passed from the first time instance and that the second threshold period of time has passed from the third time instance, permanently deleting, based on the first timestamp identifying the copy of the revised data as the most recent version of the first portion of object data, the copy of the first portion of previous data from the storage device as object data.

6. The method of claim 1 , wherein the index further includes a third timestamp corresponding to the original data and representative of the first time instance, the third timestamp updating the second timestamp.

7. The method of claim 6 , wherein the third timestamp extends the second timestamp based on the first time instance.

8. The method of claim 1 , wherein the operations further comprise:
receiving a request to calculate a space reclamation amount from permanently deleting the copy of the first portion of previous data from the storage device as object data;
retrieving a plurality of indexes, each index of the plurality of indexes including index entries corresponding to a respective version of the first portion of object data, and the plurality of indexes including:
a previous index corresponding to the previous revision;
a subsequent index corresponding to a subsequent revision occurring after the current revision; and
a plurality of intermediate indexes, the plurality of intermediate indexes including the current revision, and each intermediate index of the plurality of intermediate indexes corresponding to a respective revision occurring between the previous revision and the subsequent revision;

determining, based on a number of intermediate indexes including index entries corresponding to a respective version of the first portion of object data different from both the respective version of the first portion of object data of the previous index and the respective version of the first portion of object data of the subsequent index, a tally of deletable blocks; and
determining, based on the tally of deletable blocks, the space reclamation amount.

9. The method of claim 8 , wherein determining the space reclamation amount comprises:
determining a storage size of each deletable block of the tally of deletable blocks;
determining a metadata size of each deletable block of the tally of deletable blocks; and
determining a sum of the storage sizes and the metadata sizes for the tally of deletable blocks.

10. The method of claim 1 , wherein generating the changed block of data comprises compressing the changed chunk of data.

11. A system comprising:
data processing hardware; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions executed on the data processing hardware that cause the data processing hardware to perform operations comprising:
receiving first data representing a changed chunk of data in a current revision of a data volume stored on a storage device, the changed chunk of data comprising:
revised data having changes from a first portion of previous data of a previous revision of the data volume; and
original data unchanged from a second portion of previous data of the previous revision of the data volume;

generating a changed block of data representing a copy of the changed chunk of data for storage on the storage device as object data, the storage device further storing:
a copy of the first portion of previous data as a respective version of a first portion of object data; and
a copy of the second portion of previous data as a respective version of a second portion of object data;

generating, based on the changed block of data, an index corresponding to the current revision, the index including:
a first timestamp corresponding to the revised data and representative of a first time instance at which a copy of the revised data was generated for storage as object data, the first timestamp iden

Assignees

• Google Llc

Inventors

• Murphy Christopher

Classifications

• G06F11/1451 Primary

  by selection of backup contents · CPC title

• G06F16/219

  Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477) · CPC title

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F2201/80

  Database-specific techniques · CPC title

• G06F2201/805

  Real-time · CPC title