Partition keys with a consistent hash ring

Hard~30 min

Build a consistent hash ring:

h(s) = int(hashlib.md5(s.encode()).hexdigest()[:8], 16).
Each node has vnodes points at h(f"{node}#{i}") for i in 0..vnodes-1.
A key belongs to the node owning the first point ≥ h(key), wrapping to the smallest point. (Point collisions are broken by node name.)

Assign every key, then remove the node remove and assign again. Return {"assignment": {key: node}, "counts": {node: n}, "moved": n} where assignment/counts describe the ring before removal, and moved is how many keys changed node.

Function

Implement hash_ring. Input: nodes: list[str], vnodes: int, keys: list[str], remove: str. Returns: dict.

Examples

>>> hash_ring(['a', 'b', 'c'], 50, ['user:1', 'user:2', 'user:3', 'user:4', 'user:5', 'user:6'], 'b')

{'moved': 2, 'counts': {'a': 3, 'b': 2, 'c': 1}, 'assignment': {'user:1': 'a', 'user:2': 'b', 'user:3': 'b', 'user:4': 'a', 'user:5': 'a', 'user:6': 'c'}}

Details

Level: Concurrency, resilience patterns, performance constraints and production-style automation.
Roles: Platform Engineer, Backend Engineer, Solutions Architect
Topics: Hashing, Binary search
Tests: 1 public (run with Run), 2 hidden (graded on Submit)
Grading: Exact match of the return value

Build a consistent hash ring:

h(s) = int(hashlib.md5(s.encode()).hexdigest()[:8], 16).
Each node has vnodes points at h(f"{node}#{i}") for i in 0..vnodes-1.
A key belongs to the node owning the first point ≥ h(key), wrapping to the smallest point. (Point collisions are broken by node name.)

Function

Implement hash_ring. Input: nodes: list[str], vnodes: int, keys: list[str], remove: str. Returns: dict.

Examples

>>> hash_ring(['a', 'b', 'c'], 50, ['user:1', 'user:2', 'user:3', 'user:4', 'user:5', 'user:6'], 'b')

{'moved': 2, 'counts': {'a': 3, 'b': 2, 'c': 1}, 'assignment': {'user:1': 'a', 'user:2': 'b', 'user:3': 'b', 'user:4': 'a', 'user:5': 'a', 'user:6': 'c'}}

Details

Level: Concurrency, resilience patterns, performance constraints and production-style automation.
Roles: Platform Engineer, Backend Engineer, Solutions Architect
Topics: Hashing, Binary search
Tests: 1 public (run with Run), 2 hidden (graded on Submit)
Grading: Exact match of the return value

Python 3.13

import hashlib

def hash_ring(nodes, vnodes, keys, remove):
    assignment = {k: nodes[hash(k) % len(nodes)] for k in keys}
    return {"assignment": assignment, "counts": {}, "moved": 0}

Ctrl/⌘ + Enter runs · Ctrl/⌘ + Shift + Enter submits

Run executes the public tests. Submit grades against public and hidden tests.

Partition keys with a consistent hash ring · Python practice