Balancing load across cache servers in a distributed data store

Patent metadata

Field	Value
Publication number	US-9871855-B2
Application number	US-201414491760-A
Country	US
Kind code	B2
Filing date	Sep 19, 2014
Priority date	Sep 19, 2014
Publication date	Jan 16, 2018
Grant date	Jan 16, 2018

Abstract

A technology for balancing computing resource load across cache servers in a distributed data store is disclosed. The technology can monitor computing resource load on each cache server to increase or decrease an assigned weight of the cache server. The technology can use two hash functions to reallocate, based on the change in the assigned weight, a portion of the key space from one cache server to another. The first hash function can be a consistent hash function that identifies a cache server mapped to an entity identifier. The second hash function can be employed to determine a hash weight of the cache server. The hash weight of the cache server can then be evaluated against the assigned weight to determine whether the entity identifier should remain mapped to the same cache server or should be reevaluated for allocation to a different cache server.

First claim

We claim:

1. A method, comprising:
distributing a set of entity identifiers among cache servers in a cluster of cache servers, each cache server having associated therewith a subset of the set of entity identifiers;
monitoring an operational parameter associated with each cache server in the cluster, the operational parameter providing a measure of a computing resource load on the cache server;
adjusting, based on a value of the operational parameter, a weight assigned to a first cache server among the cache servers to balance the computing resource load across the cache servers, wherein adjusting the weight generates an adjusted weight; and
re-distributing, based on the adjusted weight of the first cache server, a specified entity identifier of the subset of the set of entity identifiers from the first cache server to a specified cache server of the cache servers in the cluster to balance the computing resource load across the cache servers, wherein the redistributing includes:
determining, using a consistent hash function, a specified cache server of the cache servers mapped to a modified version of the specified entity identifier,
confirming that a hash weight of the specified cache server is less than an assigned weight of the specified cache server, the hash weight of the specified cache server computed using a second hash function with the modified version of the specified entity identifier as an input, wherein the determining and confirming is performed repeatedly, after salting the specified entity identifier to generate the modified version in each repetition, until the hash weight is less than the assigned weight, and
assigning, in response to the confirming, the specified entity identifier to the specified cache server.

2. The method of claim 1 , wherein the operational parameter is one of: a CPU utilization, a cache hit rate or a number of requests per entity identifier.

3. The method of claim 1 , wherein the adjusting includes decreasing the weight assigned to the first cache server when the value of the operational parameter indicates an increased computing resource load on the first cache server.

4. The method of claim 3 , further comprising flushing out data related to the specified entity identifier from the first cache server to prevent cache inconsistency.

5. The method of claim 1 , wherein the modified version of the specified entity identifier includes the specified entity identifier with a string appended thereto, wherein the string is different in each repetition.

6. The method of claim 1 , wherein an entity identifier from the set of entity identifiers is one of a user identifier or a database identifier, wherein each database identifier is mapped to a cache server among the cache servers in the cluster.

7. A non-transitory computer-readable storage medium storing instructions, comprising:
instructions for receiving a request including an identifier;
instructions for determining, using a consistent hash function, that the identifier is allocated to a first cache server among a plurality of cache servers;
instructions for computing a hash weight of the first cache server using a specified hash function;
instructions for receiving an assigned weight of the first cache server;
instructions for comparing the hash weight against the assigned weight to reallocate the identifier to a second cache server among the plurality of cache servers to balance computing resource load across the plurality of cache servers, wherein the instructions for comparing include:
instructions for determining one of the cache servers as the second cache server based on the consistent hash function, the consistent hash function using a modified version of the identifier as an input,
instructions for confirming that a hash weight of the second cache server is less than an assigned weight of the second cache server, the hash weight computed using the specified hash function with the modified version of the identifier as an input, wherein the determining and confirming is performed repeatedly, after salting the identifier to generate the modified version in each repetition, until the hash weight is less than the assigned weight, and
instruction for reallocating the identifier to the second cache server.

8. The non-transitory of claim 7 , further comprising instructions for reallocating the identifier to the second cache server when the hash weight is greater than or equal to the assigned weight of the first cache server.

9. The non-transitory of claim 8 , further comprising instructions for flushing cached elements associated with the identifier from the first cache server when the identifier is reallocated to the second cache server to prevent cache inconsistency, wherein the identifier is a database identifier.

10. The non-transitory of claim 8 , wherein the modified identifier is salted by appending a string to the identifier, wherein a different string is used in each repetition.

11. The non-transitory of claim 7 , wherein the identifier is one of: a user identifier or a database identifier, wherein each database identifier is mapped to a cache server.

12. The non-transitory of claim 7 , further comprising:
instructions for monitoring computing resource load on each of the plurality of cache servers; and
instructions for detecting an increase in the computing resource load on the first cache server.

13. The non-transitory of claim 10 , further comprising instructions for decreasing an assigned weight of the first cache server in proportion to the increase in the computing resource load on the first cache server.

14. The non-transitory computer-readable medium of claim 10 , wherein the computing resource load on each of the plurality of cache servers is measured based on a number of requests per second per entity identifier, CPU utilization, a cache hit rate or a combination of thereof.

15. A system, comprising:
a cluster including a plurality of cache servers, wherein each cache server has a processor and a memory; and
a module for balancing computing resource load across the plurality of cache servers;
wherein the module is configured to:
allocate a key space to each cache server in the plurality of cache servers so that each cache server is associated with the key space allocated to the cache server;
monitor an operational parameter associated with each cache server, the operational parameter providing a measure of computing resource load on the cache server;
detect, based on a value of the operational parameter associated with a first cache server, an increased computing resource load on the first cache server;
adjust an assigned weight of the first cache server among the plurality of cache servers to reduce the computing resource load on the first cache server, wherein the assigned weight is adjusted to generate an adjusted weight; and
reallocate, based on the adjusted weight of the first cache server, a specified identifier in the key space from the first cache server to a specified cache server of the plurality of cache servers, wherein the module is configured to reallocate by:
determining, using a consistent hash function, a specified cache server of the cache servers mapped to a modified version of the specified identifier,
confirming that a hash weight of the specified cache server is less than an assigned weight of the specified cache server, the hash weight computed using a second hash function with the modified version of the specified identifier as an input, wherein the determining and confirming is performed repeatedly, after salting the specified identifier to generate the modified

Assignees

• Facebook Inc

Inventors

• Likhtarov Anton
• Meisner David Max
• Michelson Scott David
• Grynenko Andrii

Classifications

• H04L67/1008 Primary

  based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) · CPC title

• H04L43/0817

  by checking functioning · CPC title