Change tracking using redundancy in logical time

Tracking changes amongst unit portions (e.g., blocks or files) of a storage system. A logical time identifier is associated with each unit portion and is included within a logical time identifier structure. When writing to a particular write portion, the mechanism updates the appropriate logical time identifiers, calculates redundancy data of a group of one or more logical time identifiers associated with the unit portion(s) of the write portion. Furthermore, the write portion of the storage system is written. In addition, the corresponding redundancy data for that write portion is written to the logical time identifier structure. Later, for a given write portion, the redundancy data is verified to be consistent or inconsistent with the group of one or more logical time identifiers associated with the write portion. If the redundancy data is not consistent, then a current logical time identifier is assigned to each of the logical time identifiers.

BACKGROUND

Computing systems and associated networks have revolutionized the way human beings work, play, and communicate, heralding in what is now termed the “information age”. Data management is thus an important field in modern times. One aspect of data management is change tracking. For instance, it is often helpful to be able to distinguish what portions of data have changed between two instances in time.

As an example, when backing up a storage system, a copy of the storage system is written to a backup site. The next time the storage system is backed up, rather than copy again the entire storage system, only a changed subset of the storage system is backed up. Accordingly, to perform this incremental backup, determining which portions of the storage system have changed is a prerequisite. Furthermore, when recovering a storage system to a particular logical time (e.g., as during a recovery), change tracking allows the recovery system to determine which portions of the data are consistent with the state of the storage system at that particular logical time.

BRIEF SUMMARY

At least some embodiments described herein relate to tracking changes amongst unit portions of a storage system. As an example, the unit portions might be files in a file system, or blocks in block-based storage system. For each at least some of the unit portions of the storage system, a logical time identifier is associated with unit portion and is included within a logical time identifier structure.

When writing to a particular write portion that includes one or more unit portions of the storage system, the logical time identifier is updated for any changed unit portions within the write portion. Furthermore, once the appropriate logical time identifier(s) has changed, the mechanism calculates redundancy data, such as a checksum, of a group of one or more logical time identifiers associated with the one or more portions of the write portion. The write portion of the storage system is written. In addition, the corresponding redundancy data for the group of logical time identifiers associated with that write portion is written to the logical time identifier structure.

Later, for a given write portion, the redundancy data is verified to be consistent or inconsistent with the group of one or more logical time identifiers associated with the write portion. If the redundancy data is not consistent, then a current logical time identifier is assigned to each of the logical time identifiers. Accordingly, inconsistent write portions are treated as recently written to. During incremental backup, the logical time identifiers are used to determine which unit portions have changed, and thus to determine which unit portions need to be backed up. Since inconsistent redundancy data for a write portion results in the logical time identifiers for the entire write portion receiving the current logical time, this causes the appearance to the backup system that all unit portions of that write portion have been newly written to. Accordingly, the backup system causes the entire write portion to be backed up, even though one or more of its unit portions might not have changed. While this might perhaps result in more backup data being transferred than absolutely necessary in the rare case that the redundancy data loses consistency, it protects against data inconsistency when such cases occur.

This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

DETAILED DESCRIPTION

At least some embodiments described herein relate to tracking changes amongst unit portions of a storage system. As an example, the unit portions might be files in a file system, or blocks in block-based storage system. For each at least some of the unit portions of the storage system, a logical time identifier is associated with unit portion and is included within a logical time identifier structure.

When writing to a particular write portion that includes one or more unit portions of the storage system, the logical time identifier is updated for any changed unit portions within the write portion. Furthermore, once the appropriate logical time identifier(s) has changed, the mechanism calculates redundancy data, such as a checksum, of a group of one or more logical time identifiers associated with the one or more portions of the write portion. The write portion of the storage system is written. In addition, the corresponding redundancy data for the group of logical time identifiers associated with that write portion is written to the logical time identifier structure.

