Peer-to-peer auction based data distribution

• US 7,558,859 B2
• Filed: 10/17/2005
• Issued: 07/07/2009
• Est. Priority Date: 10/17/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jones, Ronald H. Jr., Kasiolas, Anastasios
• Primary Examiner(s): Backer; Firmin
• Assistant Examiner(s): Casaw; Tobias J
• Application Number:
  US11/252,002
• Publication Number:
  US 20070088703A1
• Time in Patent Office: 1,359 Days
• Field of Search: 709/226
• US Class Current: 709/226
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• 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 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• CPC Class Codes: H04L 51/42 Mailbox-related aspects, e.g. synchronisation of mailboxes
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A peer-to-peer auction based strategy balances the storage of data in a data center. Each cluster of the data center has a cluster manager and associated data storage nodes on which data is stored. The data storage nodes can periodically announce their respective utilization levels to other data storage nodes. If the announcing nodes are over capacity, the other nodes in the cluster respond by checking their utilization level and placing a bid if they are able to accept new data. Data is then relocated to one or more selected bidding nodes. If data cannot be balanced at the data storage node level, the cluster manager can identify nodes in other clusters that are able to accept new data. Multiple auctions for the same or different categories of data can be conducted at the same time by the data storage nodes and/or cluster managers.

Claims

1. A computer-implemented method for balancing a data load among a plurality of data storage nodes in at least one network, comprising:

determining, at a first data storage node of the plurality of data storage nodes, an amount of data subject to an auction to reduce an amount of data stored at the at least one utilization level of a first data storage node, the amount of data subject to the auction is determined based on an amount of data stored at the first data storage node;

multicasting, in the at least one network, information regarding the amount of data subject to the auction, the information indicating that the data subject to the auction includes data of relatively high activity user accounts and data of relatively low activity user accounts;

the information is received by other data storage nodes of the plurality of data storage nodes which have registered to receive multicast announcements from the first data storage node; and

in response to receipt of the information, each of the other data storage nodes checks an amount of data stored thereat to determine whether it has available capacity to accept new data, and communicates a bid to the first data storage node if it has the capacity to accept new data, the bid from at least one of the other data storages nodes indicates that at least one of data of the relatively high activity user accounts and data of the relatively low activity user accounts will be accepted by the at least one of the other data storages nodes, where the first data storage node accepts at least one bid and relocates data to one or more of the other data storage nodes whose bids were accepted.

2. The computer-implemented method of claim 1, wherein:

the first data storage node determines, at regular intervals, an amount of data subject to periodic auctions based on an amount of data stored at the first data storage node at the regular intervals; and

the first data storage node multicasts in the at least one network, at the regular intervals, information regarding the amount of data subject to the periodic auctions, the periodic auctions are conducted regardless of a level of the amount of data stored at the first data storage node at the regular intervals.

3. The computer-implemented method of claim 1, wherein:

the bid from the at least one of the other data storages nodes indicates an amount of data that the at least one of the other data storage nodes can accept.

4. The computer-implemented method of claim 1, wherein:

the determining the amount of data subject to the auction comprises determining a first amount of data subject to the auction for a first category of user accounts which are serviced by the first data storage node, and determining a second amount of data subject to the auction for a second category of user accounts which are serviced by the first data storage node;

the multicasting information comprises multicasting information regarding the first and second amounts of data in the at least one network;

the first data storage node accepts at least one bid for the first category of user accounts, and relocates data of the first category of user accounts to one or more of the other data storage nodes whose bid for the first category of user accounts was accepted; and

the first data storage node accepts at least one bid for the second category of user accounts, and relocates data of the second category of user accounts to one or more of the other data storage nodes whose bid for the second category of user accounts was accepted.

5. The computer-implemented method of claim 4, wherein:

user accounts in the first category have a relatively high activity and consume relatively more resources than user accounts in the second category, and the first data storage node relocates the data of the first category so that the first data storage node is not burdened by a disproportionate number of high activity accounts.

