CN103415842A - Systems and methods for data management virtualization - Google Patents

Abstract

Systems and methods for data management virtualization are disclosed. The systems have a data management engine for performing data management functions, including at least a snapshot function and a back-up function, and a service level policy engine that controls the scheduling of the data management functions using service level agreements in electronic form. Data objects are organized in a deduplicated content store using an organized arrangement of temporal structures to represent states of data over time. Hash signatures are used to track content segments for performing deduplicated copies from a first deduplicated store to a second deduplicated store. Garbage collection is performed on the deduplicated content store for only content segments that have changed relative to an immediately-prior state of a given data object.

Description

Systems and methods for data management virtualization

Cross References to Related Applications

This application claims priority to the following patent applications: U.S. Patent Application No. 12/947,393, filed November 16, 2010, and entitled "System and Method for Performing Backup or Restore Operations Utilizing Difference Information and Timeline State Information," filed November 16, 2010 U.S. Patent Application No. 12/947,385, filed on November 16, 2010, entitled "System and Method for Managing Data with Service Level Agreements That May Specify Non-Uniform Copying of Data" and entitled "System and Method for Performing a Plurality of Prescribed Data Management Functions in a Manner That Reduces Redundant Access Operations to Primary Storage", U.S. Patent Application No. 12/947,436, filed November 16, 2010, entitled "System and Method for Creating Deduplicated Copies of Data by Tracking Amongel Temporations and by Ingesting Difference Data", U.S. Patent Application No. 12/947,418, filed November 16, 2010 and entitled "System and Method for Managing Deduplicated Copies of Data Using Temporal Relationships Among Copies", U.S. Patent Application No. 12/947,375, 2010 U.S. Patent Application No. 12/947,383, filed November 16, 2010, entitled "System and Method for Improved Garbage Collection Operations in a Deduplicated Store by Tracking Temporal Relationships Among Copies" U.S. Patent Application No. 12/947,513, filed November 16, entitled "System and Method for Creating Deduplicated Copies of Data by Sending Difference Data Between Two Near-Neighbor Temporal States," and filed November 16, 2010, entitled "System and US Patent Application No. 12/947,438 for "Method for Creating Deduplicated Copies of Data Storage Non-Lossy Encodings of Data Directly in a Content Addressable Store".

technical field

The present invention generally relates to data management, data protection, disaster recovery and business continuity. More specifically, the present invention relates to systems and methods for performing recovery utilizing disparate information and timeline state information.

Background technique

Business requirements for managing the lifecycle of application data have traditionally been met through the use of multiple point solutions, where each solution handles a portion of the lifecycle. This results in a complex and expensive infrastructure where multiple copies of the data are created and moved multiple times to separate repositories. The adoption of server virtualization has become a catalyst for simple, flexible and low-cost computer infrastructure. This leads to larger deployments of virtual hosts and storage, further exacerbating the gap between emerging computing models and current data management implementations.

Applications that provide business services depend on the storage of business service data at various stages of the data life cycle. Figure 1 shows a general set of data management operations that will apply to data of an application such as a database under business services such as payroll management. In order to provide business services, applications 102 require master data storage 122 with a certain reduced level of reliability and availability.

Backups 104 are made to protect against corruption or failure of the primary data storage through hardware or software failure or human error. Typically, backups may be made daily or weekly to local disk or tape 124 and moved less frequently (weekly or monthly) to a physically remote secure location 125 .

Simultaneous development and testing 106 of new applications based on the same database requires the development team to have access to another copy of the data 126 . Such snapshots may be made weekly, depending on the development schedule.

Compliance 108 with legal or voluntary policies may require that some data be retained for secure future access over a number of years; typically, data is copied to long-term archiving systems 128 on a regular basis (eg, monthly).

Disaster recovery service 110 prevents catastrophic loss of data if the system providing the primary business service fails due to some physical disaster. Given other constraints (such as cost), master data is copied ( 130 ) to physically distinct locations reasonably frequently. In the event of a disaster, the primary site can be rebuilt and the data moved back from the safe copy.

Business continuity services 112 provide facilities for ensuring continued business services if the primary site is damaged. Typically this requires a hot copy 132 of the master data that is nearly in sync with the master data, and a replication system and application and mechanism for switching incoming requests to the business continuity server.

Thus, data management is currently a collection of point applications that manage different parts of the lifecycle. This is an artifact of the evolution of data management solutions over the last two decades.

Description of drawings

Figure 1 is a simplified diagram of the current approach used to manage the data lifecycle of a business service.

Figure 2 is a schematic diagram of managing data throughout its life cycle through a single data management virtualization system.

Figure 3 is a simplified block diagram of a data management virtualization system.

Figure 4 is a view of a data management virtualization engine.

Figure 5 shows the object management and data movement engine.

Figure 6 shows a storage pool manager.

Figure 7 shows the breakdown of a service level agreement.

Figure 8 shows application specific modules.

Figure 9 shows the service policy manager.

Figure 10 is a flow diagram of the service policy scheduler.

Figure 11 is a block diagram of a Content Addressable Storage (CAS) provider.

Fig. 12 shows the definition of object handles within the CAS system.

Figure 13 shows the data model and operation of the temporal relationship graph stored for objects within the CAS.

Fig. 14 is a diagram representing the operation of the garbage collection algorithm in the CAS.

Fig. 15 is a flowchart of the operation of copying an object to the CAS.

16 is a system diagram of a general deployment of a data management virtualization system.

Fig. 17 is a schematic diagram of a featured physical server device for use on a data management virtualization system.

Detailed ways

Current data management structures and implementations such as those described above involve multiple applications handling different parts of data lifecycle management, all of which perform certain common functions: (a) make copies of application data (the frequency of this action is often referred to as Recovery Point Objective (RPO)), (b) stores a copy of the data in a dedicated repository, typically in a dedicated format, and (c) retains the copy for some duration measured as the retention time. The main differences within each point solution are the frequency of RPOs, retention times, and the characteristics of the individual repositories used, including capacity, cost, and geographic location.

The present disclosure relates to data management virtualization. Data management virtualization such as backup, replication, and archiving are virtualized in that they do not have to be configured to operate individually and separately. Instead, users define their business requirements regarding the lifecycle of the data, and the data management virtualization system automatically performs these operations. The snapshot is brought from primary storage to secondary storage; this snapshot is then used for backup operations to other secondary storage. Essentially, any number of these backups can be made, assuming the level of data protection dictated by the service level agreement.

The present disclosure also relates to a system for backing up data from a first storage pool to a second storage pool using differing information between temporal states, incorporated for performing data management functions including at least backup functions to create backup copies of data - the data management engine. The data management engine is operable to perform a sequence of snapshot operations to create point-in-time images of the application data on the first storage pool, each successive point-in-time image corresponding to a particular successive time-state of the application data, and each snapshot operation creating an indication Different information about which application data has changed and the content of the changed application data for a corresponding time state. The data management engine is also operable to perform on the application data at least one backup function that is scheduled for execution at discrete time-states and is also populated with maintained history information having time-state information indicating The time-status of the last backup function performed on application data by the corresponding backup copy of . The data management engine creates composite differential information from the differential information for each time state between the time-state of the last backup function performed on the application data and the time-state of the currently scheduled backup function to be performed on the application data, and The composite differential information is sent to the second storage pool to be compiled using the backup copy of the data at the last time-state to create a backup copy of the data for the current time-state.

The data management virtualization technology according to the present disclosure is based on a structure and implementation based on the following guiding principles.

First, define the business requirements for applications that use service level agreements (SLAs) for their entire data lifecycle. SLAs are much more complex than individual RPOs, retention and recovery time objectives (RTOs). It describes data protection characteristics at each stage of the data lifecycle. Each application can have a different SLA.

Second, provide a unified data management virtualization engine that manages the data protection lifecycle, moving data across various storage repositories with increased storage capacity and network bandwidth. Data management virtualization systems achieve these improvements by complementing the extended capabilities of modern storage systems by tracking the portions of data that change over time and by accessing replication and compression algorithms that reduce the amount of data that needs to be copied and moved .

Third, a single master copy of application data is supplemented as the basis for multiple elements within the lifecycle. Many data management operations such as backup, archive and replication depend on having a stable and consistent copy of the data to be protected. A data management virtualization system supplements a single copy of data for multiple purposes. A single instance of data maintained by the system can be used as a source, from which each data management function can make additional copies as needed. This is in contrast to the need for application data to be copied multiple times through multiple independent data management applications in traditional approaches.

Fourth, the abstraction of physical storage resources into a series of data protection storage pools, physical storage resources from different categories of storage - including local and remote disk, solid state storage, tape and optional media, dedicated, public and / or hybrid Storage Cloud - Virtualized. Storage pools provide access regardless of type, physical location, or underlying storage technology. Business requirements for the lifecycle of data may require that data be copied to different types of storage media at different times. Data management virtualization systems allow users to classify and aggregate different storage media into storage pools such as fast recovery storage pools consisting of high-speed disks and can be cost-effective deduplicated storage libraries or tape libraries on high-capacity disks long-term storage pool. A data management virtualization system can move data among these pools to take advantage of the unique characteristics of each storage medium. Abstraction of storage pools provides access regardless of type, physical location, or underlying storage technology.

Fifth, the movement of data between storage pools and disaster locations is improved by utilizing basic device capabilities and access to replicated application data. A data management virtualization system discovers the capabilities of storage systems, including storage pools, and utilizes these capabilities to move data efficiently. If the storage system is a disk array that supports the ability to create snapshots or clones of data volumes, the data management virtualization system will take advantage of this capability and use snapshots to make copies of data, rather than reading data from one place and writing it to another place. Similarly, if the storage system supports change tracking, the data management virtualization system will only update older copies with changes to effectively create new copies. When moving data across the network, the data management virtualization system uses deduplication and compression algorithms that avoid sending data that is already available on the other side of the network.

A key aspect of improving data movement is recognizing that application data changes slowly over time. A copy of an application made today will generally have much similarity to a copy of the same application made yesterday. In fact, today's copy of data can be represented as yesterday's copy with a series of incremental transformations, where the incremental transformations themselves are usually much smaller in size than all the data in the copy itself. The data management virtualization system captures and records these transformations in the form of bitmaps or range lists. In one embodiment of the system, the underlying storage resource—a disk array or server virtualization system—is capable of tracking changes made to volume or files; in these environments, the data management virtualization system queries the storage resource for a list of these changes , and save it with the protected data.

In a preferred embodiment of the data management virtualization system, there is a mechanism for eavesdropping on the main data access path of the application, which enables the data management virtualization system to observe which parts of the application data are modified, and to generate other parts of the modified data. own bitmap. If, for example, an application modifies blocks 100, 200, and 300 during certain periods of time, the data management virtualization system will eavesdrop on these events and create a bitmap indicating that these certain blocks were modified. When processing the next copy of the application data, the data management virtualization system will only process blocks 100, 200 and 300 because it knows that these blocks are only modified blocks.

In one embodiment of the system, where the application's main storage is a modern disk array or storage virtualization appliance, the data management virtualization system utilizes the point-in-time snapshot capability of the underlying storage device to make an initial copy of the data. This virtual copy mechanism is a fast, efficient and low-impact technique for creating an initial copy that does not guarantee that all bits will be copied or stored together. Instead, virtual copies are constructed by maintaining metadata and data structures that allow the copy to be recreated at access time, such as copy-on-write volume bitmaps or extents. Copying has a relatively light impact on the application and on the primary storage device. In another embodiment (where the application is based on a server virtualization system such as VMware or Xen), the data management virtualization system uses a similar virtual machine snapshot capability built into the server virtualization system. When virtual copy capabilities are not available, the data management virtualization system may include its own built-in snapshot mechanism.

It is possible to use snapshots as data primitives that form the basis of all data management functions supported by the system. Because it is portable, a snapshot can be used as an internal operation, even if the requested operation is not itself a snapshot; it is created to implement and facilitate other operations.

When creating a snapshot, there may be some preparatory operations involved in order to create a coherent snapshot or coherent image so that the image can be restored to a state that is usable by the application. These preparatory operations only need to be performed once, even though the snapshot will be replenished in multiple data management functions in the system, such as policy-scheduled backup copies. Preparing operations may include application quiescence, which includes clearing the data cache and freezing the state of the application; it may also include other operations known in the art and useful to maintain a complete image, such as from storing with the image The application collects metadata information.

