500 databases or 1 database with 500 tables or just 1 table with all the records? I currently have an application that is used by a single end customer. For ease of discussion assume the application only needs a single database table for all records. I now need to support multi-tenancy and so in the future I will have about 500 customers using the same database server.

1) A possible solution is to have a separate database for each customer. As there will be around 500 customers that means having MySQL/SQL Server/Oracle/etc... host 500 separate databases. This sounds like overkill for a database server running on an average cloud based server.

2) Another solution is to stick with the single database I already have but to have 500 different tables, one for each end customer. Each customer only averages around 2000 records in their own table. This is easy to implement and I would guess makes it easy to migrate the customer to another server, just move the entire table data over.

3) Lastly I could stick to using a single table in the single database. Instead I add an additional column that identifies the customer the record belongs to. But then the table ends up with about 1,000,000 records which is the aggregate of all 500 customers that average 2,000 each. 

I do not know enough about performance and scaling to know 1, 2, 3 is going to give the best performance. Any ideas?
Having been on the receiving end of this multiple times from COTS applications, I would choose multiple databases almost every time. In this case, I would still choose multiple databases over any other, and here is why:

!This is for the SQL Server related tag and is not transferrable in logic to other RDBMSs!


Standards - each database is setup the same way with the same standard names and tables.
Flexibility - a new customer needs their language to be finnish and a different collation to be used, easy enough since it's in it's own database. Try dealing with that with a single table and everyone's information in it. Making a change for a request or feature but only for a single customer, you'll start to like a database for each customer.
Security - depending on needs, a different login and user for each database to keep security tight.
Automation - since each database is an exact copy (or base tables are exact copies at least), this makes it extremely easy to automate tasks.
Upgrades/Changes - changes and updates can be rolled out for each customer on their specific schedules and needs. If a single upgrade or schema change goes wrong, only a single customer is down and not all customers.
Granularity - ever need to restore older data that may have been accidentally deleted? Yep, much easier to do this when segregated by database rather tan all jumbled together in the same table or restoring a huge database for a few records in a different schema.
Locking and Blocking - if all of the records are in the same table, some type of optimistic locking will need to be used if you don't want too many performance problems of all of the customers attempting to read/write their data at the same time. This is going to lead to more tempdb utilization and make a process much heavier in terms of resources than it should be.


Some of the downsides:


Admin Overhead - if automation is not used and scripts created for re-use... it's going to make completing tasks manually a large effort. If automated or scripted properly, there should be little administrative overhead.
Backups - now there are more databases and your restore strategy has to take that into account. The backup routine that is being used needs to automatically understand that new databases should be backed up.
Disk Space - sure, using individual databases could lead to lower space utilization efficiency. I find this to be a very small downside, almost non-existent but depending on implementation could represent an impact, especially if in the full recovery model.


The pros (IMHO) extremely out-weigh the cons. We don't know your specifics so some of these items might be moot, but there are many different things to think about and I hope I captured most of the big ones with what you'll be needing to use these for.