3.1.1 A Crash Course in Simple Probability

The probability of an event, A, happening in a certain period is denoted P(A). Probabilities range between zero and one. Zero probability means that the event never occurs; one means that the event certainly occurs. The probability that an event, A, does not occur is 1 – P(A). A and B are independent events if the occurrence of one does not affect the probability of the occurrence of the other. Given independent events A and B, consider the following possibilities and their equations:

For example, if the chance a system fails in a day is .01, the chance the telephone network fails is .02, and the chance the terminal fails is .03, then the chance of all three failing (using Equation 3.1) is .01 • .02 • .03, or 6 • 10⁻⁶. The chance of any one of the three failing (using Equation 3.3) is .01 + .02 + .03, or .06.

Failure rates are often memoryless: If the system has been operating for a month, it is no more likely to fail now than it was a month ago. It is as though in each time unit the system flips the failure coin, and with probability P(A) the coin comes up fail; otherwise, the system keeps working without failure. To illustrate: The chance of your dying in the next ten minutes is just about the same as the chance of your dying tomorrow at this time. In the short term, then, your death rate (hazard) is memory less. Of course, when you are 100 years old the hazard function is likely to be higher.

Failure rates are such tiny numbers (say, 10⁻⁶) that the reciprocals of the probabilities are used. If the event rate P(A) is memory less and much less than one, the mean time (average time) before the event is expected to occur MT(A) is the reciprocal of the rate, or 1/P(A):

The mean time to failure of the components used in the previous example is 100 days (1/.01) for the system, 50 days (1/.02) for the network, and 33 days (1/.03) for the terminal. The mean time to any of them failing is about 17 days (1/.06), and the mean time to all of them failing is 170,000 days (1/(6 • 10⁻⁶)).

System designers are often presented with modules A, B, C, which fail independently and have mean times to failures MT(A), MT(B), MT(C). If they are simply combined into a group G, then the failure of any one is likely to fail the whole group. What is MT(G)? Using Equation 3.3, the probability, P(G), that any one of them fails is approximately P(A) + P(B) + P(C). So, using Equation 3.4:

This is the math needed for this chapter. But, it is very important to understand three key assumptions that underlie these assumptions: (1) The event probabilities must be independent, (2) the probabilities must be small, and (3) the distributions must be memoryless. Exercises 1 and 2 explore these points.

3.1.2 An External View of Fault Tolerance

Fault tolerance is a major concern of transaction processing. Early batch transaction processing systems achieved fault tolerance by using the old master-new master technique, in which the batch of transactions accumulated during the day, week, or month was applied to the old master file, producing a new master file. If the batch run failed, the operation was restarted. To protect against loss or damage of the transaction file (typically a deck of cards), or the master file (typically a tape), an archive copy of each was maintained. Recovery consisted of carefully making a copy of the old master or transaction batch, then using the copy to rerun the batch (see Figure 3.1). Copies of the old masters were retained for five days, then week-old, month-old, and year-old copies were kept. In addition, all transaction inputs were kept. With this data, any old state could be reconstructed.

Programs had internal checks to detect missing and incorrect data. When data was corrupted or missing, the redundant data in the old masters and in the transaction histories made it possible to reconstruct a correct current state.

This design tolerated any single failure and could tolerate several multi-failure scenarios. A failure might delay the batch processing, but the system could tolerate any failure short of destruction of both the archive and active copies of the files. In modern terminology, the old master-new master scheme tolerates any single fault; it is single-fault tolerant. It could be made n-fault tolerant by making n + 1 copies of each item, with n + 1 tape drives and operators, and storing them in n + 1 archives. But this was rarely done—single-fault tolerance was usually considered adequate, especially since the master file could probably be reconstructed from the old, old master (the Sunday Master in Figure 3.1) and the log (all the transactions since Sunday).

The more modern version of the same system is shown in Figure 3.2. In that system, the transactions are not batched but are processed while the customer waits. Using online transaction processing, or OLTP, the database is continuously updated by transactions. The new master database has been replaced by the online database, and the archive has been replaced by a second, geographically remote data center. This second center has a current replica of the data and can take over service in case the primary data center fails.

The bank with the system depicted in Figure 3.2 has gone to considerable lengths to provide its customers with a highly available service. It bought dual fault-tolerant data centers, dual telephone networks, and installed dual automated teller machines (ATMs) at each kiosk. In this example, the ATMs are the most unreliable component of the system, yielding about 99% availability. To mask the unreliability of the ATMs, the bank puts two at each customer site. If one ATM fails, the client can step to the adjacent one to perform the task. This is a good example of analyzing the overall system availability and applying redundancy where it is most appropriate.

Figure 3.2 raises the issue of what it means for a system of many components to be available. If the bank in that figure has 10,000 ATM kiosks, some kiosks (pairs of ATMs) will be out of service at any instant. In addition, it is always possible that the database is down, or at least the part that some customer wants to access is unavailable (being recovered). The system is probably never completely “up,” so the concept of system availability becomes:

System availability is usually expressed as a percentage. To apply this idea, suppose the ATMs in Figure 3.2 average one unscheduled outage every 100 days, and the problem takes on average a day to fix.¹ Such a high failure rate (1%) dominates the system availability. From the customer’s perspective the system availability is 99% (=100% – 1%) without the duplexed ATMs. If the ATMs are duplexed at each site and if they have independent failure modes, then the customer is denied service only if both ATMs are broken. What is the chance of that? Using Equation 3.1, if the probability of one ATM failing in a day is 1%, then the chance of both breaking in the same day is .01% (.01 • .01). The ATM-pair availability is therefore 99.99%. Using Equation 3.4, this is a 10,000-day mean time to both failing. With 10,000 such kiosks, only one would normally be out of service at any instant.

A 99% availability was considered good in 1980, but by 1990 most systems are operating at better than 99.9% availability. After all, 99% availability is 100 minutes per week of denied service. As the nines begin to pile up in the availability measure, it becomes more convenient to think of availability in terms of denial-of-service measured in minutes per year. For example, 99.999% availability is about 5 minutes of service denial per year (see Table 3.3). Even this metric, though, is a little cumbersome so we introduce the concept of availability class, or simply class. This metric is analogous to the hardness of diamonds or the class of a clean room:

Alternatively, the denial-of-service metric can be measured on a system-wide basis or on a per-customer basis. To see the per-customer view, consider the 99% available ATM that denies service to a customer an average of one time in 100 tries. If the customer uses an ATM twice a week, then a single ATM will deny a customer service once a year on average (≈ 2 • 52 weeks = 104 tries). A duplexed ATM will deny the customer service about once every hundred years. For most people, this is the difference between rarely down and never down.

To give a sense of these metrics, nuclear reactor monitoring equipment is specified to be class 5, telephone switches are specified to be class 6, and in-flight computers are specified to be class 9. In practice, these demanding specifications are sometimes met.

3.2.1 Fault, Failure, Availability, Reliability

A system can be viewed as a single module, yet most systems are composed of multiple modules. These modules have internal structures consisting of smaller modules. Although this presentation discusses the behavior of a single module, the terminology applies recursively to modules with internal modules.

Each module has an ideal specified behavior and an observed behavior. A failure occurs when the observed behavior deviates from the specified behavior. A failure occurs because of an error, or a defect in the module. The cause of the error is a fault. The time between the occurrence of the error and the resulting failure is the error latency. When the error causes a failure, it becomes effective; before that, the failure is latent (see Figure 3.4).

For example, a programmer’s mistake is a fault. It creates a latent error in the software. When the erroneous instructions are executed with certain data values, they cause a failure and the error becomes effective. As a second example, a cosmic ray (fault) may discharge a memory cell, causing a memory error. When the memory is read, it produces the wrong answer (memory failure), and the error becomes effective.

The observed module behavior alternates between service accomplishment, when the module acts as specified, and service interruption, when the module’s behavior deviates from the specified behavior. These states are illustrated in Figure 3.4.

3.2.2 Taxonomy of Fault Avoidance and Fault Tolerance

Module reliability can be improved by reducing failures, and failures can be avoided by valid construction and by error correction. The following taxonomy of validation and correction from the IFIP Working Group [Laprie 1985] may help to define the terms.

Validation can remove errors during the construction process, thus ensuring that the constructed module conforms to the specified module. Since physical components fail during operation, validation alone cannot ensure high reliability or high availability. Error correction reduces failures by using redundancy to tolerate faults. Error correction is of two types.