Later, for a given write portion, the redundancy data is verified to be consistent or inconsistent with the group of one or more logical time identifiers associated with the write portion. If the redundancy data is not consistent, then a current logical time identifier is assigned to each of the logical time identifiers. Accordingly, inconsistent write portions are treated as recently written to. During incremental backup, the logical time identifiers are used to determine which unit portions have changed, and thus to determine which unit portions need to be backed up. Since inconsistent redundancy data for a write portion results in the logical time identifiers for the entire write portion receiving the current logical time, this causes the appearance to the backup system that all unit portions of the write portion have been newly written to. Accordingly, the backup system causes the entire write portion to be backed up, even though one or more of the unit portions might not have changed. While this might perhaps result in more backup data being transferred than absolutely necessary in the rare case that the redundancy data loses consistency, it protects against data inconsistency when such cases occur.

Some introductory discussion of a computing system will be described with respect toFIG. 1. Then, the structure and operation of embodiments described herein will be presented with respect to subsequent figures.

Computing systems are now increasingly taking a wide variety of forms. Computing systems may, for example, be handheld devices, appliances, laptop computers, desktop computers, mainframes, distributed computing systems, datacenters, or even devices that have not conventionally been considered a computing system, such as wearables (e.g., glasses). In this description and in the claims, the term “computing system” is defined broadly as including any device or system (or combination thereof) that includes at least one physical and tangible processor, and a physical and tangible memory capable of having thereon computer-executable instructions that may be executed by a processor. The memory may take any form and may depend on the nature and form of the computing system. A computing system may be distributed over a network environment and may include multiple constituent computing systems.

As illustrated inFIG. 1, in its most basic configuration, a computing system100typically includes at least one hardware processing unit102and memory104. The memory104may be physical system memory, which may be volatile, non-volatile, or some combination of the two. The term “memory” may also be used herein to refer to non-volatile mass storage such as physical storage media. If the computing system is distributed, the processing, memory and/or storage capability may be distributed as well. As used herein, the term “executable module” or “executable component” can refer to software objects, routines, or methods that may be executed on the computing system. The different components, modules, engines, and services described herein may be implemented as objects or processes that execute on the computing system (e.g., as separate threads).

In the description that follows, embodiments are described with reference to acts that are performed by one or more computing systems. If such acts are implemented in software, one or more processors (of the associated computing system that performs the act) direct the operation of the computing system in response to having executed computer-executable instructions. For example, such computer-executable instructions may be embodied on one or more computer-readable media that form a computer program product. An example of such an operation involves the manipulation of data. The computer-executable instructions (and the manipulated data) may be stored in the memory104of the computing system100. Computing system100may also contain communication channels108that allow the computing system100to communicate with other computing systems over, for example, network110.

Computer-executable instructions comprise, for example, instructions and data which, when executed at a processor, cause a general purpose computing system, special purpose computing system, or special purpose processing device to perform a certain function or group of functions. The computer executable instructions may be, for example, binaries or even instructions that undergo some translation (such as compilation) before direct execution by the processors, such as intermediate format instructions such as assembly language, or even source code. Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the described features or acts described above. Rather, the described features and acts are disclosed as example forms of implementing the claims.

FIG. 2illustrates a timeline200of operation in accordance with the principles described herein. First, is a provisioning phase210in which a computing system prepares for operation to keep track of changes in a storage system by setting up a logical time identifier structure. Second, is an operation phase220in which the computing system engages in normal operation and as such performs write operations221to the storage system and equivalent writes to the logical time identifier structure, and then later verifies222consistency of the write operations using the logical time identifier structure in accordance with the principles described herein. Finally, there is a potential backup phase230in which the logical time identifier structure is used to backup the storage system to a consistent state.

More specifically,FIG. 3illustrates a flowchart of a method300for keeping track of changes amongst portions of a storage system. In the provisioning phase210, a logical time identifier is associated with each unit portion in a logical time identifier structure (act310).FIG. 4illustrates an example storage system400that includes a logical time identifier structure. The example ofFIG. 4will be described prior to returning to the flowchart of the method300ofFIG. 3.

As an example,FIG. 4illustrates an example storage system400that includes data storage400A and a logical time identifier structure400B. The data storage400A includes unit portions401A through409A. In one embodiment, the storage system400A is a file system in which each unit portion401A through409A is a file. However, the storage system400A might also be a block-based system in which each unit portion401A through409A is a block. Of course, there may be many more unit portions in a typical storage system, but the example ofFIG. 4is kept simple for purposes of clarity.

