It looks like you're using SHA1 as your hash algorithm which isn't a great choice for sharding. Look into using a consistent hashring algorithm. Basically you want to minimize the number of keys you need to redistribute if you add/remove nodes.
https://pypi.python.org/pypi/hash_ring/What would be cooler than this would be to port the CRUSH algorithm to python. CRUSH is what Ceph (distributed file system) uses to map data to storage servers. This allows you to define a 'map' of how you want data distributed - i.e by rack, row, or datacenter and it can handle replicas, failures, and overloaded systems as well. Whitepaper: http://ceph.com/papers/weil-crush-sc06.pdf
