Partitioning and routing — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 5: Correctness across machines

Prerequisites: Lesson 28 and the preceding foundations.

Learning outcomes

• Choose partition keys and routing metadata from access patterns, tenant boundaries, and skew.
• Trace ownership transfer during splitting or rebalancing without admitting two authoritative owners.
• Explain why a hot logical key survives naive resharding.

Adding nodes does not split one hot invariant

A service distributes a hundred thousand writes per second across one hundred shards. The average is one thousand writes per shard per second. However, one tenant receives 40% of traffic, so its shard receives forty thousand writes per second before any unrelated data sharing that shard is counted. The cluster’s average utilization conceals the bottleneck.

Partitioning divides data and responsibility. Routing finds the current owner. Placement assigns ownership to machines and failure domains. Rebalancing changes those assignments. These mechanisms make independent work scalable only when their boundaries fit the workload.

Hash and range partitioning

Hash partitioning maps keys through a hash into ownership buckets. It tends to spread distinct keys and can reduce ordered-edge hotspots. It makes arbitrary key-range queries touch several partitions unless another structure or partition dimension helps.

Range partitioning assigns ordered intervals. It can preserve locality for scans and let the engine split a large interval. Sequential new keys can concentrate writes at the active edge. A range split divides a key interval; it does not necessarily divide traffic if every request still targets one key.

The partition key is therefore a workload decision. A tenant identifier can keep tenant-local transactions together while making a large tenant hard to split. A time prefix can help retention while concentrating current writes. A compound key can introduce a bucket dimension while changing query fan-out and transaction locality.

Logical partitions and physical placement

A logical shard need not map permanently to one machine. Virtual partitions create smaller movable units. Several can share a host, and one replicated partition can span several hosts. Keeping logical identity separate from physical address allows movement without changing every application key.

Metadata maps a key or partition identifier to current owners and routing generations. The metadata itself needs availability and consistency appropriate to its authority. Cached routes improve performance but become stale. A request reaching an old owner should be redirected or rejected safely rather than accepted under obsolete ownership.

A generation or epoch can fence stale routes. The exact protocol must cover in-flight requests during movement. An old owner that has handed off authority cannot continue acknowledging writes simply because a client still has its address.

A safe move has an ownership boundary

Moving a partition involves copying state, catching up changes, and transferring authority. The destination must know the state boundary it received and the subsequent mutations required. The source must stop or redirect authoritative work at a coordinated point.

copy snapshot at position S
    -> stream changes after S
    -> destination catches up
    -> establish new ownership generation
    -> route new work to destination
    -> retire old state after safety conditions

The schematic lists responsibilities, not a complete universal algorithm. A replicated engine can implement the transition through its consensus configuration or lease mechanisms. A simpler service may pause writes briefly. The important property is that every accepted operation belongs to one valid ownership history.

A failed move should leave a recoverable owner or a controlled unavailability state, not two independent owners. Retiring the source too early can lose required history. Retaining it indefinitely wastes space and can confuse diagnostics. Cleanup is a separate stage after authority is safely established.

Splitting ranges and preserving transactions

A range split creates two ownership intervals from one. Metadata and data structures must agree on the split key. Requests using old routing information need a safe response. Transactions spanning the new boundary may require distributed coordination that was unnecessary before the split.

This can change performance without changing the application query. A previously local transfer can become cross-partition after rebalancing or growth. A placement-aware engine may keep related ranges nearby, but the architecture should not assume stable locality unless it guarantees it.

Secondary indexes complicate partitioning. A global index may distribute differently from the base table. Maintaining it can create cross-partition writes or asynchronous freshness. A local index keeps maintenance near the data but requires fan-out for queries missing the partition key. The index’s scope is part of the transaction and query contract.

Hot keys and hot ranges

A hot range containing many independent keys can be split to create more parallel ownership. A hot key with one exclusive state transition cannot be divided transparently while preserving the same simple invariant. It can be processed faster, batched, queued, or redesigned using independent rights where the business permits.

For a stock counter, preallocating regional quotas can make purchases local. The system must then handle quota exhaustion, transfer, and stranded stock. A region can sell out its quota while inventory remains elsewhere. That is a tradeoff in the business interface, not merely an internal shard setting.

