Method and System For Uploading Data Into A Distributed Storage System

• US 20110196822A1
• Filed: 02/08/2011
• Published: 08/11/2011
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zunger, Yonatan, Drobychev, Alexandre, Kesselman, Alexandre
• Granted Patent: US 9,305,069 B2
• Time in Patent Office: Days
• US Class Current: 707/609
• 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 having one or more processors and memory storing programs executed by the one or more processors, wherein the computing device is connected to a 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, wherein the write token identifies a respective chunk store that stores the chunk;

inserting 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;

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; and

sending the digest of the extents table to the distributed storage system, wherein the distributed storage system is configured to use the digest to determine whether it has each of the one or more client-expected chunks.

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 includes the uploaded chunk'"'"'s chunk ID, 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 distribute storage system;

storing the chunk within the identified chunk store; and

returning a write token for the chunk to the client, wherein the client is configured to insert an entry into an extents table of the object for the chunk in accordance with the write token and the chunk ID, chunk offset, and chunk size of the 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; and

determining whether the distributed storage system has the one or more client-expected chunks in accordance with the received digest.

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 an uploaded chunk'"'"'s chunk ID, 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, 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 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 distribute storage system;

storing the chunk within the identified chunk store; and

returning a write token for the chunk to the client, wherein the client is configured to insert an entry into an extents table of the object for the chunk in accordance with the write token and the chunk ID, chunk offset, and chunk size of the 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; and

determining whether the distributed storage system has the one or more client-expected chunks in accordance with the received digest.

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 distribute storage system;

store the chunk within the identified chunk store; and

return a write token for the chunk to the client, wherein the client is configured to insert an entry into an extents table of the object for the chunk in accordance with the write token and the chunk ID, chunk offset, and chunk size of the 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; and

determine whether the distributed storage system has the one or more client-expected chunks in accordance with the received digest.