Excerpts from Butler Lampson's "Hints for Computer System Design"

Butler W. Lampson
Hints for Computer System Design
Ninth ACM Symposium on Operating Systems Principles
in Operating Systems Review 17,5 (October 1983) pages 33-48.
Later republished, but with less satisfactory copy editing,
in IEEE Software 1,1 (January 1984) pages 11-28.
(C) 1983 ACM 0-89791-115-6/83/010/0033 $00.75
[BibTeX versions at end of page.]

• Abstract

  Experience with the design and implementation of a number of computer systems, and study of may other systems, has led to some general hints for system design which are described here. They are illustrated by a number of examples, ranging from hardware such as the Alto and the Dorado to applications programs such as Bravo and Star.

• Introduction

  There probably isn't a best way to build the system, [...] much more important is to avoid choosing a terrible way.
  From this experience come some general hints for designing successful systems.
  I claim no originality for them; most are part of the folk wisdom of experienced designers. Nonetheless, even the expert often forgets [...].
  These [...] are just hints. Some are quite general and vague; others are specific techniques which are more widely applicable than many people know. [...] oversimplified [...] controversial.

• Functionality
  • Keep it simple
    • Do one thing at a time, and do it well.
      

      Perfection is reached, not when there is no longer anything to add, but when there is no longer anything to take away. (A. Saint-Exupery)

      An interface should capture the minimum essentials of an abstraction. Don't generalize; generalizations are generally wrong.
      When an interface undertakes too much, the result is an implementation which is large, slow, and complicated.
      [...] service must have a fairly predictable cost [...]
      
    • Get it right.
      Neither abstraction nor simplicity is a substitute for getting it right.
  • Corollaries The rule about simplicity and generalization has many interesting corollaries.
    • Make it fast, rather than general or powerful.
      If it's fast, the client can program the function it wants, [...].
      It is much better to have basic operations executed quickly than more powerful ones which are slower (of course, a fast, powerful operation is best, if you know how to get it).
      The trouble with slow, powerful operations is that the client who doesn't want the power pays more for the basic function. [Which is usually] not the right one.
    • Don't hide power.
      The purpose of abstraction is to conceal undesirable properties; desirable ones should not be hidden.
    • Use procedure arguments
      This [...] can greatly simplify an interface, eliminating a jumble of parameters whose function is to provide a small programming language.
    • Leave it to the client.
      As long as it is cheap to pass control back and forth, an interface can combine simplicity, flexibility and high performance together by solving only one problem and leaving the rest to the client.
  • Continuity
    • Keep basic interfaces stable.
    • Keep a place to stand, if you do have to change interfaces.
  • Making implementations work
    • Plan to through one away; you will anyhow.
      If there is anything new about the function of a system, the first implementation will have to be redone completely to achieve a satisfactory (i.e., acceptably small, fast and maintainable) result.
    • Keep secrets of the implementation
    • Divide and conquer
    • Use a good idea again, instead of generalizing it.
      A specialized implementation of the idea may be much more effective than a general one.
  • Handling all the cases
    • Handle normal and worst case separately as a rule, because the requirements for the two are quite different: the normal case must be fast; the worst case must make some progress.
      Sometimes radically different strategies are appropriate [...].
• Speed
  • Split resources in a fixed way if in doubt, rather than sharing them.
    It is usually faster to allocate dedicated resources, it is often faster to access them, and the behavior of the allocator is more predictable.
    
  • Use static analysis if you can;
    this is another way of stating the last slogan.
    The result [...] is known properties of the program which can usually be used to improve its performance.
    The hooker is "if you can;" when a good static analysis is not possible, don't delude yourself with a bad one, but fall back on a dynamic scheme.
  • Dynamic translation
    from a convenient (compact, easily modified or easily displayed) representation to one which can be quickly interpreted is an important variation on the old idea of compiling.
    
  • Cache answers
    to expensive computations, rather than doing them over.
  • Use hints to speed up normal execution.
    A hint, like a cache entry, is the saved result of some computation. It is different in two ways: it may sometimes be wrong, and it is not necessarily reached by an associative lookup.
    It is checked against the truth, information which must be correct, but which can be optimized for [the check] and need not be adequate for efficient execution.
    [Examples include Internet routing, Ethernet scheduling, etc.]
  • When in doubt, use brute force.
    Especially as the cost of hardware declines, a straightforward, easily analyzed solution which requires a lot of special-purpose computing cycles is better than a complex, poorly characterized one which may work well if certain assumptions are satisfied.
  • Compute in background
  • Use batch processing
    Doing things incrementally almost always costs more [... and] batch processing permits much simpler error recovery.
  • Safety first.
    In allocating resources, strive to avoid disaster, rather than to attain the optimum.
  • Shed load to control demand,
    rather than allowing the system to become overloaded.
    This is a corollary of the previous rule.
• Fault-tolerance
  • End-to-end error recovery is absolutely necessary for a reliable system, and any other error detection or recovery is not logically necessary, but is strictly for performance.
    Many uses of hints are applications of this idea.
  • Log updates to record the truth about the state of an object.
    
  • Make actions atomic or restartable.
• Conclusion

@ARTICLE{ LampsonHints83,
  author    = "Lampson, Butler W.",
  title     = "Hints for Computer System Design",
  journal   = "Operating Systems Review",
  publisher = "ACM",
  year      = 1983,
  month     = October,
  volume    = 17,
  number    = 5,
  pages     = 33-48,
  note      = "{\em Ninth ACM Symposium on Operating Systems Principles}.
               Later republished, but with less satisfactory copy editing,
               in {\em IEEE Software} 1,1 (January 1984) pages 11-28."
}

@ARTICLE{ LampsonHints84,
  author    = "Lampson, Butler W.",
  title     = "Hints for Computer System Design",
  journal   = "IEEE Software",
  year      = 1984,
  month     = January,
  volume    = 1,
  number    = 1,
  pages     = 11-28,
  note      = "This is republished, with less satisfactory copy editing, from
               {\em Ninth ACM Symposium on Operating Systems Principles} in
               {\em Operating Systems Review} 17,5 (October 1983) pages 33-48."
}

History:
1999.Mar.03   Noticed Butler now has it online.
1997.Jan.02   Written.