Hints for Computer System Design

Type git status in a repo and it answers almost instantly, with two lines you have probably stopped reading: "Your branch is up to date with 'origin/main'." and "nothing to commit, working tree clean". To say either line, Git did not read the contents of your files and did not ask the server. It answered both from information it saved earlier.

In our example, a teammate, Maya, pushed a fix to the server ten minutes ago, so the first line is simply wrong. Run git fetch and the same command changes its mind: "Your branch is behind 'origin/main' by 1 commit, and can be fast-forwarded." So why would a well built tool answer from saved information that might be wrong, and what stops that from hurting you? Butler Lampson wrote that move down in 1983, next to 26 other slogans, in this paper.

The Problem in 1983

Lampson worked in the Computer Science Laboratory at Xerox PARC in Palo Alto. His examples come mostly from systems he had worked on there: the Alto personal computer, the Ethernet, the Bravo editor, the Dover printer and the Grapevine mail system. The paper was presented at SOSP '83, the ninth ACM Symposium on Operating Systems Principles (proceedings pages 33 to 48). Nine years later, in 1992, he received the ACM Turing Award "for contributions to the development of distributed, personal computing environments."

The paper opens with a warning: designing a computer system is very different from designing an algorithm. A system differs in three ways:

So he does not offer laws. He offers hints, and he lists what they are not: not novel (with a few exceptions), not foolproof recipes, not laws of system design or operation, not precisely formulated, not consistent, not always appropriate, not approved by all the leading experts, not guaranteed to work. Most of them, he writes, "are part of the folk wisdom of experienced designers." He decorates the paper with quotations from Hamlet, most from Polonius' advice to Laertes.

The Map

He organizes the slogans in a table, Figure 1, along two axes:

Each hint is summarized by a slogan, which when properly interpreted reveals its essence. Figure 1 organizes the slogans along two axes:

Why it helps in making a good system: with functionality (does it work?), speed (is it fast enough?), or fault-tolerance (does it keep working?).

Where in the system design it helps: in ensuring completeness, in choosing interfaces, or in devising implementations.

(p. 34)

Here is Figure 1, redrawn:

That is 27 different slogans. Some appear more than once: end-to-end three times, use hints and make actions atomic twice, and in the paper double lines join the copies. The body follows the columns: functionality (section 2), speed (section 3), fault-tolerance (section 4). This page, like the video, takes one path through it: simple interfaces first, then the speed tricks, then how systems keep working.

Do One Thing Well

The biggest cell is about interfaces, which Lampson calls "the most important part of system design" and usually "the most difficult." An interface is the set of assumptions each side may make about the other. It has to be simple, complete, and allow a small, fast implementation, and those three pull against each other.

Do one thing at a time, and do it well. An interface should capture the minimum essentials of an abstraction. Don't generalize; generalizations are generally wrong.

(p. 35)

Clients depend on two things: what the interface does, and that it does it at a reasonable cost. Now stack interfaces the way real systems do. Lampson's example: six levels, each costing 50% more than is reasonable. Adding would suggest about three times the cost. But each level pays for everything below it, so the costs multiply:

In his words, "the service delivered at the top will miss by more than a factor of 10." So an interface must not promise "more than the implementer knows how to deliver," and its cost must be predictable.

Generality's Price

Two words first. Virtual memory lets a program use more memory than the machine has by keeping pages of it on the disk; a page fault is the moment a program touches a page that has to come from the disk.

"The extra functionality is bought at a high price," and the people who built Pilot were "highly competent and experienced."

An abstraction can also hide a cost. One major commercial system had FindIthField, which finds the i-th field of a document by scanning from the start, so it takes time proportional to the document's length. FindNamedField was then written the natural way: fetch field 0, then field 1, then field 2, each scanning from the start again. Every step looks cheap; the total grows with the square of the length, O(n²). The slogan: get it right. "Neither abstraction nor simplicity is a substitute for getting it right."

Fast, Not General

Make it fast, rather than general or powerful. If a basic operation is fast, each client can build what it wants on top. If it is slow and powerful, "the client who doesn't want the power pays more for the basic function." Lampson's example: studies show programs spend most of their time on loads, stores, tests for equality and adding one, so machines like the 801 and the RISC, which do those quickly, run programs faster for the same hardware than the VAX, whose powerful instructions are slower in the simple cases. "It is easy to lose a factor of two."

To find where your own time goes, measure: "it is normal for 80% of the time to be spent in 20% of the code," and intuition usually can't find that 20%. Tuning Interlisp-D with measurement tools sped it up by a factor of 10.

Leave it to the client. Solve one problem and let the client combine the rest. His example is the subject of the Unix paper: small programs that each take streams in, do one operation, and write streams out.

Stable Interfaces

Keep basic interfaces stable. An interface is a set of assumptions shared by many parts, and without type checking there is no way to track down every client. Once a system grows past 250,000 lines of code, "the amount of change becomes intolerable," so you break it into pieces joined by interfaces that stay stable for years.

Keep a place to stand if you must change one: a compatibility package that runs the old interface on top of the new system. Tenex kept old software running by simulating the supervisor calls of TOPS-10; the IBM 360/370 emulated older machines like the 1401 and 7090.

