Heat-based load balancing
Methods, apparatus and computer software products implement embodiments of the present invention that include receiving requests from clients to access a corpus of data that is replicated on a group of servers, and distributing the requests among the servers for execution in accordance with an allocation function, which indicates a respective fraction of the requests that is to be assigned to each of the servers for execution. Respective cache miss rates incurred by the servers in responding to the requests that are distributed to each of the servers are measured, and the allocation function is adjusted responsively to the cache miss rates.
1. A method, comprising:
replicating a corpus of data on a group of a plurality of servers;
receiving requests from clients to access the corpus of data that is replicated on the group of servers;
distributing the requests among the servers for execution in accordance with an allocation function, which indicates respective fractions of the requests that are to be assigned to each of the servers for execution, such that different servers in the group receive requests at different rates;
measuring respective cache miss rates incurred by the servers in responding to the requests that are distributed to each of the servers; and
adjusting the fractions in the allocation function and the corresponding rates at which the servers receive requests, responsively to the cache miss rates.
2. The method according to claim 1 , wherein measuring the respective cache miss rates comprises measuring respective first and second cache miss rates of first and second servers in the group and detecting that the first cache miss rate is higher than the second cache miss rate, and wherein adjusting the allocation function comprises, responsively to detecting that the first cache miss rate is higher than the second cache miss rate, decreasing a first fraction of the requests that is assigned to the first server while increasing a second fraction of the requests that is assigned to the second server.
3. The method according to claim 1 , wherein adjusting the allocation function comprises assigning each of the fractions a value inversely proportional to its respective cache miss rate.
4. The method according to claim 1 , wherein the corpus of data comprises a multi-node database, and wherein the servers comprise nodes of the multi-node database.
5. The method according to claim 4 , wherein the steps of receiving the requests, distributing the requests, measuring the respective miss rates, and adjusting the allocation function are performed by each of the nodes.
6. The method according to claim 5 , wherein the multi-node database has a specific number of replications, wherein each of the nodes receives respective disjoint subsets of the requests, and wherein distributing the requests to the nodes comprises processing locally, by the given node a number of its received subset of requests in accordance with its respective fraction in the allocation function and the number of replications, and forwarding its other received requests to the other nodes, thereby minimizing, on the network, data traffic for processing the received requests.
7. The method according to claim 6 , wherein the nodes comprise respective storage devices, and wherein processing, by a given node, a given request locally comprises retrieving data from its respective storage device.
8. The method according to claim 1 , wherein adjusting the allocation function equalizes the cache miss rates when processing additional requests to access the corpus of data.
9. A computer, comprising:
a memory configured to store an allocation function; and
a processor configured:
to replicate a corpus of data on a group of a plurality of servers;
to receive requests from clients to access the corpus of data that is replicated on the group of servers,
to distribute the requests among the servers for execution in accordance with the allocation function, which indicates respective fractions of the requests that are to be assigned to each of the servers for execution, such that different servers in the group receive requests at different rates,
to measure respective cache miss rates incurred by the servers in responding to the requests that are distributed to each of the servers, and
to adjust the fractions in the allocation function and the corresponding rates at which the servers receive requests, responsively to the cache miss rates.
10. The computer according to claim 9 , wherein the processor is configured to measure the respective cache miss rates by measuring respective first and second cache miss rates of first and second servers in the group and detecting that the first cache miss rate is higher than the second cache miss rate, and wherein the processor is configured to adjust the allocation function by, responsively to detecting that the first cache miss rate is higher than the second cache miss rate, decreasing a first fraction of the requests that is assigned to the first server while increasing a second fraction of the requests that is assigned to the second server.
11. The computer according to claim 9 , wherein the processor is configured to adjust the allocation function by assigning each of the fractions a value inversely proportional to its respective cache miss rate.
12. The computer according to claim 9 , wherein the processor comprises a first processor and the memory comprises a second processor, wherein the corpus of data comprises a multi-node database, and wherein the servers comprise nodes of the multi-node database, each of the nodes comprising a second processor, a second memory, and one or storage devices.
13. The computer according to claim 12 , wherein the steps of receiving the requests, distributing the requests, measuring the respective miss rates, and adjusting the allocation function are performed by each of the nodes.
14. The computer according to claim 13 , wherein the multi-node database has a specific number of replications, wherein each of the nodes is configured to receive respective disjoint subsets of the requests, and wherein a given node is configured to distribute the requests to the nodes by processing locally, a number of its received subset of requests in accordance with its respective fraction in the allocation function and the number of replications, and forwarding its other received requests to the other nodes, thereby minimizing, on the network, data traffic for processing the received requests.
15. The computer according to claim 14 , wherein processing, by the given node, a given request locally comprises retrieving data from its respective storage device.
16. The computer according to claim 9 , wherein adjusting the allocation function equalizes the cache miss rates when processing additional requests to access the corpus of data.
17. A computer software product, the product comprising a non-transitory computer-readable medium, in which program instructions are stored, which instructions, when read by a computer, cause the computer:
to replicate a corpus of data on a group of a plurality of servers;
to receive requests from clients to access the corpus of data that is replicated on the group of servers;
to distribute the requests among the servers for execution at different rates in accordance with an allocation function, which indicates respective fractions of the requests that are to be assigned to each of the servers for execution, such that different servers in the group receive requests at different rates;
to measure respective cache miss rates incurred by the servers in responding to the requests that are distributed to each of the servers; and
to adjust the fractions in the allocation function and the corresponding rates at which the servers receive requests, responsively to the cache miss rates.