Method for distributing keys using two auxiliary hashing functions

Patent metadata

Field	Value
Publication number	US-11429452-B2
Application number	US-202016850643-A
Country	US
Kind code	B2
Filing date	Apr 16, 2020
Priority date	Apr 16, 2020
Publication date	Aug 30, 2022
Grant date	Aug 30, 2022

Abstract

This disclosure includes an improvement to hashing methods, which can help achieve faster load balancing of computing resources (e.g., processors, storage systems, web servers or other computer systems, etc.) This improvement may be particularly beneficial when a quantity of the available resources changes. Such hashing methods may include assigning a data object associated with a key to a particular computing resource of the available computing resources by using two auxiliary functions that work together to uniformly distribute data objects across available computing resources and reduce an amount of time to assign the data object to the particular computing resource.

First claim

What is claimed is:

1. A non-transitory computer-readable medium having instructions stored thereon that are executable by a computer system to perform operations comprising:
receiving, by a load balancer executing on the computer system, a key associated with a data object;
assigning, by the load balancer, the data object to one of N nodes by:
determining a first result that maps the key to one of M nodes, wherein M is an integer that is a power of two and greater than or equal to N;
in response to determining that the first result is less than N, selecting the first result as a final assignment;
otherwise:
determining a second result that maps the key to a first subset of the N nodes;
in response to determining that the second result corresponds to a particular node within the first subset, selecting a third result as the final assignment, wherein the third result is within a second subset of the N nodes; and
otherwise, selecting the second result as the final assignment; and

storing the data object using a given node of the N nodes that corresponds to the final assignment.

2. The non-transitory computer-readable medium of claim 1 , wherein the first subset of the N nodes includes a node S through a final node of the N nodes, and wherein the particular node corresponds to node S.

3. The non-transitory computer-readable medium of claim 2 , wherein the operations further comprise selecting a value of S using a largest power of two value that is less than N.

4. The non-transitory computer-readable medium of claim 2 , wherein a probability of a given key being mapped to node S is greater than a probability of the given key being mapped to any other node within the first subset.

5. The non-transitory computer-readable medium of claim 2 , wherein the second subset of the N nodes includes node S.

6. The non-transitory computer-readable medium of claim 1 , wherein the operations further comprise, in response to one or more of the N nodes being unavailable, reassigning, using respective alternate keys, data objects included in unavailable nodes to currently available nodes of the N nodes.

7. The non-transitory computer-readable medium of claim 6 , wherein reassigning a particular data object includes determining the respective alternate key using a shifted version of a key associated with the particular data object.

8. The non-transitory computer-readable medium of claim 7 , wherein reassigning the particular data object further includes:
repeating, using the respective alternate key, the assigning by the load balancer; and
in response to determining that the final assignment corresponds to an unavailable node, selecting a fallback node as the final assignment.

9. A non-transitory computer-readable medium having instructions stored thereon that are executable by a computer system to hash a key into one of N buckets by performing operations comprising:
determining a first result by hashing, using a first hashing function, the key into one of M buckets, wherein M is an integer greater than or equal to N; and
assigning a final bucket by:
in response to the first result corresponding to one of the N buckets, assigning the first result as the final bucket; and
otherwise:
determining a second result by hashing the key into a first range within the N buckets using a second hashing function in which a probability of a given key being mapped to a bucket S within the first range is greater than a probability of the given key being mapped to remaining buckets within the first range; and
assigning the final bucket based on whether the second result corresponds to bucket S.

10. The non-transitory computer-readable medium of claim 9 , wherein assigning the final bucket based on whether the second result corresponds to bucket S comprises:
in response to the second result indicating a bucket other than bucket S, assigning the second result as the final bucket; and
otherwise, assigning a third result as the final bucket, by hashing, using a third hashing function, the key into one of a second range of the N buckets.

11. The non-transitory computer-readable medium of claim 10 , wherein a value of S is a lower limit of the first range and an upper limit of the second range.

12. The non-transitory computer-readable medium of claim 10 , wherein the first, second, and third hashing functions each have a constant execution time and, in combination, uniformly distribute keys among the N buckets.

13. The non-transitory computer-readable medium of claim 10 , wherein the first hashing function and the third hashing function are a same function with different inputs.

14. The non-transitory computer-readable medium of claim 9 , wherein the operations further comprise:
selecting a value of M using a smallest power of two value that is greater than or equal to N; and
selecting a value of S using a largest power of two value that is less than N.

15. The non-transitory computer-readable medium of claim 9 , wherein the operations further comprise mapping each of the N buckets to one of P nodes, wherein a value of P is less than a value of N, and wherein at least one of the P nodes is mapped from more of the N buckets than another one of the P nodes.

16. A method comprising:
receiving, by a computer system, a key associated with a data object to be assigned to one of N buckets;
determining, by the computer system, a first result using a first hashing function to hash the key into one of M buckets, wherein M is an integer greater than N;
in response to determining that the first result is greater than N, determining, by the computer system, a second result by hashing the key into a first range within the N buckets using a second hashing function in which a probability of a given key being mapped to a bucket S within the first range is greater than a probability of the given key being mapped to remaining buckets within the first range; and
in response to determining that the second result corresponds to bucket S, assigning, by the computer system, the data object to one particular bucket of a second, different, range of the N buckets by hashing the key using a third hashing function to generate a third result.

17. The method of claim 16 , further comprising:
selecting a value of M that is based on a smallest power of two value that is greater than N; and
selecting a value of S that is based on a largest power of two value that is less than N.

18. The method of claim 16 , further comprising, in response to a removal of one or more of the N buckets, reassigning, using respective alternate keys, data objects included in unavailable buckets to one of a set of fallback buckets, different from the N buckets.

19. The method of claim 16 , further comprising:
receiving, by the computer system, a second key associated with a second data object to be assigned to one of N′ buckets, wherein N′ is an updated value of N that is equal to a power of two;
performing, by the computer system, the first hashing function to obtain a fourth result; and
assigning, by the computer system, the second data object to one of the N′ buckets that corresponds to the fourth result.

20. The method of claim 16 , wherein the first and third hashing functions are a same function that includes:
dividing the M buckets into a number of groups, wherein the number of groups is equal to log 2 (M), wherein each group has an associated group number, and wherein a number of the M buckets mapped to a given group is based on the associated group number for that gr

Assignees

• Paypal Inc

Inventors

• Leu Eric

Classifications

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title