Data and replica placement using r-out-of-k hash functions

• US 20080065704A1
• Filed: 09/12/2006
• Published: 03/13/2008
• Est. Priority Date: 09/12/2006
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Junfeng, Murphy, Nicholas, MacCormick, John Philip, Wieder, Ehud, Ramasubramanian, Venugopalan, Zhou, Lidong
• Application Number:
  US11/519,538
• Publication Number:
  US 20080065704A1
• Time in Patent Office: Days
• US Class Current: 707/204
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems

Abstract

A distributed data store employs replica placement techniques in which a number k hash functions are used to compute k potential locations for a data item. A number r of the k locations are chosen for storing replicas. These replica placement techniques provide a system designer with the freedom to choose r from k, are structured in that they are determined by a straightforward functional form, and are diffuse such that the replicas of the items on one server are scattered over many other servers. The resulting storage system exhibits excellent storage balance and request load balance in the presence of incremental system expansions, server failures, and load changes. Data items may be created, read, and updated or otherwise modified.

Claims

1. A data and replica placement method for a data store comprising a plurality of computing devices, comprising:

dividing the computing devices into a number of groups corresponding to a first number, and maintaining a first number of hash functions and a second number corresponding to a replication factor, where the second number is less than the first number;

hashing a data item to a number of locations in the data store among the plurality of computing devices, the number of locations based on the first number; and

storing the data item on a number of the computing devices, the number of computing devices based on the second number.

2. The method of claim 1, wherein the computing devices are servers, and dividing the computing devices into the number of groups comprises partitioning the plurality of servers into the first number of disjoint servers of approximately equal size.

3. The method of claim 2, wherein storing the data item comprises determining the second number of disjoint servers having the least amount of data among the first number of disjoint servers and storing the data item on the second number of disjoint servers.

4. The method of claim 1, wherein the first number of hash functions is based on a level of redundancy and replication.

5. The method of claim 1, further comprising receiving the data item for storage in the data store, prior to hashing the data item.

6. The method of claim 1, further comprising determining the least utilized computing devices.

7. The method of claim 6, wherein the number of the computing devices on which the data item is stored corresponds to the least utilized computing devices.

8. The method of claim 6, wherein determining the least utilized computing devices comprises determining the computing devices with the most spare storage capacity.

9. The method of claim 1, further comprising reading the data item from the computing device on which it is stored that has the least network load.

10. The method of claim 1, further comprising updating the data item on the number of computing devices along with an updated version number.

11. A data and replica placement method for a data store, comprising:

hashing a data item to a number of locations in the data store among a plurality of computing devices, the number of locations based on a first number;

storing the data item on a number of the computing devices, the number of computing devices based on a second number, where the second number is less than the first number; and

updating or modifying the data item on the number of computing devices.

12. The method of claim 11, further comprising dividing the computing devices into a number of groups corresponding to the first number, and wherein the second number corresponds to a replication factor.

13. The method of claim 11, wherein updating or modifying the data item on the number of computing devices includes providing an updated version number.

14. A data and replica placement method for a data store comprising a plurality of computing devices, comprising:

storing a data item on a number of the computing devices;

detecting a failure of one of the computing devices on which the data item is stored;

determining an unused storage location on another of the computing devices outside of the number of computing devices on which the data item is stored; and

copying the data item from one of the computing devices on which the data item is stored to the unused location.

15. The method of claim 14, wherein the number of computing devices on which the data item is stored is based on a replication factor r, r being less than a number of possible locations k in the plurality of computing devices in which the data item may be stored.

16. The method of claim 15, wherein storing the data item comprises:

parameterizing the data store by a k number of hash functions;

hashing the data item to the k possible locations; and

storing the data item on an r number of computing devices of the k possible locations.

17. The method of claim 16, wherein the r number of the computing devices on which the data item is stored corresponds to the least utilized r computing devices.

18. The method of claim 17, further comprising determining the least utilized computing devices by determining the computing devices with the most spare storage capacity.

19. The method of claim 14, wherein copying the data item comprises identifying a copy of the data item on one of the number of the computing devices that has not failed.