Consistent Hashing

Background. A consistent-hash ring spreads keys over workers. Each worker sits at several points on a circle of positions, and a key goes to the worker whose point comes first at or after the key's own position. A worker that joins or leaves then changes the worker of only the keys next to its own points.

Implement HashRing in ring.py: HashRing(points_per_worker), add_worker(worker_id), remove_worker(worker_id) and worker_for(key).

Positions come from position(text) in ringhash.py: an integer from 0 to RING_SIZE - 1, where RING_SIZE is 2 ** 32.

• add_worker(worker_id) puts points_per_worker points on the ring for the worker: point i sits at position(f"{worker_id}:{i}"), for i from 0 to points_per_worker - 1. It is never called for a worker already on the ring.
• remove_worker(worker_id) takes every point of the worker off the ring. For a worker not on the ring it does nothing and raises nothing.
• worker_for(key) returns the worker of the first point whose position is at least position(key). When no point is that high, it wraps around and returns the worker of the lowest point. On a ring with no points it returns None.
• Two points can share a position. They are taken in order of worker id, plain str order ("c10" before "c9"): a key that reaches that position goes to the smaller id, and once that worker is removed, to the other.

Example

ring = HashRing(2)
ring.add_worker("oak")
ring.add_worker("elm")
ring.add_worker("ash")
ring.worker_for("order-100")  # "ash"
ring.worker_for("order-112")  # "oak"
ring.worker_for("order-104")  # "elm": no point is that high, so the lowest point, elm:0
ring.remove_worker("ash")
ring.worker_for("order-100")  # "oak": ash:0 is gone, and oak:0 comes next

The points and keys in ring order:

| On the ring | position() | |---|---| | point elm:0 | 98,977,715 | | key order-100 | 760,767,782 | | point ash:0 | 904,903,776 | | key order-112 | 1,610,222,734 | | point oak:0 | 2,073,473,868 | | point ash:1 | 2,078,700,507 | | point elm:1 | 2,154,310,927 | | point oak:1 | 3,460,922,416 | | key order-104 | 3,910,197,293 |

Notes

• points_per_worker is 1 to 200. A worker id is 1 to 30 characters of ASCII letters, digits, - and _; a key is any string of 0 to 100 characters, the empty string included.
• Several rings can exist at once, each with its own workers.
• On the starter, all 8 tests in tests/test_part1.py fail.

Done when Submit goes green.