Dynamic placement of replica data

• US 8,560,639 B2
• Filed: 04/24/2009
• Issued: 10/15/2013
• Est. Priority Date: 04/24/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Murphy, Elissa E. S., Leshinsky, Yan V., Mehr, John D.
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): SHAW, ROBERT A
• Application Number:
  US12/430,018
• Publication Number:
  US 20100274762A1
• Time in Patent Office: 1,635 Days
• Field of Search: 709/219
• US Class Current: 709/219
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

The claimed subject matter relates to systems and/or methodologies that facilitate distributed storage of data. A distributed file system can be implemented on storage nodes such that the system places multiple copies of data (e.g., replicas) on a variety of disparate storage nodes to guarantee availability of the data and minimize loss of the data. Storage nodes are dynamically evaluated to identify respective characteristics. In one example, the characteristics can include availability of a storage node, capacity of a storage node, data storage cost associated with a storage node, data transfer costs associated with a storage node, locality of a storage node, network topology, or user preferences associated with a storage node. The characteristics can be employed to generate optimal placements decisions.

Claims

1. A system that facilitates allocation of replicas among a set of storage nodes in a hybrid backup environment, the hybrid backup environment including one or more storage nodes located in a cloud storage location of a cloud backup environment, one or more storage nodes located in a peer-to-peer backup environment and one or more peers of the peer-to-peer backup environment, the system comprising:

a processor coupled to a memory that retains computer-executable instructions, wherein the processor executes;

(A) a replication component that;

identifies properties of a portion of data,

evaluates both the one or more storage nodes located in the cloud storage location of the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment to identify characteristics of the one or more storage nodes located in the cloud storage location of the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment,

wherein the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment are disjoint sets; and

wherein the one or more peers of the peer-to-peer backup environment consist of one or more devices and the cloud storage location is accessible to the one or more devices via a network, the cloud storage interacting with the one or more peers via the network, and

generates a replica requirement for the portion of data based at least in part on an analysis of (1) the identified properties of the portion of data and (2) the identified characteristics of both the one or more storage nodes located in the cloud storage location of the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment, the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets;

wherein the identified properties include the size of the portion of data and at least one of;

compressibility of the portion of data and reparability of the portion of data; and

(B) a placement component that;

generates a placement policy based, at least in part on (1) the identified characteristics of the one or more storage nodes located in the cloud storage location of the cloud backup environment and the identified characteristics of the one or more storage nodes located in the peer-to-peer backup environment, the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets, the identified characteristics including one or more of;

availability of a storage node, available storage capacity of the storage node, cost of storage corresponding to the storage node, cost of data transfer to or from the storage node, and network locality of the storage node relative to an origin node, and (2) user preferences, comprising (i) a weighting of;

each one of the identified characteristics of the one or more storage nodes located in the cloud storage location of the cloud backup environment and the identified characteristics of the one or more storage nodes located in the peer-to-peer backup environment used in generating the placement policy, the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets, and (ii) an identification of a preferred storage node; and

distributes one or more replicas of the portion of data among both the one or more storage nodes located in the cloud storage location of the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment of the hybrid backup environment, based on the replica requirement, the placement policy, the identified characteristics of the one or more storage nodes located in the cloud storage location of the cloud backup environment, and the identified characteristics of the one or more storage nodes located in the peer-to-peer backup environment, the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets,

(C) an observation component that monitors the one or more storage nodes located in the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment to identify changes in the characteristics thereof.

2. The system of claim 1, wherein the properties of the portion of data include compressibility of the portion of data.

3. The system of claim 1, wherein the properties of the portion of data include reparability of the portion of data.

4. The system of claim 1, wherein the properties of the portion of data further include licensing restrictions on the portion of data.

5. The system of claim 1, wherein the analysis of the identified properties of the portion of data and the identified characteristics of the one or more storage nodes located in the cloud storage location of the cloud backup environment and the identified characteristics of the one or more storage nodes located in the peer-to-peer backup environment employs statistical models based upon at least one of machine learning or heuristics.

6. The system of claim 1, wherein the placement policy specifies a ranking of storage nodes, and wherein the placement component gives priority to higher ranking storage nodes when distributing replicas.

7. The system of claim 1, wherein the placement component includes a cataloguing component that maintains an index listing relationships between replicas of the portion of data and storage nodes to which the replicas have been distributed, and wherein the placement component at least one of adds, deletes, or modifies entries in the index when replica distribution decisions are rendered by the placement component.

8. The system of claim 1, wherein the placement component dynamically adjusts distribution of replicas based upon monitor results continuously communicated by the observation component.

9. The system of claim 1, wherein the replication component utilizes one of the one or more user preferences to generate the replica requirement and the placement component utilizes one of the one or more user preferences to distribute replicas.

10. The system of claim 1, wherein the placement component distributes replicas through application of a higher level of preference on the one or more storage nodes located in the peer-to-peer backup environment than to the one or more storage nodes located in the cloud storage location of the cloud backup environment.

11. A method for replicating data across one or more storage locations in a hybrid backup environment, the hybrid backup environment including one or more storage nodes located in a cloud storage location of a cloud backup environment, one or more storage nodes located in a peer-to-peer backup environment and one or more peers of the peer-to-peer backup environment, the method comprising:

employing a processor executing computer-executable instructions stored on a computer-readable storage device that retains computer-executable instructions, to implement the following acts;

assigning characteristics to both the one or more storage nodes located in the cloud storage location of the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment, the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets;

wherein the one or more peers of the peer-to-peer backup environment consist of one or more devices and the cloud storage location is accessible to the one or more devices via a network;

identifying properties of a portion of data, wherein the identified properties include the size of the portion of data and at least one of;

compressibility of the portion of data and reparability of the portion of data,

specifying a replica requirement for the portion of data based at least in part on (1) an analysis of the identified properties of the portion of data and (2) the assigned characteristics of both the one or more storage nodes located in the cloud storage location of the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment, the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets;

generating a placement policy based, at least in part on (1) each one or the assigned characteristics of the one or more storage nodes located in the cloud storage location of the cloud backup environment and the identified characteristics of the one or more storage nodes located in the peer-to-peer backup environment, the one or more storage nodes located in the cloud storage location of the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets, and (2) a user preference,

the assigned characteristics including one or more of;

availability of a storage node, available storage capacity of the storage node, cost of storage corresponding to the storage node, cost of data transfer to or from the storage node, and network locality of the storage node relative to an origin node, and

wherein the user preference comprises (i) a weighting of each one of the assigned characteristics of both the one or more storage nodes located in the cloud storage location of the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment used in generating the placement policy, the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets, and (ii) an identification of a preferred storage node; and

placing one or more replicas of the portion of data on both the one of the one or more storage nodes located in the cloud storage location of the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment of the hybrid backup environment, based on the replica requirement, the placement policy, the assigned characteristics of the one or more storage nodes located in the cloud storage location of the cloud backup environment, and the assigned characteristics of the one or more storage nodes located in the peer-to-peer backup environment, the one or more storage nodes located in the cloud storage location and the one or more storage nodes located in the peer-to-peer backup environment being disjoint sets, wherein the cloud storage interacts with the one or more peers of the peer-to-peer backup environment, via the network, and

monitoring the one or more storage nodes located in the cloud backup environment and the one or more storage nodes located in the peer-to-peer backup environment to detect changes in the characteristics thereof and assigning the changed characteristics thereto.