Generating monotone hash preferences
Selecting a resource to fulfill a resource requirement is disclosed. For each resource requirement, a resource-specific affinity value is computed with respect to each of a plurality of resources. A bias is applied to each of at least a subset of the resource-specific affinity values. The biased, as applicable, resource-specific affinity values are sorted into a resource preference list. The sorted preference list is used to select a resource to fulfill the resource requirement.
1. A method of selecting a resource to fulfill a resource requirement, comprising:
computing for each of a plurality of resources, with respect to the resource requirement, a resource-specific affinity value;
applying a bias to each of at least a subset of the resource-specific affinity values, wherein the bias comprises a function that is monotonically increasing both in terms of an input hash and a desired bias;
sorting the biased, as applicable, resource-specific affinity values into a resource preference list; and
using the sorted preference list to select a resource to fulfill the resource requirement.
2. The method of claim 1 , wherein the resource-specific affinity value comprises a resource-specific hash value.
3. The method of claim 1 , wherein the resource-specific affinity value is computed by computing a resource requirement-specific hash value, the hash value corresponding to a resource requirement-associated point in a space; and calculating a distance in the space between the resource requirement-associated point and a second point associated with the resource with respect to which the resource-specific affinity value is being computed.
4. The method of claim 1 , wherein the bias comprises a resource-specific bias.
5. The method of claim 1 , wherein a first resource-specific bias is applied to a first resource-specific affinity value associated with a first resource and a second resource-specific bias is applied to a second resource-specific affinity value associated with a second resource.
6. The method of claim 1 , wherein the bias comprises a resource-specific bias determined for a particular resource based at least in part on a data associated with that particular resource.
7. The method of claim 1 , wherein the bias is determined based at least in part on a data associated with the resource requirement.
8. The method of claim 1 , wherein the bias is determined for a particular resource based at least in part on a data reflecting a relationship between the resource requirement and the particular resource.
9. The method of claim 8 , wherein the bias is determined based at least in part on a stored data reflecting a past relationship between the resource and the resource requirement.
10. The method of claim 8 , wherein the bias is determined based at least in part on a stored data reflecting a past relationship between a resource and one or more descriptive attributes of the resource requirement.
11. The method of claim 8 , wherein the bias is determined based at least in part on a stored data reflecting a user configured relationship between a resource and one or more descriptive attributes of the resource requirement.
12. The method of claim 8 , wherein the bias is determined based at least in part on a stored data reflecting a past relationship between the resource and a user with which the resource requirement is associated.
13. The method of claim 1 , wherein the bias comprises a multiplicative bias.
14. The method of claim 1 , wherein the resource requirement comprises a request to store a data object.
15. The method of claim 1 , wherein the resource requirement comprises a request to find a previously stored data object.
16. The method of claim 1 , wherein the plurality of resources comprises a plurality of storage nodes.
17. The method of claim 1 , wherein a consistent hash function is used to compute the resource-specific affinity values.
18. The method of claim 1 , wherein a monotone hash function is used to compute the resource-specific affinity values.
19. The method of claim 1 , further comprising:
detecting that a removed resource has been removed from the plurality of resources; and
determining for the resource requirement a new sorted resource preference list that does not include the removed resource.
20. The method of claim 19 , further comprising determining that the resource requirement was fulfilled previously, at least in part, using the removed resource.
21. The method of claim 1 , further comprising:
detecting that an added resource has been added to the plurality of resources; and
determining for the resource requirement a new sorted resource preference list that includes the added resource.
22. The method of claim 21 , further comprising using the new sorted resource preference list to determine that the added resource is to be used to fulfill the resource requirement.
23. The method of claim 1 , wherein using the sorted preference list to select a resource to fulfill the resource requirement comprises using a first m resources in the sorted preference list to fulfill the resource requirement.
24. The method of claim 1 , wherein using the sorted preference list to select a resource to fulfill the resource requirement comprises using a first m available resources in the sorted preference list to fulfill the resource requirement.
25. A resource selection system, comprising:
a communication interface configured to receive a communication comprising a resource requirement; and
a processor coupled to the communication interface and configured to:
compute for each of a plurality of resources, with respect to the resource requirement, a resource-specific affinity value;
apply a bias to each of at least a subset of the resource-specific affinity values, wherein the bias comprises a function that is monotonically increasing both in terms of an input hash and a desired bias;
sort the biased, as applicable, resource-specific affinity values into a resource preference list; and
use the sorted preference list to select a resource to fulfill the resource requirement.
26. The system of claim 25 , wherein a first resource-specific bias is applied to a first resource-specific affinity value associated with a first resource and a second resource-specific bias is applied to a second resource-specific affinity value associated with a second resource.
27. The system of claim 25 , wherein the bias is determined for a particular resource based at least in part on a data reflecting a relationship between the resource requirement and the particular resource.
28. The system of claim 25 , wherein the resource requirement comprises a request to store a data object and the plurality of resources comprises a plurality of storage nodes.
29. The system of claim 25 , wherein the processor is further configured to:
detect that a removed resource has been removed from the plurality of resources; and
determine for the resource requirement a new sorted resource preference list that does not include the removed resource.
30. The system of claim 25 , wherein the processor is further configured to:
detect that an added resource has been added to the plurality of resources; and
determine for the resource requirement a new sorted resource preference list that includes the added resource.
31. A computer program product for selecting a resource to fulfill a resource requirement, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
computing for each of a plurality of resources, with respect to the resource requirement, a resource-specific affinity value;
applying a bias to each of at least a subset of the resource-specific affinity values, wherein the bias comprises a function that is monotonically increasing both in terms of an input hash and a desired bias;
sorting the biased, as applicable, resource-specific affinity values into a resource preference list; and
using the sorted preference list to select a resource to fulfill the resource requirement.