Hashing spreads keys evenly but scatters neighbors everywhere, so a range scan has to hit every shard. Range sharding does the opposite: it splits the key space at boundaries, keeping ordered keys together (great for range queries, at the risk of hot spots).
Given ascending boundaries, shard i holds keys < boundaries[i], and the last shard holds everything from the final boundary up.
_shard_for(key): return the shard index for key using the boundaries (put/get are implemented)class RangeShardedDB:
def __init__(self, boundaries):
# boundaries: ascending list. shard i holds keys < boundaries[i];
# the final shard holds keys >= the last boundary.
self.boundaries = boundaries
self.shards = [dict() for _ in range(len(boundaries) + 1)]
def _shard_for(self, key):
"""Return the shard index for an ordered key using the range boundaries."""
# TODO: scan self.boundaries in ascending order and answer with the
# position of the first boundary the key sits strictly below.
# A key equal to a boundary belongs above it, and a key that is below
# no boundary at all belongs in the final shard.
pass
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)
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Hashing spreads keys evenly but scatters neighbors everywhere, so a range scan has to hit every shard. Range sharding does the opposite: it splits the key space at boundaries, keeping ordered keys together (great for range queries, at the risk of hot spots).
Given ascending boundaries, shard i holds keys < boundaries[i], and the last shard holds everything from the final boundary up.
_shard_for(key): return the shard index for key using the boundaries (put/get are implemented)Press Run Tests or ⌘↩ to check your solution.