I would go with Google cloud SQL which gives you the power of MySQL as a service. It has some powerful options and you can use it both from google app engine and google compute engine. Of course, that you can try amazon SQL options as well at: http://aws.amazon.com/rds/ which contain a nice sets of RDSs. If you wish noSQL solutions there are many options out there:
- Google datastore - It's a powerful technology that bring you lots of power.
- Amazon - http://aws.amazon.com/nosql/
- http://tour.mongohq.com/