CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 3 of 6 · 4 min read

Unreliable networks and timeouts

A missing reply has many possible causes, and the sender cannot tell which.

Think of posting a letter and getting no answer. The letter may have been lost. The reader may be away. The reader may have replied and the reply may be lost. From your doorstep these look the same.

The book describes most data centre networks and the internet as asynchronous packet networks: a node can send a message, but nothing is promised about when, or whether, it arrives. When a request gets no response, any of six things may have happened:

  1. The request was lost.
  2. The request waits in a queue and will arrive later.
  3. The remote node failed.
  4. The remote node paused for a while (for example a garbage collection pause) and will answer later.
  5. The remote node processed the request but the response was lost.
  6. The remote node processed the request but the response is delayed.

All six look the same to the sender. The only tool is a timeout: give up after some time. Even then the sender does not know whether the request was carried out, and a queued request may still be delivered later.

Timeout

A timeout is a limit on how long to wait for a reply before treating the request as failed.

Example: a client waits 2 seconds for a server. After 2 seconds without a reply, it tries another server, not knowing whether the first one did the work.

Network faults really happen. The book cites a study of a medium-sized data centre with about 12 network faults per month. Half disconnected one machine and half disconnected a whole rack. Adding duplicate network equipment did not help as much as hoped, because people misconfiguring switches is a major cause. One odd fault is a network card that drops all incoming packets but still sends outgoing ones, so a link may work in one direction only. A network fault that cuts one part off from the rest is called a network partition [not the same as a shard of a database].

Why delays vary: queues. Delay varies mostly because of queueing, like traffic on a road:

  • Several nodes send to one destination, and the switch lines the packets up. A full queue drops packets.
  • The receiving machine has all CPU cores busy, so the operating system queues the request.
  • A virtual machine is paused for tens of milliseconds while another uses the core.
  • TCP slows the sender (flow control), and resends packets that are not acknowledged, which the application sees as delay.

Queues grow fast when a system runs close to its capacity. In shared clouds, a noisy neighbour using lots of network adds more variation.

Choosing a timeout. If the network had a known maximum delay d and a node answered in a known maximum time r, then 2d + r would be a correct timeout. Real systems have neither bound. A short timeout detects failures fast but wrongly declares slow nodes dead. A long timeout waits too long. The book advises measuring round-trip times over a long period to choose, or better, letting the system adjust the timeout from what it observes. The phi accrual failure detector, used in Akka and Cassandra, does this.

Why not a perfect network? The old telephone network reserves a fixed circuit for each call, so there is no queueing and the delay is bounded. Data networks use packet switching because traffic is bursty: a circuit would waste capacity or make transfers slow. So delay stays unbounded.

A worked example. A client calls a service and each reply normally takes about 20 ms. Measured over a day: 99% under 50 ms, and 1% around 400 ms because of queues.

Timeout Effect
30 ms About 10 to 20 percent of healthy calls are treated as failed (made up to show the idea). Retries add load
100 ms Most healthy calls pass. The 1% slow calls are treated as failures and retried
1,000 ms Almost no false alarms, but a dead server takes a full second to notice

There is no value that is both fast and safe. That is why retries need idempotency (module 1) and why detection uses several signals (module 5).

For the curious For the curious

The book notes that UDP, used for calls and video, skips resends and flow control. A late packet is worthless in a call, so it is better to fill the gap with silence than to wait.

Check yourself:

  • A client sends a payment request and gets no reply. Name three possible states of the world.
  • Why is a short timeout dangerous?