Figure 2 illustrates one way in which a virtualized data management system can handle the data lifecycle requirements described earlier in accordance with these principles.

To serve local backup requirements, a sequence of valid snapshots is generated within the local high availability storage 202 . Some of these snapshots are used to accommodate dev/test requirements without making another copy. For longer-term retention of local backups, copies are efficiently made into long-term local storage 204, which in this implementation uses deduplication to reduce duplicate copies. The copy in long-term storage can be accessed as a backup or processed as an archive, depending on the retention policy applied by the SLA. Copies of data are made to remote storage 206 in order to meet remote backup and business continuity requirements—again, a single set of copies meets both purposes. As an alternative to remote backup and disaster recovery, another copy of the data can effectively be made to a repository 208 hosted by a commercial or private cloud storage provider.

Data Management Virtualization System

Figure 3 shows the high-level components of a data management virtualization system implementing the principles described above. Preferably, the system includes these basic functional components described further below.

Application 300 creates and owns data. This is a software system that has been deployed by a user as, for example, an e-mail system, a database system, or a financial reporting system in order to satisfy a certain computing need. Applications typically run on servers and utilize memory. For illustrative purposes, only one application is indicated. In fact, there may be hundreds or even thousands of applications managed by a single data management virtualization system.

Storage resources 302 are where application data is stored throughout its life cycle. Storage resources are physical storage assets including internal disk drives, disk arrays, optical and tape repositories, and cloud-based storage systems that users have acquired to handle data storage requirements. The storage resource consists of a primary memory 310 where an online active copy of the application data is stored and a secondary memory where an additional copy of the application data is stored for purposes such as backup, disaster recovery, archiving, indexing, Reporting and Other Purposes. Secondary storage resources may include additional storage within the same enclosure as primary storage as well as storage based on similar or different storage technologies within the same data center, another location, or across the Internet.

One or more management workstations 308 allow users to specify service level agreements (SLAs) 304 , which define the life cycle of application data. A management workstation is a desktop or laptop computer or mobile computing device used to configure, monitor, and control a data management virtualization system. A service level agreement is a detailed specification that captures detailed business requirements regarding the creation, retention and deletion of secondary copies of application data. SLAs are much more complex than the simple RTO and RPO used in traditional data management applications to express the frequency and expected recovery time of copies of a single secondary storage class. SLAs capture multiple stages in the data lifecycle specification and allow for non-uniform frequency and retention specifications within each secondary storage class. The SLA is described in more detail in FIG. 7 .

The data management virtualization engine 306 manages the entire lifecycle of application data as specified in the SLA. It may manage a large number of SLAs for a large number of applications. The data management virtualization engine takes input from the user through the management workstation and interacts with the application to discover application primary storage resources. The data management virtualization engine makes decisions about what data needs to be protected and what secondary storage resources best meet the protection needs. For example, if a business specifies its accounting data as requiring copies to be made at very short intervals for business continuity purposes and backup purposes, the engine may decide to create copies of the accounting data at short intervals according to an appropriate set of SLAs to the primary storage pool, and also create backup copies of the accounting data to the secondary storage pool at longer intervals. This is determined by the business requirements of the storage application.

The engine then uses the advanced capabilities of the available storage resources to make a copy of the application data. In the above example, the engine may use the storage device's built-in virtual copy or snapshot capabilities to schedule business continuity copies at short intervals. The data management virtualization engine moves application data among storage resources in order to meet business requirements captured in SLAs. The data management virtualization engine is described in more detail in FIG. 4 .

The data management virtualization system as a whole can be deployed within a single host computer system or device, or it can be one logical entity but physically distributed across a network of general and special purpose systems. Certain components of the system may also be deployed in computing or storage clouds.

In one embodiment of the data management virtualization system, the data management virtualization engine runs primarily as multiple processes on a pair of fault-tolerant redundant computers. Certain components of the data management virtualization engine may run adjacent to the application within the application server. Some other components may operate within the storage structure near the primary and secondary storage or within the storage system itself. Management stations are typically desktop and laptop computers and mobile devices connected to the engine over a secure network.

Data Management Virtualization Engine

Figure 4 shows an architectural overview of the data management virtualization engine 306 according to some embodiments of the invention. Engine 306 includes the following modules:

Application specific module 402 . This module is responsible for controlling and collecting metadata from the application 300 . Application metadata includes information about the application, such as the type of application, details about its configuration, the location of its data repository, its current operating state. Controlling the operation of an application includes actions such as flushing cached data to disk, freezing and unfreezing application I/O, rotating or truncating log files, and shutting down and restarting applications. The application specific modules perform these operations and send and receive metadata in response to commands from the service level policy engine 406 described below. The application specific modules are described in more detail with reference to FIG. 8 .

The service level policy engine 406 operates according to the SLA 304 provided by the user to make decisions regarding the creation, movement and deletion of copies of application data. Each SLA describes the business requirements associated with the protection of an application. The service level policy engine analyzes each SLA and derives a series of actions, where each action involves the copying of application data from one storage location to another. The service level policy engine then reviews these actions to determine priority and relevance, and schedules and initiates data movement jobs. The service level policy engine is described in more detail with reference to FIG. 9 .

The object manager and data movement engine 410 creates composite objects consisting of application data, application metadata and SLAs that it moves through different storage pools according to instructions from the policy engine. The object manager receives instructions in the form of commands from the service policy engine 406 to create a copy of the application data in a particular pool or in another pool from an existing copy eg 415 based on the live master data 413 belonging to the application 300 . The copy of the composite object created by the object manager and data movement engine is self-contained and self-describing because it contains not only application data, but also application metadata and SLAs for the application. The object manager and data movement engine are described in more detail with reference to FIG. 5 .

Storage pool manager 412 is a component that adapts and abstracts underlying physical storage resources 302 and presents them as virtual storage pools 418 . Physical storage resources are actual storage assets, such as disk arrays and tape libraries that a user has deployed for the purpose of supporting the lifecycle of data for the user's applications. These storage resources can be based on different storage technologies such as disk, tape, flash memory or optical storage. Storage resources can also have different geographic locations, cost and speed attributes, and can support different protocols. The role of the storage pool manager is to combine and aggregate storage resources and to mask the differences between its programming interfaces. The storage pool manager presents physical storage resources to the object manager 410 as a set of storage pools with characteristics that make the pools suitable for specific stages in the lifecycle of application data. The storage pool manager is described in more detail with reference to FIG. 6 .

Object Manager and Data Movement Engine

FIG. 5 shows the object manager and data movement engine 410 . The object manager and data movement engine discover and use the virtual storage resources 510 presented to it by the pool manager 504 . It accepts requests from the service level policy engine 406 to create and maintain data storage object instances from resources in the virtual storage pool, and it copies applications between instances of storage objects in the virtual storage pool according to instructions from the service level policy engine data. The target pool selected for copying implicitly specifies the selected business operation, such as backup, replication or restore. The Service Level Policy Engine resides locally to the Object Manager (on the same system) or remotely and communicates through standard networked communications using protocols. TCP/IP can be used in the preferred embodiment because it is well understood, widely available, and allows the Service Level Policy Engine to be located locally to the Object Manager or remotely with little modification.

In one embodiment, the system can deploy the service level policy engine and the object manager on the same computer system for ease of implementation. In another embodiment, the system may use multiple systems, each hosting a subset of components if beneficial or convenient to the application, without changing the design.

Object manager 501 and storage pool manager 504 are software components that may be resident on a computer system platform that interconnects storage resources and the computer systems that use those storage resources, where user applications reside on the on the computer system. The placement of these software components on an interconnect platform is specified as a preferred embodiment and may provide the ability to connect client systems to storage via communication protocols (e.g., Fiber Channel, iSCSI, etc.) widely used for such applications, and Ease of deployment of various software components may also be provided.

Object manager 501 and storage pool manager 504 communicate with the underlying storage virtualization platform via application programming interfaces provided by the platform. These interfaces allow the software component to query and control the behavior of the computer system on which the user's applications reside and how it interconnects storage resources with the computer system. As is common in practice, components apply modularization techniques to allow replacement of intercommunication code specific to a given platform.

Object managers and storage pool managers communicate via a protocol. These are transmitted via standard networking protocols such as TCP/IP or standard interprocess communication (IPC) mechanisms generally available on computer systems. Depending on the particular computer platform, this allows comparable communication between components if the components are resident on the same computer platform or on multiple computer platforms connected by a network. For ease of deployment, the current configuration has all local software components resident on the same computer system. As mentioned above, this is not a strict requirement of the design and can be reconfigured as needed in the future.

object manager

Object manager 501 is a software component for maintaining data storage objects and provides a set of protocol operations to control it. Operations include creation, destruction, copying and copying of data between objects, maintaining access to objects, and in particular allowing specification of storage pools for creating copies. There is no common subset of features supported by all pools; however, in a preferred embodiment, the primary pool may be performance optimized, i.e., lower latency, while the backup or replicated pool may be capacity optimized, supporting larger The data sum of the quantity is content addressable. Pools can be remote or local. Storage pools are classified according to various criteria, including the means available to users to make business decisions, such as cost per gigabyte of storage.

First, the particular storage device from which storage is taken may be a consideration, as devices are allocated for different business purposes along with associated cost and other practical considerations. Some equipment may not even be actual hardware, but capacity offered as a service, and the selection of such resources may be done for actual business purposes.

Second, network topology "proximity" is considered, because nearby storage is generally connected by low-latency, inexpensive network resources, while distant storage can be connected by high-latency, bandwidth-limited expensive network resources; conversely, when geographical The distance of the storage pool relative to the source can be beneficial when diversity is protected from physical disasters affecting local resources.

Third, consider storage optimization characteristics, some of which are optimized for space-efficient storage but require computational time and resources to analyze or transform data before it is stored, while others are "performance-optimized" in comparison, In contrast, more storage resources are used, but less computer time or resources are used to transform the data (if any).

Fourth, consider the "speed of access" feature, where some resources inherent to the storage computer platform become readily and quickly available to user applications, such as virtual SCSI block devices, while some resources may only be used indirectly. These eases and speeds of recovery are often governed by the type of storage used, and this allows it to be categorized appropriately.

Fifth, take into account the amount of storage used and available in a given pool, as there may be benefits to pooling or expanding the storage capacity used.

A service level policy engine, described below, combines user provided SLAs with classification criteria to determine how and when to maintain application data, and the storage pool draws the required resources from it to meet the service level agreement (SLA).

The object manager 501 creates, maintains and uses a history mechanism to track the series of operations performed on data objects within a performance pool and correlate those operations with other operations that move objects to other storage pools, especially capacity optimized operations. This series of records for each data object is maintained at the object manager of all data objects in the main pool, all data objects are initially associated by the main data object, and then in order of operations: each object's timeline and all such List of timelines. Each operation performed exposes basic virtualization primitives to capture the state of a data object at a given point in time.

Furthermore, the base storage virtualization apparatus can be modified to expose and allow retrieval of internal data structures such as bitmaps indicating modifications of portions of data within data objects. These data structures are exploited to capture the state of a data object at a data point: for example, a snapshot of the data object, and provide the differences between snapshots taken at specified times, and thus enable optimal backup and recovery. Although specific implementations and data structures may change among different devices from different vendors, data structures are used to track changes to data objects, and memory is used to maintain the original state of those parts of the objects that have changed: The indications correspond to data retained in memory. When accessing the snapshot, the data structure is consulted, and for changed parts, the saved data is accessed instead of the current data, because the data object was modified at the region so indicated. The general data structure used is a bitmap, where each bit corresponds to a section of a data object. A set bit indicates that the extent was modified after the point in time of the snapshot operation. The basic snapshot primitive mechanism maintains this as long as the snapshot object exists.

The timeline described above maintains a list of snapshot operations against a given original data object, including when the operation started, when it stopped (if any), a reference to the snapshot object, and references to internal data structures (e.g., bitmap or range list), making it available from the base system. Also maintained is the copying of the state of the data object into another pool at any given point in time—as an example, copying the state of the data object into the capacity-optimized pool 407 using the content addressing results in the object handle A reference to the result. This object handle corresponds to the given snapshot and is stored in the timeline using the snapshot operation. This association is used to identify an appropriate starting point.

