Preparing your workspaceloading the brief, studio & editor…

Loadingone moment…

Rebalance a keyspace with consistent hashing · Python scenario · D8LooP

Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.

CODE WORKSPACE

Rebalance a keyspace with consistent hashing

State for the streaming job is sharded across worker nodes by key. The current assignment is hash(key) % len(nodes), so adding a fourth worker moved almost every key and the job spent forty minutes reloading state it already had. The proposal is a hash ring, and the team wants the movement measured before committing to it. Write rebalance(keys, nodes_before, nodes_after, replicas).

Function to write

rebalance(keys: list, nodes_before: list[str], nodes_after: list[str], replicas: int) -> dict

A dict with the keys that changed owner, how many moved and how many keys there were.

How to approach it

Build both rings, then ask each key who owns it before and after.

Sample cases

+ 2 held back until you submit

adding a fourth node

Growing the cluster should move roughly a quarter of the keys, not almost all of them.

Input

Argument 1

[
  'user:1',
  'user:2',
  'user:3',
  'user:4',
  'user:5',
  'user:6',
  'user:7',
  'user:8',
  'user:9',
  'user:10',
  'user:11',
  'user:12',
  'user:13',
  'user:14',
  'user:15'
]

Argument 2

[
  'node-a',
  'node-b',
  'node-c'
]

Argument 3

[
  'node-a',
  'node-b',
  'node-c',
  'node-d'
]

Argument 4

Returns

{
  'moves': [
    {
      'key': 'user:11',
      'from': 'node-c',
      'to': 'node-d'
    },
    {
      'key': 'user:12',
      'from': 'node-c',
      'to': 'node-d'
    },
    {
      'key': 'user:15',
      'from': 'node-b',
      'to': 'node-d'
    },
    {
      'key': 'user:8',
      'from': 'node-c',
      'to': 'node-d'
    }
  ],
  'moved': 4,
  'total': 15
}

losing a node

Only the failed node's keys move, and they spread across the survivors rather than shifting everything.

Input

Argument 1

[
  'user:1',
  'user:2',
  'user:3',
  'user:4',
  'user:5',
  'user:6',
  'user:7',
  'user:8',
  'user:9',
  'user:10',
  'user:11',
  'user:12',
  'user:13',
  'user:14',
  'user:15'
]

Argument 2

[
  'node-a',
  'node-b',
  'node-c'
]

Argument 3

[
  'node-a',
  'node-c'
]

Argument 4

Returns

{
  'moves': [
    {
      'key': 'user:13',
      'from': 'node-b',
      'to': 'node-c'
    },
    {
      'key': 'user:14',
      'from': 'node-b',
      'to': 'node-c'
    },
    {
      'key': 'user:15',
      'from': 'node-b',
      'to': 'node-a'
    },
    {
      'key': 'user:2',
      'from': 'node-b',
      'to': 'node-a'
    }
  ],
  'moved': 4,
  'total': 15
}

no change at all

An identical node list moves nothing, which is the property the whole scheme exists for.

Input

Argument 1

[
  'user:1',
  'user:2',
  'user:3',
  'user:4',
  'user:5',
  'user:6',
  'user:7',
  'user:8',
  'user:9',
  'user:10',
  'user:11',
  'user:12',
  'user:13',
  'user:14',
  'user:15'
]

Argument 2

[
  'node-a',
  'node-b'
]

Argument 3

[
  'node-a',
  'node-b'
]

Argument 4

Returns

{
  'moves': [],
  'moved': 0,
  'total': 15
}

no keys

An empty keyspace has nothing to move, whatever happens to the cluster.

Input

Argument 1

[] (empty list)

Argument 2

[
  'node-a'
]

Argument 3

[
  'node-a',
  'node-b'
]

Argument 4

Returns

{
  'moves': [],
  'moved': 0,
  'total': 0
}

Constraints

1Place each node on a ring at replicas positions, derived from the node name and the replica index.
2A key belongs to the first node position at or clockwise from the key's own position. Past the end of the ring, wrap to the beginning.
3Use a stable hash. Python's built-in hash is randomised per process, so the same key would land on a different node in a different worker.
4Compare ownership before and after, and report only the keys that moved, with the node they left and the one they joined.
5Duplicate keys count once. Compare keys as text.
6An empty node list owns nothing: every key's owner is None.
7A replicas of zero or less describes no ring at all: return no moves.
8Report the moves sorted by key, along with how many moved out of how many.

Worked example

Adding node-d to a three-node cluster should move about a quarter of the keys — the ones that fall in the arcs the new node's positions took over. Every other key keeps its node, so its state stays where it is and the job resumes immediately. Under modulo assignment, user:1 through user:15 are distributed by hash % 3 and then by hash % 4, and the two have almost nothing to do with each other: roughly three quarters of the keys change hands. That is the forty minutes. The ring's guarantee is that adding the Nth node moves about 1/N of the keys and touches nobody else's assignment. The replicas count is what makes the arcs even. With one position per node the ring is lumpy — one node can own half the circle by chance — so real implementations use a hundred or more virtual nodes each, and the load evens out.

What this tests

Why consistent hashing exists at all: not to distribute keys, which modulo does fine, but to make the distribution stable under change. The virtual-node count is the second half of that, and it is the part people leave out.

PYTHONrebalance(keys: list, nodes_before: list[str], nodes_after: list[str], replicas: int) -> dict

AI evaluation

The reviewer reads your query.

Submit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.

Desktop only

This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.

Read the library instead Back to modules