Method and system for scaleable, distributed, differential electronic-data backup and archiving

• US 20070250674A1
• Filed: 04/25/2006
• Published: 10/25/2007
• Est. Priority Date: 04/25/2006
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Mehra, Pankaj, Fineberg, Samuel
• Granted Patent: US 8,862,841 B2
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

One embodiment of the present invention provides a distributed, differential electronic-data backup and archiving system that includes client computers and cells. Client computers execute front-end-application components of the distributed, differential electronic-data backup and archiving system, the front-end application components receiving data objects from client computers and sending the received data objects to cells of the distributed, differential electronic-data backup and archiving system for storage. Cells within the distributed, differential electronic-data backup and archiving system store the data objects, each cell comprising at least one computer system with attached mass-storage and each cell storing entire data objects as lists that reference stored, unique data chunks within the cell, a cell storing all of the unique data chunks for all data objects stored in the cell.

Claims

1. A distributed, differential electronic-data backup and archiving system comprising:

client computers that execute front-end-application components of the distributed, differential electronic-data backup and archiving system, the front-end application components receiving data objects from client computers and sending the received data objects to cells of the distributed, differential electronic-data backup and archiving system for storage; and

cells within the distributed, differential electronic-data backup and archiving system that store the data objects, each cell comprising at least one computer system with attached mass-storage, each cell storing entire data objects as lists that reference stored, unique data chunks within the cell by content, a cell storing all of the unique data chunks for all data object stored in the cell.

2. The distributed, differential electronic-data backup and archiving system of claim 1 wherein the front-end-application component of a client computer executes a STORE request received from a higher-level routine within the client computer by:

generating a list representation of the data object;

transmitting the list representation of the data object to a processing component of the distributed, differential electronic-data backup and archiving system;

receiving an indication of data chunks within the data object that need to be transmitted by the front-end-application component to a cell of the distributed, differential electronic-data backup and archiving system; and

transmitting the needed data chunks to the cell.

3. The distributed, differential electronic-data backup and archiving system of claim 1 wherein the front-end-application component of a client computer generates a list representation of the data object by:

partitioning the data object into data chunks;

computing a hash value or other collision-resistant identifier for the contents of each data chunk; and

composing a list to describe the data object.

4. The distributed, differential electronic-data backup and archiving system of claim 1 wherein each cell includes a hash-value index.

5. The distributed, differential electronic-data backup and archiving system of claim 4 wherein a cell stores a data object by:

receiving a hash-list representation of the data object;

identifying hash values within the hash-list representation that are not stored within the hash-value index of the cell;

requesting data chunks corresponding to the identified hash values not stored within the hash-value index of the cell from the front-end-application component that transmitted the hash-list representation of the data object;

creating a chunked-object entry within a container object for the data object, and storing the received hash-list representation of the data object within the chunked-object entry;

receiving the requested data chunks from the front-end-application component; and

storing the received data chunks within data-chunk entries in containers.

6. The distributed, differential electronic-data backup and archiving system of claim 1 wherein a container object includes:

meta data;

an entry list comprising a sequence of entry-list nodes, each entry-list node identifying an entry within the container; and

one or more entries.

7. The distributed, differential electronic-data backup and archiving system of claim 6 wherein entries include chunked-object entries and data-chunk entries.

8. The distributed, differential electronic-data backup and archiving system of claim 7 wherein each chunked-object entry includes a list comprising a sequence of list entries, each list entry including a collision-resistant content identifier and a reference to a stored data chunk.

9. The distributed, differential electronic-data backup and archiving system of claim 7 wherein each data-chunk object entry includes stored, unique data chunks and back pointers that reference containers with chunked-object entries that reference one or more stored, unique data chunks within the data-chunk entry.

10. The distributed, differential electronic-data backup and archiving system of claim 1 further including one or more portal computers that receive requests from front-end-application components of client computers and forward the received requests to cells of the distributed, differential electronic-data backup and archiving system for execution.

11. The distributed, differential electronic-data backup and archiving system of claim 1 wherein each stored data object is uniquely identified by an object ID.

12. The distributed, differential electronic-data backup and archiving system of claim 11 wherein each object ID is computed from:

a cell ID that identifies a cell in which the data object identified by the object ID is stored;

a container ID that identifies a container object within the cell in which a chunked-object entry or other entry representing the stored data object; and

an entry ID that identifies an entry within the container that stores the chunked-object entry or other entry representing the stored data object.

19. The method of claim 1 further including uniquely identifying each stored data object within distributed, differential electronic-data backup and archiving system by an object ID.

20. The method of claim 19 further including computing each object ID from:

a cell ID that identifies a cell in which the data object identified by the object ID is stored;

a container ID that identifies a container object within the cell in which a chunked-object entry or other entry representing the stored data object; and

an entry ID that identifies an entry within the container that stores the chunked-object entry or other entry representing the stored data object.

13. A method for backing up and archiving a data object on behalf of a client computer, the method comprising:

providing a distributed, differential electronic-data backup and archiving system comprising

a front-end-application component of the distributed, differential electronic-data backup and archiving system that executes on the client computer, and

cells within the distributed, differential electronic-data backup and archiving system that store the data objects, each cell comprising at least one computer system with attached mass-storage;

receiving, by the front-end-application component, a request to store an object;

transmitting a STORE request to a cell within the distributed, differential electronic-data backup and archiving system; and

storing the data object, by the cell within the distributed, differential electronic-data backup and archiving system, as a list that references stored, unique data chunks within the cell by content, the cell storing all of the unique data chunks for all data object stored in the cell.

14. The method of claim 13 wherein the front-end-application component of the client computer transmits a STORE request by:

generating a list representation of the data object;

transmitting the list representation of the data object to the cell within the distributed, differential electronic-data backup and archiving system;

receiving an indication of data chunks within the data object that need to be transmitted by the front-end-application component to the cell within the distributed, differential electronic-data backup and archiving system; and

transmitting the needed data chunks to the cell.

15. The method of claim 13 wherein the front-end-application component of the client computer generates a list representation of the data object by:

partitioning the data object into data chunks;

computing a collision-resistant content identifier for each data chunk; and

composing a hash list to describe the data object.

16. The method of claim 13

wherein each cell includes a hash-value index;

and

wherein a cell stores a data object by;

receiving a hash-list representation of the data object,

identifying hash values within the hash-list representation that are not stored within the hash-value index of the cell,

requesting data chunks corresponding to the identified hash values not stored within the hash-value index of the cell from the front-end-application component,

creating a chunked-object entry within a container object for the data object, and storing the received hash-list representation of the data object within the chunked-object entry,

receiving the requested data chunks from the front-end-application component, and

storing the received data chunks within data-chunk entries in containers.

17. The method of claim 16 wherein each container object includes:

meta data;

an entry list comprising a sequence of entry-list nodes, each entry-list node identifying an entry within the container;

and one or more entries.

18. The method of claim 17

wherein entries include chunked-object entries and data-chunk entries;

wherein each chunked-object entry includes a hash list comprising a sequence of hash-list entries, each hash-list entry including a hash value and a reference to a store data chunk; and

wherein each data-chunk object entry includes stored, unique data chunks and back pointers that reference containers with chunked-object entries that reference one or more stored, unique data chunks within the data-chunk entry.