Você pode começar lendo estes artigos:
Multi tenant storage with amazon dynamodb
Multi tenancy and cloud
Mas acima de tudo, não importa onde está hospedado. Oq diferencia é a oferta de produtos que a empresa de cloud vai te oferecer pra facilitar a arquitetura. Você pode perguntar pra Locaweb como proceder numa arquitetura assim, etc e tal.
Eu atualmente trabalho com Amazon EC2 e meu banco de dados é NoSQL, nunca trabalhei com multi tenant em base relacional como o MySQL, mas acredito que você pode fazer teste local (prova de conceito) simulando dois potenciais clientes, dado que teus clientes vão utilizar o mesmo schema:
- sobe duas instâncias do web server, cada uma com um nome específico, como se fosse cada cliente
- cria dois banco de dados diferentes no MySQL, sendo que o nome de cada um tem que ser exatamente o mesmo nome da instância do web server
- dentro da aplicação, você precisa conectar no banco correto a partir do nome da instância
Tenta seguir estes passos, talvez deve funcionar no teu caso, e se funcionar, é questão de replicar isso no cloud de forma mais adequada. Entretanto, caso você no futuro precise que cada cliente tenha schema de dados diferente, é muito provável que terá que partir pra uma solução NoSQL, como por exemplo MongoDB.