You may have noticed that the OP's requirements were: * a REST interface * sharding The costs of SQL Server are unbelievably high, and which you can do horizontal partitioning and sharding, Riak is designed to be used in this manner. On the other hand, re: SQL Server according to this article the "horizontal partitioning feature requires Enterprise or Datacenter licenses which have a retail price of 27,495 and 54,990 per processor." I think the OP made a wise choice. http://www.infoq.com/news/2011/02/SQL-Sharding
Apparently really high-end clustered databases solve this problem correctly, i.e., the schema is extended to specify where any record can be found, the cluster uses that to work out a minimally-stupid query plan, and record->shard mapping becomes merely a tuning decision. I've never had the opportunity to work with one. But I'm not bitter.
Given that a pair of 2TB drives is less than $250 on ebuyer right now, 2TB of data is not 'big data'. You could comfortably stuff that in any decent database (SQL Server for example, I'm sure PostgreSQL would work too).
Just because a tiny machine on slicehost isn't big enough doesn't mean that your data won't fit in a normal database.