DATA ALLOCATION AND REPLICATION ACROSS DISTRIBUTED STORAGE SYSTEM

• US 20100115216A1
• Filed: 11/04/2008
• Published: 05/06/2010
• Est. Priority Date: 11/04/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jia, Hongzhong, Goldszmidt, Moises
• Granted Patent: US 8,380,960 B2
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/306 User profiles

Abstract

In a distributed storage system such as those in a data center or web based service, user characteristics and characteristics of the hardware such as storage size and storage throughput impact the capacity and performance of the system. In such systems, an allocation is a mapping from the user to the physical storage devices where data/information pertaining to the user will be stored. Policies regarding quality of service and reliability including replication of user data/information may be provided by the entity managing the system. A policy may define an objective function which quantifies the value of a given allocation. Maximizing the value of the allocation will optimize the objective function. This optimization may include the dynamics in terms of changes in patterns of user characteristics and the cost of moving data/information between the physical devices to satisfy a particular allocation.

Claims

1. A data allocation and replication method, comprising:

determining a plurality of characteristics of each user of a distributed storage system comprising a plurality of storage nodes, each user having data stored on the distributed storage system;

determining a plurality of characteristics of the distributed storage system;

determining an effect the characteristics of each user has on the characteristics of the distributed storage system;

determining a user assignment plan mapping each user to one of the storage nodes of the distributed storage system based on the effect the characteristics of each user has on the characteristics of the distributed storage system; and

moving the users and the data based on the user assignment plan.

2. The method of claim 1, further comprising forecasting a plurality of future characteristics of the users, wherein the user assignment plan is further based on the future characteristics of the users that are forecasted.

3. The method of claim 1, further comprising:

determining a current user distribution of the users on the distributed storage system; and

determining a user moving plan based on the current user distribution and the user assignment plan, wherein moving the users and the data is based on the user moving plan.

4. The method of claim 1, wherein the characteristics of each user comprise an account size, an account size growth rate, an average daily traffic generation, a dynamic daily traffic generation, and a registration date.

5. The method of claim 1, wherein the characteristics of the distributed storage system comprise a performance and a capacity of the each of the storage nodes of the distributed storage system.

6. The method of claim 1, further comprising:

obtaining an objective of the distributed storage system; and

determining a function directed to meeting the objective, wherein the user assignment plan is further based on the function directed to meeting the objective.

7. The method of claim 6, further comprising determining a plurality of constraints regarding the distributed storage system, wherein the function is further directed to meeting the constraints.

8. The method of claim 7, wherein the constraints comprise a quality of service policy and a replication of data policy.

9. The method of claim 6, further comprising performing clustering of the users into a plurality of clusters based on the effect the characteristics of each user has on the characteristics of the distributed storage system, the function based on the clusters.

10. The method of claim 6, wherein the objective comprises an objective to achieve a balanced disk input/output traffic processing capability and storage consumption across the storage nodes or an objective to achieve a predetermined disk input/output traffic processing capability and storage consumption across the storage nodes.

11. The method of claim 10, wherein the function comprises a summation of differences of disk input/output utilization and storage utilization among a plurality of pairs of the storage nodes.

12. The method of claim 1, wherein moving the users and the data comprises determining a minimum number of moves of the users and the data to balance the storage nodes and to achieve a balanced allocation of the users and the data.

13. A data allocation and replication system, comprising:

a characteristic analyzer and correlator that determines a plurality of characteristics of each user of a distributed storage system, a plurality of characteristics of the distributed storage system, and an effect the characteristics of each user has on the characteristics of the distributed storage system; and

a user allocation engine that determines a user assignment plan mapping each user to one of a plurality of storage nodes in the distributed storage system based on the effect the characteristics of each user has on the characteristics of the distributed storage system, and moves the users and data of the users based on the user assignment plan.

14. The system of claim 13, further comprising a characteristic forecaster that forecasts a plurality of future characteristics of the users, wherein the user assignment plan is further based on the future characteristics of the users.

15. The system of claim 13, further comprising an objective determiner that obtains an objective of the distributed storage system, the user assignment plan based on a function directed to meeting the objective.

16. The system of claim 15, further comprising a clustering engine that clusters the users into a plurality of clusters based on the effect the characteristics of each user has on the characteristics of the distributed storage system, the function based on the clusters.

17. The system of claim 15, wherein the objective comprises an objective to achieve a balanced disk input/output traffic processing capability and storage consumption across the storage nodes, and wherein the function comprises a summation of differences of disk input/output utilization and storage utilization among a plurality of pairs of the storage nodes.

18. A system comprising:

a distributed storage system comprising a plurality of storage nodes;

a web service comprising a plurality of users allocated among the storage nodes; and

an allocation and replication system in communication with the distributed system and the web service via a communications network, the allocation and replication system dynamically monitoring and balancing an allocation of the users across the storage nodes.

19. The system of claim 18, wherein the allocation and replication system comprises a data engine that determines a plurality of characteristics of each user and a plurality of characteristics of the distributed storage system, the allocation of the users being balanced based on the characteristics of each user and the characteristics of the distributed storage system.

20. The system of claim 19, wherein the characteristics of each user comprise at least one of an account size, an account size growth rate, an average daily traffic generation, a dynamic daily traffic generation pattern, or a registration date, and wherein the characteristics of the distributed storage system comprise at least one of a performance or a capacity of the distributed storage system.