Teaching Sand to Think

Start with a beach. Most of the sand on it is quartz, which is silicon bonded to oxygen. Heat it with carbon in an arc furnace and the oxygen leaves. Refine what remains until fewer than one atom in a billion is anything other than silicon, grow it into a single flawless crystal taller than a person, and slice that into wafers thinner than a fingernail. Then print switches onto the wafer, each one smaller than a virus, tens of billions of them on a piece the size of your thumbnail.

That piece of sand is in your pocket. It adds billions of numbers a second, keeps a lifetime of photographs, reaches almost any other machine on the planet in a fraction of a second, and since about 2022 it can hold a reasonable conversation about nearly anything.

None of this was designed at once. It was built in layers over about ninety years by people who mostly never met. Each layer takes something unreliable or awkward underneath and turns it into something dependable on top, so that the people working above it can forget what lies below. A transistor is a noisy analog device, and the layer above treats it as a perfect 1 or 0. A network loses packets, and the layer above delivers every byte in order. Most of the time the forgetting works. The interesting parts of computer science, and nearly all of the outages, live in the places where it doesn’t.

This essay builds the machine from the sand up, in roughly the order people worked it out. Each section starts with a problem the previous one left behind, follows the idea that solved it and the people who had it, and then shows how that layer fails, because failure is usually where you find out what a layer really does. A date above each section marks when its central idea arrived. You don’t need any background: every term is explained where it first appears. Every dotted link opens a part of this site that goes much further, with the code and the diagrams.

Begin with the smallest useful thing: a switch, which is either on or off. Call on 1 and off 0. One such value is a bit, and everything a computer will ever do is built out of bits.

Why only two states, when a dimmer switch has infinitely many? Because electricity is noisy. Voltages sag, wires pick up interference from their neighbors, parts drift as they warm up. A circuit that had to tell ten voltage levels apart would misread them constantly. A circuit that only asks “nearer high, or nearer low?” almost never does, and each stage restores its output to a clean high or low, so noise never accumulates across billions of stages. This is the digital abstraction, and the whole field stands on it. Below it lies a continuous, messy physical world. Above it, ones and zeros that are exactly what they claim to be.

The logic arrived almost a century before the hardware. In 1854 George Boole, a largely self-taught mathematician teaching in Cork, published an algebra of true and false that he meant as a model of human reasoning: AND, OR, NOT, and the rules for combining them. For eighty years it was a curiosity of philosophy. Then in 1937 Claude Shannon, a 21-year-old master’s student at MIT, showed that the relay circuits in telephone exchanges obey Boole’s algebra exactly. Two switches in series pass current only when both are closed: AND. Two in parallel pass it when either is: OR. A switch that opens when its control is energized gives NOT. From that point, any rule you could state precisely in logic, you could build out of switches.

The first electronic computers built it from vacuum tubes, which glow, run hot and burn out. ENIAC, completed in 1945, used about 17,500 of them, filled a large room and lost a tube every couple of days. The replacement came in December 1947 at Bell Labs, where John Bardeen and Walter Brattain, working in William Shockley’s group, demonstrated the first transistor: a switch with no moving parts and nothing to burn out. In the kind used today, a voltage on one terminal, the gate, lets current flow between the other two or stops it. In 1958 and 1959 Jack Kilby at Texas Instruments and Robert Noyce at Fairchild worked out how to make many transistors and the wires between them together on one piece of material. That was the integrated circuit, and the chip.

A modern logic gate is two to six transistors. Everything else in the machine is gates.

Gates can decide. To compute, they have to do arithmetic. Add two bits: 0 + 0 is 0, 0 + 1 is 1, and 1 + 1 is 10 in binary, a 0 with a 1 carried into the next column. An XOR gate, on when exactly one input is on, produces the sum digit, and an AND gate produces the carry. That pair is a half adder. Give it a third input for the incoming carry and it becomes a full adder; chain 64 of those, each passing its carry to the next, and you can add 64-bit numbers. Waiting for a carry to ripple through 64 stages is slow, so real chips use carry-lookahead circuits that work out all the carries in parallel. It is an early example of a trade the field makes constantly: spend more hardware to save time.

Subtraction comes nearly free. In two’s complement, the standard way to store signed numbers, you negate a number by flipping its bits and adding one, so the same adder handles negative numbers with no extra circuitry. Multiplication is shifting and adding, and division is the long division you learned at school, done in binary.

Then memory. Feed two gates’ outputs back into each other’s inputs and the loop holds its value after the input goes away. That loop, a latch, is the seed of all memory. Add a clock, a signal ticking billions of times a second that tells every latch when to update, and a pile of gates becomes a machine that steps from one state to the next in lockstep. Latches built from six transistors (SRAM) are fast and expensive and make up the processor’s caches. Main memory (DRAM) stores each bit as a little charge in a capacitor guarded by one transistor. It is far denser, but the charge leaks, so every row must be read and rewritten about every 64 milliseconds. Your laptop’s memory is forgetting everything, all the time, and being reminded fast enough that nobody notices.

In 1965 Gordon Moore, who went on to co-found Intel, observed that the number of transistors on a chip was doubling at a steady rate; in 1975 he settled on every two years. Intel’s first microprocessor, the 4004 of 1971, had about 2,300 transistors. A current phone processor has tens of billions. For three decades each smaller transistor also drew proportionally less power, a rule Robert Dennard of IBM set out in 1974, so chips got faster without getting hotter. Dennard scaling ran out around 2005: push the clock any faster and the chip cooks itself. Clock speeds have stayed in the same few-gigahertz range ever since, and manufacturers have added more cores instead. That one physical fact is why modern software has to do many things at once, and why concurrency bugs turn up in nearly every section that follows.

