Distributed scalable deduplicated data backup system

• US 8,996,467 B2
• Filed: 12/29/2011
• Issued: 03/31/2015
• Est. Priority Date: 12/29/2011
• Status: Active Grant

• Current Assignee: Druva Incorporated
• Original Assignee: Druva Incorporated
• Inventors: Apte, Anand, Puthuparackat, Faisal, Singh, Jaspreet, Borate, Milind, Deshkar, Shekhar S.
• Primary Examiner(s): THAI, HANH B
• Application Number:
  US13/340,441
• Publication Number:
  US 20130173553A1
• Time in Patent Office: 1,188 Days
• Field of Search: 707/640, 707/692, 707/741, 711/118, 711/156, 711/695, 711/822
• US Class Current: 707/640
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00

Abstract

A distributed, cloud-based storage system provides a reliable, deduplicated, scalable and high performance backup service to heterogeneous clients that connect to it via a communications network. The distributed cloud-based storage system guarantees consistent and reliable data storage while using structured storage that lacks ACID compliance. Consistency and reliability are guaranteed using a system that includes: 1) back references from shared objects to referring objects, 2) safe orders of operation for object deletion and creation, 3) and simultaneous access to shared resources through sub-resources.

Claims

1. A computer-implemented method comprising:

receiving at a server, a request from a client device to store data, the request comprising a request checksum computed from the data;

creating an inode entry comprising metadata associated with the data;

accessing a dedupe database, the dedupe database having a plurality of dedupe entries and each dedupe entry comprising a stored checksum;

searching the dedupe database for a matching dedupe entry with a stored checksum equal to the request checksum;

responsive to finding the matching dedupe entry, storing in the matching dedupe entry a back reference to the inode entry, and storing in the inode entry a reference to the matching dedupe entry that further comprises;

searching the dedupe database again for the matching dedupe entry; and

responsive to the matching dedupe entry no longer existing;

receiving the data at the server;

storing the data in a block data store;

creating a new dedupe entry;

storing the request checksum in the new dedupe entry;

storing a reference to the location of the stored data in the new dedupe entry;

storing the new dedupe entry in the dedupe database;

storing a back reference to the inode entry in the new dedupe entry; and

storing in the inode entry a reference to the new dedupe entry; and

storing the inode entry in an inode database.

2. The method of claim 1, further comprising, responsive to finding no dedupe entry with a stored checksum equal to the request checksum:

receiving at the server, the data;

storing the data in a block data store;

creating a new dedupe entry;

storing the request checksum in the new dedupe entry;

storing a reference to the location of the stored data in the new dedupe entry;

storing the new dedupe entry in the dedupe database;

storing a back reference to the inode entry in the new dedupe entry; and

storing in the inode entry a reference to the new dedupe entry.

3. The method of claim 2, wherein receiving at the server, the data, further comprises:

receiving a request to update a resource counter;

responsive to the request, selecting a random sub-resource counter;

determining that the sub-resource counter lock list is empty;

responsive to determining that the sub-resource counter lock list is empty, adding a reference to the sub-resource counter lock list;

determining that the sub-resource counter lock list has at most one reference in it;

responsive to determining that the sub-resource counter has at most one reference in it, locking the sub-resource counter, updating the sub-resource counter, and releasing the lock on the sub-resource counter.

4. The method of claim 3, further comprising:

updating the resource counter using the information in the sub-resource counter.

5. A computer-implemented method comprising:

accessing a data object in a dedupe database referencing a corresponding block data in a block data store, the data object comprising a back reference list to inode entries in an inode database, the back reference list comprising a list of references to back referenced objects, each back referenced object comprising a reference list, the reference list comprising a list of references to objects in the dedupe database;

determining if the back reference list is empty; and

responsive to the back reference list being empty, deleting the data object in the dedupe database.

6. The method of claim 5 further comprising, responsive to the back reference list being non-empty:

accessing a back referenced object;

searching the reference list of the back referenced object for a reference to the data object; and

responsive to no reference to the data object being found in the back referenced object'"'"'s reference list, deleting the reference to the back referenced object in the data object'"'"'s back reference list.

7. The method of claim 6, wherein the data object further comprises a time stamp.

8. The method of claim 7, further comprising, determining if the data object is mature enough to delete based on the time stamp.

9. A computer-implemented method comprising:

accessing a data object in an inode database referenced by a corresponding file entry in a backup directory database, the data object comprising a reference list to dedupe entries in a dedupe database, the reference list comprising a list of references to referenced objects, each referenced object comprising a back reference list, the back reference list comprising a list of references to back referenced objects in the inode database;

accessing a referenced object in the dedupe database;

searching the back reference list of the referenced object for a reference to the data object in the inode database; and

responsive to no reference to the data object being found in the referenced object'"'"'s back reference list, adding a reference to the data object to the referenced object'"'"'s back reference list.

10. A computer for data storage, the computer comprising:

a non-transitory computer-readable storage medium storing executable computer program instructions for;

receiving a request from a client device to store data, the request comprising a request checksum computed from the data;

creating an inode entry comprising metadata associated with the data;

accessing a dedupe database, the dedupe database having a plurality of dedupe entries and each dedupe entry comprising a stored checksum;

searching the dedupe database for a matching dedupe entry with a stored checksum equal to the request checksum;

responsive to finding the matching dedupe entry, storing in the matching dedupe entry a back reference to the inode entry, and storing in the inode entry a reference to the matching dedupe entry that further comprises;

searching the dedupe database again for the matching dedupe entry; and

responsive to the matching dedupe entry no longer existing;

receiving the data;

storing the data in a block data store;

creating a new dedupe entry;

storing the request checksum in the new dedupe entry;

storing a reference to the location of the stored data in the new dedupe entry;

storing the new dedupe entry in the dedupe database;

storing a back reference to the inode entry in the new dedupe entry; and

storing in the inode entry a reference to the new dedupe entry; and

storing the inode entry in an inode database; and

a processor for executing the computer program instructions.

11. The computer of claim 10, further comprising instructions for, responsive to finding no dedupe entry with a stored checksum equal to the request checksum:

receiving the data;

storing the data in a block data store;

creating a new dedupe entry;

storing the request checksum in the new dedupe entry;

storing a reference to the location of the stored data in the new dedupe entry;

storing the new dedupe entry in the dedupe database;

storing a back reference to the inode entry in the new dedupe entry; and

storing in the inode entry a reference to the new dedupe entry.

12. The computer of claim 11, wherein the instructions for receiving the data, further comprise instructions for:

receiving a request to update a resource counter;

responsive to the request, selecting a random sub-resource counter;

determining that the sub-resource counter lock list is empty;

responsive to determining that the sub-resource counter lock list is empty, adding a reference to the sub-resource counter lock list;

determining that the sub-resource counter lock list has at most one reference in it;

responsive to determining that the sub-resource counter has at most one reference in it, locking the sub-resource counter, updating the sub-resource counter, and releasing the lock on the sub-resource counter.

13. The computer of claim 12, further comprising instructions for:

updating the resource counter using the information in the sub-resource counter.

14. A computer for data storage, the computer comprising:

a non-transitory computer-readable storage medium storing executable computer program instructions for;

accessing a data object in a dedupe database referencing a corresponding block data in a block data store, the data object comprising a back reference list to inode entries in an inode database, the back reference list comprising a list of references to back referenced objects, each back referenced object comprising a reference list, the reference list comprising a list of references to objects in the dedupe database;

determining if the back reference list is empty; and

responsive to the back reference list being empty, deleting the data object in the dedupe database; and

a processor for executing the computer program instructions.

15. The computer of claim 14 further comprising instructions for, responsive to the back reference list being non-empty:

accessing a back referenced object;

searching the reference list of the back referenced object for a reference to the data object; and

responsive to no reference to the data object being found in the back referenced object'"'"'s reference list, deleting the reference to the back referenced object in the data object'"'"'s back reference list.

16. The computer of claim 15, wherein the data object further comprises a time stamp.

17. The computer of claim 16, further comprising instructions for, determining if the data object is mature enough to delete based on the time stamp.

18. A computer for data storage, the computer comprising:

A non-transitory computer-readable storage medium storing executable computer program instructions for;

accessing a data object in an inode database reference by a corresponding file entry in a backup directory database, the data object comprising a reference list to dedupe entries in a dedupe database, the reference list comprising a list of references to referenced objects, each referenced object comprising a back reference list, the back reference list comprising a list of references to back referenced objects in the inode database;

accessing a referenced object in the dedupe database;

searching the back reference list of the referenced object for a reference to the data object in the inode database; and

responsive to no reference to the data object being found in the referenced object'"'"'s back reference list, adding a reference to the data object to the referenced object'"'"'s back reference list; and

a processor for executing the computer program instructions.