Granted Patent B2

US 9,336,224 · App. 14/580,246 · Granted May 10, 2016

Abstract

Claims (75)

1. A computer-implemented method for providing increased scalability in deduplication storage systems, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

identifying a database that stores a plurality of reference objects, wherein each reference object within the database comprises a reference list that identifies one or more backed-up files that currently reference a particular unique file segment stored in a deduplication storage system;

determining that the size of the entire database as a whole has reached a predetermined threshold;

in response to determining that the size of the entire database as a whole has reached the predetermined threshold:

partitioning the database into a plurality of sub-databases capable of being updated independent of one another, the plurality of sub-databases comprising an inactive sub-database that is empty after the time of the partition;

designating the inactive sub-database within the plurality of sub-databases as an active sub-database for storing reference objects created after the time of the designation;

identifying a request to perform an update operation that updates one or more reference objects stored within the active sub-database;

performing the update operation only on the active sub-database to avoid processing costs associated with performing the update operation on all of the sub-databases within the plurality of sub-databases, wherein the update operation comprises adding a reference that identifies a particular backed-up file to one or more reference lists stored within the active sub-data base.

2. The computer-implemented method of claim 1 , wherein determining that the size of the entire database as a whole has reached the predetermined threshold comprises at least one of:

determining that the number of reference objects stored within the database has reached a predetermined threshold;

determining that the reference objects stored within the database are consuming a predetermined amount of storage space.

3. The computer-implemented method of claim 1 , wherein partitioning the database into the plurality of sub-databases comprises storing, within another sub-database within the plurality of sub-databases, the reference objects contained in the database at the time of the partition.

4. The computer-implemented method of claim 1 , further comprising identifying another database that stores another plurality of reference objects that each comprise a reference count that identifies the number of backed-up files that currently reference a particular unique file segment stored in the deduplication storage system.

5. The computer-implemented method of claim 1 , further comprising performing another update operation only on the active sub-database, wherein the other update operation comprises at least one of:

removing a reference that identifies a particular backed-up file from one or more reference lists stored within the active sub-database;

creating, within the active sub-database, a new reference list for identifying one or more backed-up files that reference a new unique file segment added to the deduplication storage system.

6. The computer-implemented method of claim 4 , further comprising performing another update operation only on an active sub-database of the other database, wherein the other update operation comprises at least one of:

increasing at least one reference count to indicate that an increased number of backed-up files currently reference a particular unique file segment;

decreasing at least one reference count to indicate that a decreased number of backed-up files currently reference a particular unique file segment;

creating, within the active sub-database of the other database, a new reference count for identifying the number of backed-up files that currently reference a new unique file segment added to the deduplication storage system.

7. The computer-implemented method of claim 1 , further comprising:

upon performing the update operation, determining that one of the reference objects updated by the update operation indicates that no backed-up files currently reference a particular unique file segment stored in the deduplication storage system;

marking the unique file segment associated with the reference object to be reclaimed by the deduplication storage system.

8. The computer-implemented method of claim 1 , further comprising identifying another request to perform another update operation that updates one or more reference objects stored within at least one different sub-database within the plurality of sub-data bases;

wherein performing the update operation only on the active sub-database comprises simultaneously performing the update operation on the active sub-database and the other update operation on the different sub-database.

9. The computer-implemented method of claim 1 , wherein performing the update operation only on the active sub-database comprises:

postponing performing the update operation until identifying a predetermined number of other requests to perform other update operations on the active sub-database;

identifying other requests to perform other update operations on the active sub-data base;

determining that the number of the other requests identified has reached the predetermined number of other requests;

sequentially performing the update operation and the other update operations on the active sub-database.

10. The computer-implemented method of claim 1 , further comprising:

determining that at least one size-related characteristic of at least one sub-database has reached a predetermined threshold;

partitioning the sub-database into a plurality of additional sub-databases capable of being updated independent of one another.

11. A system for providing increased scalability in deduplication storage systems, the system comprising:

an identification module, stored in memory, that identifies a database that stores a plurality of reference objects, wherein each reference object within the database comprises a reference list that identifies one or more backed-up files that currently reference a particular unique file segment stored in a deduplication storage system;

