Key doesn't exist error returned during repartitioning

[vsreekanti]

When nodes are added or removed from the cluster, we incrementally repartition data by gossiping keys to the new sets of nodes responsible for them. However, we immediately change the hash ring to reflect the new cluster state. As a result, requests will sometimes be sent to an old node once the key has been gossiped to a new node or to a new node that hasn't yet received the key. The result is that the user gets a "key does not exist" error.

We probably want to maintain both the old and new hash rings, so we can appropriately forward a request to the right node when it is sent to the wrong one. (Of course, we should be careful about making sure we don't infinite loop between the two if a key actually doesn't exist.)

Joe also proposed something related to multiple hash rings, which change at different rates (à la LSM), but I don't completely understand how this would work.