The storage system400A also includes write portions411A through413A. In accordance with the broadest aspect described herein, the write portions may include one or more unit portions, and represent how the unit portions may be written into the storage system. For instance, if the storage system400A is a file system, then typically, one file is written at a time. Accordingly, the write portions might contain just one unit portion (i.e., one file) each. However, if the storage system400A is a block-based storage system, then typically the blocks are written one page at a time, with one page encompassing multiple blocks. In the illustrated example, the write portions411A through413A are each represented as encompassing three unit portions each. This is again for purposes of simplicity and clarity in describing the example. In a typical storage system, there may be millions or billions of unit portions and write portions, and each write portion can potentially encompass different numbers of unit portions.

The logical time identifier structure400B includes logical time identifiers401B through409B associated with each of the unit portions401A through409A, respectively.FIG. 5A through 5Gillustrates progressive states of the logical time identifier structure400B as the state will be in a particular example described hereinafter. In the example ofFIGS. 5A through 5G, the logical time identifier structure including a linear array of entries, with each entry being a logical time identifier for an associated unit portion of the storage system.FIGS. 6A through 6Fillustrates progressive states of the logical time identifier structure400B, in which a tree structure is used to track redundancy data.FIGS. 5A through 5Dcorrespond toFIGS. 6A through 6D, respectively.FIGS. 5E and 5Fcorrespond toFIG. 6E.FIGS. 5F and 5Gcorrespond toFIGS. 6E and 6F, respectively. Accordingly, the examples ofFIGS. 5A through 5G, as well asFIGS. 6A through 6F, will be referred to frequently in describing the scenario below.

In the particular example ofFIGS. 5A through 5GandFIGS. 6A through 6F, the logical time identifiers are sequence numbers, and logical time is represented by a sequence number that increments by one each time logical time advances. For instance, in state500A ofFIG. 5A, and in state600A ofFIG. 6A, the logical time identifiers401B through409B are each zero′ed out. In some cases, the logical time identifiers might be associated with a real time, such that a real time may be entered, and the corresponding logical time identifier may be retrieved.

Referring again toFIG. 4, the group of logical time identifiers for each of the write portions411A through413A has associated redundancy data411B through413B, respectively. The redundancy data411B through413B may be used to confirm correctness of the logical time identifiers within the corresponding write portions411A through413A, respectively. For instance, the write portion411A is associated with unit portions401A through403A; and the unit portions401A through403A have associated logical time identifiers401B through403B. Accordingly, the redundancy data411B represents redundancy data (e.g., a checksum) that may be used to verify accuracy of the logical time identifiers401B through403B. Also, the write portion412A is associated with unit portions404A through406A; and the unit portions404A through406A have associated logical time identifiers404B through406B. Accordingly, the redundancy data412B represents redundancy data (e.g., a checksum) that may be used to verify accuracy of the logical time identifiers404B through406B. Finally, the write portion413A is associated with unit portions407A through409A; and the unit portions407A through409A have associated logical time identifiers407B through409B. Accordingly, the redundancy data413B represents redundancy data (e.g., a checksum) that may be used to verify accuracy of the logical time identifiers407B through409B.

With the logical time identifiers401A through409A being zero'ed out inFIG. 5A, the redundancy data411B,411B and411C each represent the redundancy data for three zero's. In the nomenclature of the illustratedFIGS. 5A through 5G, redundancy data for a sequence of numbers is symbolized by having the sequence of numbers illustrated with a jagged underline. For instance, inFIG. 5A, the redundancy data411B is represented as having value 000.

FIGS. 6A through 6Fillustrate various stages of another embodiment of the logical time identifier structure ofFIG. 4following along the same particular scenario as was described with respect toFIGS. 5A through 5G. However, in this second embodiment, the logical time identifier structure may take the form of a tree structure.

In this tree structure, if a write portion does not have an associated group of logical time identifiers, then the logical time identifiers are assumed to be a default value represented by a root node in the tree. If any of the group of logical time identifier structures for a write portion is different than the default value represented at the root node, then that group of logical time identifier structures will have its own child node. If the group of logical time identifiers are the same for a given write portion, then the child node will simply hold that value. If each of the group of logical time identifiers are not the same for the write portion, then the child node will contain the redundancy data for the series of logical time identifiers.

