Tokyo Cabinet (TC) is what I was going to recommend as well. It's crazy fast and quite reliable. It also does zlib compression so your dataset will be smaller t

Tokyo Cabinet (TC) is what I was going to recommend as well. It's crazy fast and quite reliable. It also does zlib compression so your dataset will be smaller than with most other key/value stores. Be careful picking an open source key/value store because a lot of them are kinda half baked right now. (But TC is very solid.) My first attempt would be as suggested above, to use a single instance of TC. If it ever started to get slow or you simply ran out of space you could even put a consistent hash in front of a cluster of machines. Though I wouldn't be surprised if a single machine would be enough for your current needs (20 billion). The hash doesn't have to be very complicated, depending on your key. If your key is just a numeric auto incremented id for example you could implement a "hash" with modulo which just maps 0-x billion to machine 1, x-2x billion to machine 2, etc. If you do this though you'll lose the ability to generate keys to search through your data. If you need to generate keys and your data is distributed I highly recommend sphinx search ( http://www.sphinxsearch.com/ http://www.sphinxsearch.com/ ). Technically, it's a full-text search engine but I use it for normal searching. You can build an index distributed across multiple machines and even multiple cores of multiple machines. For example, if you have 2 boxes with 4 cores each, you can split your data into 8 chunks, 4 of the chunks running on one machine, 4 on the other with a single "distributed index" that ties them all together. When you do a search on your distributed index for say 100 items sorted by date, 8 threads will search the 8 chunks, return the 100 best results and the distributed index will filter out duplicates and return the 100 best results. And it'll do it incredibly quickly. We're using sphinx with mysql. I'm not sure how you'd get the data from TC to sphinx (there may or may not be adapters for that I'm not sure) but if you have to pick between sphinx and TC you'd have to decide what's most important for you, low storage space with very quick lookup or very low latency search. If you need low latency search I suggest you simply use mysql for storage and index your data with sphinx.