ASYNCHRONOUS DISTRIBUTED GARBAGE COLLECTION FOR REPLICATED STORAGE CLUSTERS

• US 20100161688A1
• Filed: 12/22/2009
• Published: 06/24/2010
• Est. Priority Date: 12/22/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: KESSELMAN, Alexander, DROBYCHEV, Alexandre
• Granted Patent: US 8,346,820 B2
• Time in Patent Office: Days
• US Class Current: 707/813
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method may be performed by a device of a group of devices in a distributed data replication system. The method may include storing objects in a data store, at least one or more of the objects being replicated with the distributed data replication system, and conducting a scan of the objects in the data store. The method may further include identifying one of the objects as not having a reference pointing to the object, storing a delete negotiation message as metadata associated with the one of the objects, and replicating the metadata with the delete negotiation message to one or more other devices of the group of devices.

Claims

1. A method performed by a device of a plurality of devices in a distributed data replication system, the method comprising:

storing objects in a data store, at least one or more of the objects being replicated with the distributed data replication system;

conducting a scan of the objects in the data store;

identifying one of the objects as not having a reference pointing to the object;

storing a delete negotiation message as metadata associated with the one of the objects; and

replicating the metadata with the delete negotiation message to one or more other devices of the plurality of devices.

2. The method of claim 1, where the metadata with the delete negotiation message is replicated using an underlying replication layer of the distributed multi-master data replication system.

3. The method of claim 1, further comprising:

identifying another one of the objects as having another delete negotiation message in metadata associated with the another one of the objects.

4. The method of claim 3, further comprising:

storing one of an acknowledgement, a negative acknowledgement, or a confirmation to the another delete negotiation message as metadata associated with the another one of the objects; and

replicating the metadata of the another one of the objects with the acknowledgement or the negative acknowledgement to the delete negotiation message to one or more other devices of the plurality of devices.

5. The method of claim 3, further comprising:

deleting the negotiation message from the object metadata if another delete negotiation message indicates a failed negotiation.

6. The method of claim 3, further comprising:

deleting the object if another delete negotiation message indicates a successful negotiation.

7. The method of claim 1, where storing the delete negotiation message includes:

writing a negotiation message indicator, a storage cluster identification, and a unique negotiation request identification.

8. The method of claim 1, where new references cannot be added to the one of the objects with the delete negotiation message.

9. 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.

10. The system of claim 9, further comprising:

means for deleting the new negotiation message and the other negotiation messages if the other negotiation messages indicate a failed negotiation.

11. 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.

12. The system of claim 11, where the new negotiation messages and the other negotiation messages are embedded in metadata associated with the object and where the negotiation messages are exchanged using a replication layer in a distributed multi-master data replication environment.

13. The system of claim 12, where the processor is further configured to:

delete the new negotiation message from the object metadata if the terminal status indicates a failed delete negotiation.

14. The system of claim 12, where the processor is further configured to:

delete the object if the terminal status indicates a successful delete negotiation.

15. The system of claim 11, where the new negotiation message comprises:

a negotiation message indicator;

a storage cluster identification, and

a unique negotiation request identification.

16. The system of claim 15, where the negotiation message indicator includes one of:

a delete indicator for initiating a delete negotiation,

an acknowledgement indicator for providing a positive acknowledgement to the delete negotiation,

a negative acknowledgement indicator for providing a negative acknowledgement to the delete negotiation, or

a synchronization indicator for providing a confirmation that acknowledgements have been received from other of storage clusters.

17. A method, comprising:

exchanging, among storage clusters within a distributed multi-master data replication system, one or more delete negotiation messages, where each of the delete negotiation messages is included in metadata of an object that is the subject of the delete negotiation message, and where the delete negotiation message is sent among the storage clusters using a replication layer of the distributed multi-master data replication system; and

deleting the object if a distributed consensus is reached among the storage clusters based on the one or more delete negotiation messages.

18. The method of claim 17, where each of the delete negotiation messages includes:

a negotiation message indicator,

a storage cluster identification, and

a unique negotiation request identification.

19. The method of claim 17, where the negotiation message indicator includes:

a delete indicator for initiating a delete negotiation,

an acknowledgement indicator for providing a positive acknowledgement to the delete negotiation,

a negative acknowledgement indicator for providing a negative acknowledgement to the delete negotiation, and

a synchronization indicator for providing a confirmation that acknowledgements have been received from other of storage clusters.

20. The method of claim 19, where the delete indicator or the acknowledgement indicator preclude the storage cluster that initiated the delete indicator or the acknowledgement indicator from adding new references to the object.

21. 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.

22. The computer-readable memory of claim 21, further comprising:

one or more instructions to delete the new negotiation message and the other negotiation messages if the consensus indicates a failed negotiation; and

one or more instructions to delete the object if the consensus indicates a successful negotiation.

23. The computer-readable memory of claim 21, further comprising:

one or more instructions to maintain the write-order fidelity of the new negotiation message and the other negotiation messages.

24. The computer-readable memory of claim 21, further comprising:

one or more instructions to preclude adding new references to the object after a delete negotiation message has been initiated.