For instance, referring to the example ofFIG. 6A, none of the logical time identifiers are different than a default value of zero. Accordingly, since the values of the logical time identifiers401B through409B are each 0, there is but a single root node610that represents the value 0.

Moving onto the writing operation221of the phase220, when writing to a particular write portion that includes unit portion(s) of the storage system, the system updates the logical time identifiers for any of the unit portion(s) of the write portion that have changed (act320), and calculates the redundancy data (e.g., a checksum) associated with a logical time identifier(s) associated with the unit portion(s) of the write portion (act321). The system writes the write portion (act322) and also writes the associated redundancy data (act323). In some embodiments, the redundancy data is written (act323) in parallel with the updating of the logical time identifiers (act320). Accordingly, if the redundancy data is later found to be inconsistent with the logical time identifiers (act324), then a power failure has likely occurred, and the logical time identifiers may be treated as corrupt. This is why the logical time identifiers are, in that case, marked with the current logical time as measured by the application using the data.

For instance, referring to the state500B ofFIG. 5B, suppose that a write is made to unit portions402A and403A, and that logical time has advanced to time 1. Accordingly, the logical time identifiers401B through403B of the corresponding unit portions401A through403A for write portion411A change from 000 to 011 (act320). The redundancy data411B is then recalculated (act321) as 011. The system then writes the new write portion411A to the unit portions401A through403A (act322), and also writes the new redundancy data411B now having value 011 (act323). Referring to the state600B ofFIG. 6B, since the write portion411A is no longer accurately represented by the root node610, a leaf node611is created, which contains the redundancy data (e.g., a checksum) for the logical time identifiers401B through403B.

Next, referring to state500C ofFIG. 5C, suppose that a write is made to unit portions403A and404A, and that logical time has advanced to time 2. Accordingly, the logical time identifiers401B through403B of the corresponding unit portions401A through403A for write portion411A change from 011 to 012 (act320). Furthermore, the logical time identifiers404B through406B of the corresponding unit portions404A through406A for write portion412B change from 000 to 200 (also act320). The redundancy data411B is then recalculated (act321) as 012. In addition, the redundancy data412B is then recalculated (also act321) as 200. The system then writes the new write portion411A to the unit portions401A through403A (act322), the new write portion412A of the unit portions404A through406A (also act322), the new redundancy data411B now having value 012 (act323), and the new redundancy data412B now having value 200 (also act323). Referring to the state600C ofFIG. 6C, since the write portion412A is no longer accurately represented by the root node610, a leaf node612is created, which contains the redundancy data (e.g., a checksum) for the logical time identifiers404B through404B. Furthermore, the leaf node611has been altered in the same manner as the redundancy data411B.

Next, referring to state500D ofFIG. 5D, suppose that a write is made to unit portions405A and406A, and that logical time has advanced to time 3. Accordingly, the logical time identifiers404B through406B of the corresponding unit portions404A through406A for write portion412A change from 200 to 233 (act320). The redundancy data412B is then recalculated (act321) as 233. The system then writes the new write portion412A to the unit portions404A through406A (act322), and also writes the new redundancy data412B now having value 233 (act323). Similarly, referring to the state600D ofFIG. 6D, the value of the leaf node612also changes accordingly.

Referring back toFIG. 2, during the operational phase220, a verify operation222may be occasionally performed. This verify operation222may be performed in response to certain events, and/or might be periodically performed. As an example, the verify operation222might be performed after a power cycle has been detected to occur in the system.

During a verify operation222, it might be verified after the write operation221that the redundancy data is not consistent with the group of one or more logical time identifiers (act324). If the redundancy data is not consistent, then a write operation221is performed with respect to the current logical time 3 for all of the unit portions in the corresponding write portion.

