Method and system for managing weakly mutable data in a distributed storage system

• US 8,615,485 B2
• Filed: 02/09/2011
• Issued: 12/24/2013
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Drobychev, Alexandre, Kesselman, Alexander, Datuashvili, George, Yonatan, Zunger, Syed, Zia M.
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): Mobin, Hasanul
• Application Number:
  US13/024,250
• Publication Number:
  US 20110196838A1
• Time in Patent Office: 1,049 Days
• Field of Search: None
• US Class Current: 707/610
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

A method for managing multiple generations of an object within a distributed storage system is implemented at a computing device. The computing device receives metadata and content of a first generation of an object from a first client connected to the distributed storage system and stores the first generation'"'"'s metadata and content within a first storage sub-system. The computing device receives metadata and content of a second generation of the object from a second client connected to the distributed storage system and stores the second generation'"'"'s metadata and content within a second storage sub-system. The computing device independently replicates the first generation'"'"'s metadata and content from the first storage sub-system to the second storage sub-system and replicates the second generation'"'"'s metadata and content from the second storage sub-system to the first storage sub-system such that both storage sub-systems include a replica of the object'"'"'s first and second generations.

Claims

1. A computer-implemented method for managing multiple generations of an object within a distributed storage system, wherein the distributed storage system includes a plurality of storage sub-systems having one or more processors and memory storing one or more programs for execution by the one or more processors to perform the method, comprising:

receiving metadata and content of a first generation of an object from a first client connected to the distributed storage system, wherein the first generation is identified by an object ID and a first generation ID;

storing the first generation'"'"'s metadata and content within a first storage sub-system of the distributed storage system;

receiving metadata and content of a second generation of the object from a second client connected to the distributed storage system, wherein the second generation is identified by the object ID and a second generation ID;

storing the second generation'"'"'s metadata and content within a second storage sub-system of the distributed storage system; and

independently replicating the first generation'"'"'s metadata and content from the first storage sub-system to the second storage sub-system and replicating the second generation'"'"'s metadata and content from the second storage sub-system to the first storage sub-system such that both the first and second storage sub-systems include a replica of the object'"'"'s first and second generations, wherein each generation ID includes a first component that corresponds to a respective object generation'"'"'s creation time and a second component that corresponds to a tie-breaker that defines an order among multiple generations of the same object and wherein the second generation'"'"'s content is dynamically replicated from the second storage sub-system to the first storage sub-system in response to a first client request.

2. The computer-implemented method of claim 1, wherein the content of either the first generation or the second generation is immutable over time until the deletion of the respective generation.

3. The computer-implemented method of claim 1, wherein there is at least one content difference between the first generation and the second generation.

4. The computer-implemented method of claim 1, further comprising:

at either of the first and second storage sub-systems,

comparing the first generation'"'"'s content with the second generation'"'"'s content; and

deleting one of the first generation and the second generation from a respective storage sub-system if the two generations have identical content.

5. The computer-implemented method of claim 1, further comprising:

before the replication of the second generation'"'"'s metadata from the second storage sub-system to the first storage sub-system,

receiving a second client request for a latest generation of the object;

returning the first generation'"'"'s content and metadata to the requesting client in response to the second client request;

after the replication of the second generation'"'"'s metadata from the second storage sub-system to the first storage sub-system,

receiving from a third client request for a latest generation of the object; and

returning the second generation'"'"'s content and metadata to the requesting client in response to the third client request.

6. The computer-implemented method of claim 1, further comprising:

at either of the first and second storage sub-systems,

determining a total number of generations of the object at the respective storage sub-system; and

deleting one or more generations of the object from the respective storage sub-system in accordance with their respective generation IDs if the total number of generations exceeds a predefined number associated with the object.

7. A computer system in association with a distributed storage system that includes a plurality of storage sub-systems, comprising:

one or more processors;

memory; and

one or more programs stored in the memory for execution by the one or more processors, the one or more programs comprising instructions for;

receiving metadata and content of a first generation of an object from a first client connected to the distributed storage system, wherein the first generation is identified by an object ID and a first generation ID;

storing the first generation'"'"'s metadata and content within a first storage sub-system of the distributed storage system;

receiving metadata and content of a second generation of the object from a second client connected to the distributed storage system, wherein the second generation is identified by the object ID and a second generation ID;

storing the second generation'"'"'s metadata and content within a second storage sub-system of the distributed storage system; and