Best Backup and Recovery Advisory list of operations from desired start point to end point. The time-ordered list of operations and their corresponding data structures (bitmaps) are structured such that a continuous time series from start to finish is realized: there is no gap between the start times of the operations in the series. This ensures that all changes to the data object are represented by the corresponding bitmap data structure. It is not necessary to retrieve all operations from start to finish; concurrent data objects and base snapshots overlap in time; it is only necessary that there are no gaps in time where untracked changes may occur. When a bitmap indicates that a certain memory block has changed but not what the change was, the bitmaps can be added or composed together to achieve a set of all changes that occur in a time interval. Rather than using this data structure to access the state at a point in time, the system instead exploits the fact that the data structure represents data that is modified as time passes forward. Rather, the final state of the data object is accessed at the indicated region, thus returning the set of changes to the given data object from the given start time to the end time.

Backup operations utilize this timeline, associated references and access to internal data structures to implement our backup operations. Similarly, it uses the system in a complementary way to implement our recovery operations. Specific steps are described below in the "Best Backup/Restore" section.

Virtual storage pool type

Figure 5 shows several representative storage pool types. Although one primary storage pool and two secondary storage pools are depicted in the figures, more storage pools may be configured in some embodiments.

Main Storage Pool 507 - Contains storage resources for creating data objects where user applications store their data. This is in contrast to other storage pools, which exist to primarily implement the operations of the data management virtualization engine.

Performance Optimized Pool 508 - a virtual storage pool capable of providing high performance backup (ie, point-in-time copy described below) and fast access to backup images by user applications.

Capacity Optimized Pool 509 - A virtual storage pool that provides storage of data objects primarily in a highly space efficient manner by using the replication techniques described below. A virtual storage pool provides access to copies of data objects, but does not do so with high performance as its primary goal, in contrast to the performance-optimized pools above.

The initial deployment contains storage pools as described above as a minimal set of operations. The design fully anticipates multiple pools of various types representing various combinations of the criteria described above and multiple pool managers conveniently representing all storage in future deployments. The trade-offs shown above are characteristic of computing data storage systems.

From a practical point of view, these three pools represent a preferred embodiment that handles most user requirements in a very simple manner. Most users will find that if they have one pool of storage for emergency recovery needs (which provides fast recovery) and another pool at low cost so that large numbers of images can be retained over long periods of time, almost all aspects of data protection are Commercial requirements can be met with little damage.

The format of the data in each pool is dictated by the objects and technologies used within the pool. For example, the fast recovery pool is maintained in a form that closely resembles the original data to minimize required transformations and increase the speed of recovery. Long-term storage pools, on the other hand, use deduplication and compression to reduce the size of data and thus the cost of storage.

Object Management Operations 505

Object manager 501 creates and maintains instructions for data storage objects 503 from virtual storage pool 418 according to instructions sent to it by service level agreement engine 406 . The object manager provides data object operations in five main areas: point-in-time copy or copy (often referred to as "snapshot"), standard copy, object maintenance, map and access maintenance, and collection.

Object management operations also include a series of resource discovery operations for maintaining the virtual storage pools themselves and retrieving information about them. The pool manager 504 ultimately provides the functionality for these.

Point-in-time copy ("snapshot") operations

A snapshot operation creates a data object instance representing the initial object instance at a particular point in time. More specifically, a snapshot operation uses the resources of a specified virtual storage pool to create a complete virtual copy of a member of the collection. This is called a datastore object. The multiple states of the data storage object are maintained over time such that the state of the data storage object present at the data point is available. As mentioned above, a virtual copy is a copy implemented using the base storage virtualization API, which allows data to be copied in a portable manner using back-on-write or other in-band techniques rather than copying and storing all bits of the copied data to disk. create. In some embodiments, this can be accomplished using software modules written to get the capabilities of the off-the-shelf basic storage virtualization systems provided by, for example, EMC, vmware, or IBM. Where such basic virtualization is not available, the system may provide its own virtualization layer for interfacing with intelligent hardware.

Snapshot operations require the application to freeze the state of the data to a specific point so that the image data is coherent and the snapshot can be used later to restore the state of the application at the time of the snapshot. Other preliminary steps may also be required. These are handled by application specific modules 302 described in subsequent sections. Therefore for real-time applications, the most portable operation is required.

Snapshot operations are used as data primitives for all high-level operations in the system. In effect, they provide access to the state of the data at a specific point in time. Because snapshots are also typically implemented using copy-on-write technology that separates changed content from what is resident on disk, these snapshots provide diffs that can also be composed or added together to effectively copy data across the system. The format of the snapshot may be the format of the data copied by the data mover 502, which is described below.

standard copy operation

When a copy operation is not a snapshot, it can be considered a standard copy operation. A standard copy operation copies all or a subset of a source data object in one storage pool to a data object in another storage pool. The result is two different objects. One type of standard copy operation that can be used is an initial "baseline" copy. This is typically done when data is initially copied from one virtual storage pool to another, such as from a performance optimized pool to a capacity optimized storage pool. Another type of standard consideration operation may be used, where only changed data or differences are copied to the target storage pool to update the target object. This will occur after the initial baseline copy was previously performed.

A fully detailed version of the object need not be kept in the system each time a copy is made, even though a baseline copy is required when the data virtualization system is first initialized. This is because each virtual copy provides access to a full copy. Any deltas or differences can be expressed as being relative to the virtual copy rather than the baseline. This has the positive side effect of virtually eliminating the common step of walking through a series of change lists.

A standard copy operation is initiated by a series of instructions or requests provided by the pool manager and received by the data mover to cause the movement of data among the data storage objects and maintain the data storage objects themselves. A copy operation allows a copy of a specified data storage object to be created using a specified virtual storage pool. The result is a copy of the source data object in the target data object in the storage pool.

Snapshot and copy operations are each constructed using a prepare operation and an activate operation. The two steps of preparation and activation allow long-running resource allocation operations (which are characteristic of the preparation phase) to be decoupled from activation. This may be desired for applications that only pause for a short while while implementing the point-in-time characteristics of snapshot operations, which actually take a finite but non-zero amount of time to implement. Similar to copy and snapshot operations, this two-step provisioning and activation structure allows the policy engine to continue operating only when all set members' resources can be allocated.

object maintenance

Object maintenance operations are a series of operations for maintaining data objects, including creation, destruction, and replication. Object managers and data movers use the capabilities of the pool request broker (more on that below) to implement these operations. Data objects can be maintained at the global level, per storage pool or preferably both.

gather

The collect operation is a helper function. A collection is an abstract software concept, a list maintained in memory by an object manager. They allow policy engine 206 to request a series of operations on all members of the set, allowing consistent application of requests to all members. The use of collections allows simultaneous activation of point-in-time snapshots such that multiple data store objects are all captured at exactly the same point in time, as this is generally required for applications of logically correct recovery. The use of collections allows for convenient requests for copy operations across all members of the collection, where an application will use multiple storage objects as a logical whole.

Resource discovery operation

The object manager discovers virtual storage pools by issuing object management operations 505 to the pool manager 504, and uses the information obtained about each pool to select a pool that meets the required criteria for a given request, or in the case of no match, A failure pool is selected, and the object manager can then use resources from the selected virtual storage pool to create data storage objects.

mapping and access

The object manager also provides a set of object manager operations to enable and maintain the availability of these objects to external applications. The first set is operations for registering and deregistering the user's application-resident computer. Register the computer with an identity typical for the storage network in use (eg, Fiber Channel WWPN, iSCSI identity, etc.). The second set is the "map" operation, and when allowed by the storage pool from which the object is created, a datastore object can be "mapped", that is, made available to the computer on which the user application resides.

This availability takes the form of appropriate storage, such as block devices that exist as Fiber Channel disks on a SAN or iSCSI devices on a network, file systems on a file sharing network, etc., and are available to the operating system on the application computer. Similarly, the "unmap" operation reverses the availability of the virtual storage device on the network to the user application. In this way, data stored for one application, ie, a backup, can be made available, ie, restored, to another application on another computer at a later time.

502 Data Mover

Data mover 502 is a software component within the object manager and data mover that reads and writes data among various data storage objects 503 according to instructions received from the object manager for snapshot (point-in-time) copy requests and standard copy requests device. Data movers provide operations for reading and writing data among instances of data objects throughout the system. The Data Mover also provides operations that allow querying and maintaining the state of long-running operations that the Object Manager requests it to perform.

The Data Mover uses capabilities from the Pool Capabilities Provider (see Figure 6) for its operations. A snapshot function provider 608 allows the creation of a data object instance representing the initial object instance at a particular point in time. The difference engine function provider 614 is used to request a description of the difference between two data objects related on the time chain. For data objects stored on content-addressable pools, a special function is provided that provides the difference between any two arbitrary data objects. This functionality is also provided for performance optimized pools in some cases by the underlying storage virtualization system and in other cases by modules that implement this on commodity storage. Data mover 502 uses the information about differences to select the data sets it copies between instances of data object 503 .

For a given pool, a difference engine provider provides a specific representation of the difference between two states of a datastore object over time. For a snapshot provider, changes between two points in time are recorded as writes to a given portion of a datastore object. In one embodiment, the differences are represented as a bitmap, where each bit corresponds to an ordered list of regions of the data object starting at the first and ascending to the last, with a set bit indicating the modified region. This bitmap is derived from the copy-on-write bitmap used by the underlying storage virtualization system. In another embodiment, the differences may be represented as a list of extents corresponding to changed regions of the data. For the content-addressable storage provider 610, this representation is described below and is used to effectively determine the different parts of two content-addressable data objects.

The data mover uses this information to copy only those parts that differ, so that a new version of a data object can be created from an existing version by first copying it, getting a list of differences, and then moving only the data corresponding to those differences in the list . The data mover 502 traverses the list of differences, moving the indicated regions from the source data object to the target data object. (See Best Ways to Backup and Restore Data).

506 copy operation - request conversion and instruction

Object manager 501 instructs data mover 502 through a series of operations to copy data among data objects in virtual storage pool 418 . The process consists of the following steps that begin when an instruction is received:

First, create a collection request. The name of the collection is returned.

Second, add the object to the collection. The collection name from above is also used as the name of the source data object to be copied and the names of the two preceding instances: the data object in the source storage resource pool that is compared for differences and the corresponding data object in the target storage resource pool . This step is repeated for each source data object that will be operated on in this collection.

Third, prepare the copy request. A collection name is also provided, and a storage resource pool acts as a target. The prepare command instructs the object manager to contact the storage pool manager to create the necessary target data objects corresponding to each resource in the collection. The prepare command also provides the corresponding data object in the target storage resource pool to be copied, so the provider can copy the provided object and use it as the target object. The reference name of the copy request is returned.

Fourth, activate the copy request. The reference name of the copy request returned above is provided. A data mover is instructed to copy a given source object to its corresponding target object. Each request includes a reference name and a sequence number describing the overall work (the entire set of source-target pairs) and a sequence number describing each individual source-target pair. Except for source-target pairs, the name of the corresponding predecessor is provided as part of the copy instruction.

Fifth, the copy engine uses the name of the data object in the storage pool to get the difference between the previous instance and from the difference engine at the source. The indicated differences are then transferred from the source to the target. In one embodiment, these differences are transmitted as bitmaps and data. In another embodiment, these differences are transmitted as range lists and data.

503 data storage object

Data storage objects are software structures that allow the storage and retrieval of application data using idioms and methods familiar to computer data processing devices and software. In practice, these currently take the form of SCSI block devices on storage networks, such as SCSI LUNs or content-addressable containers, where a pointer to content is constructed from the data within and uniquely identifies that data. Create and maintain data storage objects by issuing instructions to the pool manager. The actual storage used to make application data persistent is drawn from the virtual storage pool, from which data storage objects are created.

The structure of the data storage objects varies according to the storage pool from which the data storage objects are created. For objects that take the form of a block device—a data structure for a given block device—on a storage network, the data object implements the logical block address (LBA) and device identity of the actual storage location for each block within the data object Mapping between tokens and LBAs. The identifier of the data object is used to identify the mapping set to use. The current embodiment relies on the services provided by the underlying physical computer platform to implement this mapping, and on its internal data structures such as bitmaps or range lists.