For instance, referring to state500E ofFIG. 5E, suppose that while still at logical time 3, that the redundancy data412B now has a corrupt value (represented by “***”) that is no longer consistent with the value 233 of the logical time identifiers404B through406B of the unit portions404A through406A associated with the corresponding write portion412A (act324). In that case, as represented in the state ofFIG. 5F, the logical time identifiers404B through406B of the corresponding unit portions404A through406A of the write portion412A are each re-written with current logical time identifier 3 (act325). The new redundancy data412B is then calculated as 333, (act321), and the redundancy data is written (act323). Referring to the state600E ofFIG. 6E, since the logical time identifiers404B through406B of the write portion corresponding to leaf node611are now all of the same (logical time 3), the leaf node612may optionally transform to having a simple value of 3. Alternatively, the leaf node612could have had the redundancy value of 333.

In other words, if the redundancy data (e.g., the checksum) is incorrect, the entire associated write portion is treated as though it has the latest sequence number. The next time the write portion is updated, the current logical time is explicitly stored for each logical time identifier for that write portion. This means that if the page becomes corrupt somehow, when the user requests the set of changes from time t (which is less than the current time), the user will see that everything represented by this part of the logical time identifier structure) has changed, even though only some or even none of the unit portions of this write portion have changed. This is much safer than assuming nothing changed (since it is unknown what changed).

Next, referring to the state500G ofFIG. 5G, suppose that a write is made to unit portions406A and407A, and that logical time has advanced to time 4. Accordingly, the logical time identifiers404B through406B of the corresponding unit portions404A through406A for write portion412A change from333to334(act320). Furthermore, the logical time identifiers407B through409B of the corresponding unit portions407A through409A for write portion413A change from000to400(also act320). The redundancy data412B is then recalculated (act321) as334. In addition, the redundancy data413B is then recalculated (also act321) as400. The system then writes the new write portion412A to the unit portions404A through406A (act322), the new write portion413A of the unit portions407A through409A (also act322), the new redundancy data412B now having value 334 (act323), and the new redundancy data413B now having value 400 (also act323). Referring to the state600F ofFIG. 6F, since the write portion413A is no longer accurately represented by the root node610, a leaf node613is created, which contains the redundancy data (e.g., a checksum) for the logical time identifiers407B through409B. Furthermore, since the value in the leaf node612(of 3) no longer represents all of the logical time identifiers of the write portion412A, the leaf node612is modified to include the redundancy data334.

Referring again toFIG. 4, now suppose that the storage system400needs to be backed up. For instance, inFIG. 2, the timeline200proceeds from normal operation phase220to the backup phase230. The logical time identifiers are used by the backup system to determine what unit portions have changed. For instance, referring toFIGS. 5G and 6F, if the last backup was taken after logical time 0 but before logical time 1, then unit portions402A through407A are to be backed up since their respective logical time identifiers402B through407B are each logical time 1 or later. If the last backup was taken after logical time 1 but before logical time 2, then unit portions403A through407A are to be backed up since their respective logical time identifiers403B through407B are each logical time 2 or later. If the last backup was taken after logical time 2 but before logical time 3, then unit portions404A through407A are to be backed up since their respective logical time identifiers404B through407B are each logical time 3 or later. If the last backup was taken after logical time 3 but before logical time 4, then unit portions406A and407A are to be backed up since their respective logical time identifiers406B and407B are each logical time 4 or later.

Since inconsistent redundancy data for a write portion results in the logical time identifiers for the entire write portion receiving the current logical time, this causes the appearance to the backup system that all unit portions of that write portion have been newly written to. Accordingly, the backup system causes the entire write portion to be backed up, even though one or more of the unit portions might not have changed. While this might perhaps result in more backup data being transferred than absolutely necessary in the rare case that the redundancy data loses consistency, it protects consistency of the actual data when such cases occur

FIG. 7abstractly illustrates an architecture700that includes various processing components that may operate within the storage system to provision, operate, and backup the storage system. In particular, a provisioning component710may be structured and configured to perform the operations described above for the provisioning phase210, a write component721may be structured and configured to perform the write operations221, a verify component722may be structured and configured to perform the verify operations222, and a backup component730may be structured and configured to perform the operations described above for the backup phase230.

Accordingly, the principles described herein provide an efficient mechanism for keeping track of changes between arbitrary versions of a storage system. The present invention may be embodied in other specific forms without departing from its spirit or essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.