Process Pauses

Let’s consider another example of dangerous clock use in a distributed system. Say you have a database with a single leader per shard. Only the leader is allowed to accept writes. How does a node know that it is still leader (that it hasn’t been declared dead by the others) and that it may safely accept writes?

One option is for the leader to obtain a lease from the other nodes, which is similar to a lock with a timeout. Only one node can hold the lease at any one time. Thus, when a node obtains a lease, it knows that it is the leader for a certain amount of time, until the lease expires. To remain leader, the node must periodically renew the lease before it expires. If the node fails, it stops renewing the lease, so another node can take over when it expires.

You can imagine the request-handling loop looking something like this:

while (true) {
    request = getIncomingRequest();

    // Ensure that the lease always has at least 10 seconds remaining
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }

    if (lease.isValid()) {
        process(request);
    }
}

What’s wrong with this code? First, it’s relying on synchronized clocks: the expiry time on the lease is set by a different machine (where the expiry may be calculated as the current time plus 30 seconds, for example), and it’s being compared to the local system clock. If the clocks are out of sync by more than a few seconds, the code will start doing strange things.

Second, even if we change the protocol to use only the local monotonic clock, there is another problem: the code assumes that very little time passes between the point that it checks the time (System.currentTimeMillis()) and the time when the request is processed (process(request)). Normally this code runs very quickly, so the 10-second buffer is more than enough to ensure that the lease doesn’t expire in the middle of processing a request.

However, what if an unexpected pause occurs in the execution of the program? For example, imagine the thread stops for 15 seconds around the line that calls lease.isValid before finally continuing. In that case, the lease will likely have expired by the time the request is processed, and another node will already have taken over as leader. However, there is nothing to tell this thread that it was paused for so long, so the code won’t notice that the lease has expired until the next iteration of the loop—by which time it may have already done something unsafe by processing the request.

Is it reasonable to assume that a thread might be paused for so long? Unfortunately, yes. There are various reasons this could happen:

• Contention among threads accessing a shared resource, such as a lock or queue, can cause threads to spend a lot of their time waiting. Such problems are often worse on machines with more CPU cores, and contention problems can be difficult to diagnose.

• Many programming language runtimes (such as the JVM) have a garbage collector that occasionally needs to stop all running threads. In the past, such “stop-the-world” garbage collection pauses would sometimes last for several minutes! With modern GC algorithms this is less of a problem, but GC pauses can still be noticeable (see “Limiting the impact of garbage collection”).

• In virtualized environments, a VM can be suspended (pausing the execution of all processes and saving the contents of memory to disk) and resumed (restoring the contents of memory and continuing execution). This pause can occur at any time in a process’s execution and can last for an arbitrary length of time. This feature is sometimes used for live migration of VMs from one host to another without a reboot, in which case the length of the pause depends on the rate at which processes are writing to memory.

• On end-user devices such as laptops and phones, execution may also be suspended and resumed arbitrarily (e.g., when the user closes the lid of their laptop).

• When the operating system context-switches to another thread, or when the hypervisor switches to a different VM (when running in a VM), the currently running thread can be paused at any arbitrary point in the code. In the case of a VM, the CPU time spent in other VMs is known as steal time. If the machine is under heavy load—that is, if a long queue of threads is waiting to run—it may take some time before the paused thread gets to run again.

• If the application performs synchronous disk access, a thread may be paused waiting for a slow disk I/O operation to complete. In many languages, disk access can happen surprisingly, even if the code doesn’t explicitly mention file access—for example, the Java classloader lazily loads class files when they are first used, which could happen at any time in the program execution. I/O pauses and GC pauses may even conspire to combine their delays. If the disk is actually a network filesystem or network block device (such as Amazon EBS), the I/O latency is further subject to the variability of network delays.

• If the operating system is configured to allow swapping to disk (paging), a simple memory access may result in a page fault that requires a page from disk to be loaded into memory. The thread is paused while this slow I/O operation takes place. If memory pressure is high, this may in turn require a different page to be swapped out to disk. In extreme circumstances, the operating system may spend most of its time swapping pages in and out of memory and get little actual work done (this is known as thrashing). To avoid this problem, paging is often disabled on server machines (if you would rather kill a process to free up memory than risk thrashing).

• A Unix process can be paused by sending it the SIGSTOP signal—for example, by pressing Ctrl-Z in a shell. This signal immediately stops the process from getting any more CPU cycles until it is resumed with SIGCONT, at which point it continues running where it left off. Even if your environment does not normally use SIGSTOP, it might be sent accidentally by an operations engineer.

