Weakly synchronized garbage collection and compaction for aggregated, replicated object stores

Patent metadata

Field	Value
Publication number	US-9396202-B1
Application number	US-201314142662-A
Country	US
Kind code	B1
Filing date	Dec 27, 2013
Priority date	Dec 27, 2013
Publication date	Jul 19, 2016
Grant date	Jul 19, 2016

Abstract

Managing consistency of object replicas is performed at a first instance of a distributed storage system. The first instance performs garbage collection on a shard that includes a first plurality of object chunks, thereby removing a second plurality of object chunks from the shard. This leaves a third plurality of object chunks in the shard, where the first plurality of object chunks is the union of the second and third pluralities of object chunks. The first instance sends a first list of identifiers to a second instance of the distributed storage system. The second instance has a replica of the shard. The first list of identifiers specifies the object chunks in the third plurality of object chunks. The second instance removes all object chunks from the replica of the shard that are not included in the first list.

First claim

What is claimed is:

1. A method for managing consistency of object replicas in a distributed storage system, comprising:
at a first instance of the distributed storage system, having one or more processors and memory, wherein the memory stores one or more programs for execution by the one or more processors:
performing garbage collection and compaction on a first shard comprising a first plurality of object chunks, thereby removing a second plurality of object chunks from the first shard and leaving a third plurality of object chunks in the first shard, wherein the first plurality of object chunks is the union of the second and third pluralities of object chunks;
sending a first list of identifiers to a second instance of the distributed storage system, wherein the second instance has a replica of the first shard and wherein the first list of identifiers specifies the object chunks in the third plurality of object chunks; and

at the second instance, having one or more processors and memory, wherein the memory stores one or more programs for execution by the one or more processors:
compacting the replica of the first shard to remove all object chunks that are not included in the first list.

2. The method of claim 1 , further comprising:
after removing the second plurality of object chunks from the first shard, assigning a compaction identifier to the first shard based on the first list of identifiers; and
after removing all object chunks from the replica of the first shard that are not included in the first list, assigning a replica compaction identifier to the replica of the first shard based on a second list of identifiers of object chunks in the replica of the first shard after removal of object chunks not included in the first list;
wherein the compaction identifier and the replica compaction identifier are the same when the first list is the same as the second list.

3. The method of claim 2 , wherein the compaction identifier for the first shard is computed as a function of an ordered list of chunk identifiers included in the first shard.

4. The method of claim 3 , wherein the function is a hash function.

5. The method of claim 2 , further comprising:
performing a bitwise comparison of data in the first shard with data in the replica of the first shard when the compaction identifier of the first shard matches the replica compaction identifier of the replica of the first shard; and
when the bitwise comparison shows that the replica of the first shard is not identical to the first shard, identifying one or more object chunks within the first shard that are not identical to corresponding object chunks in the replica of the first shard.

6. The method of claim 1 , wherein compacting the replica of the first shard comprises constructing a new replica of the first shard that includes object chunks from the replica of the first shard that are in the first list, updating object metadata to specify the new replica as storing the object chunks in the new replica, and deleting the replica of the first shard.

7. The method of claim 6 , wherein constructing the new replica comprises retaining the order of object chunks as previously stored in the replica.

8. The method of claim 6 , wherein constructing the new replica comprises storing object chunks in order by chunk identifiers corresponding to stored object chunks.

9. The method of claim 1 , wherein the first and second instances are at distinct geographic locations.

10. A computer system for managing consistency of object replicas in a distributed storage system, comprising:
a first instance and a second instance, each having
one or more processors;
memory; and
one or more programs stored in the memory, the one or more programs comprising instructions executable by the one or more processors;

wherein the one or more programs at the first instance include instructions for:
performing garbage collection and compaction on a first shard comprising a first plurality of object chunks, thereby removing a second plurality of object chunks from the first shard and leaving a third plurality of object chunks in the first shard, wherein the first plurality of object chunks is the union of the second and third pluralities of object chunks;
sending a first list of identifiers to a second instance of the distributed storage system, wherein the second instance has a replica of the first shard and wherein the first list of identifiers specifies the object chunks in the third plurality of object chunks; and

wherein the one or more programs at the second instance include instructions for:
compacting the replica of the first shard to remove all object chunks that are not included in the first list.

11. The computer system of claim 10 , the one or more programs further comprising instructions for:
after removing the second plurality of object chunks from the first shard, assigning a compaction identifier to the first shard based on the first list of identifiers; and
after removing all object chunks from the replica of the first shard that are not included in the first list, assigning a replica compaction identifier to the replica of the first shard based on a second list of identifiers of object chunks in the replica of the first shard after removal of object chunks not included in the first list;
wherein the compaction identifier and the replica compaction identifier are the same when the first list is the same as the second list.

12. The computer system of claim 11 , wherein the compaction identifier for the first shard is computed as a function of an ordered list of chunk identifiers included in the first shard.

13. The computer system of claim 12 , wherein the function is a hash function.

14. The computer system of claim 11 , the one or more programs further comprising instructions for:
performing a bitwise comparison of data in the first shard with data in the replica of the first shard when the compaction identifier of the first shard matches the replica compaction identifier of the replica of the first shard; and
when the bitwise comparison shows that the replica of the first shard is not identical to the first shard, identifying one or more object chunks within the first shard that are not identical to corresponding object chunks in the replica of the first shard.

15. The computer system of claim 10 , wherein the instructions for compacting the replica of the first shard comprise instructions for constructing a new replica of the first shard that includes object chunks from the replica of the first shard that are in the first list, updating object metadata to specify the new replica as storing the object chunks in the new replica, and deleting the replica of the first shard.

16. The computer system of claim 15 , wherein the instructions for constructing the new replica comprise instructions for retaining the order of object chunks as previously stored in the first shard.

17. The computer system of claim 15 , wherein the instructions for constructing the new replica comprise instructions for storing object chunks in order by chunk identifiers corresponding to stored object chunks.

18. The computer system of claim 10 , wherein the first and second instances are at distinct geographic locations.

19. A non-transitory computer readable storage medium storing one or more programs configured for execution by one or more processors of a computer system to manage consistency of object replicas in a distributed storage system having a first instance and a second instance, the one or more

Assignees

• Google Inc

Inventors

• Drobychev Alexandre
• Kesselman Alexander

Classifications

• G06F17/30153 Primary

  Physics · mapped topic

• G06F16/178 Primary

  Techniques for file synchronisation in file systems · CPC title

• G06F16/1744 Primary

  using compression, e.g. sparse files · CPC title