Between the nine fortified passes of the Longyou frontier lay the grandest granary complex of the Great Li Dynasty. Three thousand stone caves had been chiseled into three soaring mountain ranges, stretching for hundreds of leagues from north to south. Within each range wound dozens of rugged valleys, and upon the cliff faces stood caverns of vastly different capacities: some were as cavernous as military parade grounds, capable of sheltering ten thousand bushels of barley; others were modest clefts carved into the rock, holding merely a hundred sacks of millet.

In the early days of the empire, a towering fortress known as the “Grand Registry Bureau” stood sentinel at the gateway pass.

Within the bureau, sunlight never penetrated. Hundreds of grain scribes hunched over cedar tables, surrounded by tens of thousands of vellum ledgers treated with herb-infused insect repellent. Whenever a grain caravan arrived from the central plains, pack horses and ox carts backed up for leagues outside the fortress gates. The transport officer had to present wooden tokens bearing imperial stamps and wait in endless lines while scribes scoured their voluminous records.

A scribe would leaf through yellowed pages, seeking among thousands of caves: which cavern had vacant space? Which dark recess suited dry grain? Once decided, the scribe dipped his brush in cinnabar, marked both the master ledger and branch volumes, and handed the officer a wooden guide-token inscribed with “North Range, Pine Valley, Cavern No. 4.” Only then could the caravan snap its whips and journey across peaks and ravines to unload its cargo.

When armies on the march needed provisions, requisitions likewise had to pass through the Grand Registry to uncover where grain had been sealed years prior, cancel the records, and grant tokens to unseal the caves.

As the decades slipped by and border garrisons expanded, the stockpiled grain exploded from tens of thousands of bushels to tens of millions of sacks.

The long tables of the Grand Registry groaned under the weight of rotting parchment. Locating a single sack of grain often demanded sifting through dozens of tattered scrolls amidst endless coughing and sighs. Scribes labored from dawn to midnight, yet caravans outside the mountain pass still queued far beyond the horizon. In summer heat, grain sacks spoiled under the relentless sun; in winter blizzards, pack animals froze in their tracks.

Worse still were fire and ink-borne errors.

One night, lightning struck the bureau’s eastern wing, reducing thousands of ledgers to ash. Tens of thousands of garrison troops stood before the mountains, looking out across three thousand caves, yet no living soul knew which cavern held what provisions—they were starving atop a mountain of buried gold. On other occasions, exhausted scribes blundered, assigning all three redundant backup sacks of a vital shipment to the very same damp, low-lying limestone cavern. When spring floods triggered a mudslide, the entire shipment was wiped out in a single stroke, leaving no reserve alive.

As border logistics teetered on the brink of collapse, Master Pei, an astronomer and master horologist living in reclusion on Mount Zhongnan, answered an imperial summons.

Master Pei entered the chaotic halls of the Grand Registry. He neither drafted new scribes nor ground fresh ink. Surveying the mountains of parchment, he swept his sleeves and chuckled: “The grain of the realm is as vast as the stars. To chase an infinite harvest with finite ink and paper—how could it not exhaust you? Why ask mortal scribes where grain resides? The order of three thousand peaks is already written into the architecture of heaven and earth.”

With that, Master Pei ordered every ledger closed and sealed into deep vaults, discarded forever.

From his wooden trunk, he produced a bronze armillary astrolabe. Its concentric rings were finely engraved with interlocking teeth and hair-thin scales.

Gathering the grain wardens and caravan masters, Master Pei unveiled three cardinal laws:

First, The Chart of Peaks and Valleys (Hierarchical Topology). He mapped the three thousand caverns into a golden tree diagram: at the summit stood the three great mountain ranges—Qinling, Qilian, and Helan; beneath them branched the deep valleys; below the valleys sat the fortress camps; and at the foundation lay the individual caverns. Each cave possessed a measured weight: a grand hall holding ten thousand bushels received a heavy oak block, while a narrow crevice received a feather-light bronze slip. Every warden received a replica of this chart.

