Systems and methods for repairing corrupted data segments

The disclosed computer-implemented method for repairing corrupted data segments may include (1) detecting a corrupted data segment in a backup stored in a data storage system, (2) identifying at least one additional backup stored in the data storage system that exceeds a predetermined threshold for probability of comprising an uncorrupted version of the corrupted data segment, (3) matching at least a portion of a data segment in the additional backup with at least a portion of a data segment adjacent to the corrupted data segment in the backup, (4) locating, at least in part by examining data adjacent to the matched data segment in the additional backup, the uncorrupted version of the corrupted data segment, and (5) repairing the corrupted data segment in the backup by using the uncorrupted version of the corrupted data segment located in the additional backup. Various other methods, systems, and computer-readable media are also disclosed.

BACKGROUND

In an era of constant connectivity, an inability to efficiently create and maintain backups of important data can be a severe liability. Computing devices are prone to a wide variety of both temporary and fatal errors, and even temporary losses of data or services may be devastating to enterprises. The ability to maintain accurate and stable backups is crucial to enterprises that wish to maintain consistent services. While it is also important to have the ability to quickly create and copy backups and to quickly retrieve data from backups, none of that matters if the data within the backup is corrupted and unusable. Many backup systems reduce the problem of corrupted data by keeping multiple copies of each stored item of data. However, one corrupted copy of backup data can still cause trouble if that copy is not quickly repaired.

Many traditional backup systems store data in segments. These traditional backup systems may repair corrupted segments by searching for uncorrupted copies of the corrupted segment and replacing the corrupted data with intact data from the uncorrupted copy. However, many traditional systems may rely on fixed-width deduplication algorithms that have difficulty locating copies of segments that have become offset from their original position and no longer perfectly match other copies of the same segment. Accordingly, the instant disclosure identifies and addresses a need for additional and improved systems and methods for repairing corrupted data segments.

SUMMARY

As will be described in greater detail below, the instant disclosure describes various systems and methods for repairing corrupted data segments by using data from adjacent segments to locate corresponding uncorrupted data segments in other backups, even when the corrupted data segment is offset and may not be fixable using fixed-width matching algorithms.

In one example, a computer-implemented method for repairing corrupted data segments may include (1) detecting a corrupted data segment in a backup stored in a data storage system, (2) identifying at least one additional backup stored in the data storage system that exceeds a predetermined threshold for probability of including an uncorrupted version of the corrupted data segment, (3) matching at least a portion of a data segment in the additional backup with at least a portion of a data segment adjacent to the corrupted data segment in the backup, (4) locating, at least in part by examining data adjacent to the matched data segment in the additional backup, the uncorrupted version of the corrupted data segment, and (5) repairing the corrupted data segment in the backup by using the uncorrupted version of the corrupted data segment located in the additional backup.

In some examples, detecting the corrupted data segment may include detecting an offset corrupted data segment. In these examples, an uncorrupted version of the offset corrupted segment may not be able to be located using a fixed-length deduplication algorithm.

In some examples, identifying at least one additional backup may include determining a container identifier of a container that includes the corrupted data segment and determining that at least one additional backup includes a container with the container identifier. Additionally or alternatively, identifying at least one additional backup may include (1) identifying a group of additional backups that exceeds the predetermined threshold for probability of including the uncorrupted version of the corrupted data segment, (2) ranking each backup within the additional backups according to at least one of stability and size, and (3) selecting the highest-ranked backup within the additional backups.

In some examples, matching the portion of the data segment in the additional backup with the portion of the data segment adjacent to the corrupted data segment in the backup may include creating a partial fingerprint of the data segment adjacent to the corrupted data segment in the backup and matching the partial fingerprint to a partial fingerprint of the data segment in the additional backup. Additionally or alternatively, locating the uncorrupted version of the corrupted data segment may include identifying a fingerprint of the uncorrupted version of the corrupted data segment stored in an index and attempting to match at least one portion of the data adjacent to the matched data segment in the additional backup with the fingerprint by examining each portion of the data in turn to determine whether the portion of the data matches the fingerprint. In one embodiment, the data segment adjacent to the corrupted data segment in the backup may be a data segment that was stored in the backup prior to the corrupted data segment being stored in the backup.

