Systems and methods for removing unreferenced data segments from deduplicated data systems

A computer-implemented method for removing unreferenced data segments from deduplicated data systems may include: 1) identifying a deduplicated data system that contains a plurality of data segments, 2) identifying a plurality of containers within the deduplicated data system, with each container containing a subset of the data segments within the deduplicated data system, 3) identifying at least one container within the plurality of containers that is likely to include a large proportion of data segments that are not referenced by data objects within the deduplicated data system, and then, for each identified container, 4) searching for unreferenced data segments within the identified container and 5) removing the unreferenced data segments from the identified container. Various other methods, systems, and computer-readable media are also disclosed.

BACKGROUND

Deduplicated data systems are often able to reduce the amount of space required to store files by recognizing redundant data patterns. For example, a deduplicated data system may reduce the amount of space required to store similar files by dividing the files into data segments and storing only unique data segments. In this example, each deduplicated file may simply consist of a list of data segments that make up the file.

While conventional deduplicated data systems may reduce the space required to store files, the mechanisms used by such conventional systems to manage deduplicated data may present unwanted limitations. For example, since more than one file may reference any given data segment, the data segments that make up a file cannot simply all be removed when the file is deleted. In order to safely delete data segments, a deduplicated data system must distinguish between referenced and unreferenced data segments.

In some cases, conventional deduplicated data systems may use bilateral referencing systems in order to ensure that data segments are not prematurely removed. For example, each file in a conventional deduplicated data system may include a list of data segments that make up the file. Likewise, each data segment within the deduplicated data system may maintain a list that identifies each file within the system that references the data segment. The deduplicated data system may use the lists maintained by both the files and the data segments to identify unreferenced data segments (i.e., data segments that are no longer referenced by any of the files in the deduplicated data system) that may be removed from the system.

Unfortunately, the bilateral referencing systems used by many conventional deduplicated data systems suffer from a number of deficiencies. For example, when a file in a conventional deduplicated data system is updated, the system may need to update both the referential list maintained by the file and the referential list maintained by each data segment referenced by the file. The process of creating and updating two referential lists may be both time consuming and resource intensive.

In other examples, conventional deduplicated data systems may use mark-and-sweep systems in order to ensure that data segments are not prematurely removed. For example, a deduplicated data system may check each data segment to see if that data segment is referenced by any file in the deduplicated data system. In this example, if a mark-and-sweep system finds a file that includes the data segment, the mark-and-sweep system may mark the data segment as referenced. The mark-and-sweep system may then sweep the deduplicated data system for unmarked data segments and delete the unmarked data segments. Unfortunately, a brute force approach of checking each data segment may also be time consuming and resource intensive. Accordingly, the instant disclosure identifies a need for efficiently marking and sweeping unreferenced data segments in deduplicated data systems.

SUMMARY

As will be described in greater detail below, the instant disclosure generally relates to systems and methods for efficiently removing unreferenced data segments from deduplicated data systems by focusing mark-and-sweep operations on groups of data segments that are likely to include large proportions of unreferenced data segments. In one example, one or more of the various systems described herein may accomplish this task by: 1) identifying a deduplicated data system that contains a plurality of data segments, 2) identifying a plurality of containers within the deduplicated data system that contain a subset of the data segments within the deduplicated data system, 3) identifying at least one container within the plurality of containers that is likely to include a large proportion of data segments that are not referenced by data objects within the deduplicated data system, and, for each identified container, 4) searching for unreferenced data segments within the identified container and then 5) removing the unreferenced data segments from the identified container.

In some examples, the subset of data segments contained within each of the plurality of containers may include interrelated data segments (e.g., data segments likely to be dereferenced at or near the same time). Due to this interrelation, some containers may include significantly more unreferenced data segments than others.

In some embodiments, identifying at least one container within the plurality of containers that is likely to include a large proportion of unreferenced data segments may entail sampling data segments from the containers. A method for accomplishing this task may include: 1) identifying a sample of data segments within the plurality of data segments, 2) identifying unreferenced data segments within the sample of data segments, and, for each unreferenced data segment, 3) identifying a container that contains the unreferenced data segment. In some examples, identifying the sample may include randomly selecting the sample. In certain embodiments, identifying the sample may include selecting the sample from an index of data segments within the deduplicated data system.

In some contexts, the data in the deduplicated data system may be divided into data selections (e.g., backup instances). Each data selection may reference some of the data objects in the deduplicated data system. In these contexts, identifying data segments within the sample of data segments that are not referenced by data objects within the deduplicated data system may include identifying a plurality of data selections within the deduplicated data system and creating a list of data objects that are referenced by at least one data selection within the plurality of data selections. In some examples, creating the list of referenced data objects may include: 1) identifying at least one active data selection within the plurality of data selections that has had a relatively large number of data objects removed since the last time the active data selection was analyzed, 2) analyzing the active data selection to identify each data object referenced by the active data selection, and then 3) including each data object referenced by the active data selection in the list of referenced data objects.

