Method and system for uploading data into a distributed storage system

• US 9,305,069 B2
• Filed: 02/08/2011
• Issued: 04/05/2016
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zunger, Yonatan, Kesselman, Alexander, Drobychev, Alexandre
• Primary Examiner(s): MENG, JAU SHYA
• Application Number:
  US13/023,384
• Publication Number:
  US 20110196822A1
• Time in Patent Office: 1,883 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A method for uploading an object into a distributed storage system is implemented at a computing device The computing device splits an object into one or more chunks and uploads the one or more chunks into the distributed storage system. For each uploaded chunk, the computing device receives a write token from the distributed storage system, inserts an entry into an extents table of the object for the chunk in accordance with the received write token and the chunk ID, chunk offset, and chunk size of the chunk, generates a digest of the extents table, the digest representing the one or more chunks that the client expects to be within the distributed storage system, and sends the digest of the extents table to the distributed storage system. The distributed storage system is configured to use the digest to determine whether it has each of the one or more client-expected chunks.

Claims

1. A computer-implemented method for uploading an object into a distributed storage system, wherein the distributed storage system includes a plurality of chunk stores, comprising:

at a computing device, distinct from the distributed storage system, having one or more processors and memory storing programs executed by the one or more processors, wherein the computing device is connected to the distributed storage system through a network;

splitting an object into one or more chunks, wherein the one or more chunks have a predefined sequence and a respective chunk has a chunk ID, a chunk offset, and a chunk size;

uploading the one or more chunks into the distributed storage system;

for a respective uploaded chunk,

receiving a write token from the distributed storage system after the respective uploaded chunk has been stored into the distributed storage system, wherein the write token identifies a respective chunk store that stores the uploaded chunk and includes the chunk ID, the chunk offset, and chunk size of the uploaded chunk;

inserting an entry into an extents table of the object for the uploaded chunk in accordance with the write token received from the distributed storage system, the write token indicating the respective chunk store and including the chunk ID, chunk offset, and chunk size of the uploaded chunk, wherein the extents table is stored at the computing device;

generating a digest of the extents table, wherein the digest represents the one or more chunks that a client expects to be within the distributed storage system, the digest indicating a total number of client-expected chunks; and

sending the digest of the extents table to the distributed storage system, wherein the distributed storage system uses the digest to determine whether it has each of the one or more client-expected chunks, including by comparing the total number of client-expected chunks with a number of chunks of the object stored in the distributed storage system, wherein the computing device re-uploads any missing chunks of the object into the distributed storage system.

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

inserting a dummy entry into the extents table for a respective gap between two consecutive but non-contiguous chunks of the object in accordance with the predefined sequence.

3. The computer-implemented method of claim 2, wherein the dummy entry corresponds to a dummy chunk that has a predefined chunk ID, a chunk offset, and a chunk size.

4. The computer-implemented method of claim 1, wherein the client is configured to choose a destination chunk store for the object to be the chunk store that has more bytes of the object than any other chunk stores of the distributed storage system.

5. The computer-implemented method of claim 1, wherein the one or more chunks have the same chunk size.

6. The computer-implemented method of claim 1, wherein at least two of the one or more chunks have two different chunk sizes.

7. The computer-implemented method of claim 1, wherein each of the plurality of chunk stores has a respective store type, and uploading the one or more chunks to the plurality of chunk stores further comprises:

choosing a store type in accordance with a total size of the object and a user-specified storage policy for the object; and

notifying the distributed storage system of the chosen store type such that the one or more chunks are uploaded into a subset of the plurality of chunk stores that have the chosen store type.

8. The computer-implemented method of claim 1, wherein the write token further includes, the respective chunk store'"'"'s chunkstore ID and a cryptographic signature associated with the uploaded chunk.

9. The computer-implemented method of claim 1, wherein the extents table defines a map from a logical byte range of the object to one or more chunk IDs of the one or more chunks stored within the distributed storage system.

10. The computer-implemented method of claim 1, wherein the digest of the extents table further includes a total number of chunks of the object that the client expects to be within the distributed storage system.

11. A computer-implemented method for storing an object within a plurality of chunk stores of a distributed storage system, comprising:

at a computing device having one or more processors and memory storing programs executed by the one or more processors, wherein the computing device is connected to the distributed storage system through a network;

receiving from a client a request to store an object having one or more chunks, wherein the one or more chunks have a predefined sequence and a respective chunk has a chunk ID, a chunk offset, and a chunk size;