The first type of error correction, latent error processing, tries to detect and repair latent errors before they become effective. Preventive maintenance is an example of latent error processing. The second type, effective error processing, tries to correct the error after it becomes effective. Effective error processing can either mask the error or recover from the error.

Error masking uses redundant information to deliver the correct service and to construct a correct new state. Error correcting codes (ECC) used for electronic, magnetic, and optical storage are examples of masking. Error recovery denies the requested service and sets the module to an error-free state. Error recovery can take two forms.

The first form of error recovery, backward error recovery, returns to a previous correct state. Checkpoint/restart is an example of backward error recovery. The second form, forward error recovery, constructs a new correct state. Redundancy in time, such as resending a damaged message or rereading a disk page, is an example of forward error recovery.

3.2.3 Repair, Failfast, Modularity, Recursive Design

Section 3.7 specifies the correct behavior and some faults of the classic software modules: processes, messages, and storage. A failure that merely constitutes a delay of the correct behavior—for example, responding in one day rather than in one second—is called a timing failure. Faults can be hard or soft. A module with a hard fault will not function correctly—it will continue with a high probability of failing—until it is repaired. A module with a soft fault appears to be repaired after the failure. Soft faults are also known as transient or intermittent faults. Timing faults, for example, are often soft.

Recall that the time between the occurrence of a fault (the error) and its detection (the failure) is called the fault latency. A module is failfast if it stops execution when it detects a fault (stops when it fails), and if it has a small fault latency (the fail and the fast). The term failstop is sometimes used to mean the same thing.

As shown later, failfast behavior is important because latent errors can turn a single fault into a cascade of faults when the recovery system tries to use the latent faulty components. Failfast minimizes fault latency and so minimizes latent faults.

Modules are built recursively. That is, the system is a module composed of modules, which in turn are composed of modules, and so on down to leptons and quarks. The goal is to start with ordinary hardware, organize it into failfast hardware and software modules, and build up a system (a super module) that has no faults and, accordingly, is a highly available system (module). This goal can be approached with the controlled use of redundancy and with techniques that allow the super-module to mask, or hide, the failures of its component modules. Many examples of this idea appear throughout this chapter and this book.

3.3.1 Outages Are Rare Events

In former times, everyone knew why computers failed: It was the hardware. Now that hardware is very reliable, outages (service unavailability) are rare, and, since much of our experience is anecdotal, patterns are not so easy to discern. The American telephone network had two major problems in 1990. In one outage, a fire in a midwest switch disabled most of the Chicago area for several days; in another outage, a software error clogged the long-haul network for eight hours. The New York Stock Exchange had four outages in the 1980s. It closed for a day because of a snowstorm, it closed for four hours due to a fire in the machine room, it closed 45 seconds early because of a software error, and trading stopped for three hours due to a financial panic. The Internet was accidentally clogged by a student one day, and so on.

If we look at hundreds of events from many different fault-tolerant systems, the main pattern that emerges is that these events are rare—in fact, very rare. Each is the combination of special circumstances. Some patterns do emerge, however, if we look at the sources of failures.

Perhaps the first thing to notice from the anecdotes above, and this is borne out in the broader context as well, is that few of the outages were caused by hardware faults. Fault-tolerance masks most hardware faults. If a fault-tolerant system failed due to a hardware fault, there was probably also a software error (the software should have masked the hardware fault) or an operator error (the operator did not initiate repair) or a maintenance error (all the standby spares were broken and had not been repaired) or an environmental failure (the machine room was on fire). As explained in greater detail in Sections 3.5 and 3.6, hardware designers have developed very simple and effective ways of making arbitrarily reliable hardware, and software designers have developed ways to mask most of the residual hardware faults. As hardware prices plummet, the use of these techniques is becoming standard. Outages (denial of service) can be traced to a few broad categories of causes:

This taxonomy gives considerable latitude to interpretation. For instance, if a disgruntled operator destroys the system, is the damage due to sabotage (environment) or operations? Sabotage (environment) is probably the correct interpretation, because it was not a simple operations or maintenance mistake. If the system is located in an area of intense electrical storms, but lacks surge protection, is environment or process the cause? Process should probably be held accountable, because the problem has a solution that the customer has not installed.

3.3.2 Studies of Conventional Systems

Given this taxonomy, what emerges from measurements of “real” systems? Unfortunately, that is a secret. Almost no one wants to tell the world how reliable his system is. Since hundreds or thousands of systems must be examined to see any patterns, there is little hope of forming a clear picture of the situation.

The most extensive public study was done by the Japanese Information Processing Development Corporation (JIPDEC) in 1985. It surveyed the outages reported by 1,383 institutions in 1985 [Watanabe 1986]. The institutions reported 7,517 outages, with average durations of 90 minutes, resulting in a MTTF of about ten weeks and an availability of 99.91%. The study is summarized in Figure 3.5.

This study is especially interesting since these are not fault-tolerant systems. They are just ordinary computers managed by people who have a justly deserved reputation for careful planning and good quality. These statistics compare favorably with the best numbers reported by comparable groups in the United States, and are better by a factor of ten than typical reports (see, for example, the study by Mourad [1985]).

The categories shown in Figure 3.5 do not correspond exactly to the ones introduced earlier; they lump hardware, vendor software, and vendor maintenance together. But the study shows one thing very clearly: if the vendor provided perfect hardware, software, and maintenance, the system MTTF would be four months (this is an application of Equation 3.5). If the goal is to build systems that do not fail for years or decades, then all aspects of availability must be addressed—simple hardware fault tolerance is not enough.

3.3.3 A Study of a Fault-Tolerant System

A more recent study of a fault-tolerant system provides a similar picture. Unfortunately, the study was based on outages reported to the vendor, and therefore it grossly underreports outages due to environment, operations, and application software. It really captures only the top wedge of the figure above. But since data is so scarce in this area, the results are presented with that caveat. The study covered the reported outages of Tandem computer systems between 1985 and 1990, encompassing approximately 7,000 customer years, 30,000 system years, 80,000 processor years, and over 200,000 disk years. The summary information for three periods is shown in Table 3.6.

Table 3.6 summarizes the statistical base, and Figures 3.7 and 3.8 display the information by category. They show the causes of outages and the historical trends: Reported system outages per 1,000 years (per millennium) improved by a factor of two by 1987 and then held steady. Most of the improvement came from improvements in hardware and maintenance, which together shrank from 50% of the outages to under 10%. By contrast, operations grew from 9% to 15% of outages. Software’s share of the problem got much bigger during the period, growing from 33% to more than 60% of the outages.

Figure 3.7 seems to imply that operations and software got worse, but that is not the case. Figure 3.8 shows that software and operations MTTF stayed about constant, while the other fault sources improved considerably.

Two forces explain the maintenance improvements: technology and design. Disks give the best example of both forces. In 1985, each disk had to be serviced once a year. This involved powering down the disk, replacing an air filter, adjusting the power system, and sometimes adjusting head alignment. In addition, the typical 1985 disk required one unscheduled service call per year for repair. This resulted in 32,000 tasks per year in 1985 for customer engineers, and it created many opportunities for mistakes. In addition, the disk cabinets and connectors were not designed for maintenance, rendering maintenance tasks awkward and requiring special tools. If technology and design had not changed, engineers would have been performing 150,000 maintenance tasks per year in 1989—the equivalent of 175 full-time people just doing the error-prone task of disk maintenance.

Instead, 1990-vintage disks have no scheduled maintenance. Fiber-optic connectors reduce cabling and connectors by a factor of 20, and installation and repair require no tools (only thumb screws are used). All field-replaceable units have built-in self-test and light-emitting diodes that indicate correct operation. In addition, disk MTTF rose from 8,000 hours to over 100,000 hours (observed) since 1985. Disk controllers and power supplies experienced similar dramatic improvements. The result was that the disk population grew ba factor of five while the absolute number of outages induced by disk maintenance shrank by a factor of four—a 2,000% improvement. Almost all the reported disk maintenance problems were with older disks or were incident to installing new disks.

This is just one example of how technology and design have improved the maintenance picture. Since 1985, the size of Tandem’s customer engineering staff has held almost constant and shifted its focus from maintenance to installation, even while the installed base tripled. This is an industry trend; other vendors report similar experience. Hardware maintenance is being simplified or eliminated.