In some examples, creating the list of referenced data objects also may include: 1) identifying at least one inactive data selection within the plurality of data selections that has had relatively few data objects removed since the last time the inactive data selection was analyzed, 2) including each data object marked as referenced by the inactive data selection in the list of referenced data objects, and 3) including each data object recently added to the inactive data selection in the list of referenced data objects.

In certain contexts, a data index may map data segments in the deduplicated data system to their respective containers. In these contexts, identifying (for each unreferenced data segment) a container that contains the unreferenced data segment may include identifying a fingerprint of the unreferenced data segment and querying a data index of the deduplicated data system using the fingerprint to locate the container of the unreferenced data segment.

In some examples, a container may include a large proportion of unreferenced data segments if it includes a proportion of unreferenced data segments exceeding a predetermined threshold. In other examples, a container may include a large proportion of unreferenced data segments if it includes a larger proportion of unreferenced data segments than other containers.

The search for unreferenced data segments within the identified container (for each identified container) may operate in a variety of ways. In some examples, searching for unreferenced data segments within the identified container may entail exhaustively searching for unreferenced data segments within the identified container. In other embodiments, the search may include marking referenced data segments within the identified container as referenced and then identifying unmarked data segments.

In some embodiments, the method may also include, for each container not identified as likely to include a large proportion of unreferenced data segments: 1) identifying a list of data segments in the container previously marked as referenced, 2) identifying a set of data segments recently added to the container, and then 3) adding the set of data segments recently added to the container to the list of marked data segments in the container.

As will be explained below, by focusing mark-and-sweep procedures on containers that are more likely to include a proportionally large number of unreferenced data segments, the systems and methods described herein may efficiently delete unreferenced data segments by reducing the amount of computing resources consumed per data-segment deletion. Moreover, in some cases the systems and methods described herein may also improve the analysis of data selections in the course of mark-and-sweep procedures by only fully analyzing data selections that have had a large number of data objects removed.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

As will be described in greater detail below, the instant disclosure generally relates to systems and methods for efficiently removing unreferenced data segments from deduplicated data systems. The phrase “deduplicated data system,” as used herein, generally refers to storage systems that reduce redundant data by only storing a single instance of data (e.g., a data segment), potentially referencing each data instance multiple times. Examples of deduplicated data systems may include SYMANTEC's NETBACKUP PUREDISK. As will be described in greater detail below, a single instance of data may be referenced by a single data object (e.g., a file) or a plurality of data objects within the deduplicated data system.

The following will provide, with reference toFIGS. 1-2, detailed descriptions of exemplary systems for removing unreferenced data segments from deduplicated data systems. Detailed descriptions of corresponding computer-implemented methods will also be provided in connection withFIGS. 3-7. In addition, detailed descriptions of an exemplary computing system and network architecture capable of implementing one or more of the embodiments described herein will be provided in connection withFIGS. 8 and 9, respectively.

FIG. 1is a block diagram of an exemplary system100for removing unreferenced data segments from deduplicated data systems. As illustrated in this figure, exemplary system100may include one or more modules102for performing one or more tasks. For example, and as will be explained in greater detail below, exemplary system100may include an identification module104programmed to identify a deduplicated data system that contains a plurality of data segments. Identification module104may also be programmed to identify a plurality of containers within the deduplicated data system, each of which may contain a subset of the data segments within the deduplicated data system. Exemplary system100may also include a targeting module105programmed to identify at least one container within the plurality of containers that is likely to include a large proportion of data segments that are not referenced by data objects within the deduplicated data system.

Exemplary system100may also include a marking module106programmed to search for unreferenced data segments within each identified container (e.g., by marking referenced data segments within each identified container and locating unmarked data segments). In addition, and as will be described in greater detail below, exemplary system100may include a sweeping module108programmed to remove unreferenced data segments from each identified container. Although illustrated as separate elements, one or more of modules102inFIG. 1may represent portions of a single module or application.

As illustrated inFIG. 1, exemplary system100may also include a deduplicated data system120. Deduplicated data system120may represent portions of a single storage system or computing device or a plurality of storage systems or computing devices. For example, deduplicated data system120may represent a portion of computing system202inFIG. 2, computing system810inFIG. 8, and/or portions of exemplary network architecture900inFIG. 9. Alternatively, deduplicated data system120inFIG. 1may represent one or more physically separate devices capable of being accessed by a computing device, such as computing system810inFIG. 8and/or portions of exemplary network architecture900inFIG. 9.

Exemplary system100may be deployed in a variety of ways. For example, all or a portion of exemplary system100may represent portions of an exemplary system200inFIG. 2. As shown inFIG. 2, exemplary system200may include a computing system202including deduplicated data system120fromFIG. 1. In one embodiment, and as will be described in greater detail below, modules102fromFIG. 1may program computing system202to: 1) identify a deduplicated data system (such as deduplicated data system120) that contains a plurality of data segments (such as data segments224), 2) identify a plurality of containers within the deduplicated data system (such as containers226), with each container containing a subset of the data segments within the deduplicated data system, 3) identify at least one container within the plurality of containers that is likely to include a large proportion of data segments that are not referenced by data objects within the deduplicated data system (such as data objects222), and, for each identified container, 4) search for unreferenced data segments within the identified container and then 5) remove the unreferenced data segments from the identified container (e.g., delete the unreferenced data segments within the identified container).