Second, The Mandate of Separation (Failure Domain Isolation). Every grain deposit required three replicas against disaster. But these three copies were never placed at whim; the astrolabe held an unbending decree: “Of three sibling sacks, the first shall enter the Eastern Range, the second shall cross to the Western Peaks, and the third shall rest in the Central Valley. Never shall two share the same gorge, and never shall two drink from the same stream.”

Third, The Nine-Palace Computation (Computing in Place of Lookups). No scribes. No ledgers. No central queries.

When grain was bagged, an indelible seal was branded upon the hemp cloth—a unique weave number and imperial serial. When a caravan reached the mountain pass, the driver consulted no official. He drew his personal bronze astrolabe, dialed the sack’s serial number into the central spindle, and turned the bronze crank three full revolutions.

Cogs meshed; brass gears hummed. The astrolabe’s internal clockwork executed a deterministic pseudo-random progression, walking down the hierarchy of peaks and caverns according to the sack’s number and the proportional weights of the caves:

The needle clicked and settled upon the outer ring: “Southern Qilian Range”; The second ring aligned to “Snow Maple Valley”; Sweeping past minor crags, drawn by the gravitational pull of the largest cavern’s weight, it snapped firmly into “Cavern No. 7, The Black Tortoise.”

To place the second replica, the driver simply notched the auxiliary lever dictated by the Mandate of Separation. The gears instantly steered clear of the southern mountains, pointing deterministically to a secluded cave in the northern Helan Range.

The entire derivation took no more than three breaths. The driver packed his astrolabe, leaped onto his horse, and rode directly to the designated cave to deliver his grain.

When military commanders needed to retrieve provisions, their quartermasters dialed the exact same serial number into their own astrolabes. The needle halted unerringly at the exact same stone chamber where the grain had been stowed seasons before.

Across thousands of peaks, queues vanished from the gates. Worn ledgers were forgotten.

Years later, an earthquake collapsed an ancient cavern deep within the Qilian Mountains. The garrison general panicked, fearing that tens of millions of records would need to be recalculated across the empire.

Master Pei remained serene. He dispatched a wafer-thin brass shim to the border posts, slipping it into the astrolabes to flatten the collapsed cave’s weight to zero.

A marvel occurred: under the updated gear ratio, tens of millions of sacks resting peacefully in the other thousands of caves remained completely untouched. Only the tiny fraction of grain originally calculated for the collapsed cavern was gently redistributed among neighboring caves in the same valley with capacity to spare.

Without a single page of text, myriad bushels lay in perfect harmony; without a single scribe, the frontier stood secure. The Nine-Palace Astrolabe hung above the gates, and a thousand peaks became a self-navigating chessboard.

——By now you have probably recognized it: this is the foundation of modern distributed storage—Ceph’s core data distribution algorithm, CRUSH (Controlled Replication Under Scalable Hashing).

What it is

In massive distributed storage systems spanning petabytes or exabytes across tens of thousands of hard drives, deciding where an object should live is the core architectural challenge.

Traditional distributed storage relied on centralized metadata tables (such as a Metadata Server or lookup directory): every time a file was written, a central catalog recorded an explicit mapping of ObjectID → NodeIP/DiskID. But as the number of objects surged into billions and trillions, central metadata servers inevitably hit hard limits: memory exhaustion, disk I/O bottlenecks, network saturation, and catastrophic single-point failures.

In 2006, Sage Weil introduced the CRUSH algorithm in his seminal doctoral thesis, forever ending the era of table lookups:

