US 8,527,558 B2Granted

Distributed garbage collection

AssigneeSepation, Inc.

InventorsStefan Merrill King, David Kopper

Life of this patent

Estimating the term…

Loading patent…

Abstract

Described are computer-based methods and apparatuses, including computer program products, for garbage collection. A garbage collection data structure is provided for deleting unused data objects. One or more object identifiers are stored in a first data structure in the garbage collection data structure. Each object identifier represents a data object about to be created but not yet assigned any references from other data objects. The first data structure prevents the data object from being deleted during creation of the data object but before one or more references are created to the data object. Data indicative of one or more objects is stored in a second data structure in the garbage collection data structure. The data includes one or more object identifiers, each object identifier representing a created data object. The data also includes one or more references to created data objects.

Claims20

Dependent claims

A method for deleting data objects in a distributed computer system, the method comprising:

creating, by a computer, a first data structure configured to store one or more object identifiers;
creating, by the computer, a second data structure configured to store at least one object identifier and one or more references to objects;
creating a copy of the second data structure;
storing, by the computer, the one or more object identifiers in the first data structure, each object identifier of the one or more object identifiers representing a corresponding data object about to be created but not yet assigned any references from other data objects;
identifying, within the copy of the second data structure, at least one first candidate object identifier representing at least one first candidate data object identified for deletion, at least one second candidate object identifier representing at least one second candidate data object identified for deletion and at least one third candidate object identifier representing at least one third candidate data object identified for deletion;
determining the at least one first candidate data object is being used;
in response to determining the at least one first candidate data object is being used, not deleting the at least one first candidate data object;
determining the at least one second candidate object identifier is stored within the first data structure;
in response to determining the at least one second candidate object identifier is stored within the first data structure, not deleting the at least one second candidate data object;
and
deleting the at least one third candidate data object.

8 more elements

An apparatus for deleting data objects in a distributed computer system, the apparatus comprising:

a memory configured to store a first data structure configured to store one or more object identifiers and a second data structure configured to store at least one object identifier and one or more references to objects;
a processor in communication with the memory configured to:
create the first data structure;
create the second data structure;
create a copy of the second data structure;
store the one or more object identifiers in the first data structure, each object identifier of the one or more object identifiers representing a corresponding data object about to be created but not yet assigned any references from other data objects;
identify, within the copy of the second data structure, at least one first candidate object identifier representing at least one first candidate data object identified for deletion, at least one second candidate object identifier representing at least one second candidate data object identified for deletion, and at least one third candidate object identifier representing at least one third candidate data object identified for deletion;
determine the at least one first candidate data object is being used;
in response to determining the at least one first candidate data object is being used, not deleting the at least one first candidate data object;
determine the at least one second candidate object identifier is stored within the first data structure;
in response to determining the at least one second candidate object identifier is stored within the first data structure, not deleting the at least one second candidate data object;
and
delete the at least one third candidate data object.

10 more elements

A computer program product, tangibly embodied in a non-transitory computer readable medium, the computer program product including instructions being configured to cause a data processing apparatus to execute a process for deleting data objects, the process including:

creating a first data structure configured to store one or more object identifiers;
creating a second data structure configured to store at least one object identifier and one or more references to objects;
creating a copy of the second data structure;
storing the one or more object identifiers in the first data structure, each object identifier of the one or more object identifiers representing a corresponding data object about to be created but not yet assigned any references from other data objects;
identifying, within the copy of the second data structure, at least one first candidate object identifier representing at least one first candidate data object identified for deletion, at least one second candidate object identifier representing at least one second candidate data object identified for deletion, and at least one third candidate object identifier representing at least one third candidate data object identified for deletion;
determining the at least one first candidate data object is being used;
in response to determining the at least one first candidate data object is being used, not deleting the at least one first candidate data object;
determining the at least one second candidate object identifier is stored within the first data structure;
in response to determining the at least one second candidate object identifier is stored within the first data structure, not deleting the at least one second candidate data object;
and
deleting the at least one third candidate data object.

8 more elements

Dependencies are inferred from the claim text.