independently replicating the first generation'"'"'s metadata and content from the first storage sub-system to the second storage sub-system and replicating the second generation'"'"'s metadata and content from the second storage sub-system to the first storage sub-system such that both the first and second storage sub-systems include a replica of the object'"'"'s first and second generations, wherein each generation ID includes a first component that corresponds to a respective object generation'"'"'s creation time and a second component that corresponds to a tie-breaker that defines an order among multiple generations of the same object and wherein the second generation'"'"'s content is dynamically replicated from the second storage sub-system to the first storage sub-system in response to a first client request.

8. The computer system of claim 7, wherein the content of either the first generation or the second generation is immutable over time until the deletion of the respective generation.

9. The computer system of claim 7, wherein there is at least one content difference between the first generation and the second generation.

10. The computer system of claim 7, further comprising:

at either of the first and second storage sub-systems,

instructions for comparing the first generation'"'"'s content with the second generation'"'"'s content; and

instructions for deleting one of the first generation and the second generation from a respective storage sub-system if the two generations have identical content.

11. The computer system of claim 7, further comprising:

at the first storage sub-system,

instructions for receiving a second client request for a latest generation of the object before the replication of the second generation'"'"'s metadata from the second storage sub-system to the first storage sub-system;

instructions for returning the first generation'"'"'s content and metadata to the requesting client in response to the second client request;

instructions for receiving from a third client request for a latest generation of the object after the replication of the second generation'"'"'s metadata from the second storage sub-system to the first storage sub-system; and

instructions for returning the second generation'"'"'s content and metadata to the requesting client in response to the third client request.

12. The computer system of claim 7, further comprising:

at either of the first and second storage sub-systems,

instructions for determining a total number of generations of the object at the respective storage sub-system; and

instructions for deleting one or more generations of the object from the respective storage sub-system in accordance with their respective generation IDs if the total number of generations exceeds a predefined number associated with the object.

13. A non-transitory computer readable storage medium storing one or more programs configured for execution by a server computer system having one or more processors and memory storing one or more programs for execution by the one or more processors in association with a distributed storage system that includes a plurality of storage sub-systems, the one or more programs comprising instructions to:

receive metadata and content of a first generation of an object from a first client connected to the distributed storage system, wherein the first generation is identified by an object ID and a first generation ID;

store the first generation'"'"'s metadata and content within a first storage sub-system of the distributed storage system;

receive metadata and content of a second generation of the object from a second client connected to the distributed storage system, wherein the second generation is identified by the object ID and a second generation ID;

store the second generation'"'"'s metadata and content within a second storage sub-system of the distributed storage system; and

independently replicate the first generation'"'"'s metadata and content from the first storage sub-system to the second storage sub-system and replicate the second generation'"'"'s metadata and content from the second storage sub-system to the first storage sub-system such that both the first and second storage sub-systems include a replica of the object'"'"'s first and second generations, wherein each generation ID includes a first component that corresponds to a respective object generation'"'"'s creation time and a second component that corresponds to a tie-breaker that defines an order among multiple generations of the same object and wherein the second generation'"'"'s content is dynamically replicated from the second storage sub-system to the first storage sub-system in response to a first client request.

14. The non-transitory computer readable storage medium of claim 13, wherein the content of either the first generation or the second generation is immutable over time until the deletion of the respective generation.

15. The non-transitory computer readable storage medium of claim 13, wherein there is at least one content difference between the first generation and the second generation.

16. The non-transitory computer readable storage medium of claim 13, further comprising:

at either of the first and second storage sub-systems,

instructions for comparing the first generation'"'"'s content with the second generation'"'"'s content; and

instructions for deleting one of the first generation and the second generation from a respective storage sub-system if the two generations have identical content.

17. The non-transitory computer readable storage medium of claim 13, further comprising:

at the first storage sub-system,

instructions for receiving a second client request for a latest generation of the object before the replication of the second generation'"'"'s metadata from the second storage sub-system to the first storage sub-system;

instructions for returning the first generation'"'"'s content and metadata to the requesting client in response to the second client request;

instructions for receiving from a third client request for a latest generation of the object after the replication of the second generation'"'"'s metadata from the second storage sub-system to the first storage sub-system; and

instructions for returning the second generation'"'"'s content and metadata to the requesting client in response to the third client request.

18. The non-transitory computer readable storage medium of claim 13, further comprising:

at either of the first and second storage sub-systems,

instructions for determining a total number of generations of the object at the respective storage sub-system; and

instructions for deleting one or more generations of the object from the respective storage sub-system in accordance with their respective generation IDs if the total number of generations exceeds a predefined number associated with the object.