The abstraction leaks. In 2014 researchers showed that reading one row of DRAM hundreds of thousands of times in quick succession disturbs the charge in the neighboring rows and flips bits the program never touched. Within a year Google’s Project Zero turned this effect, Rowhammer, into an attack that took full control of the operating system. Physics sits under every layer of this story, and every so often it gets through.

We now have a machine that can store and add bits. Nothing about a bit says what it means. Press Enter on a USB keyboard and it sends the number 40; nothing about the pattern 00101000 says “Enter.” A pattern of bits means whatever two sides have agreed it means, and most of computing is built on such agreements.

Eight bits make a byte, with 256 possible patterns. Read as a binary number, 00101010 is 42. Every fixed-width number has an edge, though. On 4 June 1996 the first Ariane 5 rocket veered off course and destroyed itself 37 seconds after launch, because guidance software reused from the slower Ariane 4 converted a 64-bit velocity into a 16-bit integer and the new rocket’s value didn’t fit. Unix systems that count time as a signed 32-bit number of seconds since 1970 reach their edge at 03:14:07 UTC on 19 January 2038.

Fractions are worse. Floating point stores numbers the way scientific notation does, as digits and an exponent. It covers an enormous range, but most decimal fractions can only be approximated in binary, which is why 0.1 + 0.2 comes out as 0.30000000000000004. Small errors compound. In February 1991 a Patriot missile battery in Dhahran had been running for about a hundred hours, counting time in tenths of a second with a truncated binary approximation of 0.1. The accumulated drift reached a third of a second, enough for its radar to look in the wrong place for an incoming Scud. Twenty-eight soldiers died.

Text is numbers under another agreement. ASCII, standardized in 1963, gave 128 numbers to English letters, digits and punctuation, and every other language improvised its own incompatible extension. Unicode now assigns a number to roughly 150,000 characters across the world’s writing systems, and UTF-8 stores each one in one to four bytes, with plain English still costing one. When two programs disagree about the encoding, you get the garbled characters everyone has seen on a badly built web page.

Shannon returns here. In 1948, at Bell Labs, he defined information precisely: the less predictable a message, the more information it carries, measured in bits. Predictable data can therefore be squeezed, which is what ZIP files, JPEGs and video codecs do, and truly random data can’t be compressed at all. Run the idea in reverse and you get error-correcting codes, extra bits arranged so that damage can be detected and repaired. Server memory uses them because stray particles, cosmic rays included, flip bits more often than you would guess. In a 2003 Belgian election, one flipped bit in a voting machine added exactly 4,096 votes (2 to the 12th) to one candidate. The total exceeded the number of eligible voters, which is the only reason anyone noticed.

Everything is bits plus an interpretation, including, as the next section shows, the instructions themselves.

A circuit of gates does one fixed job. ENIAC could compute almost anything, but changing what it computed meant rearranging cables and switches by hand, which took days. The machine needed a way to be told what to do.

The idea came before any electronic computer existed. In 1936 Alan Turing, aged 24, described a machine that reads and writes symbols on a tape by following a table of rules. Then he proved that one such machine, handed the rule table of any other as data, can do whatever that other machine does. One universal machine was enough. In 1945 John von Neumann, writing up the design discussions of the team that built ENIAC, described the practical version: keep the program in the same memory as the data. On 21 June 1948 the Manchester “Baby” ran the first program stored that way. A computer is a machine that reads its own instructions.

The processor runs a loop: fetch an instruction from memory, decode it, execute it, repeat, a few billion times a second on each core. The instructions are humble (add these, compare those, load from memory, store to memory, jump elsewhere if a condition holds), and the values being worked on sit in a few dozen registers beside the arithmetic circuits. The instruction set, whether x86, ARM or RISC-V, is a contract between hardware and software. Below it, chip designers may change anything. Above it, machine code compiled decades ago still runs.

Inside that contract, processors take startling liberties. They overlap instructions like an assembly line (pipelining), keep a couple of hundred in flight at once, execute them out of order, and guess which way each branch will go before the answer is known, discarding the work when they guess wrong. The program still sees one instruction after another. In January 2018 the Spectre and Meltdown disclosures showed the illusion had a crack: speculative work that was supposedly thrown away left traces in the cache, and by timing memory accesses carefully, an attacker could read data they had no right to see. The fixes cost measurable performance across the whole industry.

The deeper constraint is distance. An addition takes a fraction of a nanosecond; fetching a value from main memory takes around a hundred. A few numbers are worth carrying in your head:

• about 1 ns to read the processor’s nearest cache
• about 100 ns to reach main memory
• tens of µs to read from a fast SSD
• about 0.5 ms for a round trip between two machines in one data center
• about 150 ms from California to Europe and back

Eight orders of magnitude separate the top of that list from the bottom, and a large part of systems design is arranging for work to happen near the top.

The main tool is the cache: a small, fast memory holding copies of recently used data, on the bet that it will be wanted again soon. Data moves between cache and memory in 64-byte lines, so walking an array in order is fast and jumping around at random is slow, even when the arithmetic is identical. Caches cause some of the strangest performance bugs there are. Two threads on different cores updating two different variables that happen to share a cache line will fight over that line, each write invalidating the other core’s copy, and the program gets slower as you add cores. This is false sharing, and no amount of reading the code will show it to you.

Caches come back at every scale from here on, always with the same three questions: what to keep, when to throw it away, and what happens when the copy and the original disagree. The complete memory picture follows them through every level.