Git makes the same kind of promise. Its git status --porcelain format "will remain stable across Git versions and regardless of user configuration," while the default output's "contents and format are subject to change at any time." One interface for people, free to change; one for programs, held still.

Cache Answers

The first speed trick: cache answers to expensive computations, rather than doing them over. Lampson describes a cache entry as the triple [f, x, f(x)], kept so you can look up f(x) instead of computing it. The hard part is when f "can give different results with the same arguments": then you need a way to invalidate or update the entry. His example: keep the sum of 1,000 numbers; when one changes, subtract the old value and add the new one. And "the secret of success is to organize the cache so that small changes only invalidate a few entries."

This is how git status can say "working tree clean" without rereading every file. For each tracked file, Git's index saves the expensive answer, the file's hash (a short fingerprint computed from every byte of the file), next to cheap facts read with lstat: size, change times and a few more. On the next status Git compares the cheap facts. If they match, it usually trusts the saved hash; if they differ, it can mark the file changed without reading its contents. One edited file, one invalidated entry. A timestamp edge case below requires a content check.

Git also knows when its cheap facts could fool it. A file edited right after the index was written can keep the same timestamp and look unchanged (the "racy Git" problem), so for files whose timestamp is not older than the index file, Git compares the contents too.

A Saved Answer That May Be Wrong

origin/main is Git's record of where the server's main was the last time you talked to the server. Git moves it only when it talks to the server, and status uses it to say "up to date" without the network. In our example Maya pushes, the server's main moves on, your record does not, and status says "up to date". It is wrong.

That is not a bug, because of what happens next. You commit and push. The server first lists where each of its branches points right now; Git sees a commit you don't have, and moving main to your commit would throw Maya's work away. So the push is refused (real output, git 2.54.0):

 ! [rejected]        main -> main (fetch first)
hint: Updates were rejected because the remote contains work that you do not
hint: have locally. This is usually caused by another repository pushing to
hint: the same ref. If you want to integrate the remote changes, use
hint: 'git pull' before pushing again.