In one embodiment, a system for implementing the above-described method may include (1) a detection module, stored in memory, that detects a corrupted data segment in a backup stored in a data storage system, (2) an identification module, stored in memory, that identifies at least one additional backup stored in the data storage system that exceeds a predetermined threshold for probability of including an uncorrupted version of the corrupted data segment, (3) a matching module, stored in memory, that matches at least a portion of a data segment in the additional backup with at least a portion of a data segment adjacent to the corrupted data segment in the backup, (4) a location module, stored in memory, that locates, at least in part by examining data adjacent to the matched data segment in the additional backup, the uncorrupted version of the corrupted data segment, (5) a repair module, stored in memory, that repairs the corrupted data segment in the backup by using the uncorrupted version of the corrupted data segment located in the additional backup, and (6) at least one physical processor configured to execute the detection module, the identification module, the matching module, the location module, and the repair module.

In some examples, the above-described method may be encoded as computer-readable instructions on a non-transitory computer-readable medium. For example, a computer-readable medium may include one or more computer-executable instructions that, when executed by at least one processor of a computing device, may cause the computing device to (1) detect a corrupted data segment in a backup stored in a data storage system, (2) identify at least one additional backup stored in the data storage system that exceeds a predetermined threshold for probability of including an uncorrupted version of the corrupted data segment, (3) match at least a portion of a data segment in the additional backup with at least a portion of a data segment adjacent to the corrupted data segment in the backup, (4) locate, at least in part by examining data adjacent to the matched data segment in the additional backup, the uncorrupted version of the corrupted data segment, and (5) repair the corrupted data segment in the backup by using the uncorrupted version of the corrupted data segment located in the additional backup.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

The present disclosure is generally directed to systems and methods for repairing corrupted data segments. As will be explained in greater detail below, by locating an uncorrupted version of a corrupted data segment by matching data from adjacent segments, the systems described herein may repair corrupted data segments that cannot be repaired using fixed-length deduplication algorithms.

The following will provide, with reference toFIGS. 1, 2, and 5, detailed descriptions of exemplary systems for repairing corrupted data segments. Detailed descriptions of corresponding computer-implemented methods will also be provided in connection withFIG. 3. Detailed descriptions of a set of exemplary data segments will be provided in connection withFIG. 4. 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. 6 and 7, respectively.

FIG. 1is a block diagram of exemplary system100for repairing corrupted data segments. 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 a detection module104that detects a corrupted data segment in a backup stored in a data storage system. Exemplary system100may additionally include an identification module106that identifies at least one additional backup stored in the data storage system that exceeds a predetermined threshold for probability of including an uncorrupted version of the corrupted data segment. Exemplary system100may also include a matching module108that matches at least a portion of a data segment in the additional backup with at least a portion of a data segment adjacent to the corrupted data segment in the backup. Exemplary system100may additionally include a location module110that locates, at least in part by examining data adjacent to the matched data segment in the additional backup, the uncorrupted version of the corrupted data segment. Exemplary system100may also include a repair module112that repairs the corrupted data segment in the backup by using the uncorrupted version of the corrupted data segment located in the additional backup. Although illustrated as separate elements, one or more of modules102inFIG. 1may represent portions of a single module or application.

Exemplary system100inFIG. 1may be implemented in a variety of ways. For example, all or a portion of exemplary system100may represent portions of exemplary system200inFIG. 2. As shown inFIG. 2, system200may include a computing device202. In one example, computing device202may be programmed with one or more of modules102.

In one embodiment, one or more of modules102fromFIG. 1may, when executed by at least one processor of computing device202, enable computing device202to repair corrupted data segments. For example, and as will be described in greater detail below, detection module104may detect a corrupted data segment212in a backup210stored in a data storage system208. Identification module106may identify at least one backup216stored in data storage system208that exceeds a predetermined threshold for probability of including a data segment218that is an uncorrupted version of corrupted data segment212. Once backup216has been identified, matching module108may match at least a portion of a data segment in backup216with at least a portion of data segment214in backup210. Next, location module110may locate, at least in part by examining data220adjacent to the matched data segment in backup216, data segment218. Finally, repair module112may repair corrupted data segment212in backup210by using data segment218located in backup210216.

Computing device202generally represents any type or form of computing device capable of reading computer-executable instructions. Examples of computing device202include, without limitation, laptops, tablets, desktops, servers, cellular phones, Personal Digital Assistants (PDAs), multimedia players, embedded systems, wearable devices (e.g., smart watches, smart glasses, etc.), gaming consoles, combinations of one or more of the same, exemplary computing system610inFIG. 6, or any other suitable computing device.

FIG. 3is a flow diagram of an exemplary computer-implemented method300for repairing corrupted data segments. 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, computing system610inFIG. 6, and/or portions of exemplary network architecture700inFIG. 7.

As illustrated inFIG. 3, at step302, one or more of the systems described herein may detect a corrupted data segment in a backup stored in a data storage system. For example, detection module104may, as part of computing device202inFIG. 2, detect corrupted data segment212in backup210stored in data storage system208.

