Each user has some small arbitrary information associated with them, with potentially tens of millions of users (and no doubt more in the future). There's not really a structure due to the nature of the project, each user needs personalised information and structure associated to them.

I don't think that amount of information is really suitable for a database? It may be larger in some cases too, so there's not guarantees I can even make about size.

Document stores shine in that case. Depending on the exact case something like postgres's HSTORE, couchdb, couchbase, mongodb or similar would work. They're all capable of storing arbitrary json docs under a given key and efficiently retrieve it. Partial indexing is possible as well.

Ah, sorry, I missed that you were still referring to the 'filesystem as a database'-project :).