Other hardware experienced a similar improvement in MTTF. Based on Table 3.6, during 1989 there were well over 30,000 hardware faults, yet only 29 resulted in a reported system outage. The vast majority were masked by the software (the Tandem system is single-fault tolerant, requiring two hardware faults to cause an outage). The MTTF of a duplexed pair goes up as the square of the MTTF of the individual modules (see Section 3.6). Thus, minor changes in module MTTF can have a dramatic effect on system MTTF. The clear conclusion is that hardware designers did a wonderful job. Hardware faults were rare, and all but 4% of the ones that did occur were masked by software.

While hardware and maintenance show a clear trend toward improvement, operations and software did not improve. The reason for this lies in the fact that few tools were provided to the operators; thus there is no reason to expect their performance to have changed. According to Figure 3.8, every 150 system-years some operator made a mistake serious enough to crash a system. Clearly, mistakes were made more frequently than that, but most operations mistakes were masked by the system, which has some operator fault tolerance.

Operations mistakes were split evenly between two broad categories: configuration and procedures. Configuration mistakes involve such things as having a startup file that asks the transaction manager to reinitialize itself. This works fine the first time the system starts, but it causes loss of transactions and data integrity when the system is restarted from a crash. Mixing incompatible software versions or using an old version of software are common configuration faults. The most common procedural mistake is letting the system fill up by allowing a file to get so big that either there is no more disk space for it or no new records can be added to it.

No clearer pattern of operations faults emerges from the Tandem study. The basic problem of improving operations is that the only known technique is to eliminate or automate the operations process, replacing operators with software.

As Figure 3.7 shows, software is a major source of outages. The software base (number of lines of code) grew by a factor of three during the study period, but the software MTTF held almost constant. This reflects a substantial improvement in software quality. But if these trends continue, the software will continue to grow at the same rate that the quality improves, and software MTTF will not improve. The software in this study uses many of the software fault tolerance techniques described later in this chapter. But that is not enough; a tenfold improvement in software quality is needed to achieve Class 5 availability. At present, no technique offers such an improvement without huge expense. Section 3.6 surveys the most effective approaches: N-version programming and process-pairs combined with transactions.

Thus far, we examined the failure rates of whole systems. We now look at typical failure rates for system components such as processors, disks, networks, and software.

3.5.1 The Basic N-Plex Idea: How to Build Failfast Modules

Failfast modules are easily constructed from ordinary hardware. The simplest design, called pairing or duplexing, connects the inputs and outputs of two modules to a comparator that stops if the module outputs disagree; this is the failfast aspect of the design. Although a pair fails about twice as often as a single module, a failfast module gives clean failure semantics; it also reduces the number of cases fault-tolerant software needs to deal with by converting all failures to a very simple class: stopping. To provide both failfast behavior and increased module MTTF, modules are n-plexed, and a voter takes a majority of their outputs. If there is no majority, the voter stops the n-plex module. The most common case in the n-plex design in which n is greater than 2 (n = 2 is simply pairing) is n = 3. This is generally called triple module redundancy, or TMR. The double and triple redundancy cases are shown in Part A of Figure 3.13.

The basic n-plex design generalizes to a recursive one that allows failfast modules to be aggregated into bigger failfast modules, and that tolerates voter failures and connector failures. In that design, each n-plexed module has n voters and n outputs (see Part B of Figure 3.13).

3.5.2 Failfast versus Failvote Voters in an N-Plex

As the voting scheme is described in the previous section, the voter requires that a majority of the modules be available. If there is no majority, the voter stops. This is called failvote. An alternative scheme, called either failfast voting or failfast represents a fundamental refinement. This scheme has the voter first sense which modules are available and then use the majority of the available modules. Thus, a failfast voter can operate with less than a majority of the modules.

If each of the component modules is failfast, then a failfast voter can operate by observing the outputs of the non-faulty modules. In theory, a voter combining the outputs of failfast sub-modules never detects a mismatch; it just detects missing votes from failed modules. For example, disk modules are usually assumed to be failfast. A failfast voter managing a pair of disks can detect disk failures and can still operate if only one of the two disks is functional. This permits the supermodule (disk pair) to function with only one module.

Even if the component modules are not failfast, the voter can still operate with failfast voting. To do so, a module is marked as failed each time it miscompares, and the voter ignores its inputs until it is repaired. Thus the voter forms a majority from the non-faulty modules. Take as an example a 10-plexed module composed of ordinary (not necessarily failfast) modules. A failvote voter operating the 10-plex will fail when five modules have failed. A failfast voter will continue operating until the ninth module fail, because a failfast voter on non-failfast modules requires only two available modules to operate. This indicates that fail-fast voting has better reliability than failvote voting.

Consider a failvote n-plex and ignore failures of the voters (comparators) and connectors. (For the scenario that follows, refer to Figure 3.14.) Given modules, each of which is failfast, with an MTTF of 10 years, the MTTF of the paired supermodule is about five years (10/2 years, using Equation 3.6).² The MTTF for the triplex system is about 8.3 years (using Equation 3.6, it is 10/3, or about 3.3 years to the first failure and 10/2, or 5 years to the second and fatal failure). The analysis of pair-and-spare is a little more tricky, since the first pair will fail the first time one of the four processors fails. Equation 3.6 says that is expected to happen in 10/4, or 2.5 years. After one pair fails, the remaining pair is expected to operate for five years, as computed here. Thus, pair and spare has a 7.5-year MTTF. This logic (simply adding the times), incidentally, shows how the memoryless property simplifies analysis.

So far, all this redundancy does not look like a good idea. All three schemes cut the MTTF, making failure more likely. However, there are two extenuating circumstances. First, and most important, n-plexing yields failfast modules. Failfast modules have vastly simplified failure characteristics; they either work correctly or they stop. This simplicity makes it possible to reason about their behavior. If modules can have arbitrary failure behavior, there is little hope of building fault-tolerant systems.

The second benefit of triplexing and pair-and-spare is that if soft (transient) faults dominate, then pair-and-spare or TMR can be a big improvement (recall that modules continue to function after soft errors). Both schemes mask virtually all soft faults, and two of the three would have to have exactly the same fault for the voter to pass on the faulty result. Thus if the ratio of hard faults to total faults is 1:100, and if TMR masks all transient faults, the module MTTF rises by a factor of 100 to become 1,000 years MTTF; in addition, TMR failvote improves the MTTF from about 8.3 years to about 8,333 (≈10,000 • (1/3 + 1/2)) using Figure 3.14).

3.5.3 N-Plex plus Repair Results in High Availability

The key to getting this hundred-fold MTTF improvement is repairing the faulted module immediately after the fault. If the module has no internal state, recovery from a soft fault is easy; the module goes on to compute the next state from its next inputs. But typically, the faulted module is a processor or memory with an incorrect internal state. To repair it, the design must somehow resynchronize the faulted module with the other two modules. The easy way to do this is to reset all the modules to their initial states, but this will probably reflect the fault outside the module. Mechanisms to resynchronize the faulted module without disrupting the service of the other two modules are usually complex and ad hoc. For storage modules, such mechanisms consist of rewriting the state of the faulted storage cell. For processing modules, they generally set the state (registers) of the faulted processor to the state of one of the good processors.

The huge benefit of tolerating soft faults is just one aspect of the key to availability: repair. Soft errors postulate instant mean time to module repair; when the module faults, it is instantly repaired. Failvote duplex and failfast TMR both provide excellent reliability and availability if repair is added to the model.

The failure analysis of a failvote n-plex is easy to follow. Each module goes through the cycle of operation, fault, repair, and then operation again. The supermodule (the n-plex module) will fail if all the component modules fail at once. More formally, the n-plex will fail if all but one module are unavailable, and then the available module fails. The analysis first determines the probability that a particular module, N, will be the last to fail (all others have already failed and are still down). The probability that a particular module is unavailable is

$P_1=MTTR/\left(MTTF+MTTR)\right)=\left(MTTR/MTTF\right)\text{since}\hspace{1em}MTTR\ll MTTF.$ (3.7)

Using Equation 3.1 with Equation 3.7, the probability that the other n – 1 modules are unavailable is then

$P_{n-1}=P_1^{n-1}={\left(MTTR/MTTF\right)}^{n-1}$ (3.8)

