Cloud Data Backup Storage

• US 20110055161A1
• Filed: 09/01/2009
• Published: 03/03/2011
• Est. Priority Date: 09/01/2009
• Status: Active Grant

• Current Assignee: Xero Limited
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Wolfe, Andrew
• Granted Patent: US 8,370,307 B2
• Time in Patent Office: Days
• US Class Current: 707/652
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2211/1088 Scrubbing in RAID systems with parity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding

Abstract

Techniques for cloud data backup are disclosed. Example methods may store backup data from a client computer on portions of data storage media associated with peer computers. In some example embodiments, a file may be encoded into segments using an error-tolerant encoding scheme, and the segments may be stored on peer computers. In some example embodiments, individual segments may be stored on more than one peer machine and/or an individual peer machine may not receive all of the segments associated with the file.

Claims

1. A method of backing up data comprising:

identifying at least one file to be backed up, wherein the file is stored locally on a client computer;

encoding the file into K file segments, wherein K is an integer greater than one;

requesting at least R*K storage blocks on a plurality of peer computers, wherein R is a redundancy factor;

transmitting segments from the client computer to the plurality of peer computers such that each of the K file segments is stored on at least R peer computers.

2. The method of claim 1, wherein the client is associated with a unique client identifier, the file is associated with a unique file identifier, and segments are associated with unique segment identifiers on an individual basis.

3. The method of claim 1, wherein at least one of the segments does not comprise the file in its entirety.

4. The method of claim 3, wherein less than all of the K segments associated with the file are transmitted to at least one of the peer computers.

5. The method of claim 1, further comprising:

querying the peer computers to identify segments associated with the file stored on any of the peer computers;

receiving at least one of the segments associated with the file;

reconstructing a copy of the file from the received at least one segments.

6. The method of claim 1, further comprising:

querying the peer computers to identify segments associated with the file stored on any of the peer computers;

if a number of any one of the K segments stored on the peer computers is less than R, transmitting the one of the K segments to one or more of the peer computers such that each of the K segments is stored on R peer computers.

7. The method of claim 1, further comprising:

encrypting at least one of the segments prior to transmission to the peer computers.

8. The method of claim 1, wherein the file comprises a plurality of data words including a plurality of bits;

and wherein an individual segment includes one or more, but fewer than all, of the bits of an individual data word.

9. The method of claim 1, wherein encoding the file into the K file segments includes

encoding the file using an error detection and correction code, and

dividing the file into the K file segments such that the file can be reconstructed from any K-1 of the file segments.

10. The method of claim 1, wherein encoding the file into K file segments includes

encoding the file using an error detection and correction code, and

dividing the file into the K file segments such that, for an integer N, the file can be reconstructed from any K-N of the file segments.

11. The method of claim 10, further comprising:

querying the peer computers to identify segments associated with the file stored on any of the peer computers;

receiving at least one of the segments associated with the file;

if fewer than all of the K segments are received,

reconstructing at least one missing segment from the received segments, and

transmitting the reconstructed missing segment to at least one of the peer computers such that each of the K segments is stored on R peer computers.

12. The method of claim 1, wherein individual segments comprise an error-detecting code.

13. The method of claim 12, further comprising:

querying the peer computers to identify segments associated with the file stored on any of the peer computers;

receiving at least one segment associated with the file;

checking the received at least one segment for error-containing segments using said error-detecting code;

if any error-containing segments are identified,

reconstructing at least one of the error-containing segments from at least one error-free segment,

replacing the at least one error-containing segment with an error-free copy on at least one of the peer computers.

14. An apparatus for data backup comprising:

a client computer associated with a unique client identifier, the client computer being configured to;

identify a file for backup, the file being associated with a unique file identifier;

separate the file into K file segments, wherein K is an integer greater than one, wherein individual segments are associated with unique segment identifiers, and wherein no single segment comprises the complete file;

transmit the segments to a plurality of peer computers such that no single peer computer receives all K segments associated with the file and such that individual segments are received by at least R peer computers, wherein R is a redundancy factor;

receive from the peer computers at least some of the segments associated with the file; and

reconstruct the file, based upon at least the unique file identifier and the unique segment identifier, from the received segments.

15. The apparatus of claim 14, wherein the client computer is configured to encrypt at least one of the segments.

16. The apparatus of claim 14, wherein the client computer is configured to separate the file into K file segments by encoding individual bytes of the file into 12-bit Hamming-type code.

17. The apparatus of claim 14, wherein the client is configured to store the file in a first storage device partition;

and wherein the client is configured to store file segments received from the peer computers in a second storage device partition.

18. The apparatus of claim 14, wherein the client is configured to request at least R*K storage blocks on the peer computers.

19. The apparatus of claim 18, wherein the client is configured to request the at least R*K storage blocks on the peer computers from a cloud storage manager;

and wherein the client is configured to receive the identities of the peer computers from the cloud storage manager.

20. The apparatus of claim 14, wherein at least one segment comprises an error-detecting code.

21. A storage medium comprising machine-readable instructions stored thereon, which, when executed by one or more processing units, operatively enable a computing platform to:

identify a file stored locally on a client computer for backup;

create a plurality of file segments from the file, wherein individual segments comprise less than the complete file, and wherein individual segments comprise an error-detecting code; and

transmit individual segments from the client computer to a plurality of peer computers such that individual segments are stored on at least R peer computers, wherein R is a redundancy factor, and wherein fewer than all of the segments are transmitted to individual peer computers.

22. The storage medium of claim 21, wherein the storage medium further comprises machine-readable instructions enabling the computing platform to:

query the peer computers to ascertain which, if any, of the segments is held by each of the peer computers; and

for any one of the segments held by fewer than R peer computers, transmit the segment to additional peer computers such that the segment is held by R peer computers.

23. The storage medium of claim 21, wherein the storage medium further comprises machine-readable instructions enabling the computing platform to:

request storage blocks on the peer computers;

wherein the plurality of file segments comprises K file segments, wherein K is an integer greater than one; and

wherein at least R*K storage blocks are requested.

24. The storage medium of claim 21, wherein the storage medium further comprises machine-readable instructions enabling the computing platform to:

request the storage block on the peer computers from a cloud storage manager; and

receive, from the cloud manager, identities of the peer computers associated with the storage blocks.