You fetch, your record catches up, you combine the two commits, and the push goes through. The saved answer made every status instant; the check at the server made sure the wrong answer never cost anyone their work. (git push --force-with-lease makes the same check explicit: it overwrites only if the server's branch still matches your remote-tracking branch, which the Git docs call "a heuristic.")

Use Hints

Lampson has a name for that record:

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 be wrong, and it is not necessarily reached by an associative lookup. Because a hint may be wrong, there must be a way to check its correctness before taking any unrecoverable action. It is checked against the truth, information which must be correct, but which can be optimized for this purpose and need not be adequate for efficient execution.

(p. 43)

Calling origin/main a hint is our mapping, not Lampson's. His own examples:

• The Alto's disk. Every disk page carries a label with its file's identifier and page number: that is the truth. Directories and page maps are hints that make finding a page fast. Information from a hint "is checked when it is used, by checking the label," and if it proves wrong, "all of it can be reconstructed by scanning the disk."
• Smalltalk calls. A call site remembers the type it saw last time and jumps straight to that code, checking the type first. "Measurements show that this cache hits about 96% of the time."
• The Ethernet. No carrier on the cable is "a hint that a packet can be sent." Two senders that take the hint at once collide, both notice, wait a random time and try again; after n collisions in a row each takes it as a hint of 2ⁿ senders and waits longer.

Like a cache entry, a hint exists to make the system faster, so "it must be correct nearly all the time."

Brute Force and Background

When in doubt, use brute force. "A straightforward, easily analyzed solution" that burns computing beats "a complex, poorly characterized one which may work well if certain assumptions are satisfied." Ken Thompson's chess machine Belle relied mainly on special hardware to generate moves and evaluate positions rather than on sophisticated strategy, and won the world computer chess championship several times. The 7040 Watfor compiler used a plain linear search for symbols, because student programs have so few that a smarter structure could never recover its setup time.

Compute in background. Do as little work as possible before responding, and do the rest when the machine is idle: mail can be delivered in the background ("within an hour or two is usually acceptable"), and many banks consolidate accounts at night. Batch processing is its cousin: the Bank of America's tellers' system ran all day, but each morning its data was replaced by the results of the night's batch run.

Git does both. A commit records a full snapshot; each changed file is stored whole, as a "loose" object. Later Git packs loose objects into one packfile, storing similar versions as deltas, and by default the automatic git gc --auto runs in the background (gc.autoDetach defaults to true).

Avoid Disaster

The completeness row is about the worst day.

• Separate normal and worst case. "The normal case must be fast; the worst case must make some progress." One crash a week can be "a cheap price to pay for 20% better performance," as long as recovery works.
• Safety first. "Strive to avoid disaster, rather than to attain an optimum." His two-thirds capacity rule of thumb applies unless the load can be characterized extremely well; it is a warning for general-purpose or less predictable loads, not a hard physical limit. The first paging systems tried clever tricks to squeeze every byte; "No one ever learned how to do this." Memory got cheaper, and the only thing that mattered was to avoid thrashing, where a system "spends all its time waiting for the disk."
• Shed load. Refuse new users, limit the jobs, discard packets. The Arpanet's original rule guaranteed delivery of every accepted packet; it made deadlock (parts of a system waiting on each other forever) very hard to avoid, and was eventually abandoned. The Pup internet "has always ruthlessly discarded packets at the first sign of congestion."

Keep Working

End-to-end. Recovery at the application level is the check that is truly necessary; any other check "is strictly for performance." His example: to trust a file copied from machine A to machine B, read it back from B's disk and compare a 64-bit checksum with one computed from A's. Lampson credits the observation to Saltzer, the subject of the end-to-end paper.

Log updates. A log is append-only, so it is cheap to write and "easy to ensure that the log is valid no matter when a crash occurs." Each entry records an update procedure and its arguments, and the procedure must be a true function. "When a log holds the truth, the current state of the object is very much like a hint."

Make actions atomic or restartable. An atomic action (a transaction) "either completes or has no effect," so recovery never deals with a half-done change; databases do it with a log and a commit record. A log entry should be restartable, safe to run again: "storing a set of values into a set of variables is a restartable action; incrementing a variable by one is not." In our example, setting a balance to 50 twice leaves 50; adding one twice adds two. "Sometimes such an action is called idempotent."

Git changes many of its files this way. From its lockfile.h: "we create a lockfile <filename>.lock, write the new file contents into it, and then rename the lockfile to its final destination <filename>," so readers see either the old contents or the new ones (where the file system renames atomically).

Where It Lives Today

Put the map over the tool you started with (the mapping is ours, not a claim that Git's authors followed Lampson):

What Aged

Lampson rewrote it himself. In 2020 he published Hints and Principles for Computer System Design, "this new long version of my 1983 paper." He writes that for many years he "saw no reason to rewrite or extend" it, but since the mid-1990s the Internet, the web, search engines, mobile phones, social media and more became part of everyday life, "and concurrency and scaling are now dominant themes in systems." He reorganized the hints around goals (Simple, Timely, Efficient, Adaptable, Dependable, Yummy: STEADY) and techniques (Approximate, Incremental, Divide & Conquer: AID).

Hints need a backup path, and "unrecoverable" is wider than it looked. His 2020 definition: a hint "bypasses an expensive computation if it's correct; it's cheap to check that it's correct, and there's a (perhaps more expensive) backup path that will work if it's wrong." His example is the processor: it "predicts whether a conditional branch will be taken; the check is to wait for the condition, the backup is to undo any state changes." The 1983 paper already had this in the S-1, with one prediction bit per instruction. The Spectre research, made public in January 2018, showed the undo was incomplete: when a guess is wrong the CPU "reverts any changes made to its nominal microarchitectural state. However, changes made to the cache state are not reverted," and those changes can leak information. Speculative execution's errors, the authors write, "were previously assumed to be safe."

One brute force example flipped. In 1983 Lampson cited "the success of personal computers over time-sharing systems." In 2020 he notes that virtual machines, which isolate different users of one machine, "are the backbone of cloud computing."

The Takeaway

We skipped split resources, static analysis, dynamic translation, use procedure arguments, don't hide power, divide and conquer, use a good idea again and the Grapevine example: each needs its own story to teach properly. Two cells point to other papers in this library: "plan to throw one away" cites Brooks (No Silver Bullet is his), and Lampson's advice on interfaces points to "Parnas' classic paper" (On the Criteria to Be Used in Decomposing Systems into Modules). Lampson ends with an admission:

Such a collection of good advice and anecdotes is rather tiresome to read; perhaps it is best taken in small doses at bedtime. In extenuation I can only plead that I have ignored most of these rules at least once, and nearly always regretted it.

(p. 47)

Make the normal case fast with answers you saved earlier, and keep a cheap way to check them against the truth before anything you can't undo.

Every hint here keeps data somewhere clever: a cache, an index, a log, a packed file. Which raises the question that Codd's relational model answers: what if a program could ask for data only by what it means, never by where it is stored, so the system could change all those clever structures without breaking a single program?

References

• Butler W. Lampson, "Hints for Computer System Design," SOSP '83, Proceedings of the Ninth ACM Symposium on Operating Systems Principles, October 1983, pp. 33 to 48. ACM Digital Library.
• Butler Lampson, "Hints and Principles for Computer System Design," 2020 (revised 2021). arXiv:2011.02455.
• ACM A.M. Turing Award, Butler W. Lampson. amturing.acm.org.
• Git documentation and source (git/git): Documentation/technical/racy-git.adoc, git-status, git-push, git-gc, gitprotocol-pack, lockfile.h. git-scm.com/docs and github.com/git/git.
• Scott Chacon and Ben Straub, Pro Git, chapters "What is Git?", "Remote Branches", "Packfiles", "Plumbing and Porcelain." git-scm.com/book.
• Paul Kocher et al., "Spectre Attacks: Exploiting Speculative Execution." spectreattack.com. Google Project Zero, "Reading privileged memory with a side-channel," January 2018. googleprojectzero.blogspot.com.