After Boeing Shut His Lab, He Put a Hard Drive in the Personal Computer

In 1970, when Boeing curtailed basic research, 24-year-old Edward McCreight left Seattle for Xerox PARC. Partnering with Butler Lampson, he co-designed the local disk subsystem for the Xerox Alto using roughly 55 TTL chips, 150 microinstructions, and sector label verification to tame spinning magnet

分享
After Boeing Shut His Lab, He Put a Hard Drive in the Personal Computer

A recreation of the early 1970s Xerox PARC Computer Science Laboratory featuring the Xerox Alto and Diablo disk drive. Illustration, AI-generated.

In our earlier chronicle on the origins of the B-tree (The Tree Behind Nearly Every Database Came from Boeing as It Cut 46,000 Workers), we traced the sudden contraction of Seattle's aerospace giant in 1970 and the young researchers at the Boeing Scientific Research Laboratories (BSRL).

That chapter closed with a dispersal. As Boeing cut research budgets and shifted BSRL toward short-term applied tasks, its research staff scattered. Rudolf Bayer left for academia, while 24-year-old Edward McCreight, who had implemented and benchmarked the original algorithm, headed south to California. He joined the newly established Xerox Palo Alto Research Center (PARC).

The young engineer who had run B-tree benchmarks on an IBM mainframe in Seattle did not stay in pure software.

By the early 1970s, McCreight teamed up with Butler Lampson to engineer the local disk subsystem for the prototype personal workstation: the Xerox Alto.

From blackboard algorithms in Seattle to microcode control in Palo Alto, McCreight encountered rotating magnetic media twice in quick succession. It remains one of the most compelling engineering transitions in computing history: the same systems engineer, confronting physical media bottlenecks at two completely different layers, delivered two opposite engineering solutions.

Seattle Problem: Mechanical Arms Were Slow, so Minimize Disk Seeks

The story begins before the blackboard in Boeing’s Seattle laboratory in the autumn of 1969.

According to Bayer’s 2014 memoir, Bayer sketched the core concept of a multi-way balanced index on his office blackboard. The division of labor was clear: Bayer focused on the algorithmic description and mathematical bounds, while McCreight wrote the code and conducted empirical tests on an IBM System/360 Model 44.

Their peripheral storage was an IBM 2311 moving-head disk drive with a capacity of 7.25 MB.

IBM 2311 Disk Drive

An IBM 2311 moving-head disk storage drive (7.25 MB capacity, the model utilized by Bayer and McCreight to benchmark B-trees at Boeing). Photo by ArnoldReinhold, CC BY-SA 3.0, via Wikimedia Commons.

The IBM 2311 confronted them with an unforgiving physical reality: mechanical positioning was orders of magnitude more expensive than sequential data streaming. Reading a 14-byte index element sequentially took roughly 90 microseconds; repositioning the mechanical arm to a specified cylinder and awaiting rotational latency averaged approximately 50 milliseconds. That was a five-hundred-fold discrepancy.

If one placed a standard in-memory binary search tree onto disk, tree depth would expand rapidly as records accumulated. Every step down the tree risked an independent physical seek, leaving the CPU idling while waiting for the mechanical drive heads to settle.

Bayer and McCreight responded by aligning node sizes to physical disk pages and packing as many ordered keys as possible into each node to maximize the branching factor. This became the B-tree.

Wide branching flattened the tree. In their published paper (Page 186, Figure 9), with node capacity sized for 120 keys ($k=60$), a three-level tree at full capacity held 1,771,560 keys. Looking up any record required reading at most three disk pages, drastically curtailing physical mechanical seeks.

In 1970, Boeing cut back basic scientific research and pivoted its laboratory to direct product engineering. Bayer departed for Purdue University and subsequently joined the Technical University of Munich (TUM) in 1972; McCreight moved to the newly formed Computer Science Laboratory at Xerox PARC.

At Boeing, McCreight and Bayer solved their problem through pure software algorithms: flattening the tree to spare the sluggish mechanical disk arm.

Palo Alto Problem: Catching the Unbuffered Stream under a Desk

When McCreight walked into Xerox PARC, he was handed a disk dilemma pointing in the exact opposite direction.