a partitioning module, stored in memory, that:

determines that the size of the entire database as a whole has reached a predetermined threshold;

in response to determining that the size of the entire database as a whole has reached the predetermined threshold:

partitions the database into a plurality of sub-databases capable of being updated independent of one another, the plurality of sub-databases comprising an inactive sub-database that is empty after the time of the partition;

designates the inactive sub-database within the plurality of sub-databases as an active sub-database for storing reference objects created after the time of the designation;

an update module, stored in memory, that:

identifies a request to perform an update operation that updates one or more reference objects stored within the active sub-database;

performs the update operation only on the active sub-database to avoid processing costs associated with performing the update operation on all of the sub-databases within the plurality of sub-databases, wherein the update operation comprises adding a reference that identifies a particular backed-up file to one or more reference lists stored within the active sub-database;

at least one physical processor that executes the identification module, the partitioning module, and the update module.

12. The system of claim 11 , wherein the partitioning module determines that the size of the entire database as a whole has reached the predetermined threshold by at least one of:

determining that the number of reference objects stored within the database has reached a predetermined threshold;

determining that the reference objects stored within the database are consuming a predetermined amount of storage space.

13. The system of claim 11 , wherein the partitioning module stores, within another sub-database within the plurality of sub-databases, the reference objects contained in the database at the time of the partition.

14. The system of claim 11 , wherein the identification module identifies another database that stores another plurality of reference objects that each comprise a reference count that identifies the number of backed-up files that currently reference a particular unique file segment stored in the deduplication storage system.

15. The system of claim 11 , wherein the update module performs another update operation only on the active sub-database, the other update operation comprising at least one of:

removing a reference that identifies a particular backed-up file from one or more reference lists stored within the active sub-database;

creating, within the active sub-database, a new reference list for identifying one or more backed-up files that reference a new unique file segment added to the deduplication storage system.

16. The system of claim 14 , wherein the update module performs another update operation only on the active sub-database, the other update operation comprising at least one of:

increasing at least one reference count to indicate that an increased number of backed-up files currently reference a particular unique file segment;

decreasing at least one reference count to indicate that a decreased number of backed-up files currently reference a particular unique file segment;

creating, within the active sub-database, a new reference count for identifying the number of backed-up files that currently reference a new unique file segment added to the deduplication storage system.

17. The system of claim 11 , wherein the update module:

determines that, upon performing the update operation, one of the reference objects updated by the update operation indicates that no backed-up files currently reference a particular unique file segment stored in the deduplication storage system;

marks the unique file segment associated with the reference object to be reclaimed by the deduplication storage system.

18. The system of claim 11 , wherein the update module:

identifies another request to perform another update operation that updates one or more reference objects stored within at least one different sub-database within the plurality of sub-databases;

simultaneously performs the update operation on the active sub-database and the other update operation on the different sub-database.

19. The system of claim 11 , wherein the update module:

postpones performing the update operation until identifying a predetermined number of other requests to perform other update operations on the active sub-database;

identifies other requests to perform other update operations on the same sub-database;

determines that the number of the other requests identified has reached the predetermined number of other requests;

sequentially performs the update operation and the other update operations on the active sub-database.

20. A non-transitory computer-readable-storage medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

identify a database that stores a plurality of reference objects, wherein each reference object within the database comprises a reference list that identifies one or more backed-up files that currently reference a particular unique file segment stored in a deduplication storage system;

determine that the size of the entire database as a whole has reached a predetermined threshold;

in response to determining that the size of the entire database as a whole has reached the predetermined threshold:

partition the database into a plurality of sub-databases capable of being updated independent of one another, the plurality of sub-databases comprising an inactive sub-database that is empty after the time of the partition;

designate the inactive sub-database within the plurality of sub-databases as an active sub-database for storing reference objects created after the time of the designation;

identify a request to perform an update operation that updates one or more reference objects stored within the active sub-database;

perform the update operation only on the active sub-database to avoid processing costs associated with performing the update operation on all of the sub-databases within the plurality of sub-databases, wherein the update operation comprises adding a reference that identifies a particular backed-up file to one or more reference lists stored within the active sub-database.

Assignments (13)