4301TFVIL
`
`1
`
`LYFT 1034
`
`....lk v A._.."k .I '-t • o i~.__~
`

`

`C omputmg systems consist of a multitude of hardware and software components that are bound to fail even- tually. In many systems, such component failures can lead to unanticipated, potenti- ally disruptive failure behavior and to service unavailability. Some sys- tems are designed to be fault-toler- ant: they either exhibit a well- defined failure behavior when components fail or mask compo- nent failures to usersIthat is, con- tinue to provide their specified standard service despite the occur- rence of component failures. To many users temporary errant sys- tem failure behavior or service un- availability is acceptable. There is, however, a growing number of user communities for whom the cost of unpredictable, potentially hazard- ous failures or system service un- availability can be very significant. Examples include the on-line trans- action processing, process control, and computer-based communica- tions user communities. To mini- mize losses due to unpredictable failure behavior or service unavail- ability, these users rely on fault- tolerant systems. With the ever- increasing dependence placed on computing services, the number of users who will demand fault-toler- ance is likely to increase. The task of designing and un- derstanding fault-tolerant distrib- uted system architectures is notori- ously difficult: one has to stay in control of not only the standard system activities when all compo- nents are well, but also of the com- plex situations which can occur when some components fail. The difficulty of this task can be exacer- bated by the lack of clear structur- ing concepts and the use of a con- fusing terminology. Presently, it is quite common to see different peo- ple use different names for the same concept or use the same term for different concepts. For exam- ple, what one person calls a failure, a second person calls a fault, and a third person might call an error. Even the term "fault-tolerant" itself is used ambiguously to designate such distinct system properties as "the system has a well-defined fail- ure behavior" and "the system masks component failures." This article attempts to introduce some discipline and order in un- derstanding fault-tolerance issues in distributed system architectures. In the following section, "Basic Architectural Concepts," a small number of basic architectural con- cepts are proposed. In the sections entitled "Hardware Architectural Issues" and "Software Architectural Issues" these concepts are used to formulate a list of key hardware and software issues that arise when designing or examining the archi- tecture of fault-tolerant distributed systems. Since the search for satis- factory answers to most of these is- sues is a matter of current research and experimentation, this article examines various proposals, dis- cusses their relative merits, and il- lustrates their use in existing com- mercial fault-tolerant systems. Besides being useful as a design guide, this article's list of issues also provides a basis for classifying ex- isting and future fault-tolerant sys- tem architectures. The final section of this article comments on the ade- quacy of the proposed concepts. Basic Architectural Concepts To achieve fault tolerance, a dis- tributed system architecture incor- porates redundant processing com- ponents. Thus, before the issues which underlie fault-tolerance--or redundancy management--in such systems are discussed, it is necessary to introduce their basic architec- tural building blocks and classify the failures that these basic blocks can experience. services, Servers, and the "Depends" Relation The concepts of service, server, and the "depends upon" relation among servers are the three notions that the author believes provide the best means to explain computing systems architectures. A computing service specifies a collection of operations whose exe- cution can be triggered by inputs from service users or the passage of time. Operation executions may result in outputs to users and in ser- vice state changes. For example, an IBM4381 raw processor service consists of all the operations de- fined in a 4381 processor manual, and a DB2 database service consists of all the relational query and up- date operations that clients can make on a database. The operations defined by a ser- lice specification can be performed only by a server for that service. A server implements a service without exposing to users the internal ser- vice state representation and opera- tion implementation details. Such details are hidden from users, who need know only the externally spec- ified service behavior. Servers can be hardware or software imple- mented. For example, a 4381 raw processor service is typically imple- mented by a hardware server; how- ever, sometimes one can see this service "emulated" by software. A DB2 service is typically imple- mented by software, although it is conceivable to implement this ser- vice by a hardware database ma- chine. Servers implement their service by using other services which are implemented by other servers. A server u depends on a server r if the correctness of u's behavior depends on the correctness of r's behavior. The server u is called a user (or cli- ent) of r, while r is called a resource of u. Resources in turn might de- pend on other resources to provide their service, and so on, down to the atomic resources of a system, which one does not wish to analyze any further. Thus, the user/client and resource/server names are relative to the "depends" relation: what is a resource or server at a certain level of abstraction can be a client or a user at another level of abstraction. This relation is often represented as an acyclic graph in which nodes denote servers and arrows repre- sent the "depends" relation. Since it is customary to represent graphi- COMMUNICATIONS OF THE ACM/February 1991/Vol.34, No.2 S 7
`
`2
`
`

`

