If you are sharding, I recommend "distributed hash table" http://en.wikipedia.org/wiki/Distributed_hash_table with a twist - make sure each physical machine participates in the table many times (1000). This way you can relocate small pieces of data to balance the load without affecting other machines.