1. Computation over Lookup ($O(1)$ Addressing): When reading or writing data, clients never query a central authority for placement coordinates. Instead, they execute the CRUSH algorithm locally. The algorithm requires only three inputs: the Object Identifier ($x$), the Hierarchical Cluster Map ($M$), and the Placement Rule ($R$). Using deterministic pseudo-random hash functions, the client calculates the exact list of target storage daemons ($\vec{OSD} = (osd_1, osd_2, \dots, osd_n)$) in nanoseconds, enabling entirely decentralized, massively parallel data access.
2. Failure-Domain-Aware Hierarchical Topology: CRUSH models the physical layout of a data center as a tree (Root → Datacenter → Rack → Row → Host → OSD). Administrators configure placement rules (for instance: place three replicas across three separate racks, or across different power distribution zones). As CRUSH traverses the tree top-down, it strictly enforces these fault-isolation constraints, ensuring that a severed network cable, power supply blowout, or rack failure cannot take down all replicas simultaneously.
3. Capacity-Weighted Bucket Algorithms: Internal nodes within the CRUSH hierarchy are known as “buckets.” To accommodate heterogeneous hardware (mixing high-capacity spinning disks with ultra-fast NVMe SSDs) and different rates of hardware churn, CRUSH provides several bucket types with distinct computational complexities and rebalancing characteristics:
   • Uniform: All child nodes have identical weights. Selection is $O(1)$, but adding or removing devices of varying capacities is impossible.
   • List: Children are linked sequentially. Adding a new device appends it to the head, guaranteeing zero data movement among existing devices, but traversal cost scales as $O(n)$.
   • Tree: Children are organized into a binary tree with $O(\log n)$ traversal time, well-suited for very large, stable clusters.
   • Straw / Straw2: The modern default in Ceph. All children compete dynamically based on their individual weights, like drawing straws from a canister. When an OSD fails or a new disk is introduced, data migration occurs strictly between the altered device and its immediate peers; data across unaffected disks remains completely undisturbed.

Why it matters

CRUSH was a paradigm shift in distributed storage, transforming systems from centrally coordinated clusters into self-organizing fleets:

• Shattering the Scale Ceiling: By removing centralized lookup tables, Ceph scales horizontally to thousands of storage nodes (OSDs) and trillions of objects. Throughput scales linearly with the addition of storage drives and client nodes.
• Resilient Fault Isolation: By embedding physical failure boundaries (power feeds, racks, failure domains, availability zones) directly into algorithmic rules, the system mathematically guarantees that data survives even when entire server racks go dark.
• Smooth Expansion with Minimal Data Movement: Under classic modulo hashing ($hash(key) \pmod N$), adding or removing a node rehashes nearly $100\%$ of all keys across the cluster, triggering disastrous network floods and storage paralysis. CRUSH (especially Straw2) ensures that adding an $n$-th drive migrates only a minimal $1/n$ fraction of data, allowing live production clusters to expand seamlessly under heavy workloads.
• Architectural Pitfalls to Avoid:
  • PG (Placement Group) Sizing: Objects map first to logical Placement Groups (PGs), which CRUSH then maps to OSDs. If the PG count is too low, data distribution skews severely, leaving some disks overflowing while others sit idle. If the PG count is too high, OSD daemons suffer excessive memory and CPU overhead.
  • CRUSH Map Transition Shock: While Straw2 minimizes rebalancing, sweeping alterations to CRUSH rules (such as migrating from host-level to rack-level replication) will trigger immense data shuffling (peering and backfilling). Production operators must strictly throttle recovery bandwidth using parameters like ceph osd set-max-backfills to prevent user latency spikes.

Metaphor mapping

• Three thousand caverns across the Longyou mountains → Storage daemons and physical disks in a cluster (OSDs)
• The overcrowded, bottlenecked Grand Registry Bureau → Traditional centralized metadata servers and lookup tables (Metadata Server / Central Catalog)
• Master Pei’s Nine-Palace Armillary Astrolabe → The locally computed CRUSH algorithm engine (CRUSH Algorithm)
• The Chart of Peaks and Valleys on golden foil → The hierarchical cluster map (Hierarchical Cluster Map)
• The Mandate of Separation across ranges and rivers → Failure domain placement rules (Placement Rules & Failure Domain Isolation)
• Dialing the unique weave serial number into the central gear → Hashing the Object ID ($x$) to determine placement
• Calibrating cave weights with oak and bronze blocks → Capacity-weighted bucket types (Straw2 Bucket Weights)
• Bypassing the bureau to deliver grain directly to the indicated cave → Completely decentralized, client-side $O(1)$ routing (Algorithmic Self-Routing)
• Inserting a brass shim to nullify a collapsed cave while other grain rests untouched → Minimal data movement during node failure or expansion (Minimal Data Movement & Rebalancing)