Hints For Reckoner Arrangement Design, Acm-Os'83

My seminar on cloud computing systems has started today amongst 2 papers. Here is the summary of the showtime newspaper nosotros covered inward the seminar.

Designing a figurer arrangement is rattling dissimilar from designing an algorithm: The external interface (that is, the requirement) is less exactly defined, to a greater extent than complex, as well as to a greater extent than dependent to change. The arrangement has much to a greater extent than internal structure, as well as thence many internal interfaces. The stair out of success is much less clear. In this 1983 paper, Butler Lampson gives hints for figurer arrangement pattern based on his sense on edifice several systems inward Xerox PARC labs. It is amazing how relevant as well as how fresh these hints are after xxx years of their publication. While these hints were non specifically targeting distributed systems design, several of these hints are applicable (and widely used) for cloud computing systems.

Most of the text below is verbatim copied from the paper. I omitted almost one-half of the hints, as well as details/justifications almost the hints. The actual newspaper is 27 pages long, as well as is good worth a read. A related newspaper is past times Jim Waldo, called "On System Design". Another related paper, targeting cloud computing arrangement pattern is past times James Hamilton, called "On designing as well as deploying Internet scale services". We volition comprehend that newspaper at the terminate of the semester inward our seminar.

Hints pertaining to Functionality

"An interface separates an implementation of closed to abstraction from the clients who utilization the abstraction." I recall most people are familiar amongst this definition. But, I guess, the side past times side observation may come upwardly every bit a revelation to many (except those that receive got studied formal methods as well as plan verification). "The interface betwixt 2 programs consists of the laid of assumptions that each programmer needs to brand almost the other plan inward club to demonstrate the correctness of his program." The argue this Definition of interface is lesser-known could live because this aspect of interfaces make non demo upwardly often on traditional APIs. But this type of rely-guarantee interfaces is rattling relevant as well as of import for right arrangement design. A ingredient relies on closed to assumptions to live able to render its guarantees.

Defining interfaces is the most of import component division of arrangement design. Usually it is likewise the most difficult, since the interface pattern must satisfy 3 conflicting requirements: an interface should live simple, it should live complete, as well as it should acknowledge a sufficiently small-scale as well as fast implementation.

Keep it simple: Do i matter at a time, as well as make it well. An interface should capture the minimum essentials of an abstraction.

Make it fast, rather than full general or powerful, as well as leave of absence it to the client: The Unix arrangement encourages the edifice of small-scale programs that receive got i or to a greater extent than graphic symbol streams every bit input, create i or to a greater extent than streams every bit output, as well as make i operation. When this vogue is imitated properly, each plan has a elementary interface as well as does i matter well, leaving the customer to combine a laid of such programs amongst its ain code as well as accomplish exactly the upshot desired.

Handle normal as well as worst cases separately: The requirements for the 2 are quite different; The normal illustration must live fast. The worst illustration must brand closed to progress. Caches as well as hints are examples of especial handling for the normal case, but at that topographic point are many others.

Hints pertaining to Speed

Split resources inward a fixed way if inward doubt, rather than sharing them. Use static analysis if you lot can. Cache answers to expensive computations, rather than doing them over. Safety first, optimize later.

Use hints to speed upwardly normal execution: A hint, similar a cache entry, is the saved outcome of closed to computation. It is dissimilar inward 2 ways: it may live wrong, as well as it is non necessarily reached past times an associative lookup. Because a hint may live wrong, at that topographic point must live a way to depository fiscal establishment stand upwardly for its correctness earlier taking whatever unrecoverable action. It is checked against the 'truth', information that must live right but tin live optimized for this purpose rather than for efficient execution. Like a cache entry, the purpose of a hint is to brand the arrangement run faster. Usually this way that it must live right nearly all the time. Hints are rattling relevant for speculative execution, as well as you lot tin disclose several examples of hints as well as speculative execution inward figurer systems. One illustration of a hint is inward the Ethernet, inward which lack of a carrier signal on the cable is used every bit a hint that a package tin live sent. If 2 senders receive got the hint simultaneously, at that topographic point is a collision that both tin detect; both stop, delay for a randomly chosen interval, as well as and so travail again.

