The painful part of hash sharding: when you add a node, % num_shards changes for almost every key, so you must rehash and move the data. (This is exactly the pain that consistent hashing was invented to avoid.)
add_shard(): gather all current data, grow the shard count by one, and re-insert every key so it lands in its new shardclass 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 self._hash(key) % self.num_shards
def put(self, key, value):
self.shards[self._shard_for(key)][key] = value
def get(self, key):
return self.shards[self._shard_for(key)].get(key)
def all_items(self):
result = {}
for shard in self.shards:
result.update(shard)
return result
def count(self):
return sum(len(shard) for shard in self.shards)
def add_shard(self):
"""Add a shard and rehash every existing key into the new layout."""
# TODO: snapshot the current pairs with all_items() before anything moves,
# raise self.num_shards by one, and reset self.shards to that many empty
# dicts. Then re-insert every snapshotted pair through put() so each one
# is routed by the new shard count, with nothing lost or duplicated.
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
The painful part of hash sharding: when you add a node, % num_shards changes for almost every key, so you must rehash and move the data. (This is exactly the pain that consistent hashing was invented to avoid.)
add_shard(): gather all current data, grow the shard count by one, and re-insert every key so it lands in its new shardPress Run Tests or ⌘↩ to check your solution.