The term “data segment,” as used herein, generally refers to any defined amount of data stored in a storage system. In some embodiments, a data segment may include a portion of a file and/or one or more variables. In some embodiments, a large number of data segments may be stored in a backup image.

The term “corrupted data segment,” as used herein, generally refers to any data segment that includes any sort of error. In some examples, a corrupted data segment may be unreadable. In other examples, a corrupted data segment may be readable but may contain incorrect data.

The term “backup,” as used herein, generally refers to any copy of an object, file, folder, operating system, application, and/or other computing object that is stored in a storage system. In some embodiments, the data in a backup may be divided into a number of data segments.

The term “data storage system” or “storage system,” as used herein, generally refers to any system that stores data. In some embodiments, a data storage system may store backups. In one embodiment, a data storage system may include a deduplication system. In some embodiments, a data storage system may include multiple backup copies of the same data.

Detection module104may detect the corrupted data segment in a variety of ways. For example, detection module104may detect the corrupted data segment directly. In another embodiment, detection module104may receive information from another application indicating that the data segment is corrupted. In some embodiments, detection module104may routinely check data in the storage system for corruption.

In some examples, detection module104may detect an offset corrupted data segment. In these examples, an uncorrupted version of the offset corrupted segment may not be able to be located using a fixed-length deduplication algorithm. An offset data segment may not have the same fingerprint as a non-offset version of the same data segment. As illustrated inFIG. 4, a backup400may include data segments402,404,406, and/or408with fingerprints403,405,407, and/or409, respectively. These data segments may not be offset. Meanwhile, a backup410may include data segments412,414,416, and/or418that represent the same data as data segments402,404,406, and/or408, respectively. However, while data segment412may share a fingerprint with data segment402, offset data segments414,416, and/or418may have different fingerprints than data segments404,406, and/or408and may instead have fingerprints415,417, and/or419, respectively. In this example, if data segment418were to become corrupted, a fixed-length deduplication algorithm may not correctly locate data segment408as the uncorrupted version of the same segment due to the change in fingerprint caused by the offset.

Returning toFIG. 3, at step304, one or more of the systems described herein may identify at least one additional backup stored in the data storage system that exceeds a predetermined threshold for probability of including an uncorrupted version of the corrupted data segment. For example, identification module106may, as part of computing device202inFIG. 2, identify backup216stored in data storage system208that exceeds a predetermined threshold for probability of including data segment218.

Identification module106may identify the additional back up in a variety of ways. In some examples, identification module106may identify the additional backup by determining a container identifier of a container that includes the corrupted data segment and determining that the additional backup includes a container with the container identifier. In one example, identification module106may use a container map to identify every backup that includes a container with the same identifier as the container that includes the corrupted data segment.

In some embodiments, identification module106may identify at least one additional backup by identifying several additional backups that each exceed the predetermined threshold for probability of including the uncorrupted version of the corrupted data segment, ranking each backup according to stability and/or size, and selecting the highest-ranked backup. For example, if identification module106identifies three backups that may contain the corrupted data segment and two of the backups are very large while one is comparatively small, identification module106may select the smallest backup in order to speed up processing time in subsequent steps. In another example, identification module106may identify several backups and may select the least frequently modified backup in order to increases the chances of finding uncorrupted data.

Identification module106may determine the predetermined threshold for probability in a variety of ways. In one embodiment, identification module106may determine that any backup listed in a container identifier map as including a container with an identifier that matches the container identifier for the corrupted data segment has a high probability of including the corrupted data segment. In another embodiment, identification module106may determine that a backup that is identified as storing data about the same object, file, and/or application as the backup with the corrupted data segment has a high probability of including the corrupted data segment.

At step306, one or more of the systems described herein may match at least a portion of a data segment in the additional backup with at least a portion of a data segment adjacent to the corrupted data segment in the backup. For example, matching module108may, as part of computing device202inFIG. 2, match at least a portion of a data segment in backup216with at least a portion of data segment214in backup210.

Matching module108may match the data within the data segments in a variety of ways. For example, matching module108may match the portion of the data segment in the additional backup with the portion of the data segment adjacent to the corrupted data segment in the backup by creating a partial fingerprint of the data segment adjacent to the corrupted data segment in the backup and matching the partial fingerprint to a partial fingerprint of the data segment in the additional backup. The term “partial fingerprint,” as used herein, typically refers to any representation of a portion of a data segment. For example, matching module108may hash a portion of the data segment adjacent to the corrupted data segment and compare that hash to a hash of a portion of a data segment in the additional backup.