All these occurrences can preempt the running thread at any point and resume it at a later time, without the thread even noticing. The problem is similar to making multithreaded code on a single machine thread-safe; you can’t assume anything about timing, because arbitrary context switches and parallelism may occur.

When writing multithreaded code on a single machine, we have fairly good tools for making it thread-safe: mutexes, semaphores, atomic counters, lock-free data structures, blocking queues, and so on. Unfortunately, these tools don’t directly translate to distributed systems, because a distributed system has no shared memory—only messages sent over an unreliable network.

A node in a distributed system must assume that its execution can be paused for a significant length of time at any point, even in the middle of a function. During the pause, the rest of the world keeps moving and may even declare the paused node dead because it’s not responding. Eventually, the paused node may continue running, without even noticing that it was asleep until it checks its clock sometime later.

Provididng response time guarantees

As we’ve just discussed, in many programming languages and operating systems, threads and processes may pause for an unbounded amount of time. However, those reasons for pausing can be eliminated if you try hard enough.

Some software runs in environments where a failure to respond within a specified time can cause serious damage. Computers that control the movements of aircraft, rockets, robots, cars, and other physical objects, for example, must respond quickly and predictably to their sensor inputs. In these so-called hard real-time systems, the software must respond by a specified deadline; failure to meet the deadline may cause a failure of the entire system.

Note

In embedded systems, real-time means that a system is carefully designed and tested to meet specified timing guarantees in all circumstances. This meaning is in contrast to the more vague use of the term real-time on the web, where it describes servers pushing data to clients and stream processing without hard response-time constraints.

For example, if your car’s onboard sensors detect that you are currently experiencing a crash, you wouldn’t want the release of the airbag to be delayed because of an inopportune GC pause in the airbag release system.

Providing real-time guarantees in a system requires support from all levels of the software stack. A real-time operating system (RTOS) that allows processes to be scheduled with a guaranteed allocation of CPU time in specified intervals is needed; library functions must document their worst-case execution times; dynamic memory allocation may be restricted or disallowed entirely (real-time garbage collectors exist, but the application must still ensure that it doesn’t give the garbage collector too much work to do); and an enormous amount of testing and measurement must be done to ensure that guarantees are being met.

All of this requires a large amount of additional work and severely restricts the range of programming languages, libraries, and tools that can be used (since most languages and tools do not provide real-time guarantees). For these reasons, developing real-time systems is very expensive, and they are most commonly used in safety-critical embedded devices. Also, “real-time” is not the same as “high-performance”—in fact, real-time systems may have lower throughput, since they have to prioritize timely responses above all else (see “Latency and Resource Utilization”).

For most server-side data processing systems, real-time guarantees are simply not economical or appropriate. Consequently, these systems must suffer the pauses and clock instability that come from operating in a non-real-time environment.

Limiting the impact of garbage collection

Garbage collection used to be one of the biggest reasons for process pauses, but fortunately GC algorithms have improved a lot. A properly tuned collector will now usually pause processes for no more than a few milliseconds. The Java runtime offers collectors such as concurrent mark sweep (CMS), garbage-first (G1), the Z garbage collector (ZGC), Epsilon, and Shenandoah. Each is optimized for different memory profiles, such as high-frequency object creation, large heaps, and so on. By contrast, Go offers a simpler concurrent mark and sweep garbage collector that attempts to optimize itself.

If you need to avoid GC pauses entirely, one option is to use a language that doesn’t have a garbage collector. For example, Swift uses automatic reference counting to determine when memory can be freed, while Rust and Mojo track object lifetimes via the type system so the compiler can determine how long memory must be allocated for.

It’s also possible to use a garbage-collected language while mitigating the impact of pauses. For example, objects can be stored and reused in pools rather than discarded, or data can be allocated off-heap. A more extreme approach is to treat GC pauses like brief planned outages of a node and let other nodes handle requests from clients while one node is collecting its garbage. If the runtime can warn the application that a node soon requires a GC pause, the application can stop sending new requests to that node, wait for it to finish processing outstanding requests, and then perform the GC while no requests are in progress. This trick hides GC pauses from clients and reduces the high percentiles of the response time.

A variant of this idea is to use the garbage collector for only short-lived objects (which are fast to collect) and to restart processes periodically, before they accumulate enough long-lived objects to require a full GC of long-lived objects. One node can be restarted at a time, and traffic can be shifted away from the node before the planned restart, as in a rolling upgrade.

These measures cannot fully prevent GC pauses, but they can usefully reduce their impact on the application.