My company was using AppEngine to host our product but we switched over to AWS (python, nginx/tornado, mongo) last year because of similar problems. On a small

My company was using AppEngine to host our product but we switched over to AWS (python, nginx/tornado, mongo) last year because of similar problems. On a small amount of load the problems you are describing can be high. On a large scale like we have these problems cost a fortune. We new that some of the costs we were incurring were do to bad design on our part (We were all new to No-SQL databases when we started). But after going through our internal cost of resolving these issues versus rewriting our app to use Mongo we decided on the latter. We haven't looked back since...