In some embodiments, matching module108may compare data in the additional backup starting with data within the container with the same container identifier as the container that contains the corrupted data segment. Additionally or alternatively, matching module108may use an index and/or map that includes information about data segments to determine a likely spot to start attempting to match data.

In one embodiment, the data segment adjacent to the corrupted data segment in the backup may be a data segment that was stored in the backup prior to the corrupted data segment being stored in the backup. In some examples, the data segment adjacent to the corrupted data segment may have been stored immediately prior to the corrupted data segment being stored. By using an older data segment, the systems described herein may reduce chances that the adjacent data segment has also been corrupted.

At step308, one or more of the systems described herein may locate, at least in part by examining data adjacent to the matched data segment in the additional backup, the uncorrupted version of the corrupted data segment. For example, location module110may, as part of computing device202inFIG. 2, locate, at least in part by examining data220adjacent to the matched data segment in backup216, data segment218.

Location module110may locate the uncorrupted version of the corrupted data segment in a variety of ways. In some embodiments, location module110may locate the uncorrupted version of the corrupted data segment by identifying a fingerprint of the uncorrupted version of the corrupted data segment stored in an index and attempting to match at least one portion of the data adjacent to the matched data segment in the additional backup with the fingerprint by examining each portion of the data in turn to determine whether the portion of the data matches the fingerprint. In one embodiment, location module110may start with the data immediately adjacent to the matched segment and work outwards from there.

In some embodiments, location module110may use fast data anchoring, a fast digest algorithm, convergent eigenvalues and/or segment metadata to locate the uncorrupted version of the corrupted segment. In one embodiment, location module110may execute in a separate sandbox from the deduplication engine in order to improve performance. In some embodiments, location module110may only scan data up to a predetermined distance away from the matched adjacent segment before returning a result that no matching data was found.

At step310, one or more of the systems described herein may repair the corrupted data segment in the backup by using the uncorrupted version of the corrupted data segment located in the additional backup. For example, repair module112may, as part of computing device202inFIG. 2, repair corrupted data segment212in backup210by using data segment218located in backup216.

Repair module112may repair the corrupted data segment in a variety of ways. For example, repair module112may replace the entire corrupted data segment with the uncorrupted version from the additional backup. In other examples, repair module112may replace a portion of the data in the corrupted data segment with data from the uncorrupted version of the data segment.

In some embodiments, the systems described herein may be located on different computing systems and/or servers. For example, as illustrated inFIG. 5, a computing device502may host modules102and/or may communicate with servers506and/or508via a network504. In this example, server506may host a backup510that includes a corrupted data segment512and/or server508may host a backup516that includes a data segment518that is the uncorrupted version of corrupted data segment512. In some embodiments, network504may represent a local area network and computing device502, server506, and/or server508may all be located in the same physical location. In other embodiments, network504may represent the Internet and computing device502, server506, and/or server508may be located remotely (i.e., on the cloud).

As described in connection with method300above, the systems and methods described herein may fetch healthy duplicate data for corrupt data segment repair across segment boundaries in a deduplication system. Upon detecting a corrupt data segment, the systems described herein may determine the container identifier of the container that contains the segment and then search for other backups that include containers with that same identifier. After locating one or more backups that include containers with the appropriate identifier, the systems described herein may rank the backups according to stability and/or size to determine which backup to check first. The systems described herein may then attempt to match a partial fingerprint of the segment immediately prior to the corrupted segment with a partial fingerprint of a segment in the found backup to determine where, if anywhere, in the found backup the segment that corresponds to the corrupted segment is located. If the systems described herein do not find a match for the partial fingerprint, the systems described herein may move to the next backup. When a match is found, the systems described herein may then search nearby data for a segment that matches a stored representation in an index for the corrupted data segment. After locating an uncorrupted version of the corrupted data segment, the systems described herein may then repair the corrupted data segment using the uncorrupted data. By searching for replacement data segments by using partial fingerprints of adjacent segments rather than fixed-length deduplication algorithms, the systems and methods described herein may efficiently repair corrupted data segments even in cases where some segments have become offset from their original position.

As detailed above, computing system610and/or one or more components of network architecture700may 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 repairing corrupted data segments.

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 recited herein may receive data to be transformed, transform the data by creating a fingerprint, output a result of the transformation to a matching technique, use the result of the transformation to locate similar data, and store the result of the transformation to a variable and/or file. Additionally or alternatively, one or more of the modules recited herein may transform a processor, volatile memory, non-volatile memory, and/or any other portion of a physical computing device from one form to another by executing on the computing device, storing data on the computing device, and/or otherwise interacting with the computing device.