Early computers ran one program at a time. You handed over a deck of punched cards and came back hours later for the printout, and every program carried its own code for driving the card reader, the tape drive and the printer. Two problems followed: the expensive machine sat idle while it waited on slow devices, and every program had to reinvent the same fragile plumbing. The answer was a program that runs all the other programs, the operating system.

Time-sharing systems in the early 1960s let many users work at once, and in 1969 Ken Thompson and Dennis Ritchie at Bell Labs began Unix, whose ideas (a small kernel, processes, files, and everything-is-a-file plumbing between small tools) run through Linux, macOS, Android and iOS today. The kernel is the first real program to run when the machine powers on. A tiny program in firmware loads a bootloader, which loads the kernel, which starts everything else, each stage bringing up just enough of the machine for the next. From then on the kernel owns the hardware and hands out limited access to it. The processor enforces the boundary: ordinary programs run in a restricted mode and must ask the kernel, through a system call, to open a file, get memory or send data over the network. Devices get the kernel’s attention through interrupts: when you press a key, the processor saves its place in whatever it was doing and jumps to a handler the kernel registered for the keyboard.

The kernel’s main job is sharing. A laptop runs hundreds of processes on a handful of cores, so the scheduler gives each a few milliseconds, saves its registers, loads the next one’s and moves on, fast enough that they all appear to run at once.

Inside a process, threads share memory, and that is where the trouble starts. If two threads both read a counter, add one and write it back, one of the increments can vanish: a race condition. Locks prevent that and bring their own failures. Two threads each holding a lock the other needs will wait forever, a deadlock. Locks also interact with scheduling in ways that are easy to miss. In July 1997, days after landing, the Mars Pathfinder lander began resetting itself. A low-priority task held a lock that a high-priority task needed, and medium-priority tasks kept preempting the low-priority one, so it never got to release the lock. This is priority inversion. Engineers on Earth reproduced it on a replica and uploaded a fix that turned on priority inheritance, which temporarily lends a lock holder the priority of the most important task waiting for it.

The second great illusion is virtual memory, first built on the Atlas computer at Manchester in 1962. Every process sees a large, private range of addresses. Hardware translates each address through page tables the kernel maintains, mapping 4-kilobyte pages to wherever they really live in physical memory, or on disk. Touch a page that isn’t loaded and the kernel catches the fault and fetches it. Programs can’t trample each other’s memory, because their addresses don’t lead there. When processes together want more memory than exists, the machine spends its time shuffling pages instead of working (thrashing), and Linux’s last resort is the out-of-memory killer, which picks a process and ends it. In production that is often the first sign that something has been leaking for days. Memory management covers the machinery.

The third illusion is the file. Disks deal in numbered blocks that can fail, and in writes that can be cut off halfway by a power loss; a file system turns that into named files that survive crashes. Mostly. Data written to a file usually waits in kernel memory and becomes durable only after an explicit flush, a call named fsync. In 2018 PostgreSQL developers found that on Linux, when fsync failed, the kernel could discard the unwritten data and report success on the retry. One of the most careful databases in the world had relied for years on a guarantee the kernel never actually made. Talking to the disk, the network card and everything else goes through device drivers, which is also where a large share of kernel crashes come from.

Machine code is a list of numbers, and writing large programs in it is slow and error-prone. In 1952 Grace Hopper wrote one of the first compilers, a program that translates something closer to human notation into machine code; colleagues told her computers could only do arithmetic, not write programs. In 1957 John Backus’s team at IBM shipped FORTRAN, and spent much of their effort on making its output as fast as hand-written code, because they knew nobody would adopt it otherwise. They succeeded, and programming became something scientists did instead of something only machine specialists did.

A compiler turns source into machine code in stages. It splits the text into tokens, parses them into a tree that reflects the program’s structure, checks the types, lowers the tree into a simpler intermediate form, optimizes that, and emits instructions. An interpreter skips the last steps and runs the program directly, which is simpler and slower. Modern JavaScript and Java runtimes do both: they interpret code at first, watch which paths run hot, and compile those to machine code while the program runs. That trick, just-in-time compilation, is how a browser tab became fast enough to host whole applications.

The deepest difference between languages is who manages memory. In C, which Ritchie created for Unix in 1972, and in C++, the programmer allocates and frees memory by hand. The mistakes are not just crashes; they are the largest single source of security holes in software. The Morris worm of 1988, one of the first to spread across the internet, got in by writing past the end of a buffer, and Microsoft and Google have each reported that about 70% of the serious security bugs in their big C and C++ codebases are memory-safety errors. Lisp introduced the alternative around 1959: a garbage collector that finds memory nothing refers to any more and reclaims it. Java, Go and Python work this way. That removes a whole class of bugs and adds pauses, which matter when you care about your slowest requests: in 2020 Discord rewrote a busy service from Go to Rust because garbage collection caused a latency spike every two minutes. Rust checks ownership rules at compile time instead, so memory is freed at a known point with no collector at all. Compilers and runtimes in depth lays out the trade-offs.

Types let the compiler reject whole categories of mistakes before the program ever runs. Languages also encourage different ways of thinking: statements that change state step by step, objects that bundle data with behavior, or pure functions that only map inputs to outputs. The functional style matters more than it once did, because code that never mutates shared state can’t have the races of the previous section. If you want to try these ideas with your hands, the site has practical introductions to Python, Rust and Go.

Languages make promises in both directions. C lets the compiler assume a program never does anything the standard leaves undefined, such as overflowing a signed integer, and optimize on that assumption. A safety check written to catch overflow after it happens can be legally deleted by the optimizer, because in a correct program it could never be true. Part of knowing a language is knowing what the compiler is allowed to assume about you.