For objects in the form of content addressable containers, the content identifying characteristics are used as identifiers and the data objects are stored as described below in the section on deduplication.

504 Pool Manager

Pool manager 504 is a software component for managing virtual storage resources and related functional features as described below. Object manager 501 and data movement engine 502 communicate with one or more pool managers 504 to maintain data storage objects 503 .

510 virtual storage resources

Virtual storage resources 510 are various types of storage available to the pool manager for implementing storage pool functions, as described below. In this embodiment, a storage virtualizer is used to present various external Fiber Channel or iSCSI storage LUNs to the pool manager 504 as virtualized storage.

storage pool manager

FIG. 6 further illustrates the storage pool manager 504 . The purpose of the storage pool manager is to provide basic virtual storage resources to the object manager/data mover as a storage resource pool, which is an abstraction of storage and data management functions with a common interface utilized by other parts of the system. These common interfaces generally include mechanisms for identifying and handling data objects associated with a particular temporal state and for generating differences between data objects in the form of bitmaps or ranges. In this embodiment, the facility manager provides primary storage pools, performance optimized pools and capacity optimized pools. The public interface allows object managers to create and delete datastore objects in these pools, either as copies of other datastore objects or as new objects, and data movers can move objects between datastore objects, and can use data object distinctions the result of the operation.

A storage pool manager has a general structure of common interfaces for different implementations of similar functions, some of which are provided by "intelligent" primitives, while other functions must be implemented on less functional primitives.

Pool request broker 602 and pool function provider 604 are software modules that execute in the same process as the object manager/data mover or in another process that communicates via a local or network protocol such as TCP. In this embodiment, the providers include a main storage provider 606, a snapshot provider 608, a content addressable provider 610, and a difference engine provider 614, and these providers are further described below. In another embodiment, the set of providers may be a superset of the providers shown here.

Virtual storage resources 510 are different types of storage that can be employed by the pool manager for implementing storage pool functionality. In this embodiment, the virtual storage resource consists of a group of SCSI logical units of the storage virtualization system: The storage virtualization system runs on the same hardware as the pool manager and is accessible (for data and management operations) through a programming interface: except In addition to standard block storage functionality, additional capabilities are available, including creating and deleting snapshots, and tracking changed parts of a volume. In another embodiment, virtual resources can come from external storage systems that expose similar capabilities, and can be accessed on interfaces (for example, through a file system or through network interfaces such as CIFS, iSCSI, or CDMI), in capabilities (for example, whether the resource operations that support copy-on-write snapshots), or in non-functional aspects (eg, high-speed/limited-capacity such as solid state disks versus slow/high-capacity such as SATA disks). The available capabilities and interfaces determine which providers can consume virtual storage resources, and which pool functionality needs to be implemented within the pool manager by one or more providers: for example, this implementation of the Content Addressable Storage provider requires only "dumb " storage, and the implementation is entirely within the content-addressable provider 610; the basic content-addressable virtual storage resource can be used instead on a simpler "pass-through" provider. Instead, this implementation of the snapshot provider generally "passes through" and needs to expose storage for fast point-in-time copy operations.

The pool request broker 602 is a simple software component that provides requests for storage pool specific functions by executing an appropriate set of pool function providers against the configured virtual storage resources 510 . Requests that can be served include, but are not limited to, creating an object in a pool; deleting an object from a pool; writing data to an object; reading data from an object; copying an object within a pool; copying an object between pools; requesting two objects in a pool An overview of the differences between .

Primary storage provider 606 implements a management interface (eg, creating and deleting snapshots and tracking changed parts of files) for virtual storage resources that are also directly exposed to applications via interfaces such as Fiber Channel, iSCSI, NFS, or CIFS.

Snapshot provider 608 implements the functionality of making point-in-time copies of data from the primary storage pool. This creates an abstraction of another resource pool populated with snapshots. As implemented, a point-in-time copy is a copy-on-write snapshot of an object from the main storage pool, consuming a second virtual storage resource to accommodate the copy-on-write copy, since this management function is shared by both for main storage and for the snapshot provider virtual storage resources exposed.

The difference engine provider 614 may fulfill requests for two objects in the pool to be compared, connected in a time chain. Differences between these two objects are identified and outlined in a provider-specific way, eg using bitmaps or ranges. For example, a difference portion may be represented as a bitmap, where each set bit represents a fixed-size region where the two objects differ; or a difference may be represented procedurally as a series of function calls or callbacks.

Depending on the virtual storage resource on which the pool is based or the other provider that implements the pool, the difference engine can efficiently produce results in various ways. As implemented, a diff engine operating on a pool implemented via a snapshot provider uses the copy-on-write feature of the snapshot provider to track changes to objects made by snapshots. Successive snapshots of a single changed original object thus have a record of differences stored with them by the snapshot provider, and the snapshot pool's difference engine retrieves only this record of changes. As also implemented, the difference engine acting on pools implemented via content-addressable providers uses the efficient tree structure of content-addressable implementations (see below, Figure 12) to accomplish fast translation between objects on demand Compare.

Content Addressable Provider 610 implements a write-once-read-many content-addressable interface for the virtual storage resources it consumes. It satisfies read, write, copy and delete operations. Each written or copied object is identified by a unique handle derived from its contents. The Content Addressable Provider (Figure 11) is described further below.

Pool Manager Operations

In operation, the pool request broker 502 accepts requests for data manipulation operations such as copying, snapshotting, or deleting pools or objects. The request broker determines which provider code from pool 504 is executed by looking at the name or reference of the pool or object. The mediation then converts the incoming service request into a form that can be processed by the specific pool function provider and invokes the appropriate sequence of provider operations.

For example, an incoming request may request that a snapshot from a volume in the primary storage pool be snapped into the snap pool. Incoming requests identify objects (volumes) in the main storage pool by name, and the combination of name and operation (snapshot) determines that a snapshot provider should be invoked, which can produce point-in-time snapshots from the main pool using basic snapshot capabilities. This snapshot provider translates the request into the exact form required by the native copy-on-write functionality performed by the underlying storage virtualization appliance, such as a bitmap or extent, and it translates the result of the native copy-on-write functionality into a form that can be returned to the object manager pool manager and use in future requests to the pool manager.

Best way to backup data using Object Manager and Data Mover

The best way to back up data is as a series of operations that produce successive versions of application data objects over time while minimizing the amount of data that must be passed using bitmaps, extents, and other time-difference information stored in the object mover. to be copied. It stores application data in data storage objects and associates it with metadata that relates changes to application data over time so that changes over time can be easily identified.

In a preferred embodiment, the process includes the following steps:

1. The mechanism provides the initial reference state of the application data within the data storage object, such as T0;

2. Create subsequent instances (versions) of the data store object in the virtual storage pool with the difference engine provider on demand over time;

3. Each successive version such as T4, T5 uses the virtual storage pool's difference engine provider to get the difference between it and the instance created before it, so that T5 is stored as a reference to T4 and a reference between T5 and T4 group difference;

4. The copy engine receives requests to copy data from one data object (source) to another data center (destination);

5. If the virtual storage pool (in which the destination object is to be created) contains no other objects created from previous versions of the source data object, a new object is created in the destination virtual storage pool and the entire contents of the source data object is copied to Destination object; the process ends. Otherwise, the next step follows;

6. If the virtual storage pool (in which the object was created) contains objects created from a previous version of the source data object, then the most recently created previous version in the destination virtual storage pool for which virtual storage of the source data object exists is selected The corresponding previous version in the pool. For example, if a copy of T5 originates from a snap pool, and the object created at time T3 is the most recent version available at the target, T3 is chosen as the previous version;

7. A time-ordered list of versions of the source data objects is constructed, starting with the initial version identified in the previous steps and ending with the source data objects to be copied. In the above example, at the snapshot pool, all states of the object are available, but only the states including and after T3 make sense: T3, T4, T5;

8. A corresponding list of differences between each successive version in the list is constructed such that all differences from the starting version to the final version of the list are represented. Differences both identify which part of the data was changed and include new data at the corresponding time. This produces a set of differences from the target version to the source version, for example the differences between T3 and T5.

9. creating a destination object by copying a previous version of the object identified in step 6 in the destination virtual storage pool, for example object T3 in the destination repository;

10. The set of differences identified in the list created in step 8 is copied from the source data object to the destination object and the process ends.

Each data object within the destination virtual storage pool is complete; that is, it represents the entire data object and allows access to all application data at one point in time without requiring knowledge of the state or Represents an external reference. Objects are reachable without passing all deltas from the baseline state to the current state. Furthermore, replication of initial and subsequent versions of data objects in the destination virtual storage pool does not require an exhaustive replication of the data content in which it is applied. Finally, reaching the second and subsequent states requires only the transfer of the tracked and maintained changes, as described above, and no traversal, transfer or copying of the contents of the data store object.

Best way to use data resources with object managers and data movers

Intuitively, the best way for data resources is the transformation of the best way for data backup. Recreating the desired state of the data objects in the destination virtual storage pool at a given point in time includes the following steps:

1. A version of a data object in another virtual storage pool with a difference engine provider corresponding to a desired state to be created is identified. This is the source data object in the source virtual storage pool;

2. identifying previous versions of data objects recreated in the destination virtual storage pool;

3. If no data objects are identified in step 2, a new destination object in the destination virtual storage pool is created and data is copied from the source data object to the destination data object. The process is complete. Otherwise, continue with the following steps;

4. If the version of the data object is identified in step 2, identifying the data object in the source virtual storage pool corresponding to the data object identified in step 2;

5. If no data objects are identified in step 4, a new destination object in the destination virtual storage pool is created and data is copied from the source data object to the destination data object. The process is complete. Otherwise, continue with the following steps;

6. creating a new destination data object in the destination virtual storage pool by duplicating the data object identified in step 2;

7. using the difference engine provider of the source virtual storage pool to obtain a set of differences between the data object identified in step 1 and the data object identified in step 4;

8. Copy the data identified by the list created by step 7 from the source data object to the destination data object. The process ends.

Access to the desired state is complete: it requires no external references to other containers or external state. Neither an exhaustive traversal nor an exhaustive transfer is required to establish the reference state for a given desired state, only the fetched changes indicated by the provided representation within the source virtual storage pool.

service level agreement

Figure 7 shows a service level agreement. Service level agreements capture detailed business requirements regarding secondary copies of application data. In the simplest description, business requirements define when and how often copies are created, how long they are retained and in what type of storage pool those copies exist. This simplistic description fails to capture several aspects of business requirements. The frequency at which copies of a pool of a given type are created may not be consistent throughout all hours of the day or all days of the week. Certain hours of the day or days of the week or month may represent more (less) critical periods in the application data, and thus may require more (or less) frequent copies. Similarly, all copies of application data in a particular pool may not need to be kept for the same length of time. For example, a copy of application data created at the end of monthly processing may need to be retained for a longer period of time than a copy in the same storage pool created in mid-January.

The Service Level Agreement 304 of certain embodiments is designed to represent all of these complexities that exist in business requirements. A service level agreement has four main parts: a name, a destination, a collection of housekeeping attributes, and a service level policy. As mentioned above, each application has an SLA.

The name attribute 701 allows each service level agreement to have a unique name.

Description attribute 702 is a helpful description of the user-specifiable service level agreement.

The service level agreement also has a number of housekeeping attributes 703 that enable it to be maintained and modified. These attributes include, but are not limited to, identity of owner, date and time of creation, modification and access, priority, enable/disable flag.

The service level agreement also contains a number of service level policies 705 . Some service level agreements may have only a single service level policy. More generally, a single SLA can contain dozens of policies.

In some embodiments, each service level policy consists of at least the following: source storage pool location 706 and type 708; target storage pool location 710 and type 712; frequency of creating copies 714 represented as a time period; represented by The length of the retention period for copies of the time period 716; the time of day during which this particular service level policy operates 718; and the days of the week, month, or year to which this service level policy applies 720.

Each service level policy specifies source and target storage pools and the frequency at which application data is required to be copied between those storage pools. In addition, the Service Level Policy specifies the hours of its operation and the days on which it is applicable. Each service level policy is an expression of a single statement in the business requirements for protection of application data. For example, if a particular application has a business requirement for archive copies created each month after monthly shutdown and retention for three years, this may translate to the need to move from the local backup storage pool to the long-term archive in the middle of the night on the last day of January The service level policy for copies of storage pools, with a retention period of three years.

