Asynchronous distributed garbage collection for replicated storage clusters

A device of a plurality of devices in a distributed data replication system, the device comprising:

• means for identifying an object in a data store as having a negotiation message associated with the object;
• means for associating a new negotiation message with the object, the new negotiation message based on the status of the object;
• means for replicating the new negotiation message to a storage cluster;
• means for receiving other negotiation messages associated with a replica of the object;
• and
• means for deleting the object if the other negotiation messages indicate a successful negotiation.

A system, comprising:

• a memory to store instructions and a data store;
• and
• a processor to execute the instructions in the memory to:
• identify a status of an object in the data store, the status relating to whether the object has a reference and whether a delete negotiation message is associated with the object;
• write a new negotiation message to the object metadata based on the status of the object,
• replicate the metadata with the new negotiation message to one or more devices, and
• receive, from one of the one or more devices, other negotiation messages associated with the object,
• where the new negotiation message and the other negotiation messages provide a consensus for a delete negotiation of the object.

A computer-readable memory comprising computer-executable instructions, the computer-readable memory comprising:

• one or more instructions to identify a status of an object in a data store, the status relating to whether the object has a reference and whether a delete negotiation message is associated with the object;
• one or more instructions to write, to metadata of the object, a new negotiation message associated with the object based on the status of the object;
• one or more instructions to replicate the object metadata with the new negotiation message to a storage cluster;
• one or more instructions to receive, from one or more other devices, other negotiation messages associated with the object;
• and
• one or more instructions to determine consensus for a delete negotiation of the object based on the other negotiation messages associated with the object.