Granted Patent B2

US 8,868,647 · App. 13/348,243 · Granted Oct 21, 2014

Abstract

Claims (87)

1. A method of storing a file block in a cloud system including a plurality of data centers, the method comprising:

receiving, at a first data center, a file block from a client;

generating a plurality of chunks from the file block, wherein each chunk is smaller than the file block, and the file block is capable of reconstruction from a subset of the chunks,

wherein the plurality of chunks are generated according to a systematic erasure code wherein the file block is divided into a subset of un-encoded chunks and a subset of coded chunks;

distributing the plurality of chunks to at least two of the plurality of data centers; wherein at least a first chunk and a second chunk of the plurality of chunks are distributed to different ones of the plurality of data centers; and

initiating storage of the file block in a cache at the first data center.

2. The method of claim 1 , further comprising:

receiving a request, from a client, to read the file block;

determining whether the file block is stored in the cache;

if the file block is stored in the cache, sending the file block stored in the cache to the client.

3. The method of claim 2 , further comprising:

if the file block is not stored in the cache:

requesting chunks from the plurality of data centers;

receiving at least a subset of the plurality of chunks from the plurality of data centers;

reconstructing the file block from the subset of chunks;

storing the file block in a cache at the first data center; and

sending the reconstructed file block to the client.

4. The method of claim 1 , wherein the step of generating a plurality of chunks from the file comprises using an erasure code to generate the plurality of chunks.

5. The method of claim 4 , wherein the erasure code is at least one of Reed-Solomon codes, MDS codes, and LDPC codes.

6. The method of claim 1 , further comprising:

receiving a request to write to the file block;

writing to the file block in the cache;

closing the written file block;

generating a second plurality of chunks from the written file block; and

distributing each chunk of the second plurality of chunks to a different one of the plurality of data centers.

7. The method of claim 6 , wherein the second plurality of chunks includes only modified chunks.

8. A method of storing a file block in a cloud system including a plurality of data centers, the method comprising:

receiving, at a first data center, a file block from a client;

generating a plurality of chunks from the file block, wherein each chunk is smaller than the file block, and the file block is capable of reconstruction from a subset of the chunks;

distributing the plurality of chunks to at least two of the plurality of data centers; wherein at least a first chunk and a second chunk of the plurality of chunks are distributed to different ones of the plurality of data centers;

initiating storage of the file block in a cache at the first data center;

comparing an actual storage and transfer cost for a current cache size with a hypothetical storage and transfer cost for a previous cache size; and

adjusting the cache size based on the lower storage and transfer cost.

9. The method of claim 1 , further comprising:

determining that the cache is full; and

removing a file block from the cache.

10. The method of claim 1 , wherein the number of chunks is at least two more than the number in a subset of chunks.

11. A cloud system for storing a file block, the system comprising:

a plurality of data centers including a primary data center, the primary data center comprising:

a cache configured to store at least one complete file block;

a chunk storage configured to store a chunk for each of a plurality of file blocks;

a file encoder configured to generate a plurality of chunks from the file block, wherein each chunk is smaller than the file block and the file block is capable of reconstruction from a subset of the chunks,

wherein the plurality of chunks are generated according to a systematic erasure code wherein the file block is divided into a subset of un-encoded chunks and a subset of coded chunks; and

a file decoder configured to reconstruct a complete file block from a subset of the chunks.

12. The cloud system of claim 11 , wherein the cache is a hard disk.

13. The cloud system of claim 11 , wherein the primary data center further comprises a client interface configured to receive complete file blocks from a client and send complete file blocks to a client.

14. The cloud system of claim 11 , wherein the primary data center further comprises a cloud interface configured to distribute a chunk of a plurality of chunks to each of the plurality of data centers and configured to receive a subset of chunks from the plurality of data centers.

15. The cloud system of claim 11 , wherein the number of chunks in the subset is at least two less than the number of the plurality of chunks generated by the file encoder.

16. A tangible and non-transitory machine-readable storage medium encoded with instructions thereon for execution by a data center, the tangible and non-transitory machine-readable storage medium comprising:

instructions for receiving, at a first data center, a file block of a file from a client;

instructions for generating a plurality of chunks from the file block, wherein each chunk is smaller than the file block and the file block is capable of reconstruction from a subset of the chunks,

wherein the instructions for generating a plurality of chunks from the file block comprise instruction for using a systematic erasure code to generate the plurality of chunks wherein the file block is divided into a subset of un-encoded chunks and a subset of coded chunks;

instructions for distributing the plurality of chunks to at least two of the plurality of data centers; wherein at least a first chunk and a second chunk of the plurality of chunks are distributed to different ones of the plurality of data centers; and

instructions for initiating storage of the file block in a cache at the first data center.

17. The tangible and non-transitory machine-readable storage medium of claim 16 , further comprising:

instructions for receiving a request to write to the file block;

instructions for writing to the file block in the cache;

instructions for closing the written file block;

instructions for generating a second plurality of chunks from the written file block;

instructions for distributing each chunk of the second plurality of chunks to a different one of the plurality of data centers.

18. A tangible and non-transitory machine-readable storage medium encoded with instructions thereon for execution by a data center, the tangible and non-transitory machine-readable storage medium comprising:

instructions for receiving, at a first data center, a file block of a file from a client;

instructions for generating a plurality of chunks from the file block, wherein each chunk is smaller than the file block and the file block is capable of reconstruction from a subset of the chunks;

instructions for distributing the plurality of chunks to at least two of the plurality of data centers; wherein at least a first chunk and a second chunk of the plurality of chunks are distributed to different ones of the plurality of data centers;

instructions for initiating storage of the file block in a cache at the first data center;

instructions for comparing an actual storage and transfer cost for a current cache size with a hypothetical storage and transfer cost for a previous cache size; and

instructions for adjusting the cache size based on the lower storage and transfer cost.

19. The tangible and non-transitory machine-readable storage medium of claim 16 , further comprising:

instructions for receiving a request to read the file block from a client;

instructions for determining whether the file block is stored in the cache;

if the file block is not stored in the cache:

instructions for requesting chunks from the plurality of data centers;

instructions for receiving a subset of chunks from the plurality of data centers;

instructions for reconstructing the file block from the subset of chunks;

instructions for storing the file block in the cache; and

instructions for sending the file block to the client.

20. An apparatus for storing a file block, the apparatus comprising:

a cache configured to store at least one complete file block;

a chunk storage configured to store a chunk for each of a plurality of file blocks;

a file encoder configured to generate a plurality of chunks from the file block, wherein each chunk is smaller than the file block and the file block is capable of reconstruction from a subset of the chunks,

wherein the file encoder is configured to use a systematic erasure coding to generate the plurality of chunks wherein the file block is divided into a subset of un-encoded chunks and a subset of coded chunks; and

a file decoder configured to reconstruct a complete file block from a subset of the chunks.

21. The apparatus of claim 20 , further comprising

a cloud interface configured to distribute the plurality of chunks to at least two of a plurality of data centers; wherein at least a first chunk and a second chunk of the plurality of chunks are distributed to different ones of the plurality of data centers.

22. The apparatus of claim 21 , further comprising a client interface configured to: receive a request, from a client, to read the file block; determine whether the file block is stored in the cache; and send the file block stored in the cache to the client,

wherein if the file block is not stored in the cache, the cloud interface is further configured to: request chunks from the plurality of data centers; and receive at least a subset of the plurality of chunks from the plurality of data centers,

wherein the file decoder is configured to reconstruct the file block from the subset of chunks and store the file block in the cache.

Assignments (11)