If a timeout is the only sure way of detecting a fault, then how long should the timeout be? There is unfortunately no simple answer.
A long timeout means a long wait until a node is declared dead (and during this time, users may have to wait or see error messages). A short timeout detects faults faster but carries a higher risk of incorrectly declaring a node dead when in fact it has only suffered a temporary slowdown (e.g., because of a load spike on the node or the network).
Prematurely declaring a node dead is problematic. If the node is actually alive and in the middle of performing an action (e.g., sending an email), and another node takes over, the action may end up being performed twice. We will discuss this issue in more detail in “Knowledge, Truth, and Lies” and in the related discussion.
When a node is declared dead, its responsibilities need to be transferred to other nodes, which places additional load on those nodes and the network. If the system is already struggling with high load, declaring nodes dead prematurely can make the problem worse. In particular, it could happen that the node actually wasn’t dead but only slow to respond because of overload; transferring its load to other nodes can cause a cascading failure (in the extreme case, all nodes declare each other dead, and everything stops working—see “When an Overloaded System Won’t Recover”).
Imagine a fictitious system with a network that guarantees a maximum delay for packets. Every packet is either delivered within time d or lost, and delivery never takes longer than d. Furthermore, assume that you can guarantee that a non-failed node always handles a request within time r. In this case, you could guarantee that every successful request receives a response within time 2d + r—and if you don’t receive a response within that time, you know that either the network or the remote node is not working. If this was true, 2d + r would be a reasonable timeout to use.
Unfortunately, most systems we work with have neither of those guarantees. Asynchronous networks have unbounded delays (they try to deliver packets as quickly as possible, but there is no upper limit on the time it may take for a packet to arrive), and most server implementations cannot guarantee that they can handle requests within a maximum time (see “Provididng response time guarantees”). For failure detection, it’s not sufficient for the system to be fast most of the time: if your timeout is low, it takes only a transient spike in round-trip times to throw the system off balance.
Network congestion and queueing
When driving a car, travel times on road networks often vary most because of traffic congestion. Similarly, the variability of packet delays on computer networks is most often due to queueing:
-
If several nodes simultaneously try to send packets to the same destination, the network switch must queue them up and feed them into the destination network link one by one (as illustrated in Figure 9-2). On a busy network link, a packet may have to wait a while until it can get a slot (this is called network congestion). If there is so much incoming data that the switch queue fills up, the packet is dropped, so it needs to be resent—even though the network is functioning fine.
-
When a packet reaches the destination machine, if all CPU cores or application threads are currently busy, the incoming request from the network is queued by the operating system until the application is ready to handle it. Depending on the load on the machine, this may take an arbitrary length of time.
-
In virtualized environments, a running operating system is often paused for tens of milliseconds while another virtual machine (VM) uses a CPU core. During this time, the VM cannot consume any data from the network, so the incoming data is queued (buffered) by the VM monitor, further increasing the variability of network delays.
-
As mentioned earlier, to avoid overloading the network, TCP limits the rate at which it sends data. This means additional queueing at the sender before the data even enters the network.
Diagram illustrating network traffic flow with input and output links, showing congestion at port 3 where multiple inputs attempt to send packets to the same destination.
Figure 9-2. If several machines send network traffic to the same destination, its switch queue can fill up. Here, ports 1, 2, and 4 are all trying to send packets to port 3.
Moreover, when TCP detects and automatically retransmits a lost packet, the application does not see the packet loss directly but does see the resulting delay (waiting for the timeout to expire, and then waiting for the retransmitted packet to be acknowledged).
TCP Versus UDP
Some latency-sensitive applications, such as videoconferencing and Voice over IP (VoIP), use UDP rather than TCP. This choice is a trade-off between reliability and variability of delays: as UDP does not perform flow control and does not retransmit lost packets, it avoids some of the reasons for variable network delays (although it is still susceptible to switch queues and scheduling delays).
UDP is a good choice when delayed data is worthless. For example, in a VoIP phone call, there probably isn’t enough time to retransmit a lost packet before its data is due to be played over the speaker. In this case, there’s no point in retransmitting the packet—the application must instead fill the missing packet’s time slot with silence (causing a brief interruption in the sound) and move on in the stream. The retry happens at the human layer instead. (“Could you repeat that please? The sound just cut out for a moment.”)
Variability of network delays
All these factors contribute to the variability of network delays. Queueing delays have an especially wide range when a system is close to its maximum capacity. A system with plenty of spare capacity can easily drain queues, whereas in a highly utilized system, long queues can build up very quickly.
In public clouds and multitenant datacenters, resources are shared among many customers. The network links and switches, and even each machine’s network interface and CPUs (when running on VMs), are shared. Processing large amounts of data can use the entire capacity of network links (saturate them). Because you have no control over or insight into other customers’ usage of the shared resources, network delays can be highly variable if someone near you (a noisy neighbor) is using a lot of resources.
In such environments, you can choose timeouts only experimentally: measure the distribution of network round-trip times over an extended period, and over many machines, to determine the expected variability of delays. Then, taking into account your application’s characteristics, you can determine an appropriate trade-off between failure detection delay and risk of premature timeouts.
Even better, rather than using configured constant timeouts, systems can continually measure response times and their variability (jitter) and automatically adjust timeouts according to the observed response time distribution. The Phi Accrual failure detector (which is used, for example, in Akka and Cassandra), is one way of doing this. TCP retransmission timeouts work similarly.