All service level policies with a particular combination of source and destination pools and locations, such as source main storage pools and destination local snap pools, when considered together specify the business requirements for creating copies into that particular destination pool. Business requirements may dictate, for example, that snapshot copies are created every hour during regular business hours but only every four hours outside of these hours. Two service level policies with the same source and target storage pools will effectively capture these requirements in a form enforceable by the service policy engine.

This form of service level agreement allows for the planned representation of daily, weekly and monthly business activities, and thus captures business requirements for securing and managing application data more accurately than traditional RPO and RPO-based approaches. Scheduling can occur on a "calendar basis" by allowing hours of operation and days, weeks, and months of the year.

All service level policies with one specific combination of source and destination such as "source: local primary and destination: local performance optimized" together capture non-uniform data protection requirements for a type of storage. A single RPO number on the other hand enforces a single consistent frequency of data protection at all times of day and in all days. For example, a combination of service level policies may require a large number of snapshots to be kept for a short period of time, such as 10 minutes, and a smaller number of snapshots to be kept for a longer period of time, such as 8 hours; this allows recovery of small amounts of information that are accidentally deleted to the state no more than 10 minutes ago while still providing substantial data protection over longer time horizons without the storage overhead of storing all the snapshots taken every ten minutes. As another example, a backup data protection function may be given a policy that operates at one frequency during the work week and at another frequency during the weekend.

SLAs fully capture all data for the entire application—including local snapshots, local long-duration repositories, off-device storage, archives, etc.—when service level policies for all different classes of source and destination storage are included Include requirements. A collection of policies within an SLA can represent when a given function should be performed, and can represent the various data management functions that should be performed on a given data source.

Service level agreements are created and modified by users through the user interface on the management workstation. These agreements are electronic documents stored by the Service Policy Engine in a structured SQL database or other repository it manages. Policies are retrieved, electronically analyzed and acted upon by the service policy engine through its normal schedule as described above.

FIG. 8 shows an application specific module 402 . Application specific modules run adjacent to the application 300 (described above) and interact with the application and its operating environment to collect metadata and query and control the application as needed for data management operations.

Application-specific modules interact with the various components of the application and its operating environment, including application service processes and daemons 801, application configuration data 802, operating system storage services 803 (such as VSS and VDS on Windows), logical volume management and file system services 804 and operating environment drivers and modules 805 .

The application specific modules perform these operations in response to control commands from the service policy engine 406 . There are two purposes for these interactions with applications: metadata collection and application consistency.

Metadata collection is the process by which an application specific module collects metadata about an application. In some embodiments, metadata includes information such as: the application's configuration parameters; the application's state and status; the application's control files and startup/shutdown scripts; the location of the application's data files, logs, and transaction records; File system fixpoints, logical volume names, and other such entities that can affect access to application data.

Metadata is collected and stored along with application data and SLA information. This ensures that each copy of the application data within the system is complete and includes all details needed to reconstruct the application data.

Application consistency is a set of actions that, when a copy of application data is created, ensures that the copy is valid and recoverable to a valid instance of the application. This is critical when business requirements dictate that the application is protected while the application is active, in its online operating state. Applications may have interdependent data relationships within their data stores, and if these are not copied in a consistent state, this will not provide a valid restorable image.

The exact process for achieving application consistency varies from one application to another. Some applications have simple flush commands that force cached data to disk. Some applications support a hot standby mode, where the application ensures that its operations are recorded in a manner that ensures consistency, even when application data changes. Some applications require interaction with operating system storage devices such as VSS and VDS to ensure consistency. Application-specific modules are purpose-built to work with and ensure consistency with a specific application. Application specific modules interact with the underlying storage virtualization appliance and object manager to provide consistent snapshots of application data.

A preferred embodiment of the application specific module 402 is to run on the same server as the application 300 for efficiency. This ensures minimal latency in interactions with the application and provides access to storage services and file systems on the application host. The application host is generally considered main memory, which is then snapshotted to a performance-optimized repository.

To minimize disruption to running applications, including minimizing preparatory steps, application-specific modules are only triggered when access to corresponding data is required at a specific time and when a snapshot for that time does not exist elsewhere in the system Snapshots are taken, as tracked by the object manager. By tracking when snapshots were taken, the object manager is able to fulfill subsequent data requests from the performance optimized data store, including for satisfying multiple requests for backup and replication, which may originate from secondary capacity optimized pools. Depending on the underlying storage, the object manager may be able to provide object handles to snapshots in the performance-optimized store and may boot the performance-optimized store in a native format specific to the snapshot's format. In some embodiments, this format may be application data combined with one or more LUN bitmaps indicating which blocks changed; in other embodiments, it may be a specific range. The format used for data transfer is thus able to use only bitmaps or ranges to transfer deltas or differences between two snapshots.

Metadata such as the application's version number may also be stored for each application along with the snapshot. When the SLA policy is enforced, the application metadata is read and used for the policy. This metadata is stored along with the data object. For each SLA, application element data will only be read once during a lightweight snapshot operation, and preparatory operations such as clearing the cache that occur at that time will only be performed once during a lightweight snapshot operation, even if this copy of the application data Together with its metadata, it can be used in several data management functions.

Service Policy Engine

FIG. 9 shows service policy engine 406 . The service policy engine includes a service policy scheduler 902 that examines all service level agreements configured by the user and makes scheduling decisions to satisfy the service level agreements. It relies on several data repositories to capture the information and make it persistent over time, the data repositories include in some embodiments: the SLA repository 904, where configured service level agreements are persisted and updated; Configuration file repository 906, which stores resource configuration files that provide a mapping between logical storage pool names and actual storage facilities; protection directory repository 908, which stores information about previous successful copies created in various facilities that have not yet expired and cataloging information; and a centralized historian database 910 .

History repository 910 is for use with all data management applications to hold historical information about past actions, including timestamps, order and hierarchy of previous copies of each application to various storage tools. For example, a snapshot copy from the primary storage database to the capacity optimized datastore initiated at 1pm and scheduled to expire at 9pm would be recorded in the history store 910 in the temporary datastore, the temporary datastore The repository also includes linked object data for snapshots of the same source and target that occurred at 11:00 am and 12:00 noon.

These repositories are managed by the service policy engine. For example, when a user creates a service level agreement or modifies one of the policies within it through an administrative workstation, it is the service policy that persists the new SLA in its repository and reacts to this modification by scheduling a copy as indicated by the SLA engine. Similarly, when the service policy engine successfully completes a data movement job that results in a new copy of the application in the storage pool, the storage policy engine updates the history store so that the copy will be factored into future decisions.

A preferred embodiment of the various repositories used by the service policy engine is in the form of tables in a redundant database management system in close proximity to the service policy engine. This ensures consistent business semantics when querying and updating the repository, and allows flexibility in retrieving interdependent data.

The scheduling algorithm of the service policy scheduler 902 is shown in FIG. 10 . When the service policy scheduler decides that it needs to make a copy of application data from one storage pool to another, it initiates the data movement requester and monitor task 912 . These tasks are not recurring tasks and are terminated after they complete. Depending on how the service level policy is specified, many of these requestors are operating concurrently.

The service policy scheduler takes into account the priorities of the service level agreements when determining which additional tasks to undertake. For example, if one SLA has a high priority because it specifies protection for a mission-critical application, and another SLA has a lower priority because it specifies protection for a test database, the service policy engine may choose to only Run protection for mission-critical applications and defer or even skip protection for lower-priority applications altogether. This is accomplished by a service policy engine that schedules higher priority SLAs ahead of lower priority SLAs. In a preferred embodiment, in such cases, the service policy engine will also trigger a notification event to the management workstation for inspection purposes.

Policy Scheduling Algorithm

Figure 10 shows a flow diagram of the Policy Scheduling Engine. The Policy Scheduling Engine continuously cycles through all SLAs defined. When it reaches the end of all SLAs, it sleeps for a while, say 10 seconds, and restarts browsing the SLAs again. Each SLA encapsulates the data protection business requirements for an application, so all SLAs represent all applications.

For each SLA, the scheduling engine 1000 collects together all service level policies that have the same process state for the source and destination pools 1004 and repeats at 1002 for the next SLA in the set of SLAs. This subset of service level policies collectively represent all requirements for copying from this source storage pool to this particular destination storage pool.

Of this subset of service level policies, the Service Policy Scheduler discards policies that are not applicable today or outside of their operating hours. Among the strategies left, the strategy with the shortest frequency is found (1006), and based on the historical data and in the historical repository 910, the strategy with the longest retention that needs to be run next (1008) is found.

Next, there is a series of checks 1010-1014 which at this point prevent making a new copy of the application data because the new copy has not yet expired, because a copy is already in progress or because there is no new data to copy. If any of these conditions apply, the service policy scheduler moves to the new combination of source and destination pools 1004 . If none of these conditions apply, a new copy is initiated. Copying is performed as specified in the corresponding service level policy within this SLA 1016.

Next, the scheduler moves to the next source and destination pool combination of the same service level agreement 1018 . If there are no more different combinations, the scheduler moves on to the next service level agreement 1020 .

After the service policy scheduler goes through all source/destination pool combinations for all service level agreements, it pauses for a short period of time and then restarts the cycle.

A simple example system with a snapshot repository and a backup repository (only 2 policies defined) would interact with the service policy scheduler as follows. Given two policies, one stating "Backup every hour, the backup will be kept for 4 hours" and the other stating "Backup every 2 hours, the backup will be kept for 8 hours", the result will be a single snapshot taken every hour, every A snapshot is copied to the backup repository, but is retained for a different amount of time in the snapshot repository and the backup repository. The "backup every 2 hours" policy is scheduled to be enforced by the system administrator at 12 noon.

At 4 PM, when the service policy scheduler starts operating at step 1000, it finds two policies at step 1002. (Both strategies work because multiples of two hours have elapsed since 12 noon). At step 1004 there is only one source and destination pool combination. At step 1006 there are two frequencies, and the system chooses the 1 hour frequency because it is shorter than the 2 hour frequency. At step 1008 there are two operations with different retention periods, and the system selects the operation with an 8-hour retention period because it has the longer retention value. Instead of making one copy to meet the 4 hour requirement and another copy to meet the 8 hour requirement, both requirements are combined into the longer 8 hour requirement and satisfied by a single snapshot copy operation. The system determines that the copy is expired at step 1010, and checks the relevant objects at the history store 910 to determine whether a copy has already been made at the target (at step 912) and at the source (at step 914). If these checks pass, the system initiates a copy at step 916, and in the process triggers a snapshot to be made and saved in the snapshot repository. The snapshots are then copied from the snapshot repository to the backup repository. The system then sleeps (1022) and wakes up again after a short period of time, eg 10 seconds. The result is a copy at the backup repository and a copy at the snapshot repository, where each even-hour snapshot lasts 8 hours and each odd-hour snapshot lasts 4 hours. Even-hour snapshots in both the backup repository and the snapshot repository are tagged with an 8-hour retention period and will be automatically detected from the system through another process at this time.

Note that there is no reason to take two snapshots or make two backup copies at 2, even though both policies would apply, since both policies are satisfied by a single copy. Combining and merging these snapshots results in a reduction of unnecessary operations while maintaining the flexibility of multiple individual policies. It can also be helpful for two policies that have simultaneous activity on the same target with multiple retention periods. In the given example, there are more hourly copies than two-hour copies, resulting in greater granularity for restoring at a time closer to the present. For example, in the previous system, if at 7:30 pm the image was discovered from earlier in the afternoon, the backup would be available for each of the past four hours: 4, 5, 6, 7 pm. Two more backups will be kept from 2pm and 12pm.

Content Addressable Repository

FIG. 11 is a block diagram of modules implementing a content-addressable repository of a content-addressable provider 510 .