Computing system202generally represents any type or form of computing device capable of reading computer-executable instructions. Examples of computing system202include, without limitation, laptops, desktops, servers, cellular phones, personal digital assistants (PDAs), multimedia players, embedded systems, combinations of one or more of the same, exemplary computing system810inFIG. 8, or any other suitable computing device.

FIG. 3is a flow diagram of an exemplary computer-implemented method300for removing unreferenced data segments from deduplicated data systems. The steps shown inFIG. 3may be performed by any suitable computer-executable code and/or computing system. In some embodiments, the steps shown inFIG. 3may be performed by one or more of the components of system100inFIG. 1, system200inFIG. 2, and/or system800inFIG. 8.

As illustrated inFIG. 3, at step302one or more of the systems described herein may identify a deduplicated data system that contains a plurality of data segments. For example, at step302identification module104fromFIG. 1may, as part of computing system202inFIG. 2, identify deduplicated data system120. As used herein, the term “data segment” may refer to a segment of data, a block of data, or any other suitable unit of data used for data deduplication.

Identification module104may perform step302in any suitable manner. In one example, identification module104may identify the deduplicated data system by reading a configuration file associated with the deduplicated data system. Additionally or alternatively, identification module104may identify the deduplicated data system by identifying (e.g., intercepting, receiving, or retrieving) a request to remove unreferenced data segments from the deduplicated data system. In some contexts, identification module104may be an extension and/or a component of the deduplicated data system, and may implicitly identify the deduplicated data system simply through the context in which it is executing.

At step304, one or more of the systems described herein may identify a plurality of containers within the deduplicated data system. In some examples, each container may include a subset of the data segments within the deduplicated data system. For example, at step304identification module104inFIG. 1may, as part of computing system202inFIG. 2, identify containers226within deduplicated data system120. As used herein, the term “container” may refer to any data structure, storage system, and/or location that stores, contains, includes, and/or points to a subset of data segments.

In some contexts, the subset of data segments contained within each given container in the plurality of containers may be interrelated. For example, the data segments of the deduplicated data system may be non-randomly distributed among the containers. In some contexts, this non-random distribution may arise because the containers may contain or tend to contain data segments from interrelated data objects. For example, if the deduplicated data system is part of a backup system, the deduplicated data system may store (or attempt to store) the data segments of all files in a given backup in the same container or set of containers. Since the files in a given backup may tend to be removed together (e.g., if the backup is deleted), many of the data segments of those files may become unreferenced at the same time. As will be described in greater detail below, the container or set of containers used for that backup may then have a disproportionately large number of unreferenced data segments, making that container or set of containers a good target for a focused mark-and-sweep operation. While the backup data deduplication system described in the example above may be suitable for the methods and systems described herein, any deduplicated data system that may, for any reason, lead to an uneven distribution of unreferenced data segments across containers may also be suitable.

Identification module104may perform step304in any suitable manner. For example, identification module104may identify the plurality of containers by reading a configuration file associated with the containers (e.g., a configuration file of the deduplicated data system identifying the containers). Additionally or alternatively, identification module104may identify the plurality of containers by receiving and/or intercepting a message identifying the containers.

Returning toFIG. 3, at step306one or more of the systems described herein may identify at least one container (e.g., each container) within the plurality of containers that is likely to include a large proportion of data segments that are not referenced by data objects within the deduplicated data system. For example, targeting module105inFIG. 1may, as part of computing system202inFIG. 2, identify at least one container within containers226that is likely to include a large proportion of data segments that are not referenced by data objects222. As used herein, the term “data object” may refer to any collection of data suitable for deduplication, such as a file.

By way of example and to further illustrate the description of the steps inFIG. 3,FIG. 4shows an exemplary deduplicated data system400. As illustrated inFIG. 4, exemplary deduplicated data system400may include data objects402-412. Each of these data objects may include references to data segments (e.g., some of data segments422-458). For example, data object402may include references to data segments422,424,426, and428. Data segments422-458may be organized into, stored in, or allocated to containers (e.g., containers460and470). For example, data segments422-438may be stored in container460and data segments442-458may be stored in container470.

Some data segments may be referenced by only one data object (such as data segment424, which is only referenced by data object402). Other data segments may be referenced by more than one data object (such as data segment428, which is referenced by data objects402,404, and406). For example, in the example illustrated inFIG. 5(which is an illustration of exemplary deduplicated data system400in a different state), data objects402and404may have been deleted. This operation may leave some, but not all, of the data segments included by data objects402and404unreferenced. For example, data object402may have originally referenced data segments422,424,426, and428. After removing data object402, data segments422,426, and428may still be referenced by at least one data object (in this case, data object406), while data segment424may not be referenced by any data object and should therefore be deleted to recover storage space on the deduplicated data system.

Returning to step306ofFIG. 3, targeting module105may identify one or more containers that are likely to include a large proportion of data segments in a variety of ways. In one example, targeting module105may keep a tally for each container indicating the number of times that a data object that referenced a data segment within the container has been deleted. In this example, a high tally may indicate a likelihood of a large number of unreferenced data segments.