Using Equation 3.4, the probability that a module, N, fails is

$P_f=1/MTTF.$ (3.9)

Equation 3.1 can combine Equations 3.8, and 3.9 to compute the probability that the last module N fails, and that all the other modules are unavailable:

$P_f•P_{n-1}=\left(1/MTTF\right)•{\left(MTTR/MTTF\right)}^{n-1}$ (3.10)

This is the probability that module N causes the n-plex failure. There are n such identical modules. To compute the probability that any one of these n modules causes an n-plex failure, Equation 3.10 is combined n times using Equation 3.3:

$P_{n-plex}=\left(\frac{n}{MTTF}\right)•{\left(\frac{MTTR}{MTTF}\right)}^{n-1}$ (3.11)

Equation 3.11 is therefore the probability that a failvote n-plex will completely fail. Using Equation 3.4 with Equation 3.11 gives the mean time to total failure for a failfast n-plex:

$MTT{F}_n=\left(\frac{MTTF}{n}\right)•{\left(\frac{MTTF}{MTTR}\right)}^{n-1}$ (3.12)

Applying Equation 3.12 and using the 1-year MTTF with a 4-hour MTTR,

$MTT{F}_{pair}=\frac{MTT{F}^2}{2MTTR}=1095\hspace{1em}\text{years}.$ (3.13)

The corresponding result for a TMR group is

$MTT{F}_{TMR}=\frac{MTT{F}^3}{3MTT{R}^2}=1,600,000\hspace{1em}\text{years}.$ (3.14)

Starting with two modest one-year MTTF modules, we have now built a one-millennium module! Thousands of these could be used to build a supermodule with a one-year MTTF. The construction can be repeated to obtain a system with a one-millennium MTTF—a powerful idea (see Table 3.15).

3.5.4 The Voter’s Problem

There is a nasty flaw in the previous reasoning: Namely, the assumption that the voters and connectors are faultless. The recursive construction was careful to replicate the voters and connectors for this very reason, so that the construction actually tolerates failures in connectors and voters. Fundamentally, however, system reliability and availability are limited by the reliability of the top-level voters.

In some situations, voting can be carried all the way to the physical system. For example, by putting three motors on the airplane flaps or reactor rods and having them “vote” at the physical level, two can overcome the force of the third. Often the voter cannot be moved to the transducer. In those situations, the message itself must be failfast—it must have a checksum or some other consistency check—and the client must become the voter. Two examples of moving the voter to the client appear in Figure 3.16.

The first example in Figure 3.16 is a repetition of the banking system depicted in Figure 3.2. It shows the failure rates for the various system components and indicates that the ATM is the least reliable component. But using the pair-and-spare scheme produces instant repair times (repair in the sense of providing service): If one ATM fails, the client can step to the adjacent ATM. That moves the voter into the customer. If each ATM is failfast, the customer can operate with a correct one.

The second example in Figure 3.16 shows a disk pair. Data is read from either disk and written to both. Each disk and each controller is a failfast module. In addition, the wires are failfast, because the messages they carry are checksum protected. If the message checksum is wrong, the message is discarded. But the client (the processor in this case) must try the second channel (the second path) to the device if the first fails, much as the bank client must try the second ATM if the first fails. These are both examples of moving the voter into the client.

3.5.5 Summary

The foregoing presentation is from the traditional perspective of hardware fault tolerance. The next two sections develop similar ideas from a software perspective. To bridge these two perspectives, it is important to see the following connections:

To summarize, reliability plus repair means doing the right thing eventually; the module may stop, but eventually it is repaired and continues to function. Failfast is the A of ACID, and reliability plus repair are the A, C, and D of ACID. High availability modules can be built by n-plexing failfast modules and by using a failfast voting scheme.

Historically, transaction processing systems have been geared toward reliability—never losing the database. But for many reasons, they often delivered poor availability. Many TP systems were designed in an era when one failure per day was considered typical and when 98% availability was considered high. Technology advances and declining hardware prices have shifted the emphasis from reliability to availability, which means doing the right thing and doing it on time. Repair is the key to reliability, since with enough repair the job eventually gets done. Instant repair is the key to high availability: It almost always masks the failure such that module failures do not cause a denial of service. Combined with failfast, instant repair makes all single faults appear to be soft faults. Both TMR and pair-and-spare provide instant MTTR for hardware faults. These techniques make it possible to buy conventional components off the shelf and combine them to build super-reliable and super-available modules. The next sections show how to achieve instant software MTTR, implying highly available software systems.

3.6.1 N-Version Programming and Software Fault Tolerance

The main hope of dealing with design faults is for designers to develop techniques to tolerate design faults, much as hardware designers are able to tolerate hardware faults. Of course, hardware design is software, so hardware designers have the same problem: Their techniques to tolerate physical hardware faults do not mask design faults. There are two major software fault tolerance techniques:

Both these approaches are statistical and both have merit, but both can fail if there is a fault in the original specification.

The n-version programming approach is expensive to implement and to maintain. That is because to get a majority, n must be at least 3. In addition, the n-version programming approach suffers from the “average IQ” problem. If n students are given a quiz, all of them will get the easy problems right, some will get the hard problems right, and almost none will get the hardest problem right (if it is a good quiz). Also, several will make the same mistakes. An n-version program taking this quiz would score in the 60th percentile. It would solve all the easy problems and might even solve a few of the harder problems. However, there would be no consensus, or consensus would be wrong, on the hardest problems.

A final problem with n-version programming is that module repair is not trivial. Since each module has a completely different internal state, one cannot simply copy the state of a good module to the state of a failing module. Without repair, n-plexing has a worse MTTF than simplexing (see Table 3.15).

N-version programming is often used in high-budget projects employing many low-budget programmers. You can imagine the controversy surrounding this idea. Better results might be obtained by spending three times more on better-quality programmers and on better infrastructure, or on more careful testing of one program.

3.6.2 Transactions and Software Fault Tolerance

Transactions are even more of a gamble. When a production computer system crashes due to software, computer users do not wait for the software to be fixed. They don’t wait for the next release, but instead restart the system and expect it to work the next time; after all, they reason, it worked yesterday. By using transactions, a recent consistent system state is restored so that service can continue. The theory is that it was a Heisenbug that crashed the system. A Heisenbug is a transient software error (a soft software error) that only appears occasionally and is related to timing or overload. Heisenbugs are contrasted to Bohrbugs which, like the Bohr atom, are good, solid things with deterministic behavior.

Although this is preposterous, the test of a theory is whether it explains the facts—and the Heisenbug theory does explain many observations. For example, a careful study by Adams [1984] of all software faults of large IBM systems over a five-year period showed that most bugs were Heisenbugs. The Adams study dichotomized bugs into benign bugs—ones that had bitten only one customer once—and virulent bugs—ones that had bitten many customers or had bitten one customer many times. The study showed that the vast majority (well over 99%) of the bugs were benign (Heisenbugs). Adams also concluded from this study that customers should not rush to install bug fixes for benign bugs, as the expense and risk are unjustified.

There are several other instances of the Heisenbug idea. Most large software systems have data structure repair programs that traverse data structures, looking for inconsistencies. Called auditors by AT&T and salvagers by others, these programs heuristically repair any inconsistencies they find. The code repairs the state by forming a hypothesis about what data is good and what data is damaged beyond repair. In effect, these programs try to mask latent faults left behind by some Heisenbug. Yet, their techniques are reported to improve system mean times to failure by an order of magnitude (for example, see the discussion of functional recovery routines in Mourad [1985] or in Chapter 8 of this book).

Heisenbug proponents suggest crashing the system and restarting at the first sign of trouble; this is the failfast approach. It appears to make things worse, since the system will be crashing all the time, and the database and network will be corrupted when the system is restarted. This is where transactions come in. Transactions, and their ACID properties, have four nice features:

These features mean that transactions allow the system to crash and restart gracefully; the only thing lost is the time required to crash and restart. Transactions also limit the scope of failure by perhaps only undoing one transaction rather than restarting the whole system. But the core issue for distributed computing is that the whole system cannot be restarted; only pieces of it can be restarted, since a single part generally doesn’t control all the other parts of the network. A restart in a distributed system, then, needs an incremental technique (like transaction undo) to clean up any distributed state. Even if a transaction contains a Bohrbug, the correct distributed system state will be reconstructed by the transaction undo, and only that transaction will fail.

