LearnastraTHE DESIGN COURSE

Understand the building blocks / CHAPTER 10

Load balancing algorithms

Choose a routing policy using request cost, connection lifetime, and placement needs.

Intermediate1h of deliberate study10 questions

Builds on Load balancing.

By the end, you can
  • Compare round robin, least connections, weighted routing, and hashing.
  • Explain why request count can differ from actual load.
  • Select a policy and define its failure fallback.

01First decide what “less busy” means

A new download request reaches a balancer. Servers A, B, and C are ready, but which should receive it? Count connections, measure transferred bytes, or observe processor use and you may get different answers. Start by asking what work the request needs.

Use this measured snapshot. MB/s means decimal megabytes transferred per second. Capacity weights are operator-supplied estimates based on tests; they are not current load measurements.

Server Capacity weight Active connections Current MB/s Response time CPU busy Queued jobs
A 4 8 80 40 ms 70% 8
B 2 6 20 20 ms 50% 2
C 1 3 60 60 ms 20% 10

Read the numbers before choosing a rule:

  • C has the fewest connections, but those connections may carry large downloads.
  • B transfers the fewest bytes and has the lowest measured response time.
  • A has more connections, but testing assigns it more capacity.
  • C uses little CPU while ten jobs wait. It might be blocked on another service, so low CPU alone does not prove it can finish new jobs quickly.

A balancing algorithm is the rule that turns such information into a destination. First exclude unready servers; then apply the rule to those still eligible.

02Nine policies, with actual choices

The table applies nine common rules to the same snapshot. Product implementations may use different measurements or tie-breaking, so state the calculation you mean.

Algorithm How it chooses Example and limitation
Round robin Select A, then B, then C, and repeat. Twelve comparable arrivals give four each. Equal counts can overload a smaller server.
Weighted round robin Assign request shares in proportion to tested capacity weights. Weights 4:2:1 give eight, four, and two of fourteen arrivals. Static weights do not follow a sudden slowdown.
Least connections Select the server with the fewest active connections. C has three. One connection can carry much more work than another.
Weighted least connections In this simplified rule, divide active connections by capacity weight and select the smallest result. A: 8/4=2; B: 6/2=3; C: 3/1=3. Choose A. Connections must still be comparable measures of work.
Least response time Favor the server with the lowest recent measured response time. B has 20 ms. An old or unusually fast sample may mislead.
Least bandwidth Select the lowest measured rate of transferred bytes. B has 20 MB/s. This says little about its CPU capacity.
IP hash Apply a repeatable calculation to the client address and map the result to a server. The same address usually gets the same choice while the mapping remains unchanged. Many people may share that address.
Random Choose independently, with equal probability among eligible servers. Long-run shares tend toward equality. Twelve arrivals need not split four each.
Custom load Select using an explicitly defined application measurement. Fewest queued jobs chooses B. Lowest CPU chooses C. Choose the measurement that reflects the incoming work.

Separate the two weighted policies:

  1. Weighted round robin divides arrivals according to capacity shares. For fourteen arrivals, the total weight is seven; each weight unit receives two requests.
  2. Weighted least connections checks the current connection count as well as capacity. It can choose a different next server even with unchanged weights.

Measurements need interpretation:

  • A 20 MB/s flow fills a 20 MB/s link but uses only one fifth of a 100 MB/s link. Compare traffic with link capacity when links differ.
  • Combine recent response-time samples over a stated window rather than reacting entirely to one sample. This is smoothing. Some products also consider active work.
  • Define the maximum age of a report, behavior when it is missing, and how a recovered server gets enough trial traffic to be measured again.

03Affinity, feedback, and a practical selection

Consider two office users who share one public network address. A network device translates their private addresses to that shared public address; this is network address translation, or NAT. An IP-hash rule sees the shared address rather than their separate account identities.

A toy mapping makes the effect visible:

  1. Number the servers A=0, B=1, and C=2.
  2. Suppose a repeatable calculation on the address produces 8.
  3. Divide by the server count and take the remainder: 8 mod 3 = 2. Select C.
  4. Both office users therefore reach C. Their traffic can concentrate there.
  5. If adding D changes this simple rule to 8 mod 4 = 0, the same address now reaches A. Other implementations can use different mapping rules.

Address affinity has further limits:

  • A mobile user’s address can change. A proxy may hide the original address.
  • Accept a forwarded address only from a configured proxy that removes caller-supplied fakes.
  • An address does not identify a person or guarantee the nearest region.
  • If C fails, another server needs recoverable session data. Repeated routing to C did not copy C’s memory elsewhere.

Choose and operate a policy in steps:

  1. Identify the constrained resource. Separate long downloads from CPU-heavy reports when they interfere.
  2. Pick a signal that reflects that resource. For a job service, count waiting jobs only if those jobs have sufficiently comparable costs.
  3. Record when each load report was measured. For example, with one report per second, discard reports older than two seconds and fall back to weighted round robin across ready servers while keeping concurrency limits. Shift traffic gradually and check whether response times rise after adding that work.
  4. Limit work admitted when all servers are full. Choosing the least busy overloaded server does not create spare capacity.

Two extensions are worth recognizing. Least outstanding requests counts unfinished requests rather than connections, which matters when one connection carries many requests. Power of two choices samples two eligible servers and chooses the less loaded of those two. Object-key routing can improve cache reuse, but one extremely popular object can still overload its assigned server; Chapter 15 explains stable placement as membership changes.

Raw and normalized connections select different servers