In another example, targeting module105may: 1) sample data segments from the containers, 2) analyze the sample, and then 3) extrapolate information about the container based on the sample. For example, targeting module105may identify a sample of data segments within the plurality of data segments, determine which data segments in the sample are not referenced by data objects within the deduplicated data system, and then identify a container containing each unreferenced data segment in the sample. In this example, targeting module105may then create a frequency table or a similar data structure to compare the relative incidence of unreferenced data segments within the sample across containers. A large proportion of unreferenced data segments in the sample for a given container may indicate a large proportion of unreferenced data segments within the container.

Targeting module105may identify the sample of data segments in the above example in a number of ways. In one example, targeting module105may identify the sample of data segments by randomly selecting the sample of data segments. For example, targeting module105may use a pseudorandom number generator to generate a series of numbers that map to data segments in the deduplicated data system. In some examples, targeting module105may guarantee that an equal and/or proportionate number of data segments are sampled from each container.

Targeting module105may select the sample of data segments from a number of sources. For example, targeting module105may select the sample of data segments from containers, from data objects, and/or any other data structure that references the data segments. In one example, targeting module105may select the sample of data segments from an index of data segments within the deduplicated data system. This index of data segments may include any data structure that indexes data segments and/or data objects containing data segments. In some examples, this index of data segments may include fingerprints (e.g., unique identifiers) of each data segment in the deduplicated data system. In some embodiments, the index of data segments may provide indexing for the entire deduplicated data system. In addition, the index of data segments may include several indexes and/or data structures that provide indexing for the deduplicated data system.

FIG. 6is a block diagram illustrating an exemplary sampling of an exemplary index610within an exemplary deduplicated data system600. As illustrated inFIG. 6, index610may index data segments422-458(e.g., fromFIGS. 4-5). Targeting module105may randomly sample fingerprints of data segments from index610, creating a sample660. In this example, sample660may include fingerprints corresponding to data segments422,426,430,436,446,448,454, and456.

Returning to step306ofFIG. 3, as previously mentioned targeting module105may identify data segments within the sample of data segments that are not referenced by data objects within the deduplicated data system. In the example illustrated inFIG. 6and described above, targeting module105may identify data segments within sample660that are not referenced by data objects (e.g., data objects406-412ofFIG. 5) within the deduplicated data system. As illustrated inFIG. 5, after the deletion of data objects402and404, two of the data segments included in sample660(data segments430and436) may be left unreferenced.

Targeting module105may identify data segments within the sample of data segments that are not referenced by data objects within the deduplicated data system in a variety of contexts. In some contexts, the deduplicated data system may include data selections. As used herein, the term “data selection” may refer to any selection, collection, and/or grouping of data objects within the deduplicated data system. For example, a data selection may refer to a backup (e.g., a collection of backed up data objects). In this example, a data selection may include metadata associated with data objects that are backed up, fingerprints of the backed up files, and/or references to data objects.

FIG. 7illustrates an exemplary deduplicated data system700having two data selections: data selection702and data selection704. Each data selection may include (e.g., reference) a number of data objects. For example, data selection702may include data objects402-412(e.g., fromFIGS. 4-5) and data selection704may include data objects712-722. As illustrated in bothFIG. 5andFIG. 7, data objects402and404may be deleted and/or in the process of deletion.

In contexts where the deduplicated data system includes data selections, targeting module105may create a list of data objects to check for references to the sampled data segments. For example, targeting module105may identify a plurality of data selections within the deduplicated data system and create a list of data objects that are referenced by at least one data selection within the plurality of data selections. These steps may be helpful or necessary when determining which data objects are in use by any data selection. For example, data object404in data selection702and data object714in data selection704may be the same data object. In this example, even though a reference to data object404is deleted from data selection702, data object404(i.e., data object714) must not be deleted since data selection704still references data object714.

Targeting module105may identify data selections in any suitable manner. For example, targeting module105may identify a plurality of data selections by reading from a configuration file associated with the plurality of data selections. Additionally or alternatively, targeting module105may identify a plurality of data selections by identifying (e.g., receiving, intercepting, and/or retrieving) a message identifying the plurality of data selections.

Targeting module105may create a list of referenced data objects in a variety of ways. In some examples, targeting module105may create the list of referenced data objects by culling a list of referenced data objects from each data selection within the plurality of data selections. For example, targeting module105may identify both “active” data selections and “inactive” data selections. Active data selections may include each data selection from which a relatively large number of data objects have been removed since the last time the active data selection was analyzed. In contrast, inactive data selections may include all data selections that are not identified as “active” (e.g., data selections from which relatively few data objects have been removed since the last time the active data selection was analyzed).

