Memory-efficient technique for weighted round-robin load balancing

1. A non-transitory computer-readable medium comprising program code that is executable by a processor for causing the processor to:

determine an offset to apply to a list of node identifiers based on a counter value, wherein the node identifiers uniquely identify a plurality of computing nodes in a distributed computing system;

select a subset of node identifiers, from the list of node identifiers, based on the offset;

determine a length of the subset of node identifiers, the length being a number of node identifiers in the subset;

select a node identifier, from the subset of node identifiers, based on the counter value and the length of the subset of node identifiers; and

transmit data to a node corresponding to the node identifier.

2. The non-transitory computer-readable medium of claim 1 , further comprising program code that is executable by the processor for causing the processor to:

obtain a mapping that correlates keys to offsets; and

select the offset from the mapping by comparing the counter value to the keys.

3. The non-transitory computer-readable medium of claim 2 , further comprising program code that is executable by the processor for causing the processor to generate the mapping based on a plurality of weights, each weight in the plurality of weights being assigned to a respective node of plurality of computing nodes in the distributed computing system and dictating an amount of data to be transmitted to the respective node by a load balancer.

4. The non-transitory computer-readable medium of claim 3 , further comprising program code that is executable by the processor for causing the processor to determine each weight in the plurality of weights based on a number of recipients executing on the respective node corresponding to the weight.

5. The non-transitory computer-readable medium of claim 3 , further comprising program code that is executable by the processor for causing the processor to:

sort the plurality of weights from a lowest value to a highest value to generate a sorted list of weights;

obtain a list of weight increments based on the sorted list of weights; and

generate the mapping based on the list of weight increments.

6. The non-transitory computer-readable medium of claim 5 , further comprising program code that is executable by the processor for causing the processor to determine the list of weight increments by:

initializing a data structure for storing the list of weight increments; and

for each index position of a plurality of index positions in the sorted list of weights:

determining a respective weight value that is located at the index position in the sorted list of weights;

determining a respective weight increment by subtracting a respective reference value from the respective weight value, wherein the respective reference value is zero or a particular weight value in the sorted list of weights; and

storing the respective weight increment in the data structure, wherein the data structure serves as the list of weight increments.

7. The non-transitory computer-readable medium of claim 5 , further comprising program code that is executable by the processor for causing the processor to generate the mapping based on the list of weight increments by, for each weight increment in the list of weight increments:

determining a respective key range based on the weight increment;

determining a respective offset corresponding to the respective key range; and

storing a relationship between the respective key range and the respective offset in the mapping.

8. The non-transitory computer-readable medium of claim 1 , further comprising program code that is executable by the processor for causing the processor to select the node identifier from the subset of node identifiers by:

dividing the counter value by the length of the subset of node identifiers to obtain a remainder; and

selecting the node identifier from the subset of node identifiers based on the remainder.

9. The non-transitory computer-readable medium of claim 1 , wherein the program code forms at least part of a load balancer for the distributed computing system.

10. The non-transitory computer-readable medium of claim 1 , wherein the subset of node identifiers is a proper subset of the list of node identifiers.

11. A distributed computing system, comprising:

a processor;

a list of node identifiers that uniquely identify a plurality of computing nodes in the distributed computing system;

a mapping of keys to offsets, wherein the keys are counter values, and wherein the offsets are index positions in the list of node identifiers;

a counter indicating a counter value; and

a memory including instructions for a load balancer, the instructions being executable by the processor for causing the processor to implement a load-balancing process involving:

determining a key that matches the counter value in the mapping;

determining an offset corresponding to the key in the mapping;

selecting a subset of node identifiers, from the list of node identifiers, based on the offset;

determining a length of the subset of node identifiers, the length being a number of node identifiers in the subset;

selecting a node identifier, from the subset of node identifiers, based on the counter value and the length of the subset of node identifiers; and

transmitting data to a node, of the plurality of computing nodes, corresponding to the node identifier.

12. The distributed computing system of claim 11 , wherein the instructions are further executable by the processor to generate the mapping based on a plurality of weights, each weight in the plurality of weights being assigned to a respective node of the plurality of computing nodes in the distributed computing system based on a number of recipients executing on the respective node.

13. The distributed computing system of claim 12 , wherein the instructions are further executable by the processor to:

sort the plurality of weights from a lowest value to a highest value to generate a sorted list of weights;

obtain a list of weight increments based on the sorted list of weights; and

generate the mapping based on the list of weight increments.

14. The distributed computing system of claim 13 , wherein the instructions are further executable by the processor to determine the list of weight increments by:

initializing a data structure for storing the list of weight increments;

for each index position of a plurality of index positions in the sorted list of weights:

determining a respective weight value that is located at the index position in the sorted list of weights;

determining a respective weight increment by subtracting a respective reference value from the respective weight value, wherein the respective reference value is zero or a particular weight value located at a prior index position in the sorted list of weights; and

storing the respective weight increment at the index position in the data structure, wherein the data structure serves as the list of weight increments.

15. A method comprising:

determining, by a processor, an offset to apply to a list of node identifiers based on a counter value, wherein the node identifiers uniquely identify a plurality of computing nodes in a distributed computing system;

selecting, by the processor, a subset of node identifiers from the list of node identifiers based in the offset;

determining, by the processor, a length of the subset of node identifiers, the length being a number of node identifiers in the subset;

selecting, by the processor, a node identifier from the subset of node identifiers based on the counter value and the length of the subset of node identifiers; and

transmitting, by the processor, data to a node corresponding to the node identifier.

16. The method of claim 15 , further comprising:

generating a mapping of keys to offsets based on a plurality of weights, each weight in the plurality of weights being assigned to a respective node of the plurality of computing nodes in the distributed computing system based on a number of recipients executing on the respective node; and

selecting the offset from the mapping by comparing the counter value to the keys in the mapping.

17. The method of claim 16 , further comprising:

sorting the plurality of weights from a lowest value to a highest value to generate a sorted list of weights;

determining a list of weight increments based on the sorted list of weights; and

generating the mapping based on the list of weight increments.

18. The method of claim 17 , further comprising determining the list of weight increments by:

initializing a data structure for storing the list of weight increments; and

for each index position of a plurality of index positions in the sorted list of weights:

determining a respective weight value that is located at the index position in the sorted list of weights;

determining a respective weight increment by subtracting a respective reference value from the respective weight value, wherein the respective reference value is zero or a particular weight value in the sorted list of weights; and

storing the respective weight increment in the data structure, wherein the data structure serves as the list of weight increments.

19. The method of claim 17 , further comprising generating the mapping based on the list of weight increments by, for each weight increment in the list of weight increments:

determining a respective key range based on the weight increment;

determining a respective offset corresponding to the respective key range; and

storing a relationship between the respective key range and the respective offset in the mapping.

20. The method of claim 15 , further comprising selecting the node identifier from the subset of node identifiers by:

dividing the counter value by the length of the subset of node identifiers to obtain a remainder; and

selecting the node identifier from the subset of node identifiers based on the remainder.