for a respective received chunk,

identifying a respective chunk store in accordance with a load balance of the distributed storage system;

storing the received chunk within the respective chunk store; and

returning a write token for the received chunk to the client after the received chunk has been stored into the distributed storage system, wherein the client inserts an entry into an extents table of the object for the received chunk in accordance with the write token, the write token indicating the respective chunk store and including the chunk ID, chunk offset, and chunk size of the received chunk;

receiving a digest of the extents table of the object from the client, wherein the digest represents the one or more chunks that the client expects to be within the distributed storage system, the digest indicating a total number of client-expected chunks; and

determining whether the distributed storage system has the one or more client-expected chunks in accordance with the received digest, including by comparing the total number of client-expected chunks with a number of chunks of the object stored in the distributed storage system, wherein the client re-uploads any missing chunks of the object into the distributed storage system.

12. The computer-implemented method of claim 11, wherein the digest includes information of at least one dummy entry in the extents table, and wherein the dummy entry corresponds to a gap between two consecutive but non-contiguous chunks of the object in accordance with the predefined sequence.

13. The computer-implemented method of claim 12, wherein the dummy entry corresponds to a dummy chunk that has a predefined chunk ID, a chunk offset, and a chunk size.

14. The computer-implemented method of claim 11, further comprising:

identifying a destination chunk store for the object as the chunk store that has more bytes of the object than any other chunk stores of the distributed storage system; and

transferring the received chunks from a non-destination chunk stores to the destination chunk store.

15. The computer-implemented method of claim 11, wherein the one or more chunks have the same chunk size.

16. The computer-implemented method of claim 11, wherein at least two of the one or more chunks have two different chunk sizes.

17. The computer-implemented method of claim 11, wherein each of the plurality of chunk stores has a respective store type and a chunk store is chosen for storing a chunk of the object if its store type is the same as a client-chosen store type.

18. The computer-implemented method of claim 11, wherein a respective write token includes a respective chunk store'"'"'s chunkstore ID and a cryptographic signature associated with the uploaded chunk.

19. The computer-implemented method of claim 11, wherein the extents table defines a map from a logical byte range of the object to one or more chunk IDs of the one or more chunks.

20. The computer-implemented method of claim 11, wherein the digest of the extents table further includes a total number of chunks that the client expects to be within the distributed storage system.

21. A computer system for managing a distributed storage system, 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 to perform;

receiving from a client a request to store an object having one or more chunks, wherein the one or more chunks have a predefined sequence and a respective chunk has a chunk ID, a chunk offset, and a chunk size;

for a respective received chunk,

identifying a respective chunk store in accordance with a load balance of the distributed storage system;

storing the received chunk within the respective chunk store; and

returning a write token for the received chunk to the client after the received chunk has been stored into the distributed storage system, wherein the client inserts an entry into an extents table of the object for the received chunk in accordance with the write token, the write token indicating the respective chunk store and including the chunk ID, chunk offset, and chunk size of the received chunk;

receiving a digest of the extents table of the object from the client, wherein the digest represents the one or more chunks that the client expects to be within the distributed storage system, the digest indicating a total number of client-expected chunks; and

determining whether the distributed storage system has the one or more client-expected chunks in accordance with the received digest, including by comparing the total number of client-expected chunks with a number of chunks of the object stored in the distributed storage system, wherein the client re-uploads any missing chunks of the object into the distributed storage system.

22. 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, the one or more programs comprising instructions to:

receive from a client a request to store an object having one or more chunks, wherein the one or more chunks have a predefined sequence and a respective chunk has a chunk ID, a chunk offset, and a chunk size;

for a respective received chunk,

identify a respective chunk store in accordance with a load balance of the distributed storage system;

store the received chunk within the respective chunk store; and

return a write token for the received chunk to the client after the received chunk has been stored into the distributed storage system, wherein the client inserts an entry into an extents table of the object for the received chunk in accordance with the write token, the write token indicating the respective chunk store and including the chunk ID, chunk offset, and chunk size of the received chunk;

receive a digest of the extents table of the object from the client, wherein the digest represents the one or more chunks that the client expects to be within the distributed storage system, the digest indicating a total number of client-expected chunks; and

determine whether the distributed storage system has the one or more client-expected chunks in accordance with the received digest, including by comparing the total number of client-expected chunks with a number of chunks of the object stored in the distributed storage system, wherein the client re-uploads any missing chunks of the object into the distributed storage system.