CLOUD DATA BACKUP STORAGE MANAGER

• US 20140250083A1
• Filed: 05/12/2014
• Published: 09/04/2014
• 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 9,330,137 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-24. -24. (canceled)

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

querying the plurality of peer computers to determine a number of accessible and/or verifiable copies of the K file segments that are stored on the plurality of peer computers, wherein when any K file segment of the K file segments does not have R available copies, request and reserve space for one or more additional copies of the K file segment and/or create one or more additional copies of the K file segment on one or more of the peer computers of the plurality of peer computers such that R copies of the K file segment are accessible and/or verifiable.

26. The method of claim 25, 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.

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

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

29. The method of claim 25, 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.

30. 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;

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

query the plurality of peer computers to determine a number of accessible and/or verifiable copies of the K file segments that are stored on the plurality of peer computers, wherein when any K file segment of the K file segments does not have R available copies, request and reserve space for one or more additional copies of the K file segment and/or create one or more additional copies of the K file segment on one or more of the peer computers of the plurality of peer computers such that R copies of the K file segment are accessible and/or verifiable.

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

32. The apparatus of claim 30, 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.

33. The apparatus of claim 30, 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.

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