Balancing load across cache servers in a distributed data store

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.

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 version in each repetition, until the hash weight is less than the assigned weight of the specified cache server, and
• reallocating the specified identifier to the specified cache server.