`cally a user u of a resource r above r, u is said to be at a level of abstrac- tion "higher" than r [25, 51, 54]. For example, a file server f, which uses the services provided by a disk space allocation server s and a disk I/O' server d to provide file cre- ation, access, update, and deletion service, depends on s and d (see Fig- ure 1). To implement the file ser- vice, the designer off assumes that the allocation and I/O services pro- vided by s and d have certain prop- erties. If the specifications of s and d imply these properties and f, s and d are correctly implemented, thenf will behave correctly. All of the above servers depend on processor service provided to them by some underlying operating system when they execute (or are interpreted). If they were written in a high-level language, they also depend on compilers and link-editors to be translated correctly in machine lan- guage. When all software servers under discussion depend on such translation and processor services, it is customary to omit representing this fact in the "depends" graph. Note that the static "depends" relation defined above relates to the correctness of a service implemen- tation and differs from the dynamic "call" (or flow control) and "inter- prets" (or executes) relations which can exist at runtime between serv- ers situated at different abstraction levels. For example, the file serverf will typically use synchronous, blocking, "down-calls" to ask the allocation server s for free storage and will use asynchronous, non- blocking, down-calls to ask the I/O server d to initiate disk I/O in paral- lel. When the I/O is completed, the I/O server will typically notify the file server f by using an "up-call" [15] which might interrupt f. If a processor p interprets the programs of f, s, ;and d these "depend" on p (although p "executes" them). A distributed system consists of software servers which depend on processor and communication ser- vices. Processor service is typically provided concurrently to several software servers by a multiuser operating system such as Unix or MVS. These operating systems in turn depend on the raw processor service provided by physical proc- essors, which in turn depend on lower-level hardware resources such as CPUs, memories, I/O con- trollers, disks, displays, keyboards, and so on. The communication ser- vices are implemented by distrib- uted communication servers which implement communication proto- cols such as TCP/IP and SNA by depending on lower-level hardware networking services. It is customary f :IGURE 1 An Illustration Depicting Relations between File Server f, Disk Space AlloCation Server $, and Disk I/O Server d. to designate the union of processor and communication service opera- tions provided to application serv- ers as a distributed operating system service. Failure Classification A server designed to provide a cer- tain service is correct if, in response to inputs, it behaves in a manner consistent with the service specifica- tion. This article assumes the speci- fication prescribes both the server's response for any initial server state and input and the real-time interval within which the response should occur. By a server's response we mean any outputs that it has to de- liver to users as well as any state transition that it must undergo. A server failure occurs when the server does not behave in the man- ner specified. An omission failure occurs when a server omits to re- spond to an input. A timing failure occurs when the server's response is functionally correct but untimely-- the response occurs outside the real-time interval specified. Timing failures thus can be either early tim- ing failures or late timing failures (performance failures). A response failure occurs when the server re- sponds incorrectly: either the value of its output is incorrect (value fail- ure) or the state transition that takes place is incorrect (state transi- tion failure). If, after a first omis- sion to produce output, a server omits to produce output to subse- quent inputs until its restart, the server is said to suffer a crash fail- ure. Depending on the server state at restart, one can distinguish be- tween several kinds of crash failure behaviors. An amnesia-crash occurs when the server restarts in a prede- fined initial state that does not de- pend on the inputs seen before the crash. A partial-amnesia-crash oc- curs when, at restart, some part of the state is the same as before the crash while the rest of the state is reset to a predefined initial state. A pause-crash occurs when a server restarts in the state it had before the crash. A halting-crash occurs when a crashed server never restarts. Note that while crashes of stateless servers, pause-crashes and halting crash behaviors are subsets of omis- sion failure behaviors; in general, partial and total amnesia crash be- haviors are not a subset of omission failure behaviors. In what follows we follow accepted practice and use the term crash ambiguously to des- ignate one or more of the above kinds of crash failure behaviors; the particular meaning intended should be clear from the way the state and the restart operation of the server(s) under consideration are defined. The following are examples of crash failures: an operating system crash followed by reboot in a pre- defined initial system state and a database server crash followed by recovery of a database state that reflects all transactions committed before the crash. A communication service that occasionally loses but 58 February 1991 ]Vo1134, No.2/COMMUNICATIONS OF THE ACM
`
`3
`
`

`

