The first thing I would try is rebuilding the cache. Since you only need to do key-value lookups, there are many (easy) approaches, that can scale better than M

The first thing I would try is rebuilding the cache. Since you only need to do key-value lookups, there are many (easy) approaches, that can scale better than MySQL. You could do JSON files on a filesystem (with some nesting, as you don't want to put 20 million files in 1 dir). Or Redis: 20 million x 1 KB is 20 GB. You will need more with overhead, but a few machines would work. Or Riak (we went > 1 billion items with Riak). But even MySQL should be able to handle this: We had over 100 million records in MySQL (on SSD's) before switching to something else. That seems to be the quickest win to reduce the number of requests, but it will depend on the overlap of your usersets how much this will help.