Cloud data backup storage manager

• US 9,330,137 B2
• Filed: 05/12/2014
• Issued: 05/03/2016
• 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
• Primary Examiner(s): Badawi, Sherief
• Assistant Examiner(s): Nguyen, Loan T
• Application Number:
  US14/275,815
• Publication Number:
  US 20140250083A1
• Time in Patent Office: 722 Days
• US Class Current: 1/1
• 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 to back up data, comprising:

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

querying the plurality of peer computers to determine a number of copies of the K file segments that are stored on the plurality of peer computers, wherein in response to any particular file segment of the K file segments not having R available copies, the method comprises at least one of;

request and reserve space for one or more additional copies of the particular file segment;

or

instruct creation of one or more additional copies of the particular file segment on one or more of the peer computers of the plurality of peer computers such that R copies of the particular file segment are stored at the one or more of the peer computers.

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

3. The method of claim 1, wherein at least one of the K file segments comprises less than an entirety of the file.

4. The method of claim 3, wherein less than all of the K file 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 identified segments associated with the file; and

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

13. The method of claim 1, wherein querying the plurality of peer computers to determine the number of copies of the K file segments includes querying the plurality of peer computers to determine a number of copies of the K file segments that are accessible and verifiable.

6. 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 a single segment comprises less than an entirety of the file;

transmit the segments to a plurality of peer computers such that each single peer computer receives less than all of the K file segments 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;

reconstruct the file, based upon at least the unique file identifier and the unique segment identifiers, from the received at least some of the segments; and

query the plurality of peer computers to determine a number of copies of the K file segments that are stored on the plurality of peer computers, wherein the client computer is configured to, in response to any particular file segment of the K file segments not having R available copies, perform or control performance of at least one of;

request and reserve space for one or more additional copies of the particular file segment;

or

instruct creation of one or more additional copies of the particular file segment on one or more of the peer computers of the plurality of peer computers such that R copies of the particular file segment are stored at the one or more of the peer computers.

7. The apparatus of claim 6, wherein the client computer is configured to encrypt at least one of the K file segments.

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

9. The apparatus of claim 6, wherein the client computer includes first and second storage device partitions, wherein the client computer is configured to store the file in the first storage device partition, and wherein the client computer is configured to store the at least some of the segments received from the peer computers in the second storage device partition.

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

11. The apparatus of claim 6, wherein the query to determine the number of copies includes a query to determine a number of copies of the K file segments that are accessible and verifiable.

12. The apparatus of claim 6, wherein the client computer includes a cloud storage manager service configured to perform or control performance of at least some of the identify, separate, transmit, receive, reconstruct, query, request, and instruct.

14. An apparatus, comprising:

a computer configured to identify a file to be backed up and to encode the file into K file segments, wherein K is an integer greater than one, the computer being further configured to request at least R*K storage blocks on a plurality of peer computers, wherein R is a redundancy factor;

wherein segments are transmitted from a client computer to the plurality of peer computers such that each of the K file segments is stored on at least R peer computers;

the computer further being configured to query the plurality of peer computers to determine a number of copies of the K file segments that are stored on the plurality of peer computers, wherein the computer is configured to, in response to any particular file segment of the K file segments not having R available copies, perform or control performance of least one of;

request and reserve space for one or more additional copies of the particular file segment;

or

instruct creation of one or more additional copies of the particular file segment on one or more of the peer computers of the plurality of peer computers such that R copies of the particular file segment are stored at the one or more of the peer computers.

15. The apparatus of claim 14, wherein the file to be backed up is stored locally on the client computer.

16. The apparatus of claim 14, wherein the query to determine the number of copies includes a query to determine a number of copies of the K file segments that are accessible and verifiable.

17. The apparatus of claim 14, wherein the computer is configured to operate as a cloud storage manager that is separate from the client computer.

18. The apparatus of claim 14, wherein the computer is one of the peer computers and includes a cloud storage manager service configured to perform or control performance of at least some of the identify the file, encode the file, request the at least R*K storage blocks, query the plurality of peer computers, request and reserve space, and instruct creation of one or more additional copies.

19. The apparatus of claim 14, wherein the computer is the client computer and includes a cloud storage manager service configured to perform or control performance of at least some of the identify the file, encode the file, request the at least R*K storage blocks, query the plurality of peer computers, request and reserve space, and instruct creation of one or more additional copies.