`,, ' • . . . - . " . • - ., • does not delay messages is an exam- ple of a service that suffers omis- sion failures. An excessive message transmission or message-processing delay due to an overload affecting a set of communication servers is an example of a communication per- formance failure. When some action is taken by a processor too soon, perhaps because a timer runs too fast, it is considered an early timing failure. A search procedure that "finds" a key not inserted in a table, and an alteration of a mes- sage by a communication link sub- ject to random noise are examples of server response failures. Failure Semantics When programming recovery ac- tions for a server failure, it is im- portant to know what failure be- haviors the server is likely to exhibit. The following example il- lustrates this point. Consider a cli- ent u which sends a service request sr through a communication link l to a server r. Let d be the maximum time needed by l to transport sr and p be the maximum time needed by r to receive, process, and reply to sr. If the designer of u knows that communication with r via 1 is af- fected only by omission--not per- formance--failures, then if no reply to sr is received by u within 2(d + p) time units, u will never re- ceive a reply to sr. To handle this, u might resend a new service request sr' to r, but u will not have to main- tain any local data that would allow it to distinguish between answers to "current" service requests, such as sr', and answers to "old" service requests, such as sr. If, on the other hand, the designer of u knows that l and r can suffer performance fail- ures, if no reply to sr is received by u within 2(d + p) time units, u will have to maintain some local data, for example a sequence number, that will allow it to discard any "late" answer to sr. Since the recovery actions in- voked upon detection of a server failure depend on the likely failure behaviors of the server, in a fault- tolerant system one has to extend the standard specification of servers to include, in addition to their familiar failure-free semantics (the set of failure-free behaviors), their likely failure behaviors, or failure semantics [18]. If the specification of a server s prescribes that the failure behav- iors likely to be observed by s users should be in class F, it is said that "s has F failure semantics" (a discus- sion of what we mean by "likely" is deferred to the section entitled "Choosing a Failure Semantics"). The term failure "semantics" is used instead of failure "mode" be- cause semantics is already a widely accepted term for characterizing behaviors in the absence of failures, and there is 'no logical reason why such dissimilar words as "seman- tics" and "mode" should be used to label the same notion: allowable server behaviors. For example, if a communication service is allowed to lose messages, but the probability that it delays or corrupts messages is negligible, we say that it has omission failure se- mantics (what "negligible" means is discussed in the section "Choosing a Failure Semantics"). When the ser- vice is allowed to lose or delay mes- sages, but it is unlikely that it cor- rupts messages, we say that it has omission/performance failure se- mantics. Similarly, if a processor is likely to suffer only crash failures or a memory is likely to suffer only COMMUNICATIONS OF THE ACM/February 1991/Vol.34, No,2 Sg
`
`4
`
`

`