Targeting module105may determine that a relatively large number of data objects have been removed from a data selection in a variety of ways. For example, targeting module105may determine that the number of data objects removed from an active data selection (e.g., the absolute number or proportionate number of data objects removed) exceeds a predetermined threshold. Additionally or alternatively, targeting module105may determine that the number of data objects removed from an active data selection exceeds the number removed from one or more other data selections. In some embodiments, targeting module105may be able to directly determine the exact number of data objects removed from each data selection by observing the removal of the data objects and counting the number of data objects removed (e.g., targeting module105may count the number of data objects removed from a relational table). In certain embodiments, targeting module105may also account for the size of the data objects removed (e.g., targeting module105may determine that a relatively large number of data objects have been removed if the cumulative size of the data objects exceeds a predetermined threshold).

UsingFIG. 7as an example, targeting module105may identify data selection702as active since two data objects (data objects402and404) have been removed from data selection702. In contrast, targeting module105may identify data selection704as inactive since no data objects have been removed from data selection704. In this example, targeting module105may determine that702is active due to a predetermined threshold (e.g., more than 20 percent of the data objects have been removed), or due to a relative comparison (e.g., data selection702has a higher percentage of removed data objects than any other data selection).

In some embodiments, in the course of culling a list of referenced data objects from each data selection to create a list of referenced data objects within the deduplicated data system, targeting module105may treat active and inactive data selections differently. For example, targeting module105may analyze each active data selection to determine exactly which files in the active data selection are no longer referenced (e.g., included in a data selection). Targeting module105may then add only those files confirmed (e.g., marked) as referenced in the list of referenced data objects within the deduplicated data system.

In the case of inactive data selections, targeting module105may make simplifying assumptions, adding data objects which are most likely still referenced to the list of referenced data objects. For example, targeting module105may include each data object marked as referenced by the inactive data selection in the list of referenced data objects and also include each data object recently added to the inactive data selection in the list of referenced data objects. In the above examples, targeting module105may effectively create a list of referenced data objects that is mostly accurate (e.g., a majority data objects on the list may still be included within a data selection, although a few may no longer be).

As will be described in greater detail below, since the above-described list of referenced data objects may be used to identify data segments that are still referenced by at least one data object, including a small number of data objects that are no longer included in any data selection may make the list of referenced data objects slightly overbroad, potentially leading to marking some data segments as referenced even though the only data objects referencing them are invalid. However, by only analyzing active data selections (e.g., data selections with many data objects removed), this drawback may be minimized while saving significant amounts of time and computing resources.

Returning to step306ofFIG. 3, as mentioned earlier targeting module105may, for each unreferenced data segment, identify a container that contains the unreferenced data segment. UsingFIGS. 5-6as an example, targeting module105, having identified data segments430and436as unreferenced data segments within sample660, may identify both data segments as belonging to container460.

Targeting module105may identify a container that contains an unreferenced data segment in any suitable manner. For example, targeting module105may identify a fingerprint of the unreferenced data segment and query a data index of the deduplicated data system using the fingerprint to locate the container of the unreferenced data segment. As used herein, the term “fingerprint” may refer to any fingerprint, hash, checksum, and/or unique identifier of a unit of data. UsingFIGS. 5-6as an example, targeting module105may query index610with a fingerprint of unreferenced data segment430and receive information from index610indicating that data segment430is contained within container460.

Returning to step306ofFIG. 3, targeting module105may identify that a container has a large proportion of unreferenced data segments based on a variety of criteria. For example, targeting module105may identify that the container includes a proportion of unreferenced data segments that exceeds a predetermined threshold. In another example, targeting module105may determine that the amount of data that the unreferenced data segments represent exceeds a predetermined threshold (by determining, e.g., that the number of bytes that would be freed if the unreferenced data segments were removed exceeds a predetermined threshold). Additionally or alternatively, targeting module105may determine that the container includes a larger proportion of unreferenced data segments than other containers. UsingFIG. 5as an example, four out of the nine data segments within container460may be unreferenced after the deletion of data objects402and404(data segments424,430,434, and436). In contrast, none of the data segments within container470may be unreferenced. In this example, targeting module105may determine that container460has a large proportion of unreferenced data segments since the percentage of unreferenced data segments within contain460(in this example, 44 percent) exceeds a predetermined threshold (e.g., 25 percent), and/or because container460has a larger proportion of unreferenced data segments than container470. As described earlier, targeting module105may merely estimate the proportion of unreferenced data segments in each container. As long as the estimation approach is reasonably accurate, targeting module105may correctly identify those containers that have a large proportion of unreferenced data segments.

Returning toFIG. 3, at step308one or more of the systems described herein may, for each identified container, search for unreferenced data segments within the identified container. For example, marking module106inFIG. 1may, as part of computing system202inFIG. 2, search for unreferenced data segments within each of containers226that has been identified as likely to contain a large proportion of unreferenced data segments. According to some examples described above and illustrated inFIG. 5, targeting module105may have identified container460as likely to contain a large proportion of unreferenced data segments. In these examples, marking module106may search for unreferenced data segments within container460.

Marking module106may search for data segments within the identified container using a variety of approaches. For example, marking module106may access an identified container and search through each data segment within the identified container. Additionally or alternatively, marking module106may search through a data structure related to an identified container that may serve as a proxy for the identified container (e.g., the data structure may include both a majority of the data segments included within the identified container and relatively few data segments that are not included within the identified container).