In Palo Alto, the team rejected time-shared mainframe terminals in favor of giving every researcher an interactive workstation with local processing and a dedicated portrait display. In his December 1972 internal memorandum Why Alto?, Butler Lampson argued Xerox needed to build dozens of real machines in a distributed network to validate personal computing.

For an individual workstation to run software and retain files independently, reliable local persistent storage was essential.

Xerox Alto Workstation and Under-Desk Cabinet

A complete Xerox Alto personal workstation. The upper hatch of the lower desk cabinet houses the Diablo cartridge disk drive slot. Photo by Joho345, Public Domain, via Wikimedia Commons.

The team chose the Series 30 Model 31 cartridge disk drive manufactured by California-based Diablo Systems, offering 2.5 MB of storage on a single platter. The unit was compact enough to slide beneath a desk inside the Alto cabinet. However, the drive was an entirely mechanical transport: it contained zero onboard RAM buffer memory.

IBM 2315 Single-Platter Disk Cartridge

An IBM 2315 single-platter disk cartridge (the Diablo Series 30 Model 31 used identical 14-inch cartridges storing approximately 2.5 MB). Photo by ArnoldReinhold, CC BY-SA 3.0, via Wikimedia Commons.

At Boeing, the arm was too slow; at Alto, the disk spun fast, hurling an unbuffered data stream straight at the bus.

The Diablo drive streamed bits continuously, while the Alto controller hardware provided only a single-word buffer (16 bits).

Roughly every 10 microseconds, a 16-bit word landed in the controller buffer. If the system failed to retrieve that word within 10 microseconds, the incoming word overwrote it, corrupting the sector.

On contemporary mainframes, engineers solved such timing challenges with bulky, expensive standalone hardware controllers containing hundreds of chips and dedicated Direct Memory Access (DMA) channels. But the Alto had to fit under an office desk; neither chassis volume nor unit cost could tolerate a massive controller box.

McCreight and Lampson adopted an integrated hardware-software architecture: strip dedicated controller circuits to the bone, shifting control state machines into the central processor via microcode.

Butler Lampson

Butler Lampson (1992 ACM Turing Award Laureate), who co-designed the Xerox Alto disk controller microcode and file system architecture alongside Edward McCreight. Photo by Microsoft PDC, CC BY 2.0, via Wikimedia Commons.

The final Alto disk controller hardware was minimalist. The entire board used approximately 55 Medium-Scale Integration (MSI) TTL chips and four dedicated registers. Most controller state sequencing was delegated to two microcode tasks occupying roughly 150 microinstructions in the processor's control store:

  • Disk Data Task: Assigned the highest fixed microcode priority. During active data streaming, hardware awakened this task roughly once every 10 microseconds. In less than 1.7 microseconds, it transferred one 16-bit word between main memory and the single-word buffer, cleared its request, and yielded the processor back to display, network, or emulation tasks.
  • Disk Sector Task: Assigned lower priority. It ran only when the physical read head crossed a sector gap (approximately every 3 milliseconds), checking drive status, issuing seek commands, and setting parameters for subsequent sector transfers.

Defensive Reliability: Moving Data Fast, Writing only where Permitted

Moving words every 10 microseconds solved only half the battle. On a desktop machine, the designers faced another hazard: how to prevent wild writes from destroying user data.

Cartridge disk drives suffered mechanical positioning drift, and unverified software could issue bad cylinder addresses. Without hardware guardrails, an errant head position would write across unrelated sectors, erasing innocent files.

McCreight and Lampson embedded a defensive label system between the hardware controller and the file system. Every physical sector was divided into three distinct records:

  1. Header: Contained the cylinder address, track address, and sector number.
  2. Label: Contained the unique file ID, page number within the file, and bidirectional pointers linking to the predecessor and successor physical pages.
  3. Data: The payload of 256 sixteen-bit words.

The controller hardware supported independent Read, Write, and Check operations across all three records. Before writing data, software routinely instructed the controller to check the Header and Label first. Only when the hardware verified the physical read head was on the correct cylinder and the sector's file ID and page number matched expectations did microcode proceed to write data. Any mismatch aborted the write immediately.