The programming style of failfast software designs is called defensive programming by analogy with the defensive automobile driving style advocated by traffic-safety experts. Defensive programming advocates that every software module check all its inputs and raise an exception if the inputs are incorrect. This essentially makes the software module failfast. The module checks all its parameters, and as it traverses internal data structures it checks their integrity. To give a specific example, a program traversing a doubly linked list checks the back-pointer in the next block to be sure that it points to the previous block, and the program checks other redundant fields in the block for sanity. If a list element does not satisfy these tests, then an error has been detected, and it is repaired by discarding the block or by repairing it. Whenever a module calls a subroutine, the callee checks the parameters for sanity, and the caller checks the routine’s results. In case an error is found, an exception handler is invoked. Exception handlers are much like the repair programs mentioned earlier in this section. The exception handler either masks the exception (if it is an internal inconsistency that can be repaired), or the module reflects the exception back to the caller (if it is the caller’s error). In extreme cases, the exception handler cannot mask the fault and, consequently, reflects it as a transaction abort, a subsystem restart, or another coarse form of recovery.

Failfast creates a need for instant crash and restart. This again may seem a preposterous approach, but computer system architectures are increasingly adopting this approach. The concept of process pair (covered in Subsection 3.7.3) specifies that one process should instantly (in milliseconds) take over for the other in case the primary process fails. In the current discussion, we take the more Olympian view of system pairs, that is two identical systems in two different places. The second system has all the data of the first and is receiving all the updates from the first. Figure 3.2 has an example of such a system pair. If one system fails, the other can take over almost instantly (within a second). If the primary crashes, a client who sent a request to the primary will get a response from the backup a second later. Customers who own such system pairs crash a node once a month just as a test to make sure that everything is working—and it usually is.

If Heisenbugs are the dominant form of software faults, then failfast plus transactions plus system pairs result in software fault tolerance. Geographically remote system pairs tolerate not just Heisenbugs, but many other problems as well. They tolerate environmental faults, operator faults, maintenance faults, and hardware faults. Two systems in two different places are not likely to have the same environmental problems: They are on different power grids, different phone grids, and different earthquake faults, and they have different weather systems overhead. They have independent operations staffs, different maintenance personnel, and different hardware. All this means that the two systems have largely independent failure modes. Section 12.6 develops the concept of system pairs in more detail.

3.6.3 Summary

Software faults are the dominant source of system failures. All other faults can be masked with a combination of redundancy, geographic diversity, and software to automate tasks. Software can automate system operations and mask operations and maintenance failures. Software faults, however, remain an unsolved problem.

There are two approaches to software fault tolerance: n-version programming and transactions. The two approaches could be combined. Advocates of n-version programming aim to combine several incorrect programs into a better, more reliable one. N-version programming may also be a good way to write failfast programs. Transaction advocates aim to detect incorrect programs and minimize their effects by undoing them. Transactions encourage a failfast design by allowing the system to quickly crash and restart in the most recent consistent state. By having a standby system, restart can begin within milliseconds.

3.7.1 An Overview of the Model

The model describes each aspect of the system—storage, processors, and communications—by presenting a program that simulates the behavior of such entities, complete with their failure characteristics. For example, a storage module reads and writes data at storage addresses, but it also occasionally writes the data to the wrong place, invalidates a page, or damages the whole store (the latter two events require the store to be repaired). Given these errant storage modules, the presentation then shows programs to mask the failures through failvote duplexing and writes a program to repair the failures in the background.

The presentation then models processes and messages. Messages can be lost, duplicated, delayed, corrupted, and permuted. By implementing sessions, timeouts, and message sequence numbers, all message failures are converted to lost messages. By combining this simple failure model with message acknowledgment and sender timeout plus message retransmission, the message system becomes highly available.

These techniques for building reliable stores and reliable messages demonstrate how software masks hardware faults, but they have little to do with masking software faults. Still, the presentation is instructive in that it sets the stage for the software fault tolerance discussion that follows.

Processes fail by occasionally being delayed for some repair period, having all their data reset to the null state, and then having all their input and output messages discarded. The presentation then uses this model to show how to build process-pairs. One process, called the primary, does all the work until it fails; then the second process, called the backup, takes over for the primary and continues the computation. During normal processing, the primary periodically sends I’m Alive messages to the backup. If the backup does not receive an I’m Alive message from the primary for a couple of messages periods, it assumes the primary has failed and takes over for the primary. Three kinds of takeover are described:

The benefits and programming styles of these three forms of process pairing are contrasted. To preview that discussion:

Process pairs mask hardware failures (processor failures) as well as transient software failures (Heisenbugs). As such, they are the key to software fault tolerance.

This concludes the overview. The following discussion turns to describing the behavior of storage, processes, and messages by the behavior of programs that simulate their behavior. The Lampson-Sturgis model is very instructive and provides a clear way of contrasting some subtle issues. However, the material is very challenging. Readers who do not care to delve in depth into this subject may wish to skim the rest of this section.

3.7.2 Building Highly Available Storage

Reliable storage is built as follows: First, the basic storage operations and failure behavior are defined. Then higher-level operations are defined; with high probability, these mask the failure behavior by n-plexing the devices. This is the analog of the hardware discussion of Section 3.6, but it is less abstract, since specific modules and specific failure modes are involved.

3.7.2.2 Definition of Store and of Store Read and Write

The definitions of the data structures for the programs are given in the following listing and are illustrated in Figure 3.17.

Storage objects support two operations: read and write. They are defined by the simple code fragments that follow. Notice in particular that writes may occasionally fail (with probability pwf) by having no effect.

These programs model, or simulate, durable storage devices such as disks, tapes, and battery-protected electronic RAM. For simplicity, the code does not model soft read faults (a read that fails but will be successful on retry). It does model the simple case of a write occasionally having no effect at all (null writes in the third statement of store_write()). This happens rarely, with a probability pwf (probability of write failure). As explained in the next paragraph, address faults (a write of a page other than the intended page) are modeled by page decay (spontaneous page failure) and by null writes (writes that have no effect).

The model assumes that reads and writes of incorrect locations produce a FALSE status flag and consequently are detectable errors. Both appear to be a spontaneous decay of the page (see below). Incorrect reads and writes are typically detected by storing the page address as part of the page value, so that a read of a wrong page produces a FALSE status flag. This mechanism also detects a write of a correct value to an incorrect address when the overwritten data is subsequently read, because the page address stored in the value will not match the page’s store address. In addition, each page is covered by a checksum that is used as follows:

Write. When a page is written, the writer computes the page checksum and stores it in the page, and

Read. When the page is read, the checksum is recomputed from the value and compared to the original checksum stored in the page.

If the checksums do not match, the page is invalid. All this validity checking is implicit in the status flag.

3.7.2.3 Storage Decay

Each store and each page may fail spontaneously, or a page may fail due to an incorrect store_write(). The spontaneous failure is modeled by a decay process for each store. Operating in the background, this decay process occasionally causes a page to become invalid (status = FALSE) or even invalidates the entire store. The model postulates that store and page errors are independent and that the frequency of such faults obeys a negative exponential distribution with means MTTVF and MTTSF, respectively. Table 3.10 suggests values for such means. The storage decay process is given in the code segment that follows.

As defined, storage gradually decays completely. According to the parameters described earlier, half the stores will have decayed after three years. Such stores are not reliable—reliable devices continue service from their pre-fault state when the fault is repaired. The model assumes that each store and each store page are failfast and are repaired and returned to service in an empty state; that is, all pages have status = FALSE. Algorithms presented next will make them reliable.

3.7.2.4 Reliable Storage via N-Plexing and Repair

In Section 3.6, we saw that repair is critical to availability. The goal is to build reliable stores from off-the-shelf, unreliable components. A reliable store can be constructed by n-plexing the stores, by reading and writing all members of an n-plex group, and by adding a page repair process for each group of stores. Storage is assumed to have exponentially distributed repair times with a mean of a few hours (MTSR ≈ 10⁴ seconds). This includes the latency to detect storage faults.

The idea here is to divide the stores into groups of n members and then to pretend that there are only

$\frac{MAXSTRORES}{\text{n}}$

logical stores. Each reliable_write() attempts to write all members of the group, and each reliable_read() attempts to read all members of the group.⁶ The write case is easy and is represented by the following code:

Note that a really careful design might read the value after writing to make sure that at least one of the pages now has the correct value.

The reliable_read() faces two problems:

All fail. If none of n members can be read, then reliable_read() fails. This should be rare. If its frequency is unacceptably high, then n can be increased.

Ambiguity. If some of the n members are readable (all have good status) but give different values, there is a dilemma: which value should the reliable_read() return? The problem can easily arise if some earlier writes fail (had no effect or had an address fault). This problem can’t be solved by increasing n; in fact the frequency of the problem increases with n. Setting n to 1 “solves” the problem but does not give a reliable store.

One solution to resolving ambiguous reads is to take the majority view, the most popular value. But that only works if there is a majority value. If there are two stores and two values (the most common case), there is no majority.

The premise is that there is a correct value—the most recently written one.⁷ Thus it is postulated that each page has a version generated at the time of the write as part of the value.⁸ The key property is that version numbers increase monotonically. Page value versions are assumed to have the property

If the n-plex reliable_read() discovers a version mismatch, it takes the most recent value and writes that to all other members of the group. In addition, if it finds a member with bad status, it rewrites that member with the most recent version. This could be left to the repair process, but it is repeated here to minimize the latency between fault detection and repair. The reliable read code for n-plex stores follows.

If an n-plexed page is not read for many years, all n copies of it will likely decay. To prevent this scenario, a store repair process runs in the background for each n-plex group. This process merely reads each page of the group once a day (or at some other frequency). The reliable_read() routine performs any needed repair. As part of its normal operation, it reads all copies and updates them if any disagree or are bad. The store repair process repairs any broken pages in a store within a day of its failure, since it visits each page about that often.

3.7.2.5 Optimistic Reads of the N-Plex Group

N-plexing of disks and other storage is common and is implemented as described previously. Writes are done to both disks. But often, especially in the duplexed disk case, the read operation is optimistic: it is directed to only one disk. If that fails, then the other disk is consulted. The logic is something like this:

Optimistic reading is dangerous. Suppose one of the n store_write() operations within a reliable_store_write() fails; that is, suppose it is a null operation. Then, that storage group of pages will have different page values and different page versions. If only one member of the n-plex is read, it may have the old version rather than the new version, a stale read. Stale reads occur half the time for a duplexed disk page damaged by a failed write. Believers in optimistic reads assume each disk is failfast. If so, the writer can sense the write failure and immediately initiate recovery. Recovery from the write failure includes retrying the write, sparing the page to a new location (remapping the address to a new storage page), or ultimately invalidating the whole storage module containing the bad page. The stale write problem often is not carefully thought through, and it is a typical flaw in optimistic Az-plex schemes. To summarize, optimistic reads get the performance benefits of reduced read traffic but risk reading stale data.

The implementation of storage operations assumes that each n-plexed read and write is atomic. That is, if I do a read while you are doing a write, then I will see the store as it was before or after your write, but not the state during your write. A similar assumption applies to two concurrent write operations. The usual way to ensure this one-at-a-time serialization is to have some (reliable and available) process perform the storage reads and writes for everyone else. Such a server, which serializes the requests, could be appointed for each n-plex page or for any larger group. Alternatively, a locking scheme can be used. A highly available and reliable server manages the lock requests for individual pages and serializes access to the pages, but it actually does none of the work. Each of these designs suggests the need for reliable processes, which is the next topic.

The preceding discussion covered n-plexing of storage. A different approach is to use one or more stores to hold an error-correcting code for a set of stores [Patterson et al. 1988]. This approach could also be described and analyzed using the model presented here. That is left as a term-project exercise.

3.7.3 Highly Available Processes

Highly reliable and available processes can be constructed from failfast processes and messages. Processes and their interactions cannot be discussed without talking about messages; unfortunately, the opposite is also true. Because we have to begin somewhere, we start by defining messages. The treatment of messages beyond their definition is reserved for the next subsection. Indeed, it will turn out that reliable messages require reliable processes to implement them.

3.7.3.1 Messages Defined

Processes interact by sending messages to one another or by writing to shared storage that is later read by others. A message is a value sent from one process to another. Figure 3.18 diagrams the flow of a message from a sending process to a receiving process.

Message delivery is not reliable. Some messages are lost (they are never delivered). Some may be delayed, arbitrarily permuting the message delivery order to a process’s input queue. Even if a message is delivered, there is some small chance it will be corrupted, so that the message data is unreadable. The loss and corruption of messages is quantified as the probability of message failure, pmf. There is a comparable chance that the message will be duplicated, so that the message appears twice in the process’s input queue. The following example code demonstrates the external definition of message gets and sends.

The next piece of code gives a sense of how these routines are used, and it defines a useful routine. This get_msg() routine discards corrupt input messages and returns false if there are no good new messages in the process input queue, or returns true and the data of the next input message.

This completes our brief overview of messages. Messages are explored further in Subsection 3.7.4, following the introduction of reliable processes.

3.7.3.2 Process Fault Model

A process executes a program, transforms the process state, and displays an execution behavior. The process’s external behavior is a sequence of store_read(), store_write(), message_send(), and message_get() operations. This external behavior is created by the process executing its program logic on the process state. Each process state is a bundle of bytes containing its program and data. Each process has two states, an initial state that never changes and a current state that changes at each program step. In addition, each process has an input queue, an unordered set of messages sent to it by other processes.

A process fails by stopping for a while (say, an hour) to be repaired, then being reset to its initial state, and having all its unprocessed input messages discarded. That is analogous to a restart of processors in many operating systems. At any instant, each process runs the risk of faulting. After a reset, the process executes its restart logic and continues processing. Of course, it runs the risk of experiencing another reset during the restart.

Here is a way to think of process faults: Imagine that each process is implemented by a lower-level automaton that usually executes the next step of the process, but sometimes stops the process execution for a repair period, discards all the process’ messages, resets the process to the initial state, and then continues the process execution from the initial state (this state includes the process’ program). In addition, the process may have defensive programming tests that cause it to failfast by calling panic() if the test is false. These calls to panic are modeled as just another aspect of the execution automaton occasionally failing the process. Such an automaton is defined as follows:

3.7.3.3 Reliable Processes via Checkpoint-Restart

So far, the processes described are failfast: they either execute the next step, or they fail and reset to the null state. They are not reliable because they do not repair their state upon failure. This failure behavior is similar to the storage failure model in which stores return to service in the null state. Some mechanism is needed to repair the process state, that is, to bring it up to its most recent value.

There are many ways to build such reliable processes from failfast processes. For simplicity, assume that every process’ state fits within a single page. It is then easy to generalize to larger processes.

The following discussion proceeds by example, showing three different ways to implement the same server process. The server’s job is to return a unique sequence number, called here a ticket, to each client upon request. It must never return the same ticket number to two different client requests. Clearly, to achieve this the server must reliably remember the most recently granted ticket number.

The simplest design is the checkpoint-restart approach. The process keeps two copies of its state in reliable storage. At each state change, it overwrites the oldest state value (ticket number) in reliable storage. At restart, it reads both state values and resumes execution from the most recent one (see Figure 3.19). The following code gives a simple example of a reliable checkpoint-restart process.

Checkpoint-restart is a classic technique that has been widely used for decades (see Figure 3.1). Its major problem is that the repair time for the process can be quite long, since the process does not resume service until it is started and refreshes its state from persistent storage. The total repair time is therefore the process repair time plus the restart time, which, according to the model, is several hours altogether.

Because of the long repair times, checkpoint-restart yields highly reliable process execution, but not highly available process execution. The goal is to continue the process execution immediately after the process faults, meaning instant (almost zero) MTTR of process faults. If the fault is caused by hardware, it is likely that pair-and-spare hardware or triplexed hardware can mask it. If the fault is caused by software, by operations, or by environment (as most faults are), then the process and processors will fault, and the process will stop. Why not have a second process in a second processor take over from the first if the first process fails? That idea, called process pairs, is the next technique.

3.7.3.4 Reliable and Available Processes via Process Pairs

The process pair technique is somewhat analogous to n-plexed storage; it is a collection of n processes dedicated to providing a service. One of the processes is primary at any time. The primary process delivers the service. If the primary fails, the backup process continues the service. Clients send their requests to the primary, and if the primary fails, the new primary informs the clients of its new role.⁹

The two-process case, process pairs, is subtle enough. It allows a second process to take over from the primary. There are two delicate aspects of takeover:

Detection. Knowing that the primary is dead (being repaired).

Continuation. Knowing the most recent state of the primary.

As with all aspects of fault tolerance, detecting the primary failure is purely statistical. Because the primary can send messages only when it is operating, a failed primary cannot inform the backup that the primary is broken. For this reason, the primary sends I’m Alive messages to the backup on a regular basis. If one I’m Alive message fails to arrive on time, it is assumed to be delayed or damaged. But if several I’m Alive messages fail to arrive within a reasonable time, the backup assumes that the primary did not send them and is being repaired.

Suppose the backup has decided that the primary is dead. What should it do? How can it continue the computation from the most recent primary state? First, it needs to know the most recent primary state. The usual technique is for the primary to combine state-change messages to the backup with the I’m Alive messages, so-called checkpoint messages. For example, in Figure 3.20 the I’m Alive messages are being sent frequently to the backup. Clearly, the state-change messages can piggyback on the I’m Alive messages, or they can act as surrogates for them. The basic logic of a process-pair program is shown in Figure 3.21.

The idea presented in Figure 3.21 is that both processes start out in the restart state. One process (say, the even-numbered one) is the default primary and takes priority by waiting only one second to see if the other is alive. After two seconds, either the default primary process will have generated an I’m Alive message to the default backup, or the backup decides the primary is dead. In that case, the backup becomes the primary. In any case, whichever becomes the primary broadcasts its identity to all concerned and then goes into a loop of looking for input and processing it. This loop continuously sends I’m Alive messages to the backup, whether there is any input or not. For its part, the backup sleeps for a second, looks to see what the new state is, and then goes back to sleep. The “newer state” test is designed to avoid the possible permutation of messages in the input queue by ignoring states older than the current backup’s state. This test also discards duplicate messages. If the backup does not get a new state within a second, then the primary must be dead, since the primary ought to be able to send hundreds of I’m Alive messages in that time. If the primary is dead, the backup broadcasts that it is the new primary and waits for requests.

There is one more delicate takeover issue. At takeover, the backup is in the same state the primary was in when it sent the checkpoint message to the backup. But the primary may have failed before sending the reply that the last state transition generated (the bottom box of Figure 3.21). So, if a reply was owed to a client, the reply is resent. This may generate a duplicate message to the client, but that was a possibility of the message system anyway.

To continue the discussion of Figure 3.21: If the maximum propagation time for messages is one millisecond, and the maximum service time for a request is a millisecond, then waiting ten milliseconds (five message cycles) is long enough to detect process failure. This period is long enough for five consecutive lost I’m Alive messages if processors are dedicated to processes. Thus, process takeover times of ten milliseconds can easily be achieved. Typically, though, the primary shares the processor with other processes and, for resource consumption reasons, does not continuously send I’m Alive messages. Consequently, a longer latency is more typical.

In fault-tolerant operating systems, process pairs are a basic notion provided by the system. Such operating systems inform the backup process when the primary process fails and automatically redirect all new client requests to the backup process. This means that the primary can dispense with the idle state checkpoint messages and the I’m Alive messages. It also means that the backup can dispense with the one-second waits, because all the messages are important. The backup can also dispense with the broadcast to clients at startup and takeover. These are just performance optimizations; the programming style of checkpointing state changes is the same for this simple model and for the “real” fault-tolerant systems.

Adapting the checkpoint_restart_process() example to process_pair_process() using the logic of Figure 3.21 is straightforward (about one page of C code). The complexity of process pairs apparent in the above explains why the discussion here is restricted to process pairs, rather than including n-plexed processes.

3.7.3.6 Persistent Processes—The Taming of Process Pairs

As can be seen from the previous discussion, writing process pairs is very demanding. Indeed, it is the authors’ experience that everyone who has written one thinks it is the most complex and subtle program they have ever written. However, reliable systems use these techniques, and those systems do mask many failures.

There is a particularly simple form of process pair called a persistent process pair. Persistent process pairs have a property that is variously called context free, stateless, or connectionless. Persistent processes are almost always in their initial state. They perform server functions, then reply to the client and return to their initial state. The primary of the persistent process pair does not checkpoint or send I’m Alive messages, but just acts like an ordinary server process. If the primary process fails in any way, the backup takes over in the initial state.

Persistent process pair takeover works as follows. The underlying fault-tolerant operating system knows that the primary and backup are a process pair. If the primary fails, or if the processor on which the primary is executing fails, the operating system of the backup process senses the failure and informs the backup process of the failure. The operating system also redirects all client messages to the backup. In this situation, the backup takes over in its initial state and begins offering service.

As described, persistent processes are easy to program and make high-availability servers, but these servers seem to provide little more than encapsulation of the server logic to the client. The servers do not maintain network state or database state. To make persistent processes useful, someone else must maintain such states.

For example, imagine that such a persistent process acted as your mailbox. It would receive messages for you, but would always return to the null state (no messages for you)—not a very useful program. Similarly, if the server actually kept your state in a file, the updates to receive or discard a mail message might be partially incomplete at the time the server failed. In this case, your mailbox file would be left in that state by the backup persistent process when it took over in the null state.

These examples hint at the solution. A persistent process server should maintain its state in some form of transactional storage: a transaction-protected database. When the primary process fails, the transaction mechanism should abort the primary’s transaction, and the backup should start with a consistent state. On the other hand, if the server calls commit_work() after making the changes, the transaction mechanism should reliably deliver the server’s message to the client as part of the atomicity guarantee of ACID transactions.

Given that, the transaction mechanism returns the database and the network to their state as of the start of the server function. Persistent processes need not send application checkpoint messages to indicate state changes, since the initial state is the takeover state. When running on a fault-tolerant system that provides persistent process pairs as a primitive, the program need not concern itself with takeover or message retransmission. That logic is handled for the program by the underlying system. All this makes persistent process pairs very easy to program. They have the following form:

The following code illustrates the checkpoint-restart ticket server of Subsection 3.7.3.3 reprogrammed as a transactional server.

Notice that to become a process pair, the ticket server application did nothing more than represent its state in transactional storage and call the operating system routine wait_to_be_primary(). There are no checkpoint messages, no I’m Alive messages, and no takeover logic. Yet this process has much higher availability than the checkpoint-restart process. In addition, if the transaction did complex updates to its database, each group of updates (transactions) would have all the ACID properties.

3.7.4 Reliable Messages via Sessions and Process Pairs

Having shown how to convert faulty processes and faulty storage to highly available processes and storage, the discussion turns to converting faulty messages to highly reliable messages. This section first defines the behavior and fault model for messages. It then shows how sessions, session sequence numbers, acknowledgment, timeout, and retransmission can all be combined to provide reliable message delivery. Since either the message source process or the destination process can fail, process pairs are part of the mechanism needed to convert faulty messages into reliable messages.

3.7.4.1 Basic Message Model

A process can send a message to another process by invoking message_send(), which specifies the process identifier and the message data. This copies the message data from the sender’s address space to the receiver’s input queue. The receiver can then call message_get() to copy the message from its input queue to its address space.

The message and process queue definitions were already given. Here is the code to implement message_send and message_get:

Messages have simple failure modes; some fraction of them spontaneously decay (status = FALSE) and some fraction of them are duplicated. This models failure of communication lines, buffer overflows, and the like. It also models the retransmission logic underlying message systems that occasionally duplicate a message. In addition, the messages in a process’s input queue may be arbitrarily permuted. This models the possibility that messages can be arbitrarily delayed in the network.

3.7.4.2 Sessions Make Messages Failfast

As defined, messages are not failfast; corrupt and duplicate messages are delivered, and messages are delivered out of order. The first step in making messages reliable is to give them simple failure semantics—failfast semantics. To make all messages failfast, faulty messages are converted to lost messages. Message semantics, then, are as follows: (1) messages are delivered in order, and (2) some messages are lost. In the simplified model, the only form of message failure is a lost message.

First, let’s convert corrupt messages to lost messages. The message status flag models the idea that the message contents are self-checking, so that corrupt messages can be detected and discarded. It is standard to compute a message checksum at the source and to send the checksum as part of the message. The receiver recomputes the checksum and compares it to the sender’s checksum. If the two checksums are different, the message has been corrupted and is discarded. This converts a corrupt message to a lost message. The get_msg() procedure defined in Subsection 3.7.3.1 discards all such corrupt messages.