The implementation of the content addressable storage library 510 provides a pool of storage resources optimized for capacity rather than for copy-in or copy-out speed, as will be the case with the performance-optimized pools implemented in snapshots described earlier, and thus generally For offline backup, replication and remote backup. Content-addressable memory provides a way to store common subsets of different objects just once, where those common subsets can be of varying sizes, but are typically as small as 4 kilobytes. Content-addressable repositories have low storage overhead compared to snapshot repositories, although access times are typically higher. Typically, objects in a content-addressable repository have no intrinsic relationship to each other, even though they may share most of their content, although in this implementation, historical relationships are also maintained, which is the result of various optimizations that will be described Launcher. This is in contrast to snapshot repositories where snapshots inherently form a chain, each storing only incremental or baseline copies from previous snapshots. In particular, a content-addressable repository will only store one copy of a subset of data that is repeated many times within a single object, while a snapshot-based repository will store at least one copy of any object.

The content addressable store 510 is a software module executing on the same system as the pool manager via a local transport such as TCP, in the same process or in a separate process. In this embodiment, the content addressable memory modules run in separate processes in order to minimize the impact of software failures from different components.

The purpose of this module is to allow storage of data storage objects 403 in a highly space-efficient manner by duplicating content (ie, ensuring that duplicate content within a single or multiple data objects is only stored once).

The content addressable storage module provides services to the pool manager via a programmable API. These services include the following:

Objects of Process Map 1102: Objects can be created by writing data into the repository via the API; once the data is fully written, the API will return an object handle determined by the object's content. Instead, data can be read from an offset within the object as a stream of bytes by providing a handle. Details of how to construct the handle are explained with reference to the description of FIG. 12 .

Time tree management 1104 tracks parent/child relationships between stored data objects. When a data object is written to the repository 510, the API allows it to be linked as a child to a parent object already in the repository. This indicates to the content addressable store that the child object is a modification of the parent object. A single parent may have multiple children with different modifications, as may be the case, for example, if the application's data is regularly saved to the repository for a while; the earlier copy is then restored and used as a new starting point for subsequent Modifications. The time tree management operations and data model are described in more detail below.

Difference engine 1106 can generate an overview of the regions of difference between two arbitrary objects in the repository. The diff operation is invoked via an API specifying the handles of the two objects to be compared, and the diff summation is in the form of a series of callbacks with offsets and successive diff part sizes. Computes differences by comparing two hash representations of objects in parallel.

Garbage collector 1108 is a service that analyzes the repository to find held data that is not referenced by any object handles and reclaims the storage space committed to that data. The nature of content-addressable repositories is that much data is referenced by multiple object handles, i.e., data is shared among data objects; some data will be referenced by a single object handle; but no data referenced by object handles (as may is the case if the object handle is deleted from the content addressable system) can be safely overwritten by new data.

Object Replicator 1110 is a service that replicates data objects between two different content addressable repositories. Multiple content addressable repositories can be used to meet additional business requirements, such as offline backup or remote backup.

These services are implemented using the functional modules shown in Figure 11. The data hash module 1112 generates fixed length keys for data blocks up to a fixed size limit. For example, in this embodiment, the maximum size of a block for which the hash generator will generate keys is 64KiB. Fixed-length keys are hashes that are tagged to indicate the hashing scheme or lossless algorithm encoding used. The hashing scheme used in this example is SHA-1, which produces secure cryptographic hashes with a uniform distribution and a probability of hash collision close enough to zero that no facilities need to be incorporated into the system to detect and handle collisions .

Data handle cache 1114 is a software module that manages an in-memory database that provides transient storage of data and handle-to-data mappings.

The persistent handle management index 1104 is a reliable persistent database of CAH-to-data mappings. In this embodiment, it is implemented as a B-tree, mapping a hash from a hash generator to a page in the persistent data store 1118 containing the data for this hash. Because the full B-tree cannot be kept in memory at once, this embodiment also uses an in-memory evolution filter for efficiency to avoid expensive B-tree searches for hashes that are not known to exist.

The persistent data storage module 1118 stores data and handles to long-term persistent storage, returning a token indicating where the data is stored. The handle/token pair is then used to retrieve the data. When data is written to persistent storage, it passes through a layer of lossless data compression 1120 implemented using zlib in this embodiment and an optional layer of reversible encryption 1122 not enabled in this embodiment.

For example, copying a data object into a content addressable store is an operation provided by the object/handle mapper service, since incoming objects will be stored and handles will be returned to the requester. The object/handle mapper reads incoming objects, requests hashes produced by the data hash generator, stores data to persistent data storage and handles to persistent handle management indexes. The data processing cache remains updated for future fast lookups of the handle's data. Data stored to persistent data storage is compressed and (optionally) encrypted before being written to disk. Typically, a request for a copy in a data object will also invoke a time tree management service to generate the object's history, and this is persisted via persistent data storage.

As another example, copying a data object from a content-addressable repository to which a handle is given is another operation provided by the object/handle mapper service. The handle is looked up in the data handle cache to locate the corresponding data; if the data is lost in the cache, a persistent index is used; decompressed disk data) are retrieved and then redistributed back to the requester.

Content addressable repository handle

Figure 12 shows how handles to content addressable objects are generated. The data object manager references all content-addressable objects that have a content-addressable handle. This handle consists of three parts. The first part 1201 is the size of the primitive data object directly pointed to by the handle. The second part 1202 is the depth of the object it points to. The third 1203 is the hash of the object it points to. Field 1203 optionally includes a tag indicating that the hash is a lossless encoding of the underlying data. The tag indicates the encoding scheme used, such as a form of run-length encoding (RLE) used for algorithmically encoded data, if the block of data can be adequately represented as a short-length RLE. If the underlying data object is too large to be represented as a lossless encoding, then a mapping from hashes to pointers or references to the data is stored separately in the persistent handle management index 1104 .

Content addressable objects are divided into blocks 1204 . The size of each block must be addressable by a content addressable handle 1205 . The data is hashed by the data hashing module 1102, and the block's hash is used to generate a handle. If the object's data fits together in a block, the handle created is the final handle to the object. If not, the handles themselves are grouped together into blocks 1206, and a hash is generated for each group of handles. This grouping of handles continues (1207) until there is only one resulting handle 1208, which is then the object's handle.

When the object is to be recreated from the content handle (copy out operation of the storage resource pool), the top level content handle is dereferenced to get the list of the next level content handles. These are in turn dereferenced to get additional lists of content handles, until a depth 0 handle is obtained. These extend to data by looking up handles in managed indexes or caches, or (in the case of algorithmic hashes such as run-length programming) deterministically extend to full content.

time tree management

Figure 13 shows the temporal tree relationships created for data objects stored in a content addressable repository. This particular data structure is only utilized within content-addressable repositories. The time tree management module maintains a data structure 1302 in persistent storage that relates each content-addressed data object to a parent (which may be zero, so as to be first in the modification sequence). Individual nodes of the tree contain a single hash value. This hash value refers to a block of data - if the hash is a depth 0 hash, or a list of other hashes - if the hash is a depth 1 or higher hash. References mapped to hash values are included in the persistent handle management index 1104 . In some embodiments, the edges of the tree may have weights or lengths, which may be used in algorithms to find neighbors.

This is a standard tree structure, and the module supports standard manipulation operations, in particular: 1310 add: add a leaf below the parent, which results in a change to the tree between the initial state 1302 and the added state 1304; and 1312 remove: A node is removed (and its children are reparented by their parents), which results in a change in the tree between the added state 1304 and the removed state 1306 .

The "add" operation is used whenever an object is copied into the CAS from an external pool. If copy-in is via the best way for data backup, or if the object originates from a different CAS pool, then the predecessor object needs to be specified and the add operation called to record this predecessor/descendant relationship.

The "remove" operation is invoked by the object manager when the policy manager determines that the object's retention period has expired. This can result in data stored in the CAS having no objects in the time tree that references it, and thus a subsequent garbage collection pass can free that data for reuse for reuse.

Note that a single predecessor may have multiple descendants or child nodes. This may occur, for example, if an object was originally created at time T1 and modified at time T2, the modification is re-executed via a restore operation, and the subsequent modification is made at time T3. In this example, state T1 has two children, state T2 and state T3.

Different CAS pools can be used to achieve different business goals, such as providing disaster recovery at remote locations. When copying from one CAS to another, the copy can be sent as a hash and offset to take advantage of the target CAS's native deduplication capabilities. The base data pointed to by any new hash is also sent on an as-needed basis.

Time tree structures are read or managed to traverse as part of the implementation of various services:

• Garbage collection tries to traverse the tree in order to reduce the cost of the "marking" phase, as described below.

• Replication to different CAS pools finds a set of neighbors in the temporal tree that are also known to have been transmitted to other CSA pools, so that only a small set of differences needs to be additionally transmitted.

• The best way for data recovery uses time trees to find predecessors that can be used as a basis for recovery operations. In the CAS time tree data structure, children are subsequent versions, eg, as dictated by the archive policy. Multiple children are supported on the same parent; this can happen when the parent changes, is then used as the basis for recovery, and then changes again.

CAS difference engine

The CAS difference engine 1106 compares two objects as identified by hashes or handles in FIGS. 11 and 12 and generates a sequence of offsets and ranges within the objects where the object data is known to differ. This sequence is implemented by traversing two object trees in parallel in the hash data structure of FIG. 12 . Tree traversal is standard depth or breadth first traversal. During traversal, compare the hashes at the current depth. Where the hash of a node is the same between both sides, there is no need to go further down the tree, so the traversal can be shortened. If the hashes of the nodes are not the same, traversal continues descending to the next lowest level of the tree. If traversal reaches a depth-0 hash that is not identical to its counterpart, the absolute offset within the data object being compared (where the non-identical data occurs along with the data length) is emitted into the output sequence. If one object is smaller in size than the other, its traversal will complete earlier, and all subsequent offsets encountered in traversals of other trees are emitted as differences.

Differentiated Garbage Collection

As described below in Figure 11, the Garbage Collector is a service that analyzes a particular CAS repository to find saved data referenced by any object handles in the CAS repository time data structure, and reclaims the objects committed to that data. storage. Garbage collection uses the standard "mark and sweep" method. Because the "marking" phase can be quite expensive, the algorithm used for the marking phase tries to minimize marking the same data multiple times, even though it can be referenced many times; however, the marking phase must be complete, ensuring that no referenced data is kept Unmarked as this will result in loss of data from the repository as unmarked data after the scan phase will be overwritten by new data later.

The algorithm for labeling the referenced data uses the fact that objects in the CAS are arranged in a curve with a time relationship using the data structure depicted in FIG. 13 . Objects sharing edges in these curves may only differ in a small subset of their data, and it is also rare that any new chunk of data that arises when an object is created from a predecessor should reappear between any two other objects. Thus, the marking phase of garbage collection processes each connected component of the time curve.

Figure 14 is an example of garbage collection using temporal relationships in some embodiments. A depth-first search of the data structure containing temporal relationships is performed, represented by arrow 1402 . A start node 1404 is taken, from which the tree traversal begins. Node 1404 is the root of the tree and has no referenced objects. Node 1406 contains references to objects _H1 and _H2 , representing the hash value of object 1 and the hash value of object 2. All data objects of depth 0, depth 1 and higher that are referenced by node 1406 (here _H1 and _H2 ) are enumerated and marked as referenced.

Next, node 1408 is processed. When it shares an edge with the marked node 1406, the difference engine is applied to the difference between the object referenced by 1406 and the object referenced by 1408, resulting in a set of depths that exist in unmarked objects but not in marked objects 0, depth 1 and higher hashes. In the figure, the hash that exists in node 1408 but not in node 1406 is _H3 , so _H3 is marked as referenced. This process continues until all edges are exhausted.

A comparison of the results produced by the prior art algorithm 1418 and _the present example 1420 shows that when node 1408 is processed by the prior art algorithm, previously seen hashes _H1 and _H2 are sent to in the output stream. This embodiment 1420 does not emit previously seen hashes into the output stream, resulting in only new hashes _H3 , _H4 , _H5 , _H6 , _H7 being emitted into the output stream, with a performance penalty Corresponding improvement. Note that this method does not guarantee that data will not be marked more than once. For example, if hash value _H4 independently occurs in node 1416, it will be independently marked a second time.

Copy the object to CAS

Copying an object from another pool into the CAS uses the software modules described in FIG. 11 to generate data structures referenced by object handles as in FIG. 12 . The input to the process is (a) a sequence of data blocks at specified offsets, sized appropriately so as to generate a depth 0 handle, and optionally (b) a previous version of the same object. Implicitly, the new object will be the same as the previous version, except where the input data is provided and itself is different from the previous version. The algorithm for the copy-in operation is shown in the flowchart of FIG. 15 .