This sector Label architecture formed the foundation of the Alto file system. If a directory was corrupted, the Scavenger repair utility scanned surviving sector labels across the entire disk pack, following page pointers to reconstruct file chains and restore the directory tree.

Replacing hardware chips with microcode achieved dramatic cost savings, but it carried an explicit performance tradeoff. As documented in Xerox PARC report CSL-79-11, the controller consumed up to approximately 20% of processor time during active disk streaming. Alto traded one-fifth of its central processor capacity to keep the hardware small enough to live under a desk.

Two Divergent Engineering Tradeoffs for the Same Physics

From Seattle to Palo Alto, Edward McCreight’s work captures two fundamentally different ways systems engineers tame rotating magnetic storage.

The two projects shared no direct implementation code; instead, each addressed the physical limits of magnetic media at a different layer of abstraction:

At Boeing's algorithm layer, the bottleneck was fifty milliseconds of mechanical seek latency; the solution was multi-way balanced indexing to minimize physical page reads.

At Xerox PARC's systems layer, the constraints were a 10-microsecond single-word buffer deadline and mechanical head drift; the solution was trading processor time for minimal controller circuits, backstopped by sector label verification to prevent wild writes.

When physical reality imposes limits on computer systems, pragmatic systems engineers refuse to be boxed in by rigid divisions between software algorithms and hardware microcode. Instead, they operate across abstraction boundaries to find the most balanced compromise between performance, silicon budget, and data integrity.

Technical Notes and Primary Sources

  1. Interrupt Mask Mechanisms: According to Section 6 of the Alto Hardware Manual (August 1976 revision by Diana Merry, Ed McCreight, and Bob Sproull), sector pulses awaken microcode tasks directly; notifying host software requires setting the interrupt mask in communication block address KBLK+3. Normal command completion interrupts are masked in DCB+6, while error completion interrupts are masked in DCB+7.
  2. Microtask Switching: According to Xerox report CSL-79-11, a running microtask must explicitly execute a microinstruction containing the TASK flag to initiate a task switch. The hardware priority scheduler selects the highest-priority ready task, with a latency of one microinstruction.
  3. Primary References:
  4. Rudolf Bayer, Edward M. McCreight, Organization and Maintenance of Large Ordered Indices, Acta Informatica 1, 173–189 (1972).
  5. Rudolf Bayer, Memoiren, Technical University of Munich (TUM), 2014.
  6. C. P. Thacker, E. M. McCreight, B. W. Lampson, R. F. Sproull, D. R. Boggs, Alto: A Personal Computer, Xerox PARC Technical Report CSL-79-11 (August 7, 1979).
  7. Diana Merry, Ed McCreight, Bob Sproull, Alto: A Personal Computer System Hardware Manual, Xerox PARC (August 1976 revision).
  8. Butler W. Lampson, Why Alto?, Xerox PARC Internal Memorandum (December 1972).

阅读更多

16 位 Unicode 差点毁掉所有 C 语言代码,Ken Thompson 如何在餐馆纸垫上写出统治互联网的 UTF-8

1980 年代各大厂商为解决 ASCII 限制各自拼凑代码页导致严重的乱码危机,统一码联盟在 1988 年提出定长 16 位的 UCS-2 试图一统天下,却在 1992 年险些因 0x00 空字节炸毁全球 C 语言与 Unix 管道。Ken Thompson 与 Rob Pike 在新泽西餐馆等菜时在纸垫上推导出的 5 组前缀位掩码,不仅零破坏兼容 ASCII,更赋予了字节流 3 字节内必自愈的容错能力。

By huizhou92
一个伪装成“性能测量工具”的五人项目,如何在 IBM 官方系统溃败时造出了现代虚拟机

一个伪装成“性能测量工具”的五人项目,如何在 IBM 官方系统溃败时造出了现代虚拟机

1967 年春,IBM 耗费重兵打造的官方分时系统 TSS/360 每次启动要等 10 分钟,平均不到 10 分钟就崩溃一次。剑桥科学中心 5 名工程师在 256KB 二线机器上借“性能测量工具”之名给每位用户发了一台虚拟裸机,不仅 1 分钟点亮全部终端,还在 6 年后用 5 层嵌套虚拟化救活了 IBM 正统旗舰 MVS。

By huizhou92