consistent sharding

reshard.py

def generate_keysets(n_shards, keys):
    n_keys = len(keys)
    shards = []
    shards.append(keys)
    elements_required = n_keys
    shard_to_pop = 0
    for step in xrange(1,n_shards):
        need_count = n_keys // (step+1)
        new_shard = []
        for i in xrange(0,need_count):
            if shard_to_pop == step or len(shards[shard_to_pop]) < elements_required:
                shard_to_pop = 0
                elements_required -= 1
            new_shard.append(shards[shard_to_pop].pop())
            shard_to_pop += 1
        shards.append(new_shard)
    return shards

def generate_shardmap(keysets):
    result = dict()
    for i in xrange(0,len(keysets)):
        for key in keysets[i]:
            result[key] = i
    return result