In some embodiments, marking module106may exhaustively search for unreferenced data segments within the identified container (by, e.g., checking every data segment within the container). Alternatively, marking module106may perform an extensive but not exhaustive search for unreferenced data segments within the identified container (by, e.g., checking a majority of data segments within the container but skipping some data segments for efficiency purposes). In various embodiments, marking module106may perform a more extensive search for unreferenced data segments within the identified container than for unreferenced data segments within containers not identified as likely to include many unreferenced data segments.

Marking module106may search for unreferenced data segments within the identified container in a variety of ways. In some examples, marking module106may search for unreferenced data segments within the identified container as part of a mark-and-sweep process. For example, marking module106may mark referenced data segments within the identified container as referenced and then identify unmarked data segments. In this example, marking module106may mark referenced data segments in the identified container by checking each data segment in the identified container against a list of data objects in the deduplicated data system and marking a data segment when a data object that references the data segment is found.

According to some embodiments, marking module106may also mark data segments within containers that are not identified as likely to include a large proportion of unreferenced data segments. Rather than extensively analyzing these containers, however, marking module106may simply, for each container not identified, combine old marking results for the container with information on data segments recently added to the container. For example, marking module106may: 1) identify a list of data segments within the container that were previously marked as referenced, 2) identify a set of data segments recently added to the container, and then 3) add the set of data segments recently added to the container to the list of marked data segments within the container. Data segments recently added to the container may include data segments added to the container since the last marking operation performed on data segments in the container.

By using old marking results and marking newly added data segments, marking module106may efficiently ensure that referenced data segments within containers that were not identified as likely to contain unreferenced data segments do not remain unmarked. While relatively few unreferenced data segments may become marked in this method, the computing resources saved by not extensively analyzing a container that may have a small proportion of unreferenced data segments may outweigh the marginal benefit of removing this relatively small number of unreferenced data segments.

Returning toFIG. 3, at step310sweeping module108may remove the unreferenced data segments from the identified container (e.g., from each container identified as likely to have a large proportion of unreferenced data segments). For example, sweeping module108may, as part of computing system202, remove unreferenced data segments from a container within containers226that was identified as likely to have a large proportion of unreferenced data segments.

Sweeping module108may perform step310in any suitable manner. For example, if marking module106identified unreferenced data segments by marking referenced data segments, sweeping module108may remove unmarked data segments from the identified container.

While the foregoing descriptions and examples may refer to data objects as files and data segments as file portions, the methods and systems described herein may apply to any level of data deduplication. For example, if data selections within a deduplicated data system are grouped into “data super-selections,” the methods and systems described herein may identify those data super-selections that have (or are likely to have) data selections that would benefit most from an extensive analysis and, subsequently, focus a mark-and-sweep operation on those data super-selections.

