3. Ranges and the key space

Chapter 1 claimed the cluster is one sorted key-value map and SQL is an encoding into it. This chapter takes that apart, because almost every performance problem in CockroachDB becomes obvious once you can see the keys.

One map, ordered

There is exactly one key space in a cluster. Every database, table, index and internal system table lives in it, sorted by byte order.

   THE WHOLE CLUSTER, IN ORDER

   /Meta1/…          the directory of the directory
   /Meta2/…          the directory of every range
   /System/…         node liveness, timeseries, settings
   /Table/50/…       a table
   /Table/51/1/…       its primary index
   /Table/51/2/…       its secondary index
   /Table/52/…       …and so on, to the end

Sorted, not hashed. One choice, two consequences that run through the entire product:

   a range scan is CHEAP         rows that sort together
                                 are stored together
   sequential inserts are HOT    rows that sort together
                                 are stored together

You get both or neither. Cassandra made the opposite choice — hash the partition key, scatter the rows, lose ordered scans.

How a row becomes a key

CREATE TABLE users (
  id     INT PRIMARY KEY,
  email  STRING,
  region STRING,
  INDEX  (email)
);

CockroachDB gives the table an ID (say 53) and its primary index the ID 1. The row id = 4718 is stored under a key built from those parts:

   /Table/53/1/4718/0   →   ("alice@example.com", "eu-west")
     │      │  │    │
     │      │  │    └── column family 0
     │      │  └─────── the primary key value
     │      └────────── index 1 = the primary index
     └───────────────── table 53

The primary index is the table

As in MySQL’s InnoDB, there is no separate heap. The row lives inside its primary index, so the primary key decides the row’s physical position — which range it lands in, and therefore which machine takes the write. It is the most consequential line in your schema.

A secondary index is just more keys

   /Table/53/2/"alice@example.com"/4718/0   →   (empty)
     │      │           │           │
     │      │           │           └── the primary key,
     │      │           │               so the row can be
     │      │           │               fetched afterwards
     │      └───────────┴── index 2 = the email index
     └─── same table

So WHERE email = 'alice@…' is two lookups in two distant parts of the key space, which may be on two different machines:

   1. read /Table/53/2/"alice@…"/…   → range 44,  lease n1
   2. read /Table/53/1/4718/0        → range 137, lease n8

That second step is an index join, and chapter 9 shows how to see it in a plan and when to remove it with a covering index (STORING).

Ranges

The key space is cut into contiguous chunks — ranges — each covering [start_key, end_key), with a default target size of 512 MiB.

   TABLE 53 GROWS, AND SPLITS

   at 400 MiB                  one range
   ┌──────────────────────────────────────────┐
   │ /Table/53/1/1 ………………………… /Table/53/1/9m │  r137
   └──────────────────────────────────────────┘

   past 512 MiB                split near the midpoint
   ┌────────────────────┐ ┌────────────────────┐
   │ …/1 … …/4.5m       │ │ …/4.5m … …/9m      │
   │       r137         │ │       r212         │ ← new group,
   └────────────────────┘ └────────────────────┘   new leases,
                                                   placed by the
                                                   allocator

Splits are automatic, cheap and constant. The new range gets its own Raft group, its own replicas and its own leaseholder, usually somewhere other than the old one — which is how a growing table spreads itself across a cluster with nobody resharding anything. Merges run the other way, so a table you mostly deleted does not leave thousands of near-empty ranges behind.

Three things cause a split:

   SIZE      the range passed its target. the common case.

   LOAD      the range is hot and the traffic can be
             divided. CockroachDB samples request keys,
             finds a split point that halves the load,
             and splits a range nowhere near 512 MiB.

   BOUNDARY  every table and index always starts a new
             range. a 2 KB lookup table gets one to itself.

You can also place split points yourself when you know the load pattern in advance:

ALTER TABLE users SPLIT AT VALUES (1000000), (2000000);
ALTER TABLE users UNSPLIT ALL;

Finding a range

Ranges move constantly, so no node holds a static map. The directory lives in the key space itself, in the meta ranges at the start:

   /Meta2/Table/53/1/9000000   → r137, replicas n2 n5 n8, lease n8
   /Meta2/Table/53/1/18000000  → r212, replicas n1 n4 n7, lease n4

To locate /Table/53/1/4718, a node looks up the first meta key greater than or equal to it — one ordered lookup, which is exactly what this store is good at. Every node caches the answer, and stale caches are the design rather than a fault:

   n3 ──► n8   "read /Table/53/1/4718"
       ◄──     NotLeaseHolderError: lease is on n5
   n3 ──► n5   "read /Table/53/1/4718"
       ◄──     rows

