The first thing I have to say about adding nodes is to not do it. Salvatore Sanfilippo wrote a great post about sharding Redis, and his recommendation is that re-hashing is difficult and instead you should create a large number of small Redis instances up front, that way you don’t have to add more nodes down the road.
Why not going the extra mile and use consistent hashing then? This if using Gizzard or riak_core is not an option.
Original title and link: Redis Sharding with Erlang (NoSQL databases © myNoSQL)