How Were the Weightings in the Linux Load Computation Chosen

How to prove the Nginx smoothing weight load balancing algorithm mathematically?

It is not exactly clear what exactly is the property you want to be proven. The correctness with regarding to weights is not hard to prove.

Assume we have integer weights Wi with sum S.

Claim #1: over S consecutive selections each i-th server will be selected exactly Wi times.

Here is a sketch of the proof. Claim #1 follows from the Claim #2: at no point server with a negative current weight (CWi) can be selected. Which in turn follows from the Claim #3: at every step the sum of all current weights is 0.

The Claim #3 is obviously true: at each step of the algorithm we add each Wi to the current weights CWi and subtract S from the one being selected. So we add and subtract S. So the sum stays the same as it was before the first step i.e. 0.

If the sum is always 0, it means that if there is some negative current weight, there must be a positive current weight. Obviously any positive current weight is a better choice than a negative one so we have the Claim #2 proven.

Back to the Claim #1: Assume some i-th sever has been selected Ni times, more then Wi. Let's look at the last time such a selection was made. Let that be some step number j (0 < j < S, strictly speaking you need to also consider the case of the selection at the very first step j=0, but it is obvious that every server with non-zero weight will be selected at least once so "overflow" can't happen at the first step). At j-th step its current weight CWi = j*Wi - (Ni-1)*S. Since Ni > Wi, it means Ni-1 >= Wi; and j < S. So j*Wi < (Ni-1)*S or CWi < 0. And we know that a server with a negative current weight can never be selected. Contradiction.

Now assume some i-th server has been selected less times then Wi. Since the total number of server selections is fixed, some other j-the server has been selected more times than Wj and we already know that can't happen. This finishes our proof for the Claim #1.

As for "the distribution is also relatively uniform" part it is not a formalized statement and thus can't be proven.

Weighted random numbers

There is a straightforward algorithm for picking an item at random, where items have individual weights:

1) calculate the sum of all the weights

2) pick a random number that is 0 or greater and is less than the sum of the weights

3) go through the items one at a time, subtracting their weight from your random number, until you get the item where the random number is less than that item's weight

Pseudo-code illustrating this:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

This should be straightforward to adapt to your boost containers and such.

---

If your weights are rarely changed but you often pick one at random, and as long as your container is storing pointers to the objects or is more than a few dozen items long (basically, you have to profile to know if this helps or hinders), then there is an optimisation:

By storing the cumulative weight sum in each item you can use a binary search to pick the item corresponding to the pick weight.

---

If you do not know the number of items in the list, then there's a very neat algorithm called reservoir sampling that can be adapted to be weighted.

Does linux kernel assume that it is located at a particular physical address?

The kernel does expect to be at a specific location. That location is architecture specific. You can reconfigure and recompile the kernel to adjust this.

I was actually researching this recently for x86/x86_64, which is well documented. I would expect to find Sparc documentation there, though it doesn't jump out at me. Some information can be found here, though.

The relevant bit seems to be:

The boot sector that gets loaded is what you find in /boot/first.b in
your Linux-Sparc system, and is a bare 512 bytes. It is loaded to
address 0x4000 and its role is retrieving from disk /boot/second.b and
putting it to address 0x280000 (2.5 megs); the address has been chosen
because the Sparc specifications state that at least three megabytes
of RAM are mapped at boot time.

---

Related Topics