Instead of using normal hashing you can use consistent hashing so you don't need to move that many users. Here's a post explaining it: http://www.spiteful.com/2008/03/17/programmers-toolbox-part-...