When one machine can't hold all your data, you shard it. Split it across N nodes. The first question is which shard owns a key. The classic answer: hash the key and take it modulo the shard count.
A deterministic _hash(key) is provided (Python's built-in hash is randomized per process, so we roll a stable one).
_shard_for(key): return the shard index: the hash modulo self.num_shardsclass ShardedDB:
def __init__(self, num_shards):
self.num_shards = num_shards
self.shards = [dict() for _ in range(num_shards)]
def _hash(self, key):
h = 0
for ch in str(key):
h = (h * 31 + ord(ch)) & 0xffffffff
return h
def _shard_for(self, key):
"""Return the shard index that owns this key."""
# TODO: return self._hash(key) % self.num_shards
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
When one machine can't hold all your data, you shard it. Split it across N nodes. The first question is which shard owns a key. The classic answer: hash the key and take it modulo the shard count.
A deterministic _hash(key) is provided (Python's built-in hash is randomized per process, so we roll a stable one).
_shard_for(key): return the shard index: the hash modulo self.num_shardsPress Run Tests or ⌘↩ to check your solution.