Raw and normalized connections select different serversCompare the current connection counts: A has eight, B six, and C three. The raw-count rule selects C. Divide those counts by weights four, two, and one. The resulting counts per capacity unit are two, three, and three, so the weighted rule selects A. Numbered arrows correspond to the connection key below. All connections are directional.Next requestAll three serverseligibleLeast connectionsCompare 8,6,3Weighted leastconnectionsCompare 8/4,6/2,3/1Choose C3 raw connectionsChoose ANormalized load 21234Raw and normalized connections select different serversCompare the current connection counts: A has eight, B six, and C three. The raw-count rule selects C. Divide those counts by weights four, two, and one. The resulting counts per capacity unit are two, three, and three, so the weighted rule selects A. Numbered arrows correspond to the connection key below. All connections are directional.Next requestAll three serverseligibleLeast connectionsCompare 8,6,3Weighted leastconnectionsCompare 8/4,6/2,3/1Choose C3 raw connectionsChoose ANormalized load 21234Raw and normalized connections select different serversCompare the current connection counts: A has eight, B six, and C three. The raw-count rule selects C. Divide those counts by weights four, two, and one. The resulting counts per capacity unit are two, three, and three, so the weighted rule selects A. Numbered arrows correspond to the connection key below. All connections are directional.Next requestAll three serverseligibleLeast connectionsCompare 8,6,3Weighted leastconnectionsCompare 8/4,6/2,3/1Choose C3 raw connectionsChoose ANormalized load 21234

Follow the numbered arrows

  1. Next request → Least connectionsuse raw count
  2. Next request → Weighted least connectionsuse capacity-normalized count
  3. Least connections → Choose C3 is smallest
  4. Weighted least connections → Choose A2 is smallest
The same request has two possible destinations depending on the chosen rule. Comparing raw connections picks C. Dividing connections by tested capacity weight picks A. Neither calculation measures the exact work of the next request.
Trace the diagram in words
  1. Compare the current connection counts: A has eight, B six, and C three.
  2. The raw-count rule selects C.
  3. Divide those counts by weights four, two, and one.
  4. The resulting counts per capacity unit are two, three, and three, so the weighted rule selects A.

DRAW. CALCULATE. EXPLAIN.

Compare policies on one snapshot

20 minutes · guided practice

For ready servers A, B, C, use these measurements:

Server Weight Connections MB/s Response time
A 3 12 90 30 ms
B 1 5 10 50 ms
C 2 6 40 20 ms
  1. Select the next server for least connections, weighted least connections, least bandwidth, and least response time.
  2. Divide twelve comparable arrivals by weighted round robin.
  3. Explain one reason the selected server might still be unsuitable.
Your self-check
Compare the worked solution
  1. Least connections chooses B: five is smaller than twelve or six.
  2. Weighted least connections compares 12/3=4, 5/1=5, and 6/2=3. It chooses C.
  3. Least bandwidth chooses B at 10 MB/s. Least response time chooses C at 20 ms.
  4. Weighted round robin uses total weight 3+1+2=6. Twelve arrivals give two per weight unit: A receives six, B two, and C four.
  5. These are rule outputs, not guaranteed fastest results. One connection may carry a large download, measurements may be old, or the tested capacity may not match today’s work. Check those assumptions and limit new work if all servers are full.

The checkboxes record your own assessment. The worked solution gives you a way to check the reasoning.

RETRIEVE BEFORE YOU REVEAL

Keep the important ideas.

Say the answer aloud, then turn the card over.

CARD 01How do the nine policies differ?
  • Round robin and weighted round robin divide arrivals equally or by capacity shares.
  • Connections, response time, bandwidth, and custom load use different observations.
  • IP hash repeats an address-based choice.
  • Random makes independent choices.

First ask which resource limits the incoming work.

CARD 02What does weighted least connections compare?
  1. Divide each active-connection count by its capacity weight.
  2. For A, B, C: 8/4=2, 6/2=3, and 3/1=3.
  3. Choose A, the smallest result.

This works only as well as connections and tested weights represent the work.

CARD 03What does IP affinity fail to guarantee?
  1. IP hash selects from an address, not an account identity.
  2. Many office users can share one address and one destination.
  3. Addresses and server membership can change the mapping.
  4. Failure recovery still requires session data saved beyond the chosen server.
Practise this topic in the revision deck ↗

CHECK THE REASONING

Can you explain the choice?

Answer every question, then finish for an immediate score and an explanation for each answer. Aim for 80%, then revisit any gaps.

1 / 10With three equal servers and 12 similar arrivals, what does round robin target?
2 / 10Weights 4:2:1 serve 14 similar arrivals. What are the ideal weighted-round-robin shares?
3 / 10Active connection counts are A: 8, B: 6 and C: 3. Which server does unweighted least connections choose?
4 / 10Divide active connections by capacity weight: A has 8/4, B has 6/2 and C has 3/1. Which server does the stated weighted-least-connections rule choose?
5 / 10A transfers 80 MB/s, B: 20 MB/s and C: 60 MB/s. Which server does least bandwidth choose?
6 / 10B has the lowest observed response time. What should a latency-aware policy still account for?
7 / 10A thousand office users share one NAT public address. What is an IP-hash risk?
8 / 10Independent uniform random selection sends 12 requests to three servers. Must each receive four?
9 / 10Policy X chooses the lowest CPU use; policy Y chooses the fewest queued jobs. C uses 20% CPU with 10 queued jobs; B uses 50% CPU with 2. What follows?
10 / 10All eligible servers exceed the useful concurrency limit. What is needed in addition to a routing algorithm?
0 of 10 answered

CLOSE THE LOOP

Explain it without the page.

Summarise the mechanism, one trade-off, and one failure mode. Then mark this chapter complete.

Go to the source