6. The computer-implemented method of claim 1, further comprising:

implementing an aging process to control a time period after which data which was relocated to the first data storage node can be relocated from the first data storage node in an auction, including tracking a time at which the relocated data was relocated to the first data storage node, and ensuring that the relocated data is not relocated from the first data in an auction for a specified period of time.

12. The computer-implemented method of claim 1, wherein:

the first data storage node maintains a timer that determines when the first data storage node determines the amount of data subject to the auction and when the first data storage node multicasts the information regarding the amount of data subject to the auction.

13. The computer-implemented method of claim 1, wherein:

a token is passed among the plurality of data storage nodes, the first data storage node determines the amount of data subject to the auction and multicasts the information regarding the amount of data subject to the auction when the first data storage node receives the token.

14. The computer-implemented method of claim 1, wherein:

the multicast information specifies a minimum unit of data which is to be relocated from the first data storage node; and

in response to receipt of the information, each of the other data storage nodes determines whether it is able to accept the minimum unit of data, and each of the other data storage nodes which determines that it cannot accept the minimum unit of data does not place a bid.

15. The computer-implemented method of claim 1, wherein:

the amount of data which is subject to the auction exceeds a per-auction limit;

the first data storage node rejects at least one bid which, if accepted, would cause the amount of data which is relocated by the first data storage node in the auction to exceed the per-auction limit; and

at least a portion of data of the first data storage node for which the at least one bid was rejected is subject to a subsequent auction.

7. A computer-implemented method for balancing a data load among a plurality of clusters in at least one network, each cluster comprising a plurality of data storage nodes, the method comprising:

determining an amount of data stored at a first cluster of the plurality of clusters;

determining an amount of data subject to an auction of the first cluster based on the amount of data stored, the auction is for relocating data from the first cluster to at least one other cluster of the plurality of clusters, to reduce an amount of data stored at the first cluster;

multicasting information regarding the amount of data subject to the auction from the first cluster to the other clusters, the information indicating that the data subject to the auction includes data of relatively high activity user accounts and data of relatively low activity user accounts;

the information is received by other clusters of the plurality of clusters which have registered to receive multicast announcements from the first cluster; and

in response to receipt of the information, each of the other clusters checks an amount of data stored thereat to determine whether it has available capacity to accept new data, and communicates a bid to the first cluster if it has the capacity to accept new data, the bid from at least one of the other clusters indicates that at least one of data of the relatively high activity user accounts and data of the relatively low activity user accounts will be accepted by the at least one of the other clusters, where the first cluster accepts at least one bid and relocates data to one or more of the other clusters whose bids were accepted.

8. The computer-implemented method of claim 7, wherein:

the information is provided to the other clusters even when the first cluster is not over- capacity.

9. The computer-implemented method of claim 7, wherein:

the at least one bid indicates an amount of data that the at least one of the other clusters can accept.

10. The computer-implemented method of claim 7, wherein:

the determining the amount of data subject to the auction comprises determining a first amount of data subject to the auction for a first category of user accounts which are serviced by the first cluster, and determining a second amount of data subject to the auction for a second category of user accounts which are serviced by the first cluster; and

the multicasting information comprises multicasting information regarding the first and second amounts of data to the other clusters;

the first cluster accepts at least one bid for the first category of user accounts, and relocates data of the first category of user accounts to one or more of the other clusters whose bid for the first category of user accounts was accepted; and

the first cluster accepts at least one bid for the second category of user accounts, and relocates data of the second category of user accounts to one or more of the other clusters whose bid for the second category of user accounts was accepted.

11. The computer-implemented method of claim 10, wherein:

user accounts in the first category have a relatively high activity and consume relatively more resources than user accounts in the second category; and

the first cluster relocates the data of the first category so that the first cluster is not burdened by a disproportionate number of high activity accounts.