With a fast machine and a language to instruct it, the next limit is the instructions themselves. Two correct programs can differ in speed by a factor of a million, and the difference is almost always in how they organize data and how much work they do.

An array keeps items side by side, so reading the thousandth is instant and scanning them is cache-friendly, but inserting one in the middle shifts everything after it. A hash table turns a key into a slot number with a hash function and finds things in close to constant time however large it grows; a large share of the lookups any web request triggers go through one. Balanced trees keep items sorted, which makes ranges and nearest neighbors cheap. Graphs model anything with connections: roads, friendships, links between web pages, calls between services. In 1956 Edsger Dijkstra, wanting a demonstration for a new computer in Amsterdam, worked out how to find the shortest route between two cities in about twenty minutes at a café table, without pencil and paper. Some form of his algorithm runs every time a map app plans a trip or a network routes a packet.

Big-O notation describes how cost grows with the size of the input. Scanning a billion unsorted items is O(n), a billion steps. Binary search over sorted data is O(log n), about thirty. Comparing every pair is O(n²), a billion billion steps, which at a billion steps a second takes about thirty years. The classic algorithms for sorting, searching, shortest paths and dynamic programming are mostly clever ways of not doing that work, and Python in practice works through them in code.

The analysis has to cover inputs an adversary chooses. A hash table is fast on average, but if an attacker picks keys that all land in the same slot, every lookup becomes a linear scan. In 2011 researchers showed that a single crafted web request could pin a server’s processor for minutes by flooding the hash table that parsed its form fields, and many languages switched to randomized hashing in response. Regular expressions hide the same trap. On 2 July 2019 Cloudflare deployed one new firewall rule whose regular expression backtracked catastrophically on certain inputs. CPU use hit 100% on its servers worldwide, and much of the web returned errors for about half an hour.

Some of the most useful structures give up exactness on purpose. A Bloom filter, described by Burton Bloom in 1970, answers “have I seen this key?” using a few bits per item. It is never wrong when it says no, and wrong at a rate you choose when it says yes. That trade will earn its keep in front of a database later in this essay.

And some problems can’t be solved at all. Turing proved in the same 1936 paper that no program can decide, for every program and input, whether that program will eventually stop: the halting problem. Many practical problems (scheduling, routing, packing) have answers that are easy to check but, as far as anyone knows, hard to find. Stephen Cook made that precise in 1971, and whether the gap is real is the P versus NP question, still open. Cryptography depends on problems believed to be hard in exactly this sense, such as factoring enormous numbers. The next section relies on one.

At 10:30 in the evening on 29 October 1969, a student at UCLA tried to log in to a computer at the Stanford Research Institute, 350 miles away, over a new network called ARPANET. He typed L and O, and the receiving machine crashed. The first message ever sent over the network that became the internet was “LO.”

ARPANET used packet switching, an idea developed independently by Paul Baran and Donald Davies in the 1960s: instead of reserving a circuit for each conversation, as the telephone network did, chop data into small packets, each carrying its destination, and let every link carry packets from many conversations. Today the internet connects devices from thousands of manufacturers across networks run by tens of thousands of organizations, none coordinating in real time. It works because of layering. Wi-Fi or Ethernet moves frames between neighboring devices. The Internet Protocol (IP) gives every machine an address and forwards packets hop by hop, each router choosing the next hop, with no promise of delivery. TCP builds a reliable, ordered stream of bytes on top: it numbers the bytes, waits for acknowledgments and resends whatever goes missing. Vint Cerf and Bob Kahn designed the pair in 1974, and on 1 January 1983 ARPANET switched over to them in a single day. Applications ride above. In 1989 Tim Berners-Lee at CERN proposed the World Wide Web, and its protocol, HTTP, still carries most of what you do online.

TCP also has to decide how fast to send, and the internet learned that the hard way. In October 1986 the link between Lawrence Berkeley Laboratory and UC Berkeley, about four hundred yards apart, fell from 32,000 bits per second to 40. Senders were retransmitting lost packets as fast as they could, the retransmissions caused more loss, and the network spent its capacity carrying copies destined for the bin. This is congestion collapse: useful throughput falls as load rises. Van Jacobson’s fix, deployed in 1988, made senders cut their rate sharply at the first sign of loss and then creep back up. TCP still works this way, and the shape of the problem (more load, less useful work) will return, much larger, inside the data center.

Ordered delivery has a cost. When one packet is lost, everything behind it waits, even data that has already arrived. This is head-of-line blocking, and it is one reason HTTP/3 runs over QUIC, which carries independent streams over UDP so that a loss stalls only its own stream. The advanced protocols chapter covers it and its relatives.

A machine also has to find the one it wants. DNS, introduced in 1983, turns a name into an address through a hierarchy of servers, and every resolver along the way caches the answer for as long as its time-to-live allows, which is why a bad DNS record keeps doing damage for hours after it is fixed. Underneath, networks tell each other which addresses they can reach using BGP, a protocol that runs largely on trust. In February 2008 Pakistan Telecom, ordered to block YouTube inside the country, announced a more specific route to YouTube’s addresses. The announcement leaked to the rest of the internet, and for about two hours much of the world’s YouTube traffic went to Pakistan. Hold on to DNS and BGP. They are the two halves of one of the largest outages in history, near the end of this essay.

