Which one to use? InnoDB Replication or MySQL Cluster? I am building a url shortener and I use InnoDB as the storage engine for link data. I will start with a single VPS containing both application instance and MySQL database instance on the same Virtual Machine. I want the application to be easily scalable, I want to be able to add new nodes and make the system perform better as easily as possible when needed. 

I have been reading about MySQL Cluster and MySQL Replication, but I haven't been able to decide on which one to use. You can imagine that (a popular) url shortener will be both write and read intensive. What is the structure that you would use in such a case? Would you go for cluster or replication?

Then based on the choice of cluster or replication, what is the infrastructure/configuration that I am supposed to have in order to be able to expand from a single innoDB engined Database to a cluster or replication structure? I want to start correctly, I don't want to be stucked in a situation where I can not expand/improve the database system when I need to.

Thanks A lot

sr.
MySQL Cluster possibly a good fit for you because of your key:value lookup traffic pattern. NDB is traditionally poor with joins or compex queries. I would say however that it is not the same as MySQL and has caveats that you need to understand before jumping into bed with it. It's shared nothing architecture means that you should operate it at scale with decent (and inclusive redundancy) network infrastructure. It is perhaps worth a proof of concept project to fit it out and test it. The guys at severalnines have configuration tools to get you up and running.  

Mongo isn't a bad fit either and as you state you cannot give up A_I, why not? What about values like (1902jdd,"/page/id") needs and auto inc? Mongo documents are schemaless and you add superfluous data to a document where you see fit and query in a key:value style too. Statistics moving forward would put you into the map reduce world which could be fun.

Keeping with traditional RDBMS and requiring performance you should look at memcached and the mysql memcached api for rapid key:value access to the data which would retain the relational aspect for aggregation queries (select [count|max|avg]... group by order by blah, blah...