Sequence (a) may be a sparse set of changes from (b) if a previous version (b) is provided. Where the object to be copied is known to differ from the previous object at only a few points, this can greatly reduce the amount of data that needs to be copied in, and thus reduce the computation and i/o activity required. This is eg the case when objects are copied in via the previously described optimal means of data backup.

Even if the sequence (a) includes parts that are largely unchanged from the predecessor, identifying the predecessor (b) allows the copy-in process to perform a quick check that the data has indeed changed, and thus avoids using the The difference engine in the pool may replicate data at a finer granularity level.

Then implicitly, the new object will be the same as the previous version, except where the input data is provided and itself is different from the previous version. The algorithm for the copy-in operation is shown in the flowchart of FIG. 15 .

The process begins at step 1500 when a data object of any size in temporary storage is provided, and proceeds to 1502, which enumerates any and all hashes (depth 0 to highest level), if such a hash is provided. This will be used as a quick check to avoid storing data already contained in predecessors.

At step 1504, if a predecessor is entered, a reference to its clone in the content addressable data store temporal data structure is created. The clone will be updated to become the new object. Thus, the new object will become a copy of the predecessor modified by the difference copied from the copy source pool into the CAS.

In steps 1506, 1508, the data mover 502 pushes the data into the CAS. The data is accompanied by an object reference and an offset, which is the target location of the data. Data can be sparse, since only differences from predecessors need to be moved into new objects. At this point, incoming data is divided into depth-0 blocks of a size small enough that each block can be represented by a single depth-0 hash.

At step 1510, the data hashing module generates a hash (hash) for each depth-0 block.

At step 1512, the predecessor hash at the same offset is read. If the hash of the data at the same offset matches the hash of the predecessor, then no data needs to be stored, and depth 1 and higher objects need not be updated for this depth 0 block. In this case, return to accept the next depth 0 block of data. This enables temporary de-duplication without expensive global lookups. Even if the source system ideally sends only differences from data previously stored in the CAS, this check may be necessary if the source system is performing diffs at a different level of granularity, or if data is marked as changed but changed back to its previously stored value. Differentiation can be performed at different levels of granularity, if for example the source system is a snapshot pool that creates deltas on 32KiB boundaries, and the CAS repository creates hashes on 4KiB blocks.

If a match is not found, the data can be hashed and stored. Once the new data is exhausted, the data is written, starting and ending at the previous offset. Once the data is stored, at step 1516, if the offset is still contained in the same depth 1 object, depth 1, depth 2, and all higher objects are updated 1518, generating new hashes at each level, and depth 0 , depth 1 and all higher objects are stored to local cache at step 1514 .

However, at step 1520, if the amount of data to be stored exceeds the depth 1 block size and the offset is to be contained in a new depth 1 object, then the current depth 1 must be cleared to the store unless it is determined to have been stored over there. Check it out at Global Index 1116 first. If it is found to be there, then depth 1 and all related depth 0 objects are removed from the local cache, and a new block 1522 is continued.

At step 1524 , as a quick check to avoid browsing the global index, for each depth 0, depth 1 and higher object in the local cache, its hash is looked up in the local repository established in 1502 . Anything that matches is discarded.

In step 1526. For each depth 0, depth 1 and higher object in the local cache, its hash is looked up in the global index 1116 . Anything that matches is discarded. This ensures that data is de-duplicated globally.

At Step 1528: Store all remaining content from local cache into persistent storage, then continue processing new blocks.

Reading objects from CAS is a relatively simple process and is common in many implementations of CAS. The object's handle is mapped to the persistent data object via the global index, and the required offset is read from within the persistent data. In some cases several deep recursions through the object handle tree may be necessary.

CAS object network replication

As described under FIG. 11 , replicator 1110 is a service that replicates data objects between two different content addressable repositories. Replication can be done by reading from one repository and writing back to another, but this architecture allows for more efficient replication over limited-bandwidth connections such as local or wide area networks.

The replication system operating on each CAS repository uses the difference engine service described above together with the temporal relational structure as described in Figure 13, and additionally stores on a per object basis in the temporal data structure used by the CAS repository A record of which remote repository the object has been copied to. This provides explicit knowledge of the existence of objects at a certain data repository.

Using temporal data structures, it is possible for the system to determine which objects exist on which data repositories. This information is utilized by the data mover and difference engine to determine the smallest subset of data to send over the network during the copy operation to bring the target data store up to date. For example, if data object O has been copied from a server in Boston to a remote server in Seattle at time T3, protection catalog store 908 will store object O that existed in both Boston and Seattle at time T3. At time T5, during the subsequent copy from Boston to Seattle, the temporal data structure will be consulted to determine the previous state of object O in Seattle that should be used for differentiation on the origin server in Boston. The Boston server will then take the difference between T5 and T3 and send that difference to the Seattle server.

The process of copying object A is then as follows: Identify object A0 that is recorded as having been copied to the target repository and A's neighbors in the local repository. If no such object A0 exists, A is sent to the remote repository, and it is recorded locally as sent. To send a local object to a remote repository, the general approach as embodied here is: send all hashes and offsets of the data blocks within the object; query the remote repository as to which hashes represent data that does not exist remotely; Send the required data to the remote repository (sending the data and hash is achieved in this example by encapsulating them in a TCP data stream).

Conversely, if A0 is identified, run the difference engine to identify data blocks that are in A but not in A0. This should be a superset of the data that needs to be sent to the remote repository. Send hashes and offsets of blocks that are in A but not in A0. Query the remote repository about which hashes represent data that does not exist remotely; send the required data to the remote repository.

Sample Deployment Architecture

Figure 16 illustrates the software and hardware components of one embodiment comprising a data management virtualization (DMV) system. The software comprising the system executes as three distributed components:

Host agent software 1602a, 1602b, 1602c implement some of the application specific modules described above. It executes on the same server 1610a, 1610b, 1610c as the application whose data is managed.

DMV server software 1604a, 1604b implements the remainder of the system as described herein. It runs on a set of Linux servers 1612, 1614 that also provide highly available virtualized storage services.

The system is controlled by management client software 1606 running on a desktop or laptop computer 1620 .

These software components communicate with each other via a network connection over the IP network 1628 . Data management virtualization systems communicate with each other between primary site 1622 and data replication (DR) site 1624 over an IP network (eg, the backbone of the public Internet).

The DMV systems at the primary and DR sites access one or more SAN storage systems 1616 , 1618 via Fiber Channel network 1626 . Servers running host applications access storage virtualized by the DMV system via Fiber Channel over Fiber Channel networks or iSCSI over IP networks. The DMV system at the remote DR site runs a parallel instance of the DMV server software 1604c on a Linux server 1628. Linux server 1628 may also be an Amazon Web Services EC2 instance or other similar cloud computing resource.

Figure 17 is a diagram depicting various components of a computerized system on which certain elements may be implemented, according to some embodiments of the present invention. The logic modules can be implemented on a host computer 1701 including volatile memory 1702 , persistent storage (eg, hard drive 1708 ), processor 1703 and network interface 1704 . Using a network interface, the system computer can interact with the storage pools 1705, 1706 through SAN or Fiber Channel devices, among other embodiments. Although FIG. 17 shows a system in which the system computer is separate from the various storage pools, some or all of the storage pools may be housed within the host computer, thereby eliminating the need for a network interface. Programming processes can be performed on a single host as shown in Figure 17, or they can be distributed among multiple hosts.

The host computer shown in Figure 17 may be used as a management workstation, or may implement applications and application specific agents 402, or may implement any and all of the logic modules described in this specification, including the data virtualization system itself, or may be used as a Storage pools of physical media are exposed to the system's storage controller. A workstation may be connected to a graphics display device 1707 and input devices such as mouse 1709 and keyboard 1710 . Alternatively, the active user's workstation may include a handheld device.

Throughout this specification we refer to software components, but references to software components are intended to apply to software running on hardware. References to objects and data structures in this specification are intended to apply to data structures that are actually stored in memory, volatile or non-volatile. Likewise, servers are contemplated for software and engines are contemplated for software, both running on hardware such as the computer system described in FIG. 17 .

The foregoing outlines some of the more relevant features of the subject. These features should be construed as merely illustrative. Many other beneficial results can be obtained by applying the disclosed subject matter in a different manner or by modifying the subject matter as will be described. For example, the disclosed garbage collection algorithms may incorporate other garbage collection optimization techniques such as three-color marking.

Claims (49)

1. one kind for to reduce the system of the mode of the redundant access operation of primary memory being carried out to the data management function of a plurality of regulations, and described system comprises:

Data management engine, it is for the executing data management function, comprise the video snapshot functions of external memory of the time point that can operate at least to create main memory data, and at least one backup functionality that can operate to create at least one backup copy of data, described data management engine is in response to the electronic service level agreements (SLA) of the plan that is given for the executing data management function

Wherein the time point of data reflection comprises the quoting of the variance data of the change to described data of the baseline full reflection of the data at particular point in time and indication particular point in time afterwards, and

Wherein, the described plan be performed simultaneously in response at least some data management functions of needs, described data management engine creates the time point reflection of described main memory data, and the different information of this time point reflection is delivered to described external memory with at least one in the backup copy that upgrades described master data, make for the described primary memory of all corresponding renewal set to described external memory only once accessed.

2. the system as claimed in claim 1, wherein the described time point reflection at the main memory data at external memory place is stored on the external memory of performance optimization.

3. the system as claimed in claim 1, wherein the described backup copy of the described time point reflection of main memory data is stored on remote memory.

4. the system as claimed in claim 1, wherein the described backup copy of the described time point reflection of main memory data is stored in the storer place that capacity is optimized.

5. system as claimed in claim 4, on the storer that wherein the reflection capacity that is stored in that copies as releasing of the described backup copy of the described time point reflection of main memory data is optimized.

6. the system as claimed in claim 1, wherein variance data comprises message bit pattern, each of described bitmap part corresponding to main memory data, and comprise the new data of those parts that are provided to the described bitmap that designation data changed.

7. the system as claimed in claim 1, wherein variance data comprises range information.

8. the system as claimed in claim 1, wherein said data management engine comprise calling described primary memory with the logic of time point reflection that data are provided and comprise from the logic of the described time point reflection of described primary memory retrieval.

9. one kind for the data management function coming the system of management data, described service level agreement to be given on the calendar basis to put rules into practice according to service level agreement (SLA) and be used to reducing the plan of redundancy between function, and described system comprises:

Data management engine, it is for the executing data management function, comprise at least one snapshot functions and at least one backup functionality, described data management engine comprises the service level policy engine, described service level policy engine receives the SLA with electronic form, and control the scheduling of described data management function according to it

Wherein each electronics SLA is relevant to the respective application of usage data, and wherein each SLA stipulates at least one service level strategy, the pond, source of each tactful specified data, should make therein the pond, destination of copy of the data in pond, described source, indicate the copy frequency of frequency of the operation of this strategy, indicate given copy before being allowed to expire, should be retained retention period how long and indication when described strategy is ready operation hour with the plan information of number of days, make the set of the strategy in SLA can mean for when carrying out the incomparable inconsistent plan of given function and can mean to tackle a plurality of data management functions that carry out in the given source of data, and

Wherein said data management engine can operate to use described application and use pond, described source to carry out preparatory function, the relevant reflection that makes the pond, described source of data have data to be copied, and wherein said preparatory function is performed once, even a plurality of data management functions that described SLA regulation will be carried out this pond, source in the current time.

10. system as claimed in claim 9, if wherein two or more copy functions are scheduled to occur in the synchronization between pond, Chi He destination, same source, in described two or more copy functions only one by described data management engine, carried out, and should copy relevant to the maximum retention time of copy function corresponding to described two or more scheduling.

11. system as claimed in claim 9, wherein preparatory function comprises that described data management engine collects metadata about described application in conjunction with application data, to store.

12. system as claimed in claim 9, wherein preparatory function comprises the static operation of application.

13. system as claimed in claim 12, the static operation of wherein said application comprise, freeze described application and further do not upgrade application data.

14. system as claimed in claim 12, the static operation of wherein said application comprises the I/O cache memory of the application server of removing application data.

15. one kind for using different information between time state by the system of data from the first storage pool backup to the second storage pool, described system comprises:

Data management engine, it is for the executing data management function, comprises creating at least one backup functionality of the backup copy of data,

Described data management engine can operate to carry out the snapshot operation of a sequence on the first storage pool, to create the time point reflection of application data, each continuous time point reflection is corresponding to specific continuous time of the state of described application data, and each snapshot operation creates, and which application data of indication has changed and the different information of the content of the application data changed of corresponding time state;

Described data management engine can operate carries out at least one backup functionality to described application data, and wherein said backup operation is scheduled at discrete time state and carries out,

Wherein said data management engine can operate to maintain the historical information with time state information, and described time state information is indicated the time state of the upper backup functionality that described application data is carried out for the respective backup copy of data; And

Wherein said data management engine can operate come for described application data is carried out described on each time state between the time state of time state and the backup functionality of the current scheduling that will carry out described application data of a backup functionality from the compound different information of described different information establishment, and wherein said data management engine can operate described compound different information is sent to the second storage pool compiles to create the data of described current time state together with the backup copy of the data with a time state on described backup copy.

16. system as claimed in claim 15, wherein different information comprises message bit pattern, each of described bitmap part corresponding to main memory data, and comprise the new data of those parts that are provided to the described bitmap that designation data changed.

17. system as claimed in claim 15, wherein different information comprises range information.

18. system as claimed in claim 15, wherein a plurality of backup functionalitys are scheduled to occur simultaneously, each backup functionality has the different gap of discontinuous time state, and each backup functionality has the different composite different information produced corresponding to described different gap.

19. one kind is recovered the system of the data of storage pool for the different information of use between time state from the backup copy of data, described system comprises:

Data management engine, wherein said data management engine can operate to maintain the historical information of the described time state of indication, and for described time state, storage pool has the time point reflection of application data; And

Wherein said data management engine comprises the logic of time point reflection that returns to the described data of official hour state for the application data by storage pool;

Described data management engine can operate to identify the existence of the time point reflection of stating data for the time state before described official hour state in described storage pool place, and will send to described storage pool with the different information of the described backup copy of data, which application data described different information indicates changed and in the content of described official hour state and the application data changed of the time between the time state before described official hour state.

20. system as claimed in claim 19, wherein different information comprises message bit pattern, each of described bitmap part corresponding to main memory data, and comprise the Backup Data of those parts that are provided to the described bitmap that designation data changed.

21. system as claimed in claim 19, wherein different information comprises range information.

22. system as claimed in claim 19, wherein said time state and described official hour state in the past is discrete time state.

23. the different information of a use between the time state of data object forms the method for the reflection that the releasing of the described data object changed along with the time copies, described method comprises:

By the Content Organizing of the described data object of very first time state, be a plurality of inclusive segments and described inclusive segment is stored in data repository;

Create the layout of organizing of Hash structure to be illustrated in the described data object in its very first time state, wherein for the subset of described Hash structure, each structure comprises the hash signature of corresponding inclusive segment and to relevant to quoting of corresponding inclusive segment, and the logical organization of wherein said layout means the tissue as the described inclusive segment of described inclusive segment being expressed in described data object;

Receive the different information of described data object, described different information indication is with respect to the content changed of the described data object of the second time state of described very first time state, and the position of described different information indication described content changed in described data object;

Form at least one hash signature of the described content changed;

The described content changed that will be unique in described data repository is stored as inclusive segment;

The layout of organizing of revising the Hash structure is with the new construction of described at least one hash signature of merging the described content changed, with as described in indicate in different information as described in the content that changed as described in merge in the layout of organizing of corresponding position, position in structure in data object as described in new construction, and make the hash signature of described new construction relevant to quoting of corresponding inclusive segment to the described content changed; And

Make described new construction relevant to described the second time state, thus, the reflection that the releasing of the described data object of the second time state copies is stored, and does not need to receive the full image of the described data object of described the second time state.

24. method as claimed in claim 23, wherein after forming described at least one hash signature of the described content changed, by least one the hash signature comparison in the layout of organizing of formed signature and Hash structure with in the layout of determining formed structure and whether Already in being organized.

25. method as claimed in claim 23, wherein said at first with as described in indicate in different information as described in occur together with Hash structure in the layout of organizing of corresponding position, position of the content that changed.

26. method as claimed in claim 23, wherein the layout of organizing of Hash structure is the tree construction of tissue.

27. method as claimed in claim 23, wherein the layout of organizing of time structure is maintained, and each time structure is relevant to time state, and each time structure comprises the information of indication corresponding to the Hash structure of relevant time state.

28. the method for the reflection that the releasing of the data object that a management changed along with the time copies, described method comprises:

The unique content of each data object is organized as to a plurality of inclusive segments and described inclusive segment is stored in data repository;

For each data object, create the organized layout of Hash structure, wherein for the subset of described Hash structure, each structure comprises the hash signature of corresponding inclusive segment and to relevant to quoting of corresponding inclusive segment, the logical organization of wherein said layout means the logical organization as the described inclusive segment of described inclusive segment being expressed in described data object, and another subset of wherein said Hash structure comprises the level of hash signature of the described hash signature of corresponding inclusive segment, make the layout of organizing can be traversed to determine that whether content is meaned by the layout of the described tissue of Hash structure, and

For each data object, the layout of organizing of the structure of holding time is to mean the corresponding data object changed along with the time, wherein each structure is relevant to the time state of described data object, and wherein the logic arrangement of structure is indicated the time state of the change of described data object, and wherein each time state is relevant to the Hash structure of the content that means described data object during this time state.

29. method as claimed in claim 28, wherein preset time state data object described time structure to respect to described data object before the Hash structure of the data object content that changed of time state relevant.

30. method as claimed in claim 28, the described Hash structure of the wherein said data content changed are organized as the figure separated with the layout of organizing of the Hash structure of former time state.

31. method as claimed in claim 28, the difference wherein from a time state to the content of the data object of another time state layout of organizing of the time structure of another time state and the every other time state between described another time state and a described state by reference make difference to be determined to determine at a plurality of time states.

32. store the method for removing the reflection copied for one kind, the part of wherein said reflection directly is stored in Hash table with coding form, described method comprises:

The unique content of each data object is organized as to a plurality of inclusive segments and described inclusive segment is stored in data repository;

For each data object, create the organized layout of Hash structure, wherein for the subset of described Hash structure, each structure comprise comprising corresponding inclusive segment hash signature field and to relevant to quoting of corresponding inclusive segment, the logical organization of wherein said layout means the logical organization as the described inclusive segment of described inclusive segment being expressed in described data object;

Reception will be included in the content in the reflection that the releasing of described data object copies;

Whether definite content received can encode with predetermined lossless coding technique, and wherein encoded radio will be engaged in be used in the described field that comprises hash signature;

If so, coding is placed in described field, and the described Hash structure of mark is to indicate described field to comprise the encoded content of the reflection that described releasing copies;

If not, produce the hash signature of the content received, and described hash signature is placed in described field, and by the corresponding inclusive segment of Content placement in described data repository received, its prerequisite is that the content received is unique.

33. method as claimed in claim 32, wherein said lossless coding is run length encoding.

34. method as claimed in claim 32, wherein the hash signature of each data object creates by the SHA-1 keyed Hash function.

35. method as claimed in claim 32, it also comprises subsequently rebuilds described content from encoded content.

36. one kind for removing and to copy thesaurus and to mean that information that how data object changes along with the time upgrades second and remove the method that copies thesaurus with first, described method comprises:

First, remove and copy the thesaurus place, the unique content of each data object is organized as to a plurality of inclusive segments and described inclusive segment is stored in data repository;

First, remove and copy the thesaurus place, for each data object, create the organized layout of Hash structure, wherein for the subset of described Hash structure, each structure comprises the hash signature of corresponding inclusive segment and to relevant to quoting of corresponding inclusive segment, the logical organization of wherein said layout means the logical organization as the described inclusive segment of described inclusive segment being expressed in described data object;

First, remove and copy the thesaurus place, for each data object, the layout of organizing of the structure of holding time is to mean the corresponding data object changed along with the time, wherein each structure is relevant to the time state of described data object, and wherein the logic arrangement of structure is indicated the time state of the change of described data object, and wherein each time state is relevant to the Hash structure of the content that means the described data object changed with respect to former time state;

Second, remove and copy the thesaurus place, the unique content of each data object is organized as to a plurality of inclusive segments and described inclusive segment is stored in data repository;

Second, remove and copy the thesaurus place, for each data object, maintain the layout of organizing of Hash structure, namely in described the first releasing, copy at least one subset of the described Hash structure at thesaurus place;

Second, remove and copy the thesaurus place, for each data object, the layout of organizing of the structure of holding time is to mean the corresponding data object changed along with the time, wherein the layout of the described tissue of time structure is to remove at least one subset of the described time structure that copies the thesaurus place described first, thereby means the subset of described time state;

In response to using, from described first, remove the information updating that copies thesaurus described second and remove the request that copies thesaurus, find described first remove copy thesaurus and second remove copy thesaurus common and with described second remove the current state time state around that copies thesaurus; And

The hash signature group of the content that the current time state that compiling copies thesaurus from described common state to described the first releasing has changed, and described hash signature group is sent to described second remove and to copy thesaurus, so its layout organized that can upgrade its Hash structure to mean until described first remove the content of the described data object of the current time state that copies thesaurus.

37. method as claimed in claim 36, it also comprises and maintains the history that each releasing copies the described hash signature that thesaurus comprises, and to copy thesaurus be the hash signature in new described hash signature group for to described second, removing, send the corresponding inclusive segment that copies thesaurus from described the first releasing, making described the second releasing copy thesaurus can upgrade its data repository with fresh content.

38. method as claimed in claim 36 is wherein the arest neighbors state of described current state near the described second described time state of removing the described current state that copies thesaurus.

39. method as claimed in claim 36 is wherein ancestors' state of described current state near the described second described time state of removing the described current state that copies thesaurus.

40. method as claimed in claim 36 is wherein the sub-state of described current state near the described second described time state of removing the described current state that copies thesaurus.

41. method as claimed in claim 38, wherein said arest neighbors state are the states connected by one group of edge, described edge and lower than any other group edge and.

42. method as claimed in claim 36, wherein the described logic arrangement of structure comprises branch.

43. method as claimed in claim 37, it also is included in described current state record and has been sent to what state corresponding to the described inclusive segment of described current time state.

44. a method of carrying out the inclusive segment that refuse collection no longer copies to be cited in storage system in releasing with identification, wherein the operation of the redundant marks in mark and scanning technique is avoided, and described method comprises:

The unique content of each data object is organized as to a plurality of inclusive segments in described releasing copies storage system;

For each data object, create the organized layout of Hash structure, wherein for the subset of described Hash structure, each structure comprises the hash signature of corresponding inclusive segment and to relevant to quoting of corresponding inclusive segment, the logical organization of wherein said layout means the logical organization as the described inclusive segment of described inclusive segment being expressed in described data object, and another subset of wherein said Hash structure comprises the level of hash signature of the described hash signature of corresponding inclusive segment, make the layout of organizing can be traversed to determine that whether content is meaned by the layout of the described tissue of Hash structure,

For each data object, the layout of organizing of the structure of holding time is to mean the corresponding data object changed along with the time, wherein each structure is relevant to the time state of described data object, and the time state of the change of the described data object of the logic arrangement of structure indication wherein, and wherein the Hash structure of the content of the described data object that changed with respect to the previous time state of described data object of each time state and expression is relevant;

For described releasing, copy each inclusive segment in storage system, remove its corresponding refuse collection state;

Iteration on described time structure, and for each time structure, the described refuse collection state of the inclusive segment that the described inclusive segment mark only changed for the previous time state with respect to described data object is relevant; And

Any inclusive segment is turned back to the free core pool of the refuse collection state with removing after described iterative step.

45. method as claimed in claim 44, it also comprises use depth-first search iteration on described time structure.

46. method as claimed in claim 44, it also comprises with periodic intervals and repeats described method.

47. method as claimed in claim 44, it carries out described method after also being included in the new time state that adds data object.

48. method as claimed in claim 44, it carries out described method after also being included in the time state that removes data object.

49. method as claimed in claim 44, it also comprises and maintains the global reference list that described releasing copies all the elements section of having distributed in storage system.

Images