A public network needs secrets. In 1976 Whitfield Diffie and Martin Hellman showed how two parties can agree on a shared key over a channel everyone can read, without ever sending the key, and in 1977 Rivest, Shamir and Adleman published RSA. Both rest on problems that are easy one way and infeasible to reverse. TLS, the protocol behind the padlock in your browser, uses them to agree on a key, uses certificates signed by trusted authorities to prove the server is who it claims to be, and then encrypts everything with fast symmetric ciphers. Certificates expire, and a forgotten renewal is one of the most common causes of outages that have nothing to do with load.

Physics sets the floor. Light in optical fiber covers about 200 kilometers per millisecond, so no protocol will ever bring a New York to London round trip much under 60 milliseconds. For every layer firing in order, there is a full walk-through of what happens when you type a URL, and the complete network stack in practice shows the tools for watching it happen.

Programs end and machines restart, but a bank balance has to outlive both, and it has to stay correct while thousands of people change it at once. In the 1960s, programs stored records in linked structures and navigated them by hand, pointer by pointer, so every new question meant new code and every change to the layout broke old programs. In 1970 Edgar Codd at IBM proposed the relational model: store data as tables, and let programs say what they want rather than how to find it. A system then works out the how. SQL followed from IBM in the mid-1970s, and databases built on Codd’s idea still hold most of the world’s important records.

A database’s central promise is the transaction: a group of changes that happens completely or not at all, keeps the data consistent, is isolated from other transactions running at the same time, and survives a crash once committed. Durability comes from an old trick. Append every change to a write-ahead log and flush it to disk before reporting success; after a crash, replay the log. Replication is mostly that same log shipped to other machines.

Isolation is where the subtlety lives, because full isolation is expensive and most databases default to something weaker. Two requests read a balance of 100, each adds 50, both write 150, and a deposit has vanished: a lost update. Or two doctors on call each check that at least one other doctor is still on call, and both sign off in concurrent transactions. Each check was true when it ran, and the hospital ends up with nobody on call. This is write skew, a standard example from Martin Kleppmann’s Designing Data-Intensive Applications, and the weaker isolation levels allow it.

Underneath, storage engines strike different bargains. A B-tree, invented by Rudolf Bayer and Edward McCreight in 1970, keeps data sorted in nodes the size of a disk page, so finding one row among billions touches three or four pages. An LSM tree (1996) collects writes in memory, flushes them as sorted files and merges those in the background; it takes writes much faster, but the merging rewrites the same data several times and a read may have to check several files. Storage engines are largely a study of where you would rather pay, and database internals shows how indexes, query planners and locks sit on top of them.

Systems also have to tell the rest of the world what happened, and that is harder than it looks. If a service writes to its database and then publishes an event, one step can succeed while the other fails, and the two drift apart: the dual-write problem. The outbox pattern writes the event into a table in the same transaction as the data and has a separate process publish from that table. Messages are, in practice, delivered at least once, because a network that can lose acknowledgments makes guaranteed exactly-once delivery impossible. What well-built systems provide is exactly-once effect, using idempotency keys: a repeated “charge this card” carrying the same key is recognized and not charged twice. Payment APIs work this way, and so should anything else that moves money.

Through all of it, the shape you give your data is the decision hardest to undo.

By the late 1990s some services had more users than any single computer could handle, however large. Google’s answer was to stop buying large computers. It filled buildings with cheap, ordinary machines, assumed some of them would be failing at any moment, and wrote software to cope. Its papers on the Google File System (2003) and MapReduce (2004) showed the rest of the industry how, and the job of most backend engineers since has been to build one reliable service out of many unreliable machines.

The basic shape is simple. A load balancer spreads incoming requests across servers. The servers keep no memory of a user between requests, so any of them can take any request, and capacity grows by adding machines. The application is split into services (accounts, payments, search, notifications), each owned by its own team, packed into containers since Docker popularized them in 2013, and scheduled across thousands of machines. One click on a large website fans out into dozens or hundreds of internal calls, built from a standard kit of building blocks: queues, caches, object stores, search indexes, batch and stream processors.

Fan-out changes the statistics. Suppose a service answers in 10 milliseconds 99% of the time and takes a full second the other 1%. Call it once and you will rarely notice. Call a hundred such services in parallel and wait for all of them, and 63% of your requests hit at least one slow reply. Jeff Dean and Luiz Barroso set this out in “The Tail at Scale” in 2013: in a large system, the slowest one percent of each component becomes the normal experience of the user. That is why engineers watch 99th- and 99.9th-percentile latency rather than averages, and why some systems send hedged requests: if a reply hasn’t come back within the time that covers 95% of requests, send a duplicate to another replica and take whichever answers first, at the cost of a few percent of extra load.

Measuring the tail honestly is harder than it sounds. Many load-testing tools send a request, wait for the reply, then send the next. When the server stalls, the tool politely stops sending, so a stall that would have hit hundreds of real users (who don’t wait politely) shows up as one slow request. Gil Tene named this coordinated omission, and it makes a great many published latency numbers look far better than reality. Observability, the logs, metrics and traces that let you see inside a running system, is only as good as what it measures.

Underneath sits queueing theory. Little’s Law says the average number of requests inside a system equals their arrival rate times the average time each spends there. The standard queueing models add the uncomfortable part: time spent waiting grows like 1/(1 − utilization). At 50% busy, a request waits about one service time; at 90%, about nine; at 99%, about ninety-nine. Latency doesn’t degrade gently as a system nears capacity. It shoots up, which is why well-run systems keep headroom, and why “we’re only at 85% CPU” is less comforting than it sounds. Performance engineering is largely the practice of measuring all of this correctly, and designing a real system puts the pieces together.