Read hotspots offer different options. Immutable or versioned data can be cached and replicated widely. A global read-mostly catalog and a global strictly current ownership counter therefore have different scaling opportunities even if both use one logical key.

Rebalancing consumes capacity

Moving data uses source reads, destination writes, network bandwidth, log retention, and metadata work. If rebalancing starts only after every node is saturated, the cluster may lack resources to improve the situation. Capacity headroom must include growth and failure recovery.

A rebalancer needs hysteresis and rate limits so it does not chase transient load or oscillate ownership. Data size, traffic, compaction debt, and tenant fairness can suggest different moves. Moving the largest byte range may not move the hottest CPU workload.

Autoscaling also has delay. A new node needs provisioning, membership, data transfer, cache warm-up, and possibly replica catch-up before it provides useful capacity. An instantaneous graph of node count overstates the speed of the actual resource change.

Case connection

CockroachDB’s distribution-layer documentation describes range-based responsibilities and routing within its architecture. Cassandra’s query-driven data modeling describes a different partition-oriented application interface. These implementations illustrate how partition choices shape both engine machinery and the queries applications should issue.

The general analysis is that partitioning benefits operations aligned with its boundaries. An application that repeatedly ignores those boundaries can create distributed joins, fan-out, and coordination. A good engine may handle those operations correctly while charging the real cost that the workload imposes.

Choose keys from transactions and queries together

A multitenant service might use (tenant_id, object_id) as its logical key. Range partitioning over that composite key groups a tenant’s objects, making tenant-scoped scans and transactions natural. A very large tenant can dominate one range or several adjacent ranges. Hashing the entire composite key spreads writes more widely but scatters tenant scans across owners.

Adding a bucket field can split a large tenant: (tenant_id, bucket, object_id). The application or engine now needs a way to choose buckets for writes and find them for reads. A query for all tenant objects may fan out to every bucket and merge results. A transaction over two objects may become distributed. The extra parallelism has moved cost into routing, queries, and coordination.

An ordered time key presents another tradeoff. Keys beginning with a timestamp support time-range scans and retention, but current inserts can concentrate at the newest edge. Prefixing with a hash bucket spreads the active edge across several owners at the price of scanning several streams for a time range. The ideal bucket count depends on write rate, per-owner capacity, and acceptable query fan-out.

A unique item identifier can remain globally meaningful while physical ownership changes. Stable logical identity should not embed a machine address unless the system explicitly accepts the resulting mobility constraints. Clients can keep object IDs while routing metadata maps them to changing owners. This separation is central to resharding without rewriting every reference.

Routing caches need a safe miss and stale-route path

A client computes a partition or looks up a range descriptor, caches the route, and sends a request with a descriptor generation. The old owner may know the new route and return a redirect. If it cannot prove ownership, it must not accept a write merely because the key used to belong to it.

route_operation(key, operation_id):
    descriptor = cached_or_authoritative_lookup(key)
    response = send(descriptor.owner, descriptor.epoch, operation_id)
    if response indicates stale_route:
        invalidate_only_obsolete_descriptor()
        refresh_with_bounded_retries()
    preserve operation_id across every retry

The retry retains identity because the first request may have committed before the route changed or its reply disappeared. A fresh route does not establish that the old attempt failed. The server’s deduplication or transaction-status protocol must survive the ownership move if the operation contract requires it.

Metadata has its own bootstrapping problem: clients need an initial location for authoritative descriptors. A small well-known group, hierarchical lookup, or service discovery can provide entry. The metadata path must not become a remote lookup for every ordinary operation if cached routing is intended to be fast. Cache invalidation and safe redirects let the common path avoid that cost without trusting stale ownership.

A redirect loop can occur during rapid movement or inconsistent caches. Bound retries by a deadline and refresh from an authoritative source when needed. Error messages should distinguish stale routing, lost authority, unavailable owner, and ambiguous transaction outcome. Treating every case as an ordinary network retry can multiply work and duplicate effects.

A partition move has three distinct planes

The data plane copies a state image and subsequent mutations. The authority plane decides which owner may accept new operations. The routing plane informs request senders. These planes do not update at exactly the same instant, so the protocol must tolerate their temporary disagreement.