`omission failures in response to read requests (because of parity errors), we say that the processor and the memory have crash and read omission failure semantics, respectively. In general, if the fail- ure specification of a server s allows s to exhibit behaviors in the union of two failure classes F and G, we say that s has F/G failure semantics. Since a server that has F/G failure semantics can experience more fail- ure behaviors than a server with F failure semantics, we say that F/G is .a weaker (or less restrictive) failure semantics than F. Equivalently, F is stronger (or more restrictive) than F/G. When any failure behavior is allowed for a server s, that is, the failure semantics specified for s is the weakest possible, we say that s has arbitrary failure semantics. Thus, the class of arbitrary failure behaviors includes all the failure classes defined previously. It is the responsibility of a server designer to ensure that it properly implements a specified failure se- mantics. For example, to ensure that a local area network service has omission/performance failure se- mantics, it is standard practice to use error-detecting codes that de- tect with high probability any mes- sage corruption. To ensure that a local area network has omission failure '.semantics, one typically uses network access mechanisms that guaranl:ee bounded access delays and real-time executives that guar- antee upper bounds on message transmission and processing delays [45]. To implement a raw hardware processor service with crash failure semantics, one can use duplication and matching--that is, use two physically independent processors that execute in parallel the same sequence of instructions and that compare their results after each instruction execution, so that a crash occurs when a disagreement between processor outputs is de- tected [62]. In general, the stronger a speci- fied failure semantics is, the more expensive and complex it is to build a server that implements it. The following examples illus- trate this general rule of fault-toler- ant computing. A processor that achieves crash failure semantics by using duplication and matching, as discussed in [62], is more expensive to build than an elementary proces- sor which does not use any form of redundancy to prevent users from seeing arbitrary failure behaviors. A storage system that guarantees that an update is either completely performed or is not performed at all when a failure occurs is more expensive to build than a storage system which can restart in an in- consistent state because it allows updates to be partially completed when failures occur. More design effort is required to build a real- time operating system that provides processor service with crash failure semantics than to build a standard multiuser operating system, such as Unix, which provides processor service with only crash/perfor- mance failure semantics [45]. Hierarchical Failure Masking A failure behavior can be classified only with respect to a certain server specification, at a certain level of abstraction. If a server depends on lower-level servers to correctly pro- vide its service, then a failure of a certain type at a lower level of ab- straction can result in a failure of a different type at the higher level of abstraction. For example, consider a value failure at the physical trans- mission layer of a network which causes two bits of a message to be corrupted. If the data link layer above the physical layer uses at least 2-bit error-detecting codes to detect message corruption and discards corrupted messages, then this fail- ure is propagated as an omission failure at the data link layer. As another example, consider a clock affected by a crash failure that dis- plays the same "time." If that clock is used by a higher-level communi- cation server that is specified to as- sociate different timestamps with different messages it sends at dif- ferent real times, then the commu- nication server may be classed as experiencing an arbitrary failure [23]. As illustrated above, failure propagation among servers situ- ated at different abstraction levels of the "depends upon" hierarchy can be a complex phenomenon. In general, if a server u depends on a resource r with arbitrary failure semantics, then u will likely have arbitrary failure semantics, unless u has some means to check the cor- rectness of the results provided by r. Since the task of checking the correctness of results provided by lower-level servers is very cumber- some, fault-tolerant systems design- ers prefer to use (whenever possi- ble) servers with failure semantics stronger than arbitrary--such as crash, omission or performance. In hierarchical systems relying on such servers, exception handling provides a convenient way to propagate in- formation about failure detections across abstraction levels and to mask low-level failures from higher-level servers [20]. The pat- tern is as follows. Let i andj be two levels of abstraction, so that a server u atj depends on the service imple- mented by the lower level i. If u down-calls a server r at i, then in- formation about the failure of r propagates to u by means of an ex- ceptional return from r (this can be a time-out event signalling no timely return from r). If the server u at j depends on up-calls from lower-level servers at i to imple- ment its service, u needs some knowledge about the timing of such up-call events to be able to detect lower-level server failures. For ex- ample, if the server u expects an interrupt from a sensor server every per milliseconds, a missing sensor data update can be detected by a timeout. If the server u atj can provide its service despite the fail- ure of r at i we say that u masks r's failure. Examples of masking ac- tions that u can perform are down- calls to other, redundant servers r', r", . . . at i, or repeated down-calls to r if r is likely to suffer transient omission failures. If u's masking attempts do not succeed, a consis- 60 February 1991/Vo1.34, NO.2/COMMUNIC&TIONS OF THE ACM
`
`5
`
`

`