In 1965 Maurice Wilkes at Cambridge proposed putting a small, fast “slave memory” in front of a large, slow one. The same idea now runs the data center. The cheapest request is the one you never make, so this city of machines is full of caches: in front of databases, inside services, and out at the edge in content delivery networks that keep copies of popular content in hundreds of cities. A cache that absorbs 99% of reads lets the database be sized for the other 1%. That makes the cache load-bearing, and its failures everyone’s problem. There are five classic ones, and every large system meets all of them.

Stampede. A popular key (say, a configuration object every request reads) expires. In the instant after, every request in flight misses at once and they all rebuild the same value from the database. The fixes: let one request recompute while the rest wait for its result (request coalescing, which Go ships as a small library called singleflight), or refresh early, with a probability that rises as expiry nears, so one request rebuilds the value before anyone misses.

Penetration. Requests for keys that don’t exist miss every time, because there is nothing to cache, and every miss goes to the database. An attacker who notices can bypass the cache entirely by asking for random IDs. Cache the “not found” answer too, or check a Bloom filter of keys that do exist before touching the database.

Avalanche. Many keys written at the same moment with the same time-to-live also expire at the same moment. The same flood arrives when a cache node dies, or a deploy leaves you with a cold cache. The fix for the first is jitter, a random amount added to every expiry; for the second, warming caches deliberately and shifting traffic gradually.

Hot keys. A celebrity’s profile or a viral post can send a large share of all traffic to the one node that owns that key. Split it into copies under different names, keep a small local cache on each server, or serve it from replicas.

Staleness. The hardest of the five is keeping the copy correct. A common race: request A reads a value from the database. Request B updates the database and deletes the cached entry. Request A, running slowly, writes its now-stale value into the cache, where it lives until it expires. Facebook’s 2013 paper on scaling memcache describes the fix it used, leases: on a miss the cache hands out a token, and it refuses a later write whose token was invalidated in the meantime. Every cache in this essay, from the processor’s to the language model’s, faces some version of this question.

The 1986 congestion collapse was the first famous instance of a pattern that keeps coming back: under enough load, a system spends its effort on work that ends up wasted, and useful throughput, called goodput, falls as demand rises. A server that answers more slowly than the client’s timeout still does all the work, but the client has already given up and, very often, asked again.

Retries are the usual accelerant. A sensible client tries a failed call three times. If the web tier, the service tier and the data tier each do that, one user request during an outage becomes 3 × 3 × 3 = 27 calls to an already drowning database, arriving exactly when it can least cope. The fixes are to retry at one layer only, to cap retries with a retry budget (retries may never exceed, say, a tenth of normal traffic), and to wait a random, growing interval between attempts.

The randomness matters because synchronization is dangerous. When a resource frees up and everything waiting for it wakes to compete, the result is a thundering herd. Clients that all reconnect the instant a server returns, health checks firing on the same second, nightly jobs scheduled for exactly midnight: each makes a spike that was in nobody’s capacity plan. The cure is jitter, applied everywhere.

Sometimes the overload outlives its cause. A brief spike pushes latency past client timeouts, the timed-out requests are retried, and the retries keep the system overloaded long after the spike has gone. The system now has two stable states, healthy and broken, and no longer needs the trigger to stay broken. A 2021 paper named these metastable failures and argued that many of the worst outages at large companies take this shape. Fixing the original fault doesn’t help. You have to remove the load that sustains the failure, often by turning most traffic away until the system recovers.

So the toolkit is mostly about refusing work early. Load shedding rejects some requests immediately and cheaply so the rest succeed. Admission control decides at the door, often by priority. Backpressure pushes “slow down” upstream, the way TCP does. Queue order matters too: a first-in, first-out queue serves the oldest requests first, and their clients have probably given up already, so some systems switch to last-in, first-out under overload. A circuit breaker stops calling a dependency that keeps failing and fails fast instead, checking now and then whether it has recovered. Bulkheads give each dependency its own pool of threads or connections, so one slow dependency can’t starve everything else. Reliability engineering goes through these patterns one by one.

A record kept on one machine is lost when that machine dies, so serious systems keep copies on several. Now those machines have to agree on what the record says, and every distributed system lives with one awkward fact: when another machine doesn’t answer, you can’t tell whether it crashed, is merely slow, or answered and the reply was lost. That uncertainty shapes everything.

To survive failures you replicate data, and then replicas can disagree. To hold more data than one machine can, you shard it, splitting it by key across machines, and then one operation may span several shards. When the network splits, the system must choose between answering with possibly stale data and refusing to answer until it is sure. Eric Brewer stated that choice as the CAP theorem in 2000, and it was proved two years later.

When machines must agree on something, such as which of them is the leader, they run a consensus protocol: Paxos, which Leslie Lamport described in 1989, or Raft, designed in 2014 to be easier to understand. Every decision needs a majority. Any two majorities of one group overlap, so two conflicting decisions can’t both win. Get it wrong and you have split brain: two nodes that each believe they are in charge, both accepting writes. On 21 October 2018 GitHub lost connectivity between its East Coast hub and its main data center for 43 seconds. Automated failover promoted databases on the West Coast. When the link returned, each side held writes the other lacked, and reconciling them took more than a day of degraded service.

A majority stops two leaders being elected, but an old leader may not know it has been replaced. It can pause for a long garbage collection, wake up and carry on writing. The defense is a fencing token, a number that rises with every new leader; storage rejects any write carrying a token older than one it has already seen.