source state at S --------snapshot--------> destination
source mutations S+1..H --catch-up--------> destination
                  authority handoff at H, new epoch
old clients -> source -> redirect or forward -> destination

The captioned boundary H represents the agreed handoff point in this conceptual protocol. The destination must have all required accepted changes through H before acting as owner. The source must be fenced from independent acceptance after the handoff. Routing can catch up later because obsolete routes are handled safely.

Forwarding can smooth the transition but needs bounded chains and retained operation identity. If A forwards to B and B has already moved to C, unbounded forwarding can create latency and failure amplification. A redirect lets the client learn the current owner but adds another exchange. Either approach requires a clear authority check at the final receiver.

Failure cases include the source crashing during copy, the destination failing after catch-up, and the metadata decision completing while one side has not heard it. A safe protocol leaves one valid authority or a controlled unavailable state. Cleanup of the old copy happens only after no supported retry, recovery, or rollback path needs it. Physical deletion is later than authority transfer.

Splits and merges change transaction locality

A range containing accounts 1 through 1,000 splits at 500. A transfer between 100 and 900 now spans owners even if it used to be local. If the database promises transparent transactions, its transaction layer must preserve correctness and handle the additional cost. Applications cannot assume a key pair stays colocated forever unless placement is part of the supported contract.

A merge reverses some fragmentation but can require coordinating active transactions and metadata. Excessively small ranges improve fine-grained placement while increasing metadata, consensus-group, scheduling, and compaction overhead. Large ranges reduce bookkeeping but can be slow to move and may combine unrelated hot and cold data.

Splitting by bytes is not the same as splitting by load. A small key range can hold a very hot counter, while a large archival range receives almost no traffic. A rebalancer benefits from separate metrics for bytes, read CPU, write CPU, log generation, and network fan-out. One scalar load score can hide the actual constrained resource.

A single hot key cannot be split by choosing a different boundary around it. Replicating reads can help a read-mostly value, but incompatible writes still require one accepted ordering under a strict invariant. Batching or redesigning the business operation may help, while arbitrary sharding of the same counter changes semantics unless a rights or aggregation protocol restores the invariant.

Secondary indexes create another placement decision

Suppose base rows are partitioned by tenant, while a global lookup searches by email. A tenant-local index supports queries with tenant identity cheaply. A globally partitioned email index can find a user without scanning tenants, but updating it may cross the base row’s ownership boundary.

A synchronous global index can require distributed transaction work to keep row and index changes atomic. An asynchronous index reduces foreground coordination while exposing a freshness interval and requiring reconciliation. A query using the asynchronous path must tolerate recently inserted or removed rows being missing or stale, or perform a final authoritative check.

Uniqueness raises the stakes. Two tenants cannot independently claim one globally unique email unless a global constraint path resolves the conflict. Prefixing uniqueness with tenant changes the invariant to tenant-local uniqueness, which may be entirely appropriate but is a product decision. A physical placement optimization must not silently alter the uniqueness domain.

Index rebuilds and repartitioning consume capacity too. Creating a new global access path can require reading every base row and catching up concurrent changes. That is a migration protocol, not just a metadata declaration. The online-evolution lessons later reuse snapshot-plus-suffix reasoning for this purpose.

Capacity planning must include movement surplus

Assume a 500 GB partition must move over a path providing an effective 250 MB/s of copy bandwidth using decimal units. The base copy alone takes 2,000 seconds, or about 33.3 minutes. If the source generates 20 MB/s of relevant changes during that interval, roughly 40 GB of additional changes accumulate before accounting for overlap.

If catch-up can process 100 MB/s while new changes continue at 20 MB/s, the net drain rate is 80 MB/s. Draining a 40 GB backlog takes another five hundred seconds in the simplified model. If apply capacity falls below the incoming rate, catch-up never reaches the handoff boundary. Provisioning a destination without sufficient surplus capacity does not solve the move.

Compression can reduce transferred bytes but consumes CPU. Source snapshot creation can retain versions or pin files. Destination ingest can trigger compaction and cache churn. A movement budget therefore needs a resource vector rather than a network-rate limit alone. Failure recovery competes for many of the same resources.

