Route Tenants With a Hash Ring
Tenants are spread across database shards by a consistent hash ring that two services, in two languages, must compute identically. The README has the ring's rules and why every routing change is a data migration. Build shards.py with the assistant, and judge each suggestion by what it would do to tenants' data.
shards.py1 of 3
Files
shards.py
Python · Editableimport bisect
import hashlib
def point(key):
"""A position on the ring: the first 8 bytes of SHA-256, big-endian. The Go billing service computes the same."""
raise NotImplementedError
class ShardRing:
"""Maps tenants to database shards with consistent hashing."""
def __init__(self, shards, vnodes=100):
self.vnodes = vnodes
self.points = [] # sorted ring positions
self.owner = {} # position -> shard
self.pins = {} # tenant -> shard, while a tenant's data is being moved
for shard in shards:
self.add_shard(shard)
def add_shard(self, shard):
raise NotImplementedError
def shard_for(self, tenant):
position = point(tenant)
raise NotImplementedError
from collections import Counter
from shards import ShardRing, point
TENANTS = [f"tenant-{n}" for n in range(20_000)]
SHARDS = ["db-1", "db-2", "db-3"]
def test_point_matches_the_billing_service():
assert point("tenant-42") == 17806449257003904200
def test_every_tenant_gets_a_shard():
ring = ShardRing(SHARDS)
assert {ring.shard_for(t) for t in TENANTS} == set(SHARDS)
def test_load_is_roughly_even():
ring = ShardRing(SHARDS)
counts = Counter(ring.shard_for(t) for t in TENANTS)
assert max(counts.values()) < 1.25 * len(TENANTS) / len(SHARDS)
def test_tenants_past_the_last_point_wrap_to_the_first():
ring = ShardRing(SHARDS)
beyond = next(t for t in TENANTS if point(t) > ring.points[-1])
assert ring.shard_for(beyond) == ring.owner[ring.points[0]]
def test_adding_a_shard_moves_only_its_share():
before, after = ShardRing(SHARDS), ShardRing(SHARDS + ["db-4"])
moved = [t for t in TENANTS if before.shard_for(t) != after.shard_for(t)]
assert {after.shard_for(t) for t in moved} == {"db-4"}
assert len(moved) < 0.35 * len(TENANTS)
def test_pinned_tenant_stays_put():
ring = ShardRing(SHARDS)
home = ring.shard_for("tenant-7")
target = next(s for s in SHARDS if s != home)
ring.pins["tenant-7"] = target
assert ring.shard_for("tenant-7") == target
# Tenant Shards
About 4,000 tenants share three Postgres shards. ShardRing (shards.py) decides which shard holds each tenant's data, using consistent hashing with virtual nodes. The API in Python and the billing service in Go both route with it, so they must agree on every tenant.
## Rules
- point is the first 8 bytes of SHA-256 of the key, read as a big-endian integer. Both services use exactly this.
- Each shard owns vnodes points on the ring, at point("<shard>#<i>"). A tenant belongs to the first point at or after its own position, wrapping around past the last point.
- Load should be roughly even: no shard more than 25% over its share.
- Adding a shard moves only the tenants the new shard takes over.
- A pinned tenant routes to its pin, whatever the ring says. Pins hold a tenant in place while its data is copied.
## Operational Stakes
- A routing change is a data migration. Every tenant whose shard changes must have its rows copied first, under a pin, or its next request reads an empty shard.
- If the two services ever disagree about a tenant, the API writes rows that billing never sees.
The tests are in test_shards.py.
Test Output
No runs yet.