`. . . • • . . ' , . . , tent state must be recovered for u before information about u's failure is propagated to the next level of ab- straction, where further masking attempts can take place. In this way, information about the failure of a lower-level server r can either be hidden from the human users by a successful masking attempt or can be propagated to the human users as a failure of a higher-level service they requested. The programming of masking and consistent state re- covery actions in a client c of u is usually simpler when c's designer knows that u does not change its state when it cannot provide its standard service. Servers which, for any initial state and input, either provide their standard service or signal an exception without chang- ing their state (termed "atomic with respect to exceptions" in [20]) sim- plify fault-tolerant programming because they provide their users with a simple-to-understand omis- sion failure semantics. The hierarchical failure-masking pattern described above can be il- lustrated by an IBM MVS operat- ing system example running on a processor with several CPUs (other examples of hierarchical masking can be found in [67]). When an at- tempt at reading a CPU register results in a parity check exception detection, there is an automatic CPU retry from the last saved CPU state. If this masking attempt suc- ceeds, data about the original fail- ure is logged and the human opera- tor is notified, but the original (transient) omission CPU failure occurrence is masked from the MVS operating system and the soft- ware servers above it. Otherwise, the observed parity exception fol- lowed by the unsuccessful CPU retry is reported by an interrupt as a crash failure of that CPU server to the MVS system; it, in turn ]nay at- tempt to mask the failure by reexecuting the program which caused the CPU register parity ex- ception (from a previously saved checkpoint) on an alternate CPU. If this masking attempt succeeds, the failure of the first CPU is masked from the higher levels of abstrac- tion-the software servers which run application programs. If there are no alternate CPUs or all mask- ing attempts initiated by the MVS system fail, a crash failure of the MVS system occurs. Group Failure Masking To ensure that a service remains available to clients despite server failures, one can implement the service by a group of redundant, physically independent, servers, so that if some of these fail, the re- maining ones provide the service. We say that a group masks the fail- ure of a member m whenever the group (as a whole) responds as specified to users despite the failure of m. While hierarchical masking (dis- cussed in the previous section) re- quires users to implement any re- source failure-masking attempts as exception handling code, with group masking, individual member failures are entirely hidden from users by the group management mechanisms. The group output is a function of the outputs of individ- ual group members. For example, the group output can be the output generated by the fastest member of the group, the output generated by some distinguished member of the group, or the result of a majority vote on group member outputs. We use the phrase "group g has F fail- ure semantics" as a shorthand for "the failures that are likely to be observable by users of g are in class F." A server group able to mask from its clients any k concurrent member failures will be termed k-fault tolerant; when k is 1, the group is single-fault tolerant, and when k is greater than 1, the group is multiple-fault tolerant. For exam- ple, if the k members of a server group have crash/performance fail- ure semantics and the group output is defined to be the output of the fastest member, the group can mask up to k-1 concurrent member failures and provide crash/perfor- mance failure semantics to its cli- ents. Similarly, a primary/standby group of k servers with crash/ performance failure semantics, with members ranked as primary, first backup, second backup ..... (k-1)th back up, can mask up to k-1 concurrent member failures and provide crash/performance failure semantics. A group of 2k + 1 mem- bers with arbitrary failure seman- tics whose output is the result of a majority vote among outputs com- puted in parallel by all members can mask a minorityithat is, up to k member failures. When a major- ity of members fail in an arbitrary way, the entire group can fail in an arbitrary way. Hierarchical and group masking are two end points of a continuum of failure-masking techniques. In practice one often sees approaches that combine elements of both. For example, a user u of a primary/ backup server group that sends its service requests directly to the pri- mary might detect a primary server failure as a transient service failure and might explicitly attempt to mask the failure by resending the last service request [7]. Even if the service request were automatically resent for u by some underlying group communication mechanism which matches service request with replies and automatically detects missing answers, it is likely that u contains exception-handling code to deal with the situation when the entire primary/backup group fails. The specific mechanisms needed for managing redundant server groups in a way that masks member failures, and at the same time makes the group behavior func- tionally indistinguishable from that of single servers depend critically on the failure semantics specified for group members and the com- munication services used. The stronger the failure semantics of group members and communica- tion, the simpler and more efficient the group management mecha- nisms can be. Conversely, the weaker the failure semantics of members and communication, the more complex and expensive the group management mechanisms COMMUNICATIONS OF THE ACM/February 1991/Vol.34, No.2 61
`
`6
`
`

`

