Partitioning: ownership, replica placement, and bounded movement

Placement answers where a key belongs. Replication chooses additional owners. Rebalancing changes assignments when load is uneven. These are separate functions with separate invariants: a stable ring does not guarantee balanced traffic, and a balanced byte count does not guarantee failure-domain diversity.

Derive clockwise ownership with boundaries

The ownership exercise receives already-hashed uint32 positions. Ignore inactive tokens, order the active ones by (Position, NodeID), and choose the first position greater than or equal to the key. If no such token exists, choose the first token and set wrapped=true. At an exact token position there is no wrap. Duplicate positions belong to the smallest node ID.

Use unsorted tokens (C,70,active), (B,20,active), (A,20,active), (D,90,inactive), with numeric node IDs A=1, B=2, C=3, D=4.

Key	Chosen node / position	Wrapped?	Reason
20	A / 20	false	Equality belongs to token; A wins tie
21	C / 70	false	First active token at or after key
80	A / 20	true	Inactive D cannot own; walk crosses end
0	A / 20	false	Smallest token is already after key

When node E joins at 50, only the interval (20,50] changes primary owner, from C to E. Keys in (50,70] remain at C. This local movement is why consistent hashing is useful; there is no promise that the moved interval contains exactly an equal fraction of keys or traffic. If all tokens are inactive, return (-1,0,false); do not index an empty ring.

Replica placement is a two-pass policy

The replica exercise adds zones and chooses distinct physical node IDs. Several virtual tokens on the same node still provide one replica. Assume every token for a physical node has the same zone; conflicting node-to-zone metadata is outside this exercise's input contract.

Take the clockwise order from key 15: B@20/east, A@30/east, C@40/west, B@60/east, D@80/west, E@90/north. For rf=4, the first pass selects B (east), skips A, selects C (west), skips B and D, then selects E (north). It has exhausted a full circuit. The second pass restarts at the same key position and selects the first unseen node, A. The result is [B,C,E,A]. It is not [B,A,C,D], which ignores diversity, nor [B,C,E,D], which resumes from the wrong point.

The first pass maximizes represented zones subject to the traversal policy; when zones are insufficient, the second pass still fills replicas from distinct nodes. rf larger than the unique active node count returns every active node once, in this two-pass order. This is zone preference, not a guarantee that an arbitrary multi-zone failure leaves enough replicas for a quorum.

Simulate a move against the global gap

The rebalance exercise minimizes max(loads)-min(loads) for each accepted move. It copies loads, keeps the last input record for each shard ID, and ignores a retained shard with an invalid node index. Deduplication happens before filtering: an invalid final record must not resurrect an older record.

Suppose loads are [14,8,2]. The highest node is 0 and the lowest is 2. Node 0 has movable shard 7 of size 7 and shard 8 of size 5, plus pinned data of size 2. The current gap is 12.

Candidate	Resulting loads	Global gap
Move size 7	[7,8,9]	2
Move size 5	[9,8,7]	2

Both improve equally, so the larger-shard tie break selects shard 7. This is followed by lower shard ID if sizes also tie. For delta=2, stop after this move. A budget of one move also stops after this move even if delta were zero.

Do not measure only the two endpoint loads. With [12,11,0], moving size 6 produces [6,11,6]: the endpoint difference is zero, but the global gap is 5 because node 1 is now the maximum. Cache the extrema of nodes other than hi and lo once per iteration; each candidate then needs only the two changed loads and those cached extrema. This meets O(maxMoves*(nodes+shards)) instead of rescanning all nodes for every candidate.

Why the greedy planner may stop early

For [10,10,0], node 0 wins the maximum-load index tie. Moving its size-10 shard to node 2 produces [0,10,10], the same gap 10, so the move is rejected. Repeating non-improving moves can oscillate. A pinned maximum node can also block progress even if another source could help. The exercise deliberately searches only the selected hi→lo pair; stopping means no improving move under this policy, not that a globally optimal assignment has been proved.

Nonnegative integral loads, positive shard sizes, physically valid ownership, and arithmetic within Go int range are assumed. Real systems additionally need move bandwidth budgets, concurrent ownership/version control, and a cutover protocol. The planner returns a proposed move list; it does not copy shard data.

Check your reconstruction

1. Key 70 equals the final active token. Answer: choose it without wrap.
2. Three replicas occupy two nodes because one node has two tokens. Answer: invalid; count node IDs, not virtual tokens.
3. In [12,11,0], why is the size-6 move's gap 5? Answer: all nodes count; the unchanged 11 remains the maximum.
4. A greedy plan stops at positive gap. Answer: inspect pinned shards, budgets and the restricted source/destination policy before claiming success.

The original Dynamo paper, section 4.2 explains consistent hashing, virtual nodes and distinct-node preference lists. The exercises add explicit duplicate-position, zone and greedy-move policies; these deterministic teaching contracts are not Dynamo's full placement protocol.