Time itself is unreliable. Clocks on different machines drift and get corrected, sometimes backwards. A lease that expires “after ten seconds” means different things on two machines whose clocks disagree, and databases that resolve conflicts by keeping the latest timestamp lose data without any error when clocks are skewed. Leap seconds have broken large parts of the internet twice: in 2012 a Linux kernel bug sent servers at Reddit, Mozilla and elsewhere into runaway CPU use, and on New Year’s Day 2017 Cloudflare’s DNS failed because its code computed a negative duration when time seemed to run backwards. Lamport showed in 1978 that events can be ordered by causality, by what could have influenced what, without trusting clocks at all, and much of distributed systems design still builds on that paper. The patterns that follow from all this, from event sourcing to change data capture, are collected in data-intensive application patterns.

Real failures are messier than up and down. A gray failure is a node that passes its health checks while failing real work: a disk that slows only writes, a network card that drops 2% of packets. Failures are correlated, too. Three replicas in one rack share a power supply; replicas in three zones may all depend on the same authentication service, the same software and the same configuration, so one bad configuration push breaks all of them together. Remember that sentence when we get to Facebook.

Every program so far was written by people as explicit instructions. Nobody can write instructions for recognizing a cat in a photograph, or for explaining why the sky is blue in a way that fits whoever is asking. The rules are too many and too fuzzy to state.

Machine learning replaces the instructions with a function that has a great many adjustable numbers, called parameters, and a way to tune them from examples. Measure how wrong the output is (the loss), work out how each parameter should change to reduce it (the gradient), nudge them all slightly, and repeat across an enormous dataset. In 1958 Frank Rosenblatt built the perceptron, a single layer of such adjustable units, and the press predicted machines that would soon walk and talk. In 1969 Marvin Minsky and Seymour Papert proved how little a single layer can do, and funding dried up for years. The fix was more layers and a way to train them: backpropagation, popularized by David Rumelhart, Geoffrey Hinton and Ronald Williams in 1986, which is the chain rule from school calculus applied systematically through the network to compute every gradient at once.

The resulting neural network is a stack of layers, each essentially a large matrix multiplication followed by a simple nonlinear step. The ideas were decades old by 2012. What changed was data and hardware. That year a network called AlexNet, trained on two gaming graphics cards, won the ImageNet image-recognition contest with an error rate of about 15%, against 26% for the runner-up. GPUs, built to shade millions of pixels in parallel, turned out to be ideal for dense matrix arithmetic. Once again the bottom of the stack decided what was possible at the top, and GPU and parallel computing explains why.

A language model reads tokens, chunks of text a few characters long, and maps each to an embedding, a vector of thousands of numbers in which related meanings sit close together. The transformer, published by a team at Google in 2017, processes those vectors with attention: each token computes how relevant every other token is and mixes in information from the relevant ones. That is how a pronoun gets tied to a noun three sentences back. The model is pretrained on a vast amount of text with a single objective, predicting the next token, and doing that well turns out to require learning grammar, facts and a good deal of something that works like reasoning. In 2020 researchers showed that performance improves predictably as parameters, data and computation grow together, and much of the industry has organized itself around that finding. The pretrained model is then trained further on examples of good answers and on human judgments of which of two responses is better, which turns a text predictor into an assistant. When OpenAI released ChatGPT in November 2022, it became one of the fastest-adopted products in history.

Training at this scale is a distributed systems problem. Thousands of GPUs must stay in lockstep for weeks, exchanging gradients over specialized networks. Meta reported that during a 54-day stretch of training Llama 3 on about sixteen thousand GPUs, the job was interrupted unexpectedly more than four hundred times, mostly by hardware faults. Everything from the section on agreement applies: checkpoint often, watch for gray failures, assume something is always broken.

Serving is its own discipline. The model reads the whole prompt in one pass, then produces the answer one token at a time, each depending on all the tokens before it. To avoid recomputing attention over the entire conversation for every new token, the server keeps intermediate results in GPU memory, the KV cache (the same cache questions, one more time). While generating, the GPU spends most of its time moving weights and cache in from memory rather than doing arithmetic, so servers batch many users together to share each pass through the weights. Memory bandwidth sets the cost of an answer as much as raw computing power does. ML infrastructure covers how this is run.

The answer a model produces is the most plausible continuation of the text in front of it. That is usually true and occasionally wrong with complete confidence, because the model has no way to check. So modern systems give it ways to check.

The first is grounding. Turn the question into an embedding, search a collection of documents for the passages closest to it, and hand them to the model to read before it answers. This is retrieval-augmented generation, or RAG. The second is tools. The model is told, in its prompt, that certain functions exist: search the web, run code, query a database. When it decides one would help, it doesn’t run anything itself. It writes a small structured request (“call run_query with this SQL”), and ordinary code outside the model executes it and pastes the result back into the conversation. Then the model is called again. Repeat until it answers. That loop of think, act and observe is all an agent is, and it is about thirty lines of code. You can build one end to end in an afternoon, and building applications with LLMs covers what it takes to ship one.

The loop needs plumbing: memory that outlives one request, retries, limits on how many steps it may take, a person’s approval before anything irreversible. Frameworks such as LangChain and LangGraph package that plumbing. It also needs a standard way to plug in tools, and since November 2024 there is one, the Model Context Protocol: JSON messages that let any agent discover and call the tools any server offers, the way USB lets any device announce itself to any computer.

Look at what this does to the stack. The model becomes a client of every layer beneath it. Its tool calls are network requests, subject to timeouts and retries; its queries hit databases with all their isolation subtleties; its memory is a cache with all the staleness problems of the cache section. And it brings a failure mode no earlier layer had. A model reads instructions and data in the same channel, so a web page or an email it fetches can contain text that says “ignore your previous instructions,” and the model may obey. This is prompt injection, and it is to agents what the buffer overflow was to C: a confusion between data and code, waiting in every input. The defenses are the old ones. Least privilege, read-only connections, allow-lists, and a human approving anything that can’t be undone. The AI engineering landscape maps where all of this is heading.