Autoscaling should begin before every node is saturated. Adding a machine produces capacity only after provisioning, bootstrap, placement, and warm-up. A sudden flash sale over one hot key may be unaffected by adding ten machines. A balanced tenant population with movable owners is a much better candidate for horizontal elasticity.

Rebalancing needs stability as well as responsiveness

If a controller moves a partition whenever load briefly exceeds a threshold, a burst can cause it to chase traffic back and forth. Movement adds load and can change the measured distribution, creating oscillation. Hysteresis, minimum residence times, confidence windows, and limited concurrent moves reduce this instability.

A controller should distinguish persistent growth from transient spikes. Moving a tenant whose daily peak lasts thirty seconds may cost more than it saves, while pre-positioning capacity before a known event can help. Predictability and workload isolation can be more valuable than aggressive reactive movement.

Failure-domain placement adds constraints. A balanced CPU layout is invalid if all replicas of one partition end up in one zone despite a zone-failure promise. A legal placement satisfies safety and durability rules first, then optimizes load. Temporary transition states need the same scrutiny as final layouts.

CockroachDB’s distribution architecture and Cassandra’s partition-oriented modeling illustrate different ways to expose these responsibilities. The mechanism-level takeaway is that independence must exist in both the workload and the ownership map. Shards are useful units of authority and movement; their count alone does not establish scalable useful work.

Read a key-to-owner map during migration

The map separates stable key intervals from physical machine addresses and authority generations. A request for key 700 carrying epoch 7 reaches A after cutover. A must redirect, forward through a safe identity-preserving path, or reject as stale. It cannot continue independently accepting updates to that interval. A request for 300 can still be valid at A under the updated descriptor.

The unrelated C interval does not need a new owner merely because one range split elsewhere. Hierarchical or partitioned metadata can localize changes and avoid invalidating every route. Its consistency mechanism still has to ensure that a given key has one valid ownership history. Local metadata efficiency does not weaken that rule.

A transaction already touching 300 and 700 spans the split boundary. The engine can finish it under an established old ownership epoch, coordinate through a transition protocol, or retry it with identity and isolation preserved. It cannot let one half commit under an old owner while the other half silently disappears during copy. Active transactions are part of the handoff state.

Separate address changes from data changes

An owner process can move to another address without repartitioning keys, and a range can split while remaining on the same machine initially. Treating these as one operation makes routing and capacity planning unnecessarily confusing. Logical ownership, replica placement, network endpoint, and storage location are related mappings with different update frequencies.

A stable partition identifier allows clients and telemetry to follow a workload as it moves. If every graph is keyed only by machine, a hot tenant can appear to vanish from one host and emerge as an unrelated problem on another. Tracking logical identity and epoch connects performance, failures, and migration events.

The same separation helps incident response. A stale route error means the sender lacks current metadata. An owner-unavailable error means the current authority cannot serve. A transaction-uncertain error means an operation may already have committed. A generic reconnect loop treats all three alike and can hide the real recovery action.

When ownership redesign is a product change

Splitting one global stock counter into regional quotas makes independent selling possible, but it can strand available inventory in the wrong region. A customer may receive “sold out here” while another region has rights remaining. Transferring rights requires coordination and may be unavailable during the very partition the scheme was meant to tolerate.

For a game world, restricting cross-region trade can make region ownership scalable. Allowing arbitrary instantaneous trade across all regions reintroduces a global coordination workload. The architecture and UX must agree: a design cannot advertise unrestricted interactions while relying on their absence for its performance argument.

These examples show the boundary between transparent optimization and changing semantics. Faster routing, better placement, and shorter transitions can preserve the existing contract. Quotas, delayed settlement, or restricted interactions can also be useful, but they create a different contract. A deep architecture explanation should make that change visible instead of presenting it as a free shard-count increase.

Design conclusion

A partition design states the key mapping, metadata authority, routing cache behavior, movement protocol, hotspot strategy, and impact on transactions and indexes. Its scalability claim should identify which work becomes independent and which remains shared.

Lesson 30 addresses the operations that cross those ownership boundaries and still require one atomic outcome. Partitioning creates parallelism; distributed transaction protocols make selected cross-partition work correct.

Sources and further reading

• CockroachDB distribution layer
• Cassandra 5.0 data modeling

Course index · Lesson plan