have you looked at the ndb backend for MySQL cluster? it seems like it would do what you need (that is, you can add nodes, in pairs to scale, and it can handle single-node failures)

another option, I guess, is to get a large dedicated server elsewhere, and use that as the db server; of course, you have latency issues then.

Yes, I do have a huge server in Texas that could be the DB server but I hope to have some low latency cloud based solution.

I haven't looked at NDB + Mysql cluster. Is mysql cluster a free download?

MySQL is free. Last time I used the NDB cluster was probably more than 3 years ago, when MySQL 5 was in beta. At that time, it was a pure in-memory database- the idea is that you had to have at least twice as much ram as data, and you would add nodes in pairs. all data would be mirrored on at least two nodes, and you could add more nodes to get more data.

From what I understand, MySQL cluster now lets you keep some data on disk.

Also consider, just from a cost perspective, anything that you leave on all the time that can use more than 8-16GB ram? you are much better buying and co-locating your hardware. (And this is coming from a guy who rents VPSs. they are a great deal if you need something small or temporary; but EC2 prices are pretty close to 2005 levels; hardware has gotten a lot cheaper since then.)

Mount elastic blocks to hold your db directories and take regular incremental snapshots.