Garbage collection: timestamp entries and remove reference counts

Patent metadata

Field	Value
Publication number	US-10409692-B1
Application number	US-201715650651-A
Country	US
Kind code	B1
Filing date	Jul 14, 2017
Priority date	Jul 14, 2017
Publication date	Sep 10, 2019
Grant date	Sep 10, 2019

Abstract

One embodiment is related to a method for performing garbage collection at a backup system, comprising: determining an object that is present in a preceding backup but is no longer present in a present backup when or after the present backup is made; associating an indicator indicative of the preceding backup with the object in response to the determination that the object is no longer present in the present backup; determining whether the object is to be deleted from the backup system based on the indicator and a policy during garbage collection; and deleting the object in response to determining that the object is to be deleted.

First claim

What is claimed is:

1. A method for performing garbage collection at a backup system, comprising:
associating each of a plurality of objects on the backup system with a first property and a second property, wherein the first property indicates a first previous backup with which the associated object was first created, and the second property indicates a second previous backup in which the associated object was present for a last time, and wherein the second property is left empty after creation of the associated object until the associated object has determined to be no longer present in a present backup;
determining a first object that is present in a preceding backup but is no longer present in the present backup when or after the present backup is made;
associating an indicator indicative of the preceding backup with the first object in response to the determination that the first object is no longer present in the present backup, wherein the indicator comprises the second property associated with the first object that indicates the preceding backup in which the first object was present for a last time;
determining whether the first object is to be deleted from the backup system based on the indicator and a policy during garbage collection; and
deleting the first object in response to determining that the first object is to be deleted.

2. The method of claim 1 , wherein the first object is a data object.

3. The method of claim 1 , wherein the first object is a metadata object.

4. The method of claim 1 , wherein the first object corresponds to a file, a directory, or a composite.

5. The method of claim 1 , wherein the second property that indicates the preceding backup comprises a time of the preceding backup.

6. The method of claim 5 , wherein the time is represented in one of: Portable Operating System Interface (POSIX) time or Microsoft time.

7. The method of claim 1 , wherein the indicator comprises values of cells in a row corresponding to the first object in a bitmap table, wherein columns of the bitmap table correspond to backups.

8. A non-transitory machine-readable medium having instructions stored therein which, when executed by a processor, cause the processor to perform storage operations, the operations comprising:
associating each of a plurality of objects on the backup system with a first property and a second property, wherein the first property indicates a first previous backup with which the associated object was first created, and the second property indicates a second previous backup in which the associated object was present for a last time, and wherein the second property is left empty after creation of the associated object until the associated object has determined to be no longer present in a present backup;
determining a first object that is present in a preceding backup but is no longer present in the present backup when or after the present backup is made;
associating an indicator indicative of the preceding backup with the first object in response to the determination that the first object is no longer present in the present backup, wherein the indicator comprises the second property associated with the first object that indicates the preceding backup in which the first object was present for a last time;
determining whether the first object is to be deleted from the backup system based on the indicator and a policy during garbage collection; and
deleting the first object in response to determining that the first object is to be deleted.

9. The non-transitory machine-readable medium of claim 8 , wherein the first object is a data object.

10. The non-transitory machine-readable medium of claim 8 , wherein the first object is a metadata object.

11. The non-transitory machine-readable medium of claim 8 , wherein the first object corresponds to a file, a directory, or a composite.

12. The non-transitory machine-readable medium of claim 8 , wherein the second property that indicates the preceding backup comprises a time of the preceding backup.

13. The non-transitory machine-readable medium of claim 12 , wherein the time is represented in one of: Portable Operating System Interface (POSIX) time or Microsoft time.

14. The non-transitory machine-readable medium of claim 8 , wherein the indicator comprises values of cells in a row corresponding to the first object in a bitmap table, wherein columns of the bitmap table correspond to backups.

15. A data processing system, comprising:
a processor; and
a memory coupled to the processor storing instructions which, when executed by the processor, cause the processor to perform storage operations, the operations including
associating each of a plurality of objects on the backup system with a first property and a second property, wherein the first property indicates a first previous backup with which the associated object was first created, and the second property indicates a second previous backup in which the associated object was present for a last time, and wherein the second property is left empty after creation of the associated object until the associated object has determined to be no longer present in a present backup;
determining a first object that is present in a preceding backup but is no longer present in the present backup when or after the present backup is made;
associating an indicator indicative of the preceding backup with the first object in response to the determination that the first object is no longer present in the present backup, wherein the indicator comprises the second property associated with the first object that indicates the preceding backup in which the first object was present for a last time;
determining whether the first object is to be deleted from the backup system based on the indicator and a policy during garbage collection; and
deleting the first object in response to determining that the first object is to be deleted.

16. The data processing system of claim 15 , wherein the first object is a data object.

17. The data processing system of claim 15 , wherein the first object is a metadata object.

18. The data processing system of claim 15 , wherein the first object corresponds to a file, a directory, or a composite.

19. The data processing system of claim 15 , wherein the second property that indicates the preceding backup comprises a time of the preceding backup.

20. The data processing system of claim 19 , wherein the time is represented in one of: Portable Operating System Interface (POSIX) time or Microsoft time.

21. The data processing system of claim 15 , wherein the indicator comprises values of cells in a row corresponding to the first object in a bitmap table, wherein columns of the bitmap table correspond to backups.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Brenner Adam
• Norton Jeffrey
• Starling Jennifer
• Malamut Mark
• Li Junxu

Classifications

• G06F11/1453

  using de-duplication of the data · CPC title

• G06F11/1451 Primary

  by selection of backup contents · CPC title

• G06F3/0671

  In-line storage system · CPC title

• G06F3/0652

  Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket · CPC title

• G06F12/0253

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title