The systems and methods described herein improve the efficiency of unreferenced data segment removal in a variety of contexts. In one example, an archiving system (such as SYMANTEC's ENTERPRISE VAULT) may retain seven years worth of backup data. During those seven years, the backup data may reside on the archiving system without inspection. Performing an extensive analysis of the entire seven years' worth of backup data may consume a large amount of computing resources. By focusing the analysis, the methods and systems described herein may detect that the containers with the most reclaimable space are those that are approximately seven years old. These containers may be analyzed extensively, while the remaining containers may be analyzed less extensively using approximation techniques.

As detailed above, by focusing mark-and-sweep procedures on containers that are more likely to include a proportionally large number of unreferenced data segments, the systems and methods described herein may efficiently delete unreferenced data segments by reducing the amount of computing resources consumed per data-segment deletion. Moreover, in some cases the systems and methods described herein may also improve the analysis of data selections in the course of mark-and-sweep procedures by only fully analyzing data selections that have had a large number of data objects removed.

FIG. 8is a block diagram of an exemplary computing system810capable of implementing one or more of the embodiments described and/or illustrated herein. Computing system810broadly represents any single or multi-processor computing device or system capable of executing computer-readable instructions. Examples of computing system810include, without limitation, workstations, laptops, client-side terminals, servers, distributed computing systems, handheld devices, or any other computing system or device. In its most basic configuration, computing system810may include at least one processor814and a system memory816.

Processor814generally represents any type or form of processing unit capable of processing data or interpreting and executing instructions. In certain embodiments, processor814may receive instructions from a software application or module. These instructions may cause processor814to perform the functions of one or more of the exemplary embodiments described and/or illustrated herein. For example, processor814may perform and/or be a means for performing, either alone or in combination with other elements, one or more of the identifying, selecting, creating, analyzing, including, querying, searching, marking, adding, and/or removing steps described herein. Processor814may also perform and/or be a means for performing any other steps, methods, or processes described and/or illustrated herein.

System memory816generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data and/or other computer-readable instructions. Examples of system memory816include, without limitation, random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory device. Although not required, in certain embodiments computing system810may include both a volatile memory unit (such as, for example, system memory816) and a non-volatile storage device (such as, for example, primary storage device832, as described in detail below). In one example, one or more of modules102fromFIG. 1may be loaded into system memory816.

In certain embodiments, exemplary computing system810may also include one or more components or elements in addition to processor814and system memory816. For example, as illustrated inFIG. 8, computing system810may include a memory controller818, an Input/Output (I/O) controller820, and a communication interface822, each of which may be interconnected via a communication infrastructure812. Communication infrastructure812generally represents any type or form of infrastructure capable of facilitating communication between one or more components of a computing device. Examples of communication infrastructure812include, without limitation, a communication bus (such as an ISA, PCI, PCIe, or similar bus) and a network.

Memory controller818generally represents any type or form of device capable of handling memory or data or controlling communication between one or more components of computing system810. For example, in certain embodiments memory controller818may control communication between processor814, system memory816, and I/O controller820via communication infrastructure812. In certain embodiments, memory controller818may perform and/or be a means for performing, either alone or in combination with other elements, one or more of the steps or features described and/or illustrated herein, such as identifying, selecting, creating, analyzing, including, querying, searching, marking, adding, and/or removing.

I/O controller820generally represents any type or form of module capable of coordinating and/or controlling the input and output functions of a computing device. For example, in certain embodiments I/O controller820may control or facilitate transfer of data between one or more elements of computing system810, such as processor814, system memory816, communication interface822, display adapter826, input interface830, and storage interface834. I/O controller820may be used, for example, to perform and/or be a means for performing, either alone or in combination with other elements, one or more of the identifying, selecting, creating, analyzing, including, querying, searching, marking, adding, and/or removing steps described herein. I/O controller820may also be used to perform and/or be a means for performing other steps and features set forth in the instant disclosure.

Communication interface822broadly represents any type or form of communication device or adapter capable of facilitating communication between exemplary computing system810and one or more additional devices. For example, in certain embodiments communication interface822may facilitate communication between computing system810and a private or public network including additional computing systems. Examples of communication interface822include, without limitation, a wired network interface (such as a network interface card), a wireless network interface (such as a wireless network interface card), a modem, and any other suitable interface. In at least one embodiment, communication interface822may provide a direct connection to a remote server via a direct link to a network, such as the Internet. Communication interface822may also indirectly provide such a connection through, for example, a local area network (such as an Ethernet network), a personal area network, a telephone or cable network, a cellular telephone connection, a satellite data connection, or any other suitable connection.

In certain embodiments, communication interface822may also represent a host adapter configured to facilitate communication between computing system810and one or more additional network or storage devices via an external bus or communications channel. Examples of host adapters include, without limitation, SCSI host adapters, USB host adapters, IEEE 1394 host adapters, SATA and eSATA host adapters, ATA and PATA host adapters, Fibre Channel interface adapters, Ethernet adapters, or the like. Communication interface822may also allow computing system810to engage in distributed or remote computing. For example, communication interface822may receive instructions from a remote device or send instructions to a remote device for execution. In certain embodiments, communication interface822may perform and/or be a means for performing, either alone or in combination with other elements, one or more of the identifying, selecting, creating, analyzing, including, querying, searching, marking, adding, and/or removing steps disclosed herein. Communication interface822may also be used to perform and/or be a means for performing other steps and features set forth in the instant disclosure.

As illustrated inFIG. 8, computing system810may also include at least one display device824coupled to communication infrastructure812via a display adapter826. Display device824generally represents any type or form of device capable of visually displaying information forwarded by display adapter826. Similarly, display adapter826generally represents any type or form of device configured to forward graphics, text, and other data from communication infrastructure812(or from a frame buffer, as known in the art) for display on display device824.

As illustrated inFIG. 8, exemplary computing system810may also include at least one input device828coupled to communication infrastructure812via an input interface830. Input device828generally represents any type or form of input device capable of providing input, either computer or human generated, to exemplary computing system810. Examples of input device828include, without limitation, a keyboard, a pointing device, a speech recognition device, or any other input device. In at least one embodiment, input device828may perform and/or be a means for performing, either alone or in combination with other elements, one or more of the identifying, selecting, creating, analyzing, including, querying, searching, marking, adding, and/or removing steps disclosed herein. Input device828may also be used to perform and/or be a means for performing other steps and features set forth in the instant disclosure.

As illustrated inFIG. 8, exemplary computing system810may also include a primary storage device832and a backup storage device833coupled to communication infrastructure812via a storage interface834. Storage devices832and833generally represent any type or form of storage device or medium capable of storing data and/or other computer-readable instructions. For example, storage devices832and833may be a magnetic disk drive (e.g., a so-called hard drive), a floppy disk drive, a magnetic tape drive, an optical disk drive, a flash drive, or the like. Storage interface834generally represents any type or form of interface or device for transferring data between storage devices832and833and other components of computing system810. In one example, data objects222fromFIG. 2may be stored in primary storage device832.

In certain embodiments, storage devices832and833may be configured to read from and/or write to a removable storage unit configured to store computer software, data, or other computer-readable information. Examples of suitable removable storage units include, without limitation, a floppy disk, a magnetic tape, an optical disk, a flash memory device, or the like. Storage devices832and833may also include other similar structures or devices for allowing computer software, data, or other computer-readable instructions to be loaded into computing system810. For example, storage devices832and833may be configured to read and write software, data, or other computer-readable information. Storage devices832and833may also be a part of computing system810or may be a separate device accessed through other interface systems.

In certain embodiments, storage devices832and833may be used, for example, to perform and/or be a means for performing, either alone or in combination with other elements, one or more of the identifying, selecting, creating, analyzing, including, querying, searching, marking, adding, and/or removing steps disclosed herein. Storage devices832and833may also be used to perform and/or be a means for performing other steps and features set forth in the instant disclosure.

The computer-readable medium containing the computer program may be loaded into computing system810. All or a portion of the computer program stored on the computer-readable medium may then be stored in system memory816and/or various portions of storage devices832and833. When executed by processor814, a computer program loaded into computing system810may cause processor814to perform and/or be a means for performing the functions of one or more of the exemplary embodiments described and/or illustrated herein. Additionally or alternatively, one or more of the exemplary embodiments described and/or illustrated herein may be implemented in firmware and/or hardware. For example, computing system810may be configured as an application specific integrated circuit (ASIC) adapted to implement one or more of the exemplary embodiments disclosed herein.

FIG. 9is a block diagram of an exemplary network architecture900in which client systems910,920, and930and servers940and945may be coupled to a network950. Client systems910,920, and930generally represent any type or form of computing device or system, such as exemplary computing system810inFIG. 8. In one example, client system910may include system100fromFIG. 1.

Similarly, servers940and945generally represent computing devices or systems, such as application servers or database servers, configured to provide various database services and/or run certain software applications. Network950generally represents any telecommunication or computer network including, for example, an intranet, a wide area network (WAN), a local area network (LAN), a personal area network (PAN), or the Internet.

As illustrated inFIG. 9, one or more storage devices960(1)-(N) may be directly attached to server940. Similarly, one or more storage devices970(1)-(N) may be directly attached to server945. Storage devices960(1)-(N) and storage devices970(1)-(N) generally represent any type or form of storage device or medium capable of storing data and/or other computer-readable instructions. In certain embodiments, storage devices960(1)-(N) and storage devices970(1)-(N) may represent network-attached storage (NAS) devices configured to communicate with servers940and945using various protocols, such as NFS, SMB, or CIFS.

Servers940and945may also be connected to a storage area network (SAN) fabric980. SAN fabric980generally represents any type or form of computer network or architecture capable of facilitating communication between a plurality of storage devices. SAN fabric980may facilitate communication between servers940and945and a plurality of storage devices990(1)-(N) and/or an intelligent storage array995. SAN fabric980may also facilitate, via network950and servers940and945, communication between client systems910,920, and930and storage devices990(1)-(N) and/or intelligent storage array995in such a manner that devices990(1)-(N) and array995appear as locally attached devices to client systems910,920, and930. As with storage devices960(1)-(N) and storage devices970(1)-(N), storage devices990(1)-(N) and intelligent storage array995generally represent any type or form of storage device or medium capable of storing data and/or other computer-readable instructions.

In certain embodiments, and with reference to exemplary computing system810ofFIG. 8, a communication interface, such as communication interface822inFIG. 8, may be used to provide connectivity between each client system910,920, and930and network950. Client systems910,920, and930may be able to access information on server940or945using, for example, a web browser or other client software. Such software may allow client systems910,920, and930to access data hosted by server940, server945, storage devices960(1)-(N), storage devices970(1)-(N), storage devices990(1)-(N), or intelligent storage array995. AlthoughFIG. 9depicts the use of a network (such as the Internet) for exchanging data, the embodiments described and/or illustrated herein are not limited to the Internet or any particular network-based environment.

In at least one embodiment, all or a portion of one or more of the exemplary embodiments disclosed herein may be encoded as a computer program and loaded onto and executed by server940, server945, storage devices960(1)-(N), storage devices970(1)-(N), storage devices990(1)-(N), intelligent storage array995, or any combination thereof. All or a portion of one or more of the exemplary embodiments disclosed herein may also be encoded as a computer program, stored in server940, run by server945, and distributed to client systems910,920, and930over network950. Accordingly, network architecture900may perform and/or be a means for performing, either alone or in combination with other elements, one or more of the identifying, selecting, creating, analyzing, including, querying, searching, marking, adding, and/or removing steps disclosed herein. Network architecture900may also be used to perform and/or be a means for performing other steps and features set forth in the instant disclosure.

As detailed above, computing system810and/or one or more components of network architecture900may perform and/or be a means for performing, either alone or in combination with other elements, one or more steps of an exemplary method for removing unreferenced data segments from deduplicated data systems.

In addition, one or more of the modules described herein may transform data, physical devices, and/or representations of physical devices from one form to another. For example, one or more of the modules described herein may transform a deduplicated data system into an efficient deduplicated data system by reducing the amount of computing resources necessary to remove unreferenced data segments from the deduplicated data system. In another example, one or more of the modules described herein may transform a deduplicated data system by removing unreferenced data segments from the deduplicated data system.