Why am I writing a data store? Because my online backup service needs to store 200,000 key-value pairs for every $/month of revenue, and existing data stores aren't optimized very well for very large numbers of very small records.
Really? Every one of the dozens of open-source key/value stores is so far off from your requirements that they just don't work for you?