The machine is built. From sand to agent, it is a tower of contracts. An instruction set, a system call, a file, a protocol, an API, a serialization format: each is an interface, a boundary that says what a component does without saying how, so the people on either side can work without talking to each other. Hyrum’s law adds the caveat that, given enough users, every observable behavior of a system will be depended on by someone, whatever the documentation says. The craft of software engineering is keeping those contracts while thousands of people change the code behind them every day. Version control (Git, written by Linus Torvalds in 2005 to manage the Linux kernel) records every change, tests check that the contracts still hold, delivery pipelines ship the changes, and security starts from the assumption that someone is trying to break each contract on purpose.

The machinery mostly works. When it doesn’t, the cause is usually a change somebody made. Configuration changes deserve special fear. They look harmless, often skip the review and testing code receives, and reach every server within seconds. On 19 July 2024 a faulty content update to CrowdStrike’s Falcon security software crashed about 8.5 million Windows computers, grounding flights and taking hospital systems offline, and many machines had to be repaired by hand. In 2012 Knight Capital deployed new trading code to seven of its eight servers. The eighth still ran old code behind a flag the new release reused, and in 45 minutes it traded the firm into a $440 million loss. The defenses are dull and they work: roll out in stages, starting small; let each stage bake long enough for problems to show; make rollback fast and rehearsed.

Good architecture limits the blast radius of any one failure. AWS divides many services into cells, independent copies of the whole stack that each serve a slice of customers, so a bad deploy or a poison request takes down one cell rather than the service. Static stability means the system keeps working when its control plane, the part that makes changes, is down: servers carry on with their last known configuration instead of failing when they can’t fetch a new one. The Amazon Builders’ Library has excellent essays on these.

Recovery paths need exercising too. In February 2017 an engineer debugging Amazon S3’s billing system mistyped a command and removed far more servers than intended, including two subsystems the rest of S3 depended on. Restarting them took hours. In the largest region they had not been fully restarted in years, and had grown enormously in the meantime.

Which brings us to the outage this essay has been building toward. At 15:39 UTC on 4 October 2021, during routine maintenance, an engineer at Facebook ran a command meant to measure the capacity of the company’s backbone, the network linking its data centers. A bug in the audit tool that should have caught it let it through, and it disconnected the backbone instead. Facebook’s DNS servers had a sensible safety rule: if a server lost contact with the data centers, it assumed it was the broken one and withdrew its routes from the internet using BGP, so users would be sent to a healthy server instead. But every DNS server lost contact at the same moment, so every one of them withdrew. A safety rule written for one machine fired on all of them together, which is the correlated failure from the section on agreement. Facebook, Instagram and WhatsApp vanished from the internet, and resolvers around the world, unable to get an answer, sent a flood of retries.

Then the second problem surfaced. The tools engineers needed to diagnose and repair the backbone depended on the backbone, and on Facebook’s DNS. This is a dependency cycle at bootstrap: the system can’t come back because the things needed to restart it require it to be running. Recovery took people physically entering secured data centers to reset equipment, and then restoring traffic in stages so that billions of returning users, a thundering herd of planetary size, didn’t trip a second outage on power systems and caches that had gone cold. It took about six hours.

Every idea in that story appeared earlier in this essay: DNS caching, BGP, retries, correlated failure, cold caches, the thundering herd, a control plane that needs itself to run. None of them is exotic. The outage was what happens when they line up.

You have been using the whole machine while reading this. The text arrived as UTF-8 bytes over a TLS connection carried by TCP, routed hop by hop across networks that agreed on paths with BGP, after DNS turned a name into an address. Your browser, one process among hundreds sharing a few cores, parsed it, laid out each line and asked the GPU to rasterize every letter from the outlines in a font file, and your display picked up each new frame on its next refresh, about sixteen milliseconds after the last. Under all of it, transistors on a sliver of refined sand switched billions of times a second, each one trusting a clean 1 or 0 out of a noisy voltage.

Read back over the essay and the same few ideas keep turning up, at scales a billion times apart. Each of them has a section of its own on this site.

Abstraction is the digital layer over physics, the instruction set over circuits, the process over the processor, TCP over lossy packets, the transaction over a crash-prone disk, the tool call over a model that can’t act. Every one of them leaks somewhere, from Rowhammer to Spectre to an fsync that didn’t mean what it said. Caching shows up in the processor, the page tables, DNS, the content network, memcache and the model’s KV cache, each asking the same questions about freshness and failure. Indirection is virtual addresses, domain names, load balancers and consistent hashing. Agreement is locks between threads, congestion control between strangers and consensus between servers. Feedback is the 1986 collapse, the retry storm and the metastable failure, one pattern seen three times, with the same cures each time: back off, add randomness, shed load.

Under all of them are trade-offs. Speed or safety; consistency or availability; fast writes or fast reads; a cache that protects the database right up until the day it takes it down. Knowing what the layer beneath you actually promises, and how it behaves when it can’t keep the promise, is most of what separates understanding a system from guessing about it. The evolution of computing paradigms and the philosophical foundations step back further still.

The field is about ninety years old if you count from Turing’s 1936 paper, and nearly all of it was built within living memory. The layer at the top of this essay barely worked a decade ago. Every layer you just climbed is explained in full on this site, from the transistor to the agent, with the code and the diagrams. Start at the ground floor, jump to whichever layer caught you, or read the big picture, where these threads are gathered in one place with a map of the whole field.