`become. To illustrate this other general rule of fault-tolerant computing, consider a single-fault-tolerant storage service S. If the elementary storage :servers used to build S have read omission failure semantics (error-detecting codes ensure that the probability of read value fail- ures caused by bit corruptions is negligible), one can implement S as follows: use two identical, physically independent elementary servers s, s'; interpret each S-write as two writes on s and s', and interpret each S-read as a read of s, and if the s-read results in an omission fail- ure, a read of s'. If the elementary storage servers are likely to suffer both omission and read value fail- ures, that is, it is possible that in re- sponse to a read either no value is returned or the value returned is different from the one written, then three elementary, physically independent servers are needed for implementing S: Each S-write re- sults in three writes to all servers, and each S-read results in three ele- mentary reads from all servers and a majority vote on the elementary results returned. If a majority ex- ists, the result of the S-read is the majority value read. If no majority exists, the S-read results in an omis- sion failure. The S service imple- mented by triplexing and voting is not only more complex and expen- sive than the service S implemented by duplexing, but is also slower. Other illustrations of the rule that group management cost in- creases ;as the failure semantics of group members and communica- tion services becomes weaker are given in [23] and [26], where fami- lies of solutions to a group commu- nication problem are studied under increasingly weak group member and communication failure seman- tics assumptions. Statistical mea- surements of run-time overhead in practical systems confirm the gen- eral rule that the cost of group management mechanisms rises when the failure semantics of group members is weak: while the run-time cost of managing server- pair groups with crash/perfor- mance failure semantics can some- times be as low as 15% [11], the cost of managing groups with arbitrary failure semantics can be as high as 80% of the total throughput of a system [50]. Since it is more expensive to build servers with stronger failure semantics, but it is cheaper to han- dle the failure behavior of such servers at higher levels of abstrac- tion, a key issue in designing multi- layered fault-tolerant systems is how to balance the amounts of fail- ure detection, recovery, and mask- ing redundancy used at the various abstraction levels of a system, in order to obtain the best possible overall cost/performance/depend- ability results. For example, in the case of the single-fault-tolerant storage service previously de- scribed, the combined cost of incor- porating effective error-correcting codes in the elementary storage servers and implementing a single- fault-tolerant service by duplexing such servers is generally lower than the cost of triplexing storage serv- ers with weaker failure semantics and using voting. Thus, a small in- vestment at a lower level of abstrac- tion for ensuring that lower-level servers have a stronger failure se- mantics can often contribute to sub- stantial cost savings and speed im- provements at higher levels of abstraction and can result in a lower overall cost. On the other hand, deciding to use too much redun- dancy, especially masking redun- dancy, at the lower levels of abstrac- tion of a system might be wasteful from an overall cost/effectiveness point of view, since such low-level redundancy can duplicate the masking redundancy that higher levels of abstraction might have to use to satisfy their own dependabil- ity requirements. Similar cost/effec- tiveness "end-to-end" arguments in layered implementations of fault- tolerant communication services have been discussed in [55]. Choosing a Failure Semantics When is the probability that a server r suffers failures outside a given failure class F small enough to be considered "negligible"? In other terms, when is it justified to assume that the only "likely" failure behaviors of r are in class F? The answer to these questions depends on the stochastic requirements placed on the system u of which r is a part. The specification of a server r must consist of not only functional requirements Sr and Fr that pre- scribe the server's standard and failure semantics, but also of a sto- chastic specification. The stochastic requirements should prescribe a minimum probability s, that the standard behavior Sr is observed at runtime, as well as a maximum probability c, that a (potentially cat- astrophic) failure different from the specified failure behavior Fr is observed. When a higher-level server u that depends on r is built, critical design decisions will depend on S, and F~. Any verification that the design satisfies u's own standard and failure functional specifications S,, and F, also relies on Sr and F~ [ 18]. To check that u satisfies its sto- chastic specifications, a designer has to rely on Sr, Cr and stochastic modeling/simulation/testing tech- niques [63] to ensure that the prob- ability of observing S, behaviors at run-time is at least s,, and the prob- ability of observing unspecified (potentially catastrophic) behaviors outside S,, or F, is smaller than c,,. If c, is small enough to allow demon- strating that the design of u meets the stochastic requirements s,,, c,, then Fr is a failure semantics that is appropriate for using r in the system u. Ifcr is significant enough to make such a demonstration impossible, the designer of u has to settle for a failure semantics F,' weaker than F,,, and redesign u by using new redundancy management tech- niques that are appropriate for F,'. To illustrate this point, consider