We added a fourth cache server and three quarters of our keys moved

Our storefront is a PHP application, and its product pages are cached in memcached across three servers. Two weeks before the peak season we added a fourth, at eleven on a Monday morning, so that we would have more room for the sale. Within a minute the cache hit rate fell from ninety seven percent to about a quarter, the product database's read load went up more than twenty times, and product pages timed out for about eighteen minutes until the cache had filled again.

Nothing in memcached had failed. The four servers were up, and the three old ones still held every item they had held at ten fifty nine.

The application uses the PHP Memcached extension, and the extension decides which server holds a key with its default distribution, which is modulo. It hashes the key and divides by the number of servers, and the remainder picks the server. With three servers, a key lives on hash modulo 3. With four, on hash modulo 4. Those two agree for only one hash in four, so adding one server sent three quarters of every lookup to a server that had never seen that key. The old copies were still in memory and nothing would ever ask for them again.

With consistent hashing, adding a fourth server moves roughly the quarter of keys that the new server takes over, and the rest stay where they were. The extension supports it through the option OPT_LIBKETAMA_COMPATIBLE, which switches the distribution to ketama. We had never turned it on, and the three servers had not changed since they were first set up.

We turned it on at four on a Sunday morning, because changing the distribution moves almost every key one last time. Cache servers are now added or removed only at that hour, one at a time, with the hit rate and the database's read load on the screen. The capacity plan for the product database now assumes a cold cache, because that is the load it carried for eighteen minutes on a Monday morning in front of our customers.

We had treated the cache as spare room we could add to. With modulo hashing, every server we added changed where almost everything lived.

– Sergey Shinder