The simplest approach to detecting and discarding duplicate and permuted messages is to use sessions and message-sequence numbers. A session is a bidirectional message pipe between two processes. Sessions have the following semantics: (1) messages are delivered to the destination in the order they were sent, and (2) no messages are duplicated or lost, but messages can be delayed. Sessions are variously called connections, sockets, pipes, dialogs, opens, ports, and myriad other names. In this text, sessions are represented by pipe icons, as shown in Figure 3.22.

Sessions implement these semantics by having the two session endpoints each maintain three sequence numbers: (1) the out sequence number, which is the sequence number of the most recently sent message on that session, (2) the in sequence number, which is the sequence number of the most recently received message on that session, and (3) the acknowledged sequence number, which is the sequence number of the most recently acknowledged message.

Each message from one process to another carries a sequence number. When a new message is sent to that receiver, the sender’s out sequence number is incremented and used to tag the sender’s message. When the receiver gets the message, if the sequence number is one greater than the most recent message, the recipient knows it is the next message and accepts it. The recipient increments the in sequence number and sends an (unsequenced) acknowledgment message to the sender, saying that the new message arrived.

Sequence numbers detect duplicate and delayed messages as follows: If a message is duplicated, the message sequence number is also duplicated; thus the recipient can detect a duplicate message by noticing that the message sequence number is equal to the most recently acknowledged sequence number. In this case, the recipient discards the message and does not change its in sequence number. In either case, the recipient acknowledges the message to the sender.

If a message is delayed and hence arrives out of order, the recipient can see that the message sequence number is less than the most recently acknowledged message and consequently can discard the message. It need not acknowledge such messages.

As described so far, sessions create the simple failure semantics of sending messages in order, thereby making messages failfast. If there were no failures, such sessions would work perfectly. But, as soon as there is a message failure, the session starts discarding all future messages in that direction. So far, then, the design has made messages failfast. The next step is to make messages reliable by repairing lost messages.

3.7.4.4 Sessions plus Process Pairs Make Messages Available

The discussion so far has focused on message failures and ignored process failures. What if the sending or receiving process fails? In that case, the message has nowhere to go or no sender to retransmit it. A session is only as reliable as its two endpoints.

The obvious solution to making reliable session endpoints is to make each endpoint a process pair. In this design, sessions connect process pairs so that delivery of new messages to the backup is automatic if the primary fails. Messages that have already been sent to the primary are probably lost and will not arrive at the backup. The sequence numbers of the primary are also maintained as part of the backup process state. If a process fails, that endpoint of the session switches to the backup of that process pair. The backup will have the current sequence numbers, and if it is sending, it will have a copy of the current message.

The logic for this is simple: The sender first checkpoints the message to the backup and then sends the message. If the backup takes over, it resends the message and continues the session. The receiver checkpoints received messages to its backup before acknowledging them. This logic is diagramed in Figure 3.23.

At process-pair takeover, the backup process broadcasts its new identity and resends any unacknowledged messages that the primary process was trying to send. The other session endpoint may get a takeover broadcast from the backup process of the process pair. In that case, the other endpoint begins sending the message to the former backup process, which is now the new primary process of the process pair. When the message is finally delivered and acknowledged, the next message can be sent via the session.

To restate this development: Session sequence numbers convert permuted messages and duplicate messages into lost messages, making all messages failfast and making sessions failfast-communications services. Acknowledgment, timeout, and retransmission make messages reliable by resending them. Messages eventually get through. Process pairs make the endpoints available; they are persistent in sending the messages until they are acknowledged. Messages are as available as the processes that send them and the wires that carry them. If the processes are duplexed, and the wires are n-plexed, the messages can be made highly available. The various time constants (acknowledge times and takeover times) are limited by message delay and processor speed. It is possible to give reliable delivery within seconds for wide-area systems (≈10,000 km) and within tens of milliseconds for local area systems (1 km). These time constants are discussed in Section 2.6.

3.7.4.5 The Code for Sessions and Messages

The code to implement sessions, acknowledgment and retransmission, and process-pair checkpoint and takeover is instructive. First, sessions and message formats are defined, and an array of sessions is added to the state of each process. These sessions hold the endpoint names and the sequence numbers.

In addition, assume that the message_send() and message_get() routines have been abstracted to session_send() and session_get() routines. These routines send and get messages that carry a session descriptor and a message type (that is, they manipulate the a_session_message type rather than just a_message type). These routines pack and unpack the session descriptor and message type descriptor as added framing information on messages. Session_send() fills in the session descriptor and value for each message. Session_get() extracts these two fields from the next process input message and returns them. Session_get() must read the message to find the session name and the sequence number. If the message is corrupt (status = FALSE), session_get() cannot read these fields and discards such messages. Consequently, it has no status parameter; any message it returns is not corrupt. These are the interfaces:

The reliable_send_message() routine sends the message, waits for the timeout period, and if no acknowledgment message has arrived, it sends the message again. It continues this until the message has been acknowledged (the acknowledgment mechanism is explained momentarily):

In this design, the sender continues sending until the receiver acknowledges the message. The receiver may be doing something else at the moment—computing, writing storage, or even sending a message to some third process. The receiver, therefore, may not be interested in acknowledging the sender’s message right away. Waiting for the receiver’s acknowledgment might cause message deadlock, with each process waiting for an acknowledgment from the next. To avoid such deadlocks, and to speed message flows, acknowledgments should be generated quickly and asynchronously from the receiver’s application program logic. This means that each process should regularly poll its input sessions for messages. Such a requirement, however, would make programs both unreadable and error-prone.

Even more fundamental, perhaps, is the fact that the sender in the code above assumes someone else is going to update the acknowledgment sequence number. The reliable_send_message() code could perform this logic, but it would vastly complicate the code. In general, this is the kind of logic that another process should manage as a service for all processes in the address space.

To preserve the program structure, almost all systems use the concept of multiple processes sharing one address space to perform such asynchronous tasks (see Chapter 2). Such lightweight processes are often called threads, but the generic term process is used here. These processes execute continuously and autonomously from the main application, communicating with it primarily via shared memory. The main application function is implemented as one or more processes (threads), and service functions such as message acknowledgment are implemented as other processes.

Each address space has a listener process that performs message acknowledgment and increments message sequence numbers for the application process executing in that address space. The listener is constantly polling the application process’s sessions. When a message arrives, the listener executes the sequence number logic. If the message is a data input message, the listener acknowledges the message and places it in the session’s message queue for the application program process. If the message is an acknowledgment, the listener implements the ack sequence number logic. Figure 3.24 illustrates the role of the listener.

The listener process executes continuously, running at high priority. When there are no input messages, it waits for the next event (in the sample code it waits for a second rather than for an event). In most designs, the listener places a limit on how many messages it will accept from a sender. This is called flow-control. Otherwise, senders could flood the receiver with messages, consuming all the listener’s storage. For simplicity, such refinements are not included in the example. Also for simplicity, the code does not deal with takeover (process pairs). The listener maintains the process sequence numbers and the FIFO session message queues.

The picture thus far is that the listener acknowledges receipt of messages promptly and saves these messages as part of the process (pair) state. The acknowledged input messages of each session are chained from the in_msg_queue[] of that session in most-recent-last order. It should now be clear that reliable_send_message() does reliably send messages. It retransmits every second until the message is acknowledged and the listener records that acknowledgment by incrementing the session.ack sequence number.¹¹

Reliable_get_message() gets the next message value from a particular session by accessing the message queue maintained by the listener. The code to reliably get a message follows:

3.7.5 Summary of the Process-Message-Storage Model

The preceding gives a simple simulation model of the three components of a computer system. The message and storage models show how software can mask hardware faults by using redundancy in hardware, duplexing storage, wires, and processors. It also shows how software can use redundancy in time by retransmitting a message if the first one fails.

This material gives a sense of three styles of software fault tolerance: checkpoint-restart, process pairs, and persistent processes. It also gives a sense of the relative difficulty and benefits of the three styles, with the goal of convincing the reader that, if possible, persistent processes plus transactions should be used to obtain highly available program execution.

In addition, this simplified model (leave aside the actual implementation) is fairly complex. No formal or theoretical development of these ideas is available—it would be too difficult and complex to handle. In contrast, the model might work well for simulation studies to help quantify the relative benefits of design alternatives.