Occasional NotLeaseHolderError is bookkeeping. Constant NotLeaseHolderError means leases are thrashing — chapter 14.

Hotspots, which are the whole reason for this chapter

Put three facts together:

   1. keys are stored in SORTED order
   2. a range is a CONTIGUOUS slice of that order
   3. one range has ONE leaseholder, on ONE machine

Therefore sequential inserts all land in the last range, whose leaseholder is one node. Add fifty machines and forty-nine of them idle through that workload.

   SEQUENTIAL PRIMARY KEY (SERIAL, timestamp, snowflake)

   /Table/53/1/1 … 4.5m    4.5m … 9m       9m … ∞
   ┌──────────────┐ ┌──────────────┐ ┌──────────────┐
   │     cold     │ │     cold     │ │  ALL WRITES  │ ◄── n8
   └──────────────┘ └──────────────┘ └──────────────┘
                                       load-based splits
                                       help a little, and
                                       then the new last
                                       range is hot too

Danger

This is the number one way a PostgreSQL migration disappoints. BIGSERIAL is not merely acceptable in PostgreSQL, it is preferred — it keeps the B-tree dense and the WAL sequential. Move the same schema here unchanged and you have pinned your write throughput to one node, on a cluster you bought for write throughput.

Fix 1: random UUIDs

CREATE TABLE users (
  id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  …
);

Inserts scatter evenly over every range. This is the default advice and usually the right answer. The cost is 16 bytes per key, repeated in every secondary index, and no useful ordering.

Fix 2: unique_rowid()

The built-in default behind SERIAL. It packs a timestamp with the node ID in the low bits, so values are unique and roughly ordered but originate on different nodes — spreading writes without full randomness. Good when you want small integer keys.

Fix 3: hash-sharded indexes

When the key genuinely must be ordered or time-based, CockroachDB prepends a computed shard column so one logical sequence becomes N physical ones:

CREATE TABLE events (
  id INT PRIMARY KEY USING HASH WITH (bucket_count = 8),
  ts TIMESTAMPTZ NOT NULL
);

-- works for secondary indexes on timestamps too
CREATE INDEX ON events (ts) USING HASH WITH (bucket_count = 8);

   WITHOUT HASH                WITH 8 BUCKETS

   … ──► [ hot range ]         shard 0 ──► [ range ] n1
                               shard 1 ──► [ range ] n4
                               shard 2 ──► [ range ] n7
                               …           …
                               one table, eight write points

The cost is paid on reads: a scan over a time window must now touch all eight buckets and merge, so pick the bucket count deliberately — commonly the number of nodes, not more.

Seeing it on a live cluster

-- every range behind a table: size, leaseholder, replicas
SHOW RANGES FROM TABLE users WITH DETAILS;

-- which range holds one specific row
SHOW RANGE FROM TABLE users FOR ROW (4718);

-- the ranges taking the most traffic right now
SELECT * FROM crdb_internal.cluster_replicas LIMIT 10;

# the same picture, per node, from outside SQL
cockroach node status --ranges --certs-dir=certs

A cluster where one node sits at 90% CPU while the others idle at 15% is nearly always this chapter’s problem rather than a tuning problem. Chapter 13 works the diagnosis; chapter 14 lists the shapes it takes.

What to take from this chapter

• There is one sorted key space for the entire cluster. Tables, indexes and system data are all encodings into it.
• A row key is /Table/<table>/<index>/<pk>/<family>. The primary index is the table — no heap, as in InnoDB.
• Secondary index entries are separate keys holding the primary key, so a non-covering lookup is an index join: a second read, possibly on another node.
• Ranges are contiguous slices of about 512 MiB, split by size, by load, and always at table and index boundaries; small adjacent ranges merge back.
• The directory lives in meta ranges inside the key space, located by an ordered lookup. Stale caches and occasional NotLeaseHolderError are normal.
• Sorted storage makes scans cheap and sequential inserts hot. One range means one leaseholder means one machine.
• Spread writes with gen_random_uuid(), unique_rowid(), or hash-sharded indexes — and expect the PostgreSQL instinct for a monotonic BIGSERIAL key to be exactly wrong here.
• SHOW RANGES, SHOW RANGE … FOR ROW and the hot-ranges view turn all of this into something you can watch during an incident.

Next: replication — one Raft group per range, why the leaseholder is deliberately separate from the Raft leader, and how the allocator decides where copies of your data belong.