Shed charge to command demand, rather than allowing the arrangement to larn overloaded: There are many ways to shed load. An interactive arrangement tin spend upwardly novel users, or fifty-fifty deny service to existing ones.

Hints pertaining to Fault-tolerance

End-to-end: Error recovery at the application grade is absolutely necessary for a reliable system, as well as whatever other mistake detection or recovery is non logically necessary but is strictly for performance. (Caveats: There are 2 problems amongst the end-to-end strategy. First, it requires a inexpensive bear witness for success. Second, it tin Pb to working systems amongst severe performance defects that may non appear until the arrangement becomes operational as well as is placed nether heavy load.)

Log updates to tape the truth almost the dry ground of an object: A log is a rattling elementary information construction that tin live reliably written as well as read, as well as cheaply forced out onto disk or other stable storage that tin live a crash. Because it is append-only, the amount of writing is minimized. To utilization the technique, tape every update to an object every bit a log entry consisting of the refer of the update physical care for (a.k.a. operation) as well as its arguments. The functioning specified past times the log entry tin live re-executed later, as well as if the object beingness updated is inward the same dry ground every bit when the update was showtime done, it volition terminate upwardly inward the same dry ground every bit after the update was showtime done. By induction, this way that a sequence of log entries tin live re-executed, starting amongst the same objects, as well as create the same objects that were produced inward the master copy execution.

Make actions atomic or restartable: An atomic activeness (often called a transaction) is i that either completes or has no effect. The advantages of atomic actions for fault-tolerance are obvious: if a failure occurs during the activeness it has no effect, so that inward recovering from a failure it is non necessary to bargain amongst whatever of the intermediate states of the action.

Summary of the hints

Final remarks

Butler Lampson (Turing abide by winner inward 1992) is a large proponent of using formal methods inward systems design. His ideas at that topographic point are heavily influenced past times Nancy Lynch's piece of work on I/O automata as well as simulation relations. The basic stance is to model the arrangement at a high grade using an I/O automaton as well as bear witness security as well as progress properties on this model. Then the arrangement is refined gradually past times writing to a greater extent than concrete I/O automata as well as proving that the concrete I/O automata "refine" (a.k.a. implement) the demeanour of the abstract I/O automaton using frontward as well as backward simulation techniques. (Refinement way that all the collective demeanour of the concrete automata is a demeanour of the abstract automaton.) See Lampson's course of report notes for details.

A related way of looking at arrangement pattern is past times Leslie Lamport. In Lamport's approach, refinement is non proved past times simulation relations of I/O automata, rather past times mathematical precondition/postcondition reasoning on dry ground machines. Lamport has designed the TLA framework to assistance inward this process. Another highlight of Lamport's approach is its emphasis on invariant-based reasoning/design for taming/overcoming the concurrency problems inward distributed systems. Invariant-based pattern provides a non-operational way to argue almost concurrent systems as well as avoids the complexities as well as bugs of operational reasoning (a.k.a. handwaving) for concurrent systems. For invariant-based reasoning, it is plenty to regard each operation/procedure in i lawsuit (instead of several times inward a describe for operational reasoning) as well as bear witness that the physical care for preserves the invariant. After proving each physical care for preserves the invariant, nosotros are guaranteed past times induction that regardless of execution sequence of the procedures the invariant continues to concur inward the system. So the security atmospheric condition inward the invariant are satisfied throughout the execution, as well as progress atmospheric condition tin live proved assuming/using this invariant every bit a starting betoken as well as showing a variant function. For details run across my Spring'10 distributed systems course notes.

Both approaches are instances of the stepwise refinement stance of Dijkstra (Turing abide by winner inward 1972). The work inward both approaches are, every bit nosotros movement to to a greater extent than concrete models things larn rattling complicated as well as larn unavoidably operational due to the large amount of state, libraries, as well as context introduced. As a result, these approaches cannot scale without closed to compiler support. Yet, non all is inward vain. The dependent of proving at the pattern grade prevents major pattern errors. During implementation closed to implementation grade errors could live introduced, however, those are non major errors as well as easier to ready compared to pattern errors. I promise to write a brace posts almost invariant-based pattern as well as stepwise refinement later.

Share this post